The EATCS Award 2013 - Laudatio for Martin Dyer

The EATCS Awards Committee consisting of Leslie Ann Goldberg, Vladimiro Sassone and Friedhelm Meyer auf der Heide (chair), has unanimously decided to give the EATCS Award to Professor Martin Dyer. (pdf)

Martin Dyer has made enormous and multifaceted contributions to Theoretical Computer Science. His work contains deep insights which have opened new frontiers and changed the research landscape. Many of his contributions are landmark results of great originality and beauty. Some of these have already become prominent textbook material. The full impact of these results is becoming increasingly clear as time progresses. We are pleased to recognise these contributions with the 2013 EATCS Award.

Scientific contributions

Dyer’s contributions span a wide range of topics within Theoretical Computer Science, including
the following.

  • Pioneering the development of linear-time algorithms for linear programming in a fixed number of dimensions. In the early 1980s, Dyer, and independently, Meggido, discovered the first linear-time algorithms for low-dimensional linear programs. Dyer’s first path-breaking result showed that these can be solved in time linear in the number of constraints when the number of variables is at most 3. These techniques were improved by Dyer and Meggido (and subsequently, by others) leading to very-efficient linear-time algorithms which have important applications in computational geometry.
  •  Developing probabilistic analysis of algorithms. Dyer and Frieze made seminal contributions to this area, showing that many NP-hard problems arising in combinatorial optimisation can be solved in polynomial expected time when the instances are drawn from natural distributions.
  •  Discovering the first polynomial-time algorithm for estimating the volume of a highdimensional convex body. In a truly magnificent paper “A random polynomial-time algorithm for approximating the volume of convex bodies”, Dyer, Frieze and Kannan gave a polynomial-time randomised algorithm for approximating the volume of a convex body in high-dimensional Euclidean space. This is essentially the problem of numerical integration. Classical approaches to solving this problem involve dissecting space into small cubes and adding the contributions from these. The running time of such methods necessarily grows exponentially in the number of dimensions. Dyer, Frieze and Kannan’s paper describes the first algorithm for volume estimation whose running time scales polynomially in the number of dimensions. This paper was awarded the 1991 Fulkerson prize for outstanding publications in discrete mathematics. The citation for Kannan’s 2011 Knuth prize referred to the result as “one of the most remarkable algorithmic achievements ever”. This result is now the textbook example of a case in which randomisation provably speeds up computation time. The result is one of the earliest, most exciting, and most important applications of the Markov Chain Monte Carlo (MCMC) method in approximation algorithms, and it shaped the way future research in this area has developed.
  • Introducing the elegant and useful path-coupling technique for bounding the mixing time of Markov chains. The MCMC method is one of the most important techniques for developing approximation algorithms, especially in applications related to approximate counting. These approximation algorithms are based on the simulation of rapidly-mixing Markov chains, and a key scientific challenge is determining the mixing rate of the chains. One of the most fruitful and elegant methods that has been discovered is the “path coupling” technique, which was discovered by Dyer together with his PhD student Bubley. Path coupling is a very simple and intuitive method for proving that a Markov chain is rapidly mixing. Despite its simplicity, it is very effective and easy to use. It has therefore become part of the repertoire of every researcher working in the area of rapid mixing Markov chain algorithms.
  • Discovering fast algorithms for approximate counting. Dyer has contributed numerousapproximate counting algorithms, giving the fastest known algorithms for many significantproblems arising in combinatorial enumeration, statistical physics and statisticalhypothesis testing. Most of these are randomised algorithms, but a notable exceptionis his dynamic-programming approach to approximation, which he used to give the firstpolynomial-time approximation algorithm for counting knapsack solutions and for othercounting problems.
  •  Classifying the complexity of counting problems. In addition to providing some of the fastest approximate counting algorithms that we have, Dyer has been a leading figure in developing a complexity theory of counting, classifying a wide domain of problems from homomorphism problems to constraint satisfaction problems. For example, his work with Frieze and Jerrum on the hardness of approximately counting independent sets in bounded-degree graphs pioneered the area of exploiting phase transitions to achieve complexity-theoretic hardness. His work with Greenhill on classifying the complexity of counting graph homomorphisms opened up a whole area of research. Finally, his alternative proof, with Richerby, of Bulatov’s #CSP dichotomy theorem is so accessible and elegant that it has spawned substantial further progress in the area.

To acknowledge these extensive and widely-recognized contributions to theoretical computer
science, we present the EATCS Award 2013 to Martin Dyer.

The EATCS Awards Committee 2013:

  •  Leslie Ann Goldberg
  •  Friedhelm Meyer auf der Heide (chair)
  •  Vladimiro Sassone your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.