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]. |
This file has been generated by bibtex2html 1.74