A Dogged Pursuit For Satisfaction
Ryan Williams (MIT CSAIL)
Distinguished Lecture Series
Thursday, October 24, 2024, 3:30 pm
Abstract
The P vs NP question boils down to whether the Boolean satisfiability problem (SAT) has a "fast" algorithm, running in polynomial time. In spite of the revolution in practical SAT solving that has occurred over the last two decades, it remains a major open problem to find an algorithm for SAT which can provably beat exhaustive search over all possibilities. In this talk, I will describe my dogged pursuit of such an algorithm and my various failures to find one, which led to new connections, research areas, and strange intellectual surprises. For one example, we found problems in P (even quadratic time) which are "harder to solve faster" than beating exhaustive search for SAT: improving upon the best algorithms for these P problems would yield improved SAT algorithms. This is one of the bedrock results in an area called "fine-grained complexity" which tries to understand which textbook algorithms are optimal, and what would be the consequences for improving them. For another example, we found that impossibility results in computing can be derived from SAT algorithms which beat exhaustive search. In particular, non-trivial procedures for analyzing small circuits can be used to rule out the possibility of small circuits computing other problems. This is the core idea in the "algorithmic method", an approach which has generated a large class of impossibility results which we currently only know how to prove by designing appropriate SAT algorithms.
Bio
Ryan Williams completed his PhD in Computer Science at Carnegie Mellon under Manuel Blum. Following postdocs at the Institute for Advanced Study and IBM Almaden, he was an Assistant Professor of Computer Science at Stanford for five years, and is presently Professor of Electrical Engineering and Computer Science at MIT. His awards include a Sloan Fellowship, an NSF CAREER fellowship, a Microsoft Research Faculty Fellowship, a Faculty Research Innovation Fellowship, and the 2024 Gödel Prize for his work on circuit lower bounds and the “algorithms to lower bounds” paradigm.
This talk is viewable on our YouTube channel.