Sunday July 9th

Registration Opens Late Afternoon

Monday, July 10th
 
 

9:00 - 10:00 

INVITED TALK
Game Semantics: Achievements and Prospects 
Samson Abramsky

10:00  - 10:50

SESSION 1
 

Clique is hard to approximate within n*(1-o(1))
Lars Engebretsen, Jonas Holmerin

Approximating the independence number and the chromatic number  in expected polynomial time
Michael Krivelevich, Van Vu
 
 

10:00  - 10:50

SESSION 2
 

Closed Types as a Simple Approach to Safe Imperative Multi-Stage Program
Cristiano Calcagno, Eugenio Moggi, Walid Taha

A Statically Allocated Parallel Functional Language
Alan Mycroft, Richard Sharp
 

(Coffee Break 10:50 - 11:10)

11:10 - 12:25

SESSION 1
 

An Optimal Minimum Spanning Tree Algorithm
Seth Pettie, Vijaya Ramachandran

Improved shortest paths on the word RAM
Torben Hagerup

Improved algorithms for finding level ancestors in dynamic trees
Stephen Alstrup, Jacob Holm
 

11:10 - 12:25

SESSION 2
 

Lax Logical Relations
Gordon Plotkin, John Power, Donald Sannella, Robert Tennent

Reasoning about Idealized Algol Using Regular Languages
Dan R. Ghica, Guy McCusker

The measurement process in domain theory
Keye Martin

(Lunch  12:30 - 14:30)

14:30  - 15:30 

INVITED TALK
Graph Transformation as Unifying Formal Framework for System Modeling and Model Evolution
Gregor Engels

15:30  - 16:20

SESSION 1
 

Monotone Proofs of the Pigeon Hole Principle
Albert Atserias, Nicola Galesi, Ricard Gavalda

Homogenization and the Polynomial Calculus
Josh Buresh-Oppenheim, Matt Clegg, Russell Impagliazzo, Toniann Pitassi
 
 

15:30  - 16:20

SESSION 2
 

Fully-abstract Statecharts Semantics via Intuitionistic Kripke Structures 
Gerald Lüttgen, Michael Mendler

Algebraic Models for Contextual Nets
Roberto Bruni, Vladimiro Sassone
 

(Coffee Break 16:20 - 16:40)

16:40 - 17:30

SESSION 1
 

Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
Beate Bollig, Ingo Wegener

Measures of Nondeterminism in Finite Automata
Juraj Hromkovic, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert
 
 

16:40 - 17:30

SESSION 2
 

LTL is expressively complete for Mazurkiewicz traces
Volker Diekert, Paul Gastin

An automata-theoretic completeness proof for Interval Temporal Logic
B. C. Moszkowski
 
 

(Welcome reception  18:00)

Tuesday,  July 11th

9:00  - 10:00 

INVITED TALK
Which NP-hard optimization problems admit non-trivial efficient approximation algorithms?
Johan Haastad

10:00  - 10:50

SESSION 1
 

Deterministic algorithms for k-SAT based on covering codes and local search
Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Schöning

Closest Vectors, Successive Minima and Dual HKZ-Bases of Lattices
Johannes Blömer
 
 

---

10:00  - 10:50

SESSION 2
 

Variable Independence, Quantifier Elimination, and Constraint Representations
Leonid Libkin

Constraint Satisfaction Problems and Finite Algebras
Andrei Bulatov, Andrei Krokhin, Peter Jeavons
 

---

(Coffee Break 10:50 - 11:10)

---

11:10 - 12:25

SESSION 1
 

An optimal online algorithm for bounded space variable-sized bin packing
Steven S. Seiden

Resource augmentation for  online bounded space  bin packing
János Csirik, Gerhard Woeginger

Optimal projective algorithms for the list update problem
Christoph Ambühl, Bernd Gärtner, Bernhard von Stengel
 

---

11:10 - 12:25

SESSION 2
 

Efficient Verification Algorithms for One-Counter Processes
Antonin Kucera

On the Complexity of Bisimulation Problems for Basic Parallel Processes
Richard Mayr

Decidable first-order transition logics for PA-processes
D. Lugiez, Ph. Schnoebelen

---

(Lunch  12:30 - 14:30)

---

 
 

14:30  - 15:30 

INVITED TALK
Non Interference for Analysis of Cryptographic Protocols
Roberto Gorrieri

15:30  - 16:20

SESSION 1
 

Average bit-complexity of Euclidean algorithms
Ali Akhavi, Brigitte Vallée

Planar maps and Airy phenomena
Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, Michèle Soria
 
 

---

15:30  - 16:20

SESSION 2
 

Analysing Input Output Capabilities of Mobile Processes with a Generic Type System
Barbara König

Information Flow vs. Resource Access in the Information Asynchronous Pi-Calculus
Matthew Hennessy, James Riely
 

---

(Coffee Break 16:20 - 16:40)

---

16:40 - 17:40

AWARD TALK

The Genomics Revolution and its Challenges for Algorithmic Research
Richard Karp

---

17:40 

EATCS General Assembly

(Wine and cheese )

top

---

Wednesday,  July 12th
 
 

9:00  - 10:00 

INVITED TALK
Alterating Verification Diagrams 
Zohar Manna

10:00  - 10:50

SESSION 1
 

