Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-025 | 14th April 2003 00:00

Constant width planar computation characterizes ACC0

RSS-Feed




TR03-025
Authors: Kristoffer Arnsfelt Hansen
Publication: 17th April 2003 15:19
Downloads: 3683
Keywords: 


Abstract:

We obtain a characterization of ACC0 in terms of a natural class of
constant width circuits, namely in terms of constant width polynomial
size planar circuits. This is shown via a characterization of the
class of acyclic digraphs which can be embedded on a cylinder surface
in such a way that all arcs flow along the same direction of the axis
of the cylinder.



ISSN 1433-8092 | Imprint