STACS 98

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Random graphs, random walks, differential equations and the probabilistic analysis of algorithms
3. Altmetric Badge
   Chapter 2 Distributed online frequency assignment in cellular networks
4. Altmetric Badge
   Chapter 3 Floats, integers, and single source shortest paths
5. Altmetric Badge
   Chapter 4 A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata
6. Altmetric Badge
   Chapter 5 Simplifying the modal mu-calculus alternation hierarchy
7. Altmetric Badge
   Chapter 6 On disguised double horn functions and extensions
8. Altmetric Badge
   Chapter 7 The complexity of propositional linear temporal logics in simple cases
9. Altmetric Badge
   Chapter 8 Searching constant width mazes captures the AC 0 hierarchy
10. Altmetric Badge
    Chapter 9 Nearly optimal language compression using extractors
11. Altmetric Badge
    Chapter 10 Random sparse bit strings at the threshold of adjacency
12. Altmetric Badge
    Chapter 11 Lower bounds for randomized read-k-times branching programs
13. Altmetric Badge
    Chapter 12 Inducing an order on cellular automata by a grouping operation
14. Altmetric Badge
    Chapter 13 Attractors of D-dimensional Linear Cellular Automata
15. Altmetric Badge
    Chapter 14 Optimal simulations between unary automata
16. Altmetric Badge
    Chapter 15 Shuffle of ω-words: Algebraic aspects
17. Altmetric Badge
    Chapter 16 A generalization of resource-bounded measure, with an application (Extended abstract)
18. Altmetric Badge
    Chapter 17 The complexity of modular graph automorphism
19. Altmetric Badge
    Chapter 18 Unary quantifiers, transitive closure, and relations of large degree
20. Altmetric Badge
    Chapter 19 On the structure of valiant's complexity classes
21. Altmetric Badge
    Chapter 20 On the existence of polynomial time approximation schemes for OBDD minimization
22. Altmetric Badge
    Chapter 21 Complexity of problems on graphs represented as OBDDs
23. Altmetric Badge
    Chapter 22 Equivalence test and ordering transformation for parity-OBDDs of different variable ordering
24. Altmetric Badge
    Chapter 23 Size and structure of random ordered binary decision diagrams
25. Altmetric Badge
    Chapter 24 Provable security for block ciphers by decorrelation
26. Altmetric Badge
    Chapter 25 On the approximation of finding A(nother) Hamiltonian cycle in cubic Hamiltonian graphs
27. Altmetric Badge
    Chapter 26 The mutual exclusion scheduling problem for permutation and comparability graphs
28. Altmetric Badge
    Chapter 27 Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem
29. Altmetric Badge
    Chapter 28 Partially persistent search trees with transcript operations
30. Altmetric Badge
    Chapter 29 Relating hierarchies of word and tree automata
31. Altmetric Badge
    Chapter 30 Languages defined with modular counting quantifiers
32. Altmetric Badge
    Chapter 31 Hierarchies of principal twist-closed trios
33. Altmetric Badge
    Chapter 32 Radix representations of algebraic number fields and finite automata
34. Altmetric Badge
    Chapter 33 Sorting and searching on the word RAM
35. Altmetric Badge
    Chapter 34 Communication-efficient deterministic parallel algorithms for planar point location and 2d Voronoi Diagram
36. Altmetric Badge
    Chapter 35 On Batcher's merge sorts as parallel sorting algorithms
37. Altmetric Badge
    Chapter 36 Minimum spanning trees for minor-closed graph classes in parallel
38. Altmetric Badge
    Chapter 37 Optimal broadcasting in almost trees and partial k-trees
39. Altmetric Badge
    Chapter 38 Local normal forms for first-order logic with applications to games and automata
40. Altmetric Badge
    Chapter 39 Axiomatizing the equational theory of regular tree languages
41. Altmetric Badge
    Chapter 40 A Logical Characterization of Systolic Languages
42. Altmetric Badge
    Chapter 41 Optimal proof systems for propositional logic and complete sets
43. Altmetric Badge
    Chapter 42 The (parallel) approximability of non-boolean satisfiability problems and restricted integer programming
44. Altmetric Badge
    Chapter 43 Interactive protocols on the reals
45. Altmetric Badge
    Chapter 44 Result-indistinguishable zero-knowledge proofs: Increased power and constant-round protocols
46. Altmetric Badge
    Chapter 45 Bounded size dictionary compression: SCk-completeness and NC algorithms
47. Altmetric Badge
    Chapter 46 Expressive completeness of LTrL on finite traces: An algebraic proof
48. Altmetric Badge
    Chapter 47 On uniform DOL words
49. Altmetric Badge
    Chapter 48 Series-parallel posets: Algebra, automata and languages
50. Altmetric Badge
    Chapter 49 On the expected number of nodes at level k in 0-balanced trees
51. Altmetric Badge
    Chapter 50 Cell flipping in permutation diagrams
52. Altmetric Badge
    Chapter 51 Construction of non-intersecting colored flows through a planar cellular figure
53. Altmetric Badge
    Chapter 52 Recursively enumerable reals and chaitin Ω numbers
54. Altmetric Badge
    Chapter 53 Uniformly defining complexity classes of functions
55. Altmetric Badge
    Chapter 54 Recognizability equals monadic second-order definability for sets of graphs of bounded tree-width