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!

Friday Fun

 

Source: One of the Computer Science students at Reykjavík University

Erik Demaine receives the EATCS Presburger Award 2013

The Presburger Award Committee, consisting of Peter Widmayer, Antonin Kucera and Monika Henzinger (chair), has unanimously decided to propose Erik Demaine (MIT, USA) as recipient of the 2013 EATCS Presburger Award for young scientists. Congratulations to Erik!

The Presburger Award is sponsored by CWI, Centrum Wiskunde & Informatica.

The citation for the award reads as follows.

Erik Demaine, born in 1981, has made outstanding contributions in several fields of algorithms, namely computational geometry, data structures, graph algorithms and recreational algorithms. In computational geometry and data structures he has solved or made significant progress on classic problems such as the carpenter’s rule problem, the hinged-dissection problem, the prefix-sum problem, and the dynamic optimality conjecture. In graph algorithms he used the powerful theory of graph minors to develop a suite of algorithms for approximately solving a general family of intractable problems. He also started the new field of computational origami, where his book is the leading authority in the field. His work  has shown promising applications to computer graphics, sensor networks, molecular biology, programmable matter, and manufacturing and engineering.

The committee recommends Erik Demaine as an exceptional young scientist who fully deserves the Presburger Award.

The committee would also like to mention that the quality of all nominations submitted this year was very high. The Presburger Award is attracting the best young scientists in the field of theoretical computer science worldwide.

Addendum, 14 February 2013: Check out a Popular Science article on Erik's work here:  http://www.popsci.com/science/article/2013-01/dazzling-sometimes-absurd-always-playful-genius-erik-demaine.

Poster for the Pearls of Computation seminar series

The poster has been designed by the talented team at Podpunkt. In case you need a good design for book covers, logos or posters, you might wish to consider them. Look at their portfolio and enjoy their work. As I remarked in an earlier post, the Podpunkt studio has strong connections with mathematics and TCS.