Ryan Williams, born in 1979, is an American computer scientist who works in the areas of computational complexity theory and algorithms.
Education
Williams graduated from the Alabama School of Mathematics and Science. He earned his bachelor's degree in math and computer science from Cornell University in 2001. He received his Ph.D. in computer science from Carnegie Mellon University in 2007 under the supervision of Manuel Blum. He was a member of the Institute for Advanced Study in Princeton during the 2008-09 academic year. From 2009 to 2011, he worked as a postdoctoral researcher in the Theory Group at IBM Almaden Research Center. From Fall 2011 to Fall 2016, he taught as a professor at Stanford University. In January 2017, he became a faculty member at MIT. As of 2020, Williams is a full professor in the Electrical Engineering and Computer Science department.
Research
Williams has been part of the program committee for the Symposium on Theory of Computing in 2011 and other conferences. He received the Ron V. Book best student paper award at the IEEE Conference on Computational Complexity in 2005 and 2007, and the best student paper award at the International Colloquium on Automata, Languages and Programming in 2004 from the European Association for Theoretical Computer Science.
Williams’ research showing that the complexity class NEXP is not contained in ACC won the best paper award at the Conference on Computational Complexity in 2011. Complexity theorist Scott Aaronson described the result as "one of the most spectacular of the decade." In 2024, Williams was honored with the Gödel Prize for this work.
Williams also studied the computational complexity of k-anonymity.
In 2025, Williams used earlier work by J. Cook and I. Mertz on catalytic computing to prove that every deterministic multitape Turing machine with time complexity t can be simulated in space O(√(t log t)), improving the previous bound of O(t / log t) by Hopcroft, Paul, and Valiant. This result strengthens the argument that PSPACE is not equal to P.