A PCP characterization of NP with optimal amortized query complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A PCP characterization of NP with optimal amortized query complexity

Full text

Pdf (838 KB)

Source

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

Portland, Oregon, United States

Pages: 191 - 199

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Alex Samorodnitsky	Institute for Advanced Study and DIMACS
Luca Trevisan	Columbia University and DIMACS

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 33, Citation Count: 27

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/335305.335329 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.

	1	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 [doi>10.1145/278298.278306]
	2	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 [doi>10.1145/273865.273901]
	3	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 [doi>10.1145/258533.258642]
	4	M. Bellare. Proof checking and approximation: Towards tight results. Sigact News, 27(1), 1996.
	5	Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
	6	M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167174]
	7	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 [doi>10.1145/195058.195129]
	8	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]
	9	Nadia Creignou, A dichotomy theorem for maximum generalized satisfiability problems, Journal of Computer and System Sciences, v.51 n.3, p.511-522, Dec. 1995 [doi>10.1006/jcss.1995.1087]
	10	Irit Dinur , Eldar Fischer , Guy Kindler , Ran Raz , Shmuel Safra, PCP characterizations of NP: towards a polynomially-small error-probability, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.29-40, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301265]
	11	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]
	12	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 [doi>10.1145/195058.195128]
	13	J. Hastad, Clique is hard to approximate within n1-, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.627, October 14-16, 1996
	14	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 [doi>10.1145/258533.258536]
	15	Sanjeev Khanna , Rajeev Motwani , Madhu Sudan , Umesh Vazirani, On Syntactic versus Computational Views of Approximability, SIAM Journal on Computing, v.28 n.1, p.164-191, Feb. 1999 [doi>10.1137/S0097539795286612]
	16	Sanjeev Khanna , Madhu Sudan , David P. Williamson, A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.11-20, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258538]
	17	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 [doi>10.1145/258533.258641]
	18	Maria J. Serna , Luca Trevisan , Fatos Xhafa, The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming, Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, p.488-498, February 25-27, 1998
	19	M. Sudan , L. Trevisan, Probabilistically Checkable Proofs with Low Amortized Query Complexity, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.18, November 08-11, 1998
	20	Luca Trevisan, Positive Linear Programming, Parallel Approximation and PCP's, Proceedings of the Fourth Annual European Symposium on Algorithms, p.62-75, September 25-27, 1996
	21	Luca Trevisan, Approximating Satisfiable Satisfiability Problems (Extended Abstract), Proceedings of the 5th Annual European Symposium on Algorithms, p.472-485, September 15-17, 1997
	22	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 [doi>10.1145/276698.276769]
	23	L. Trevisan , G. B. Sorkin , M. Sudan , D. P. Williamson, Gadgets Approximation, and Linear Programming, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.617, October 14-16, 1996
	24	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
	25	Uri Zwick, Finding almost-satisfying assignments, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.551-560, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276869]

CITED BY 27

	Aravind Srinivasan, On the approximability of clique and related maximization problems, Journal of Computer and System Sciences, v.67 n.3, p.633-651, November 2003
	Aravind Srinivasan, The value of strong inapproximability results for clique, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.144-152, May 21-23, 2000, Portland, Oregon, United States
	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
	Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Lars Engebretsen , Jonas Holmerin , Alexander Russell, Inapproximability results for equations over finite groups, Theoretical Computer Science, v.312 n.1, p.17-45, 26 January 2004
	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
	Irit Dinur , Venkatesan Guruswami , Subhash Khot , Oded Regev, A new multilayered PCP and the hardness of hypergraph vertex cover, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Lars Engebretsen , Jonas Holmerin, Towards optimal lower bounds for clique and chromatic number, Theoretical Computer Science, v.299 n.1-3, p.537-584, 18 April 2003
	Johan Håstad , Avi Wigderson, Simple analysis of graph tests for linearity and PCP, Random Structures & Algorithms, v.22 n.2, p.139-160, March 2003
	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
	Johan Håstad, Every 2-CSP allows nontrivial approximation, 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
	Subhash Khot, Guest column: inapproximability results via Long Code based PCPs, ACM SIGACT News, v.36 n.2, June 2005
	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
	Matthew Andrews , Lisa Zhang, Hardness of the undirected edge-disjoint paths problem, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Uriel Feige , Daniel Reichman, On the hardness of approximating Max-Satisfy, Information Processing Letters, v.97 n.1, p.31-35, 16 January 2006
	Adi Avidor , Ricky Rosen, A note on unique games, Information Processing Letters, v.99 n.3, p.87-91, 16 August 2006
	Alex Samorodnitsky , Luca Trevisan, Gowers uniformity, influence of variables, and PCPs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	David Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Matthew Andrews , Lisa Zhang, Logarithmic hardness of the undirected edge-disjoint paths problem, Journal of the ACM (JACM), v.53 n.5, p.745-761, September 2006
	Ryan O'Donnell , Yi Wu, Conditional hardness for satisfiable 3-CSPs, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Alex Samorodnitsky, Low-degree tests at large distances, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	William Gasarch , James Glenn , Clyde P. Kruskal, Finding large 3-free sets I: The small n case, Journal of Computer and System Sciences, v.74 n.4, p.628-655, June, 2008
	Michael Ben-or , Don Coppersmith , Mike Luby , Ronitt Rubinfeld, Non-Abelian homomorphism testing, and distributions close to their self-convolutions, Random Structures & Algorithms, v.32 n.1, p.49-70, January 2008
	Lars Engebretsen , Jonas Holmerin, More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP, Random Structures & Algorithms, v.33 n.4, p.497-514, December 2008
	Per Austrin , Johan Håstad, Randomly supported independence and resistance, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA