Name
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1109/CCC.2005.31 | IEEE Conference on Computational Complexity |
Keywords | DocType | Issue |
additional computational power,polylogarithmic genus,planar constant-width circuit,constant-width circuit,polynomial size,crossing number | Conference | 108 |
ISSN | ISBN | Citations |
1093-0159 | 0-7695-2364-1 | 4 |
PageRank | References | Authors |
0.45 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eric Allender | 1 | 1434 | 121.38 |
| Samir Datta | 2 | 200 | 19.82 |
| Sambuddha Roy | 3 | 219 | 19.23 |