Front matter
731
Hyper-Encryption and Everlasting Security
Extended Abstract
Yan Zong Ding and Michael O. Rabin
735
Models and Techniques for Communication in Dynamic Networks
Christian Scheideler
735
What Is a Theory?
Gilles Dowek
729
A Space Lower Bound for Routing in Trees
Pierre Fraigniaud and Cyril Gavoille
733
Labeling Schemes for Dynamic Tree Networks
(Extended Abstract)
Amos Korman, David Peleg and Yoav Rodeh
732
Tight Bounds for the Performance of Longest-in-System on DAGs
Micah Adler and Adi Rosén
731
Approximate Strong Separation with Application in Fractional Graph Coloring and Preemptive Scheduling
Klaus Jansen
730
Balanced Coloring: Equally Easy for All Numbers of Colors?
Benjamin Doerr
728
The Complexity of Graph Isomorphism for Colored Graphs with Color Classes of Size 2 and 3
Johannes Köbler and Jacobo Torán
733
On the Complexity of Generating Maximal Frequent and Minimal Infrequent Sets
E. Boros, V. Gurvich, L. Khachiyan and K. Makino
735
On Dualization in Products of Forests
Khaled M. Elbassioni
733
An Asymptotic O
\mathcal{O}
(ln ρ/ ln ln ρ)-Approximation Algorithm for the Scheduling Problem with Duplication on Large Communication Delay Graphs
R. Lepere and C. Rapine
729
Scheduling at Twilight the EasyWay
Hannah Bast
731
Complexity of Multi-dimensional Loop Alignment
Alain Darte and Guillaume Huard
732
A Probabilistic 3—SAT Algorithm Further Improved
Thomas Hofmeister, Uwe Schöning, Rainer Schuler and Osamu Watanabe
732
The Secret of Selective Game Tree Search, When Using Random-Error Evaluations
U. Lorenz and B. Monien
729
Randomized Acceleration of Fundamental Matrix Computations
Victor Y. Pan
732
Approximations for ATSP with Parametrized Triangle Inequality
L. Sunil Chandran and L. Shankar Ram
730
A New Diagram from Disks in the Plane
Joachim Giesen and Matthias John
729
Computing the Maximum Detour and Spanning Ratio of Planar Paths, Trees, and Cycles
Stefan Langerman, Pat Morin and Michael Soss
734
On the Parameterized Intractability of Closest Substring
and Related Problems
Michael R. Fellows, Jens Gramm and Rolf Niedermeier
735
On the Complexity of Protein Similarity Search under mRNA Structure Constraints
Rolf Backofen, N.S. Narayanaswamy and Firas Swidan
733
Pure Dominance Constraints
Manuel Bodirsky and Martin Kutz
731
Improved Quantum Communication Complexity Bounds for Disjointness and Equality
Peter Høyer and Ronald de Wolf
733
On Quantum Computation with Some Restricted Amplitudes
Harumichi Nishimura
729
A Quantum Goldreich-Levin Theorem with Cryptographic Applications
Mark Adcock and Richard Cleve
735
On Quantum and Approximate Privacy
(Extended Abstract)
Hartmut Klauck
732
On Quantum Versions of the Yao Principle
Mart de Graaf and Ronald de Wolf
731
Describing Parameterized Complexity Classes
Jörg Flum and Martin Grohe
734
On the Computational Power of Boolean Decision Lists
Matthias Krause
733
How Many Missing Answers Can Be Tolerated by Query Learners?
Hans Ulrich Simon
731
Games with a Uniqueness Property
Shin Aida, Marcel Crasmaru, Kenneth Regan and Osamu Watanabe
735
Bi-Immunity Separates Strong NP-Completeness Notions
A. Pavan and Alan L. Selman
734
Complexity of Semi-algebraic Proofs
Dima Grigoriev, Edward A. Hirsch and Dmitrii V. Pasechnik
733
A Lower Bound Technique for Restricted Branching Programs and Applications
(Extended Abstract)
Philipp Woelfel
733
The Complexity of Constraints on Intervals and Lengths
Andrei Krokhin, Peter Jeavons and Peter Jonsson
729
Nesting Until and Since in Linear Temporal Logic
Denis Thérien and Thomas Wilke
730
Comparing Verboseness for Finite Automata and Turing Machines
Till Tantau
730
On the Average Parallelism in Trace Monoids
Daniel Krob, Jean Mairesse and Ioannis Michos
734
A Further Step towards a Theory of Regular MSC Languages
Dietrich Kuske
728
Existential and Positive Theories of Equations in Graph Products
Volker Diekert and Markus Lohrey
732
The Membership Problem for Regular Expressions with Intersection Is Complete in LOGCFL
Holger Petersen
730
Recognizable Sets of Message Sequence Charts
Rémi Morin
733
Strong Bisimilarity and Regularity of Basic Parallel Processes Is PSPACE-Hard
Jiří Srba
729
On the Enumerative Sequences of Regular Languages on
k
Symbols
Béal Marie-Pierre and Dominique Perrin
735
Ground Tree Rewriting Graphs of Bounded Tree Width
Christof Löding
731
Timed Control Synthesis for External Specifications
Deepak D’souza and P. Madhusudan
733
Axiomatizing GSOS with Termination
J.C.M. Baeten and E.P. de Vink
731
Axiomatising Tree-Interpretable Structures
Achim Blumensath
734
EXPSPACE-Complete Variant of Guarded Fragment with Transitivity
(Extended Abstract)
Emanuel Kieroński
729
A Parametric Analysis of the State Explosion Problem in Model Checking
(Extended Abstract)
S. Demri, F. Laroussinie and P. Schnoebelen
731
Generalized Model-Checking over Locally Tree-Decomposable Classes
Markus Frick
732
Learnability and Definability in Trees and Similar Structures
Martin Grohe and Gyorgy Turán
Back matter