ACC^0 Versus CC^0
David Mix Barrington, UMass Amherst
Tuesday 29 September 2009, 4:00 p.m.
Room 140, Computer Science Building
The complexity class AC^0 is the set of problems solvable by circuit families of constant depth, unbounded fan-in, and polynomial size with AND and OR gates. If we add gates for counting modulo a constant, we get the class ACC^0, and if we then remove the AND and OR gates we get the class CC^0. These classes can also be defined in terms of "M-programs", which test membership in a language by carrying out a single iterated multiplication in a finite group or monoid.
ACC^0 circuits correspond to programs over solvable monoids, exactly those monoids for which you cannot simulate all of the class NC^1 using the proof technique of Barrington's Theorem. It's thus natural to conjecture that they are weaker than NC^1 circuits, though this has not been proved. Similarly, since no one knows how to simulate an AND gate in CC^0, it is natural to conjecture that this is impossible (Barrington, Straubing, Therien 1988).
After setting out this background, I will present some of the results of Hanson and Koucky from CCC 2009 that suggest that CC^0 and ACC^0 might actually be the same. In particular, ACC^0 can be simulated by probabilistic circuits over CC^0, or by small ANDs of ORs of CC^0 circuits.
Last modified 22 September 2009