Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 2, pp. 149-162.

Branching programs are a well established computation model for Boolean functions, especially read-once branching programs have been studied intensively. In this paper the expressive power of nondeterministic read-once branching programs, more precisely the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once branching programs are defined and a lower bound method is presented. Furthermore, the first exponential lower bound for integer multiplication on the size of a nondeterministic nonoblivious read-once branching program model is proven.

Classification : 68Q05, 68Q10, 68Q15, 94C10
Mots clés : computational complexity, read-once branching programs, nondeterminism, integer multiplication
@article{ITA_2001__35_2_149_0,
     author = {Bollig, Beate},
     title = {Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {149--162},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {2},
     year = {2001},
     mrnumber = {1862460},
     zbl = {0992.68057},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_2001__35_2_149_0/}
}
TY  - JOUR
AU  - Bollig, Beate
TI  - Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2001
SP  - 149
EP  - 162
VL  - 35
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_2001__35_2_149_0/
LA  - en
ID  - ITA_2001__35_2_149_0
ER  - 
%0 Journal Article
%A Bollig, Beate
%T Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 149-162
%V 35
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_2001__35_2_149_0/
%G en
%F ITA_2001__35_2_149_0
Bollig, Beate. Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 2, pp. 149-162. http://archive.numdam.org/item/ITA_2001__35_2_149_0/

[1] M. Ajtai, A non-linear time lower bound for Boolean branching programs1999) 60-70. | MR

[2] N. Alon and W. Maass, Meanders and their applications in lower bound arguments. J. Comput. System Sci. 37 (1988) 118-129. | MR | Zbl

[3] P. Beame, M. Saks, X. Sun and E. Vee, Super-linear time-space tradeoff lower bounds for randomized computation 00-025 (2000). | MR

[4] J. Bern, C. Meinel and A. Slobodová, Some heuristics for generating tree-like FBDD types. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems 15 (1995) 127-130.

[5] B. Bollig, M. Sauerhoff, D. Sieling and I. Wegener, Read-k times ordered binary decision diagrams. Efficient algorithms in the presence of null chains. Tech. Report 474. Univ. Dortmund (1993).

[6] B. Bollig, M. Sauerhoff, D. Sieling and I. Wegener, Hierarchy theorems for k-OBDDs and k-IBDDs. Theoret. Comput. Sci. 205 (1998) 45-60. | MR | Zbl

[7] B. Bollig and I. Wegener, Read-once projections and formal circuit verification with binary decision diagrams 1046 (1996) 491-502. | MR

[8] B. Bollig and I. Wegener, Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams. Theory Comput. Syst. 32 (1999) 487-503. | MR | Zbl

[9] B. Bollig and P. Woelfel, A read-once branching program lower bound of Ω(2 n/4 ) for integer multiplication using universal hashing, in Proc. of 33 rd STOC (to appear). | MR

[10] A. Borodin, A. Razborov and R. Smolensky, On lower bounds for read-k-times branching programs. Comput. Complexity 3 (1993) 1-18. | MR | Zbl

[11] R.E. Bryant, Graph-based algorithms for Boolean manipulation. IEEE Trans. Comput. 35 (1986) 677-691. | Zbl

[12] R.E. Bryant, On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication. IEEE Trans. Comput. 40 (1991) 205-213. | MR | Zbl

[13] J. Gergov, Time-space trade-offs for integer multiplication on various types of input oblivious sequential machines. Inform. Process. Lett. 51 (1994) 265-269. | MR

[14] J. Gergov and C. Meinel, Efficient Boolean manipulation with OBDDs can be extended to FBDDs. IEEE Trans. Comput. 43 (1994) 1197-1209. | Zbl

[15] J. Hromkovič, Communication Complexity and Parallel Computing (Springer, 1997). | MR | Zbl

[16] J. Hromkovič and M. Sauerhoff, Communications with restricted nondeterminism and applications to branching program complexity 1770 (2000) 145-156. | MR | Zbl

[17] J. Jain, J. Bitner, D.S. Fussell and J.A. Abraham, Functional partitioning for verification and related problems. Brown/MIT VLSI Conference (1992) 210-226.

[18] E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997). | MR | Zbl

[19] C. Meinel, Polynomial size Ω-branching programs and their computational power. Inform. and Comput. 85 (1990) 163-182. | MR | Zbl

[20] S. Ponzio, A lower bound for integer multiplication with read-once branching programs. SIAM J. Comput. 28 (1998) 798-815. | MR | Zbl

[21] M. Sauerhoff, Computing with restricted nondeterminism: The dependence of the OBDD size on the number of nondeterministic variables 1738 (1999) 342-355. | MR | Zbl

[22] P. Savický and D. Sieling, A hierarchy result for read-once branching programs with restricted parity nondeterminism 1893 (2000) 650-659. | MR | Zbl

[23] D. Sieling and I. Wegener, Graph driven BDDs - a new data structure for Boolean functions. Theoret. Comput. Sci. 141 (1995) 283-310. | Zbl

[24] J. Thathachar, On separating the read-k-times branching program hierarchy, in Proc. of 30 th Ann. ACM Symposium on Theory of Computing (STOC) (1998) 653-662. | MR | Zbl

[25] I. Wegener, Branching Programs and Binary Decision Diagrams - Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications (2000). | Zbl

[26] I. Wegener, The Complexity of Boolean Functions. Wiley-Teubner (1987). | MR | Zbl

[27] P. Woelfel, New bounds on the OBDD-size of integer multiplication via universal hashing 2010 (2001) 563-574. | MR | Zbl