Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-066 | 24th October 2002 00:00

Circuits on Cylinders

RSS-Feed




TR02-066
Authors: Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V Vinay
Publication: 10th December 2002 19:08
Downloads: 3309
Keywords: 


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.



ISSN 1433-8092 | Imprint