December 5, 2017 Theory Seminar 4:00 pm, CS 140

Nonuniform ACC Circuit Lower Bounds

William Toohey

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.