STACS 2000: 17th Annual Symposium on Theoretical Aspects of Computer Science Lille, France, February 17-19, 2000 Proceedings (Lecture Notes in Computer Science, 1770)

This book constitutes the refereed proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, held in Lille, France in February 2000. The 51 revised full papers presented together with the three invited papers were carefully reviewed and selected from a total of 146 submissions on the basis of some 700 reviewers' reports. The papers address fundamental issues from all current areas of theoretical computer science including algorithms, data structures, automata, formal languages, complexity, verification, logic, cryptography, graph theory, optimization, etc. 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 The papers in this volume address fundamental issues from all areas of theoretical computer science including: algorithms; data structures; automata; formal languages; complexity; verification; logic; cryptography; graph theory; optimization; and more.