Circuits on cylinders


Autoria(s): Hansen, Kristoffer Arnsfelt; Miltersen, Peter Bro; Vinay, V
Contribuinte(s)

Lingas, A

Nilsson, BJ

Data(s)

2003

Resumo

We consider the computational power of constant width polynomial size cylindrical circuits and non deterministic 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).

Formato

application/pdf

Identificador

http://eprints.iisc.ernet.in/39775/1/Circuits_on.pdf

Hansen, Kristoffer Arnsfelt and Miltersen, Peter Bro and Vinay, V (2003) Circuits on cylinders. In: Lecture Notes in Computer Science, 2751 . pp. 171-182.

Publicador

Springer

Relação

http://www.springerlink.com/content/dwxm3wltjjjjmq1t/

http://eprints.iisc.ernet.in/39775/

Palavras-Chave #Computer Science & Automation (Formerly, School of Automation)
Tipo

Editorials/Short Communications

PeerReviewed