Title: Williams' Lower Bound for Non-Uniform ACC

Speaker: David Mix Barrington, UMass Amherst

Abstract:

ACC (or ACC^0) is the class of problems that can be solved by
circuit families of constant depth, polynomial size, unbounded
fan-in, and gates for AND, OR, and MOD-m where m is a constant.
I defined this class in 1986 as an extension of AC^0, the similar
class without the modular counting gates.  Furst-Saxe-Sipser and
Ajtai had just proved lower bounds against AC^0, and ACC seemed
like the next natural target for lower bounds.  For AC^0, we can show
that very easy languages are not in the class, even the non-uniform
version of the class where the arrangement of the gates in the circuit
can be arbitrarily complicated.  Ryan Williams has just proved the
first significant lower bounds against the non-uniform version of ACC,
showing that ACC does not contain the rather large class NEXP.  I
will explain the context of this result (assuming as little background as
I can) and give some idea of the proof techniques.