STACS 2000 17th Annual Symposium on Theoretical Aspects of Computer Science Lille, France, February 17–19, 2000 Proceedings / [electronic resource] :
edited by Horst Reichel, Sophie Tison.
- Berlin, Heidelberg : Springer Berlin Heidelberg, 2000.
- XIV, 670 p. online resource.
- Lecture Notes in Computer Science, 1770 0302-9743 ; .
- Lecture Notes in Computer Science, 1770 .
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 -- 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 -- Graph Isomorphism 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.
9783540465416
10.1007/3-540-46541-3 doi
Computer science.
Software engineering.
Data structures (Computer science).
Information theory.
Computer graphics.
Computer Science.
Theory of Computation.
Software Engineering/Programming and Operating Systems.
Data Structures, Cryptology and Information Theory.
Computer Graphics.
Mathematics of Computing.
QA75.5-76.95
004.0151
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 -- 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 -- Graph Isomorphism 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.
9783540465416
10.1007/3-540-46541-3 doi
Computer science.
Software engineering.
Data structures (Computer science).
Information theory.
Computer graphics.
Computer Science.
Theory of Computation.
Software Engineering/Programming and Operating Systems.
Data Structures, Cryptology and Information Theory.
Computer Graphics.
Mathematics of Computing.
QA75.5-76.95
004.0151