Alan Frieze

Biographie

Frieze étudie à l'Université d'Oxford (bachelor en 1966) et obtient son doctorat à l'université de Londres en 1975 avec Keith Wolfenden [2]. En 1968/69, il est « research officer » à British Rail et en 1969/70, il est programmeur à International Computers Limited (ICL). En 1970/71, il est lecturer à Polytechnic of North London (maintenant London Metropolitan University) et de 1972 à 1987, il enseigne à la Queen Mary University of London. Il est professeur à l'université Carnegie-Mellon depuis 1987. Il est marié avec Carol Mayfield, qui enseigne également l'informatique à l'Université Carnegie Mellon, depuis 1969. Ils ont deux enfants.

Recherche

Avec Martin Dyer et Ravindran Kannan, il décrit en 1991 un algorithme en temps polynomial pour calculer les volumes des corps convexes en toutes les dimensions[3], algorithme pour lequel les trois ont reçu le prix Fulkerson en 1991. En outre, ce travail a été souligné comme l'un des développements les plus remarquables en matière d'algorithmique lors de l'attribution du prix Knuth à Ravindran Kannan. Le temps d'exécution de tous les algorithmes connus précédemment pour le calcul du volume augmente de façon exponentielle avec la dimension. Leur algorithme utilise la méthode de Monte-Carlo par chaînes de Markov (MCMC) et il est l'une des premières et des plus importantes applications de cette technique dans les algorithmes d'approximation.

Avec Ravindran Kannan, Frieze a élaboré une version algorithmique du lemme de régularité de Szemerédi[4],[5]. Dans leur article, ils ont introduit un lemme de régularité faible, qui est devenu un outil combinatoire important pour divers algorithmes (algorithmes de streaming, limites de graphes, algorithmes sous-linéaires).

Alan Frieze travaille en combinatoire probabiliste et ses applications en informatique théorique et en recherche opérationnelle. Il étudie en particulier les propriétés asymptotiques des graphes aléatoires, l'analyse du cas moyen des algorithmes et les algorithmes aléatoires. Ses travaux portent sur le comptage approximatif et le calcul de volume par le biais de marches aléatoires, la recherche de chemins disjoints dans les graphes expansifs, et l'exploration de la stabilité des algorithmes de routage.

Prix et distinctions

En 1991, il reçoit le prix Fulkerson avec Dyer et Kannan. En 1997, il a été boursier Guggenheim. En 2014, il est conférencier plénier au Congrès international des mathématiciens à Séoul ((Random structures and algorithms). Il est membre de l' American Mathematical Society[6]. Il est membre de la Society for Industrial and Applied Mathematics (SIAM) depuis 2011[7]. En 2015, il est élu Simons Fellow. Un colloque en l'honneur de Frieze, appelé « Frieze Fest », a eu lieu à l'université Carnegie-Mellon en 2005[8]

Publications (sélection)

Alan Frieze a publié quelque 300 articles d'après DBLP, et un livre :

  • Alan Frieze et Michał Karoński, Introduction to Random Graphs, Cambridge University Press, , 478 p. (ISBN 9781107118508, lire en ligne).
  • Béla Bollobás, Vladimir Nikiforov, Nicholas C. Wormald, Ralph J. Faudree et Alan M. Frieze, « Analytic Graph Theory », dans Jonathan L. Gross et Jay Yellen (éditeurs), Handbook of Graph Theory : Discrete Mathematics and Its Applications, Chapman & Hall / Taylor & Francis, (ISBN 978-1-58488-090-5), p. 787-871.
  • Alan M. Frieze et Wesley Pegden, « Maker Breaker on digraphs. 98(4): 653-661 (2021) », J. Graph Theory, vol. 98, no 4,‎ , p. 653-661 (lire en ligne).

Notes et références
  1. Dates d'après American Men and Women of Science, Thomson Gale 2004
  2. (en) « Alan Michael Frise », sur le site du Mathematics Genealogy Project.
  3. Martin Dyer, Alan Frieze et Ravindran Kannan, « A random polynomial-time algorithm for approximating the volume of convex bodies », Journal of the ACM, vol. 38, no 1,‎ , p. 1–17 (lire en ligne)
  4. Alan Frieze et Ravindran Kannan, « A simple algorithm for constructing Szemeredi's regularity partition », Electronic Journal of Combinatorics, vol. 6,‎ (lire en ligne).
  5. Alan Frieze et Ravindran Kannan, « The regularity lemma and approximation schemes for dense problems », Proc. 37. Symposium Foundations of Computer Science (FOCS),‎ .
  6. List of Fellows of the American Mathematical Society, retrieved 29 December 2012.
  7. Siam Fellows Class of 2011.
  8. « Carnegie Mellon Holds Workshop to Celebrate the Career of Influential Mathematician and Computer Scientist Alan Frieze » sur le site de CarnegieMellonToday

Liens externes
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.