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 >>>

Complexity theory is built fundamentally on the notion of efficient
reduction among computational problems. Classical
reductions involve gadgets that map solution fragments of one problem to
solution fragments of another in one-to-one, or
possibly one-to-many, fashion. In this paper we propose a new kind of
reduction that allows for gadgets ... more >>>

We give a dichotomy theorem for the problem of counting homomorphisms to
directed acyclic graphs. $H$ is a fixed directed acyclic graph.
The problem is, given an input digraph $G$, how many homomorphisms are there
from $G$ to $H$. We give a graph-theoretic classification, showing that
for some digraphs $H$, ... more >>>

It has been shown that for every perfect matching $M$ of the $d$-dimensional
$n$-vertex hypercube, $d\geq 2, n=2^d$, there exists a second perfect matching
$M'$ such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the
$d$-dimensional hypercube. We prove a generalization of a special case of ... more >>>