Vote for Italian's Chapter Council Elections 2021

Vote HERE

Voting Procedure:

• The electronic election of new members will take place from December 14th at 00:00:00 CET until December 21st at 24:00:00 CET
• The members can vote up to 3 candidates.
• Only members of the Italian chapter can vote

Results of EATCS GA Elections 2021

The new elected members of the EATCS General Assembly are (in alphabetical order):

• Tiziana Calamoneri
• Thomas Colcombet
• Javier Esparza
• Fabrizio Grandoni
• Thore Husfeldt
• Emanuela Merelli (she is also in the Council via being the EATCS Board)
• Eva Rotenberg
• Jiri Sgall
• Alexandra Silva
• Jukka Suomela

EATCS-IPEC Nerode Prize 2021

The EATCS-IPEC Nerode Award Committee has selected the following paper as the recipient of the EATCS-IPEC Nerode Prize 2021:

• "Deciding Parity Games in Quasi-polynomial Time” by Cristian Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan. SIAM Journal of Computing, Special Issue dedicated to STOC 2017, pp. 152-188, published January 2020.

A parity game is played on an $n$-vertex directed graph $G = (V, E)$ with a function $f : V \mapsto \{1, \ldots, m\}$ of colors given to the vertices. Then two players $0$ and $1$ play a game, with $0$ moving first starting from a designated start node. The players alternate, moving from the current node to one of its neighbors. This defines a possibly infinite walk on the graph. Player $0$ wins if the largest color visited infinitely often is even, and player $1$ wins otherwise.

The computational complexity of the Parity Games problem of determining a winning strategy for the players for a given game with parameters $n$ and $m$ is a longstanding open problem in algorithmic game theory. The problem is important in many applications. Games played on finite graphs are deeply connected to $\mu$-calculus, various models of automata, computer aided verification, and the decidability of theories in various logics, the latter connection going back to B\"uchi.

The Parity Games problem is known to be in NP and co-NP and in UP and co-UP. Prior to this paper, the fastest algorithm for Parity Games (Jurdzinsky et. al. STACS 2000) ran in $O(n^{\sqrt n})$ time. The Nerode prize winning paper provided a {\em quasi-polynomial} running time of $O(n^{6+\log(m)})$, an impressive achievement. The paper also gave an FPT algorithm with respect to parameter $m$, with running time $O(n^5+2^{6m+m\log(n)})$; the previous best dependence on $m$ was $n^{\Theta(m)}$.

The deep techniques in this paper inspired a long series of further improvements on the complexity of Parity Games and related problems. The paper is a true gem in multivariate algorithmic game theory.

Presburger Award for Young Scientists 2022 - Call for Nominations

Deadline: 15 February 2022

The Presburger Award recognises outstanding contributions by a young scientist in theoretical computer science, documented by a published paper or a series of published papers. It is named after Mojzesz Presburger who accomplished his ground-breaking work on decidability of the theory of addition (known today as Presburger arithmetic) as a student in 1929. The award is conferred annually by the European Association for Theoretical Computer Science (EATCS) at the International Colloquium on Automata, Languages, and Programming (ICALP).

Call for nominations: EATCS Award 2022

EATCS Fellows 2022 - Call for Nominations

Deadline: December 31, 2021

• VERY IMPORTANT: all nominees and nominators must be EATCS Members 
• Proposals for Fellow consideration in 2021 should be submitted by DECEMBER 31st, 2021 by email to the EATCS Secretary ( This e-mail address is being protected from spambots. You need JavaScript enabled to view it ). The subject line of the email should read "EATCS Fellow Nomination - <surname of candidate>".