Front matter
1-12
Codes and Graphs
M. Amin Shokrollahi
13-34
A Classification of Symbolic Transition Systems
Thomas A. Henzinger and Rupak Majumdar
35-52
Circuits versus Trees in Algebraic Complexity
Pascal Koiran
53-64
On the Many Faces of Block Codes
Kaustubh Deshmukh, Priti Shankar, Amitava Dasgupta and B. Sundar Rajan
65-73
A New Algorithm for MAX-2-SAT
Edward A. Hirsch
74-86
Bias Invariance of Small Upper Spans
Extended Abstract
Jack H. Lutz and Martin J. Strauss
87-98
The Complexity of Planarity Testing
Eric Allender and Meena Mahajan
99-109
About Cube-Free Morphisms
Extended Abstract
Gwénaël Richomme and Francis Wlazinski
110-121
Linear Cellular Automata with Multiple State Variables
Jarkko Kari
122-132
Two-Variable Word Equations
Extended Abstract
Lucian Ilie and Wojciech Plandowski
133-144
Average-Case Quantum Query Complexity
Andris Ambainis and Ronald de Wolf
145-156
Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs
Extended Abstract
Juraj Hromkovič and Martin Sauerhoff
157-168
The Boolean Hierarchy of NP-Partitions
Extended Abstract
Sven Kosub and Klaus W. Wagner
169-180
Binary Exponential Backoff Is Stable for High Arrival Rates
Hesham Al-Ammal, Leslie Ann Goldberg and Phil MacKenzie
181-192
The Data Broadcast Problem with Preemption
Nicolas Schabanel
193-204
An Approximate
L
p-Difference Algorithm for Massive Data Streams
Extended Abstract
Jessica H. Fong and Martin J. Strauss
205-216
Succinct Representations of Model Based Belief Revision
Extended Abstract
Paolo Penna
217-229
Logics Capturing Local Properties
Leonid Libkin
230-241
The Complexity of Poor Man’s Logic
Edith Hemaspaandra
242-253
Fast Integer Sorting in Linear Space
Yijie Han
254-266
On the Performance of
WEAK-HEAPSORT
Stefan Edelkamp and Ingo Wegener
267-278
On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers
Luca Aceto, Zoltán Ésik and Anna Ingólfsdóttir
279-289
Real-Time Automata and the Kleene Algebra of Sets of Real Numbers
Cătălin Dima
290-301
Small Progress Measures for Solving Parity Games
Marcin Jurdziński
302-313
Multi-linearity Self-Testing with Relative Error
Frédéric Magniez
314-323
Nondeterministic Instance Complexity and Hard-to-Prove Tautologies
Vikraman Arvind, Johannes Köbler, Martin Mundhenk and Jacobo Torán
324-333
Hard Instances of Hard Problems
Jack H. Lutz, Vikram Mhetre and Sridhar Srinivasan
334-345
Simulation and Bisimulation over One-Counter Processes
Petr Jančar, Antonín Kučera and Faron Moller
346-357
Decidability of Reachability Problems for Classes of Two Counters Automata
Alain Finkel and Grégoire Sutre
358-369
Hereditary History Preserving Bisimilarity Is Undecidable
Marcin Jurdziński and Mogens Nielsen
370-381
The Hardness of Approximating Spanner Problems
Michael Elkin and David Peleg
382-394
An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality
Extended Abstract
Hans-Joachim Böckenhauer, Juraj Hromkovič, Ralf Klasing, Sebastian Seibert and Walter Unger
395-406
λ-Coloring of Graphs
Hans L. Bodlaender, Ton Kloks, Richard B. Tan and Jan van Leeuwen
407-418
Optimal Proof Systems and Sparse Sets
Harry Buhrman, Steve Fenner, Lance Fortnow and Dieter van Melkebeek
419-430
Almost Complete Sets
Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann and Sebastiaan A. Terwijn
431-442
Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results
Vikraman Arvind and Johannes Köbler
443-454
An Approximation Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communications
Evripidis Bampis, Rodolphe Giroudeau and Jean-Claude König
455-465
Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem
Klaus Jansen and Maxim I. Sviridenko
466-478
Controlled Conspiracy-2 Search
Extended Abstract
Ulf Lorenz
479-490
The Stability of Saturated Linear Dynamical Systems Is Undecidable
Vincent D. Blondel, Olivier Bournez, Pascal Koiran and John N. Tsitsiklis
491-502
Tilings: Recursivity and Regularity
Julien Cervelle and Bruno Durand
503-515
Listing All Potential Maximal Cliques of a Graph
Vincent Bouchitté and Ioan Todinca
516-528
Distance Labeling Schemes for Well-Separated Graph Classes
Michal Katz, Nir A. Katz and David Peleg
529-541
Pruning Graphs with Digital Search Trees. Application to Distance Hereditary Graphs
Jean-Marc Lanlignel, Olivier Raynaud and Eric Thierry
542-554
Characterizing and Deciding MSO-Definability of Macro Tree Transductions
Joost Engelfriet and Sebastian Maneth
555-566
Languages of Dot-Depth 3/2
Christian Glaßer and Heinz Schmitz
567-580
Random Generation and Approximate Counting of Ambiguously Described Combinatorial Structures
Alberto Bertoni, Massimiliano Goldwurm and Massimo Santini
581-592
The CNN Problem and Other
k
-Server Variants
Elias Koutsoupias and David Scot Taylor
593-604
The Weighted 2-Server Problem
Marek Chrobak and Jiří Sgall
605-613
On the Competitive Ratio of the Work Function Algorithm for the
k
-Server Problem
Yair Bartal and Elias Koutsoupias
614-625
Spectral Bounds on General Hard Core Predicates
Extended Abstract
Mikael Goldmann and Alexander Russell
626-638
Randomness in Visual Cryptography
Annalisa De Bonis and Alfredo De Santis
639-650
Online Dial-a-Ride Problems: Minimizing the Completion Time
Norbert Ascheuer, Sven O. Krumke and Jörg Rambau
651-660
The Power Range Assignment Problem in Radio Networks on the Plane
Extended Abstract
Andrea E. F. Clementi, Paolo Penna and Riccardo Silvestri
Back matter