Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with parity nondeterminism:
TR01-017 | 14th February 2001
Petr Savicky, Detlef Sieling

A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism

Restricted branching programs are considered in complexity theory in
order to study the space complexity of sequential computations and
in applications as a data structure for Boolean functions. In this
paper (\oplus,k)-branching programs and (\vee,k)-branching
programs are considered, i.e., branching programs starting with a
... more >>>

TR01-073 | 24th October 2001
Beate Bollig, Philipp Woelfel, Stephan Waack

Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

Revisions: 1

Branching programs are a well-established computation model
for Boolean functions, especially read-once branching programs
have been studied intensively. Exponential lower bounds for
deterministic and nondeterministic read-once branching programs
are known for a long time. On the other hand, the problem of
proving superpolynomial lower bounds ... more >>>

ISSN 1433-8092 | Imprint