STACS 2000 17th Annual Symposium on Theoretical Aspects of Computer Science Lille, France, February 17-19, 2000 Proceedings
| Other Authors: | , |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
2000, 2000
|
| Edition: | 1st ed. 2000 |
| Series: | Lecture Notes in Computer Science
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers
- Real-Time Automata and the Kleene Algebra of Sets of Real Numbers
- Small Progress Measures for Solving Parity Games
- Multi-linearity Self-Testing with Relative Error
- Nondeterministic Instance Complexity and Hard-to-Prove Tautologies
- Hard Instances of Hard Problems
- Simulation and Bisimulation over One-Counter Processes
- Decidability of Reachability Problems for Classes of Two Counters Automata
- Hereditary History Preserving Bisimilarity Is Undecidable
- The Hardness of Approximating Spanner Problems
- An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality
- ?-Coloring of Graphs
- Optimal Proof Systems and Sparse Sets
- Almost Complete Sets
- GraphIsomorphism Is Low for ZPP(NP) and Other Lowness Results
- An Approximation Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communications
- Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem
- Controlled Conspiracy-2 Search
- The Stability of Saturated Linear Dynamical Systems Is Undecidable
- Tilings: Recursivity and Regularity
- Listing All Potential Maximal Cliques of a Graph
- Distance Labeling Schemes for Well-Separated Graph Classes
- Pruning Graphs with Digital Search Trees. Application to Distance Hereditary Graphs
- Characterizing and Deciding MSO-Definability of Macro Tree Transductions
- Languages of Dot-Depth 3/2
- Random Generation and Approximate Counting of Ambiguously Described Combinatorial Structures
- The CNN Problem and Other k-Server Variants
- The Weighted 2-Server Problem
- On the Competitive Ratio of the Work Function Algorithm for the k-Server Problem
- Spectral Bounds on General Hard Core Predicates
- Randomness in Visual Cryptography
- Online Dial-a-Ride Problems: Minimizing the Completion Time
- The Power Range Assignment Problem in Radio Networks on the Plane
- Codes and Graphs
- A Classification of Symbolic Transition Systems
- Circuits versus Trees in Algebraic Complexity
- On the Many Faces of Block Codes
- A New Algorithm for MAX-2-SAT
- Bias Invariance of Small Upper Spans
- The Complexity of Planarity Testing
- About Cube-Free Morphisms
- Linear Cellular Automata with Multiple State Variables
- Two-Variable Word Equations
- Average-Case Quantum Query Complexity
- Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs
- The Boolean Hierarchy of NP-Partitions
- Binary Exponential Backoff Is Stable for High Arrival Rates
- The Data Broadcast Problem with Preemption
- An Approximate L p-Difference Algorithm for Massive Data Streams
- Succinct Representations of Model Based Belief Revision
- Logics Capturing Local Properties
- The Complexity of Poor Man’s Logic
- Fast Integer Sorting in Linear Space
- On the Performance of WEAK-HEAPSORT