Smooth and Strong PCPs

摘要

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.We prove that all sets in 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 has a smooth strong *canonical* PCP of Proximity (PCPP), meaning that there is an efficiently computable bijection of 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).