Smooth and strong PCPs (Q2029773)

Probabilistically checkable proofs (PCP) play an important role in the area of randomized algorithms. Intuitively, such a proof can be checked by a randomized algorithm whose randomness of the read number of bits of the proof is bounded in some way. Acceptance of correct, respectively, rejection of false proofs must happen with very high probability. Classically, corect proofs should be always accepted while incorrect ones should be rejected with a probability \(\ge\frac{1}{2}\). The prominent PCP theorem (Arora et al.) states that \(\mathrm{PCP}[O(\log n), O(1)] = \mathrm{NP}\), where the notion \(\mathrm{PCP}[a(n),b(n)]\) is the set of decision problems for which PCPs exist that can be verified in polynomial time using at most \(a(n)\) random bits and reading at most \(b(n)\) bits of the proof. This paper covers two new features of such proofs: strong (alleged proofs of correct claims are rejected with probability proportional to its distance from some correct proof of that claim) and smooth (each location in a proof is queried with equal probability) PCPs. As a main result, NP is shown to have PCPs that are always smooth and strong, are of polynomial length and can be verified via a constant number of queries. From this result, one deduces that the hardness of approximating stable 3SAT instances with bounded variable occurrence is true (here stable refers to that the number of clauses that are falsified by an assignment is proportional to its distance from a satisfying assignment under the Hamming metric). On the first twenty pages, the author gives a good introduction and quite elaborative overview of the relevant techniques and tools that are used. After a careful explanation of the technicalities and challenges, he gives a thorough proof outline. Then, he finishes with presenting future directions. The main technicalities required are a thorough analysis of the original proof by Arora et al. and further analysing Hadamard and Reed-Muller-based PCPs. The main result even shows that for NP-languages there always exist smooth strong canonical PCPs of Proximity (PCPPs). This means that there exist efficient bijections between NP witnesses and correct proofs. The last ten pages yield more details of the proofs in the form of a technical appendix that allowed for a shorter presentation in the main part.