Efficient probabilistically checkable proofs and applications to approximations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient probabilistically checkable proofs and applications to approximations

Full text

Pdf (1.17 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 294 - 304

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

M. Bellare
S. Goldwasser
C. Lund
A. Russeli

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 31, Citation Count: 63

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/167088.167174 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AS	S. ARORA AND S. SAFRA. Approximating clique is NP-complete. FOCS 92.
	ALMSS	S. ARORA, C. LUND, R. MOTWANI, M. SU- DAN AND M. SZEGEDY. Proof verification and intractability of approximation problems. FOCS 92.
	ADP	G. AUSIELLO, A. D'ATRI AND M. PROTASI. Structure preserving reductions among convex optimization problems. Journal of Computer and System Sciences 21, 13fi-153 (1980).
	BFL	L. BABAI, L. FORTNOW AND C. LUND. Non- Deterministic Exponential Time has Two-Prover Interactive Protocols. FOCS 90.
	BFLS	László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103428]
	Be	M. BELLARB. Interactive Proofs and Approximation. IBM Research Report RC 17969 (May 1992).
	BGG	M. BELLARE, O. GOLDREICH AND S. GOLD- WASSBR. Randomness in Interactive Proofs. FOCS 90.
	BR	M. BELLARE AND P. ROGAWAY. The Complexity of Approximating a Nonlinear program. IBM Research Report RC 17831 (March 1992).
	BGKW	Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Widgerson, Multi-prover interactive proofs: how to remove intractability assumptions, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.113-131, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62223]
	BLR	M. Blum , M. Luby , R. Rubinfeld, Self-testing/correcting with applications to numerical problems, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.73-83, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100225]
	CW	A. COHEN AND A. WIGDBRSON. Dispersers, Deterministic Amplification, and Weak Random Sources. FOCS 89.
	Co	Anne Condon, The complexity of the max word problem and the power of one-way interactive proof systems, Proceedings of the 8th annual symposium on Theoretical aspects of computer science, p.456-465, February 1991, Hamburg, Germany
	FRS	L. FORTNOW, j. ROMPEL AND M. SIPSER. On the power of multiprover interactive protocols. Proceedings of the 3rd Structures, IEEE (1988).
	FGLSS	U. Feige , S. Goldwasser , L. Lovász , S. Safra , M. Szegedy, Approximating clique is almost NP-complete (preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.2-12, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185341]
	FL	Uriel Feige , László Lovász, Two-prover one-round proof systems: their power and their problems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.733-744, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129783]
	GS	Peter Gemmell , Madhu Sudan, Highly resilient correctors for polynomials, Information Processing Letters, v.43 n.4, p.169-174, Sept. 28, 1992 [doi>10.1016/0020-0190(92)90195-2]
	IZ	R. {MPAGLIAZZO AND D. ZUCKERMAN. How to Recycle Random Bits. FOCS 89.
	Jo	D. JOHNSON. Approximation algorithms for combinatorial problems. J. of Computer and System Sciences 9, 256-278 (1974).
	KT	P. KOLAITIS AND M. THAKUR. Approximation properties of NP minimization classes. Structure in Complexity Theory, 1991.
	LS	Dror Lapidot , Adi Shamir, Fully parallelized multi-prover protocols for NEXP-time, Journal of Computer and System Sciences, v.54 n.2, p.215-220, April 1997 [doi>10.1006/jcss.1997.1238]
	Lo	L. Lov,(sz. On the ratio of optimal integral and fractional covers. Discrete Mathematics 13, 383- 390 (1975).
	LY1	Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.286-293, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167172]
	LY2	Carsten Lund , Mihalis Yannakakis, The Approximation of Maximum Subgraph Problems, Proceedings of the 20th International Colloquium on Automata, Languages and Programming, p.40-51, July 05-09, 1993
	MS	F. MACWILLIAMS AND N. SLOANR. The Theory of Error-Correcting Codes. North-Holland, 1981.
	PY	Christos Papadimitriou , Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62233]
	PS	S. PHILLIPS AND S. SAFRA. PCP and tighter bounds for approximating MAXSNP. Manuscript, 1992.
	Va	Stephen A. Vavasis, On approximation algorithms for concave quadratic programming, Recent advances in global optimization, Princeton University Press, Princeton, NJ, 1992
	Zu	D. ZUOI#RMAN. NP-Complete Problems have a version that is hard to Approximate. Structure in Complexity Theory, 1993.

