[1]   Scott Aaronson: A counterexample to the Generalized Linial-Nisan Conjecture. Electron. Colloq. on Comput. Complexity (ECCC), 17:109, 2010. ECCC.

[2]   Scott Aaronson: BQP and the polynomial hierarchy. In Proc. 42nd STOC, pp. 141–150. ACM Press, 2010. See also in ECCC. [doi:10.1145/1806689.1806711]

[3]   Miklós Ajtai: Σ₁¹-formulae on finite structures. Ann. Pure Appl. Logic, 24(1):1–48, 1983. [doi:10.1016/0168-0072(83)90038-6]

[4]   Miklós Ajtai and Michael Ben-Or: A theorem on probabilistic constant depth computations. In Proc. 16th STOC, pp. 471–474. ACM Press, 1984. [doi:10.1145/800057.808715]

[5]   Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz: Cryptography in NC⁰. SIAM J. Comput., 36(4):845–888, 2006. Preliminary version in FOCS’04. [doi:10.1137/S0097539705446950]

[6]   James Aspnes, Richard Beigel, Merrick L. Furst, and Steven Rudich: The expressive power of voting polynomials. Combinatorica, 14(2):135–148, 1994. Preliminary version in STOC’91. [doi:10.1007/BF01215346]

[7]   Boaz Barak, Ronen Shaltiel, and Avi Wigderson: Computational analogues of entropy. In Proc. 7th Internat. Workshop on Randomization and Computation (RANDOM’03), pp. 200–215. Springer, 2003. [doi:10.1007/978-3-540-45198-3_18]

[8]   Richard Beigel: When do extra majority gates help? Polylog(N) majority gates are equivalent to one. Comput. Complexity, 4(4):314–324, 1994. Preliminary version in STOC’92. [doi:10.1007/BF01263420]

[9]   Ethan Bernstein and Umesh V. Vazirani: Quantum complexity theory. SIAM J. Comput., 26(5):1411–1473, 1997. Preliminary version in STOC’93. [doi:10.1137/S0097539796300921]

[10]   Manuel Blum and Silvio Micali: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput., 13(4):850–864, 1984. Preliminary version in FOCS’82. [doi:10.1137/0213053]

[11]   Mark Braverman, Anup Rao, Ran Raz, and Amir Yehudayoff: Pseudorandom generators for regular branching programs. In Proc. 51st FOCS, pp. 40–47. IEEE Comp. Soc. Press, 2010. See also at ECCC. [doi:10.1109/FOCS.2010.11]

[12]   Joshua Brody and Elad Verbin: The coin problem, and pseudorandomness for branching programs. In Proc. 51st FOCS, pp. 30–39. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.10]

[13]   Joan Feigenbaum and Lance Fortnow: Random-self-reducibility of complete sets. SIAM J. Comput., 22(5):994–1005, 1993. Preliminary version in SCT’91. [doi:10.1137/0222061]

[14]   Yuval Filmus: Smolensky’s polynomial method, 2010. See author’s home page.

[15]   Oded Goldreich: Foundations of Cryptography, Volume 1: Basic Tools. Cambridge Univ. Press, 2001. See also author’s home page.

[16]   Oded Goldreich and Leonid A. Levin: A hard-core predicate for all one-way functions. In Proc. 21st STOC, pp. 25–32. ACM Press, 1989. [doi:10.1145/73007.73010]

[17]   Oded Goldreich and Avi Wigderson: Tiny families of functions with random properties: A quality-size trade-off for hashing. Random Structures & Algorithms, 11(4):315–343, 1997. Preliminary version in STOC’94. See also at ECCC. [doi:10.1002/(SICI)1098-2418(199712)11:4¡315::AID-RSA3¿3.0.CO;2-1]

[18]   Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy N. Rothblum: Verifying and decoding in constant depth. In Proc. 39th STOC, pp. 440–449. ACM Press, 2007. [doi:10.1145/1250790.1250855]

[19]   Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy N. Rothblum: A (de)constructive approach to program checking. In Proc. 40th STOC, pp. 143–152. ACM Press, 2008. See also at ECCC. [doi:10.1145/1374376.1374399]

[20]    Shafi Goldwasser and Silvio Micali: Probabilistic encryption. J. Comput. System Sci., 28(2):270–299, 1984. [doi:10.1016/0022-0000(84)90070-9]

[21]   Venkatesan Guruswami, Christopher Umans, and Salil P. Vadhan: Unbalanced expanders and randomness extractors from Parvaresh–Vardy codes. J. ACM, 56(4), 2009. Preliminary version in CCC’07. [doi:10.1145/1538902.1538904]

[22]   Johan Håstad: Computational limitations of small-depth circuits. MIT Press, 1987. [ACM:SERIES9056.27031]

[23]   Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby: A pseudorandom generator from any one-way function. SIAM J. Comput., 28(4):1364–1396, 1999. Preliminary versions in STOC’89 and STOC’90. [doi:10.1137/S0097539793244708]

[24]   Russell Impagliazzo: Hard-core distributions for somewhat hard problems. In Proc. 36th FOCS, pp. 538–545. IEEE Comp. Soc. Press, 1995. [doi:10.1109/SFCS.1995.492584]

[25]   Russell Impagliazzo, Noam Nisan, and Avi Wigderson: Pseudorandomness for network algorithms. In Proc. 26th STOC, pp. 356–364. ACM Press, 1994. [doi:10.1145/195058.195190]

