# 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)})$. – Yuval Filmus Feb 7 '17 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? – Mike Battaglia May 11 '18 at 4:10
• This indeed sounds likely. – Yuval Filmus May 11 '18 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.