Pseudorandomness for Width-2 Branching Programs

by Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff

Theory of Computing, Volume 9(7), pp. 283-293, 2013

Bibliography with links to cited articles

[1]   David A. Mix Barrington: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. System Sci., 38(1):150–164, 1989. Preliminary version in STOC’86. [doi:10.1016/0022-0000(89)90037-8]

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

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

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

[5]   Allan Borodin, Joachim von zur Gathen, and John E. Hopcroft: Fast parallel matrix and GCD computations. Inf. Control, 52(3):241–256, 1982. Preliminary version in FOCS’82. [doi:10.1016/S0019-9958(82)90766-5]

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

[7]   Laszlo Csanky: Fast parallel matrix inversion algorithms. SIAM J. Comput., 5(4):618–623, 1976. Preliminary version in FOCS’75. [doi:10.1137/0205040]

[8]   Nathan Linial and Noam Nisan: Approximate inclusion-exclusion. Combinatorica, 10(4):349–365, 1990. Preliminary version in STOC’90. [doi:10.1007/BF02128670]

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

[10]   Ketan Mulmuley: A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica, 7(1):101–104, 1987. Preliminary version in STOC’86. [doi:10.1007/BF02579205]

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

[12]   Alexander A. Razborov: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Matematicheskie Zametki, 41:598–607, 1987. English translation: Math. Notes of the Acad. Sci. USSR, Vol. 41 (4), 1987, pp. 333-338.

[13]   Alexander A. Razborov: A simple proof of Bazzi’s theorem. ACM Transactions on Computation Theory, 1(1):3, 2009. ECCC. [doi:10.1145/1490270.1490273]

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

[15]   Luca Trevisan: A note on approximate counting for k-DNF. In Proc. 8th Internat. Workshop on Randomization and Computation (RANDOM’04), pp. 417–425. Springer, 2004. [doi:10.1007/978-3-540-27821-4_37]

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

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