skip to main content
10.1145/1132516.1132612acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article

Linear degree extractors and the inapproximability of max clique and chromatic number

Published: 21 May 2006 Publication History

Abstract

A randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. We construct new extractors which require only log n + O(1) additional random bits for sources with constant entropy rate. We further construct dispersers, which are similar to one-sided extractors, which use an arbitrarily small constant times log n additional random bits for sources with constant entropy rate. Our extractors and dispersers output 1-α fraction of the randomness, for any α>0.We use our dispersers to derandomize results of Hastad [23] and Feige-Kilian [19] and show that for all ε>0, approximating MAX CLIQUE and CHROMATIC NUMBER to within n1-ε are NP-hard. We also derandomize the results of Khot [29] and show that for some γ > 0, no quasi-polynomial time algorithm approximates MAX CLIQUE or CHROMATIC NUMBER to within n/2(log n)1-γ, unless NP = P.Our constructions rely on recent results in additive number theory and extractors by Bourgain-Katz-Tao [11], Barak-Impagliazzo-Wigderson [5], Barak-Kindler-Shaltiel-Sudakov-Wigderson [6], and Raz [36]. We also simplify and slightly strengthen key theorems in the second and third of these papers, and strengthen a related theorem by Bourgain [10].

References

[1]
M. Agrawal, N. Kayal, and N. Saxena. Primes is in P. Annals of Mathematics, 160:781--793, 2004.
[2]
M. Ajtai, J. Komlós, and E. Szemerédi. Deterministic simulation in Logspace. In 19th STOC, pages 132--140, 1987.
[3]
N. Alon, U. Feige, A. Wigderson, and D. Zuckerman. Derandomized graph products. Computational Complexity, 5:60--75, 1995.
[4]
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45:501--555, 1998.
[5]
B. Barak, R. Impagliazzo, and A. Wigderson. Extracting randomness using few independent sources. In 45th FOCS, pages 384--393, 2004.
[6]
B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, and A. Wigderson. Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors. In 37th STOC, pages 1--10, 2005.
[7]
M. Bellare, O. Goldreich, and M. Sudan. Free bits, PCPs, and nonapproximability -- towards tight results. SIAM Journal on Computing, 27(3):804--915, 1998.
[8]
M. Bellare and M. Sudan. Improved non-approximability results. In 26th STOC, pages 184--193, 1994.
[9]
R. Boppana and M. Halldorsson. Approximating maximum independent sets by excluding subgraphs. Bit, 32:180--196, 1992.
[10]
J. Bourgain. More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 1:1--32, 2005.
[11]
J. Bourgain, N. Katz, and T. Tao. A sum-product estimate in finite fields, and applications. Geometric and Functional Analysis, 14:27--57, 2004.
[12]
B. Chor and O. Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing, 17(2):230--261, 1988.
[13]
A. Cohen and A. Wigderson. Dispersers, deterministic amplification, and weak random sources. In 30th FOCS, pages 14--19, 1989.
[14]
H. Cramer. On the order of magnitude of the difference between consecutive prime numbers. Acta Arithmetica, pages 23--46, 1937.
[15]
Z. Dvir and R. Raz. An improved analysis of mergers. Technical Report TR05-025, Electronic Colloquium on Computational Complexity, 2005.
[16]
L. Engebretsen and J. Holmerin. Towards optimal lower bounds for clique and chromatic number. Theoretical Computer Science, 299:537--584, 2003.
[17]
U. Feige. Randomized graph products, chromatic numbers, and the Lovasz θ function. Combinatorica, 17:79--90, 1997.
[18]
U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43:268--292, 1996.
[19]
U. Feige and J. Kilian. Zero knowledge and the chromatic number. Journal of Computer and System Sciences, 57:187--199, 1998.
[20]
D. Gillman. A Chernoff bound for random walks on expander graphs. SIAM Journal on Computing, 27:1203--1220, 1998.
[21]
O. Goldreich. A sample of samplers -- a computational perspective on sampling (survey). Technical Report TR97-020, Electronic Colloquium on Computational Complexity, 1997.
[22]
M. Halldorsson. A still better performance guarantee for approximate graph coloring. Information Processing Letters, 45:19--23, 1993.
[23]
J. Håstad. Clique is hard to approximate within n1-ε. Acta Mathematica, 182:105--142, 1999.
[24]
J. Hastad and S. Khot. Query efficient PCPs with perfect completeness. In 42nd FOCS, pages 610--619, 2001.
[25]
R. Impagliazzo and D. Zuckerman. How to recycle random bits. In 30th FOCS, pages 248--253, 1989.
[26]
N. Kahale. Eigenvalues and expansion of regular graphs. Journal of the ACM, 42:1091--1106, 1995.
[27]
N. Kahale. Large deviation bounds for Markov chains. Combinatorics, Probability, and Computing, 6:465--474, 1997.
[28]
R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85--103. Plenum Press, New York, 1972.
[29]
S. Khot. Improved inapproximability results for MaxClique, Chromatic Number and Approximate Graph Coloring. In 42nd FOCS, pages 600--609, 2001.
[30]
S. Konyagin. A sum-product estimate in fields of prime order. Technical report, Arxiv, 2003. http://arxiv.org/abs/math.NT/0304217.
[31]
L. Lovasz. On the ratio of the optimal integral and fractional covers. Discrete Mathematics, 13:383--390, 1975.
[32]
C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM, 41:960--981, 1999.
[33]
E. Mossel and C. Umans. On the complexity of approximating the VC dimension. Journal of Computer and System Sciences, 65:660--671, 2002.
[34]
N. Nisan and A. Ta-Shma. Extracting randomness: A survey and new constructions. Journal of Computer and System Sciences, 58:148--173, 1999.
[35]
N. Nisan and D. Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43--52, 1996.
[36]
R. Raz. Extractors with weak random seeds. In 37th STOC, pages 11--20, 2005.
[37]
O. Reingold, R. Shaltiel, and A. Wigderson. Extracting randomness via repeated condensing. In 41st FOCS, pages 22--31, 2000.
[38]
A. Samorodnitsky and L. Trevisan. A PCP characterization of NP with optimal amortized query complexity. In 32nd STOC, pages 191--199, 2000.
[39]
R. Shaltiel. Recent developments in explicit constructions of extractors. Bulletin of the European Association for Theoretical Computer Science, 77:67--95, June 2002.
[40]
A. Ta-Shma, C. Umans, and D. Zuckerman. Loss-less condensers, unbalanced expanders, and extractors. In 33rd STOC, pages 143--152, 2001.
[41]
A. Ta-Shma and D. Zuckerman. Extractor codes. IEEE Transactions on Information Theory, 50:3015--3025, 2004.
[42]
A. Ta-Shma, D. Zuckerman, and S. Safra. Extractors from Reed-Muller codes. Journal of Computer and System Sciences, 2006.
[43]
C. Umans. Hardness of approximating Σ2p minimization problems. In 40th FOCS, pages 465--474, 1999.
[44]
A. Wigderson and D. Xiao. A randomness-efficient sampler for matrix-valued functions and applications. In 46th FOCS, 2005.
[45]
A. Wigderson and D. Zuckerman. Expanders that beat the eigenvalue bound: Explicit construction and applications. Combinatorica, 19(1):125--138, 1999.
[46]
D. Zuckerman. General weak random sources. In 31st FOCS, pages 534--543, 1990.
[47]
D. Zuckerman. Simulating BPP using a general weak random source. Algorithmica, 16:367--391, 1996.
[48]
D. Zuckerman. Randomness-optimal oblivious sampling. Random Structures and Algorithms, 11:345--367, 1997.

