Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-108 | 24th November 2004 00:00

Topology inside NC^1

RSS-Feed




TR04-108
Authors: Eric Allender, Samir Datta, Sambuddha Roy
Publication: 26th November 2004 17:40
Downloads: 1104
Keywords: 


Abstract:

We show that ACC^0 is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC^0. Thus polylogarithmic genus provides no additional computational power in this model.
We consider other generalizations of planarity, including crossing number and thickness. We show that thickness two already suffices to capture all of NC^1.



ISSN 1433-8092 | Imprint