9
$\begingroup$

What are the best known asymptotic upper bounds on sizes of probabilistically checkable proofs? Ideally, I am looking for a contemporary survey on this broad question, but if there is none, I am especially interested in inapproximability of 3-SAT.

Let 7/8+ε-3-SAT be 3-SAT with the promise that if 7/8+ε fraction of the clauses are satisfiable, then the instance is satisfiable. What are the best known reductions of 3-SAT with $n$ clauses to 7/8+ε-3-SAT? For example, is there a reduction using $O(n \log n)$ clauses? ($O(n)$ clauses is an open problem.) A reduction in uniform quasilinear size NC? What is the dependence on $ε$, including when $ε→0$? Is there a known linear size (dependent on $ε$) reduction of (1-ε)-3-SAT to 7/8+ε-3-SAT, and if not, do we have better bounds for (1-ε)-3-SAT? Even a partial answer would be interesting.

Also, while it would perhaps make the question too broad, I should mention that another important issue here are the constant factors, which due to techniques like the long code are commonly infeasibly large.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

The state-of-the-art for PCPs that yield a reduction to $(\frac{7}{8}+\varepsilon)$ 3-SAT (even for sub-constant $\varepsilon$) are those of Dana Moshkovitz and Ran Raz, which have length $n^{1 + o(1)}$. I do not know, however, if anyone tried to compute the exact dependence of the length on $\varepsilon$, or the computation complexity of the reduction. Their main technical result was simplified later by Irit Dinur and Prahladh Harsha.

If you are interested in short PCPs with a constant number of queries that do not necessarily give optimal hardness-of-approximation reductions (a.k.a. "high-error PCPs"), then the state-of-the-art result is PCPs of length $n\cdot \mathrm{poly}\log n$ due to Eli Ben-Sasson and Madhu Sudan and its improvement by Dinur. Again, I do not know if anyone what is the exact complexity of computing the reduction.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you; both parts were helpful. I gather that quasilinear size PCP with O(1) queries and constant error remains an open problem. $\endgroup$
    – Dmytro Taranovsky
    Commented Oct 31, 2018 at 0:25
  • $\begingroup$ No, that actually follows from the work of Ben-Sasson and Sudan. It is an open problem to get such PCPs with sub-constant error. $\endgroup$
    – Or Meir
    Commented Oct 31, 2018 at 0:39
  • 1
    $\begingroup$ I looked some more and Dinur 2007 extends the paper you cited in the second paragraph to show $SAT ∈ PCP_{\frac{1}{2},1}[\log_2 n + O(\log \log n), O(1)]$. If I understand correctly, this implies a reduction of 3-SAT to some quasilinear size $1-ε$ 3-SAT, but the result you cited in the first paragraph is nonredundant because it gives us $7/8+ε$ and more. $\endgroup$
    – Dmytro Taranovsky
    Commented Oct 31, 2018 at 3:20
  • $\begingroup$ Yes, that's correct. I forgot to mention Dinur's result, I'll add it to the answer. $\endgroup$
    – Or Meir
    Commented Oct 31, 2018 at 9:01

Your Answer

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

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