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

Meena Mahajan, Nitin Saurabh

We provide a list of new natural VNP-intermediate polynomial

families, based on basic (combinatorial) NP-complete problems that

are complete under \emph{parsimonious} reductions. Over finite

fields, these families are in VNP, and under the plausible

hypothesis $\text{Mod}_pP \not\subseteq P/\text{poly}$, are neither VNP-hard (even under

oracle-circuit reductions) nor in VP. Prior to ...
more >>>