Circuits on Cylinders

Kristoffer Arnsfelt Hansen; Peter Bro Miltersen; V Vinay

doi:10.1007/s00037-006-0207-4

Circuits on Cylinders

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V Vinay

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Tidsskriftartikel › Forskning › peer review

4 Citationer (Scopus)

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₂ o MOD o AC⁰ 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⁰.

Originalsprog	Engelsk
Tidsskrift	Computational Complexity
Vol/bind	15
Nummer	1
Sider (fra-til)	62-81
Antal sider	20
ISSN	1016-3328
DOI	https://doi.org/10.1007/s00037-006-0207-4
Status	Udgivet - 2006

Adgang til dokumentet

10.1007/s00037-006-0207-4

Citationsformater

@article{d189fda0255d11dcbee902004c4f4f50,

title = "Circuits on Cylinders",

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

keywords = "Circuit complexity, Branching programs",

author = "Hansen, {Kristoffer Arnsfelt} and Miltersen, {Peter Bro} and V Vinay",

year = "2006",

doi = "10.1007/s00037-006-0207-4",

language = "English",

volume = "15",

pages = "62--81",

journal = "Computational Complexity",

issn = "1016-3328",

publisher = "Springer Basel AG",

number = "1",

}

TY - JOUR

T1 - Circuits on Cylinders

AU - Hansen, Kristoffer Arnsfelt

AU - Miltersen, Peter Bro

AU - Vinay, V

PY - 2006

Y1 - 2006

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

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

KW - Circuit complexity

KW - Branching programs

U2 - 10.1007/s00037-006-0207-4

DO - 10.1007/s00037-006-0207-4

M3 - Journal article

SN - 1016-3328

VL - 15

SP - 62

EP - 81

JO - Computational Complexity

JF - Computational Complexity

IS - 1

ER -

Circuits on Cylinders

Abstract

Adgang til dokumentet

Fingeraftryk

Citationsformater