Proof verification and hardness of approximation problems

By Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy. 1992

The class PCP(f(n),g(n)) consists of all languages L for which there exists a polynomial-time probabilistic oracle machine that used O(f(n)) random bits, queries O(g(n)) bits of its oracle and behaves as follows: If x in L then there exists an oracle y such that the machine accepts for all random choices but if x not in L then for every oracle y the machine rejects with high probability. Arora and Safra (1992) characterized NP as PCP(log n, (loglogn)/sup O(1)/). The authors improve on their result by showing that NP=PCP(logn, 1). The result has the following consequences: (1) MAXSNP-hard problems (e.g. metric TSP, MAX-SAT, MAX-CUT) do not have polynomial time approximation schemes unless P=NP; and (2) for some epsilon >0 the size of the maximal clique in a graph cannot be approximated within a factor of n/sup epsilon / unless P=NP.<<ETX>>

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Pinocchio: Nearly Practical Verifiable Computation (2013, methodology): “Setty et al. produced a second line of PCP-based systems called Pepper [27] and Ginger [28].”
Towards Fast Computation of Certified Robustness for ReLU Networks (2018, methodology): “…of the theory of computational hardness of approximation, which investigates the inherent difficulty in designing efficient approximation algorithms for various optimization problems.2 The formal definition can be stated as follows, Theorem A.11 ((Arora & Safra, 1998; Arora et al., 1998)).”
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming (1995, background): “Furthermore, MAX CUT, MAX 2SAT, and MAX DICUT are MAX SNP-hard [55], and so it is known that there exists a constant c < 1 such that a c-approximation algorithm for any of these problems would imply that P = NP [2].”
Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture (2014, background): “Fully-homomorphic encryption (FHE) [39] and probabilistically-checkable proofs [5, 4] are powerful tools that are often used in protocols for outsourcing computations (with integrity or confidentiality guarantees, or both) [49, 54, 2, 37, 31, 47, 41].”
Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique (2004, methodology): “We look at the Low Degree Test which is an important building block of the PCP Theorem ([4], [3]).”
Resolving the conflict between generality and plausibility in verified computation (2013, methodology): “These solutions, which we refer to as verified computation protocols, use modern cryptography coupled with seminal work in complexity theory on probabilistically checkable proofs (PCPs) [6, 7].”
Parallel repetition: simplifications and the no-signaling case (2006, background): “Related work Because of the PCP-Theorem and its application to hardness of approximation [14, 2, 1], people became interested to know whether the winning probability would at least decrease exponentially in n.”
On the Power of Multi-Prover Interactive Protocols (1994, methodology): “Multiple-prover interactive proof systems have also seen several important applications including the analysis of program testing [7, 4] and the complexity of approximation algorithms [14, 2, 1].”
Towards Sharp Inapproximability For Any 2-CSP (2007, unknown): “Meanwhile, the study of inapproximability has seen a lot of progress, emanating from the discovery of the celebrated PCP theorem [4, 3].”
On the efficiency of local decoding procedures for error-correcting codes (2000, background): “Results about "low-degree tests" as developed for PCP constructions [3; 2 ; 15] imply the existence of codes having an encoding of polynomial length and a checking procedure that only reads a constant number of entries.”