Improved non-approximability results

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved non-approximability results

Full text

Pdf (967 KB)

Source

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

Montreal, Quebec, Canada

Pages: 184 - 193

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Mihir Bellare	Advanced Networking Laboratory, IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY
Madhu Sudan	Research Division, IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/195058.195129 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	N. ALON, O. GOLDREICH, J. H#.STAD AND R. PER- ALTA. Simple constructions of almost k-wise independent random variables. FOCS 90.
	2	S. ARORA, C. LUND, R. M OTWANI, M. SUDAN AND M. SZEGED~. Proof verification and intractability of approximation problems. FOCS 92.
	3	S. ARORA AND S. SAFRA. Probabilistic checking of proofs: a new characterization of NP. FOCS 92.
	4	L. BABAI, L. FORTNOW AND C. LUND. Nondeterministic Exponential time has two-prover interactive protocols. FOCS 90.
	5	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]
	6	Donald Beaver , J. Feigenbaum, Hiding instances in multioracle queries, Proceedings of the seventh annual symposium on Theoretical aspects of computer science, p.37-48, February 1990, Rouen, France
	7	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]
	8	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]
	9	Piotr Berman , Georg Schnitger, On the complexity of approximating the independent set problem, Information and Computation, v.96 n.1, p.77-94, Jan. 1992 [doi>10.1016/0890-5401(92)90056-L]
	10	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]
	11	Ravi Boppana , Magnús M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, BIT, v.32 n.2, p.180-196, 1992 [doi>10.1007/BF01994876]
	12	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]
	13	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]
	14	U. FEmE Am:) L. Lov#sz. Two-prover one round proof systems: Their power and their problems. STOC 92.
	15	N. KAHALE. On the second eigenvalue and hnear expansion of regular graphs. FOCS 92.
	16	R. KARP. Reducibility among combinatorial problems. Complexity of Computer Computations, Miller and Thatcher (eds.), Plenum Press, New York (1972).
	17	S. KHANNA, N. LINIAL AND S. SAFRA. On the hardness of approximating the chromatic number. ISTCS 93.
	18	Daphne Koller , Nimrod Megiddo, Constructing small sample spaces satisfying given constraints, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.268-277, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167168]
	19	Dror Lapidot , Adi Shamir, Fully parallelized multi prover protocols for NEXP-time (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.13-18, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185342]
	20	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]
	21	J. Naor , M. Naor, Small-bias probability spaces: efficient constructions and applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.213-223, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100244]
	22	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]
	23	L. Sell.MAN. Sample spaces uniform on neighborhoods. STOC 92.
	24	Mihalis Yannakakis, On the approximation of maximum satisfiability, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.1-9, September 1992, Orlando, Florida, United States
	25	D. ZUCKERMAN. NP-Complete Problems have a version that is hard to Approximate. Structure in Complexzty Theory, 1993.

CITED BY 33

	Oh-Heum Kwon , Kyung-Yong Chwa, Approximation algorithms for general parallel task scheduling, Information Processing Letters, v.81 n.3, p.143-150, 14 February 2002
	Marcus Peinado, Hard graphs for the randomized Boppana-Halldórsson algorithm for MAXCLIQUE, Nordic Journal of Computing, v.1 n.4, p.493-515, Winter 1994
	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
	L. J. Cowen , W. Goddard , C. E. Jesurum, Coloring with defect, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.548-557, January 05-07, 1997, New Orleans, Louisiana, United States
	Frank Nielsen, On point covers of c-oriented polygons, Theoretical Computer Science, v.263 n.1-2, p.17-29, July 28 2001
	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
	Uriel Feige, Randomized graph products, chromatic numbers, and Lovasz j-function, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.635-640, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Andrea E. F. Clementi , Miriam Di Ianni, On the hardness of approximating optimum schedule problems in store and forward networks, IEEE/ACM Transactions on Networking (TON), v.4 n.2, p.272-280, April 1996
	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, 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
	David Karger , Rajeev Motwani , Madhu Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM (JACM), v.45 n.2, p.246-265, March 1998
	Magnús M. Halldórsson , Jaikumar Radhakrishnan, Improved approximations of independent sets in bounded-degree graphs via subgraph removal, Nordic Journal of Computing, v.1 n.4, p.475-492, Winter 1994
	Magnús M. Halldórsson , Kazuo Iwano , Naoki Katoh , Takeshi Tokuyama, Finding subsets maximizing minimum structures, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.150-159, January 22-24, 1995, San Francisco, California, United States
	Maria Bonet , Mike Steel , Tandy Warnow , Shibu Yooseph, Better methods for solving parsimony and compatibility, Proceedings of the second annual international conference on Computational molecular biology, p.40-49, March 22-25, 1998, New York, New York, United States
	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
	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
	Ari Juels , Marcus Peinado, Hiding Cliques for Cryptographic Security, Designs, Codes and Cryptography, v.20 n.3, p.269-280, July 2000
	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
	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
	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
	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
	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
	Vangelis T. Paschos, A survey of approximately optimal solutions to some covering and packing problems, ACM Computing Surveys (CSUR), v.29 n.2, p.171-209, June 1997
	V. Th. Paschos, Polynomial approximation and graph-coloring, Computing, v.70 n.1, p.41-86, March 2003
	M. Kiwi, Algebraic testing and weight distributions of codes, Theoretical Computer Science, v.299 n.1-3, p.81-106, 18 April 2003
	Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001
	Oded Goldreich, Property testing in massive graphs, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	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 , 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
	András Faragó, On the complexity of finding sparsest and densest parts in wireless networks, Wireless Networks, v.1 n.2, p.221-226, 1995
	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
	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
	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