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 , il travaille au Massachusetts Institute of Technology, d'abord professeur associé et depuis 2020 professeur titulaireCV de Williams au MIT.
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 Ryan Williams, Non-Uniform ACC Circuit Lower Bounds, Preprint 2010, IEEE Conference on Computational Complexity (CCC), 2011, p. 115–125.. Il a ainsi réussi une percée alors que l'on a longtemps cherché de telles barrières pour ACC0A Circuit Lower Bound Breakthrough, Blog de Luca Trevisan, 8 novembre 2010. 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 ConferenceProceedings of 20th Annual IEEE Conference on Computational Complexity (CCC'05), San Jose, CA June 11-June 15, , et Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), San Diego, California, June 13-March 16, . 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)
Notes et références
Liens externes
Page de Ryan William au MIT
Catégorie:Lauréat du prix Gödel Catégorie:Professeur au Massachusetts Institute of Technology Catégorie:Professeur à l'université Stanford Catégorie:Étudiant de l'université Cornell Catégorie:Naissance en 1979