# Ryan Williams (informaticien)

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 informatique en 2007 à l'université Carnegie-Mellon sous la supervision de Manuel Blum. 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 travaille au Massachusetts Institute of Technology, d'abord professeur associé et depuis 2020 professeur titulaire.

## 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 (en). Il a ainsi réussi une percée alors que l'on a longtemps cherché de telles barrières pour ACC0. 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.

## 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 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.
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,‎ 15 février 2024 (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, — Leibniz International Proceedings in Informatics (LIPIcs) n$^o$ 274,‎ 2023, 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, n$^o$ 8,‎ 1er août 2023, 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,‎ 2004, p. 223–228 (ISBN 978-1581138580, DOI 10.1145/1055558.1055591, S2CID 6798963)
* Ryan Williams, « Better Time-Space Lower Bounds for SAT and Related Problems », IEEE Conference on Computational Complexity (CCC),‎ 2005, p. 40–49
* Ryan Williams, « A New Algorithm for Optimal 2-Constraint Satisfaction and Its Implications », Theoretical Computer Science, vol. 348, n$^{os}$ 2–3,‎ 2005, p. 357–365 (DOI 10.1016/j.tcs.2005.09.023 )
* Ryan Williams, « Time-Space Lower Bounds for Counting NP Solutions Modulo Integers », Computational Complexity, vol. 17, n$^o$ 2,‎ 2008, p. 179–219 (DOI 10.1007/s00037-008-0248-y, S2CID 8815358)
* Ryan Williams, « Non-Uniform ACC Circuit Lower Bounds », IEEE Conference on Computational Complexity (CCC),‎ 2011, p. 115–125 (ISBN 978-1-4577-0179-5, DOI 10.1109/CCC.2011.36, S2CID 7020039, CiteSeer$^x$ 10.1.1.225.8935, lire en ligne)