Lower bounds on the complexity of real-time branching programs
Kriegel, Klaus ; Waack, Stephan
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 22 (1988), p. 447-459 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1988__22_4_447_0,
     author = {Kriegel, Klaus and Waack, Stephan},
     title = {Lower bounds on the complexity of real-time branching programs},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {22},
     year = {1988},
     pages = {447-459},
     mrnumber = {984586},
     zbl = {0664.68046},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1988__22_4_447_0}
}

Kriegel, Klaus; Waack, Stephan. Lower bounds on the complexity of real-time branching programs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 22 (1988) pp. 447-459. http://gdmltest.u-ga.fr/item/ITA_1988__22_4_447_0/

1. M. Ajtai, L. Babai, P. Hajnal, J. Komlos, P. Pudlak, V. Rödel, E. Szemeredi and G. Turan, Two lower bounds for branching programs, 18th ACM STOC, 1986, pp. 30-39.

2. A. Borodin, D. Dolev, F. E. Fich and W. Paul, Bounds for width two branching programs, 15th ACM STOC, 1983, pp. 87-93.

3. L. Budach, Lower bounds for the number of nodes in a decision tree, EIK 21, 1985, No 4/5, pp.221-228. | MR 824578

4. A. K. Chandra, M. L. Furst and R. J. Lipton, Multiparty protocols, 15th ACM STOC, 1983, pp.94-99.

5. P. E. Dunne, Lower bounds on the complexity of 1-time-only branching programs, FCT Proc., Lect. Notes in Comp. Sci.,Vol. 199, 1985, pp. 90-99. | MR 821228 | Zbl 0575.68064

6. R. J. Lipton and Y. Zalcstein, Word problems solvable in logspace, Journal of the ACM, Vol. 24, No.3, 1977, pp. 522-526. | MR 445901 | Zbl 0359.68049

7. E. I. Nechiporuk, On a Boolean function, Dokl. Akad. Nauk USSR, Vol. 169, No. 4, 1966, pp.765-766. | MR 218148 | Zbl 0161.00901

8. P. Pudlak, A lower bound on the complexity of branching programs, Preprint, Univ. Prague, 1983. | MR 783479

9. U. Vishkin and A. Wigderson, Trode-offs between depth and width in parallel computation, SIAM J. Comput, Vol. 14, No.2, 1985, pp. 303-314. | MR 784739 | Zbl 0573.68015

10. I. Wegener, On the complexity of branching programs and decision trees for clique fonctions, Univ. of Frankfurt, Fachbereich Informatik, Interner Bericht, 5/84, 1984.

11. A. C. Yao, Lower bounds by probabilistic arguments, 24th IEEE FOCS, 1983, pp. 420-428.

12. S. Zak, An exponential lower bound for one-time-only branching programs, MFCS Proc., Lect. Notes in Comp. Sci., Vol. 176, 1984, pp. 562-566. | MR 783488 | Zbl 0558.68044

13. S. Zak, An exponential lower bound for real-time branching programs, manuscript.