Mitali Bafna, Massachusetts Institute of Technology

Abstract

The PCP Theorem [FGLSS,AS,ALMSS] is a cornerstone of theoretical computer science, with many applications in hardness of approximation, cryptography and interactive protocols. 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 eps>0 no approximation algorithm for 3-SAT can obtain an approximation ratio of 7/8+eps in time 2^{n/log^C n}, where C is a constant depending on eps. Our result builds on a recent line of independent works, by Bafna, Lifshitz, Minzer, and Dikstein, Dinur, Lubotzky that show 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 PCP construction into a PCP on a prescribed graph, provided that the latter is a graph underlying a sufficiently good high-dimensional expander. Towards this end, we use ideas from fault-tolerant distributed computing, and more precisely from the literature of the almost everywhere agreement problem starting with the work of Dwork, Peleg, Pippenger, and Upfal (1986). We show that graphs underlying HDXs admit routing protocols that are tolerant to adversarial edge corruptions, and in doing so we also improve the state of the art in this line of work. 

Based on joint work with Dor Minzer and Nikhil Vyas and Appendix by Zhiwei Yun.

See: https://theory.cs.rutgers.edu/theory_seminar