### DIMACS Theoretical Computer Science Seminar

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.)