Martin Edward Dyer (né le à Ryde, sur l'Île de Wight, en Angleterre) est un mathématicien et un théoricien de l'informatique, 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.
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 suivantesLaudatio pour le prix de l'EATCS. : 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 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) É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 FulkersonPrix Fulkerson 1991 en mathématiques discrètes pour leur article du journal de l'ACM. En 2013, l'EATCS lui attribue le Prix EATCS. Il reçoit le prix Gödel en 2021.
Publications
Notes et références
Liens externes
Page personnelle de Martin Dyer
Catégorie:Informaticien britannique Catégorie:Professeur à l'université de Leeds Catégorie:Personnalité en informatique théorique Catégorie:Naissance en juillet 1946 Catégorie:Étudiant de l'Imperial College London Catégorie:Lauréat du prix EATCS Catégorie:Lauréat du prix Fulkerson