Title: Topology and Small Circuit Complexity Classes
Speaker: Eric Allender, Rutgers University
Date: October 18, 2004 3:30-4:30pm
Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
NC^1 is a well-studied circut complexity class, consisting of all functions that can be computed by bounded-fan-in circuits of logarithmic depth. (Equivalently, it consists of all functions expressible with polynomial-size Boolean formulae.) One of the nicest results about NC^1 is Barrington's Theorem, which (among other things) gives another equivalent characterization of NC^1, as the class of functions computed by polynomial-size circuits of constant width.
The proof of Barrington's theorem makes surprising use of algebraic techniques, and shows that any regular set whose syntactic monoid contains a nonsolvable group is complete for NC^1. When attention is restricted to solvable monoids, the complexity class that results is ACC^0. In terms of circuits, ACC^0 is the class of functions computable on circuits of constant depth and polynomial size, using unbounded-fan-in AND, OR, and MOD(m) gates (for any fixed modulus m). ACC^0 has been the object of much study, because there are lower bound techniques that work quite well for subclasses of ACC^0, but no such techniques have been developed yet for ACC^0. It remains an open question if there is any problem computable in nondeterministic exponential time that is not in ACC^0.
Hansen recently provided a characterization of ACC^0 as precisely the class of problems computable by constant-width PLANAR circuits of polynomial size (with AND and OR gates, with negation available at the inputs.) The connection between ACC^0 and planarity seems quite surprising.
In this talk, I will investigate the question of what happens when slightly more general circuits are considered, where we allow the circuits to be embedded on a surface of small genus. We show that constant-width circuits of polylogarithmic genus still yield exactly ACC^0.
(This is joint work with Samir Datta and Sambuddha Roy.)