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 ageneralization of the vertex cover problem.- Partially persistent search trees with transcript operations.- Relating hierarchies of word and tree automata.- Languages defined with modular counting quantifiers.- Hierarchies of principal twist-closed trios.- Radix representations of algebraic number fields and finite automata.- Sorting and searching on the word RAM.- Communication-efficient deterministic parallel algorithms for planar point location and 2d Voronoi Diagram.- On Batcher's merge sorts as parallel sorting algorithms.- Minimum spanning trees for minor-closed graph classes in parallel.- Optimal broadcasting in almost trees and partial k-trees.- Local normal forms for first-order logic with applications to games and automata.- Axiomatizing the equational theory of regular tree languages.- A Logical Characterization of Systolic Languages.- Optimal proof systems for propositional logic and complete sets.- The (parallel) approximability of non-boolean satisfiability problems and restricted integer programming.- Interactive protocols on the reals.- Result-indistinguishable zero-knowledge proofs: Increased power and constant-round protocols.- Bounded size dictionary compression: SCk-completeness and NC algorithms.- Expressive completeness of LTrL on finite traces: An algebraic proof.- On uniform DOL words.- Series-parallel posets: Algebra, automata and languages.- On the expected number of nodes at level k in 0-balanced trees.- Cell flipping in permutation diagrams.- Construction of non-intersecting colored flows through a planar cellular figure.- Recursively enumerable reals and chaitin ? numbers.- Uniformly defining complexity classes of functions.- Recognizability equals monadic second-order definability for sets of graphs of bounded tree-width.