Smooth and Strong PCPs

by Orr Paradise

Oded's comments

I have been waiting for this posting for a while. It resolved a problem left open in my paper with Irit and Tom, showing that one can obtain strong PCPs that are also smooth, unlike the highly-unsmooth strong PCPs that are easily obtained in the former paper.

The original abstract

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 incorrect claims are rejected with high probability (regardless of the given alleged proof). We consider two possible features of PCPs:

We prove that all sets in $\mathcal{NP}$ have a smooth and strong PCP of polynomial length that can be verified based on a constant number of queries. We do so by following the proof of the PCP theorem of Arora, Lund, Motwani, Sudan and Szegedy (JACM, 1998), providing a stronger analysis of the Hadamard and Reed--Muller based PCPs and a refined PCP composition theorem. In fact, we show that any set in $\mathcal{NP}$ has a smooth strong *canonical* PCP of Proximity (PCPP), meaning that there is an efficiently computable bijection of $\mathcal{NP}$ witnesses to correct proofs.

This improves on the recent result of Dinur, Gur and Goldreich (ITCS, 2019) that constructs strong canonical PCPPs that are inherently non-smooth. Our result implies the hardness of approximating the satisfiability of "stable" 3CNF formulae with bounded variable occurrence, proving a hypothesis used in the work of Friggstad, Khodamoradi and Salavatipour (SODA, 2019). Here *stability* means that the number of clauses violated by an assignment is proportional to its distance from a satisfying assignment (in the relative Hamming metric).

See ECCC TR19-023.


Back to list of Oded's choices.