Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-048 | 3rd July 2000 00:00

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

RSS-Feed




TR00-048
Authors: Beate Bollig
Publication: 5th July 2000 12:18
Downloads: 4007
Keywords: 


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, i.e., 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.



ISSN 1433-8092 | Imprint