Circuits on Cylinders

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Department of Computer Science
  • Teoretisk naturvidenskab
We consider the computational power of constant width polynomial size cylindrical circuits and nondeterministic branching programs. We show that every function computed by a Pi2 o MOD o AC0 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 ACC0.
Original languageEnglish
JournalComputational Complexity
Volume15
Issue1
Pages (from-to)62-81
Number of pages20
ISSN1016-3328
DOIs
Publication statusPublished - 2006

    Research areas

  • Circuit complexity, Branching programs

See relations at Aarhus University Citationformats

ID: 3630567