# 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? Aug 8, 2020 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? Aug 8, 2020 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”. Aug 8, 2020 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)$. Aug 12, 2020 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? ... Aug 13, 2020 at 11:06