The Complexity of Classical and Quantum Branching Programs: A Communication Complexity Approach

  • Farid Ablayev
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3777)


We present a survey of the communication point of view for a complexity lower bounds proof technique for classical (deterministic, nondeterministic and randomized) and quantum models of branching programs.


Branching programs communication computations quantum computations 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Ablayev, F.: Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theoretical Computer Science 157, 139–159 (1996)zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    Ablayev, F.: Randomization and nondeterminism are incomparable for ordered-read once branching programs. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol. 1256, pp. 195–202. Springer, Heidelberg (1997)Google Scholar
  3. 3.
    Ablayev, F., Karpinski, M.: On the power of randomized branching programs. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol. 1099, pp. 348–356. Springer, Heidelberg (1996)Google Scholar
  4. 4.
    Ablayev, F., Karpinski, M.: On the Power of Randomized Ordered Branching Programs. Electronic Colloquium on Computational Complexity, TR98-004 (1998), available at
  5. 5.
    Ablayev, F., Karpinski, M.: A lower bound for integer multiplication on randomized ordered read-once branching programs. Information and Computation 186(1), 78–89 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    Ablayev, F., Gainutdinova, A., Karpinski, M.: On the computational power of quantum branching programs. In: Freivalds, R. (ed.) FCT 2001. LNCS, vol. 2138, pp. 59–70. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  7. 7.
    Agrawal, M., Thierauf, T.: The Satisfiability Problem for Probabilistic Ordered Branching Programs. Electronic Colloquium on Computational Complexity, TR97-060 (1997), available at
  8. 8.
    Boppana, R., Sipser, M.: The complexity of finite functions. In: Van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science. Algorithms and Complexity, vol. A, pp. 757–804. MIT Press, Elsevier, The Netherlands (1990)Google Scholar
  9. 9.
    Bryant, R.: On the complexity of VLSI implementations and graph representations of boolean functions with applications to integer multiplication. IEEE Trans. Comput. 40(2), 205–213 (1991)CrossRefMathSciNetGoogle Scholar
  10. 10.
    Bryant, R.: Symbolic boolean manipulation with ordered binary decision diagrams. ACM Computing Surveys 24(3), 293–318 (1992)CrossRefGoogle Scholar
  11. 11.
    Borodin, A., Razborov, A., Smolensky, R.: On lower bounds for read-k-times branching programs. Computational Complexity 3, 1–18 (1993)zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    Bolling, B., Sauerhoff, M., Sieling, D., Wegener, I.: On the power of different types of restricted branching programs. ECCC Reports 1994, TR94-025 (1994), Available at
  13. 13.
    Jukna, S.: Complexity of Boolean Functions, see. Electronic Colloquium on Computational Complexity, section Lecture Notes, available at
  14. 14.
    Hromkovic, J.: Communication complexity and parallel computations. Springer, Heidelberg (1997)Google Scholar
  15. 15.
    Karchmer, M., Raz, R., Wigderson, A.: Super-logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity. Computational Complexity 5, 191–204 (1995)zbMATHCrossRefMathSciNetGoogle Scholar
  16. 16.
    Klauck, H.: On quantum and probabilistic communication: La Vegas and one-way protocols. In: Proc. of the 32nd ACM Symp. Theory of Computing (2000)Google Scholar
  17. 17.
    Kremer, I., Nisan, N., Ron, D.: On randomized one-round communication complexity. In: Proceedings of the 27th annual ACM symposium on Theory of computing, pp. 596–605 (1995)Google Scholar
  18. 18.
    Krause, M., Meinel, C., Waack, S.: Separating the eraser Turing machine classes L e, NL e, co − NL e, and P e. In: Koubek, V., Janiga, L., Chytil, M.P. (eds.) MFCS 1988. LNCS, vol. 324, pp. 405–413. Springer, Heidelberg (1988)CrossRefGoogle Scholar
  19. 19.
    Kushilevitz, E., Nisan, N.: Communication comple xity. Cambridge University Press, Cambridge (1997)Google Scholar
  20. 20.
    Meinel, C., Theobald, T.: Ordered Binary Decision Diagrams and Their Significance in Computer-Aided Design of VLSI Circuits - a Survey, Electronic Colloquium on Computational Complexity, TR98-039, available at
  21. 21.
    Nakanishi, M., Hamaguchi, K., Kashiwabara, T.: Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction. In: Du, D.-Z., Eades, P., Sharma, A.K., Lin, X., Estivill-Castro, V. (eds.) COCOON 2000. LNCS, vol. 1858, pp. 467–476. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  22. 22.
    Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)zbMATHGoogle Scholar
  23. 23.
    Oklonishnikova, E.: On one lower bound for branching programs. Electronic Colloquium on Computational Complexity, TR02-020, available at
  24. 24.
    Ponzio, S.: A lower bound for integer multiplication with read-once branching programs. In: Proceedings of the 27-th STOC, pp. 130–139 (1995)Google Scholar
  25. 25.
    Ponzio, S.: Restricted Branching Programs and Hardware Verification, PhD Theses, Massachusetts Institute of Technology (1995), Available at
  26. 26.
    Razborov, A.: Lower bounds for deterministic and nondeterministic branching programs. In: Budach, L. (ed.) FCT 1991. LNCS, vol. 529, pp. 47–60. Springer, Heidelberg (1991)Google Scholar
  27. 27.
    Raz, R., McKenzie, P.: Separation of the monotone NC hierarchy. In: Proc. of the 38th Annual Symposium on Foundation of Computer Science, pp. 234–243 (1997)Google Scholar
  28. 28.
    Sauerhoff, M.: A lower bounds for randomized read-k-times branching programs Electronic Colloquium on Computational Complexity, TR97-019 (1997), available at
  29. 29.
    Savicky, P., Zak, S.: A large lower bound for 1-branching programs, Electronic Colloquium on Computational Complexity, Revision 01 of TR96-036 (1996), available at
  30. 30.
    Savicky, P., Zak, S.: A hierarchy for (1, + k)-branching programs with respect to k, Electronic Colloquium on Computational Complexity, TR96-050 (1996), available at
  31. 31.
    Simon, J., Szegedy, M.: A new lower bound theorem for read-only-once branching programs and its applications. In: Cai, J.-Y. (ed.) Advances in Computational Complexity Theory. DIMACS Series, vol. 13, pp. 183–193. AMS (1993)Google Scholar
  32. 32.
    Sauerhoff, M., Sieling, D.: Quantum branching programs and space-bounded nonuniform quantum complexity. ph/0403164 (March 2004)Google Scholar
  33. 33.
    Wegener, I.: Efficient data structures for boolean functions. Discrete Mathematics 136, 347–372 (1994)zbMATHCrossRefMathSciNetGoogle Scholar
  34. 34.
    Wegener, I.: Branching Programs and Binary Decision Diagrams. SIAM Monographs on Discrete Mathematics and Applications (2000)Google Scholar
  35. 35.
    Yao, A.: Some Complexity Questions Related to Distributive Computing. In: Proceedings of the 11th Annual ACM Symposium on the Theory of Computing, pp. 209–213 (1979)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Farid Ablayev
    • 1
  1. 1.Dept. of Theoretical CyberneticsKazan State UniversityKazanRussia

Personalised recommendations