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

Issue

No. 50 (2002): RS-50 Circuits on Cylinders

Section

Articles

License

Creative Commons License

Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.