STACS 2000

- 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
-