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

- 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 $\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.