# Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 35, Issue: 2, page 149-162
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topBollig, Beate. "Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication." RAIRO - Theoretical Informatics and Applications 35.2 (2010): 149-162. <http://eudml.org/doc/222040>.

@article{Bollig2010,

abstract = {
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.
},

author = {Bollig, Beate},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Computational complexity; read-once branching programs; nondeterminism;
integer multiplication.; branching programs; Boolean functions},

language = {eng},

month = {3},

number = {2},

pages = {149-162},

publisher = {EDP Sciences},

title = {Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication},

url = {http://eudml.org/doc/222040},

volume = {35},

year = {2010},

}

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

DA - 2010/3//

PB - EDP Sciences

VL - 35

IS - 2

SP - 149

EP - 162

AB -
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.

LA - eng

KW - Computational complexity; read-once branching programs; nondeterminism;
integer multiplication.; branching programs; Boolean functions

UR - http://eudml.org/doc/222040

ER -

## References

top- M. Ajtai, A non-linear time lower bound for Boolean branching programs, in Proc. of 40th FOCS (1999) 60-70.
- N. Alon and W. Maass, Meanders and their applications in lower bound arguments. J. Comput. System Sci.37 (1988) 118-129. Zbl0664.68045
- P. Beame, M. Saks, X. Sun and E. Vee, Super-linear time-space tradeoff lower bounds for randomized computation, in Proc. of 41st FOCS and ECCC Report TR 00-025 (2000).
- J. Bern, C. Meinel and A. Slobodová, Some heuristics for generating tree-like FBDD types. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems15 (1995) 127-130.
- 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).
- 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.68078
- B. Bollig and I. Wegener, Read-once projections and formal circuit verification with binary decision diagrams, in Proc. of 13th STACS. Springer, Lecture Notes in Comput. Sci.1046 (1996) 491-502.
- B. Bollig and I. Wegener, Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams. Theory Comput. Syst.32 (1999) 487-503. Zbl0934.68048
- 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 33rd STOC (to appear). Zbl1323.68293
- A. Borodin, A. Razborov and R. Smolensky, On lower bounds for read-k-times branching programs. Comput. Complexity3 (1993) 1-18. Zbl0777.68043
- R.E. Bryant, Graph-based algorithms for Boolean manipulation. IEEE Trans. Comput.35 (1986) 677-691. Zbl0593.94022
- 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.68060
- J. Gergov, Time-space trade-offs for integer multiplication on various types of input oblivious sequential machines. Inform. Process. Lett.51 (1994) 265-269.
- J. Gergov and C. Meinel, Efficient Boolean manipulation with OBDDs can be extended to FBDDs. IEEE Trans. Comput.43 (1994) 1197-1209. Zbl1063.68573
- J. Hromkovic, Communication Complexity and Parallel Computing (Springer, 1997). Zbl0873.68098
- J. Hromkovic and M. Sauerhoff, Communications with restricted nondeterminism and applications to branching program complexity, in Proc. of 17th STACS. Springer, Lecture Notes in Comput. Sci.1770 (2000) 145-156. Zbl0959.68522
- 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.
- E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997). Zbl0869.68048
- C. Meinel, Polynomial size $\Omega $-branching programs and their computational power. Inform. and Comput.85 (1990) 163-182. Zbl0705.68052
- S. Ponzio, A lower bound for integer multiplication with read-once branching programs. SIAM J. Comput.28 (1998) 798-815. Zbl0918.68025
- M. Sauerhoff, Computing with restricted nondeterminism: The dependence of the OBDD size on the number of nondeterministic variables, in Proc. 19th FST & TCS. Springer, Lecture Notes in Comput. Sci.1738 (1999) 342-355. Zbl0958.68062
- P. Savický and D. Sieling, A hierarchy result for read-once branching programs with restricted parity nondeterminism, in Proc. of 25th MFCS. Springer, Lecture Notes in Comput. Sci.1893 (2000) 650-659. Zbl0996.68513
- D. Sieling and I. Wegener, Graph driven BDDs - a new data structure for Boolean functions. Theoret. Comput. Sci.141 (1995) 283-310. Zbl0873.68036
- J. Thathachar, On separating the read-k-times branching program hierarchy, in Proc. of 30th Ann. ACM Symposium on Theory of Computing (STOC) (1998) 653-662. Zbl1006.68054
- I. Wegener, Branching Programs and Binary Decision Diagrams - Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications (2000). Zbl0956.68068
- I. Wegener, The Complexity of Boolean Functions. Wiley-Teubner (1987). Zbl0623.94018
- P. Woelfel, New bounds on the OBDD-size of integer multiplication via universal hashing, in Proc. of 18th STACS. Springer, Lecture Notes in Comput. Sci.2010 (2001) 563-574.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.