EATCS Awards

Gödel Prize EATCS Award Best ICALP Paper Best Student ICALP Paper Best ETAPS Paper Best ESA Paper Best Student ESA Paper Dijkstra Prize

Gödel Prize (together with ACM SIGACT)

The Gödel Prize for outstanding papers in the area of theoretical computer science is sponsored jointly by the European Association for Theoretical Computer Science (EATCS) and the Special Interest Group on Algorithms and Computing Theory of the Association of Computing Machinery (ACM SIGACT). This award is presented annually, with the presentation taking place alternately at the International Colloquium on Automata, Languages, and Programming (ICALP) and ACM Symposium on the Theory of Computing (STOC). The Prize is named in honor of Kurt Gödel in recognition of his major contributions to mathematical logic and of his interest, discovered in a letter he wrote to John von Neumann shortly before Neumann's death, in what has become the famous "P versus NP" question. The Prize includes an award of $5000 (US).

The Call for Nominations for the 2008 Gödel Prize has been posted ([html] [pdf]). The deadline for nominations is January 31, 2008. If you intend to submit a nomination, please notify the Gödel2008 Award Committee Chair, Volker Diekert, via email to diekert AT fmi.uni-stuttgart.de. Please put "Goedel08" on the "Subject" line of your message.

More information can be found on the ACM SIGACT Gödel Prize site.

Year	Awarded	Place	Committee
2007	Alexander A. Razborov Steven Rudich	STOC (San Diego)	John Reif, Duke University (chair) Volker Diekert, Universität Stuttgart Shafi Goldwasser, MIT and Weizmann Institute Christos Papadimitriou, UC Berkeley Colin Stirling, University of Edinburgh Paul Vitanyi, CWI, Amsterdam
2006	Manindra Agrawal Neeraj Kayal Nitin Saxena	ICALP (Venice)	Pierre-Louis Curien (chair) Volker Diekert Christos Papadimitriou John Reif Jeffrey Ullman Paul Vitanyi
2005	Noga Alon Yossi Matias Mario Szegedy	STOC (Baltimore)	G. Ausiello L. Babai (chair) P.-L. Curien J. Reif J. Ullman P. Vitanyi
2004	Maurice Herlihy Nir Shavit Michael Saks Fotios Zaharoglou	ICALP (Turku)	G. Ausiello L. Babai P.-L. Curien Z. Galil J. Karhumäki (chair) J. Ullman
2003	Yoav Freund Robert Schapire	STOC (San Diego)	G. Ausiello L. Babai Z. Galil J. Karhumäki D. Kozen (chair) U. Montanari
2002	Géraud Sénizergues	ICALP (Málaga)	U. Montanari D. Kozen J. Karhumäki Z. Galil J. Simon K. Mehlhorn (chair)
2001	Sanjeev Arora Uriel Feige Shafi Goldwasser Carsten Lund Laszlo Lovász Rajeev Motwani Shmuel Safra Madhu Sudan Mario Szegedy	ICALP (Crete)	F. Preparata J. Simon D. Kozen K. Mehlhorn U. Montanari W. Thomas (chair)
2000	Moshe Y. Vardi Pierre Wolper	STOC (Portland)	L. Valiant F. Preparata (chair) J. Simon A. Pnueli W. Thomas K. Mehlhorn
1999	Peter W. Shor	STOC (Philadelphia)	R . Graham (chair) L. Valiant F. Preparata A. Pnueli E. Welzl W. Thomas
1998	Seinosuke Toda	ICALP (Aalborg)	R. Graham D. Johnson L. Valiant A. Pnueli E. Welzl (chair) G. Rozenberg
1997	Joseph Halpern Yoram Moses	ICALP (Bologna)	R. Graham D. Johnson J. Hartmanis G. Plotkin E. Welzl G. Rozenberg (chair)
1996	Mark Jerrum Alistair Sinclair	FOCS (Philadelphia)	M. Rabin (chair) D. Johnson J. Hartmanis G. Plotkin J. van Leeuwen G. Rozenberg
1995	Neil Immerman Róbert Szelepcsényi	FOCS (Las Vegas)	M. Rabin R. Karp (chair) J. Hartmanis G. Plotkin J. van Leeuwen A. Salomaa
1994	Johan Håstad	ICALP (Jerusalem)	M. Rabin R. Karp S. Cook R. Milner J. van Leeuwen A. Salomaa (chair)
1993	László Babai Shlomo Moran Shafi Goldwasser Silvio Micali Charles Rackoff	STOC (San Diego)	A.C. Yao (chair) R. Karp S. Cook R. Milner B. Monien A. Salomaa

