Circuits on Cylinders

Authors

  • Kristoffer Arnsfelt Hansen
  • Peter Bro Miltersen
  • V. Vinay

DOI:

https://doi.org/10.7146/brics.v9i50.21765

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.

Downloads

Published

2002-12-05

How to Cite

Hansen, K. A., Miltersen, P. B., & Vinay, V. (2002). Circuits on Cylinders. BRICS Report Series, 9(50). https://doi.org/10.7146/brics.v9i50.21765