More on Bounded Independence Plus Noise: Pseudorandom Generators for Read-Once Polynomials

by Chin Ho Lee and Emanuele Viola

Theory of Computing, Volume 16(7), pp. 1-50, 2020

Bibliography with links to cited articles

[1]   Miklós Ajtai, János Komlós, and Endre Szemerédi: Deterministic simulation in LOGSPACE. In Proc. 19th STOC, pp. 132–140. ACM Press, 1987. [doi:10.1145/28395.28410]

[2]   Miklós Ajtai and Avi Wigderson: Deterministic simulation of probabilistic constant depth circuits. Advances in Computing Research, 5(1):199–222, 1989. Preliminary version in FOCS’85.

[3]   Roy Armoni, Michael Saks, Avi Wigderson, and Shiyu Zhou: Discrepancy sets and pseudorandom generators for combinatorial rectangles. In Proc. 37th FOCS, pp. 412–421. IEEE Comp. Soc. Press, 1996. [doi:10.1109/SFCS.1996.548500]

[4]   Louay M. J. Bazzi: Polylogarithmic independence can fool DNF formulas. SIAM J. Comput., 38(6):2220–2272, 2009. Preliminary version in FOCS’07. [doi:10.1137/070691954]

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

[6]   Andrej Bogdanov and Emanuele Viola: Pseudorandom bits for polynomials. SIAM J. Comput., 39(6):2464–2486, 2010. Preliminary version in FOCS’07. [doi:10.1137/070712109]

[7]   Ravi Boppana, Johan Hĺstad, Chin Ho Lee, and Emanuele Viola: Bounded independence versus symmetric tests. ACM Trans. Computation Theory, 11(4):21:1–27, 2019. Preliminary version in RANDOM’16. [doi:10.1145/3337783]

[8]   Suresh Chari, Pankaj Rohatgi, and Aravind Srinivasan: Improved algorithms via approximations of probability distributions. J. Comput. System Sci., 61(1):81–107, 2000. Preliminary version in STOC’94. [doi:10.1006/jcss.1999.1695]

[9]   Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, and Avishay Tal: Improved pseudorandomness for unordered branching programs through local monotonicity. In Proc. 50th STOC, pp. 363–375. ACM Press, 2018. [doi:10.1145/3188745.3188800]

[10]   Anindya De: Beyond the central limit theorem: asymptotic expansions and pseudorandomness for combinatorial sums. In Proc. 56th FOCS, pp. 883–902. IEEE Comp. Soc. Press, 2015. [doi:10.1109/FOCS.2015.59]

[11]   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), pp. 504–517. Springer, 2010. [doi:10.1007/978-3-642-15369-3_38]

[12]   Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, and Boban Veličković: Efficient approximation of product distributions. Random Structures Algorithms, 13(1):1–16, 1998. Preliminary version in STOC’92. [doi:10.1002/(SICI)1098-2418(199808)13:1ˇ1::AID-RSA1ż3.0.CO;2-W]

[13]   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. Press, 2018. [doi:10.1109/FOCS.2018.00093, arXiv:1808.06265]

[14]   Dmitry Gavinsky, Shachar Lovett, and Srikanth Srinivasan: Pseudorandom generators for read-once ACC0. In Proc. 27th IEEE Conf. on Computational Complexity (CCC’12), pp. 287–297. IEEE Comp. Soc. Press, 2012. [doi:10.1109/CCC.2012.37]

[15]   Parikshit Gopalan, Daniel M. Kane, and Raghu Meka: Pseudorandomness via the discrete Fourier transform. SIAM J. Comput., 47(6):2451–2487, 2018. Preliminary version in FOCS’15. [doi:10.1137/16M1062132, arXiv:1506.04350]

[16]   Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil 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]

[17]   Parikshit Gopalan, Raghu Meka, Omer Reingold, and David Zuckerman: Pseudorandom generators for combinatorial shapes. SIAM J. Comput., 42(3):1051–1076, 2013. Preliminary version in STOC’11. [doi:10.1137/110854990]