Cited By

View all
  • (2024)Gerrymandering Planar GraphsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662896(463-471)Online publication date: 6-May-2024
  • (2024) Group- k consistent measurement set maximization via maximum clique over k -uniform hypergraphs for robust multi-robot map merging The International Journal of Robotics Research10.1177/0278364924125697043:14(2245-2273)Online publication date: 2-Jul-2024
  • (2024)Theoretically and Practically Efficient Maximum Defective Clique SearchProceedings of the ACM on Management of Data10.1145/36771422:4(1-27)Online publication date: 30-Sep-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing
May 2006
786 pages
ISBN:1595931341
DOI:10.1145/1132516
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 May 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. NP-hard
  2. approximation
  3. chromatic number
  4. clique
  5. disperser
  6. explicit construction
  7. extractor
  8. pseudorandom

Qualifiers

  • Article

Conference

STOC06
Sponsor:
STOC06: Symposium on Theory of Computing
May 21 - 23, 2006
WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25
57th Annual ACM Symposium on Theory of Computing (STOC 2025)
June 23 - 27, 2025
Prague , Czech Republic

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)61
  • Downloads (Last 6 weeks)5
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Gerrymandering Planar GraphsProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3662896(463-471)Online publication date: 6-May-2024
  • (2024) Group- k consistent measurement set maximization via maximum clique over k -uniform hypergraphs for robust multi-robot map merging The International Journal of Robotics Research10.1177/0278364924125697043:14(2245-2273)Online publication date: 2-Jul-2024
  • (2024)Theoretically and Practically Efficient Maximum Defective Clique SearchProceedings of the ACM on Management of Data10.1145/36771422:4(1-27)Online publication date: 30-Sep-2024
  • (2024)Automated Category Tree Construction: Hardness Bounds and AlgorithmsACM Transactions on Database Systems10.1145/366428349:3(1-32)Online publication date: 9-May-2024
  • (2024)Dense Subgraph Discovery Meets Strong Triadic ClosureProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671697(3334-3344)Online publication date: 25-Aug-2024
  • (2024)Dynamic O(Arboricity) Coloring in Polylogarithmic Worst-Case TimeProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649782(1184-1191)Online publication date: 10-Jun-2024
  • (2024)Consensus Tree Under the Ancestor–Descendant Distance is NP-HardJournal of Computational Biology10.1089/cmb.2023.026231:1(58-70)Online publication date: 1-Jan-2024
  • (2024)On the parameterized complexity of non-hereditary relaxations of cliqueTheoretical Computer Science10.1016/j.tcs.2024.1146251003:COnline publication date: 1-Jul-2024
  • (2024)Repeatedly matching items to agents fairly and efficientlyTheoretical Computer Science10.1016/j.tcs.2023.114246981(114246)Online publication date: Jan-2024
  • (2024)The complexity of growing a graphJournal of Computer and System Sciences10.1016/j.jcss.2024.103587(103587)Online publication date: Sep-2024
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media