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

 

e-max.it: your social media marketing partner
 

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.

e-max.it: your social media marketing partner
Read more...
 

Obituary for Jaco de Bakker, 1939-2012

On December 13, 2012, our colleague Jacobus Willem (Jaco) de Bakker, member of the Section Informatics of the Academia Europaea since 1990, passed away surrounded by his family in his home in Amsterdam after a short illness. He is survived by his wife Angeline, his children Bas, Jaska, Catrien, Jacob and Lisa, and two grandchildren.

e-max.it: your social media marketing partner
Read more...
 

ICALP 2013: 2nd Call for Papers

The 40th International Colloquium on Automata, Languages and Programming (ICALP), the main conference and annual meeting of the European Association for Theoretical Computer Science (EATCS), will take place from the 8th to the 12th of July 2013 in Riga, Latvia.

The main conference will be preceded by a series of workshops, taking place on Sunday, July 7th, 2013 (i.e., one day before ICALP).

e-max.it: your social media marketing partner
Read more...
 

ICALP 2013 - Call for Workshop Proposals

ICALP 2013 - 40th International Colloquium on Automata, Languages and Programming

8-12 July 2013, University of Latvia, Riga, Latvia

Supported by the European Association for Theoretical Computer Science (EATCS)

http://www.icalp2013.lu.lv/

e-max.it: your social media marketing partner
Read more...
 

Gödel Prize 2013 - Call for Nominations

The Call for Nominations for the 2013 Gödel Prize has been posted (pdf). Nominations for the award should be submitted to the Chair of the Award Committee, Sanjeev Arora - This e-mail address is being protected from spambots. You need JavaScript enabled to view it . The deadline for nominations is: January 11, 2013.

More information

e-max.it: your social media marketing partner
 

EATCS Award 2013 - Call for Nominations

The Call for Nominations for the EATCS Award 2013 has been published (pdf). Nominations and supporting data should be sent to the chairman of the EATCS Award Committee, Friedhelm Meyer auf der Heide - This e-mail address is being protected from spambots. You need JavaScript enabled to view it . The next award is to be presented during ICALP 2013 in Riga, Latvia. The deadline for nominations is: December 31, 2012.

More information

e-max.it: your social media marketing partner
 
<< Start < Prev 21 22 23 24 25 26 27 28 29 30 Next > End >>

Page 25 of 38

ICALP 2018

Prague, Czech Republic

July 9-13, 2018


MFCS 2017

Aalborg, Denmark

August 21-25, 2017               


ESA 2017

Vienna, Austria

September 4-8, 2017

DISC 2017

Vienna, Austria

October 16-20, 2017               

 


ICALP 2019

Patras, Greece

July 8-12, 2019               


 

 

New BEATCS issue is out!

Number 123, October 2017

European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.