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.

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:

- A PCP is
*strong*if it rejects an alleged proof of a correct claim with probability proportional to its distance from some correct proof of that claim. - A PCP is
*smooth*if each location in a proof is queried with equal probability.

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.