The DOI matches its Crossref record; 61 of the 61 references it cites were found in a registry or an index.
Free bits, PCPs and non-approximability-towards tight results
Abstract
The first part of this paper presents new proof systems and improved non-approximability results. In particular we present a proof system for NP using logarithmic randomness and two amortized free bits, so that Max clique is hard within N/sup 1/3/ and chromatic number within N/sup 1/5/. We also show hardness of 38/37 for Max-3-SAT, 27/26 for vertex cover, 82/81 for Max-cut, and 94/93 for Max-2-SAT. The second part of this paper presents a "reverse" of the FGLSS connection by showing that an NP-hardness result for the approximation of Max clique to within a factor of N/sup 1/(g+1/) would imply a probabilistic verifier for NP with logarithmic randomness and amortized free-bit complexity g. We also show that "existing techniques" won't yield proof systems of less than two bits in amortized free bit complexity. Finally, we initiate a comprehensive study of PCP and FPCP parameters, proving several triviality results and providing several useful transformations.
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
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
Spencer, J. (1991) · Medical Entomology and Zoology · Cited by 4,310
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587 · cited 5×
“[84] which in turn build on Goemans and Williamson [51]).”
BackgroundResultInfluentialThe 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 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
Cited by
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
“Chor and Sudan [1995] apply ideas from this paper to the betweenness problem.”
InfluentialProof 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-citationProbabilistic 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
Property testing and its connection to learning and approximation
Goldreich, O., Goldwasser, S., & Ron, D. (1998) · Journal of the ACM · doi:10.1145/285055.285060 · Cited by 1,020
Self-citationCounterexample-guided abstraction refinement for symbolic model checking
Clarke, E., Grumberg, O., Jha, S., Lu, Y., & Veith, H. (2003) · Journal of the ACM · doi:10.1145/876638.876643 · Cited by 994
O'Donnell, R. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781139814782 · Cited by 932
Boros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827
“For instance the results mentioned above for the MAX-3-SAT, MAX CSP(AND3) and MAX CSP(MAJ3) problems are all known to be best possible, unless P=NP (see [20, 101, 159]).”
On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
Amaldi, E., & Kann, V. (1998) · Theoretical Computer Science · doi:10.1016/s0304-3975(97)00115-1 · Cited by 753
Clique is hard to approximate within n/sup 1-ε/
Hastad, J. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548522 · Cited by 458
Some APX-completeness results for cubic graphs
Alimonti, P., & Kann, V. (2000) · Theoretical Computer Science · doi:10.1016/s0304-3975(98)00158-3 · Cited by 361
Extractors and pseudorandom generators
(2001) · Journal of the ACM · doi:10.1145/502090.502099 · Cited by 324
Introduction to Property Testing
Goldreich, O. (2017) · Cambridge University Press eBooks · doi:10.1017/9781108135252 · Cited by 270
Self-citationModern Cryptography, Probabilistic Proofs and Pseudorandomness
Goldreich, O. (1999) · Algorithms and Combinatorics · doi:10.1007/978-3-662-12521-2 · Cited by 265
Self-citation
Metadata
- Authors
- Bellare, M., Goldreich, O., & Sudan, M.
- Venue
- Proceedings of IEEE 36th Annual Foundations of Computer Science
- Publisher
- IEEE Comput. Soc. Press
- Published
- 2002-11-19
- Pages
- 422-431
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2202947145
- Cited by
- 265
- References
- 61
- FWCI
- 18.48
- 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.