STACS 98

Random graphs, random walks, differential equations and the probabilistic analysis of algorithms.- Distributed online frequency assignment in cellular networks.- Floats, integers, and single source shortest paths.- A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata.- Simplifying the modal mu-calculus alternation hierarchy.- On disguised double horn functions and extensions.- The complexity of propositional linear temporal logics in simple cases.- Searching constant width mazes captures the AC 0 hierarchy.- Nearly optimal language compression using extractors.- Random sparse bit strings at the threshold of adjacency.- Lower bounds for randomized read-k-times branching programs.- Inducing an order on cellular automata by a grouping operation.- Attractors of D-dimensional Linear Cellular Automata.- Optimal simulations between unary automata.- Shuffle of ?-words: Algebraic aspects.- A generalization of resource-bounded measure, with an application (Extended abstract).- The complexity of modular graph automorphism.- Unary quantifiers, transitive closure, and relations of large degree.- On the structure of valiant's complexity classes.- On the existence of polynomial time approximation schemes for OBDD minimization.- Complexity of problems on graphs represented as OBDDs.- Equivalence test and ordering transformation for parity-OBDDs of different variable ordering.- Size and structure of random ordered binary decision diagrams.- Provable security for block ciphers by decorrelation.- On the approximation of finding A(nother) Hamiltonian cycle in cubic Hamiltonian graphs.- The mutual exclusion scheduling problem for permutation and comparability graphs.- Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem.- Partially persistent search trees with transcript operations.- Relating hierarchies of word and tree automata.- Languages defined with modular counting