UTCS Colloquia - Ryan Williams, Stanford University, Assistant Professor, "ACC Circuit Lower Bounds"
Signup Schedule: http://apps.cs.utexas.edu/talkschedules/cgi/list_events.cgi
Talk Audience: UTCS Faculty, Grads, Undergrads, Other Interested Parties
Host: David Zuckerman
Talk Abstract: We will give an overview of the recent proof that there are problems in nondeterministic exponential time (NEXP) which do not have constant-depth circuits of polynomial-size comprised of AND, OR, and modulo-m gates of unbounded fan-in, for all constants m. (This circuit class is often called ACC.) The problem of proving non-trivial lower bounds against ACC had been open since the 80's. Since the original proof was announced, several new simplifications and extensions have been discovered, which we plan to discuss.
Speaker Bio: Ryan Williams is an assistant professor in the computer science department at Stanford University. Previously he was the Josef Raviv postdoctoral fellow at IBM Almaden Research Center in San Jose, California, and a member of the Institute for Advanced Study in Princeton, New Jersey. He received his PhD from Carnegie Mellon in 2007 under Manuel Blum, and B.A. and M.Eng. degrees from Cornell. His primary research interests are in the theory of algorithms and computational complexity.
- Awards & Honors
- About Us
- Student Engagement and Support
- Masters Program
- Ph.D. Program
- Financial Information
- Prospective Students
- Incoming Students
- Current Students
- Curricular Practical Training
- Grad Student Talks
- UTCS Direct