[18]   Parikshit Gopalan, Ryan O’Donnell, Yi Wu, and David Zuckerman: Fooling functions of halfspaces under product distributions. In Proc. 25th IEEE Conf. on Computational Complexity (CCC’10), pp. 223–234. IEEE Comp. Soc. Press, 2010. [doi:10.1109/CCC.2010.29, arXiv:1001.1593]

[19]   Parikshit Gopalan and Amir Yehudayoff: Inequalities and tail bounds for elementary symmetric polynomial with applications, 2014. [arXiv:1402.3543]

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

[21]   Hamed Hatami: Lecture notes on Harmonic Analysis of Boolean functions, 2014. Available at author’s home page.

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

[23]   Chin Ho Lee: Fourier bounds and pseudorandom generators for product tests. In 34th Computational Complexity Conference (CCC’19), volume 137, pp. 7:1–25. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019. [doi:10.4230/LIPIcs.CCC.2019.7]

[24]   Rudolf Lidl and Harald Niederreiter: Finite Fields. Cambridge Univ. Press, 1997. [doi:10.1017/CBO9780511525926]

[25]   Shachar Lovett: Unconditional pseudorandom generators for low-degree polynomials. Theory of Computing, 5(3):69–82, 2009. Preliminary version in STOC’08. [doi:10.4086/toc.2009.v005a003]

[26]   Chi-Jen Lu: Improved pseudorandom generators for combinatorial rectangles. Combinatorica, 22(3):417–433, 2002. Preliminary version in ICALP’98. [doi:10.1007/s004930200021]

[27]   Michael Luby, Boban Veličković, and Avi Wigderson: Deterministic approximate counting of depth-2 circuits. In 2nd Israel Symp. on Theory and Computing Systems (ISTCS’93), pp. 18–24. IEEE Comp. Soc. Press, 1993. [doi:10.1109/ISTCS.1993.253488]

[28]   Raghu Meka, Omer Reingold, and Avishay Tal: Pseudorandom generators for width-3 branching programs. In Proc. 51st STOC. ACM Press, 2019. [doi:10.1145/3313276.3316319, arXiv:1806.04256]

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

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

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

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

[33]   Michael Saks and Shiyu Zhou: BPHSPACE(S) DSPACE(S32). J. Comput. System Sci., 58(2):376–403, 1999. Preliminary version in FOCS’95. [doi:10.1006/jcss.1998.1616]

[34]   Rocco A. Servedio and Li-Yang Tan: Improved pseudorandom generators from pseudorandom multi-switching lemmas. In Proc. 23rd Internat. Workshop on Randomization and Computation (RANDOM’19), pp. 45:1–45:23. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.APPROX-RANDOM.2019.45]

[35]   J. Michael Steele: The Cauchy-Schwarz Master Class. Cambridge Univ. Press, 2004. [doi:10.1017/CBO9780511817106]

[36]   Luca Trevisan: Open problems in unconditional derandomization. Slides presented at China Theory Week (CTW’10), 2010.

[37]   Yoav Tzur: Notions of weak pseudorandomness and GF(2n)-polynomials. Master’s thesis, Weizmann Institute of Science, 2009. Link at ECCC.

[38]   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. [doi:10.1137/050640941]

[39]   Emanuele Viola: The sum of D small-bias generators fools polynomials of degree D. Comput. Complexity, 18(2):209–217, 2009. Preliminary version in CCC’08. [doi:10.1007/s00037-009-0273-5]

[40]   Emanuele Viola: Randomness buys depth for approximate counting. Comput. Complexity, 23(3):479–508, 2014. Preliminary version in FOCS’11. [doi:10.1007/s00037-013-0076-6]

[41]   Emanuele Viola: Special topics in complexity theory. Lecture notes, Northeastern Univ., 2017. ECCC.