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.

Read more...
 

FIRST CALL FOR PAPERS: ETAPS 2014

17th European Joint Conferences on Theory And Practice of Software

Grenoble,  France

5-13 April 2014

http://www.etaps.org/2014

Read more...
 

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.

 

Gödel Prize - 2013

The 2013 Gödel Prize for outstanding journal articles in theoretical computer science is awarded to:

Antoine Joux: A One Round Protocol for Tripartite Diffie-Hellman, J. Cryptology 17(4): 263-276 (2004). (Conference version: ANTS 2000)

and

Dan Boneh, Matthew K. Franklin: Identity-Based Encryption from the Weil Pairing, SIAM J. Comput. 32(3): 586-615 (2003) . (Conference version: CRYPTO 2001)

Read more...
 

SECOND CFP: DISC 2013 - the 27th International Symposium on Distributed Computing - Jerusalem, Israel

SECOND CALL FOR PAPERS

Read more...
 

EATCS - IPEC Nerode Prize 2013

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.

Laudatio

More information

 

EATCS Best Paper Award at ETAPS 2013

The reciepent of the EATCS Best Paper Award in Theoretical Computer Science at the European Joint Conferences on Theory and Practice of Software 2013, ETAPS'13, has been chosen. It is the "Logical Foundations of Secure Resource Management in Protocol Implementations" by Michele Bugliesi, Stefano Calzavara, Fabienne Eigner and Matteo Maffei.

More information

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

Page 6 of 20

ESA 2014

Wrocław, Poland

September 08-12, 2014

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.