[1]   Noga Alon, László Babai, and Alon Itai: A fast and simple randomized algorithm for the maximal independent set problem. J. Algorithms, 7(4):567–583, 1986. [doi:10.1016/0196-6774(86)90019-2]

[2]   Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta: Simple constructions of almost k-wise independent random variables. Random Struct. Algor., 3(3):289–304, 1992. [doi:10.1002/rsa.3240030308]

[3]   Benny Chor and Oded Goldreich: On the power of two-point based sampling. J. Complexity, 5(1):96–106, 1989. [doi:10.1016/0885-064X(89)90015-0]

[4]   Scott Diehl and Dieter van Melkebeek: Time-space lower bounds for the polynomial-time hierarchy on randomized machines. SIAM J. Comput., 36(3):563–594, 2006. [doi:10.1137/050642228]

[5]   Michael A. Forbes and Zander Kelley: Pseudorandom generators for read-once branching programs, in any order. In Proc. 59th FOCS, pp. 946–955. IEEE Comp. Soc., 2018. [doi:10.1109/FOCS.2018.00093]

[6]   Lance Fortnow, Richard Lipton, Dieter van Melkebeek, and Anastasios Viglas: Time-space lower bounds for satisfiability. J. ACM, 52(6):835–865, 2005. [doi:10.1145/1101821.1101822]

[7]   Elad Haramaty, Chin Ho Lee, and Emanuele Viola: Bounded independence plus noise fools products. SIAM J. Comput., 47(2):493–523, 2018. Preliminary version in CCC’17. [doi:10.1137/17M1129088]

[8]   Alexander Healy and Emanuele Viola: Constant-depth circuits for arithmetic in finite fields of characteristic two. In Proc. 23rd Symp. Theoret. Aspects of Comp. Sci. (STACS’06), pp. 672–683. Springer, 2006. [doi:10.1007/11672142_55]

[9]   Frederick C. Hennie: One-tape, off-line Turing machine computations. Inform. Control, 8(6):553–578, 1965. [doi:10.1016/S0019-9958(65)90399-2]

[10]   Shlomo Hoory, Nathan Linial, and Avi Wigderson: Expander graphs and their applications. Bull. AMS, 43(4):439–561, 2006. [doi:10.1090/S0273-0979-06-01126-8]

[11]   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]

[12]   Bala Kalyanasundaram and Georg Schnitger: The probabilistic communication complexity of set intersection. SIAM J. Discr. Math., 5(4):545–557, 1992. [doi:10.1137/0405044]

[13]   Clemens Lautemann: BPP and the polynomial hierarchy. Inform. Process. Lett., 17(4):215–217, 1983. [doi:10.1016/0020-0190(83)90044-3]

[14]   Richard Lipton: Old ideas and lower bounds on SAT. Gödel’s lost letter and P=NP, 2010. Author’s website.

[15]   Wolfgang Maass: Combinatorial lower bound arguments for deterministic and nondeterministic Turing machines. Trans. AMS, 292(2):675–693, 1985. [doi:10.2307/2000238]

[16]   Wolfgang Maass and Amir Schorr: Speed-up of Turing machines with one work tape and a two-way input tape. SIAM J. Comput., 16(1):195–202, 1987. [doi:10.1137/0216016]

[17]   Dieter van Melkebeek: Time-space lower bounds for NP-complete problems. Current Trends Theor. Comp. Sci., pp. 265–291, 2004. [doi:10.1142/9789812562494_0015]

[18]   Dieter van Melkebeek: A survey of lower bounds for satisfiability and related problems. Found. Trends Theor. Comp. Sci., 2(3):197–303, 2006. [doi:10.1561/0400000012]

[19]   Dieter van Melkebeek and Ran Raz: A time lower bound for satisfiability. Theoret. Comput. Sci., 348(2–3):311–320, 2005. [doi:10.1016/j.tcs.2005.09.020]

[20]   Joseph Naor and Moni Naor: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput., 22(4):838–856, 1993. [doi:10.1137/0222053]

[21]   Valery A. Nepomnyashchii: Rudimentary predicates and Turing calculations. Dokl. Akad. Nauk SSSR (Russian), 195(2):282–284, 1970. MathNet.ru (Russian), English: Soviet Math. Dokl. 11(6), 1970, pp. 1462–1465.

[22]   Noam Nisan: Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449–461, 1992. [doi:10.1007/BF01305237]

[23]   Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, and William T. Trotter: On determinism versus non-determinism and related problems (preliminary version). In Proc. 24th FOCS, pp. 429–438. IEEE Comp. Soc., 1983. [doi:10.1109/SFCS.1983.39]

[24]   Rahul Santhanam: On separators, segregators and time versus space. In Proc. 16th IEEE Conf. on Comput. Complexity (CCC’01), pp. 286–294. IEEE Comp. Soc., 2001. [doi:10.1109/CCC.2001.933895]

[25]   Michael Sipser: A complexity theoretic approach to randomness. In Proc. 15th STOC, pp. 330–335. ACM Press, 1983. [doi:10.1145/800061.808762]

[26]   Emanuele Viola: The Complexity of Hardness Amplification and Derandomization. Ph. D. thesis, Harvard Univ., 2006. Author’s website.

[27]   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]

[28]   Ryan Williams: Inductive time-space lower bounds for SAT and related problems. Comput. Complexity, 15(4):433–470, 2006. [doi:10.1007/s00037-007-0221-1]

[29]   Ryan Williams: Algorithms and Resource Requirements for Fundamental Problems. Ph. D. thesis, Carnegie Mellon Univ., 2007. Author’s website.