Ryan Williams (computer scientist)

For other people named Ryan Williams, see Ryan Williams (disambiguation).

Ryan Williams
Williams (November 2010)
Born	1979 (age 45–46)
Nationality	American
Alma mater	Cornell University Carnegie Mellon University
Scientific career
Fields	Computational complexity theory, Algorithms
Institutions	Carnegie Mellon University IBM Almaden Research Center Stanford University
Doctoral advisor	Manuel Blum

Richard Ryan Williams, known as Ryan Williams (born 1979), is an American theoretical computer scientist working in computational complexity theory and algorithms.

Education

Williams graduated from the Alabama School of Mathematics and Science before receiving his bachelor's degree in math and computer science from Cornell University in 2001 ^[1] and his Ph.D. in computer science in 2007 from Carnegie Mellon University under the supervision of Manuel Blum. ^[2] He was a member of the Institute for Advanced Study in Princeton for the 2008-09 academic year. From 2009 to 2011, he was a postdoctoral fellow in the Theory Group of IBM Almaden Research Center. From Fall 2011 to Fall 2016, he was a professor at Stanford University. In January 2017, he joined the faculty at MIT. ^[3] As of 2020, Williams is a full professor in the department of Electrical Engineering and Computer Science.

Research

Williams has been a member of the program committee for the Symposium on Theory of Computing in 2011 and various other conferences. He won the Ron V. Book best student paper award at the IEEE Conference on Computational Complexity in 2005 and 2007, ^[4] 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. ^[5]

Williams’s result that the complexity class NEXP is not contained in ACC⁰ received the best paper award at the Conference on Computational Complexity in 2011. ^[6] Complexity theorist Scott Aaronson has called the result "one of the most spectacular of the decade". ^[7] In 2024, for this work Williams was awarded the Gödel Prize.

Williams has also worked on the computational complexity of k-anonymity. ^[8]

In 2025, Williams, leveraging previous work of J. Cook and I. Mertz ^[9] on catalytic computing, proved that every deterministic multitape Turing machine of time complexity ${\displaystyle t}$ can be simulated in space ${\displaystyle O({\sqrt {t\log t}})}$, ^[10] improving the previous bound of ${\displaystyle O(t/\log t)}$ by Hopcroft, Paul, and Valiant, ^[11] and strengthening the case in the negative for the question if PSPACE =P. ^[12]

Personal life

Ryan Williams is married to Virginia Vassilevska Williams, also a theoretical computer scientist.

Selected publications

• Meyerson, Adam; Williams, Ryan (2004), "On the complexity of optimal k-anonymity", Proceedings of the Twenty-Third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS '04), New York, NY, USA: ACM, pp. 223–228, doi:10.1145/1055558.1055591, ISBN   978-1581138580, S2CID   6798963
• Williams, R. (2005), "Better Time-Space Lower Bounds for SAT and Related Problems", IEEE Conference on Computational Complexity (CCC), pp. 40–49
• Williams, R. (2005), "A New Algorithm for Optimal 2-Constraint Satisfaction and Its Implications", Theoretical Computer Science , 348 (2–3): 357–365, doi: 10.1016/j.tcs.2005.09.023
• Williams, R. (2008), "Time-Space Lower Bounds for Counting NP Solutions Modulo Integers", Computational Complexity, 17 (2): 179–219, doi:10.1007/s00037-008-0248-y, S2CID   8815358
• Williams, R. (2011), "Non-Uniform ACC Circuit Lower Bounds", IEEE Conference on Computational Complexity (CCC) (PDF), pp. 115–125, CiteSeerX   10.1.1.225.8935 , doi:10.1109/CCC.2011.36, ISBN   978-1-4577-0179-5, S2CID   7020039

References

1. Curriculum vitae (PDF), retrieved 2017-12-02
2. Ryan Williams at the Mathematics Genealogy Project
3. "Ryan Williams | MIT CSAIL Theory of Computation". toc.csail.mit.edu. Retrieved 2021-12-18.
4. Proceedings of 20th Annual IEEE Conference on Computational Complexity (CCC'05) San Jose, CA June 11-June 15, ISBN   0-7695-2364-1, and Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07) San Diego, California, June 13-March 16, ISBN   0-7695-2780-9.
5. "Best Student ICALP Paper". European Association for Theoretical Computer Science (EATCS).
6. Program for CCC2011 at http://computationalcomplexity.org/
7. Aaronson, Scott (November 8, 2010), "State of circuit lower bounds now slightly less humiliating", MIT Technology Review .
8. Meyerson & Williams (2004).
9. Cook, James; Mertz, Ian (2024-06-10). "Tree Evaluation is in Space 𝑂 (log 𝑛 · log log 𝑛)". Proceedings of the 56th Annual ACM Symposium on Theory of Computing. ACM. pp. 1268–1278. doi:10.1145/3618260.3649664. ISBN   979-8-4007-0383-6.
10. Ryan Williams, R. (2025-06-15). "Simulating Time with Square-Root Space". Proceedings of the 57th Annual ACM Symposium on Theory of Computing. ACM. pp. 13–23. doi:10.1145/3717823.3718225. ISBN   979-8-4007-1510-5.
11. Hopcroft, John; Paul, Wolfgang; Valiant, Leslie (April 1977). "On Time Versus Space". Journal of the ACM. 24 (2): 332–337. doi:10.1145/322003.322015. ISSN   0004-5411.
12. Brubaker, Ben (2025-05-21). "For Algorithms, a Little Memory Outweighs a Lot of Time". Quanta Magazine. Retrieved 2025-05-21.

External links

• Ryan William’s homepage at MIT
• Ryan Williams publications indexed by Google Scholar
• Ryan Williams at DBLP Bibliography Server