Circuits on Cylinders | Zendy

Kristoffer Arnsfelt Hansen | Zendy; Peter Bro Miltersen | Zendy; Vishwa Vinay | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Circuits on Cylinders

Author(s) -

Kristoffer Arnsfelt Hansen,

Peter Bro Miltersen,

Vishwa Vinay

Publication year - 2002

Publication title -

brics report series

Language(s) - English

Resource type - Journals

eISSN - 1601-5355

pISSN - 0909-0878

DOI - 10.7146/brics.v9i50.21765

Subject(s) - nondeterministic algorithm , constant (computer programming) , mathematics , polynomial , branching (polymer chemistry) , function (biology) , electronic circuit , discrete mathematics , combinatorics , mathematical analysis , physics , computer science , materials science , quantum mechanics , evolutionary biology , composite material , biology , programming language

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research