Quasi-Linear Size PCPs with Small Soundness from HDX

Understand

We construct 2-query, quasi-linear size probabilistically checkable proofs (PCPs) with arbitrarily small constant soundness, improving upon Dinur's 2-query quasi-linear size PCPs with soundness $1-\Omega(1)$.

• As an immediate corollary, we get that under the exponential time hypothesis, for all $\epsilon>0$ no approximation algorithm for $3$-SAT can obtain an approximation ratio of $7/8+\epsilon$ in time $2^{n/\log^C n}$, where $C$ is a constant depending on $\epsilon$.
• Our result builds on a recent line of independent works by Bafna, Lifshitz and Minzer, and Dikstein, Dinur and Lubotzky, that showed the existence of linear size direct product testers with small soundness.
• The main new ingredient in our proof is a technique that embeds a given 2-CSP into a 2-CSP on a prescribed graph, provided that the latter is a graph underlying a sufficiently good high-dimensional expander (HDX).