Tata Institute of Fundamental Research
Ryan Williams' New Results on Non-uniform Circuit Lower Bounds - Part I
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 first part will be accessible to a general audience. In this part, we will try to understand the statement that Ryan proves. While doing so, I'll give a tour of circuit complexity over the last 3 decades, mentioning some of its successes, its setbacks and how Ryan's result resurrects some of the hope we originally had for circuit complexity.
| 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 first part will be accessible to a general audience. In this part, we will try to understand the statement that Ryan proves. While doing so, I'll give a tour of circuit complexity over the last 3 decades, mentioning some of its successes, its setbacks and how Ryan's result resurrects some of the hope we originally had for circuit complexity.
The first part will be accessible to a general audience. In this part, we will try to understand the statement that Ryan proves. While doing so, I'll give a tour of circuit complexity over the last 3 decades, mentioning some of its successes, its setbacks and how Ryan's result resurrects some of the hope we originally had for circuit complexity.