UTCS Faculty Candidate - Ryan Williams, Assistant Professor, Stanford University, "Improving Exhaustive Search and Circuit Lower Bounds"

Contact Name: 
Kevin Hendryx
ACES 2.302
Feb 7, 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: Recently we have uncovered strong connections between the art of finding good algorithms and the art of proving complexity lower bounds, i.e., mathematical limitations on what problems can be solved by good algorithms. Surprisingly, if the naive exhaustive search algorithm for the Circuit Satisfiability problem can be only slightly improved in some situations, then interesting circuit complexity lower bounds can be proved. That is, somewhat "weak" algorithms for solving one problem can be translated into strong lower bounds for solving another problem. These connections between algorithm design and complexity theory have made it possible to prove new complexity lower bounds that had long been conjectured (by designing new algorithms), and they suggest concrete directions for further progress in both algorithms and complexity.

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.