STACS 2000

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Codes and Graphs
3. Altmetric Badge
   Chapter 2 A Classification of Symbolic Transition Systems
4. Altmetric Badge
   Chapter 3 Circuits versus Trees in Algebraic Complexity
5. Altmetric Badge
   Chapter 4 On the Many Faces of Block Codes
6. Altmetric Badge
   Chapter 5 A New Algorithm for MAX-2-SAT
7. Altmetric Badge
   Chapter 6 Bias Invariance of Small Upper Spans
8. Altmetric Badge
   Chapter 7 The Complexity of Planarity Testing
9. Altmetric Badge
   Chapter 8 About Cube-Free Morphisms
10. Altmetric Badge
    Chapter 9 Linear Cellular Automata with Multiple State Variables
11. Altmetric Badge
    Chapter 10 Two-Variable Word Equations
12. Altmetric Badge
    Chapter 11 Average-Case Quantum Query Complexity
13. Altmetric Badge
    Chapter 12 Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs
14. Altmetric Badge
    Chapter 13 The Boolean Hierarchy of NP-Partitions
15. Altmetric Badge
    Chapter 14 Binary Exponential Backoff Is Stable for High Arrival Rates
16. Altmetric Badge
    Chapter 15 The Data Broadcast Problem with Preemption
17. Altmetric Badge
    Chapter 16 An Approximate L p -Difference Algorithm for Massive Data Streams
18. Altmetric Badge
    Chapter 17 Succinct Representations of Model Based Belief Revision
19. Altmetric Badge
    Chapter 18 Logics Capturing Local Properties
20. Altmetric Badge
    Chapter 19 The Complexity of Poor Man’s Logic
21. Altmetric Badge
    Chapter 20 Fast Integer Sorting in Linear Space
22. Altmetric Badge
    Chapter 21 On the Performance of WEAK-HEAPSORT
23. Altmetric Badge
    Chapter 22 On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers
24. Altmetric Badge
    Chapter 23 Real-Time Automata and the Kleene Algebra of Sets of Real Numbers
25. Altmetric Badge
    Chapter 24 Small Progress Measures for Solving Parity Games
26. Altmetric Badge
    Chapter 25 Multi-linearity Self-Testing with Relative Error
27. Altmetric Badge
    Chapter 26 Nondeterministic Instance Complexity and Hard-to-Prove Tautologies
28. Altmetric Badge
    Chapter 27 Hard Instances of Hard Problems
29. Altmetric Badge
    Chapter 28 Simulation and Bisimulation over One-Counter Processes
30. Altmetric Badge
    Chapter 29 Decidability of Reachability Problems for Classes of Two Counters Automata
31. Altmetric Badge
    Chapter 30 Hereditary History Preserving Bisimilarity Is Undecidable
32. Altmetric Badge
    Chapter 31 The Hardness of Approximating Spanner Problems
33. Altmetric Badge
    Chapter 32 An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality
34. Altmetric Badge
    Chapter 33 λ -Coloring of Graphs
35. Altmetric Badge
    Chapter 34 Optimal Proof Systems and Sparse Sets
36. Altmetric Badge
    Chapter 35 Almost Complete Sets
37. Altmetric Badge
    Chapter 36 Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results
38. Altmetric Badge
    Chapter 37 An Approximation Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communications
39. Altmetric Badge
    Chapter 38 Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem
40. Altmetric Badge
    Chapter 39 Controlled Conspiracy-2 Search
41. Altmetric Badge
    Chapter 40 The Stability of Saturated Linear Dynamical Systems Is Undecidable
42. Altmetric Badge
    Chapter 41 Tilings: Recursivity and Regularity
43. Altmetric Badge
    Chapter 42 Listing All Potential Maximal Cliques of a Graph
44. Altmetric Badge
    Chapter 43 Distance Labeling Schemes for Well-Separated Graph Classes
45. Altmetric Badge
    Chapter 44 Pruning Graphs with Digital Search Trees. Application to Distance Hereditary Graphs
46. Altmetric Badge
    Chapter 45 Characterizing and Deciding MSO-Definability of Macro Tree Transductions
47. Altmetric Badge
    Chapter 46 Languages of Dot-Depth 3/2
48. Altmetric Badge
    Chapter 47 Random Generation and Approximate Counting of Ambiguously Described Combinatorial Structures
49. Altmetric Badge
    Chapter 48 The CNN Problem and Other k -Server Variants
50. Altmetric Badge
    Chapter 49 The Weighted 2-Server Problem
51. Altmetric Badge
    Chapter 50 On the Competitive Ratio of the Work Function Algorithm for the k -Server Problem
52. Altmetric Badge
    Chapter 51 Spectral Bounds on General Hard Core Predicates
53. Altmetric Badge
    Chapter 52 Randomness in Visual Cryptography
54. Altmetric Badge
    Chapter 53 Online Dial-a-Ride Problems: Minimizing the Completion Time
55. Altmetric Badge
    Chapter 54 The Power Range Assignment Problem in Radio Networks on the Plane