Ryan Williams (Informatiker)

Datei:Ryan Williams at Dagstuhl 10441.jpg

Ryan Williams

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).<ref>Ryan Williams im Mathematics Genealogy Project (englisch) Vorlage:MathGenealogyProject/Wartung/id verwendet</ref> 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<ref>Ryan Williams, Non-Uniform ACC Circuit Lower Bounds, Preprint 2010, IEEE Conference on Computational Complexity (CCC), 2011, S. 115–125</ref>. Damit gelang ihm ein Durchbruch, nachdem lange nach solchen Schranken für ACC0 gesucht wurde.<ref>A Circuit Lower Bound Breakthrough, Blog von Luca Trevisan, 8. November 2010</ref> 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<ref>Vorlage:Cite book/URLVorlage:Cite book/Meldung2Vorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/Meldung</ref> zum katalytischen Rechnen, dass jede deterministische Multitape-Turingmaschine mit Zeitkomplexität <math>t</math> in <math>O(\sqrt{t \log t})</math> Raum simuliert werden kann.<ref>Ryan Williams: Simulating Time with Square-Root Space. 2025, arxiv:2502.17779 [cs.CC].</ref> Damit verbesserte er die bisherige Schranke von <math>O(t / \log t)</math> Hopcroft, Paul und Valiant<ref>Vorlage:Cite book/URLVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/Meldung2</ref> und untermauerte die Verneinung der Frage, ob PSPACE=P ist.<ref>Vorlage:Cite book/NameVorlage:Cite book/Name: [ For Algorithms, a Little Memory Outweighs a Lot of Time.] In: Quanta Magazine. , archiviert vom Vorlage:IconExternal (nicht mehr online verfügbar) am Vorlage:Cite book/URL; abgerufen am 11. Juni 2025 (). Vorlage:Cite book/URLVorlage:Cite book/MeldungVorlage:Cite book/Meldung2Vorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/MeldungVorlage:Cite book/Meldung</ref>

Schriften (Auswahl)

• 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

Weblinks

• Homepage am MIT

Einzelnachweise

<references />