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.
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:
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.