# Best known asymptotic PCP sizes / 3-SAT

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.

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.
• 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. Oct 31, 2018 at 3:20