Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number

by David Zuckerman

Theory of Computing, Volume 3(6), pp. 103-128, 2007

Bibliography with links to cited articles

[1] M. Ajtai, J. Komlós, and E. Szemerédi: Deterministic simulation in LOGSPACE. In Proc. 19th STOC, pp. 132-140, 1987. [STOC:28395.28410].
[2] N. Alon, U. Feige, A. Wigderson, and D. Zuckerman: Derandomized graph products. Computational Complexity, 5:60-75, 1995. [Springer:r591795p150lj86q].
[3] 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. [JACM:278298.278306].
[4] B. Barak, R. Impagliazzo, and A. Wigderson: Extracting randomness using few independent sources. In Proc. 45th FOCS, pp. 384-393, 2004. [FOCS:10.1109/FOCS.2004.29].
[5] B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, and A. Wigderson: Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors. In Proc. 37th STOC, pp. 1-10, 2005. [STOC:1060590.1060592].
[6] M. Bellare, O. Goldreich, and M. Sudan: Free bits, PCPs, and nonapproximability - towards tight results. SIAM Journal on Computing, 27(3):804-915, 1998. [SICOMP:10.1137/S0097539796302531].
[7] M. Bellare and M. Sudan: Improved non-approximability results. In Proc. 26th STOC, pp. 184-193, 1994. [STOC:195058.195129].
[8] R. Boppana and M. Halldorsson: Approximating maximum independent sets by excluding subgraphs. Bit, 32:180-196, 1992.
[9] J. Bourgain: More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 1:1-32, 2005. [WorldSci:10.1142/S1793042105000108].
[10] J. Bourgain, A. Glibichuk, and S. Konyagin: Estimates for the number of sums and products and for exponential sums in fields of prime order. Journal of the London Mathematical Society, 73:380-398, 2006. [Cambridge:10.1112/S0024610706022721].
[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. [Springer:s00039-004-0451-1].
[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. [SICOMP:10.1137/0217015].
[13] A. Cohen and A. Wigderson: Dispersers, deterministic amplification, and weak random sources. In Proc.30th FOCS, pp. 14-19, 1989.
[14] I.H. Dinwoodie: A probability inequality for the occupation measure of a reversible markov chain. Annals of Applied Probability, 5:37-43, 1995.
[15] Z. Dvir and R. Raz: Analyzing linear mergers. Technical Report TR05-025, Electronic Colloquium on Computational Complexity, 2005. [ECCC:TR05-025].
[16] L. Engebretsen and J. Holmerin: Towards optimal lower bounds for clique and chromatic number. Theoretical Computer Science, 299:537-584, 2003. [TCS:10.1016/S0304-3975(02)00535-2].
[17] U. Feige: Randomized graph products, chromatic numbers, and the Lovasz θ function. Combinatorica, 17:79-90, 1997. [Springer:x785787h43724566].
[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. [JACM:226643.226652].
[19] U. Feige and J. Kilian: Zero knowledge and the chromatic number. Journal of Computer and System Sciences, 57:187-199, 1998. [JCSS:10.1006/jcss.1998.1587].
[20] O. Gabber and Z. Galil: Explicit construction of linear sized superconcentrators. Journal of Computer and System Sciences, 22:407-420, 1981. [JCSS:10.1016/0022-0000(81)90040-4].
[21] D. Gillman: A Chernoff bound for random walks on expander graphs. SIAM Journal on Computing, 27:1203-1220, 1998. [SICOMP:10.1137/S0097539794268765].
[22] O. Goldreich: A sample of samplers - a computational perspective on sampling (survey). Technical Report TR97-020, Electronic Colloquium on Computational Complexity, 1997. [ECCC:TR97-020].
[23] B. Green: Sum-product estimates. Unpublished lecture notes. Available at author's website, 2005.
[24] M. Halldorsson: A still better performance guarantee for approximate graph coloring. Information Processing Letters, 45:19-23, 1993. [IPL:10.1016/0020-0190(93)90246-6].
[25] J. Håstad: Clique is hard to approximate within n1-ε. Acta Mathematica, 182:105-142, 1999. [Springer:m68h3576646ll648].
[26] J. Hastad and S. Khot: Query efficient PCPs with perfect completeness. In Proc. 42nd FOCS, pp. 610-619, 2001. [FOCS:10.1109/SFCS.2001.959937].
[27] A. Healy: Randomness-efficient sampling within NC1. In Proc. 10th Intern. Workshop on Randomization and Computation (RANDOM), pp. 398-409, 2006. [Springer:b773545612310728].
[28] S. Hoory, N. Linial, and A. Wigderson: Expander graphs and their applications. Bulletin of the American Mathematical Society, 43:439-561, 2006. [ http ]
[29] R. Impagliazzo and D. Zuckerman: How to recycle random bits. In Proc.30th FOCS, pp. 248-253, 1989.
[30] N. Kahale: Eigenvalues and expansion of regular graphs. Journal of the ACM, 42:1091-1106, 1995. [JACM:210118.210136].
[31] N. Kahale: Large deviation bounds for Markov chains. Combinatorics, Probability, and Computing, 6:465-474, 1997. [Cambridge:10.1017/S0963548397003209].
[32] R. M. Karp: Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pp. 85-103. Plenum Press, New York, 1972.
[33] N. Katz and C.-Y. Shen: Garaev's inequality in finite fields not of prime order. Technical report, Arxiv, 2007. [arXiv:math.NT/0703676].
[34] S. Khot: Improved inapproximability results for MaxClique, Chromatic Number and Approximate Graph Coloring. In Proc. 42nd FOCS, pp. 600-609, 2001. [FOCS:10.1109/SFCS.2001.959936].
[35] L. Lovasz: On the ratio of the optimal integral and fractional covers. Discrete Mathematics, 13:383-390, 1975.
[36] A. Lubotzky, R. Philips, and P. Sarnak: Ramanujan graphs. Combinatorica, 8:261-277, 1988. [Springer:k285687344657q53].
[37] C. Lund and M. Yannakakis: On the hardness of approximating minimization problems. Journal of the ACM, 41:960-981, 1994. [JACM:185675.306789].
[38] G.A. Margulis: Explicit group theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators. Problems of Information Transmission, 24:39-46, 1988.
[39] M. Morgenstern: Existence and explicit constructions of q+1 regular Ramanujan graphs for every prime power q. Journal of Combinatorial Theory, Series B, 62:44-62, 1994. [Elsevier:10.1006/jctb.1994.1054].
[40] E. Mossel and C. Umans: On the complexity of approximating the VC dimension. Journal of Computer and System Sciences, 65:660-671, 2002. [JCSS:10.1016/S0022-0000(02)00022-3].
[41] N. Nisan and A. Ta-Shma: Extracting randomness: A survey and new constructions. Journal of Computer and System Sciences, 58:148-173, 1999. [JCSS:10.1006/jcss.1997.1546].
[42] N. Nisan and D. Zuckerman: Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43-52, 1996. [JCSS:10.1006/jcss.1996.0004].
[43] R. Raz: Extractors with weak random seeds. In Proc. 37th STOC, pp. 11-20, 2005. [STOC:1060590.1060593].
[44] O. Reingold, R. Shaltiel, and A. Wigderson: Extracting randomness via repeated condensing. In Proc. 41st FOCS, pp. 22-31, 2000. [FOCS:10.1109/SFCS.2000.892008].
[45] A. Samorodnitsky and L. Trevisan: A PCP characterization of NP with optimal amortized query complexity. In Proc. 32nd STOC, pp. 191-199, 2000. [STOC:335305.335329].
[46] R. Shaltiel: Recent developments in explicit constructions of extractors. Bulletin of the European Association for Theoretical Computer Science, 77:67-95, June 2002. [ .ps ]
[47] A. Ta-Shma, C. Umans, and D. Zuckerman: Lossless condensers, unbalanced expanders, and extractors. Combinatorica, 27:213-240, 2007. [Springer:y86m43u236782602].
[48] A. Ta-Shma and D. Zuckerman: Extractor codes. IEEE Transactions on Information Theory, 50:3015-3025, 2004. [IEEE:10.1109/TIT.2004.838377].
[49] A. Ta-Shma, D. Zuckerman, and S. Safra: Extractors from Reed-Muller codes. Journal of Computer and System Sciences, 72:786-812, 2006. [JCSS:10.1016/j.jcss.2005.05.010].
[50] T. Tao and V. Vu: Additive Combinatorics. Cambridge University Press, 2006.
[51] C. Umans: Hardness of approximating Σ2p minimization problems. In Proc. 40th FOCS, pp. 465-474, 1999. [FOCS:10.1109/SFFCS.1999.814619].
[52] A. Wigderson and D. Xiao: A randomness-efficient sampler for matrix-valued functions and applications. In Proc. 46th FOCS, pp. 397-406, 2005. [FOCS:10.1109/SFCS.2005.8].
[53] A. Wigderson and D. Zuckerman: Expanders that beat the eigenvalue bound: Explicit construction and applications. Combinatorica, 19(1):125-138, 1999. [Springer:wcjlnyjmdxf30b9x].
[54] D. Zuckerman: Simulating BPP using a general weak random source. Algorithmica, 16:367-391, 1996. [Algorithmica:kx95d4u1jvyxh882].
[55] D. Zuckerman: Randomness-optimal oblivious sampling. Random Structures and Algorithms, 11:345-367, 1997. [Wiley:10.1002/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z].

This file has been generated by bibtex2html 1.85.