Smooth and Strong PCPs

May 14, 2019 12:45 PM
Schreiber 309, Tel Aviv University

Probabilistically checkable proofs (PCPs) can be verified based only on a constant amount of random queries, such that any correct claim has a proof that is always accepted, and any incorrect claim is rejected with high probability regardless of the given alleged proof. But what about incorrect proofs of correct claims? In a strong PCP, an alleged proof is rejected with probability proportional to its distance from a correct proof. For applications to hardness of approximation, it is useful to have strong PCPs in which each bit in the proof is equally likely to be queried. This natural property is called smoothness.

Recently, Dinur, Gur and Goldreich (ITCS, 2019) showed that any NP language has strong PCPs of polynomial length. However, their construction is inherently non-smooth. We construct polynomial-length PCPs for NP that are simultaneously smooth and strong. This is achieved by refining the proof of the PCP theorem of Arora and Safra (JACM, 1998) and Arora, Lund, Motwani, Sudan and Szegedy (JACM, 1998), and enhancing it with new tools.

In this talk, I will introduce smooth and strong PCPs, explain the main result and some of the ideas in its proof. I will also talk about its applications to hardness of approximation. No prior knowledge of PCPs is assumed.

Based on “Smooth and Strong PCPs”, Orr Paradise, 2019.