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

Leslie G. Valiant

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

Martin Dyer, Leslie Ann Goldberg, Michael S. Paterson

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

Tomas Feder, Carlos Subi

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

Cassio P. de Campos, Georgios Stamoulis, Dennis Weyland

Weighted counting problems are a natural generalization of counting problems where a weight is associated with every computational path and the goal is to compute the sum of the weights of all paths (instead of computing the number of accepting paths). We present a structured view on weighted counting by ... more >>>

Simon Straub, Thomas Thierauf, Fabian Wagner

Counting the number of perfect matchings in arbitrary graphs is a $\#$P-complete problem. However, for some restricted classes of graphs the problem can be solved efficiently. In the case of planar graphs, and even for $K_{3,3}$-free graphs, Vazirani showed that it is in NC$^2$. The technique there is to compute ... more >>>

Patrick Scharpfenecker, Jacobo Toran

The solution graph of a Boolean formula on n variables is the subgraph of the hypercube Hn induced by the satisfying assignments of the formula. The structure of solution graphs has been the object of much research in recent years since it is important for the performance of SAT-solving procedures ... more >>>

Ashish Dwivedi, Rajat Mittal, Nitin Saxena

Finding an irreducible factor, of a polynomial $f(x)$ modulo a prime $p$, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that {\em counts} the number of irreducible factors of $f\bmod p$. We can ask the same question modulo prime-powers $p^k$. The irreducible ... more >>>