Pseudorandom Generators from Polarizing Random Walks

by Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett

Theory of Computing, Volume 15(10), pp. 1-26, 2019

Bibliography with links to cited articles

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

[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]   Nikhil Bansal: Constructive algorithms for discrepancy minimization. In Proc. 51st FOCS, pp. 3–10. IEEE Comp. Soc. Press, 2010. [doi:10.1109/FOCS.2010.7, arXiv:1002.2259]

[4]   Mark Braverman: Polylogarithmic independence fools AC0 circuits. J. ACM, 57(5):28, 2010. Preliminary version in CCC’09. [doi:10.1145/1754399.1754401]

[5]   Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett: Pseudorandom generators from polarizing random walks. In Proc. 33rd Computational Complexity Conf. (CCC’18), pp. 1:1–1:21. Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.CCC.2018.1]

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

[7]   Oded Goldreich: A Primer on Pseudorandom Generators. Volume 55 of Univ. Lecture Ser. Amer. Math. Soc., 2010. author’s home page.

[8]   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, arXiv:1210.0049]

[9]   Parikshit Gopalan, Rocco A Servedio, and Avi Wigderson: Degree and sensitivity: tails of two distributions. In Proc. 31st Computational Complexity Conf. (CCC’16), pp. 13:1–13:23. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.13, arXiv:1604.07432]

[10]   Pooya Hatami and Avishay Tal: Pseudorandom generators for low sensitivity functions. In Proc. 9th Innovations in Theoretical Computer Sci. Conf. (ITCS’18), pp. 29:1–29:13. Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ITCS.2018.29]

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

[12]   Nathan Linial, Yishay Mansour, and Noam Nisan: Constant depth circuits, Fourier transform, and learnability. J. ACM, 40(3):607–620, 1993. Preliminary version in FOCS’89. [doi:10.1145/174130.174138]

[13]   Shachar Lovett and Raghu Meka: Constructive discrepancy minimization by walking on the edges. SIAM J. Comput., 44(5):1573–1582, 2015. Preliminary version in FOCS’12. [doi:10.1137/130929400, arXiv:1203.5747]

[14]   Shachar Lovett, Avishay Tal, and Jiapeng Zhang: The robust sensitivity of Boolean functions. In Proc. 29th ACM-SIAM Symp. on Discrete Algorithms (SODA’18), pp. 1822–1833. SIAM, 2018. [doi:10.1137/1.9781611975031.119]

[15]   Yishay Mansour: An nO(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]

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

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

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

[19]   Ryan O’Donnell: Analysis of Boolean Functions. Cambridge Univ. Press, 2014. [doi:10.1017/CBO9781139814782]

[20]   Omer Reingold, Thomas Steinke, and Salil Vadhan: Pseudorandomness for regular branching programs via Fourier analysis. In Proc. Internat. Workshop on Approximation, Randomization, and Combinatorial Optimization (RANDOM’13), pp. 655–670. Springer, 2013. [doi:10.1007/978-3-642-40328-6_45, arXiv:1306.3004]

[21]   Hans-Ulrich Simon: A tight Ω(log log n)-bound on the time for parallel RAM’s to compute nondegenerated Boolean functions. Inf. Control, 55(1–3):102–107, 1982. See also FCT’83. [doi:10.1016/S0019-9958(82)90477-6]

[22]   Avishay Tal: Tight bounds on the Fourier spectrum of AC0. In Proc. 32nd Computational Complexity Conf. (CCC’17), pp. 15:1–15:31. Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.CCC.2017.15]

[23]   Luca Trevisan and Tongke Xue: A derandomized switching lemma and an improved derandomization of AC0. In Proc. 28th IEEE Conf. on Computational Complexity (CCC’13), pp. 242–247. IEEE Comp. Soc. Press, 2013. [doi:10.1109/CCC.2013.32]

[24]   Salil Vadhan: Pseudorandomness. Foundations and Trends in Theoret. Computer Sci., 7(1–3):1–336, Now Publ., 2012. [doi:10.1561/0400000010]

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