UTCS Faculty Candidate - Ryan Williams, Assistant Professor, Stanford University, "Improving Exhaustive Search and 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: 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.
- Awards & Honors
- About Us
- Student Engagement and Support
- Masters Program
- Ph.D. Program
- Financial Information
- Prospective Students
- Incoming Students
- Current Students
- Portfolio Program in Robotics
- Curricular Practical Training
- Grad Student Talks
- UTCS Direct