{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T13:00:55Z","timestamp":1790773255566,"version":"4.1.0"},"reference-count":88,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>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.<\/jats:p>\n                  <jats:p>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 &gt; 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.\"<\/jats:p>\n                  <jats:p>\n                    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\n                    <jats:sup>1(1+f)<\/jats:sup>\n                    , 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.\n                  <\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.1137\/s0097539796302531","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"804-915","source":"Crossref","is-referenced-by-count":314,"title":["Free Bits, PCPs, and Nonapproximability---Towards Tight Results"],"prefix":"10.1137","volume":"27","author":[{"given":"Mihir","family":"Bellare","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oded","family":"Goldreich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"Leonard Adleman, Two theorems on random polynomial time, IEEE, Long Beach, Calif., 1978, 75\u20138380e:68095"},{"key":"R2","unstructured":"M. Ajtai, J. Komlos, and E. Szemeredi,\n                      Deterministic simulation in logspace\n                      , in Proceedings of the 19th Annual Symposium on the Theory of Computing, ACM, 1987, pp. 132\u2013140."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01277956"},{"key":"R4","unstructured":"Michael Molloy, The probabilistic method, Algorithms Combin., Vol. 16, Springer, Berlin, 1998, 1\u2013352001a:05135"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00254-G"},{"key":"R6","unstructured":"Sanjeev Arora, Reductions, codes, PCPs, and inapproximability, IEEE Comput. Soc. Press, Los Alamitos, CA, 1995, 404\u20134131619099"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"R8","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy,\n                      Proof verification and intractability of approximation problems\n                      , in Proceedings of the 33th Symposium on Foundations in Computer Science, IEEE, 1992, pp. 14\u201323."},{"key":"R9","unstructured":"S. Arora and S. Safra,\n                      Probabilistic checking of proofs: A new characterization of NP\n                      , in Proceedings of the 33th Symposium on Foundations in Computer Science, IEEE, 1992, pp. 2\u201313."},{"key":"R10","unstructured":"L. Babai,\n                      Trading group theory for Randomness\n                      , in Proceedings of the 17th Annual Symposium on the Theory of Computing, ACM, 1985, pp. 421\u2013429."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"R12","unstructured":"L. Babai, L. Fortnow, L. Levin, and M. Szegedy,\n                      Checking computations in poly\u2010logarithmic time\n                      , in Proceedings of the 23rdAnnual Symposium on the Theory of Computing, ACM, 1991, pp. 21\u201331."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90020-1"},{"key":"R14","unstructured":"R. Bar\u2010Yehuda, S. Even, A local\u2010ratio theorem for approximating the weighted vertex cover problem, North\u2010Holland Math. Stud., Vol. 109, North\u2010Holland, Amsterdam, 1985, 27\u20134587h:05158"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90086-6"},{"key":"R16","unstructured":"M. Bellare,\n                      Interactive proofs and approximation: Reductions from two provers in one round\n                      , in Proceedings of the Second Israel Symposium on Theory and Computing Science, IEEE, 1993, pp. 266\u2010274."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1109\/18.556674"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275487"},{"key":"R19","unstructured":"Mihir Bellare, Oded Goldreich, Madhu Sudan, Free bits, PCPs and non\u2010approximability\u2014towards tight results, IEEE Comput. Soc. Press, Los Alamitos, CA, 1995, 422\u20134311619100"},{"key":"R20","unstructured":"M. Bellare, O. Goldreich, and M. Sudan,\n                      Free bits, PCPs, and non\u2010approximability\u2014towards tight results\n                      , Preliminary versions of this paper. TR95\u2010024 of ECCC, the\n                      Electronic Colloquium on Computational Complexity\n                      , May 1995 (revised Sept. 1995, Jan. 1996, Dec. 96)."},{"key":"R20","unstructured":"See http:\/\/www.eccc.uni\u2010trier.de\/eccc\/."},{"key":"R21","unstructured":"M. Bellare, S. Goldwasser, C. Lund, and A. Russell,\n                      Efficient probabilistically checkable proofs and applications to approximation\n                      , in Proceedings of the 25th Annual Symposium on the Theory of Computing, ACM, 1993, pp. 294\u2013304. (See also Errata sheet in in Proceedings of the 26th Annual Symposium on the Theory of Computing, ACM, 1994, pp. 820\u2013820)."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585569"},{"key":"R22","unstructured":"Also in\n                      Complexity of Numerical Optimization\n                      , P. M. Pardalos, ed., World Scientific, 1993."},{"key":"R23","unstructured":"M. Bellare and M. Sudan,\n                      Improved non\u2010approximability results\n                      , in Proceedings of the 26th Annual Symposium on the Theory of Computing, ACM, 1994, pp. 184\u2013193."},{"key":"R24","unstructured":"M. Ben\u2010Or, S. Goldwasser, J. Kilian, and A. Wigderson,\n                      Multi\u2010Prover interactive proofs: How to remove intractability assumptions\n                      , in Proceedings of the 20th Annual Symposium on the Theory of Computing, ACM, 1988, pp. 113\u2013131."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90056-L"},{"key":"R26","unstructured":"A. Blum,\n                      Algorithms for approximate graph coloring\n                      , Ph.D. thesis, Deptartment of Computer Science, MIT, 1991."},{"key":"R27","unstructured":"Manuel Blum, Michael Luby, Ronitt Rubinfeld, Self\u2010testing\/correcting with applications to numerical problems, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, MD, 1990), Vol. 47, 1993, 549\u201359594m:65020"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01994876"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1109\/18.52484"},{"key":"R30","unstructured":"A. Cohen and A. Wigderson,\n                      Dispersers, deterministic amplification, and weak random sources\n                      , in Proceedings of the 30th Symposium on Foundations in Computer Science, IEEE, 1989, pp. 14\u201319."},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/BF01271372"},{"key":"R32","unstructured":"S. Cook,\n                      The complexity of theorem\u2010proving procedures\n                      , in Proceedings of the 3rd Annual Symposium on the Theory of Computing, ACM, 1971, pp. 151\u2013158."},{"key":"R33","unstructured":"P. Crescenzi, V. Kann, Approximation on the web: a compendium of NP optimization problems, Lecture Notes in Comput. Sci., Vol. 1269, Springer, Berlin, 1997, 111\u201311898k:68083"},{"key":"R34","unstructured":"P. Crescenzi, R. Silvestri, and L. Trevisan,\n                      To weight or not to weight: where is the question?\n                      , in Proceedings of the Fourth Israel Symposium on Theory and Computing Science, IEEE, 1996."},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1137\/0205048"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80056-X"},{"key":"R37","unstructured":"U. Feige,\n                      Randomized graph products, chromatic numbers, and the \u0141ovasz theta function\n                      , in Proceedings of the 27th Annual Symposium on the Theory of Computing, ACM, 1995, pp. 635\u2013640."},{"key":"R38","unstructured":"U. Feige,\n                      Set Cover. A threshold of ln n for approximating set cover\n                      , in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 314\u2013318, 1996."},{"key":"R39","unstructured":"U. Feige and M. Goemans,\n                      Approximating the value of two prover proof systems, with application to Max\u20102SAT and Max\u2010DICUT\n                      , in Proceedings of the Third Israel Symposium on Theory and Computing Science, IEEE, 1995, pp. 182\u2013189."},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"R41","unstructured":"U. Feige and J. Kilian,\n                      Two prover protocols \u2013 Low error at affordable rates\n                      , in Proceedings of the 26th Annual Symposium on the Theory of Computing, ACM, 1994, pp. 172\u2013183."},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1587"},{"key":"R43","unstructured":"U. Feige and L. \u0141ovasz,\n                      Two\u2010prover one round proof systems: Their power and their problems\n                      , in Proceedings of the 24th Annual Symposium on the Theory of Computing, ACM, 1992, pp. 733\u2010744."},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90251-8"},{"key":"R45","unstructured":"M. F\u00fcrer, Improved hardness results for approximating the chromatic number, in Proceedings of the 36th Symposium on Foundations in Computer Science, IEEE, 1995, pp. 414\u2013421."},{"key":"R46","unstructured":"M. F\u00fcrer, O. Goldreich, Y. Mansour, M. Sipser, and S. Zachos,\n                      On completeness and soundness in interactive proof systems\n                      , in Advances in Computing Research: a research annual, 5 (1989) (Randomness and Computation, S. Micali, ed.), pp. 429\u2013442."},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321926"},{"key":"R48","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480192243516"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"R54","unstructured":"S. Goldwasser and M. Sipser,\n                      Private coins versus public coins in interactive proof systems\n                      , in Proceedings of the 18th Annual Symposium on the Theory of Computing, ACM, 1986, pp. 59\u201368."},{"key":"R55","unstructured":"Johan H\u00e5stad, Testing of the long code and hardness for clique, ACM, New York, 1996, 11\u2013191427493"},{"key":"R56","unstructured":"J. H\u00e5stad,\n                      Clique is hard to approximate within n1-\u03b5\n                      , in Proceedings of the 37th Symposium on Foundations in Computer Science, IEEE, 1996, pp. 627\u2013636."},{"key":"R57","unstructured":"J. H\u00e5stad,\n                      Getting optimal in\u2010approximability results\n                      , in Proceedings of the 29th Annual Symposium on the Theory of Computing, ACM, 1997, pp. 1\u201310."},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90080-X"},{"key":"R59","unstructured":"R. Impagliazzo and D. Zuckerman,\n                      How to recycle random bits\n                      , in Proceedings of the 30th Symposium on Foundations in Computer Science, IEEE, 1989, pp. 248\u2013253."},{"key":"R60","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683259"},{"key":"R61","doi-asserted-by":"publisher","DOI":"10.1145\/210118.210136"},{"key":"R62","first-page":"0","author":"Kann Viggo","year":"1997","journal-title":"Chicago J. Theoret. Comput. Sci."},{"key":"R63","unstructured":"D. Karger, R. Motwani, and M. Sudan,\n                      Approximate graph coloring by semidefinite programming\n                      , in Proceedings of the 35th Symposium on Foundations in Computer Science, IEEE, 1994, pp. 2\u201313."},{"key":"R64","unstructured":"H. Karloff and U. Zwick,\n                      A 7\/8\u2010eps approximation algorithm for MAX 3SAT?\n                      , in Proceedings of the 38th Symposium on Foundations in Computer Science, IEEE, 1997, to appear."},{"key":"R65","unstructured":"R. Karp,\n                      Reducibility among combinatorial problems\n                      , Complexity of Computer Computations, Miller and Thatcher, eds., Plenum Press, New York, 1972."},{"key":"R66","unstructured":"S. Khanna, N. Linial, and S. Safra,\n                      On the hardness of approximating the chromatic number\n                      , in Proceedings of the Second Israel Symposium on Theory and Computing Science, IEEE, 1993, pp. 250\u2013260."},{"key":"R67","unstructured":"D. Lapidot and A. Shamir,\n                      Fully parallelized multi\u2010prover protocols for NEXP\u2010time\n                      , in Proceedings of the 32nd Symposium on Foundations in Computer Science, IEEE, 1991, pp. 13\u201318."},{"key":"R68","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90044-3"},{"key":"R69","first-page":"265","volume":"9","author":"Levin L.","year":"1973","journal-title":"Problemy Peredachi Informatsii"},{"key":"R70","unstructured":"A. Lubotzky, R. Phillips, and P. Sarnak,\n                      Explicit expanders and the Ramanujan conjectures\n                      , in Proceedings of the 18th Annual Symposium on the Theory of Computing, ACM, 1986, pp. 240\u2013246."},{"key":"R71","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"R72","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"R73","first-page":"137","author":"Uehara Tsuyoshi","year":"1998","journal-title":"S\u016brikaisekikenky\u016bsho K\u014dky\u016broku"},{"key":"R74","doi-asserted-by":"publisher","DOI":"10.1007\/BF00290149"},{"key":"R75","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized algorithms\n                      , Cambridge University Press, 1995."},{"key":"R76","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"R77","doi-asserted-by":"publisher","DOI":"10.1007\/BF01202286"},{"key":"R78","unstructured":"A. Polishchuk and D. Spielman,\n                      Nearly\u2010linear size holographic proofs\n                      , in Proceedings of the 26th Annual Symposium on the Theory of Computing, ACM, 1994, pp. 194\u2013203."},{"key":"R79","unstructured":"R. Raz,\n                      A parallel repetition theorem\n                      , in Proceedings of the 27th Annual Symposium on the Theory of Computing, ACM, 1995, pp. 447\u2013456."},{"key":"R80","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321975"},{"key":"R81","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"R82","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0066"},{"key":"R83","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00043-9"},{"key":"R84","unstructured":"Luca Trevisan, Gregory Sorkin, Madhu Sudan, David Williamson, Gadgets, approximation, and linear programming (extended abstract), IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, 617\u20136261450660"},{"key":"R85","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1045"},{"key":"R86","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266407"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539796302531","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:13:41Z","timestamp":1787336021000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539796302531"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":88,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539796302531"],"URL":"https:\/\/doi.org\/10.1137\/s0097539796302531","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}