Monday
Tuesday
Wednesday
Thursday
Friday
Workshops
| 09:00 | Game Semantics: Achievements and Prospects
Samson Abramsky |
|
|---|---|---|
| 10:00 | Clique is hard to approximate within n^(1-o(1))
Lars Engebretsen, Jonas Holmerin |
Closed Types as a Simple Approach to Safe
Imperative Multi-Stage Program
Cristiano Calcagno, Eugenio Moggi, Walid Taha |
| 10:25 | Approximating the independence number and
the chromatic number in expected polynomial time
Michael Krivelevich, Van Vu |
A Statically Allocated Parallel Functional
Language
Alan Mycroft, Richard Sharp |
| 10:50 | Coffee break | |
| 11:10 | An Optimal Minimum Spanning Tree Algorithm
Seth Pettie, Vijaya Ramachandran |
Lax Logical Relations
Gordon Plotkin, John Power, Donald Sannella, Robert Tennent |
| 11:35 | Improved shortest paths on the word RAM
Torben Hagerup |
Reasoning about Idealized Algol Using Regular
Languages
Dan R. Ghica, Guy McCusker |
| 12:00 | Improved algorithms for finding level ancestors
in dynamic trees
Stephen Alstrup, Jacob Holm |
The measurement process in domain theory
Keye Martin |
| 12:30 | Lunch | |
| 14:30 | Graph Transformation as Unifying Formal Framework for
System Modeling and Model Evolution
Gregor Engels |
|
| 15:30 | Monotone Proofs of the Pigeon Hole Principle
Albert Atserias, Nicola Galesi, Ricard Gavalda |
Fully-abstract Statecharts Semantics via
Intuitionistic Kripke Structures
Gerald Lüttgen, Michael Mendler |
| 15:55 | Homogenization and the Polynomial Calculus
Josh Buresh-Oppenheim, Matt Clegg, Russell Impagliazzo, Toniann Pitassi |
Algebraic Models for Contextual Nets
Roberto Bruni, Vladimiro Sassone |
| 16:20 | Coffee break | |
| 16:40 | Asymptotically optimal bounds for OBDDs and
the solution of some basic OBDD problems
Beate Bollig, Ingo Wegener |
LTL is expressively complete for Mazurkiewicz
traces
Volker Diekert, Paul Gastin |
| 17:05 | Measures of Nondeterminism in Finite Automata
Juraj Hromkovic, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert |
An automata-theoretic completeness proof
for Interval Temporal Logic
B. C. Moszkowski |
| 18:00 | Welcome reception | |
| 09:00 | Which NP-hard optimization problems admit non-trivial
efficient approximation algorithms?
Johan Hastad |
|
|---|---|---|
| 10:00 | Deterministic algorithms for k-SAT
based on covering codes and local search
Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Schöning |
Variable Independence, Quantifier Elimination,
and Constraint Representations
Leonid Libkin |
| 10:25 | Closest Vectors, Successive Minima and Dual
HKZ-Bases of Lattices
Johannes Blömer |
Constraint Satisfaction Problems and Finite
Algebras
Andrei Bulatov, Andrei Krokhin, Peter Jeavons |
| 10:50 | Coffee break | |
| 11:10 | An optimal online algorithm for bounded space
variable-sized bin packing
Steven S. Seiden |
Efficient Verification Algorithms for One-Counter
Processes
Antonin Kucera |
| 11:35 | Resource augmentation for online bounded
space bin packing
János Csirik, Gerhard Woeginger |
On the Complexity of Bisimulation Problems
for Basic Parallel Processes
Richard Mayr |
| 12:00 | Optimal projective algorithms for the list
update problem
Christoph Ambühl, Bernd Gärtner, Bernhard von Stengel |
Decidable first-order transition logics for
PA-processes
D. Lugiez, Ph. Schnoebelen |
| 12:30 | Lunch | |
| 14:30 | Non Interference for Analysis of Cryptographic Protocols
Roberto Gorrieri |
|
| 15:30 | Average bit-complexity of Euclidean algorithms
Ali Akhavi, Brigitte Vallée |
Analysing Input Output Capabilities of Mobile
Processes with a Generic Type System
Barbara König |
| 15:55 | Planar maps and Airy phenomena
Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, Michèle Soria |
Information Flow vs. Resource Access in the
Information Asynchronous Pi-Calculus
Matthew Hennessy, James Riely |
| 16:20 | Coffee break | |
| 16:40 | Award talk
The Genomics Revolution and its Challenges for Algorithmic Research Richard Karp |
|
| 17:40 | EATCS General Assembly
wine and cheese |
|
| 09:00 | Alternating Verification Diagrams
Zohar Manna |
|
|---|---|---|
| 10:00 | Necessary and sufficient assumptions for
non interactive zero knowledge proofs of knowledge for all NP relations
Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano |
A New Unfolding Approach to LTL Model Checking
Javier Esparza, Keijo Heljanko |
| 10:25 | Computational PCP: Short one-round proofs
for NP
W. Aiello, S. Bhatt, R. Ostrovsky, S. Rajagopalan |
Reasoning about message passing in finite
state environments
B. Meenakshi, R. Ramanujam |
| 10:50 | Coffee break | |
| 11:10 | Extended notions of security for multicast
public key cryptosystems
Olivier Baudron, David Pointcheval, Jacques Stern |
On the centralizer of a finite set
Juhani Karhumäki, Ion Petre |
| 11:35 | One-round secure computation and secure autonomous
mobile agents
Christian Cachin, Jan Camenisch, Joe Kilian, Joy Müller |
On the power of tree-walking automata
Frank Neven, Thomas Schwentick |
| 12:00 | Round-optimal and abuse free multi-party
contract signing
Birgit Baum-Waidner, Michael Waidner |
Determinization of transducers over infinite
words
Marie-Pierre Béal, Olivier Carton |
| 12:30 | Lunch | |
| 14:30 | City Tour and Excursion | |
| 09:00 | Graph Algorithms and Constraint Programming
Kurt Mehlhorn |
|
|---|---|---|
| 10:00 | Scalable secure storage when half the system
is faulty
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern |
Revisiting the correspondence between cut
elimination and normalisation
José Espirito Santo |
| 10:25 | Dual-bounded hypergraphs: Generating partial
and multiple transversals
Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino |
Negation Elimination from Simple Equational
Formulae
Reinhard Pichler |
| 10:50 | Coffee break | |
| 11:10 | Hardness of set cover with intersection 1
V.S. Anil Kumar, Sunil Arya, H. Ramesh |
Infinite series parallel posets: logic and
languages
Dietrich Kuske |
| 11:35 | Strong inapproximability of the basic k-Spanner
Problem
Michael Elkin, David Peleg |
On deciding if deterministic Rabin language
is in Buchi class
Tomasz Fryderyk Urbanski |
| 12:00 |
|
On Message Sequence Graphs and Finitely Generated
Regular MSC Languages
Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar, P.S. Thiagarajan |
| 12:30 | Lunch | |
| 14:30 | Pseudorandomness
Oded Goldreich |
|
| 15:30 | A bound on the capacity of backoff and acknowledgement
based protocols
Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson |
A Finite w-complete Equational Specification
of Interleaving
Wan Fokkink, Bas Luttik |
| 15:55 | Deterministic radio broadcasting
Bogdan Chlebus, Leszek Gasieniec, Anna Östlin, John Michael Robson |
A Complete Axiomatization for Observational
Congruence of Prioritized Finite-State Behaviors
Mario Bravetti, Roberto Gorrieri |
| 16:20 | Coffee break | |
| 16:40 | Tight size bounds for packet headers in narrow
meshes
Micah Adler, Faith Fich, Leslie Ann Goldberg, Mike Paterson |
On the logical characterisation of performability
properties
Christel Baier, Boudewijn Haverkort, Holger Hermanns, Joost-Pieter Katoen |
| 17:05 | Wavelength assignment problem on all-optical
networks with k fibres per link
Luciano Margara, Janos Simon |
On the Representation of Timed Polyhedra
Olivier Bournez, Oded Maler |
| 20:00 | Conference Dinner | |
| 09:00 | Min-wise Independent Permutations: Theory and Practice
Andrei Broder |
|
|---|---|---|
| 10:00 | Testing acyclicity of directed graphs in
sublinear time
Michael Bender, Dana Ron |
Lower bounds are not easier over the reals:
inside PH
Hervé Fournier, Pascal Koiran |
| 10:25 | Computing the girth of a planar graph
Hristo N. Djidjev |
Unlearning helps
Ganesh Baliga, John Case, Wolfgang Merkle, Frank Stephan |
| 10:50 | Coffee break | |
| 11:10 | Fast approximation schemes Euclidean multiconnectivity
problems
Artur Czumaj, Andrzej Lingas |
The many faces of a translation
Pierre McKenzie, Thomas Schwentick Denis Thérien, Heribert Vollmer |
| 11:35 | Approximate TSP in graphs with forbidden
minors
Michelangelo Grigni |
Gales and the constructive dimension of individual
sequences
Jack Lutz |
| 12:00 | Polynomial time approximation schemes for
general multiprocessor job shop scheduling
Klaus Jansen and Lorant Porkolab |
The global power of additional queries to
p-random oracles
Wolfgang Merkle |
| 12:30 | Lunch | |
| July 7-8 | Workshop on Theoretical Foundations of Security Analysis and Design | |
|---|---|---|
| July 14 | Workshop on Randomization and Approximation Techniques in Computer Science | |
| July 14 | Workshop on Boolean Functions and Applications | |
| July 15 | Workshop on Approximation and Randomization in Communication Networks | |
| July 15 | Workshop on Intersection Types and Related Systems | |
| July 15 | Workshop on Graph Transformation and Visual Modeling Techniques | |
| July 15 | Workshop on Process Algebra and Performance Models | |
| Main |
| List of Accepted Papers |
| Program |
| Summary Program |
| Registration |
| Practical Information |
| Workshops |
| Special Award |
| Invited Speakers |
| Awards |
| Organizing Committee |
| Call for Papers |