Topology inside NC${}^1$

Eric Allender, Samir Datta, Arsenii Karnaukhov +3

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, s…