Relations between average case complexity and approximation complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Relations between average case complexity and approximation complexity

Full text

Pdf (219 KB)

Source

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

Montreal, Quebec, Canada

SESSION: Session 9A table of contents

Pages: 534 - 543

Year of Publication: 2002

ISBN:1-58113-495-9

Author

Uriel Feige

Weizmann Institute, Rehovot, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract 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/509907.509985 What is a DOI?

ABSTRACT

We investigate relations between average case complexity and the complexity of approximation. Our preliminary findings indicate that this is a research direction that leads to interesting insights. Under the assumption that refuting 3SAT is hard on average on a natural distribution, we derive hardness of approximation results for min bisection, dense k-subgraph, max bipartite clique and the 2-catalog segmentation problem. No NP-hardness of approximation results are currently known for these problems.

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	M. Ajtai, Generating hard instances of lattice problems (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.99-108, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237838]
	2	Noga Alon , Uriel Feige , Avi Wigderson , David Zuckerman, Derandomized graph products, Computational Complexity, v.5 n.1, p.60-75, Jan. 1995 [doi>10.1007/BF01277956]
	3	Paul Beame , Richard Karp , Toniann Pitassi , Michael Saks, On the complexity of unsatisfiability proofs for random k-CNF formulas, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.561-571, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276870]
	4	Eli Ben-Sasson , Avi Wigderson, Short proofs are narrow—resolution made simple, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.517-526, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301392]
	5	Vašek Chvátal , Endre Szemerédi, Many hard examples for resolution, Journal of the ACM (JACM), v.35 n.4, p.759-768, Oct. 1988 [doi>10.1145/48014.48016]
	6	Yevgeniy Dodis , Venkatesan Guruswami , Sanjeev Khanna, The 2-catalog segmentation problem, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.897-898, January 17-19, 1999, Baltimore, Maryland, United States
	7	Uriel Feige, Guy Kortsarz, and David Peleg. "The dense $k$-subgraph problem". Algorithmica (2001) 29: 410--421.
	8	U. Feige , R. Krauthgamer, A polylogarithmic approximation of the minimum bisection, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.105, November 12-14, 2000
	9	Uriel Feige , Michael Langberg, Approximation algorithms for maximization problems arising in graph partitioning, Journal of Algorithms, v.41 n.2, p.174-211, November 2001 [doi>10.1006/jagm.2001.1183]
	10	Ehud Friedgut. "Necessary and sufficient conditions for sharp thresholds of graph properties and the k-SAT problem". Journal of the American (MATH)ematical Society 12, 1999, 1017--1054.
	11	Joel Friedman , Andreas Goerdt, Recognizing More Unsatisfiable Random 3-SAT Instances Efficiently, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.310-321, July 08-12, 2001
	12	Andreas Goerdt , Michael Krivelevich, Efficient Recognition of Random Unsatisfiable k-SAT Instances by Spectral Methods, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, p.294-304, February 15-17, 2001
	13	Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
	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	Howard Karloff , Uri Zwick, A 7/8-Approximation Algorithm for MAX 3SAT?, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.406, October 19-22, 1997
	16	Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Segmentation problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.473-482, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276860]
	17	Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
	18	Leonid A Levin, Average case complete problems, SIAM Journal on Computing, v.15 n.1, p.285-286, Feb. 1986 [doi>10.1137/0215020]
	19	Michael Mitzenmacher, On the Hardness of Finding Optimal Multiple Preset Dictionaries, Proceedings of the Data Compression Conference (DCC '01), p.411, March 27-29, 2001
	20	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 [doi>10.1145/335305.335329]
	21	H. U. Simon. "On approximate solutions for combinatorial optimization problems". SIAM J. Algebraic Discrete Methods, 3:294--310, 1990.
	22	"Phase Transitions in Combinatorial Problems." Theoretical Computer Science, Volume 265, Numbers 1-2. Guest Editors: O. Dubios, R. Monasson, B. Selma, R. Zecchina. Elsevier.
	23	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
	24	Uri Zwick, Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.679-687, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301431]

