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

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