EATCS Award

The EATCS Award is awarded in recognition of a distinguished career in theoretical computer science.

The Committee (consisting of Catuscia Palamidessi, David Peleg as chair, and Emo Welzl) of the European Association for Theoretical Computer Science in charge of evaluating the nominations to the 2008 EATCS Award has come to the decision to propose Prof. LESLIE G. VALIANT as the candidate for the 2008 EATCS Award (as it is specified by the motivation prepared by the Committee).

The proposal has been unanimously approved by the EATCS Council. The Award will be assigned during a ceremony that will take place in Reykjavik (Iceland) during ICALP (July 6-13, 2008).

A brief history of the EATCS Award follows below.

Year	Awarded	Place
2008	Leslie G. Valiant	ICALP (Reykjavik)
2007	Dana S. Scott	ICALP (Wroclaw)
2006	Mike Paterson	ICALP (Venice)
2005	Robin Milner	ICALP (Lisboa)
2004	Arto Salomaa	ICALP (Turku)
2003	Grzegorz Rozenberg	ICALP (Eindhoven)
2002	Maurice Nivat	ICALP (Málaga)
2001	Corrado Böhm	ICALP (Creta)
2000	Richard Karp	ICALP (Geneva)

Best ICALP Paper

The prize of "Best ICALP Paper" is awarded at the ICALP conferences.

A brief history of the prize follows below.

Year	Awarded	Paper	Place
2007	Jin-Yi Cai Pinyan Lu	Track A: "Holographic algorithms. The Power of Dimensionality Resolved"	Wroclaw
	Bernard Boigelot Julien Brusten	Track B: "A Generalization of Cobham's Theorem to Automata over Real Numbers"
	Tal Moran Moni Naor Gil Segev	Track C: "Deterministic History Independent Strategies for Storing Information on Write Once Memories"
2006	Martin Dyer Leslie Ann Goldberg Mike Paterson	Track A: "On counting homomorphisms to directed acyclic graphs"	Venice
	Filip Murlak	Track B: "The Wadge Hierarchy of Deterministic Tree Languages"
	Iftach Haitner Danny Harnik Omer Reingold	Track C: "Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions"
2005	Martin Grohe Christoph Koch Nicole Schweikardt	Track B: "Tight Lower Bounds for Query Processing on Streaming and External Memory Data"	Lisboa
2005	Marius Zimand	Track C: "Simple Extractors Via Constructions of Cryptographic Pseudo-random Generators"	Lisboa
2004	Christoph Dürr Mark Heiligman Peter Hoyer Mehdi Mhalla	Track A: "Quantum query complexity of some graph problems"	Turku
2004	Mikolaj Bojanczyk Thomas Colcombet	Track B: "Tree-Walking Automata Cannot Be Determinized"	Turku
2003	Anna Gal Peter Bro Miltersen	Track A: "The cell probe complexity of succint data structures"	Eindhoven
2003	Marielle Stoelinga Frits Vaandrager	Track B: "A testing scenario for probabilistic automata"	Eindhoven
2002	Lars Engebretsen Jonas Holmerin Alexander Russell	"Inapproximability Results for Equations over Finite Groups"	Málaga
2001	William Hesse	Track A: "Division is in Uniform TC0"	Creta
2001	Parosh Aziz Abdulla Luc Boasson Ahmed Bouajjani	Track B: "Effective Lossy Queue Languages"	Creta
2000	Evgeny Dantsin Andreas Goerdt Edward A. Hirsch Uwe Schöning	"Deterministic algorithms for k-SAT based on covering codes and local search"	Geneva
	Dan R. Ghica Guy McCusker	"Reasoning about idealized Algol using regular languages"
	Seth Pettie Vijaya Ramachandran	"An optimal minimum spanning tree algorithm"

Best Student ICALP Paper

