Martin Dyer
Martin E. Dyer ( * July 16, 1946 in Ryde, Isle of Wight ) is a British computer scientist.
Life
Dyer studied at the University of Leeds with a Bachelor 's degree in 1967, earned his master 's degree in 1968 at Imperial College, and in 1979 at the University of Leeds in Les G. Proll doctorate (vertex enumeration in Mathematical Programming - Methods and Applications ). He is a professor at the University of Leeds.
Work
It deals with theoretical computer science, discrete optimization, and combinatorics.
In the early 1980s he found (regardless of Nimrod Megiddo ) the first in the linear time algorithms for linear programming in low dimension with important applications in computer geometry.
With Alan Frieze and Ravindran Kannan 1991 he found a polynomial - time algorithm for computing the volumes of convex bodies in all dimensions. All three would receive for the Fulkerson price and the work was stressed during the presentation of the Knuth Prize to Kannan as one of the most significant developments of algorithms at all. The previously known algorithms for calculating the volume grew in time exponentially with the dimension. My algorithm uses Markov chain Monte Carlo algorithms ( MCMC ) and is one of the earliest and most important applications of this technique in approximation algorithms. He was included in many textbooks as a prime example of an algorithm in which is exactly detectable, which leads to the use of probabilistic methods ( randomization) to a faster solution to a problem.
With his doctoral Russ Bubley, he developed the path - coupling technique (path coupling ) to calculate 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, in Abzählproblemen based on the simulation quickly mixing Markov chains. Dyer even found some of the fastest known algorithms for such approximations for counting problems ( approximate counting ), for example, from a statistical physics and applied statistics ( statistical tests of hypotheses).
He also made important contributions to the theory of complexity Abzählproblemen and was a leader in the classification of such problems, such as Constraint Satisfaction Problems ( CSP) and Homormorphismen of graphs ( with Catherine Greenhill ). With Frieze and Mark Jerrum he proved that the counting of independent sets in graphs is NP-hard with a limited degree. More precisely, they proved that if the maximum degree is not polynomzeitlicher probabilistic approximation algorithm for the Abzählproblem exists (unless you take on RP = NP). From the work also follows that the MCMC algorithm probably ceases to work for.
Dyer and Frieze made important contributions to the probabilistic analysis of algorithms in combinatorial optimization.
Prices
In 2013 he received the EATCS Award and the 1991 Fulkerson Prize with Frieze and Kannan.