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.
Added a new co-author.
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.
The proof of the main theorem had been incorrect. The new version has a very simple (and correct) proof. There are also two new authors.
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.
The proof of Theorem 6 (the main result of the paper) is incorrect, and it is not known of Theorem 6 is correct. A discussion of this point can be found "Parting Thoughts and Parting Shots", SIGACT News, March 2023.
