
List of accepted papers
(In order of appearance)
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 selfimproving
algorithms.
 A "ProofReading" 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.
 CredentialsBased 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 subexponential 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 SecrecyPreserving 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 EvaluatorProver model which can also be realized by a
secure processor. We describe an application to secure auctions.

