Richard Ryan Williams (* 1979) ist ein US-amerikanischer theoretischer Informatiker.

Williams studierte an der Cornell University und wurde 2007 an der Carnegie Mellon University bei Manuel Blum promoviert (Algorithms and Resource Requirements for Fundamental Problems).^[1] 2010 bis 2012 war er in der Theorie-Gruppe des IBM Almaden Research Center und ab 2011 Assistant Professor an der Stanford University. Seit 2017 ist er Associate Professor am Massachusetts Institute of Technology.

Williams befasst sich mit Komplexitätstheorie (zum Beispiel von K-Anonymität) und ist bekannt für den Beweis, dass die Komplexitätsklasse NEXPTIME nicht in der Schaltkreis-Komplexitätsklasse ACC0 enthalten ist^[2]. Damit gelang ihm ein Durchbruch nachdem lange nach solchen Schranken für ACC0 gesucht wurde.^[3] Dabei ist ACC0 die Komplexitätsklasse von Schaltkreisen mit beschränkter Tiefe und unbeschränktem fan-in in AND, OR,NOT und MOD-Gattern (AC0 zusätzlich mit MOD-Gattern). Dabei sind Mod-Gatter (modulare Gatter) Verallgemeinerungen von XOR-Gattern: bei einem mod m Gatter mit n Eingängen ist das Output genau dann Null falls die Anzahl der Einsen in den Inputs ein Vielfaches von m ist (für m=2 ergibt sich das XOR-Gatter).

2014 war Williams eingeladener Sprecher auf dem Internationalen Mathematikerkongress in Seoul (Algorithms for circuits and circuits for algorithms: connecting the tractable and intractable).

2025 bewies Williams, basierend auf früheren Arbeiten von Cook und Mertz^[4] zum katalytischen Rechnen, dass jede deterministische Multitape-Turingmaschine mit der Zeitkomplexität ${\displaystyle t}$ im Raum simuliert werden kann.^[5] Damit verbesserte er die bisherige Schranke von ${\displaystyle O({\sqrt {t\log t}})}$ von Hopcroft, Paul und Valiant^[6] und untermauerte die Verneinung der Frage, ob PSPACE=P ist.^[7]

• mit Adam Meyerson: 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, 2004, ACM, S. 223–228
• Better Time-Space Lower Bounds for SAT and Related Problems, IEEE Conference on Computational Complexity (CCC), 2005, S. 40–49
• A New Algorithm for Optimal 2-Constraint Satisfaction and Its Implications, Theoretical Computer Science, Band 348, 2005, S. 357–365.
• Time-Space Lower Bounds for Counting NP Solutions Modulo Integers, Computational Complexity, Band 17, 2008, S. 179–219
• Non-Uniform ACC Circuit Lower Bounds, IEEE Conference on Computational Complexity (CCC), 2011, S. 115–125, pdf

• Homepage am MIT

1. ↑ Ryan Williams im Mathematics Genealogy Project (englisch) Vorlage:MathGenealogyProject/Wartung/id verwendet
2. ↑ Ryan Williams, Non-Uniform ACC Circuit Lower Bounds, Preprint 2010, IEEE Conference on Computational Complexity (CCC), 2011, S. 115–125
3. ↑ A Circuit Lower Bound Breakthrough, Blog von Luca Trevisan, 8. November 2010
4. ↑ James Cook, Ian Mertz: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. ACM, 2024, ISBN 979-84-0070383-6, Tree Evaluation is in Space 𝑂 (log 𝑛 · log log 𝑛), S. 1268–1278, doi:10.1145/3618260.3649664 (englisch, acm.org). 
5. ↑ Ryan Williams: Simulating Time with Square-Root Space. 2025, arxiv:2502.17779 [cs.CC].
6. ↑ John Hopcroft, Wolfgang Paul, Leslie Valiant: On Time Versus Space. In: Journal of the ACM. 24. Jahrgang, Nr. 2, April 1977, ISSN 0004-5411, S. 332–337, doi:10.1145/322003.322015 (englisch, acm.org). 
7. ↑ Ben Brubaker: For Algorithms, a Little Memory Outweighs a Lot of Time. In: Quanta Magazine. 21. Mai 2025, abgerufen am 11. Juni 2025 (englisch).