13 citations · 16 across the 2 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2013★ 3 cited
The complexity of parity graph homomorphism: an initial investigation
John Faben, Mark Jerrum
Given a graph G, we investigate the question of determining the parity of the number of homomorphisms from G to some other fixed graph H. We conjecture that this problem exhibits a…
cs.CC2008★ 13 cited
The complexity of counting solutions to Generalised Satisfiability Problems modulo k
John Faben
Generalised Satisfiability Problems (or Boolean Constraint Satisfaction Problems), introduced by Schaefer in 1978, are a general class of problem which allow the systematic study o…