Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication

 Access to full text

 Full (PDF)

1. [1] M. Ajtai, A non-linear time lower bound for Boolean branching programs, in Proc. of 40${}^{th}$ FOCS (1999) 60-70. MR1916185
2. [2] N. Alon and W. Maass, Meanders and their applications in lower bound arguments. J. Comput. System Sci. 37 (1988) 118-129. Zbl0664.68045MR979114
3. [3] P. Beame, M. Saks, X. Sun and E. Vee, Super-linear time-space tradeoff lower bounds for randomized computation, in Proc. of 41${}^{st}$ FOCS and ECCC Report TR 00-025 (2000). Zbl1326.68144MR1931815
4. [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. [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. [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. Zbl0913.68078MR1638628
7. [7] B. Bollig and I. Wegener, Read-once projections and formal circuit verification with binary decision diagrams, in Proc. of 13${}^{th}$ STACS. Springer, Lecture Notes in Comput. Sci. 1046 (1996) 491-502. MR1462120
8. [8] B. Bollig and I. Wegener, Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams. Theory Comput. Syst. 32 (1999) 487-503. Zbl0934.68048MR1693395
9. [9] B. Bollig and P. Woelfel, A read-once branching program lower bound of $\Omega \left(2^{n/4}\right)$ for integer multiplication using universal hashing, in Proc. of 33${}^{rd}$ STOC (to appear). Zbl1323.68293MR2120342
10. [10] A. Borodin, A. Razborov and R. Smolensky, On lower bounds for read-$k$-times branching programs. Comput. Complexity 3 (1993) 1-18. Zbl0777.68043MR1220075
11. [11] R.E. Bryant, Graph-based algorithms for Boolean manipulation. IEEE Trans. Comput. 35 (1986) 677-691. Zbl0593.94022
12. [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. Zbl1220.68060MR1094031
13. [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. MR1294705
14. [14] J. Gergov and C. Meinel, Efficient Boolean manipulation with OBDDs can be extended to FBDDs. IEEE Trans. Comput. 43 (1994) 1197-1209. Zbl1063.68573
15. [15] J. Hromkovič, Communication Complexity and Parallel Computing (Springer, 1997). Zbl0873.68098MR1442518
16. [16] J. Hromkovič and M. Sauerhoff, Communications with restricted nondeterminism and applications to branching program complexity, in Proc. of 17${}^{th}$ STACS. Springer, Lecture Notes in Comput. Sci. 1770 (2000) 145-156. Zbl0959.68522MR1781728
17. [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. [18] E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997). Zbl0869.68048MR1426129
19. [19] C. Meinel, Polynomial size $\Omega$-branching programs and their computational power. Inform. and Comput. 85 (1990) 163-182. Zbl0705.68052MR1044460
20. [20] S. Ponzio, A lower bound for integer multiplication with read-once branching programs. SIAM J. Comput. 28 (1998) 798-815. Zbl0918.68025MR1643441
21. [21] M. Sauerhoff, Computing with restricted nondeterminism: The dependence of the OBDD size on the number of nondeterministic variables, in Proc. 19${}^{th}$ FST TCS. Springer, Lecture Notes in Comput. Sci. 1738 (1999) 342-355. Zbl0958.68062MR1776806
22. [22] P. Savický and D. Sieling, A hierarchy result for read-once branching programs with restricted parity nondeterminism, in Proc. of 25${}^{th}$ MFCS. Springer, Lecture Notes in Comput. Sci. 1893 (2000) 650-659. Zbl0996.68513MR1844789
23. [23] D. Sieling and I. Wegener, Graph driven BDDs – a new data structure for Boolean functions. Theoret. Comput. Sci. 141 (1995) 283-310. Zbl0873.68036
24. [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. Zbl1006.68054MR1715611
25. [25] I. Wegener, Branching Programs and Binary Decision Diagrams – Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications (2000). Zbl0956.68068
26. [26] I. Wegener, The Complexity of Boolean Functions. Wiley-Teubner (1987). Zbl0623.94018MR905473
27. [27] P. Woelfel, New bounds on the OBDD-size of integer multiplication via universal hashing, in Proc. of 18${}^{th}$ STACS. Springer, Lecture Notes in Comput. Sci. 2010 (2001) 563-574. Zbl0976.68510MR1892342