Ryan Williams (computer scientist)

rdf:langString Ryan Williams (Informatiker)

rdf:langString 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). 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. Er 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 enthalten ist. Damit gelang ihm ein Durchbruch nachdem lange nach solchen Schranken für ACC0 gesucht wurde. 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 er eingeladener Sprecher auf dem Internationalen Mathematikerkongress in Seoul (Algorithms for circuits and circuits for algorithms: connecting the tractable and intractable).