Monday, September 30, 2013

Saturday, September 28, 2013

ERC Advanced Grants to TCS researchers

A couple of days ago, the ERC announced that, in its sixth and last Advanced  Grant competition under the EU's Seventh Research Framework Programme, it is awarding over €660 million to 284 senior research leaders. TCS folks will be happy to hear that the following colleagues of ours have been awarded ERC Advanced Grants:
  • Monika Henzinger. Challenges in Graph Algorithms with Applications.
  • Rachid Guerraoui. Adversary-Oriented Computing.
  • Pavel Pudlak. Feasibility, logic and randomness in computational complexity.
  • Jean-Daniel Boissonnat. Algorithmic Foundations of Geometry Understanding in Higher Dimensions.
  • David Pointcheval. Cryptography for the Cloud.
  • Nello Cristianini. Patterns in Big Data: Methods, Applications and Implications
  • Leslie Ann Goldberg. Mapping the Complexity of Counting.
Congratulations to the award recipients! I am sure that, with the support of the ERC, they will advance the state of the art in their respective fields of interest, benefiting TCS as a whole.

Addendum: As kindly pointed out by anonymous commenters, I have failed to mention that Nati Linial received an ERC Advanced Grant for the project High-dimensional combinatorics and that Lex Schrijver got one for Applying Fundamental Mathematics in Discrete Mathematics, Optimization, and Algorithmics. These two grants are in the field of mathematics, as is the one awarded to Saharon Shelah for the project Model theory and its applications: dependent classes.

Friday, September 20, 2013

Call for Nominations for the Presburger Award 2014

Presburger Award for Young Scientists 2014 
Deadline: December 31st, 2013

Starting in 2010, the European Association for Theoretical Computer Science (EATCS) established the Presburger Award. The Award is conferred annually at the International Colloquium on Automata, Languages and Programming (ICALP) to a young scientist (in exceptional cases to several young scientists) for outstanding contributions in theoretical computer science, documented by a published paper or a series of published papers. The Award is named after Mojzesz Presburger who accomplished his path-breaking work on decidability of the theory of addition (which today is called Presburger arithmetic) as a student in 1929.

Nominations for the Presburger Award can be submitted by any member or group of members of the theoretical computer science community except the nominee and his/her advisors for the master thesis and the doctoral dissertation. Nominated scientists have to be at most 35 years at the time of the deadline of nomination (i.e., for the Presburger Award of 2014 the date of birth should be in 1978 or later).

The Presburger Award Committee of 2014 consists of Antonin Kucera (Brno, chair), Claire Mathieu (Paris), and Peter Widmayer (Zurich). Nominations, consisting of a two page justification and (links to) the respective papers, as well as additional supporting letters, should be sent by e-mail to:

Antonin Kucera

The subject line of every nomination should start with "Presburger Award 2014", and the message must be received before December 31st, 2013.

The award includes an amount of 1000 Euro and an invitation to ICALP 2014 for a lecture. The Presburger Award is sponsored by CWI, Centrum Wiskunde & Informatica.

Previous Winners:
  • Mikolaj Bojanczyk, 2010 
  • Patricia Bouyer-Decitre, 2011 
  • Venkatesan Guruswami and Mihai Patrascu, 2012 
  • Erik Demaine, 2013 
Official website:

Thursday, September 19, 2013

Call for nominations: EATCS Fellows

At its meeting at ICALP 2013 in Riga, the EATCS Council decided to start an EATCS Fellows Programme. The first call for nominations is appended.

I hope that EATCS members will submit strong nominations for consideration by the first EATCS Fellow-Selection Committee, which is chaired by Anca Muscholl. The deadline for nominations is December 31. The EATCS fellows will be announced at ICALP 2014 in Copenhagen.

Please note: all nominees and nominators must be EATCS Members

Submit by December 31 of the current year for Fellow consideration by
email to the EATCS Secretary ( The subject line
of the email should read "EATCS Fellow Nomination - ".


The EATCS Fellows Program is established by the Association to
recognize outstanding EATCS Members for their scientific achievements
in the field of Theoretical Computer Science. The Fellow status is
conferred by the EATCS Fellows-Selection Committee upon a person
having a track record of intellectual and organizational leadership
within the EATCS community.  Fellows are expected to be “model
citizens” of the TCS community, helping to develop the standing of TCS
beyond the frontiers of the community.

In order to be considered by the EATCS Fellows-Selection Committee,
candidates must be nominated by at least four EATCS Members.  
Please verify your membership at

The EATCS Fellows-Selection Committee consists of 

- Rocco De Nicola (IMT Lucca, Italy) 
- Paul Goldberg (Oxford, UK)
- Anca Muscholl (Bordeaux, France, chair)
- Dorothea Wagner (Karlsruhe, Germany)
- Roger Wattenhofer (ETH Zurich, CH)


A nomination should consist of answers to the questions below. It can
be co-signed by several EATCS members. At least two nomination letters 
per candidate are recommended. If you are supporting the
nomination from within the candidate's field of
expertise, it is expected that you will be specific about the
individual's technical contributions.

To be considered, nominations for 2014 must be received by December 31, 2013.

1. Name of candidate
Candidate's current affiliation and position
Candidate's email address, postal address and phone number
Nominator(s) relationship to the candidate

2. Short summary of candidate's accomplishments (citation -- 25 words or less)

3. Candidate's accomplishments: Identify the most important
contributions that qualify the candidate for the rank of EATCS Fellow
according to the following two categories: 

A) Technical achievements
B) Outstanding service to the TCS community

