# Disproving $\oplus$ETH by reducing $\oplus k$-SAT with $n$ variables and $m$ clauses to planar graph with $o(m^2)$ vertices?

In this question and its answer, they discuss about reducing CNF-SAT with $$n$$ variables and $$m$$ clauses to a (problem on) planar graph $$G=(V,E)$$ with $$|V|$$ as small as possible. It is said that the best known reduction has $$|V| = m^2$$, and that if a better reduction with $$|V| \in o(m^2)$$ is found, that would refute ETH.

There is a reduction from $$\oplus k$$-SAT with $$n$$ variables and $$m$$ clauses to $$\oplus$$VERTEX COVER where the output graph $$G=(V,E)$$ is planar and has $$|V| = 51(k+1)nm$$. Such reduction clearly meets the $$|V| \in o(m^2)$$ requirement when $$k$$ is a constant and $$m$$ is superlinear in $$n$$.

Question
Can the same line of reasoning made within the linked question be applied here in order to refute $$\oplus$$ETH, or am I missing some important detail?

• What is $\oplus$ETH? – Emil Jeřábek Aug 8 '20 at 10:59
• @EmilJeřábek: In the paper arxiv.org/pdf/1112.2275.pdf, $\oplus$SETH is mentioned. From page 3: "Formally, $\oplus$SETH asserts that, for all $\epsilon$ < 1, there exists a (large) integer $k$ such that $\oplus k$-SAT cannot be computed in time $O(2^{\epsilon n})$". Unless I'm wrong, such definition is to $\oplus k$-SAT as the SETH is to $k$-SAT. Then, I've imagined that if $\oplus$SETH was introduced, then so was $\oplus$ETH... Is it the case that, while $\oplus$SETH exists as a conjecture, there is no such thing as $\oplus$ETH? – Giorgio Camerani Aug 8 '20 at 12:12
• I didn’t say that it didn’t exist. I simply asked what it was. “Exists” can mean anything between “someone mentioned it in passing in one obscure paper”, and “it is widely known in the field”. – Emil Jeřábek Aug 8 '20 at 13:19
• Why do you assume that $n = o(m)$? To my understanding, for the purposes of ETH (not sure about $\oplus ETH$) we should assume that $m = \Theta(n)$. – Laakeri Aug 12 '20 at 14:30
• @Laakeri: Maybe you're right, but then why in the linked question and its answer there is no such limitation? They pose no constraints on $m$. I imagine they implicitly refer to the Sparsification Lemma, but even in such case there is something unclear to me: suppose they take a CNF with unbounded $m$ and reduce it to a subexponential number of CNFs having $m' = \Theta(n)$, then they turn each of such CNFs into a planar graph to take profit of its sublinear treewidth. Even if this is their reasoning, why they write $|V| \in o(m^2)$, being $m$ the number of clauses of the original formula? ... – Giorgio Camerani Aug 13 '20 at 11:06