Circuits on Cylinders
Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, Vishwa Vinay · BRICS Report Series · 2002
We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching programs. We show that every function computed by a Pi_2 o MOD o AC^0 circuit can also be computed by a constant width polynomial size cylindrical nondeterministic branching program (or cylindrical circuit) and that every function computed by a constant width polynomial size cylindrical circuit belongs to ACC^0.