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

M. Amin Shokrollahi (auth.), Horst Reichel, Sophie Tison (eds.)3540671412, 9783540671411

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.

---

Table of contents :
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