The DOI matches its Crossref record; 39 of the 39 references it cites were found in a registry or an index.
Linear degree extractors and the inapproximability of max clique and chromatic number
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].
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
Reducibility Among Combinatorial Problems
Karp, R. M. (2010) · 50 Years of Integer Programming 1958-2008 · doi:10.1007/978-3-540-68279-0_8 · Cited by 2,490
Expander graphs and their applications
Hoory, S., Linial, N., & Wigderson, A. (2006) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-06-01126-8 · Cited by 1,723
Proof verification and the hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998) · Journal of the ACM · doi:10.1145/278298.278306 · Cited by 1,413
Clique is hard to approximate within n1−ε
Håstad, J. (1999) · Acta Mathematica · doi:10.1007/bf02392825 · Cited by 1,369
On the ratio of optimal integral and fractional covers
Lovász, L. (1975) · Discrete Mathematics · doi:10.1016/0012-365x(75)90058-8 · Cited by 1,114
Agrawal, M., Kayal, N., & Saxena, N. (2004) · Annals of Mathematics · doi:10.4007/annals.2004.160.781 · Cited by 931
On the hardness of approximating minimization problems
Lund, C., & Yannakakis, M. (1994) · Journal of the ACM · doi:10.1145/185675.306789 · Cited by 872
Nisan, N., & Zuckerman, D. (1996) · Journal of Computer and System Sciences · doi:10.1006/jcss.1996.0004 · Cited by 634
Self-citationUnbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
Chor, B., & Goldreich, O. (1988) · SIAM Journal on Computing · doi:10.1137/0217015 · Cited by 544
Interactive proofs and the hardness of approximating cliques
Feige, U., Goldwasser, S., Lovász, L., Safra, M., & Szegedy, M. (1996) · Journal of the ACM · doi:10.1145/226643.226652 · Cited by 525
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
Bellare, M., Goldreich, O., & Sudan, M. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539796302531 · Cited by 453
Impagliazzo, R., & Zuckerman, D. (1989) · 30th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63486 · Cited by 387
Self-citationApproximating maximum independent sets by excluding subgraphs
Boppana, R., & Halldórsson, M. M. (1992) · BIT · doi:10.1007/bf01994876 · Cited by 359
Zero Knowledge and the Chromatic Number
Feige, U., & Kilian, J. (1998) · Journal of Computer and System Sciences · doi:10.1006/jcss.1998.1587 · Cited by 334
Existence and Explicit Constructions of q + 1 Regular Ramanujan Graphs for Every Prime Power q
Morgenstern, M. (1994) · Journal of Combinatorial Theory, Series B · doi:10.1006/jctb.1994.1054 · Cited by 310
RECENT DEVELOPMENTS IN EXPLICIT CONSTRUCTIONS OF EXTRACTORS
SHALTIEL, R. (2004) · Current Trends in Theoretical Computer Science · doi:10.1142/9789812562494_0013 · Cited by 291
A still better performance guarantee for approximate graph coloring
Halldórsson, M. M. (1993) · Information Processing Letters · doi:10.1016/0020-0190(93)90246-6 · Cited by 224
Dispersers, deterministic amplification, and weak random sources
Cohen, A., & Wigderson, A. (1989) · 30th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63449 · Cited by 182
Extractors with weak random seeds
Raz, R. (2005) · Proceedings of the thirty-seventh annual ACM symposium on Theory of computing · doi:10.1145/1060590.1060593 · Cited by 168
Improved non-approximability results
Bellare, M., & Sudan, M. (1994) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/195058.195129 · Cited by 162
Extracting Randomness: A Survey and New Constructions
Nisan, N., & Ta‐Shma, A. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1546 · Cited by 158
Alon, N., Feige, U., Wigderson, A., & Zuckerman, D. (1995) · Computational Complexity · doi:10.1007/bf01277956 · Cited by 152
Self-citationSimulating BPP Using a General Weak Random Source
Zuckerman, D. (1996) · Algorithmica · doi:10.1007/bf01940870 · Cited by 147
Self-citationRandomness-optimal oblivious sampling
Zuckerman, D. (1997) · Random Structures and Algorithms · Cited by 145
Self-citationLoss-less condensers, unbalanced expanders, and extractors
Ta‐Shma, A., Umans, C., & Zuckerman, D. (2001) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/380752.380790 · Cited by 127
Self-citationEigenvalues and expansion of regular graphs
Kahalé, N. (1995) · Journal of the ACM · doi:10.1145/210118.210136 · Cited by 110
Zuckerman, D. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89574 · Cited by 108
Self-citationExpanders That Beat the Eigenvalue Bound: Explicit Construction and Applications
Wigderson, A., & Zuckerman, D. (1999) · COMBINATORICA · doi:10.1007/s004930050049 · Cited by 103
Self-citationBarak, B., Kindler, G., Shaltiel, R., Benny Sudakov, C., & Wigderson, A. (2005) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1060590.1060592 · Cited by 86
Lossless Condensers, Unbalanced Expanders, And Extractors
Ta‐Shma, A., Umans, C., & Zuckerman, D. (2007) · COMBINATORICA · doi:10.1007/s00493-007-0053-2 · Cited by 71
Self-citationRandomized graph products, chromatic numbers, and Lovasz j-function
Feige, U. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225281 · Cited by 64
Extracting randomness via repeated condensing
Reingold, O., Shaltiel, R., & Wigderson, A. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892008 · Cited by 61
Ta‐Shma, A., & Zuckerman, D. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.838377 · Cited by 59
Self-citationExtractors from Reed–Muller codes
Ta‐Shma, A., Zuckerman, D., & Safra, M. (2006) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2005.05.010 · Cited by 54
Self-citationHardness of Approximating Minimization Problems
Umans, C. (1999) · Cited by 45
A Probability Inequality for the Occupation Measure of a Reversible Markov Chain
Dinwoodie, I. H. (1995) · The Annals of Applied Probability · doi:10.1214/aoap/1177004826 · Cited by 38
Randomized graph products, chromatic numbers, and the Lov�sz ?-function
Feige, U. (1997) · COMBINATORICA · doi:10.1007/bf01196133 · Cited by 32
A Randomness-Efficient Sampler for Matrix-valued Functions and Applications
Wigderson, A., & Xiao, D. (2005) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2005.8 · Cited by 15
Cited by
Expander graphs and their applications
Hoory, S., Linial, N., & Wigderson, A. (2006) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-06-01126-8 · Cited by 1,723
Most Tensor Problems Are NP-Hard
Hillar, C. J., & Lim, L.-H. (2013) · Journal of the ACM · doi:10.1145/2512329 · Cited by 1,099
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E. G., Venturelli, D., & Biswas, R. (2019) · Algorithms · doi:10.3390/a12020034 · Cited by 772
A review on algorithms for maximum clique problems
Wu, Q., & Hao, J.-K. (2015) · European Journal of Operational Research · doi:10.1016/j.ejor.2014.09.064 · Cited by 314
Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
Guruswami, V., Umans, C., & Vadhan, S. (2009) · Journal of the ACM · doi:10.1145/1538902.1538904 · Cited by 281
Metadata
- Authors
- Zuckerman, D.
- Venue
- Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing
- Publisher
- ACM
- Published
- 2006-05-21
- Pages
- 681-690
- OpenAlex
- W2126186592
- Cited by
- 398
- References
- 39
- FWCI
- 14.48
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.