Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with graph homomorphisms:
TR05-121 | 17th October 2005
Martin Dyer, Leslie Ann Goldberg, Michael S. Paterson

On counting homomorphisms to directed acyclic graphs

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

TR16-038 | 15th March 2016
Meena Mahajan, Nitin Saurabh

Some Complete and Intermediate Polynomials in Algebraic Complexity Theory

Revisions: 2

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

ISSN 1433-8092 | Imprint