Smooth and strong PCPs
type: Item
instance of: scholarly article
title: Smooth and strong PCPs
zbMATH Open document ID: 1485.68101
author: Orr Paradise
published in: Computational Complexity
publication date: 2021-06-04T00:00:00Z
review text: 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 r…
reviewed by: Arne Meier
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 7355180
zbMATH Keywords: interactive and probabilistic proof systems
zbMATH Keywords: probabilistically checkable proofs
zbMATH Keywords: hardness of approximation
MaRDI profile type: Publication
full work available at URL: s00037-020-00199-3
OpenAlex ID: W3119413233
cites work: Proof verification and the hardness of approximation problems
cites work: Probabilistic checking of proofs
cites work: Center-based clustering under perturbation stability
cites work: Q5368726
cites work: Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
cites work: Short PCPs with Polylog Query Complexity
cites work: Lifts, discrepancy and nearly optimal spectral gap
cites work: Are stable instances easy?
cites work: Self-testing/correcting with applications to numerical problems
cites work: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms
cites work: Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
cites work: The PCP theorem by gap amplification
cites work: PCP characterizations of NP: toward a polynomially-small error-probability
cites work: Composition of Low-Error 2-Query PCPs Using Decodable PCPs
cites work: Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
cites work: A threshold of ln n for approximating set cover
cites work: Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-MEANS
cites work: Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length
cites work: Introduction to Property Testing
cites work: Strong Locally Testable Codes with Relaxed Local Decoders
cites work: Lower bounds for linear locally decodable codes and private information retrieval
cites work: Locally testable codes and PCPs of almost-linear length
cites work: On the Power of Relaxed Local Decoding Algorithms
cites work: Relaxed Locally Correctable Codes
cites work: Non-interactive proofs of proximity
cites work: Probabilistically Checkable Proofs of Proximity with Zero-Knowledge
cites work: On the efficiency of local decoding procedures for error-correcting codes
cites work: Combinatorial Construction of Locally Testable Codes
cites work: Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
cites work: Two-query PCP with subconstant error
cites work: Optimization, approximation, and complexity classes
cites work: Q4527015
cites work: Q3059320
cites work: Locally decodable codes
DOI: 10.1007/S00037-020-00199-3
description: scientific article; zbMATH DE number 7355180