A Non-linear Time Lower Bound for Boolean Branching Programs

by Miklós Ajtai

Theory of Computing, Volume 1(8), pp. 149-176, 2005

Bibliography with links to cited articles

[1]   K. Abrahamson: Time-Space Tradeoffs for Branching Programs Contrasted With Those for Straight-Line Programs. In 27th IEEE FOCS. IEEE Computer Society, 1986.

[2]   K. Abrahamson: Time-Space Tradeoffs for Algebraic Problems on General Sequential Machines. Journal of Computer and System Sciences, 43:269–289, 1991. [JCSS:10.1016/0022-0000(91)90014-V].

[3]   M. Ajtai: A non-linear time lower bound for boolean branching programs. In 40th IEEE FOCS, pp. 60–70. IEEE Computer Society, 1999. [FOCS:10.1109/SFFCS.1999.814578].

[4]   M. Ajtai: Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions. Journal of Computer and System Sciences, 65:2–37, 2002. [JCSS:10.1006/jcss.2002.1821].

[5]   P. Beame: General Sequential Time-Space Tradeoff for Finding Unique Elements. SIAM J. Computing, 20(2):270–277, 1991. [SICOMP:20/0220017].

[6]   P. Beame, M. Saks, and T. S. Jayram: Time-space tradeoffs for branching programs. Journal of Computer and System Sciences, 63(4):542–572, 2001. [JCSS:10.1006/jcss.2001.1778].

[7]   P. Beame, M. Saks, X. Sun, and E. Vee: Time-space tradeoff lower bounds for randomized computation of decision problems. Journal of the ACM, 50(2):154–195, 2003. [JACM:10.1145/636865.636867].

[8]   A. Borodin and S. A. Cook: A time-space tradeoff for sorting on a general sequential model of computation. SIAM J. Computing, 11:287–297, 1982. [SICOMP:11/0211022].

[9]   A. Borodin, A. A. Razborov, and R. Smolensky: On lower bounds for read-k-times branching programs. Computational Complexity, 3:1–18, 1993.

[10]   B. Chor and O. Goldreich: Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity. In 26th IEEE FOCS, pp. 429–442. IEEE Computer Society, 1985.

[11]   M. Karchmer: Two Time-Space Tradeoffs for Element Distinctness. Theoretical Computer Science, 47:237–246, 1986. [TCS:10.1016/0304-3975(86)90150-7].

[12]   S. Reisch and G. Schnitger: Three applications of Kolmogorov-complexity. In 23rd IEEE FOCS, pp. 45–52. IEEE Computer Society, 1982.

[13]   J. S. Thathachar: On separating the read-k-times branching program hierarchy. In 30th ACM STOC, pp. 653–662. ACM, 1998. [STOC:10.1145/276698.276881].

[14]   Y. Yesha: Time-Space Tradeoffs for Matrix Multiplication and the Discrete Fourier Transform of Any General Sequential Random-Access Computer. Journal of Computer and System Sciences, 29:183–197, 1984. [JCSS:10.1016/0022-0000(84)90029-1].