Martin Edward Dyer (né le 16 juillet 1946 à Ryde, sur l'Île de Wight, en Angleterre) est un mathématicien et un information théoricien, spécialiste de la complexité des problèmes d'optimisation. Il est professeur à la School of Computing de l'université de Leeds, en Angleterre.

Parcours professionnel

Il obtient un diplôme de gradué à l'université de Leeds en 1967, un M.S. à l'Imperial College London en 1968 et un Ph. D. à l'université de Leeds in 1979 (« Vertex Enumeration in Mathematical Programming - Methods and Applications ».) sous la direction de Les G. Proll^[1].

Recherche

Ses domaines de recherche sont l'informatique théorique, l'optimisation discrète et la combinatoire. Il travaille notamment sur la complexité du dénombrement et sur l'efficacité des algorithmes de dénombrement approché à l'aide de chaînes de Markov. Les contributions principales sont les suivantes^[2] :

• Martin Dyer et indépendamment Nimrod Megiddo, découvrent des algorithmes linéaires en temps pour des programmes linéaires en basse dimension. Ces algorithmes sont améliorés ensuite par Dyer, Megiddo et d'autres et conduisent à des algorithmes très efficaces en temps linéaire qui ont des applications importantes en géométrie algorithmique.
• En analyse probabiliste d'algorithmes, les résultats de Dyer et Frieze montrent que de nombreux problèmes NP-difficiles en optimisation combinatoire peuvent être résolu en temps polynomial en moyenne si les instances sont tirées selon des distributions naturelles.
• Un article, avec Alan Frieze et Ravindran Kannan^[3] décrit un algorithme randomisé en temps polynomial d'approximation du volume d'un objet convexe en grande dimension. Cet article est le plus connu. Les approches usuelles ont un temps d'exécution qui croît exponentiellement avec le nombre de dimensions. L'article des trois auteurs décrit le premier algorithme polynomial en fonction de la dimension.
• Application de la méthode de couplage de chemins pour démontrer que des chaînes de Markov sont rapidement mélangeantes (avec Russ Bubley)^[4]
• Étude de la complexité du dénombrement de problèmes de satisfaction de contraintes.

Prix et distinctions

En 1991, Martin Dyer reçoit, avec Alan Frieze and Ravi Kannan, le Prix Fulkerson^[5] en mathématiques discrètes pour leur article du journal de l'ACM^[3]. En 2013, l'EATCS lui attribue le Prix EATCS. Il reçoit le prix Gödel en 2021.

Publications

• (en) Martin Dyer et Catherine Greenhill, « Corrigendum: The complexity of counting graph homomorphisms », Random Structures and Algorithms, Wiley-Blackwell, vol. 25, n^o 3,‎ 2004, p. 346-352 (ISSN 1042-9832 et 1098-2418, DOI 10.1002/RSA.20036)
• (en) Martin Dyer, Alan Frieze et Ravi Kannan, « A random polynomial-time algorithm for approximating the volume of convex bodies », Journal of the ACM, New York, ACM, vol. 38, n^o 1,‎ 3 janvier 1991, p. 1-17 (ISSN 0004-5411 et 1557-735X, OCLC 783892264 et 1514518, DOI 10.1145/102782.102783)

Notes et références