Circuits on Cylinders

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay

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

Full Text:

PDF


DOI: http://dx.doi.org/10.7146/brics.v9i50.21765
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.
OK


ISSN: 0909-0878 

Hosted by the Royal Danish Library and Aarhus University Library