5
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Moshkovitz-Raz appears to give a "quasiquadratic" blow-up, $O(n^{2+o(1)})$. $\endgroup$
    – Yuval Filmus
    Feb 7, 2017 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, 2018 at 4:10
  • $\begingroup$ This indeed sounds likely. $\endgroup$
    – Yuval Filmus
    May 11, 2018 at 6:26

2 Answers 2

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ assuming Hypothesis 5 can we prove ETH-hardness of approximating Exct set cover. cstheory.stackexchange.com/questions/37461/… $\endgroup$
    – xyz
    Feb 7, 2017 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, 2017 at 14:06
  • $\begingroup$ Which linked problem? Can you send me a reference for that too? $\endgroup$
    – xyz
    Feb 8, 2017 at 0:32
  • $\begingroup$ cstheory.stackexchange.com/q/37461/6973 . ​ No, but I just wrote it up there. ​ ​ ​ ​ $\endgroup$
    – user6973
    Feb 9, 2017 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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