CITED BY 63

	Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998
	Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998
	Hervé Brönnimann , Michael T. Goodrich, Almost optimal set covers in finite VC-dimension: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.293-302, June 06-08, 1994, Stony Brook, New York, United States
	Uriel Feige, A threshold of ln n for approximating set cover (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.314-318, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.286-293, May 16-18, 1993, San Diego, California, United States
	Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States
	Aravind Srinivasan, Improved approximations of packing and covering problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.268-276, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Sanjeev Arora, The approximability of NP-hard problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.337-348, May 24-26, 1998, Dallas, Texas, United States
	Katalin Friedl , Zsolt Hátsági , Alexander Shen, Low-degree tests, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.57-64, January 23-25, 1994, Arlington, Virginia, United States
	Luca Trevisan, Recycling queries in PCPs and in linearity tests (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.299-308, May 24-26, 1998, Dallas, Texas, United States
	Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001
	Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998
	Yachyang Sun , Ting-Chi Wang , C. K. Wong , C. L. Liu, Routing for symmetric FPGAs and FPICs, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.486-490, November 07-11, 1993, Santa Clara, California, United States
	Ran Raz, A parallel repetition theorem, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.447-456, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Uriel Feige , Joe Kilian, Impossibility results for recycling random bits in two-prover proof systems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.457-468, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Uri Feige , Joe Kilian, Two prover protocols: low error at affordable rates, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.172-183, May 23-25, 1994, Montreal, Quebec, Canada
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Luca Trevisan, Non-approximability results for optimization problems on bounded degree instances, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.453-461, July 2001, Hersonissos, Greece
	Matthew J. Katz , Franck Nielsen, On piercing sets of objects, Proceedings of the twelfth annual symposium on Computational geometry, p.113-121, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Sanjeev Arora , Madhu Sudan, Improved low-degree testing and its applications, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.485-495, May 04-06, 1997, El Paso, Texas, United States
	Piotr Berman , Martin Fürer, Approximating maximum independent set in bounded degree graphs, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.365-371, January 23-25, 1994, Arlington, Virginia, United States
	Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998
	M. Bellare , S. Goldwasser , C. Lund , A. Russell, Efficient probabilistic checkable proofs and applications to approximation, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.820, May 23-25, 1994, Montreal, Quebec, Canada
	Johan Håstad, Testing of the long code and hardness for clique, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.11-19, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Daya Ram Gaur , Toshihide Ibaraki , Ramesh Krishnamurti, Constant ratio approximation algorithms for the rectangle stabbing problem and the rectilinear partitioning problem, Journal of Algorithms, v.43 n.1, p.138-152, April 2002
	Ari Juels , Marcus Peinado, Hiding cliques for cryptographic security, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.678-684, January 25-27, 1998, San Francisco, California, United States
	John Kececioglu , Dan Gusfield, Reconstructing a history of recombinations from a set of sequences, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.471-480, January 23-25, 1994, Arlington, Virginia, United States
	Mihir Bellare , Madhu Sudan, Improved non-approximability results, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.184-193, May 23-25, 1994, Montreal, Quebec, Canada
	Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994
	Immanuel M. Bomze , Marco Budinich , Marcello Pelillo , Claudio Rossi, Annealed replication: a new heuristic for the maximum clique problem, Discrete Applied Mathematics, v.121 n.1-3, p.27-49, 15 September 2002
	Liming Cai , David Juedes , Iyad Kanj, The inapproximability of non-NP-hard optimization problems, Theoretical Computer Science, v.289 n.1, p.553-571, 23 October 2002
	Marcos Kiwi , Frédéric Magniez , Miklos Santha, Exact and approximate testing/correcting of algebraic functions: a survey, Theoretical aspects of computer science: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2002
	Stavros G. Kolliopoulos, Approximating covering integer programs with multiplicity constraints, Discrete Applied Mathematics, v.129 n.2-3, p.461-473, 01 August 2003
	Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States
	Amir Shpilka , Avi Wigderson, Derandomizing homomorphism testing in general groups, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Irit Dinur , Shmuel Safra, On the hardness of approximating label-cover, Information Processing Letters, v.89 n.5, p.247-254, 16 March 2004
	Alex Samorodnitsky , Luca Trevisan, A PCP characterization of NP with optimal amortized query complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.191-199, May 21-23, 2000, Portland, Oregon, United States
	M. Kiwi, Algebraic testing and weight distributions of codes, Theoretical Computer Science, v.299 n.1-3, p.81-106, 18 April 2003
	Eli Ben-Sasson , Oded Goldreich , Prahladh Harsha , Madhu Sudan , Salil Vadhan, Robust pcps of proximity, shorter pcps and applications to coding, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Bozhena Bidyuk , Rina Dechter, On finding minimal w-cutset, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.43-50, July 07-11, 2004, Banff, Canada
	Ari Juels , Marcus Peinado, Hiding Cliques for Cryptographic Security, Designs, Codes and Cryptography, v.20 n.3, p.269-280, July 2000
	Ashraf M. Abdelbar, Approximating cost-based abduction is NP-hard, Artificial Intelligence, v.159 n.1-2, p.231-239, November 2004
	Katalin Friedl , Gábor Ivanyos , Miklos Santha, Efficient testing of groups, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Eli Ben-Sasson , Madhu Sudan, Simple PCPs with poly-log rate and query complexity, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Oded Goldreich, Property testing in massive graphs, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Fedor V. Fomin , Dieter Kratsch , Haiko Müller, On the domination search number, Discrete Applied Mathematics, v.127 n.3, p.565-580, 01 May 2003
	Uri Zwick, Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.201-210, January 25-27, 1998, San Francisco, California, United States
	Eli Ben-Sasson , Madhu Sudan, Robust locally testable codes and products of codes, Random Structures & Algorithms, v.28 n.4, p.387-402, July 2006
	Vitaly Feldman, Hardness of approximate two-level logic minimization and PAC learning with membership queries, Journal of Computer and System Sciences, v.75 n.1, p.13-26, January, 2009
	Noga Alon , Dana Moshkovitz , Shmuel Safra, Algorithmic construction of sets for k-restrictions, ACM Transactions on Algorithms (TALG), v.2 n.2, p.153-177, April 2006
	Vitaly Feldman, Hardness of approximate two-level logic minimization and PAC learning with membership queries, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Maria Serna , Luca Trevisan , Fatos Xhafa, The approximability of non-Boolean satisfiability problems and restricted integer programming, Theoretical Computer Science, v.332 n.1-3, p.123-139, 28 February 2005
	Oded Goldreich , Madhu Sudan, Locally testable codes and PCPs of almost-linear length, Journal of the ACM (JACM), v.53 n.4, p.558-655, July 2006
	Wenbin Chen , Jiangtao Meng, Hardness of approximating the Minimum Solutions of Linear Diophantine Equations, Theoretical Computer Science, v.374 n.1-3, p.191-195, April, 2007
	Ishay Haviv , Oded Regev, Tensor-based hardness of the shortest vector problem to within almost polynomial factors, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Julia Chuzhoy , Sanjeev Khanna, Polynomial flow-cut gaps and hardness of directed cut problems, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Oded Goldreich, A taxonomy of proof systems (part 2), ACM SIGACT News, v.25 n.1, p.22-30, March 1994
	Julia Chuzhoy , Sanjeev Khanna, Polynomial flow-cut gaps and hardness of directed cut problems, Journal of the ACM (JACM), v.56 n.2, p.1-28, April 2009
	Solmaz Kolahi , Laks V. S. Lakshmanan, On approximating optimum repairs for functional dependency violations, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia
	Boris Aronov , Esther Ezra , Micha Shair, Small-size ε-nets for axis-parallel rectangles and boxes, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Vincent Berry , François Nicolas, Maximum agreement and compatible supertrees, Journal of Discrete Algorithms, v.5 n.3, p.564-591, September, 2007
	Fabrizio Angiulli, Prototype-based Domain Description, Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence, p.107-111, June 27, 2008
	Christer Backstrom , Peter Jonsson, Planning with abstraction hierarchies can be exponentially less efficient, Proceedings of the 14th international joint conference on Artificial intelligence, p.1599-1604, August 20-25, 1995, Montreal, Quebec, Canada