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 ACC0 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).

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

Einzelnachweise

  1. ↑ Ryan Williams im Mathematics Genealogy Project (englisch)
  2. ↑ 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.