Best paper awards at ICALP 2012

The preliminary version of the detailed programme for ICALP 2012 is now available here. While skimming through the programme, I learnt that the best paper awards for the conference will go to the following papers:

• Leslie Ann Goldberg and Mark Jerrum. The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation). Best paper for Track A. 
• Volker Diekert, Manfred Kufleitner, Klaus Reinhardt and Tobias Walter. Regular Languages are Church-Rosser Congruential. Best paper for Track B.
• Piotr Krysta and Berthold Vöckin. Online Mechanism Design (Randomized Rounding on the Fly). Best paper for Track C.

The best student papers are:

• Anastasios Zouzias. A Matrix Hyperbolic Cosine Algorithm and Application. Co-recipient of the best student paper for Track A.   
• Shelby Kimmel. Quantum Adversary (Upper) Bound. Co-recipient of the best student paper for Track A. 
• Yaron Velner. The Complexity of Mean-Payoff Automaton Expression. Best student paper for Track B.
• Leonid Barenboim. On the Locality of NP-Complete Problems. Best student paper for Track C.

Congratulations to all the award recipients!

The scientific programme for ICALP 2012 looks really action packed. The invited speakers are:

• Gilles Dowek (INRIA Paris)
• Kohei Honda (Queen Mary London)
• Stefano Leonardi (Sapienza University of Rome)
• Daniel A. Spielman (Yale)
• Berthold Vöcking (RWTH Aachen)
• Alan Turing talk: David Harel (The Weizmann Institute of Science)

During the conference, there will be presented three special awards: EATCS/ACM SIGACT Gödel Prize 2012, EATCS Award 2012, and EATCS Presburger Award 2012.

• EATCS and ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT) awarded the Gödel Prize 2012 to three groups of researchers for their contributions to understanding how selfish behavior by users and service providers impacts the behavior of the Internet and other complex computational systems. The papers were presented by Elias Koutsoupias and Christos H. Papadimitriou, Tim Roughgarden and Éva Tardos, and Noam Nisan and Amir Ronen.
• The Presburger Award Committee 2012, consisting of Monika Henzinger, Antonin Kucera, and Stefano Leonardi (chair), has unanimously decided to propose Venkatesan Guruswami (Carnegie Mellon University, Pittsburgh) and Mihai Patrascu (AT&T Labs) as joint recipients of the 2012 EATCS Presburger Award for young scientists. (pdf)
• The EATCS Awards Committee consisting of Leslie Ann Goldberg, Friedhelm Meyer auf der Heide and Eugenio Moggi (chair), has unanimously decided to give the 2012 EATCS Award to Moshe Vardi (Rice University). (pdf)

The main conference will be preceded by a series of workshops taking place on Sunday, July 8.