Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits (Q1121671)

The first \(\Omega (n^ c)\), for \(c\leq 1\), lower bounds on the area complexity of multilective VLSI circuits computing a specific problem are obtained. Lower bounds of this kind are achieved not only for constant multiplicity of reading but also for multilectivity bounded by \(O(\log^ bn)\), \(b<1/2\). To establish mentioned lower bounds a new simulation of (nondeterministic) multilective VLSI circuits of area A by oblivious (disjunctive) branching programs of width exp(O(A)) which have the same multiplicity of reading as the VLSI circuit is derived. This enables to apply the exponential lower bounds on the width of linear-depth oblivious branching programs obtained by Krause, Meinel and Waack for multilective VLSI circuits.