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?

  • $\begingroup$ Moshkovitz-Raz appears to give a "quasiquadratic" blow-up, $O(n^{2+o(1)})$. $\endgroup$ – Yuval Filmus Feb 7 '17 at 13:23
  • $\begingroup$ @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? $\endgroup$ – Mike Battaglia May 11 '18 at 4:10
  • $\begingroup$ This indeed sounds likely. $\endgroup$ – 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.

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

| cite | improve this answer | |

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.