[26]   Yuval Ishai and Eyal Kushilevitz: Randomizing polynomials: A new representation with applications to round-efficient secure computation. In Proc. 41st FOCS, pp. 294–304. IEEE Comp. Soc. Press, 2000. [doi:10.1109/SFCS.2000.892118]

[27]   Yuval Ishai and Eyal Kushilevitz: Perfect constant-round secure computation via perfect randomizing polynomials. In Proc. 29th Internat. Colloq. on Automata, Languages and Programming (ICALP’02), pp. 244–256. Springer, 2002. [doi:10.1007/3-540-45465-9_22]

[28]   Alexei Kitaev, Alexander Shen, and Mikhail Vyalyi: Classical and Quantum Computation. Amer. Math. Soc., 2002. [ACM:863284]

[29]    Michal Koucký, Prajakta Nimbhorkar, and Pavel Pudlák: Pseudorandom generators for group products: extended abstract. In Proc. 43rd STOC, pp. 263–272. ACM Press, 2011. [doi:10.1145/1993636.1993672]

[30]   Chi-Jen Lu, Shi-Chun Tsai, and Hsin-Lung Wu: Complexity of hard-core set proofs. Comput. Complexity, 20(1):145–171, 2011. Preliminary version in ICALP’07. [doi:10.1007/s00037-011-0003-7]

[31]   Noam Nisan: Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63–70, 1991. [doi:10.1007/BF01375474]

[32]   Noam Nisan: Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449–461, 1992. Preliminary version in STOC’90. [doi:10.1007/BF01305237]

[33]   Noam Nisan and Avi Wigderson: Hardness vs randomness. J. Comput. System Sci., 49(2):149–167, 1994. Preliminary version in FOCS’88. [doi:10.1016/S0022-0000(05)80043-1]

[34]   Noam Nisan and David Zuckerman: Randomness is linear in space. J. Comput. System Sci., 52(1):43–52, 1996. Preliminary version in STOC’93. [doi:10.1006/jcss.1996.0004]

[35]   Ran Raz and Omer Reingold: On recycling the randomness of states in space bounded computation. In Proc. 31st STOC, pp. 159–168. ACM Press, 1999. [doi:10.1145/301250.301294]

[36]   Alexander Razborov: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mat. Zametki, 41(4):598–607, 1987. English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987. [doi:10.1007/BF01137685]

[37]   Ronen Shaltiel and Emanuele Viola: Hardness amplification proofs require majority. SIAM J. Comput., 39(7):3122–3154, 2010. Preliminary version in STOC’08. See also at ECCC. [doi:10.1137/080735096]

[38]   Roman Smolensky: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proc. 19th STOC, pp. 77–82. ACM Press, 1987. [doi:10.1145/28395.28404]

[39]   Roman Smolensky: On representations by low-degree polynomials. In Proc. 34th FOCS, pp. 130–138. IEEE Comp. Soc. Press, 1993. [doi:10.1109/SFCS.1993.366874]

[40]   Madhu Sudan, Luca Trevisan, and Salil P. Vadhan: Pseudorandom generators without the XOR lemma. J. Comput. System Sci., 62(2):236–266, 2001. Preliminary version in STOC’99. See also at ECCC. [doi:10.1006/jcss.2000.1730]

[41]   Emanuele Viola: Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates. SIAM J. Comput., 36(5):1387–1403, 2007. Preliminary version in CCC’05. See also at ECCC. [doi:10.1137/050640941]

[42]   Emanuele Viola: On approximate majority and probabilistic time. Comput. Complexity, 18(3):337–375, 2009. Preliminary version in CCC’07. [doi:10.1007/s00037-009-0267-3]

[43]   Emanuele Viola: On the power of small-depth computation. Foundations and Trends in Theoretical Computer Science, 5(1):1–72, 2009. [doi:10.1561/0400000033]

[44]   Emanuele Viola: The complexity of distributions. SIAM J. Comput., 41(1):191–218, 2012. Preliminary version in FOCS’10. [doi:10.1137/100814998]

[45]   John Watrous: Succinct quantum proofs for properties of finite groups. In Proc. 41st FOCS, pp. 537–546. IEEE Comp. Soc. Press, 2000. [doi:10.1109/SFCS.2000.892141]

[46]   Ryan Williams: Non-uniform ACC circuit lower bounds. In Proc. 26th IEEE Conf. on Computational Complexity (CCC’11), pp. 115–125. IEEE Comp. Soc. Press, 2011. [doi:10.1109/CCC.2011.36]

[47]   Ryan Williams: Improving exhaustive search implies superpolynomial lower bounds. SIAM J. Comput., 42(3):1218–1244, 2013. Preliminary version in STOC’10. [doi:10.1137/10080703X]

[48]   Andrew Chi-Chih Yao: Theory and applications of trapdoor functions (extended abstract). In Proc. 23rd FOCS, pp. 80–91. IEEE Comp. Soc. Press, 1982. [doi:10.1109/SFCS.1982.45]

[49]   David Zuckerman: Randomness-optimal oblivious sampling. Random Structures & Algorithms, 11(4):345–367, 1997. Preliminary version in STOC’96. [doi:10.1002/(SICI)1098-2418(199712)11:4¡345::AID-RSA4¿3.0.CO;2-Z]