Alan Frieze
# Alan Frieze

Alan Michael Frieze (né le 25 octobre 1945 à Londres) est un informaticien britannique.

## Biographie

Frieze étudie à l'Université d'Oxford (bachelor en 1966) et obtient son doctorat à l'université de Londres en 1975 avec Keith Wolfenden. 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, 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^,.$ 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. Il est membre de la Society for Industrial and Applied Mathematics (SIAM) depuis 2011. 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

## 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, février 2016, 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, 2003 (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, $n^o$ 4,‎ 2021, p. 653-661 (lire en ligne).
