Ryan Williams' New Results on Non-uniform Circuit Lower Bounds - Part II

Speaker: 

Prahladh Harsha School of Technology and Computer Science Tata Institute of Fundamental Research Homi Bhabha Road

Time: 

Tuesday, 30 November 2010 (All day)

Venue: 

  • A-212 (STCS Seminar Room)

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.