The prize of "Best Student ICALP Paper" is selected by the programme committee of ICALP, and is awarded to the best paper submitted to ICALP exclusively by full-time student(s).

A brief history of the prize follows below.

Year	Awarded	Paper	Place
2007	none awarded		Wroclaw
2006	Qiqi Yan	"Lower Bounds for Complementation of omega-Automata via the Full Automata Technique"	Venice
2005	Corina E. Patrascu Mihai Patrascu	Track A: "On Dynamic Bit-Probe Complexity"	Lisboa
	Damien Pous	Track B: "Up-to Techniques for Weak Bisimulation"
	Neeraj Kayal	Track C: "Solvability of a System of Bivariate Polynomial Equations over a Finite Field"
2004	Ryan Williams	Track A: "A new algorithm for optimal constraint satisfaction and its implications"	Turku
2004	Olivier Serre	Track B: "Games With Winning Conditions of High Borel Complexity"	Turku
2002	Seth Pettie	Track A: "A Faster All-pairs Shortest Path Algorithm for Real-weighted Sparse Graphs"	Málaga
2002	Colcombet Thomas	Track B: "On Families of Graphs Having a Decidable First Order Theory with Reachability"	Málaga
2001	William Hesse	"Division is in Uniform TC0"	Creta
2000	Lars Engebretsen Jonas Holmerin	Track A: "Clique is hard to approximate within n^(1-o(1))"	Geneva
2000	Tomasz Fryderyk Urbanski	Track B: "On deciding if deterministic Rabin language is in Büchi class"	Geneva
1999	Daniel Kirsten	"A connection between the star problem and the finite power property in trace monoids"	Prague
1998	Chi-Jen Lu	Track A: "Improved pseudorandom generators for combinatorial rectangles"	Aalborg
1998	Slawomir Lasota	Track B: "Partial-congruence factorization of bisimilarity induced by open maps"	Aalborg
1997	Salvador Roura	"An improved master theorem for divide-and-conquer recurrences"	Bologna

Best ETAPS Paper

The prize of "Best ETAPS Paper" is presented to the best theoretical paper at ETAPS.

A brief history of the prize follows below.

Year	Awarded	Paper	Place
2007	Christian Haack Erik Poll Jan Schaefer Aleksy Schubert	"Immutable Objects for a Java-like Language"	Braga
2006	Lutz Schröder	"A Finite Model Construction for Coalgebraic Modal Logic"	Vienna
2005	Andrzej Murawski Igor Walukiewicz	"Third-Order Idealized Algol with Iteration is Decidable"	Edingburgh
2004	Daniel Kirsten	"Distance Desert Automata and the Star Height One Problem"	Barcelona
2003	V. Sassone P. Sobocinski	"Deriving Bisimulation Congruences: 2-categories versus Precategories"	Warsaw
2002	E. Goddard Y. Metivier	"Characterization of Families of Graphs in which Election is Possible"	Grenoble
2001	Masahito Hasegawa Yoshihiko Kakutani	"Axioms for Recursion in Call-by-Value"	Genova
2000	Christophe Morvan	"On rational graphs"	Berlin

European Association for Programming Languages and Systems (EAPLS) also presents a Best Paper Award, which has been awarded since ETAPS'98.

Best ESA Paper

Beginning in 2007, EATCS sponsors an award for the best paper at ESA.

A brief history of the prize follows below.

Year	Awarded	Paper	Place
2007	Niv Buchbinder Kamal Jain Joseph (Seffi) Naor	"Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue"	Eilat

Best Student ESA Paper

EATCS sponsors an award for the best student paper at ESA. All of a paper's authors must be students for the paper to be considered for this award.

A brief history of the prize follows below.

Year	Awarded	Paper	Place
2007	Jakub Pawlewicz	"Order Statistics in the Farey Sequences in Sublinear Time"	Eilat
2006	Frederic Dorn	Design and Analysis Track: "Dynamic programming and fast matrix multiplication"	Zürich
2006	Michal Meyerovitch	Engineering and Applications Track: "Robust, generic and efficient construction of envelopes of surfaces in three-dimensional space"	Zürich
2005	Piotr Sankowski	"Shortest Paths in Matrix Multiplication Time"	Mallorca