Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with arithmetic functions:
TR95-042 | 14th September 1995
Beate Bollig, Ingo Wegener

Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams

Computational complexity is concerned with the complexity of solving
problems and computing functions and not with the complexity of verifying
circuit designs.
The importance of formal circuit verification is evident.
Therefore, a framework of a complexity theory for formal circuit
verification with binary decision diagrams ... more >>>

TR98-038 | 9th July 1998
Marek Karpinski

On the Computational Power of Randomized Branching Programs

We survey some upper and lower bounds established recently on
the sizes of randomized branching programs computing explicit
boolean functions. In particular, we display boolean
functions on which randomized read-once ordered branching
programs are exponentially more powerful than deterministic
or nondeterministic read-$k$-times branching programs for ... more >>>

ISSN 1433-8092 | Imprint