Orr Paradise
Abstract of Master Thesis (Weizmann Inst., 2019)
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 NP have PCPs that are both smooth and strong,
are of polynomial length, and can be verified based on a constant number of
queries. This is achieved 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 NP has a smooth
strong canonical PCP of Proximity (PCPP), meaning that there is an
efficiently computable bijection of 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).
Submitted to the Feinberg Graduate School
of the Weizmann Institute of Science, May 2019.
Available: the thesis (in PDF file).
Back to Oded Goldreich's homepage.