[1]   Anil Ada, Omar Fawzi, and Hamed Hatami: Spectral norm of symmetric functions. In Proc. 16th Internat. Workshop on Randomization and Computation (RANDOM’12), volume 7408 of LNCS, pp. 338–349. Springer, 2012. [doi:10.1007/978-3-642-32512-0_29, arXiv:1205.5282]

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

[3]   Mihir Bellare and John Rompel: Randomness-efficient oblivious sampling. In Proc. 35th FOCS, pp. 276–287. IEEE Comp. Soc. Press, 1994. [doi:10.1109/SFCS.1994.365687]

[4]   Michael Ben-Or and Nathan Linial: Collective coin flipping. Advances in Comput. Research, 5:91–115, 1989. Available at author’s website. Preliminary version in FOCS’85.

[5]   Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff: Pseudorandomness for width-2 branching programs. Theory of Computing, 9(7):283–293, 2013. [doi:10.4086/toc.2013.v009a007]

[6]   Andrej Bogdanov, Periklis A. Papakonstantinou, and Andrew Wan: Pseudorandomness for read-once formulas. In Proc. 52nd FOCS, pp. 240–246. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.57]

[7]   Jean Bourgain: On the distribution of the Fourier spectrum of Boolean functions. Israel J. Mathematics, 131(1):269–276, 2002. [doi:10.1007/BF02785861]

[8]   Yigal Brandman, Alon Orlitsky, and John L. Hennessy: A spectral lower bound technique for the size of decision trees and two level AND/OR circuits. IEEE Trans. Computers, 39(2):282–287, 1990. [doi:10.1109/12.45216]

[9]   Mark Braverman, Anup Rao, Ran Raz, and Amir Yehudayoff: Pseudorandom generators for regular branching programs. SIAM J. Comput., 43(3):973–986, 2014. Preliminary version in FOCS’10. [doi:10.1137/120875673]

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

[11]   Jehoshua Bruck: Harmonic analysis of polynomial threshold functions. SIAM J. Discrete Math., 3(2):168–177, 1990. [doi:10.1137/0403015]

[12]   Jehoshua Bruck and Roman Smolensky: Polynomial threshold functions, AC⁰ functions, and spectral norms. SIAM J. Comput., 21(1):33–42, 1992. Preliminary version in FOCS’90. [doi:10.1137/0221003]

[13]   L. Elisa Celis, Omer Reingold, Gil Segev, and Udi Wieder: Balls and bins: Smaller hash families and faster evaluation. SIAM J. Comput., 42(3):1030–1050, 2013. Preliminary version in FOCS’11. [doi:10.1137/120871626]

[14]   Anindya De: Pseudorandomness for permutation and regular branching programs. In Proc. 26th IEEE Conf. on Computational Complexity (CCC’11), pp. 221–231. IEEE Comp. Soc. Press, 2011. [doi:10.1109/CCC.2011.23]

[15]   Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani: Improved pseudorandom generators for depth 2 circuits. In Proc. 14th Internat. Workshop on Randomization and Computation (RANDOM’10), volume 6302 of LNCS, pp. 504–517. Springer, 2010. [doi:10.1007/978-3-642-15369-3_38]

[16]   Lars Engebretsen, Piotr Indyk, and Ryan O’Donnell: Derandomized dimensionality reduction with applications. In Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’02), pp. 705–712. ACM/SIAM, 2002. ACM DL.

[17]   Ehud Friedgut: Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27–35, 1998. [doi:10.1007/PL00009809]

[18]   Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil P. Vadhan: Better pseudorandom generators from milder pseudorandom restrictions. In Proc. 53rd FOCS, pp. 120–129. IEEE Comp. Soc. Press, 2012. [doi:10.1109/FOCS.2012.77, arXiv:1210.0049]

[19]   Ben Green and Tom Sanders: Boolean functions with small spectral norm. Geometric and Functional Analysis, 18(1):144–162, 2008. [doi:10.1007/s00039-008-0654-y]

[20]   Vince Grolmusz: On the power of circuits with gates of low ℓ₁ norms. Theoret. Comput. Sci., 188(1-2):117–128, 1997. [doi:10.1016/S0304-3975(96)00290-3]

[21]   Iftach Haitner, Danny Harnik, and Omer Reingold: On the power of the randomized iterate. SIAM J. Comput., 40(6):1486–1528, 2011. Preliminary version in CRYPTO’06. [doi:10.1137/080721820]

[22]   Johan Håstad: Almost optimal lower bounds for small depth circuits. In Proc. 18th STOC, pp. 6–20. ACM Press, 1986. [doi:10.1145/12130.12132]

[23]   Alexander Healy, Salil Vadhan, and Emanuele Viola: Using nondeterminism to amplify hardness. SIAM J. Comput., 35(4):903–931, 2006. Preliminary version in STOC’04. [doi:10.1137/S0097539705447281]

[24]   Russell Impagliazzo, Raghu Meka, and David Zuckerman: Pseudorandomness from shrinkage. In Proc. 53rd FOCS, pp. 111–119. IEEE Comp. Soc. Press, 2012. [doi:10.1109/FOCS.2012.78]