CITED BY 33

	Oded Regev, On lattices, learning with errors, random linear codes, and cryptography, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Abraham Flaxman, A spectral technique for random satisfiable 3CNF formulas, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Amin Coja-Oghlan , Andreas Goerdt , André Lanka , Frank Schädlich, Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT, Theoretical Computer Science, v.329 n.1-3, p.1-45, 13 December 2004
	W. Fernandez de la Vega , Marek Karpinski , Claire Kenyon, Approximation schemes for Metric Bisection and partitioning, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Nina Mishra , Dana Ron , Ram Swaminathan, A New Conceptual Clustering Framework, Machine Learning, v.56 n.1-3, p.115-151
	Jonas Holmerin , Subhash Khot, A new PCP outer verifier with applications to homogeneous linear equations and max-bisection, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Christopher Jermaine, Finding the most interesting correlations in a database: how hard can it be?, Information Systems, v.30 n.1, p.21-46, March 2005
	Subhash Khot, Guest column: inapproximability results via Long Code based PCPs, ACM SIGACT News, v.36 n.2, June 2005
	Michael Alekhnovich, Lower bounds for k-DNF resolution on random 3-CNFs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Erik D. Demaine , Mohammad Taghi Hajiaghayi , Uriel Feige , Mohammad R. Salavatipour, Combination can be hard: approximability of the unique coverage problem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.162-171, January 22-26, 2006, Miami, Florida
	Uriel Feige , MohammadTaghi Hajiaghayi , James R. Lee, Improved approximation algorithms for minimum-weight vertex separators, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Mohammad Taghi Hajiaghayi , Kamal Jain, The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.631-640, January 22-26, 2006, Miami, Florida
	Moses Charikar , Konstantin Makarychev , Yury Makarychev, Directed metrics and directed graph partitioning problems, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.51-60, January 22-26, 2006, Miami, Florida
	Amin Coja-Oghlan, A spectral heuristic for bisecting random graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	David S. Johnson, The NP-completeness column: The many limits on approximation, ACM Transactions on Algorithms (TALG), v.2 n.3, p.473-489, July 2006
	Julia Chuzhoy , Sanjeev Khanna, Hardness of cut problems in directed graphs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Stavros G. Kolliopoulos , George Steiner, Partially ordered knapsack and applications to scheduling, Discrete Applied Mathematics, v.155 n.8, p.889-897, April, 2007
	Dimitris Achlioptas , Assaf Naor , Yuval Peres, On the maximum satisfiability of random formulas, Journal of the ACM (JACM), v.54 n.2, p.10-es, April 2007
	Amin Coja-Oghlan, Solving NP-hard semirandom graph problems in polynomial expected time, Journal of Algorithms, v.62 n.1, p.19-46, January, 2007
	Andrej Bogdanov , Luca Trevisan, Average-case complexity, Foundations and Trends® in Theoretical Computer Science, v.2 n.1, p.1-106, October 2006
	Yon Dourisboure , Filippo Geraci , Marco Pellegrini, Extraction and classification of dense communities in the web, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
	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
	Amin Coja-oghlan , Andreas Goerdt , André Lanka, Strong Refutation Heuristics for Random k-SAT, Combinatorics, Probability and Computing, v.16 n.1, p.5-28, January 2007
	Elitza Maneva , Elchanan Mossel , Martin J. Wainwright, A new look at survey propagation and its generalizations, Journal of the ACM (JACM), v.54 n.4, p.17-es, July 2007
	Andreas Goerdt , Tomasz Jurdziński, Some Results on Random Unsatisfiable k-Sat Instances and Approximation Algorithms Applied to Random Structures, Combinatorics, Probability and Computing, v.12 n.3, p.245-267, May 2003
	Barbara M. Anthony , Vineet Goyal , Anupam Gupta , Viswanath Nagarajan, A plant location guide for the unsure, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1164-1173, January 20-22, 2008, San Francisco, California
	Akiko Suzuki , Takeshi Tokuyama, Dense subgraph problems with output-density conditions, ACM Transactions on Algorithms (TALG), v.4 n.4, p.1-18, August 2008
	Amin Coja-Oghlan , Uriel Feige , Alan Frieze , Michael Krivelevich , Dan Vilenchik, On smoothed k-CNF formulas and the Walksat algorithm, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.451-460, January 04-06, 2009, New York, New York
	Amin Coja-Oghlan , Colin Cooper , Alan Frieze, An efficient sparse regularity concept, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.207-216, January 04-06, 2009, New York, New York
	Robert Krauthgamer , Joseph (Seffi) Naor , Roy Schwartz, Partitioning graphs into balanced components, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.942-949, January 04-06, 2009, New York, New York
	Elad Hazan , Robert Krauthgamer, How hard is it to approximate the best Nash equilibrium?, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.720-727, January 04-06, 2009, New York, New York
	Yon Dourisboure , Filippo Geraci , Marco Pellegrini, Extraction and classification of dense implicit communities in the Web graph, ACM Transactions on the Web (TWEB), v.3 n.2, p.1-36, April 2009
	Benny Applebaum , Yuval Ishai , Eyal Kushilevitz, On Pseudorandom Generators with Linear Stretch in NC0, Computational Complexity, v.17 n.1, p.38-69, April 2008