On Circuit Lower Bounds from Derandomization

by Scott Aaronson and Dieter van Melkebeek

Theory of Computing, Volume 7(12), pp. 177-184, 2011

Bibliography with links to cited articles

[1]   László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson: BPP has subexponential time simulations unless EXPTIME has publishable proofs. Comput. Complexity, 3:307–318, 1993.

[2]   Oscar Ibarra and Shlomo Moran: Probabilistic algorithms for deciding equivalence of straight-line programs. J. ACM, 30(1):217–228, 1983. [doi:10.1145/322358.322373]

[3]   Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson: In search of an easy witness: Exponential time vs. probabilistic polynomial time. J. Comput. System Sci., 65(4):672–694, 2002. [doi:10.1016/S0022-0000(02)00024-7]

[4]   Russell Impagliazzo, Ronen Shaltiel, and Avi Wigderson: Reducing the seed length in the Nisan-Wigderson generators. Combinatorica, 26(2):647–681, 2006. [doi:10.1016/S0022-0000(02)00024-7]

[5]    Valentine Kabanets and Russell Impagliazzo: Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complexity, 13(1/2):1–46, 2004. [doi:10.1007/s00037-004-0182-6]

[6]   Ravi Kannan: Circuit-size lower bounds and nonreducibility to sparse sets. Inf. Control, 55(1–3):40–56, 1982. [doi:10.1016/S0019-9958(82)90382-5]

[7]   Jeff Kinne, Dieter van Melkebeek, and Ronen Shaltiel: Pseudorandom generators, typically-correct derandomization, and circuit lower bounds. Technical Report TR10-129, Electron. Colloq. on Comput. Complexity (ECCC), 2010. A preliminary version of this paper appeared in the proceedings of RANDOM ’09; the full version will appear in a special issue of Computational Complexity. [ECCC:TR10-129]

[8]   Peter Bro Miltersen, N. V. Vinodchandran, and Osamu Watanabe: Super-polynomial versus half-exponential circuit size in the exponential hierarchy. In Proc. 5th Ann. Intern. Conf. Computing and Combinatorics (COCOON ‘99), number 1627 in Lecture Notes in Comput. Sci., pp. 210–220. Springer, 1999. [doi:10.1007/3-540-48686-0_21]

[9]   Noam Nisan: Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63–70, 1991. [doi:10.1016/S0022-0000(02)00024-7]

[10]   Noam Nisan and Avi Wigderson: Hardness vs. randomness. J. Comput. System Sci., 49(2):149–167, 1994. [doi:10.1016/S0022-0000(05)80043-1]

[11]   Seinosuke Toda: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865–877, 1991. [doi:10.1137/0220053]

[12]    Leslie G. Valiant: The complexity of computing the permanent. Theoret. Comput. Sci., 8(2):189–201, 1979. [doi:10.1016/S0022-0000(02)00024-7]