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