Please limit your comments to at most three pages.

4. Nominator(s):
Affiliation(s), email and postal address(es), phone number(s)

Sunday, September 15, 2013

Gödel Prize 2014: Call for Nominations

I should be grateful if you could help disseminate this call for nominations. Feel free to post it on your blogs, send it to your collaborators and your department members, and post it on social networks. 

The Gödel Prize 2014
Call for Nominations

Deadline: January 17, 2014.

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 Association for Computing Machinery, Special Interest Group on Algorithms and Computation Theory (ACM-SIGACT). The award is presented annually, with the presentation taking place alternately at the International Colloquium on Automata, Languages, and Programming (ICALP) and the ACM Symposium on Theory of Computing (STOC). The 22nd Gödel Prize will be awarded at the 41st ICALP in Copenhagen in July 2014.

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 von Neumann’s death, in what has become the famous “P versus NP” question. The Prize includes an award of USD 5000.

Award Committee: The winner of the Prize is selected by a committee of six members. The EATCS President and the SIGACT Chair each appoint three members to the committee, to serve staggered three-year terms. The committee is chaired alternately by representatives of EATCS and SIGACT. The 2014 Award Committee consists of Krzysztof Apt (CWI Amsterdam), Giuseppe F. Italiano (Università di Roma Tor Vergata), Joseph Mitchell (State University of New York at Stony Brook), Andrew Pitts (University of Cambridge), Daniel Spielman (Yale
University), and Éva Tardos (Cornell University).

Eligibility: The rules for the 2014 Prize are given below and they supersede any different interpretation of the generic rule to be found on websites of both SIGACT and EATCS. Any research paper or series of papers by a single author or by a team of authors is deemed eligible if
  1. the paper was published in a recognized refereed journal no later than December 31, 2013;
  2. the main results were not published (in either preliminary or final form) in a journal or conference proceedings before January 1st, 2001.
The research work nominated for the award should be in the area of theoretical computer science. The term “theoretical computer science” is meant to encompass, but is not restricted to, research areas covered by ICALP and STOC. Nominations are encouraged from the broadest spectrum of the theoretical computer science community so as to ensure that potential award winning papers are not overlooked. The Award Committee shall have the ultimate authority to decide whether a particular paper is eligible for the Prize.

Nominations: Nominations for the award should be submitted by email to the Award Committee Chair Giuseppe F. Italiano: goedelprize at gmail dot com

Please make sure that the Subject line of all nominations and related messages begin with Goedel Prize 2014. To be considered, nominations for the 2014 Prize must be received by January 17, 2014.

Any member of the scientific community can make nominations. The Award Committee may actively solicit nominations. A nomination should contain a brief summary of the technical content of the paper(s) and a brief explanation of its significance. A printable copy of the research paper or papers should accompany the nomination. The nomination must state the date and venue of the first conference or workshop publication or state that no such publication has
occurred. The work may be in any language. However, if it is not in English, a more extended summary written in English should be enclosed. To be considered for the award, the paper or series of papers must be recommended by at least two individuals, either in the form of two distinct nominations or one nomination including recommendations from two different people. Additional recommendations may also be enclosed and are generally useful. The Award
Committee encourages recommendation and support letters to be mailed separately, without being necessarily shared with the nominator(s). The rest of the nomination package should be sent in a single email whenever possible. Those intending to submit a nomination should contact the Award Committee Chair by email well in advance. The Chair will answer questions about eligibility, encourage coordination among different nominators for the same paper(s), and also accept informal proposals of potential nominees or tentative offers to prepare formal nominations. The committee maintains a database of past nominations for eligible papers, but fresh nominations for the same papers (especially if they highlight new evidence of impact) are always welcome.

Selection Process: The Award Committee is free to use any other sources of information in addition to the ones mentioned above. It may split the award among multiple papers or declare no winner at all. All matters relating to the selection process left unspecified in this document are left to the discretion of the Award Committee.

Monday, September 09, 2013

EATCS Award 2014: Call for Nominations

