
A Dogged Pursuit for Satisfaction
Ryan Williams of the Institute for Advanced Study traces his long effort to find an algorithm for Boolean Satisfiability (SAT) that beats brute-force search over all 2^n possibilities, a question tied directly to P vs NP. He walks through repeated failed attempts and the unexpected payoffs they produced: the algorithmic method, which shows how SAT algorithms beating exhaustive search can be converted into new computational hardness proofs, and fine-grained complexity, which connects faster SAT algorithms to improvements on textbook problems like shortest paths in graphs. The talk is framed as a researcher's narrative of dead ends turning into new subfields rather than a straight technical survey. Delivered as an IAS Members' Colloquium, it assumes no special background and spends its hour building intuition for why SAT sits at the center of so many open questions in theoretical computer science.