Top Qs
Timeline
Chat
Perspective

Ryan Williams (computer scientist)

Computer scientist From Wikipedia, the free encyclopedia

Ryan Williams (computer scientist)
Remove ads

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

Quick Facts Born, Nationality ...
Remove ads

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] From 2010 to 2012, he was a member of 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]

Remove ads

Research

Summarize
Perspective

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 at 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 ACC0 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 Gödel Prize.

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

In a 2025 preprint Williams leveraging previous work J. Cook and Mertz[9] on catalytic computing proved that every deterministic multitape Turing machine of time complexity can be simulated in space [10] improving the previous bound of by Hopcroft, Paul, and Valiant[11] and strengthening the case in the negative for the question if PSPACE=P.[12]

Remove ads

Personal life

Ryan 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
Remove ads

References

Loading content...
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads