School of Technology and Computer Science Seminars

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

by Dr. Prahladh Harsha (School of Technology and Computer Science)

Tuesday, November 30, 2010 from to (Asia/Kolkata)
at Colaba Campus ( A-212 )
Description
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.
Organised by John Barretto