Ryan Williams - "Improving Exhaustive Search and Circuit Lower Bounds" (EECS Special Seminar)


Event Speaker: 

Ryan Williams (Stanford)

Event Location: 


Event Date/Time: 

Thursday, April 4, 2013 - 4:00pm

This talk will outline some strong connections that have
recently been discovered 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.

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
honors include several best paper awards and very recently an Alfred
P. Sloan Fellowship.