[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]   Piotr Indyk: Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM, 53(3):307–323, 2006. Preliminary version in FOCS’00. [doi:10.1145/1147954.1147955]

[27]   Eyal Kaplan, Moni Naor, and Omer Reingold: Derandomized constructions of k-wise (almost) independent permutations. Algorithmica, 55(1):113–133, 2009. Preliminary versions in RANDOM’05 and ECCC. [doi:10.1007/s00453-008-9267-y]

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

[29]   Eyal Kushilevitz and Yishay Mansour: Learning decision trees using the Fourier spectrum. SIAM J. Comput., 22(6):1331–1348, 1993. Preliminary version in STOC’91. [doi:10.1137/0222080]

[30]   Yishay Mansour: An O(n^{log log n}) learning algorithm for DNF under the uniform distribution. J. Comput. System Sci., 50(3):543–550, 1995. Preliminary version in COLT’92. [doi:10.1006/jcss.1995.1043]

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

[32]   Jelani Nelson: Exponential tail bounds without the moment generating function. MathOverflow, 2013. http://mathoverflow.net/q/147239.

[33]   Noam Nisan: ⊆ . Comput. Complexity, 4(1):1–11, 1994. Preliminary version in STOC’92. [doi:10.1007/BF01205052]

[34]   Noam Nisan and David Zuckerman: More deterministic simulation in logspace. In Proc. 25th STOC, pp. 235–244. ACM Press, 1993. [doi:10.1145/167088.167162]

[35]   Omer Reingold: Undirected connectivity in log-space. J. ACM, 55(4):17:1–17:24, 2008. Preliminary version in STOC’05. [doi:10.1145/1391289.1391291]

[36]   Omer Reingold, Thomas Steinke, and Salil P. Vadhan: Pseudorandomness for regular branching programs via Fourier analysis. In Proc. 17th Internat. Workshop on Randomization and Computation (RANDOM’13), volume 8096 of LNCS, pp. 655–670. Springer, 2013. [doi:10.1007/978-3-642-40328-6_45, arXiv:1306.3004]

[37]   Omer Reingold, Luca Trevisan, and Salil P. Vadhan: Pseudorandom walks on regular digraphs and the vs. problem. In Proc. 38th STOC, pp. 457–466. ACM Press, 2006. [doi:10.1145/1132516.1132583]

[38]   Eyal Rozenman and Salil P. Vadhan: Derandomized squaring of graphs. In Proc. 9th Internat. Workshop on Randomization and Computation (RANDOM’05), volume 3624 of LNCS, pp. 436–447. Springer, 2005. [doi:10.1007/11538462_37]

[39]   Michael E. Saks and Shiyu Zhou: BP_HSPACE(S) ⊆ DSPACE(S^3∕2). J. Comput. System Sci., 58(2):376–403, 1999. Preliminary version in FOCS’95. [doi:10.1006/jcss.1998.1616]

[40]   Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan: Chernoff-Hoeffding bounds for applications with limited independence. SIAM J. Discrete Math., 8(2):223–250, 1995. Preliminary version in SODA’93. [doi:10.1137/S089548019223872X]

[41]   Amir Shpilka, Avishay Tal, and Ben lee Volk: On the structure of boolean functions with small spectral norm. Comput. Complexity, 26(1):229–273, 2017. Preliminary version in ITCS’14. [doi:10.1007/s00037-015-0110-y, arXiv:1304.0371]

[42]   Jiří Šíma and Stanislav Žák: A sufficient condition for sets hitting the class of read-once branching programs of width 3. In Internat. Conf. Theory and Practice of Comput. Sci. (SOFSEM’12), pp. 406–418, 2012. [doi:10.1007/978-3-642-27660-6_33]

[43]   D. Sivakumar: Algorithmic derandomization via complexity theory. In Proc. 34th STOC, pp. 619–626. ACM Press, 2002. Also in CCC’02. [doi:10.1145/509907.509996]

[44]   John P. Steinberger: The distinguishability of product distributions by read-once branching programs. In Proc. 28th IEEE Conf. on Computational Complexity (CCC’13), pp. 248–254. IEEE Comp. Soc. Press, 2013. [doi:10.1109/CCC.2013.33]

[45]   Thomas Steinke: Pseudorandomness for permutation branching programs without the group theory. Electron. Colloq. on Comput. Complexity (ECCC), 19(83), 2012. Available at ECCC.

[46]   Thomas Steinke, Salil Vadhan, and Andrew Wan: Pseudorandomness and Fourier growth bounds for width-3 branching programs. In Proc. 18th Internat. Workshop on Randomization and Computation (RANDOM’14), volume 28 of LIPIcs, pp. 885–899. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2014. Preliminary version in ECCC. [doi:10.4230/LIPIcs.APPROX-RANDOM.2014.885, arXiv:1405.7028]

[47]   Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang: Fourier sparsity, spectral norm, and the log-rank conjecture. In Proc. 54th FOCS, pp. 658–667. IEEE Comp. Soc. Press, 2013. [doi:10.1109/FOCS.2013.76, arXiv:1304.1245]

[48]   Yoav Tzur: Notions of weak pseudorandomness and GF(2ⁿ)-polynomials. Master’s thesis, Weizmann Institute, 2009. Available at ECCC.