
Nonuniform ACC Circuit Lower Bounds
William Toohey
UMass
Abstract: Circuit complexity lower bounds are rare. It is still open whether NEXPTIME has polynomialsize circuits, as well as whether NP has linearsize circuits. In this talk I will explain Ryan Williams' proof that NEXPTIME has no ACC circuits. (ACC is the set of polysize, constantdepth circuits with AND, OR, NOT, and MOD m gates.) This is from his paper of the above title which appeared in JACM 2014.