The DOI matches its Crossref record; 26 of the 26 references it cites were found in a registry or an index.
The PCP theorem by gap amplification
Abstract
The PCP theorem [Arora and Safra 1998; Arora et. al. 1998] says that every language in NP has a witness format that can be checked probabilistically by reading only a constant number of bits from the proof. The celebrated equivalence of this theorem and inapproximability of certain optimization problems, due to Feige et al. [1996], has placed the PCP theorem at the heart of the area of inapproximability. In this work, we present a new proof of the PCP theorem that draws on this equivalence. We give a combinatorial proof for the NP-hardness of approximating a certain constraint satisfaction problem, which can then be reinterpreted to yield the PCP theorem. Our approach is to consider the unsat value of a constraint system, which is the smallest fraction of unsatisfied constraints, ranging over all possible assignments for the underlying variables. We describe a new combinatorial amplification transformation that doubles the unsat-value of a constraint-system, with only a linear blowup in the size of the system. The amplification step causes an increase in alphabet-size that is corrected by a (standard) PCP composition step. Iterative application of these two steps yields a proof for the PCP theorem. The amplification lemma relies on a new notion of “graph powering” that can be applied to systems of binary constraints. This powering amplifies the unsat-value of a constraint system provided that the underlying graph structure is an expander. We also extend our amplification lemma towards construction of assignment testers (alternatively, PCPs of Proximity) which are slightly stronger objects than PCPs. We then construct PCPs and locally-testable codes whose length is linear up to a polylog factor, and whose correctness can be probabilistically verified by making a constant number of queries. Namely, we prove SAT ∈ PCP 1/2,1 [log 2 ( n ⋅poly log n ), O (1)].
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The knowledge complexity of interactive proof systems
Goldwasser, S., Micali, S., & Rackoff, C. (1989) · SIAM Journal on Computing · doi:10.1137/0218012 · Cited by 3,285
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
Expander graphs and their applications
Hoory, S., Linial, N., & Wigderson, A. (2006) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-06-01126-8 · Cited by 1,723
Optimization, approximation, and complexity classes
Papadimitriou, C. H., & Yannakakis, M. (1991) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(91)90023-x · Cited by 1,653
Proof verification and the hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998) · Journal of the ACM · doi:10.1145/278298.278306 · Cited by 1,413
Probabilistic checking of proofs: a new characterization of NP
Arora, S., & Safra, S. (1998) · Journal of the ACM · doi:10.1145/273865.273901 · Cited by 1,153
Sipser, M., & Spielman, D. A. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556667 · Cited by 931
Trading group theory for randomness
Babai, L. (1985) · Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85 · doi:10.1145/22145.22192 · Cited by 772
Algebraic methods for interactive proof systems
Lund, C., Fortnow, L., Karloff, H., & Nisan, N. (1992) · Journal of the ACM · doi:10.1145/146585.146605 · Cited by 711
Raz, R. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539795280895 · Cited by 703
Shamir, A. (1992) · Journal of the ACM · doi:10.1145/146585.146609 · Cited by 662
Interactive proofs and the hardness of approximating cliques
Feige, U., Goldwasser, S., Lovász, L., Safra, M., & Szegedy, M. (1996) · Journal of the ACM · doi:10.1145/226643.226652 · Cited by 525
Non-deterministic exponential time has two-prover interactive protocols
Babai, L., Fortnow, L., & Lund, C. (1992) · Computational Complexity · doi:10.1007/bf01200430 · Cited by 520
Multi-prover interactive proofs: how to remove intractability
Ben-Or, M., Goldwasser, S., Kilian, J., & Widgerson, A. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62223 · Cited by 468
Non-deterministic exponential time has two-prover interactive protocols
Babai, L., Fortnow, L., & Lund, C. (1991) · Computational Complexity · doi:10.1007/bf01200056 · Cited by 458
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
Bellare, M., Goldreich, O., & Sudan, M. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539796302531 · Cited by 453
Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders
Reingold, O., Vadhan, S., & Wigderson, A. (2002) · Annals of Mathematics · doi:10.2307/3062153 · Cited by 408
Approximating clique is almost NP-complete
Feige, U., Goldwasser, S., Lovasz, L., Safra, S., & Szegedy, M. (2002) · [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science · doi:10.1109/sfcs.1991.185341 · Cited by 396
Nearly-linear size holographic proofs
Polishchuk, A., & Spielman, D. A. (1994) · Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 · doi:10.1145/195058.195132 · Cited by 191
On the power of multi-prover interactive protocols
Fortnow, L., Rompel, J., & Sipser, M. (1994) · Theoretical Computer Science · doi:10.1016/0304-3975(94)90251-8 · Cited by 185
Locally testable codes and PCPs of almost-linear length
Goldreich, O., & Sudan, M. (2006) · Journal of the ACM · doi:10.1145/1162349.1162351 · Cited by 152
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
Ben‐Sasson, E., Sudan, M., Vadhan, S., & Wigderson, A. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780631 · Cited by 140
Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors
Wigderson, A., Reingold, O., & Vadhan, S. P. (2002) · Digital Access to Scholarship at Harvard (DASH) (Harvard University) · Cited by 133
Robust pcps of proximity, shorter pcps and applications to coding
Ben‐Sasson, E., Goldreich, O., Harsha, P., Sudan, M., & Vadhan, S. (2004) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1007352.1007361 · Cited by 110
Robust Locally Testable Codes and Products of Codes
Ben‐Sasson, E., & Sudan, M. (2004) · Random Structures and Algorithms · doi:10.1002/rsa.20120 · Cited by 60
Impossibility results for recycling random bits in two-prover proof systems
Feige, U., & Kilian, J. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225183 · Cited by 39
Cited by
The Design of Approximation Algorithms
Williamson, D. P., & Shmoys, D. B. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511921735 · Cited by 1,301
O'Donnell, R. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781139814782 · Cited by 932
SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge
Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., & Virza, M. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40084-1_6 · Cited by 598
Undirected connectivity in log-space
Reingold, O. (2008) · Journal of the ACM · doi:10.1145/1391289.1391291 · Cited by 505
Delegating computation: interactive proofs for muggles
Goldwasser, S., Kalai, Y. T., & Rothblum, G. N. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374396 · Cited by 484
Metadata
- Authors
- Dinur, I.
- Venue
- Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing
- Publisher
- ACM
- Published
- 2006-05-21
- Volume
- 54
- Issue
- 3
- Pages
- 241-250
- OpenAlex
- W336776360
- Cited by
- 501
- References
- 26
- FWCI
- 22.95
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.