Circuits on Cylinders

Kristoffer Arnsfelt Hansen
Peter Bro Miltersen
V. Vinay

December 2002

Abstract:

We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching programs. We show that every function computed by a ${{\bf\Pi}_2 \circ {\rm\bf MOD} \circ {\rm\bf 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 ${\mbox{\rm\bf ACC}}^0$

Available as PostScript, PDF.

Last modified: 2003-06-08 by webmaster.