BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/129
DTSTAMP:20230914T125911Z
SUMMARY:Ryan Williams' New Results on Non-uniform Circuit Lower Bounds - Pa
 rt I
DESCRIPTION:Speaker: Prahladh Harsha\nSchool of Technology and Computer Sci
 ence\nTata Institute of Fundamental Research\nHomi Bhabha Road\n\nAbstract
 : \nRyan 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 bo
 unded depth circuits with AND\, OR and MOD-m gates (also called ACC circui
 ts) are not powerful enough to compute all of non-deterministic exponentia
 l time (NEXP). This result appears to have created quite a buzz on the the
 ory blogs. I plan to give an informal presentation on Ryan's new result tr
 ying to explain what the fuss is all about.\n\nThe first part will be acce
 ssible 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\, it
 s setbacks and how Ryan's result resurrects some of the hope we originally
  had for circuit complexity.\n
URL:https://www.tcs.tifr.res.in/web/events/129
DTSTART;VALUE=DATE:20101130
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR