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