The European Association for Theoretical Computer Science (EATCS) recently awarded Ryan Williams, MIT EECS professor and CSAIL member, with the 2024 Gödel Prize for his 2011 paper, “Non-Uniform ACC Circuit Lower Bounds.” Williams receives this honor for presenting a novel paradigm for a “rich two-way connection" between algorithmic techniques and lower-bound methods.
Each year, the Gödel Prize recognizes standout papers in theoretical computer science. Previous CSAIL recipients include MIT professors Shafi Goldwasser, Silvio Micali, Nir Shavit, Peter Shor, and Vinod Vaikuntanathan.
Williams is a lead researcher at the Theory of Computation group in CSAIL. He currently focuses on the theoretical design and analysis of efficient algorithms and in computational complexity theory, focusing mainly on new connections (and consequences) forged between algorithm design and logical circuit complexity.
Williams has long worked on one of the essential challenges in computational complexity: P vs. NP, a mystery first mentioned by famed mathematician and award namesake Kurt Gödel. The elusive equation P = NP proposes that if every solution to a problem can be verified quickly, then solutions can also be found quickly. Intuitively, P represents somewhat easy problems, whereas NP represents problems that are easily verified (but otherwise hard to solve). Thus P = NP would imply that computers can find easy solutions to hard problems.
To establish that some computing challenges are more difficult to solve than verify, researchers in complexity theory such as Williams continue to try to prove that P ≠ NP. They seek lower bounds — the minimum steps required for any algorithm to solve a given problem — to try to uncover what is algorithmically impossible.
Still, one particular class of computational circuits stumped computer scientists for more than two decades: ACC0. The issue prevailed until Williams presented that NEXP, a larger set of problems than NP, can’t be solved efficiently by those circuits. More broadly, Williams' paper confirmed a fruitful theoretical connection between algorithms and lower bounds that continues to stimulate new work in theoretical computer science. Winning a best paper award at the Computational Complexity Conference (CCC), he received high praise from Scott Aaronson, then-MIT faculty and current University of Texas at Austin professor: “The result is one of the most spectacular of the decade.”
The work has become a foundational paper in modern complexity theory, inspiring algorithm design for central problems. Theorists have used his technique to prove results about other classes of problems, such as the construction of rigid matrices and lower bounds in Kolmogorov complexity.
In the past, Williams has won several best paper awards, a Sloan Fellowship, an NSF CAREER Award, a Microsoft Research Faculty Fellowship, and he was an invited speaker at the 2014 International Congress of Mathematicians. He will receive his latest honor at the International Colloquium on Automata, Languages, and Programming (ICALP) in Tallinn, Estonia this July.
