The DOI matches its Crossref record; 61 of the 61 references it cites were found in a registry or an index.
Proof verification and hardness of approximation problems
Abstract
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.>
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
(1979) · Cited by 43,841
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
The Theory of Error-Correcting Codes
(1977) · North-Holland Mathematical Library · doi:10.1016/s0924-6509(08)x7030-8 · Cited by 10,760
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385
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
National Cancer Institute (2020) · Definitions · doi:10.32388/bz83sn · Cited by 2,981
Reducibility Among Combinatorial Problems
Karp, R. M. (2010) · 50 Years of Integer Programming 1958-2008 · doi:10.1007/978-3-540-68279-0_8 · Cited by 2,490
Approximation algorithms for combinatorial problems
Johnson, D. S. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80044-9 · Cited by 2,197
Some simplified NP-complete graph problems
Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976) · Theoretical Computer Science · doi:10.1016/0304-3975(76)90059-1 · Cited by 2,059
P-Complete Approximation Problems
Sahni, S., & Gonzalez, T. (1976) · Journal of the ACM · doi:10.1145/321958.321975 · Cited by 1,703
Fast Probabilistic Algorithms for Verification of Polynomial Identities
Schwartz, J. T. (1980) · Journal of the ACM · doi:10.1145/322217.322225 · Cited by 1,701
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
Bounds for Certain Multiprocessing Anomalies
Graham, R. L. (1966) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1966.tb01709.x · Cited by 1,647
nauk, R. A. (1965) · Наука eBooks · Cited by 1,013
Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
Ibarra, O. H., & Kim, C. E. (1975) · Journal of the ACM · doi:10.1145/321906.321909 · Cited by 959
Generalized first-order spectra and polynomial-time recognizable sets
Fagin, R. (1974) · Medical Entomology and Zoology · Cited by 828
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
Self-citationThe theory of error-correcting codes
Massey, J. L. (1980) · Proceedings of the IEEE · doi:10.1109/proc.1980.11608 · Cited by 676
Shamir, A. (1992) · Journal of the ACM · doi:10.1145/146585.146609 · Cited by 662
Checking computations in polylogarithmic time
Babai, L., Fortnow, L., Levin, L. A., & Szegedy, M. (1991) · Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 · doi:10.1145/103418.103428 · Cited by 616
Self-citationArthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
Babai, L., & Moran, S. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90028-1 · Cited by 589
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
Self-citationBin packing can be solved within 1 + ε in linear time
de la Véga, W. F., & Lueker, G. S. (1981) · COMBINATORICA · doi:10.1007/bf02579456 · Cited by 510
An efficient approximation scheme for the one-dimensional bin-packing problem
Karmarkar, N. K., & Karp, R. M. (1982) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1982.61 · Cited by 491
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
Self-citationThe Traveling Salesman Problem with Distances One and Two
Papadimitriou, C. H., & Yannakakis, M. (1993) · Mathematics of Operations Research · doi:10.1287/moor.18.1.1 · Cited by 412
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
Self-citationImpagliazzo, R., & Zuckerman, D. (1989) · 30th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63486 · Cited by 387
Approximate Algorithms for the 0/1 Knapsack Problem
Sahni, S. (1975) · Journal of the ACM · doi:10.1145/321864.321873 · Cited by 349
The Complexity of Near-Optimal Graph Coloring
Garey, M. R., & Johnson, D. S. (1976) · Journal of the ACM · doi:10.1145/321921.321926 · Cited by 326
Efficient probabilistically checkable proofs and applications to approximations
Bellare, M., Goldwasser, S., Lund, C., et al. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167174 · Cited by 317
Self-citationSelf-testing/correcting with applications to numerical problems
Blum, M., Luby, M., & Rubinfeld, R. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100225 · Cited by 303
Designing programs that check their work
Blum, M., & Kanna, S. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73015 · Cited by 287
Probabilistic checking of proofs; a new characterization of NP
Arora, S., & Safra, S. (1992) · Proceedings., 33rd Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267824 · Cited by 275
Self-citationStructure preserving reductions among convex optimization problems
Ausiello, G., D'Atri, A., & Protasi, M. (1980) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(80)90046-x · Cited by 264
A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
Trakhtenbrot, B. A. (1984) · IEEE Annals of the History of Computing · doi:10.1109/mahc.1984.10036 · Cited by 260
Lipton, R. (1991) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/002/13 · Cited by 255
Hiding instances in multioracle queries
Beaver, D., & Feigenbaum, J. (1990) · Lecture Notes in Computer Science · doi:10.1007/3-540-52282-4_30 · Cited by 235
Freivalds, R. (1979) · Lecture notes in computer science · doi:10.1007/3-540-09526-8_5 · Cited by 232
The complexity of multiway cuts (extended abstract)
Dahlhaus, E., Johnson, D. S., Papadimitriou, C. H., Seymour, P. D., & Yannakakis, M. (1992) · Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92 · doi:10.1145/129712.129736 · Cited by 221
Complexity of Computer Computations
Rice, J. R., Miller, R. E., & Thatcher, J. W. (1974) · Mathematics of Computation · doi:10.2307/2005950 · Cited by 205
On the Approximation of Maximum Satisfiability
Yannakakis, M. (1994) · Journal of Algorithms · doi:10.1006/jagm.1994.1045 · Cited by 200
Algebraic methods for interactive proof systems
Lund, C., Fortnow, L., Karloff, H., & Nisan, N. (2002) · Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89518 · Cited by 193
Self-citationOn 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
Non deterministic polynomial optimization problems and their approximations
Paz, A., & Moran, S. (1981) · Theoretical Computer Science · doi:10.1016/0304-3975(81)90081-5 · Cited by 183
Dispersers, deterministic amplification, and weak random sources
Cohen, A., & Wigderson, A. (1989) · 30th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63449 · Cited by 182
Two-prover one-round proof systems: Their power and their problems
Feige, U., & Lovász, L. (1992) · Symposium on the Theory of Computing · Cited by 181
Self-testing/correcting for polynomials and for approximate functions
Gemmell, P., Lipton, R., Rubinfeld, R., Sudan, M., & Wigderson, A. (1991) · Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 · doi:10.1145/103418.103429 · Cited by 181
Self-citationThe approximation of maximum subgraph problems
Lund, C., & Yannakakis, M. (1993) · Lecture notes in computer science · doi:10.1007/3-540-56939-1_60 · Cited by 175
Self-citationHighly resilient correctors for polynomials
Gemmell, P., & Sudan, M. (1992) · Information Processing Letters · doi:10.1016/0020-0190(92)90195-2 · Cited by 169
Self-citationTwo-prover one-round proof systems: their power and their problems (extended abstract)
Feige, U., & Lovász, L. (1992) · Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92 · doi:10.1145/129712.129783 · Cited by 161
On the power of multi-power interactive protocols
Fortnow, L., Rompel, J., & Sipser, M. (1988) · Structure in Complexity Theory Annual Conference · doi:10.1109/sct.1988.5275 · Cited by 159
Arithmetization: A new method in structural complexity theory
Babai, L., & Fortnow, L. (1991) · Computational Complexity · doi:10.1007/bf01200057 · Cited by 96
The decision problem for the probabilities of higher-order properties
Kolaitis, P. G., & Vardi, M. Y. (1987) · doi:10.1145/28395.28441 · Cited by 86
Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems
Sudan, M. (1996) · Cited by 82
Self-citationA mathematical theory of self-checking, self-testing and self-correcting programs
Rubinfeld, R. (1991) · Cited by 53
Toward a unified approach for the classification of NP-complete optimization problems
Ausiello, G., Marchetti-Spaccamela, A., & Protasi, M. (1980) · Theoretical Computer Science · doi:10.1016/0304-3975(80)90006-7 · Cited by 50
Self-testing polynomial functions efficiently and over rational domains
Rubinfeld, R., & Sudan, M. (1992) · Cited by 42
Self-citationTransparent (holographic) proofs
Babai, L. (1993) · Lecture notes in computer science · doi:10.1007/3-540-56503-5_52 · Cited by 13
Cited by
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
A threshold of ln n for approximating set cover
Feige, U. (1998) · Journal of the ACM · doi:10.1145/285055.285059 · Cited by 3,086
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
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
Self-citationClique is hard to approximate within n1−ε
Håstad, J. (1999) · Acta Mathematica · doi:10.1007/bf02392825 · Cited by 1,369
Metadata
- Authors
- Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M.
- Venue
- Proceedings., 33rd Annual Symposium on Foundations of Computer Science
- Publisher
- IEEE
- Published
- 1992
- Pages
- 14-23
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2143391442
- Cited by
- 741
- References
- 61
- FWCI
- 42.81
- 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.