Ryan Williams (Informatiker)

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 Zeitkomplexität ${\displaystyle t}$ in ${\displaystyle O({\sqrt {t\log t}})}$ Raum simuliert werden kann.^[5] Damit verbesserte er die bisherige Schranke von ${\displaystyle O(t/\log t)}$ Hopcroft, Paul und Valiant^[6] und untermauerte die Verneinung der Frage, ob PSPACE=P ist.^[7]