Martin Dyer

from Wikipedia, the free encyclopedia

Martin E. Dyer (born July 16, 1946 in Ryde , Isle of Wight ) is a British computer scientist .

Life

Dyer graduated from the University of Leeds with a bachelor's degree in 1967, received his master's degree from Imperial College in 1968 and received his doctorate in 1979 from the University of Leeds with Les G. Proll ( Vertex Enumeration in Mathematical Programming - Methods and Applications ). He is a professor at the University of Leeds.

plant

He deals with theoretical computer science, discrete optimization and combinatorics .

In the early 1980s he (independently of Nimrod Megiddo ) found the first linear algorithms for linear programming in low dimension with significant applications in computer geometry.

In 1991, together with Alan Frieze and Ravindran Kannan , he found a polynomial-time algorithm for calculating the volumes of convex bodies in all dimensions. All three of them received the Fulkerson Prize for this and the work was singled out as one of the most outstanding developments of algorithms at the award of the Knuth Prize to Kannan. The previously known algorithms for calculating volume grew exponentially over time with the dimension. Their algorithm uses Markov Chain Monte Carlo Algorithms (MCMC) and is one of the earliest and most important applications of this technique in approximation algorithms. It found its way into many textbooks as a prime example of an algorithm with which it can be precisely demonstrated that the use of probabilistic methods ( randomization ) leads to a faster solution to a problem.

With his doctoral student Russ Bubley he developed the path coupling technique for calculating the mixing time of Markov chains . The method is important for the development of MCMC, one of the most important techniques for approximation algorithms, for example for counting problems that are based on the simulation of rapidly mixing Markov chains. Dyer himself found some of the fastest known algorithms for such approximations for approximate counting problems, for example from statistical physics and applied statistics (statistical tests of hypotheses).

He also made important contributions to the complexity theory of counting problems and was a leader in the classification of such problems, for example constraint-satisfaction-problems (CSP) and homormorphisms of graphs (with Catherine Greenhill). With Frieze and Mark Jerrum he proved that counting independent sets in graphs of bounded degree is NP-difficult. More precisely, they proved that if the maximum degree is no polynomial-time probabilistic approximation algorithm for the counting problem exists (unless one assumes RP = NP ). It also follows from the work that the MCMC algorithm is probably already failing.

Dyer and Frieze made important contributions to the probabilistic analysis of algorithms in combinatorial optimization.

Prices

In 2013 he received the EATCS Award and in 1991 the Fulkerson Prize with Frieze and Kannan.

Web links

Individual evidence

  1. ^ Mathematics Genealogy Project
  2. ↑ Dyer, Frieze, Kannan A random polynomial-time algorithm for approximating the volume of convex bodies , Journal of the ACM, Volume 38, 1991, pp. 1-17
  3. ↑ Bubley, Dyer "Path coupling: a technique for proving rapid mixing in Markov chains" , Proceedings of the 38th Annual Symposium on Foundations of Computer Science, IEEE, 1997, pp. 223-231
  4. ↑ Sets of nodes of the graph in which no two elements of the set are connected by an edge
  5. ↑ Dyer, Frieze, Jerrum On counting independent sets in sparse graphs , SIAM J. Computing, 31, 2002, 1527-1541
personal data
SURNAME Dyer, Martin
ALTERNATIVE NAMES Dyer, Martin E.
BRIEF DESCRIPTION British computer scientist
DATE OF BIRTH July 16, 1946
PLACE OF BIRTH Ryde , Isle of Wight