Monday, February 18, 2013

EATCS Award 2013 to 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 Martin Dyer. The laudatio for Martin Dyer is available here. Martin's Wikipedia page mentions his key achievements in

(1) - polynomial time algorithm for approximating the volume of convex bodies (with Alan Frieze and Ravindran Kannan)
(2) - linear programming in fixed dimensions
(3) - the path coupling method for proving mixing of Markov chains (with Russ Bubley)
(4) - complexity of counting constraint satisfaction problems.

In addition, the laudatio singles out his work with Alan Frieze on developing the probabilistic analysis of algorithms. Dyer and Frieze showed that many NP-hard problems arising in combinatorial optimisation can be solved in polynomial expected time when the instances are drawn from natural distributions.

Congratulations to Martin!

No comments: