EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 22 / No 4 (1988) RAIRO-Theor. Inf. Appl., 22 4 (1988) 447-459 References
Free Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 22, Number 4, 1988
Page(s) 447 - 459
DOI https://doi.org/10.1051/ita/1988220404471
Published online 01 February 2017
  1. 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. [Google Scholar]
  2. 2. A. BORODIN, D. DOLEV, F. E. FICH and W. PAUL, Bounds for width two branching programs, 15th ACM STOC, 1983, pp. 87-93. [Zbl: 0589.68034] [Google Scholar]
  3. 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] [Google Scholar]
  4. 4. A. K. CHANDRA, M. L. FURST and R. J. LIPTON, Multiparty protocols, 15th ACM STOC, 1983, pp.94-99. [Google Scholar]
  5. 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] [Google Scholar]
  6. 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] [Google Scholar]
  7. 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] [Google Scholar]
  8. 8. P. PUDLAK, A lower bound on the complexity of branching programs, Preprint, Univ. Prague, 1983. [Zbl: 0572.68033] [MR: 783479] [Google Scholar]
  9. 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] [Google Scholar]
  10. 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. [Google Scholar]
  11. 11. A. C. YAO, Lower bounds by probabilistic arguments, 24th IEEE FOCS, 1983, pp. 420-428. [Google Scholar]
  12. 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] [Google Scholar]
  13. 13. S. ZAK, An exponential lower bound for real-time branching programs, manuscript. [Zbl: 0627.68044] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.