STACS 96

New trends in quantum computing.- Compressibility and resource bounded measure.- On the complexity of random strings.- Remarks on generalized Post Correspondence Problem.- Cyclic languages and strongly cyclic languages.- Resource-bounded balanced genericity, stochasticity and weak randomness.- The complexity of generating and checking proofs of membership.- Observations on measure and lowness for ? 2 P .- Solvable black-box group problems are low for PP.- Languages recognized by finite aperiodic groupoids.- Star-height of an N-rational series.- An aperiodic set of Wang cubes.- Lyndon factorization of infinite words.- Embedding graphs with bounded treewidth into optimal hypercubes.- Parallel comparability graph recognition and modular decomposition.- Fault-tolerant shared memory simulations.- On word-level parallelism in fault-tolerant computing.- Learning with confidence.- Extracting best consensus motifs from positive and negative examples.- PAC learning with simple examples.- General inductive inference types based on linearly-ordered sets.- On the power of non-observable actions in timed automata.- Trace rewriting: Computing normal forms in time O(n log n).- A decision procedure for well-formed linear quantum cellular automata.- On the complexity of worst case and expected time in a circuit.- On the existence of hard sparse sets under weak reductions.- Optimal bounds on the approximation of boolean functions with consequences on the concept of hardness.- Fine separation of average time complexity classes.- Compositional specification of timed systems.- Optimal tree-based one-time digital signature schemes.- The action of a few random permutations on r-tuples and an application to cryptography.- A unified and generalized treatment of authentication theory.- Monadic second order logic on tree-like structures.- On bijections vs. unary functions.- The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG Programs.- A combinatorial design approach to MAXCUT.- Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width.- A characterization of the quadrilateral meshes of a surface which admit a compatible hexahedral mesh of the enclosed volume.- On the expressivity of the modal mu-calculus.- Read-once projections and formal circuit verification with binary decision diagrams.- “Optimal” collecting semantics for analysis in a hierarchy of logic program semantics.- Flip-flop nets.- Lower bounds for compact routing.- On the successor function in non-classical numeration systems.- Minimal forbidden words and symbolic dynamics.- Universal hashing and k-wise independent random variables via integer arithmetic without primes.- Ranking and unranking trees using regular reductions.- On competitive on-line paging with lookahead.- Hypothesis testing in perfect phylogeny for a bounded number of characters.- The “log rank” conjecture for modular communication complexity.- Upper bounds on multiparty communication complexity of shifts.- Some bounds on multiparty communication complexity of pointer jumping.- Optimal schedules for d-D grid graphs with communication delays.- Linear programming — Randomization and abstract frameworks.