Ryan Williams (computer scientist)

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{{citation|url=http://people.csail.mit.edu/rrw/cv.pdf|title=Curriculum vitae|accessdate=2017-12-02}} and his Ph.D. in computer science in 2007 from Carnegie Mellon University under the supervision of Manuel Blum.{{MathGenealogy|117553}} 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.{{Cite web|title=Ryan Williams {{!}} MIT CSAIL Theory of Computation|url=https://toc.csail.mit.edu/user/280|access-date=2021-12-18|website=toc.csail.mit.edu|language=en}}

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,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}}. 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.{{cite web|url=http://www.eatcs.org/index.php/best-student-icalp-paper|title=Best Student ICALP Paper|publisher=European Association for Theoretical Computer Science (EATCS)}}

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.Program for CCC2011 at http://computationalcomplexity.org/ Complexity theorist Scott Aaronson has called the result "one of the most spectacular of the decade".{{citation|first=Scott|last=Aaronson|authorlink=Scott Aaronson|title=State of circuit lower bounds now slightly less humiliating|journal=MIT Technology Review|date=November 8, 2010|url= http://www.scottaaronson.com/blog/?p=472}}. In 2024, for this work Williams was awarded Gödel Prize.

Williams has also worked on the computational complexity of k-anonymity.{{sfnp|Meyerson|Williams|2004}}

In a 2025 preprint Williams, leveraging previous work of J. Cook and I. Mertz{{Cite book |last1=Cook |first1=James |last2=Mertz |first2=Ian |chapter=Tree Evaluation is in Space 𝑂 (log 𝑛 · log log 𝑛) |date=2024-06-10 |title=Proceedings of the 56th Annual ACM Symposium on Theory of Computing |chapter-url=https://dl.acm.org/doi/10.1145/3618260.3649664 |language=en |publisher=ACM |pages=1268–1278 |doi=10.1145/3618260.3649664 |isbn=979-8-4007-0383-6}} on catalytic computing, proved that every deterministic multitape Turing machine of time complexity $t$ can be simulated in space $O(\backslash sqrt\{t\; \backslash log\; t\})${{cite arXiv|eprint=2502.17779 |last1=Ryan Williams |first1=R. |title=Simulating Time with Square-Root Space |date=2025 |class=cs.CC }} improving the previous bound of $O(t/\; \backslash log\; t)$ by Hopcroft, Paul, and Valiant{{Cite journal |last1=Hopcroft |first1=John |last2=Paul |first2=Wolfgang |last3=Valiant |first3=Leslie |date=April 1977 |title=On Time Versus Space |url=https://dl.acm.org/doi/10.1145/322003.322015 |journal=Journal of the ACM |language=en |volume=24 |issue=2 |pages=332–337 |doi=10.1145/322003.322015 |issn=0004-5411}} and strengthening the case in the negative for the question if PSPACE=P.{{Cite web |last=Brubaker |first=Ben |date=2025-05-21 |title=For Algorithms, a Little Memory Outweighs a Lot of Time |url=https://www.quantamagazine.org/for-algorithms-a-little-memory-outweighs-a-lot-of-time-20250521/ |access-date=2025-05-21 |website=Quanta Magazine |language=en}}

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

{{refbegin}}

• {{citation

| last1 = Meyerson | first1 = Adam

| last2 = Williams | first2 = Ryan

| contribution = On the complexity of optimal k-anonymity

| doi = 10.1145/1055558.1055591

| isbn = 978-1581138580

| location = New York, NY, USA

| pages = 223–228

| publisher = ACM

| title = Proceedings of the Twenty-Third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS '04)

| year = 2004| s2cid = 6798963

}}

• {{Citation

|last= Williams | first = R. | authorlink=Ryan Williams (computer scientist)

|contribution=Better Time-Space Lower Bounds for SAT and Related Problems

| title=IEEE Conference on Computational Complexity (CCC)

|pages=40–49

|year= 2005}}

• {{Citation

|last= Williams | first = R. | authorlink=Ryan Williams (computer scientist)

|title= A New Algorithm for Optimal 2-Constraint Satisfaction and Its Implications

|journal= Theoretical Computer Science

|volume=348

|number=2–3

|pages=357–365

|year= 2005

|doi=10.1016/j.tcs.2005.09.023|doi-access=free

}}

• {{Citation

|last= Williams | first = R. | authorlink=Ryan Williams (computer scientist)

|title=Time-Space Lower Bounds for Counting NP Solutions Modulo Integers

|journal= Computational Complexity

|volume= 17

|number=2

|pages= 179–219

|year= 2008

|doi=10.1007/s00037-008-0248-y| s2cid = 8815358 }}

• {{Citation

|last= Williams | first = R. | authorlink=Ryan Williams (computer scientist)

|contribution=Non-Uniform ACC Circuit Lower Bounds

| title=IEEE Conference on Computational Complexity (CCC)

|year =2011

|url=http://www.stanford.edu/~rrwill/acc-lbs.pdf

|doi=10.1109/CCC.2011.36

|pages=115–125| isbn = 978-1-4577-0179-5 | citeseerx = 10.1.1.225.8935 | s2cid = 7020039 }}

{{refend}}

{{Reflist}}

• [http://people.csail.mit.edu/rrw/ Ryan William’s homepage] at MIT
• {{google scholar id|EnEiF7oAAAAJ}}
• {{DBLP|w/RyanWilliams}}

{{Authority control}}

{{Gödel winners}}

{{DEFAULTSORT:Williams, Ryan}}

Category:Theoretical computer scientists

Category:Living people

Category:1979 births

Category:Cornell University alumni

Category:Stanford University faculty

Category:Massachusetts Institute of Technology faculty

Category:Gödel Prize laureates