Abstract: Complexity lower bounds like P ≠ NP assert that no efficient program exists for solving many important computational problems. The stability of modern commerce relies on stronger lower bounds being true (most prominently in cryptography and computer security). But the general problem of mathematically proving complexity lower bounds remains a mystery: for most prominent lower bound problems, we do not know how to begin proving them true. While computer scientists are extremely adept at designing algorithms, it still seems very difficult to reason about all possible efficient algorithms, including those that we will never see or execute, and argue that none of them can solve an NP-complete problem.
As there are presently enormous gaps in our lower bound knowledge, a central question on the minds of today’s complexity theorists is: how will we find better ways to reason about all efficient programs? I will argue that some progress can be made by (very deliberately) thinking algorithmically about lower bounds: looking at lower bound problems as algorithm design problems of a different form. I will outline some new approaches for viewing lower bounds in this way. Time permitting, I will also discuss how some old lower bound methods in circuit complexity have given way to new developments in algorithms.
Ryan Williams completed his undergraduate studies in Computer Science and Mathematics at Cornell and obtained his PhD in Computer Science at Carnegie Mellon in 2007. Following postdoctoral appointments at the Institute for Advanced Study and IBM Almaden, he has been Assistant Professor of Computer Science at Stanford since 2011. Williams' research interests are in the design and analysis of efficient algorithms and computational complexity theory, especially the power and limitations of circuits. Williams is also interested in theoretical topics that help give scientific explanations for computational phenomena, such as the unreasonable effectiveness of satisfiability solvers in practice. Along with some Best Paper awards, Williams has been awarded a Sloan Fellowship, an NSF CAREER Award, and a Microsoft Research Faculty Fellowship, and he was an invited speaker at the 2014 International Congress of Mathematicians.