STACS 2000: 17th Annual Symposium on Theoretical Aspects of Computer Science Lille, France, February 17–19, 2000 Proceedings

Codes and Graphs....Pages 1-12
A Classification of Symbolic Transition Systems....Pages 13-34
Circuits versus Trees in Algebraic Complexity....Pages 35-52
On the Many Faces of Block Codes....Pages 53-64
A New Algorithm for MAX-2-SAT....Pages 65-73
Bias Invariance of Small Upper Spans....Pages 74-86
The Complexity of Planarity Testing....Pages 87-98
About Cube-Free Morphisms....Pages 99-109
Linear Cellular Automata with Multiple State Variables....Pages 110-121
Two-Variable Word Equations....Pages 122-132
Average-Case Quantum Query Complexity....Pages 133-144
Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs....Pages 145-156
The Boolean Hierarchy of NP-Partitions....Pages 157-168
Binary Exponential Backoff Is Stable for High Arrival Rates....Pages 169-180
The Data Broadcast Problem with Preemption....Pages 181-192
An Approximate L p -Difference Algorithm for Massive Data Streams....Pages 193-204
Succinct Representations of Model Based Belief Revision....Pages 205-216
Logics Capturing Local Properties....Pages 217-229
The Complexity of Poor Man’s Logic....Pages 230-241
Fast Integer Sorting in Linear Space....Pages 242-253
On the Performance of WEAK-HEAPSORT ....Pages 254-266
On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers....Pages 267-278
Real-Time Automata and the Kleene Algebra of Sets of Real Numbers....Pages 279-289
Small Progress Measures for Solving Parity Games....Pages 290-301
Multi-linearity Self-Testing with Relative Error....Pages 302-313
Nondeterministic Instance Complexity and Hard-to-Prove Tautologies....Pages 314-323
Hard Instances of Hard Problems....Pages 324-333
Simulation and Bisimulation over One-Counter Processes....Pages 334-345
Decidability of Reachability Problems for Classes of Two Counters Automata....Pages 346-357
Hereditary History Preserving Bisimilarity Is Undecidable....Pages 358-369
The Hardness of Approximating Spanner Problems....Pages 370-381
An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality....Pages 382-394
 λ -Coloring of Graphs....Pages 395-406
Optimal Proof Systems and Sparse Sets....Pages 407-418
Almost Complete Sets....Pages 419-430
Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results....Pages 431-442
An Approximation Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communications....Pages 443-454
Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem....Pages 455-465
Controlled Conspiracy-2 Search....Pages 466-478
The Stability of Saturated Linear Dynamical Systems Is Undecidable....Pages 479-490
Tilings: Recursivity and Regularity....Pages 491-502
Listing All Potential Maximal Cliques of a Graph....Pages 503-515
Distance Labeling Schemes for Well-Separated Graph Classes....Pages 516-528
Pruning Graphs with Digital Search Trees. Application to Distance Hereditary Graphs....Pages 529-541
Characterizing and Deciding MSO-Definability of Macro Tree Transductions....Pages 542-554
Languages of Dot-Depth 3/2....Pages 555-566
Random Generation and Approximate Counting of Ambiguously Described Combinatorial Structures....Pages 567-580
The CNN Problem and Other k -Server Variants....Pages 581-592
The Weighted 2-Server Problem....Pages 593-604
On the Competitive Ratio of the Work Function Algorithm for the k -Server Problem....Pages 605-613
Spectral Bounds on General Hard Core Predicates....Pages 614-625
Randomness in Visual Cryptography....Pages 626-638
Online Dial-a-Ride Problems: Minimizing the Completion Time....Pages 639-650
The Power Range Assignment Problem in Radio Networks on the Plane....Pages 651-660