UTCS Colloquia - Ryan Williams, Stanford University, Assistant Professor, "ACC Circuit Lower Bounds," GDC 4.516

Contact Name: 
David Zuckerman
GDC 4.516
Feb 8, 2013 11:00am - 12:00pm

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.