Some Limitations of the Sum of Small-Bias Distributions

by Chin Ho Lee and Emanuele Viola

Theory of Computing, Volume 13(16), pp. 1-23, 2017

Bibliography with links to cited articles

[1]   Noga Alon, Jehoshua Bruck, Joseph Naor, Moni Naor, and Ron M. Roth: Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IRE Trans. Inform. Theory, 38(2):509–516, 1992. Preliminary version in ISIT’91. [doi:10.1109/18.119713]

[2]   Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta: Simple construction 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]   Benny Applebaum, Andrej Bogdanov, and Alon Rosen: A dichotomy for local small-bias generators. J. Cryptology, 29(3):577–596, 2016. Preliminary version in TCC’12. [doi:10.1007/s00145-015-9202-8]

[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]   Avraham Ben-Aroya and Amnon Ta-Shma: Constructing small-bias sets from algebraic-geometric codes. Theory of Computing, 9(3):253–272, 2013. Preliminary version in FOCS’09. [doi:10.4086/toc.2013.v009a005]

[6]   Stuart J. Berkowitz: On computing the determinant in small parallel time using a small number of processors. Inform. Process. Lett., 18(3):147–150, 1984. [doi:10.1016/0020-0190(84)90018-8]

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

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

[9]   Ravi B. Boppana, Johan Håstad, Chin Ho Lee, and Emanuele Viola: Bounded independence vs. moduli. In Proc. 20th Internat. Workshop on Randomization and Computation (RANDOM’16), LIPIcs, pp. 24:1–24:9. Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.APPROX-RANDOM.2016.24]

[10]   Mark Braverman: Poly-logarithmic independence fools AC0 circuits. J. ACM, 57(5):28:1–28:10, 2010. Preliminary version in CCC’09. [doi:10.1145/1754399.1754401]

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

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

[13]   Thomas M. Cover and Joy A. Thomas: Elements of Information Theory. Wiley-Interscience, 2006.

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

[15]   Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, and Boban Velickovic: Efficient approximation of product distributions. Random Structures & Algorithms, 13(1):1–16, 1998. [doi:10.1002/(SICI)1098-2418(199808)13:1¡1::AID-RSA1¿3.0.CO;2-W]

[16]   Daniel Gorenstein and Neal Zierler: A class of error-correcting codes in pm symbols. J. Soc. Indust. Appl. Math., 9(2):207–214, 1961. [doi:10.1137/0109020]

[17]   Venkatesan Guruswami and Atri Rudra: Tolerant locally testable codes. In Proc. 9th Internat. Workshop on Randomization and Computation (RANDOM’05), volume 3624 of LNCS, pp. 306–317. Springer, 2005. [doi:10.1007/11538462_26]

[18]   Russell Impagliazzo: Hard-core distributions for somewhat hard problems. In Proc. 36th FOCS, pp. 538–545. IEEE Comp. Soc. Press, 1995. [doi:10.1109/SFCS.1995.492584]

[19]   Swastik Kopparty and Shubhangi Saraf: Tolerant linearity testing and locally testable codes. In Proc. 13th Internat. Workshop on Randomization and Computation (RANDOM’09), volume 5687 of LNCS, pp. 601–614. Springer, 2009. [doi:10.1007/978-3-642-03685-9_45]

[20]   Chin Ho Lee and Emanuele Viola: Some limitations of the sum of small-bias distributions. Electron. Colloq. on Comput. Complexity (ECCC). TR15-005, 2016.

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

[22]   Raghu Meka and David Zuckerman: Small-bias spaces for group products. In Proc. 13th Internat. Workshop on Randomization and Computation (RANDOM’09), volume 5687 of LNCS, pp. 658–672. Springer, 2009. [doi:10.1007/978-3-642-03685-9_49]

[23]   Elchanan Mossel, Amir Shpilka, and Luca Trevisan: On epsilon-biased generators in NC0. Random Structures & Algorithms, 29(1), 2005. Preliminary versions in FOCS’03 and ECCC. [doi:10.1109/SFCS.2003.1238188]

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

[25]   Noam Nisan: Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63–70, 1991. Preliminary version in FOCS’88. [doi:10.1007/BF01375474]

[26]   Raymond E. A. C. Paley: On orthogonal matrices. J. Math. Phys., 12(1-4):311–320, 1933. [doi:10.1002/sapm1933121311]

[27]   William Wesley Peterson: Encoding and error-correction procedures for the Bose-Chaudhuri codes. IRE Trans. Inform. Theory, 6(4):459–470, 1960. [doi:10.1109/TIT.1960.1057586]

[28]   Alexander A. Razborov: Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Mat. Zametki Akad. Nauk SSSR, 41(4):598–607, 1987. English translation in Math. Notes of the Acad. Sci. of the USSR, 41(4):333-338, 1987. [doi:10.1007/BF01137685]

[29]   Alexander A. Razborov: A simple proof of Bazzi’s theorem. ACM Trans. Comput. Theory, 1(1):3:1–3:5, 2009. [doi:10.1145/1490270.1490273]

[30]   Atri Rudra and Steve Uurtamo: Data stream algorithms for codeword testing. In Proc. 37th Internat. Colloq. on Automata, Languages and Programming (ICALP’10), pp. 629–640. Springer, 2010. [doi:10.1007/978-3-642-14165-2_53, arXiv:1004.4601]

[31]   Ronen Shaltiel and Emanuele Viola: Hardness amplification proofs require majority. SIAM J. Comput., 39(7):3122–3154, 2010. Preliminary version in STOC’08. [doi:10.1137/080735096]

[32]   Amir Shpilka: Constructions of low-degree and error-correcting ϵ-biased generators. Comput. Complexity, 18(4):495–525, 2009. Preliminary version found in CCC’06. [doi:10.1007/s00037-009-0281-5]

[33]   Roman Smolensky: Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proc. 19th STOC, pp. 77–82. ACM Press, 1987. [doi:10.1145/28395.28404]

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

[35]   Leslie G. Valiant: Graph-theoretic arguments in low-level complexity. In 6thSymp. Math. Found. Comp. Sci. (MFCS’77), volume 53 of LNCS, pp. 162–176. Springer, 1977. [doi:10.1007/3-540-08353-7_135]

[36]   Leslie G. Valiant: Exponential lower bounds for restricted monotone circuits. In Proc. 15th STOC, pp. 110–117. ACM Press, 1983. [doi:10.1145/800061.808739]

[37]   Emanuele Viola: The Complexity of Hardness Amplification and Derandomization. Ph. D. thesis, Harvard University, 2006.

[38]   Emanuele Viola: On the power of small-depth computation. Found. Trends Theor. Comput. Sci., 5(1):1–72, 2009. [doi:10.1561/0400000033]

[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 and Avi Wigderson: Norms, XOR lemmas, and lower bounds for polynomials and protocols. Theory of Computing, 4(7):137–168, 2008. Preliminary version in CCC’07. [doi:10.4086/toc.2008.v004a007]

[41]   Richard M. Wilson: Combinatorial analysis lecture notes. 2012.