Smooth and Strong PCPs

May 22, 2019 10:30 AM
Rothberg B201, Edmond J. Safra Campus, The Hebrew University of Jerusalem

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 give an overview of 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.