Gödel Prize 2014 - Call for Nominations

The Call for Nominations for the 2014 Gödel Prize has been posted (pdf). Nominations for the award should be submittedto the Chair of the Award Committee, Giuseppe F. Italiano (goedelprize at gmail dot com). The deadline for nominations is: January 17, 2014.

More information


The EATCS Award 2014 - Call for Nominations

The Call for Nominations for the EATCS Award 2014 has been published (pdf). Nominations and supporting data should be sent to the chairman of the EATCS Award Committee, Leslie Ann Goldberg - This e-mail address is being protected from spambots. You need JavaScript enabled to view it . The next award will be presented during ICALP 2014 in Copenhagen, Denmark. The deadline for nominations is: December 31, 2013.

More information


The 2013 Principles of Distributed Computing Doctoral Dissertation Award

The abundance of excellent candidates made the choice very difficult. Even after narrowing the list down, the committee still decided to split the award between two winners, listed next alphabetically by last name.  Dr. Shiri Chechik completed her thesis ``Fault-tolerant structures in graphs'' in 2012 under the supervision of Prof. David Peleg at the Weizmann Institute of Science. Dr. Danupon Nanongkai completed his thesis ``Graphs and geometric algorithms on distributed networks and databases'' in 2011 under the supervision of Prof. Richard J. Lipton at the Georgia Institute of Technology.


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 at the Springer page http://www.springer.com/?SGWID=0-102-24-0-0&searchType=EASY_CDA&queryText=mogavero.

The thesis of the other winner from last year, Rossano Venturini, will be released soon.


2013 Edsger W. Dijkstra Prize in Distributed Computing

The Dijkstra Prize Committee has selected Nati Linial as the recipient of this year Edsger W. Dijkstra Prize in Distributed Computing. The prize is given to him for his outstanding paper: "Locality in distributed graph algorithms" published in SIAM Journal on Computing, 21(1992) 193-201.



17th European Joint Conferences on Theory And Practice of Software

Grenoble,  France

5-13 April 2014



EATCS-IPEC Nerode Prize 2013 - Laudatio

On the Exact Complexity of Evaluating Quantified k-CNF
Chris Calabro, Russell Impagliazzo, Ramamohan Paturi, Algorithmica 2013

The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs
Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan, Paturi, Journal of Computer and System Sciences 2008

On the Complexity of k-SAT
Russell Impagliazzo, Ramamohan Paturi, Journal of Computer and System Sciences 2001

Which Problems Have Strongly Exponential Complexity?

Russell Impagliazzo, Ramamohan Paturi, Francis Zane, Journal of Computer and System Sciences 2001

The Nerode Prize 2013 Committee, consisting of Georg Gottlob (University of Oxford, UK), Rolf Niedermeier (TU Berlin, Germany; chair), and Peter Widmayer (ETH Zurich, Switzerland), has unanimously decided to award Chris Calabro (Google Inc., Mountain View, USA), Russell Impagliazzo (UC San Diego, USA), Valentine Kabanets (Simon Fraser University, Canada), Ramamohan Paturi (UC San Diego, USA), and Francis Zane (Alcatel Lucent, Murray Hill, USA) the 2013 EATCS-IPEC Nerode Prize for outstanding papers in the area of multivariate algorithmics.
Their series of papers elaborates on what is known as the Exponential Time Hypothesis (ETH), and its stronger variant, the Strong Exponential Time Hypothesis (SETH). These complexity assumptions state lower bounds on how fast Boolean Satis ability problems can be solved. A key result of the corresponding theory is the Sparsi cation Lemma, a core tool in the area of developing relative lower bounds for NP-hard problems, which lends credence to the ETH. Altogether, the papers open an avenue for proving exponential lower bounds (assuming ETH or SETH) for a multitude of diverse computational problems, helping to derive tight parameterized computational complexity results. This has led to numerous recent advances in the eld of multivariate algorithmics, thus adding a central tool to the repertoire of worst-case complexity analysis. The obtained insights also have a strong impact on elds such as structural and communication complexity theory. The knowledge of the (S)ETH now belongs into the standard toolkit of every researcher in multivariate algorithmics.

<< Start < Prev 1 2 3 4 5 6 7 8 9 10 Next > End >>

Page 6 of 21

SAGT 2014

Patras, Greece

September 30-October 02, 2014



New BEATCS issue is out!

Number 113, June 2014, 243pp

EATCS YouTube channel

See videos from ICALP 2013 at

EATCS YouTube channel

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