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.

Added motivation (10-May-19): PCP, like Property Testing in general, embody a fascinating relation between the global (interpreted as being far from a set) and the local (interpreted as detecting violations in small local views). This relation (of global to local) comes to an extreme in POTs (Proximity Oblivious Testers), where the distance to a set is reflected in the fraction of violating local views; that is, rather than only saying that far (in the global sense) implies many (or a majority of) violations in the local views, we say that the global distance is reflected in the fraction of violating local views. This is how global-vs-local comes to an extreme in Property Testing, but the question is what is the PCP analogue.

My answer is that it is strong and smooth PCPs. The point is that strong alone does not do it, since PCPs (unlike property testers of a fixed set/property) allows for padding that makes the global distance meaningless (unless the set is empty). This is what DGG capitalizes on; indeed, the translation of the PCP result to property testing (provided in DGG) is viewed (in DGG) as demonstrating the crucial role of encoding/representation in property testing (a feature which has been known for the very start of the area but is demonstrated more dramatically in DGG). A Honest to God result for PCP requires that the global distance is an honest/natural one (and it is not natural not to distinguish between meaningful bits and meaningless bits in the encoding). Alternatively, when defining distance, one should let the distance reflects the coverage of the local views (which is Irit's way of looking at this).

The same reasoning translates to maxSAT/CSPs: Here Irit's view is (even) more to the point, since the local constraints are not our choice (as in case we design the verifier) but are rather the description of the instance. So a honest to god global-vs-local phenomenon must refer to variables according to the number of constraints they appear in. Alternatively, one may insist on bounded-occurrences (as a natural feature of instances) and ask about the strong global-to-local relation.

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.