Ryan Williams (informaticien)
Ne doit pas être confondu avec Ryan Williams.
| Naissance | |
|---|---|
| Nationalité | |
| Formation |
Université Carnegie-Mellon (doctorat) ( - Université Cornell Alabama School of Mathematics and Science (en) |
| Activités |
| A travaillé pour | |
|---|---|
| Directeur de thèse |
Richard Ryan Williams, plus connu sous le nom de Ryan Williams (né en 1979), est un informaticien théoricien américain travaillant sur la théorie de la complexité computationnelle et les algorithmes .
Formation et carrière
Williams est diplômé de l'Alabama School of Mathematics and Science, puis il obtient un B. Sc. en mathématiques et en informatique à l'université Cornell en 2001 et ensuite puis son Ph. D. en informatiqueen 2007 à l'université Carnegie-Mellon sous la supervision de Manuel Blum[1]. De 2010 à 2012, Williams est membre du groupe de théorie du IBM Almaden Research Center. De l’automne 2011 à l’automne 2016, il est professeur à l’université Stanford. Depuis janvier 2017, il est au Massachusetts Institute of Technology, d'abord professeur associé et depuis 2020 professeur titulaire[2].
Recherche
Williams travaille en théorie de la complexité (notamment en K-anonymisation). Il est connu pour avoir prouvé que la classe de complexité NEXPTIME n'est pas incluse dans la classe de complexité de circuit ACC0[3]. Il a ainsi réussi une percée alors que l'on a longtemps cherché de telles barrières pour ACC0[4]. ACC0 est la classe de complexité des circuits avec une profondeur limitée et un fan-in illimité dans AND, OR,NOT et les portes MOD (AC0 avec en plus les portes MOD). Les portes MOD (portes modulaires) sont des généralisations des portes XOR : pour une porte mod m avec n entrées, la sortie est nulle si le nombre de 1 dans les entrées est un multiple de m (pour m=2, on obtient la porte XOR).
Williams a également travaillé sur la complexité informatique du k -anonymat[5].
Reconnaissance
Il remporte en 2005 et en 2007 le prix Ron V. Book du meilleur article, dans la catégorie "étudiant", à la Computational Complexity Conference[6] et en 2004 le prix du meilleur article étudiant au International Colloquium on Automata, Languages and Programming (ICALP) de l'European Association for Theoretical Computer Science[7].
Le résultat de Williams selon lequel la classe de complexité NEXP n'est pas contenue dans ACC0 a reçu le prix du meilleur article lors de la Conférence sur la complexité computationnelle en 2011.
En 2011, Williams est membre du comité de programme du Symposium on Theory of Computing et de diverses autres conférences.
En 2014 il est conférencier invité au congrès international des mathématiciens à Séoul (Algorithms for circuits and circumas for algorithms: connecting the tractable and intractable).
En 2024, Williams a reçu le prix Gödel pour ce travail.
Publications (sélection)
- Lijie Chen, Ce Jin, Rahul Santhanam et Ryan Williams, « Constructive Separations and Their Consequences », TheoretiCS, vol. 3, (DOI 10.46298/theoretics.24.3, arXiv 2203.14379, lire en ligne)
- Shyan Akmal, Virginia Vassilevska Williams, Ryan Williams et Zixuan Xu, « Faster Detours in Undirected Graphs », 31st Annual European Symposium on Algorithms (ESA 2023), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, , p. 7:1–7:17 (DOI 10.4230/LIPIcs.ESA.2023.7, lire en ligne)
- Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj et Ryan Williams, « Improved Merlin–Arthur Protocols for Central Problems in Fine-Grained Complexity », Algorithmica, vol. 85, no 8, , p. 2395–2426 (DOI 10.1007/s00453-023-01102-6, lire en ligne)
- Adam Meyerson et Ryan Williams, « 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, NY, USA, ACM, , p. 223–228 (ISBN 978-1581138580, DOI 10.1145/1055558.1055591, S2CID 6798963)
- R. Williams, « Better Time-Space Lower Bounds for SAT and Related Problems », IEEE Conference on Computational Complexity (CCC), , p. 40–49
- R. Williams, « A New Algorithm for Optimal 2-Constraint Satisfaction and Its Implications », Theoretical Computer Science, vol. 348, , p. 357–365 (DOI 10.1016/j.tcs.2005.09.023)
- R. Williams, « Time-Space Lower Bounds for Counting NP Solutions Modulo Integers », Computational Complexity, vol. 17, , p. 179–219 (DOI 10.1007/s00037-008-0248-y, S2CID 8815358)
- R. Williams, « Non-Uniform ACC Circuit Lower Bounds », IEEE Conference on Computational Complexity (CCC), , p. 115–125 (ISBN 978-1-4577-0179-5, DOI 10.1109/CCC.2011.36, S2CID 7020039, CiteSeerx 10.1.1.225.8935, lire en ligne)
Notes et références
- ↑ (en) « R. Ryan Williams », sur le site du Mathematics Genealogy Project
- ↑ CV de Williams au MIT
- ↑ Ryan Williams, Non-Uniform ACC Circuit Lower Bounds, Preprint 2010, IEEE Conference on Computational Complexity (CCC), 2011, p. 115–125.
- ↑ A Circuit Lower Bound Breakthrough, Blog de Luca Trevisan, 8 Novembre 2010
- ↑ Meyerson et Williams (2004).
- ↑ Proceedings of 20th Annual IEEE Conference on Computational Complexity (CCC'05) San Jose, CA June 11-June 15, (ISBN 0-7695-2364-1), et Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07) San Diego, California, June 13-March 16, (ISBN 0-7695-2780-9).
- ↑ « Best Student ICALP Paper 2004 », European Association for Theoretical Computer Science (EATCS).
Liens externes
- Ressources relatives à la recherche :
- Page de Ryan William au MIT