Necessary and sufficient assumptions for non interactive zero knowledge proofs of knowledge for all NP relations
Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano

Computational PCP: Short one-round proofs for NP
W. Aiello, S. Bhatt, R. Ostrovsky, S. Rajagopalan
 
 

---

10:00  - 10:50

SESSION 2
 

A New Unfolding Approach to LTL Model Checking
Javier Esparza, Keijo Heljanko

Reasoning about message passing in finite state environments
B. Meenakshi, R. Ramanujam
 

---

(Coffee Break 10:50 - 11:10)

---

11:10 - 12:25

SESSION 1
 

Extended notions of security for multicast public key cryptosystems
Olivier Baudron, David Pointcheval, Jacques Stern

One-round secure computation and secure autonomous mobile agents
Christian Cachin, Jan Camenisch, Joe Kilian, Joy Müller

Round-optimal and abuse free multi-party contract signing
Birgit Baum-Waidner, Michael Waidner
 

---

11:10 - 12:25

SESSION 2
 

On the centralizer of a finite set
Juhani Karhumäki, Ion Petre

On the power of tree-walking automata
Frank Neven, Thomas Schwentick

Determinization of transducers over infinite words
Marie-Pierre Béal, Olivier Carton

---

(Lunch  12:30 - 14:30)

---

 
(City Tours and Excursion 14:30)

top

---

Thursday, July 13th
 
 
 

9:00  - 10:00 

INVITED TALK
Graph Algorithms and Constraint Programming
Kurt Mehlhorn

10:00  - 10:50

SESSION 1
 

Scalable secure storage when half the system is faulty
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern

Dual-bounded hypergraphs: Generating partial and multiple transversals
Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino
 
 

---

10:00  - 10:50

SESSION 2
 

Revisiting the correspondence between cut elimination and normalisation
José Espirito Santo

Negation Elimination from Simple Equational Formulae
Reinhard Pichler
 

---

(Coffee Break 10:50 - 11:10)

---

11:10 - 12:25

SESSION 1
 

Hardness of set cover with intersection 1
V.S. Anil Kumar, Sunil Arya, H. Ramesh

Strong inapproximability of the basic k-Spanner Problem
Michael Elkin, David Peleg
 
 
 

---

11:10 - 12:25

SESSION 2
 

Infinite series parallel posets: logic and languages
Dietrich Kuske

On deciding if deterministic Rabin language is in Buchi  class
Tomasz Fryderyk Urbanski

On Message Sequence Graphs and  Finitely Generated Regular MSC Languages
Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar, P.S. Thiagarajan

---

(Lunch  12:30 - 14:30)

---

 
 

14:30  - 15:30 

INVITED TALK
Pseudorandomness
Oded Goldreich

15:30  - 16:20

SESSION 1
 

A bound on the capacity of backoff and acknowledgement based protocols
Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson

Deterministic radio broadcasting
Bogdan Chlebus, Leszek Gasieniec, Anna Östlin, John Michael Robson
 
 

---

15:30  - 16:20

SESSION 2
 

A Finite w-complete Equational Specification of Interleaving
Wan Fokkink, Bas Luttik

A Complete Axiomatization for Observational Congruence of Prioritized Finite-State Behaviors
Mario Bravetti, Roberto Gorrieri
 

---

(Coffee Break 16:20 - 16:40)

---

16:40 - 17:30

SESSION 1
 

Tight size bounds for packet headers in narrow meshes
Micah Adler, Faith Fich, Leslie Ann Goldberg, Mike Paterson

Wavelength assignment problem on all-optical networks with k fibres per link
Luciano Margara, Janos Simon
 
 

---

16:40 - 17:30

SESSION 2
 

On the logical characterisation of performability properties
Christel Baier, Boudewijn Haverkort, Holger Hermanns, Joost-Pieter Katoen

On the Representation of Timed Polyhedra
Olivier Bournez, Oded Maler
 
 

---

(Conference dinner  20:00)

---

 

Friday July 14th
 
 

9:00  - 10:00 

INVITED TALK
Min-wise Independent Permutations: Theory and Practice
Andrei Broder

10:00  - 10:50

SESSION 1
 

Testing acyclicity of directed graphs in sublinear time
Michael Bender, Dana Ron

Computing the girth of a planar graph
Hristo N. Djidjev
 
 

10:00  - 10:50

SESSION 2
 

Lower bounds are not easier over the reals: inside PH
Hervé Fournier, Pascal Koiran

Unlearning helps
Ganesh Baliga, John Case, Wolfgang Merkle, Frank Stephan

(Coffee Break 10:50 - 11:10)

11:10 - 12:25

SESSION 1
 

Fast approximation schemes for Euclidean multiconnectivity problems
Artur Czumaj, Andrzej Lingas

Approximate TSP in graphs with forbidden minors
Michelangelo Grigni

Polynomial time approximation schemes for general multiprocessor job shop scheduling
Klaus Jansen and Lorant Porkolab
 

11:10 - 12:25

SESSION 2
 

The many faces of a translation
Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer

Gales and the constructive dimension of individual sequences
Jack Lutz

The global power of additional queries to p-random oracles
Wolfgang Merkle

(Lunch  12:30 - 14:30)

WORKSHOPS START AT 14:30
(* See individual workshop programs for schedule details.)