The European Association for Theoretical Computer Science (EATCS) annually honours a respected scientist from our community with the prestigious EATCS Distinguished Achievement Award. The award is given to acknowledge extensive and widely recognized contributions to theoretical computer science over a life long scientific career.

For the EATCS Award 2014, candidates may be nominated to the Award Committee consisting of
  • Leslie Ann Goldberg (University of Oxford)
  • Kim Guldstrand Larsen (Aalborg University)
  • Vladimiro Sassone (University of Southampton)
The deadline for nominations is December 31, 2013. Nominations will be kept strictly confidential. They should include supporting justification and be sent by e-mail to the chair of the EATCS Award Committee:

Leslie Ann Goldberg,
Department of Computer Science,
University of Oxford,
Wolfson Bldg, Parks Rd,
Oxford OX1 3QD United Kingdom

The list of previous recipients of the EATCS Award may be found at

The next award will be presented during ICALP 2014, which will be held in the period 7-11 July 2014 in Copenhagen,

Friday, September 06, 2013

Preliminary call for papers for ICALP 2014

The preliminary call for papers for ICALP 2014 is available here. (Warning: it is 19 MB, so don't be surprised if it takes some time to download it.) In case, you do not want to download the file, here is the most relevant information. (In the light of a suggestion in one of the comments to this post, I copy-pasted the whole preliminary CFP below.)

Conference dates: 7-11 July 2014
Submission deadline: 14 Feb. 2014
Notification date: 11 Apr. 2014
Final version due: 28 Apr. 2014
Location: IT University Copenhagen

The PC chairs are Elias Koutsopias (Track A), Javier Esparza (Track B) and Pierre Fraigniaud (Track C).

The invited speakers are
I hope that you will submit your best work to the conference. There will be a lot going on in Copenhagen in early late June-early July, both scientifically (SEA 2014, SWAT 2014 and ICALP 2014 will all take place one after the other) and culturally.

------------------------ FULL PRELIMINARY CFP -------------

ICALP 2014
7 July – 11 July 2014
IT University of Copenhagen
Preliminary Call for Papers

Invited speakers:
Sanjeev Arora • Maurice Herlihy • Viktor Kuncak • Claire Mathieu


Track A
Elias Koutsoupias (chair) • Dimitris Achlioptas • Pankaj Agrawal • Nikhil Bansal •
Gerth Stølting Brodal • Jean Cardinal • Ning Chen • Giorgos Christodoulou • Xiaotie Deng • Ilias Diakonikolas • Chaled Elbassioni • Amos Fiat • Leslie Goldberg • Vipul Goyal • Giuseppe Italiano • Marcin Kaminsky • Haim Kaplan • Ioardanis Kerenidis • Anna Karlin • Robert Krauthgamer • James Lee • Ashwin Nayak • Jared Saia • Piotr Sankowski • Maria Serna • Christian Sohler • Ryan Williams

Track B
Javier Esparza (chair) • Paolo Baldan • Michele Boreale • Tomas Brazdil • Véronique Bruyère • Veronique Cortier • Anuj Dawar • Kousha Etessami • Maribel Fernandez • David Frutos Escrig • Pierre Ganty • Peter Habermehl • Manfred Kufleitner • Slawomir Lasota • Oded Maler • Sebastian Maneth • Madhavan Mukund • JensPalsberg • Thomas Schwentick • Sonja Smets • Jiri Srba • Steve Zdancewic

Track C
Pierre Fraigniaud (chair) • Keren Censor-Hillel • Andrea Clementi • Benjamin Doerr • Panagiota Fatourou • Michal Feldman • Antonio Fernández Anta • Leszek Gasieniec • Phillip B. Gibbons • Magnus Halldorsson • Robert Kleinberg • Anne‑Marie Kermarrec• Michal Koucky • Gopal Pandurangan • Boaz Patt-Shamir • Andrea Pietracaprina • Andrea Richa • Luís Rodrigues • Christian Scheideler  •  Jukka Suomela • Philipp Woelfel

Thore Husfeldt (chair),

Important dates

Submission deadline: Friday, 14 February 2014
Author notification: Friday, 11 April 2014
Final manuscript due: Monday, 28 April 201

Tuesday, September 03, 2013

Publication of the best Italian PhD theses in TCS

The Italian Chapter of the EATCS has reached an agreement with Atlantis Press (an imprint of Springer) for the publication of the best Italian PhD theses in TCS in a  special series. Fabio Mogavero's thesis, awarded last year, is the first volume published under this agreement and can be found here The thesis of the other winner from last year, Rossano Venturini, will be released soon.

Jacopo Mauro and Alessandra Scafuro are the two recipients of the Best Italian Ph.D. Thesis in Theoretical Computer Science Award 2013, and their theses will appear in the above-mentioned series in due course.

Congratulations to the above-mentioned young researchers!