[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 n^1-ε. 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 NC¹. 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.

[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.

[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 Σ₂^p 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].