Center for Algorithms and Theory of Computation

CS 269S, Spring 2018: Theory Seminar
Bren Hall, Room 1423, 1pm


Friday, June 1, 2018:

Non-Uniform ACC Circuit Lower Bounds

Karthik Gajulapalli, UCI

In this talk I will present Ryan Williams' proof that NEXP is not contained in ACC circuits. This paper was considered a breakthrough, because for long NEXP was considered a barrier class for circuit lower bound techniques.

Paper by Ryan Williams in CCC 2011