www.wikidata.de-de.nina.az

Ryan Williams Informatiker Richard Ryan Williams 1979 ist ein US amerikanischer theoretischer Informatiker Ryan Williams

Ryan Williams (Informatiker)

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

Ryan Williams

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) Bearbeiten

  • 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 Bearbeiten

Einzelnachweise Bearbeiten

  1. Ryan Williams im Mathematics Genealogy Project (englisch) Vorlage:MathGenealogyProject/Wartung/id verwendet
  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
Personendaten
NAME Williams, Ryan
ALTERNATIVNAMEN Williams, Richard Ryan (vollständiger Name)
KURZBESCHREIBUNG US-amerikanischer theoretischer Informatiker
GEBURTSDATUM 1979
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Richard Ryan Williams 1979 ist ein US amerikanischer theoretischer Informatiker Ryan WilliamsWilliams 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 Er befasst sich mit Komplexitatstheorie zum Beispiel von K Anonymitat und ist bekannt fur den Beweis dass die Komplexitatsklasse NEXPTIME nicht in der Schaltkreis Komplexitatsklasse ACC0 enthalten ist 2 Damit gelang ihm ein Durchbruch nachdem lange nach solchen Schranken fur ACC0 gesucht wurde 3 Dabei ist ACC0 die Komplexitatsklasse von Schaltkreisen mit beschrankter Tiefe und unbeschranktem fan in in AND OR NOT und MOD Gattern AC0 zusatzlich mit MOD Gattern Dabei sind Mod Gatter modulare Gatter Verallgemeinerungen von XOR Gattern bei einem mod m Gatter mit n Eingangen ist das Output genau dann Null falls die Anzahl der Einsen in den Inputs ein Vielfaches von m ist fur 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 Bearbeitenmit 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 pdfWeblinks BearbeitenHomepage am MITEinzelnachweise Bearbeiten Ryan Williams im Mathematics Genealogy Project englisch Vorlage MathGenealogyProject Wartung id verwendet Williams Non Uniform ACC Circuit Lower Bounds Preprint 2010 IEEE Conference on Computational Complexity CCC 2011 S 115 125 A Circuit Lower Bound Breakthrough Blog von Luca Trevisan 8 November 2010Normdaten Person LCCN no2015011146 VIAF 313501035 Wikipedia Personensuche Kein GND Personendatensatz Letzte Uberprufung 17 Marz 2019 PersonendatenNAME Williams RyanALTERNATIVNAMEN Williams Richard Ryan vollstandiger Name KURZBESCHREIBUNG US amerikanischer theoretischer InformatikerGEBURTSDATUM 1979 Abgerufen von https de wikipedia org w index php title Ryan Williams Informatiker amp oldid 213453460