Ryan Williams' New Results on Non-uniform Circuit Lower Bounds - Part II
Seminar
Speaker:
Prahladh Harsha
School of Technology and Computer Science
Tata Institute of Fundamental Research
Homi Bhabha Road
Date:
Tuesday, 30 Nov 2010 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Ryan Williams, a postdoc at IBM Almaden, posted a manuscript about a week ago on his home page (http://www.cs.cmu.edu/~ryanw/) proving that bounded depth circuits with AND, OR and MOD-m gates (also called ACC circuits) are not powerful enough to compute all of non-deterministic exponential time (NEXP). This result appears to have created quite a buzz on the theory blogs. I plan to give an informal presentation on Ryan's new result trying to explain what the fuss is all about.
The second part will be more technically involved. In this part, we will brave ourselves and dwell into Ryan's proof of NEXP not contained in ACC.