Concentration for Limited Independence via Inequalities for the Elementary Symmetric Polynomials

by Parikshit Gopalan and Amir Yehudayoff

Theory of Computing, Volume 16(17), pp. 1-29, 2020

Bibliography with links to cited articles

[1]   Miklós Ajtai and Avi Wigderson: Deterministic simulation of probabilistic constant depth circuits. In Silvio Micali and Franco Preparata, editors, Randomness and Computation, volume 5 of Adv. in Computing Research, pp. 199–222. JAI Press, 1989. Available on author’s homepage. Preliminary version in FOCS’85.

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

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

[4]   Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher: Min-wise independent permutations. J. Comput. System Sci., 60(3):630–659, 2000. Preliminary version in STOC’98. [doi:10.1006/jcss.1999.1690]

[5]   Andrei Z. Broder, Moses Charikar, and Michael Mitzenmacher: A derandomization using min-wise independent permutations. J. Discr. Algorithms, 1(1):11–20, 2003. Preliminary version in RANDOM’98. [doi:10.1016/S1570-8667(03)00003-0]

[6]   Dean Doron, Pooya Hatami, and William M. Hoza: Log-seed pseudorandom generators via iterated restrictions. In Proc. 35th Comput. Complexity Conf. (CCC’20), pp. 1–36. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.CCC.2020.6]

[7]   Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, and Boban Veličković: Efficient approximation of product distributions. Random Struct. Algor., 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]

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

[9]   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., 2012. [doi:10.1109/FOCS.2012.77, arXiv:1210.0049]

[10]   Parikshit Gopalan and Amir Yehudayoff: Inequalities and tail bounds for elementary symmetric polynomials. Electron. Colloq. Comput. Complexity, TR14-019, 2014. [ECCC]

[11]   Piotr Indyk: A small approximately min-wise independent family of hash functions. J. Algorithms, 38(1):84–90, 2001. Preliminary version in SODA’99. [doi:10.1006/jagm.2000.1131]

[12]   Nathan Linial, Michael Luby, Michael E. Saks, and David Zuckerman: Efficient construction of a small hitting set for combinatorial rectangles in high dimension. Combinatorica, 17(2):215–234, 1997. Preliminary version in STOC’93. [doi:10.1007/BF01200907]

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

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

[15]   Ketan Mulmuley: Randomized geometric algorithms and pseudorandom generators. Algorithmica, 16(4/5):450–463, 1996. Preliminary version in FOCS’92. [doi:10.1007/BF01940875]

[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 generators for space-bounded computation. Combinatorica, 12(4):449–461, 1992. Preliminary version in STOC’90. [doi:10.1007/BF01305237]

[18]   George Pólya and George Szeg˝o  : Problems and Theorems in Anaysis II. Springer, 1976.

[19]    Michael E. Saks, Aravind Srinivasan, Shiyu Zhou, and David Zuckerman: Low discrepancy sets yield approximate min-wise independent permutation families. Information Processing Letters, 73(1–2):29–32, 2000. Preliminary version in RANDOM’99. [doi:10.1016/S0020-0190(99)00163-5]

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