ECCC-Report TR03-025https://eccc.weizmann.ac.il/report/2003/025Comments and Revisions published for TR03-025en-usThu, 17 Apr 2003 15:19:31 +0300
Paper TR03-025
| Constant width planar computation characterizes ACC0 |
Kristoffer Arnsfelt Hansen
https://eccc.weizmann.ac.il/report/2003/025We 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.
Thu, 17 Apr 2003 15:19:31 +0300https://eccc.weizmann.ac.il/report/2003/025