The DOI matches its Crossref record; 63 of the 63 references it cites were found in a registry or an index.
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
Abstract
This paper continues the investigation of the connection between probabilistically checkable proofs (PCPs) and the approximability of NP-optimization problems. The emphasis is on proving tight nonapproximability results via consideration of measures such as the "free-bit complexity" and the "amortized free-bit complexity" of proof systems. The first part of the paper presents a collection of new proof systems based on a new error-correcting code called the long code. We provide a proof system that has amortized free-bit complexity of $2 + \epsilon$, implying that approximating MaxClique within $N^{\frac13-\e}$, and approximating the Chromatic Number within $N^{\frac15-\e}$, are hard, assuming $\NP\neq\coRP$, for any e > 0. We also derive the first explicit and reasonable constant hardness factors for Min Vertex Cover, $\MSAT{2}$, and Max Cut, and we improve the hardness factor for $\MSAT{3}$. We note that our nonapproximability factors for $\maxsnp$ problems are appreciably close to the values known to be achievable by polynomial-time algorithms. Finally, we note a general approach to the derivation of strong nonapproximability results under which the problem reduces to the construction of certain "gadgets." The increasing strength of nonapproximability results obtained via the PCP connection motivates us to ask how far this can go and whether PCPs are inherent in any way. The second part of the paper addresses this. The main result is a "reversal" of the connection due to Feige et al. (FGLSS connection) [J. ACM, 43 (1996), pp. 268--292]: where the latter had shown how to translate proof systems for NP into NP-hardness of approximation results for MaxClique, we show how any NP-hardness of approximation result for MaxClique yields a proof system for NP. Roughly, our result says that for any constant f, if MaxClique is NP-hard to approximate within N 1(1+f) , then $\NP\subseteq \overline{\fpcp}[\log,f]$, the latter being the class of languages possessing proofs of logarithmic randomness and amortized free-bit complexity f. This suggests that PCPs are inherent to obtaining nonapproximability results. Furthermore, the tight relation suggests that reducing the amortized free-bit complexity is necessary for improving the nonapproximability results for MaxClique. The third part of our paper initiates a systematic investigation of the properties of PCP and FPCP (free PCP) as a function of the following various parameters: randomness, query complexity, free-bit complexity, amortized free-bit complexity, proof size, etc. We are particularly interested in triviality results, which indicate which classes are not powerful enough to capture NP. We also distill the role of randomized reductions in this area and provide a variety of useful transformations between proof checking complexity classes.
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
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
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
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
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
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
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
Clique is hard to approximate within n1−ε
Håstad, J. (1999) · Acta Mathematica · doi:10.1007/bf02392825 · Cited by 1,369
Goldreich, O., Micali, S., & Wigderson, A. (1991) · Journal of the ACM · doi:10.1145/116825.116852 · Cited by 1,349
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
On the Complexity of Timetable and Multicommodity Flow Problems
Even, S., Itai, A., & Shamir, A. (1976) · SIAM Journal on Computing · doi:10.1137/0205048 · Cited by 1,057
nauk, R. A. (1965) · Наука eBooks · Cited by 1,013
On the hardness of approximating minimization problems
Lund, C., & Yannakakis, M. (1994) · Journal of the ACM · doi:10.1145/185675.306789 · Cited by 872
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
Self-testing/correcting with applications to numerical problems
Blum, M., Luby, M., & Rubinfeld, R. (1993) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(93)90044-w · Cited by 712
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
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
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
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
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
A linear-time approximation algorithm for the weighted vertex cover problem
Bar-Yehuda, R., & Even, S. (1981) · Journal of Algorithms · doi:10.1016/0196-6774(81)90020-1 · Cited by 430
Approximate graph coloring by semidefinite programming
Karger, D., Motwani, R., & Sudan, M. (1998) · Journal of the ACM · doi:10.1145/274787.274791 · Cited by 420
Self-citationA Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem
Bar-Yehuda, R., & Even, S. (1985) · North-Holland Mathematics Studies · doi:10.1016/s0304-0208(08)73101-3 · Cited by 404
Private coins versus public coins in interactive proof systems
Goldwasser, S., & Sipser, M. (1986) · Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86 · doi:10.1145/12130.12137 · Cited by 399
Impagliazzo, R., & Zuckerman, D. (1989) · 30th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63486 · Cited by 387
Approximating maximum independent sets by excluding subgraphs
Boppana, R., & Halldórsson, M. M. (1992) · BIT · doi:10.1007/bf01994876 · Cited by 359
The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations
Arora, S., Babai, L., Stern, J., & Sweedyk, Z. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1472 · Cited by 344
Zero Knowledge and the Chromatic Number
Feige, U., & Kilian, J. (1998) · Journal of Computer and System Sciences · doi:10.1006/jcss.1998.1587 · Cited by 334
Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT
Feige, U., & Goemans, M. (2002) · Proceedings Third Israel Symposium on the Theory of Computing and Systems · doi:10.1109/istcs.1995.377033 · Cited by 328
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-citationTwo theorems on random polynomial time
Adleman, L. (1978) · 19th Annual Symposium on Foundations of Computer Science (sfcs 1978) · doi:10.1109/sfcs.1978.37 · Cited by 316
Efficient bounds for the stable set, vertex cover and set packing problems
Hochbaum, D. S. (1983) · Discrete Applied Mathematics · doi:10.1016/0166-218x(83)90080-x · Cited by 272
New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
Goemans, M. X., & Williamson, D. P. (1994) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480192243516 · Cited by 227
BPP and the polynomial hierarchy
Lautemann, C. (1983) · Information Processing Letters · doi:10.1016/0020-0190(83)90044-3 · Cited by 212
The complexity and approximability of finding maximum feasible subsystems of linear relations
Amaldi, E., & Kann, V. (1995) · Theoretical Computer Science · doi:10.1016/0304-3975(94)00254-g · Cited by 201
On the Approximation of Maximum Satisfiability
Yannakakis, M. (1994) · Journal of Algorithms · doi:10.1006/jagm.1994.1045 · Cited by 200
The hardness of approximation: Gap location
Petrank, E. (1994) · Computational Complexity · doi:10.1007/bf01202286 · Cited by 196
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
Ramsey numbers and an approximation algorithm for the vertex cover problem
Monien, B., & Speckenmeyer, E. (1985) · Acta Informatica · doi:10.1007/bf00290149 · Cited by 189
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
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
Linearity testing in characteristic two
Mihir Bellare, Y., Coppersmith, D., Håstad, J., Kiwi, M. A., & Sudan, M. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556674 · Cited by 172
Self-citationImproved non-approximability results
Bellare, M., & Sudan, M. (1994) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/195058.195129 · Cited by 162
Self-citationAlon, N., Feige, U., Wigderson, A., & Zuckerman, D. (1995) · Computational Complexity · doi:10.1007/bf01277956 · Cited by 152
New problems complete for nondeterministic log space
Jones, N. D., Lien, Y. E., & Laaser, W. T. (1976) · Theory of Computing Systems · doi:10.1007/bf01683259 · Cited by 138
On Unapproximable Versions of $NP$-Complete Problems
Zuckerman, D. (1996) · SIAM Journal on Computing · doi:10.1137/s0097539794266407 · Cited by 114
Eigenvalues and expansion of regular graphs
Kahalé, N. (1995) · Journal of the ACM · doi:10.1145/210118.210136 · Cited by 110
The hardness of decoding linear codes with preprocessing
Bruck, J., & Naor, M. (1990) · IEEE Transactions on Information Theory · doi:10.1109/18.52484 · Cited by 106
Gadgets, approximation, and linear programming
Trevisan, L., Sorkin, G. B., Sudan, M., & Williamson, D. P. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1996.548521 · Cited by 69
Self-citationRandomized graph products, chromatic numbers, and Lovasz j-function
Feige, U. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225281 · Cited by 64
Randomness in interactive proofs
Bellare, M., Goldreich, O., & Goldwasser, S. (1993) · Computational Complexity · doi:10.1007/bf01275487 · Cited by 61
Self-citationReductions, codes, PCPs, and inapproximability
Arora, S. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1995.492571 · Cited by 12
Cited by
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
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
The Design of Approximation Algorithms
Williamson, D. P., & Shmoys, D. B. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511921735 · Cited by 1,301
Bomze, I. M., Budinich, M., Pardalos, P. M., & Pelillo, M. (1999) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4757-3023-4_1 · Cited by 1,148
Metadata
- Authors
- Bellare, M., Goldreich, O., & Sudan, M.
- Venue
- SIAM Journal on Computing
- Published
- 1998-06
- Volume
- 27
- Issue
- 3
- Pages
- 804-915
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2111385661
- Cited by
- 453
- References
- 63
- FWCI
- 23.60
- Type
- journal article
- 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.