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:
Post a Comment