List of accepted papers

(In order of appearance)

• Invited Lectures
• Track A: Algorithms, Automata, Complexity and Games
• Track B: Logic, Semantics and Theory of Programming
• Track C: Security and Foundations of Cryptography

Invited lectures

Ushering in a New Era of Algorithm Design

Bernard Chazelle (Princeton University)

Advances in data acquisition technology, together with the imminent demise of Moore's Law, are prompting a rethink of basic algorithm design principles. Computing with massive data sets, data streaming, coping with uncertainty, priced computation, property testing, and sublinear algorithms are all parts of the story. So is the growing trend toward using algorithms as modeling tools for natural phenomena. I will discuss some of these developments; in particular, dimension reduction, sublinear algorithms, online reconstruction, and self-improving algorithms.

A "Proof-Reading" of some Issues in Cryptography

Ivan Damgård (University of Aarhus)

In this paper, we identify some issues in the interplay between practice and theory in cryptography, issues that have repeatedly appeared in different incarnations over the years. These issues are related to fundamental concepts in the field, e.g., to what extent we can prove that a system is secure and what theoretic results on security mean for practical applications. We argue that several such issues are often overlooked or misunderstood, and that it may be very productive if both theoreticians and practitioners think more consciously about these issues and act accordingly.

Credentials-Based Authorization: Evaluation and Implementation

Fred B. Schneider (Cornell University)

 

Subexponential Parameterized Algorithms

Frederic Dorn (University of Bergen)

Fedor V. Fomin (University of Bergen)

Dimitrios M. Thilikos (University of Athens)

We present a series of techniques for the design of subexponential parameterized algorithms for graph problems. The design of such algorithms usually consists of two main steps: first find a branch- (or tree-) decomposition of the input graph whose width is bounded by a sublinear function of the parameter and, second, use this decomposition to solve the problem in time that is single exponential to this bound. The main tool for the first step is Bidimensionality Theory. Here we present the potential, but also the boundaries, of this theory. For the second step, we describe recent techniques, associating the analysis of sub-exponential algorithms to combinatorial bounds related to Catalan numbers. As a result, we have 2^O(√k) ∙ n^O(1) time algorithms for a wide variety of parameterized problems on graphs, where n is the size of the graph and k is the parameter.

The Algebraic Theory of Effects

Gordon Plotkin (University of Edinburgh)

 

Highly Efficient Secrecy-Preserving Proofs of Correctness of Computations, and Applications

Michael O. Rabin (Harvard University)

Rocco A. Servedio (Columbia University)

Christopher Thorpe (Harvard University)

We present a highly efficient method for proving correctness of computations while preserving secrecy of the input values. This is done in an Evaluator-Prover model which can also be realized by a secure processor. We describe an application to secure auctions.