Carme Alvarez, Raymond Greenlaw

We provide a compendium of problems that are complete for

symmetric logarithmic space (SL). Complete problems are one method

of studying this class for which programming is nonintuitive. A

number of the problems in the list were not previously known to be

complete. A ...
more >>>

Cristopher Moore

We propose definitions of $\QAC^0$, the quantum analog of the

classical class $\AC^0$ of constant-depth circuits with AND and OR

gates of arbitrary fan-in, and $\QACC^0[q]$, the analog of the class

$\ACC^0[q]$ where $\Mod_q$ gates are also allowed. We show that it is

possible to make a `cat' state on ...
more >>>

Miroslava Sotáková

This paper deals with the reversible circuits with n input and

output nodes, consisting of the reversible gates FAN-IN=FAN-OUT<3.

We define a normal form of such type of circuits and describe a reduction

algorithm to transform a circuit in this form. Furthermore we use it for

checking whether two circuits ...
more >>>

Eric Allender, Klaus-Joern Lange

We show that every language accepted by a nondeterministic auxiliary pushdown automaton in polynomial time (that is, every language in SAC$^1$ = LogCFL) can be accepted by a symmetric auxiliary pushdown automaton in polynomial time.

Luke Schaeffer

Several cellular automata (CA) are known to be universal in the sense that one can simulate arbitrary computations (e.g., circuits or Turing machines) by carefully encoding the computational device and its input into the cells of the CA. In this paper, we consider a different kind of universality proposed by ... more >>>