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