# ETH-Hardness of $Gap\text-MAX\text-3SAT_{c}$

The PCP theorem can be stated like this :

There is a polynomial time reduction from SAT to $Gap\text-MAX\text-3SAT_{c}$ i.e. there is a reduction that maps an instance $\phi$ of SAT to an instance $\psi$ of $Gap\text-MAX\text-3SAT_{c}$ such that

• If $\phi$ is satisfiable, so is $\psi$.
• If $\phi$ is unsatisfiable, then $OPT(\psi) \leq c$, i.e., there is no assignment to the variables of $\psi$ that satisfies more than a fraction $c$ of the clauses.

What is the blow-up of this reduction? That is, what are the parameters of the instanceof $Gap\text-MAX\text-3SAT_{c}$ in terms of parameter of the given instance of SAT. Is the blow-up linear?

• Moshkovitz-Raz appears to give a "quasiquadratic" blow-up, $O(n^{2+o(1)})$. Feb 7, 2017 at 13:23
• @YuvalFilmus Does the blow-up not depend on the choice of $c$? Intuitively, I would guess that as $c$ gets closer to 7/8, the blow-up gets larger. Is this not correct? May 11, 2018 at 4:10
• This indeed sounds likely. May 11, 2018 at 6:26

I think the best known result is that the blow-up can be quasi-linear (the new instance has size $n\cdot(\log n)^{O(1)}$). This is given in Dinur's 2007 paper (Thm 8.1), which is also cited by the Moshkovitz-Raz paper mentioned by Yuval Filmus.

As far as I know it is still open if the blow-up can be brought down to linear. Some people call this the Linear PCP conjecture, see e.g. the recent paper by Bonnet, Egri and Marx

Theorem 7 achieves polylogarithmic blow-up. ​ As the footnote at the end of the previous page alludes to, there's a simple randomized reduction which goes from m clauses to O(n) clauses and preserves satisfying assignments with certainty. ​ Based on that paper's discussion of Gap-ETH (Hypothesis 5 and the page after that), nothing tighter seems to be known. ​ Also see Corollary 11.

• assuming Hypothesis 5 can we prove ETH-hardness of approximating Exct set cover. cstheory.stackexchange.com/questions/37461/…
– xyz
Feb 7, 2017 at 13:53
• We can do that even without "assuming Hypothesis 5", since since even finding a feasible solution to the linked problem is ETH-hard. ​ ​
– user6973
Feb 7, 2017 at 14:06
• Which linked problem? Can you send me a reference for that too?
– xyz
Feb 8, 2017 at 0:32
• cstheory.stackexchange.com/q/37461/6973 . ​ No, but I just wrote it up there. ​ ​ ​ ​
– user6973
Feb 9, 2017 at 12:51