This is my PhD Thesis. It deals with questions of the computational complexity of modular counting in constraint satisfaction problems. Constraint Satisfaction Problems are a broad class of problems, including SAT and various variants of SAT, as well as some interesting graph problems. Modular Counting is exactly what it sounds like - counting the number of solutions to a problem modulo a given integer. If you don't know what computational complexity is, it isn't a great introduction. I suggest you start with something by Scott Aaronson - the essay linked to in this blogpost is a good start.
Chapters 1-5 are in the Arxiv as The Complexity of Counting Solutions to Generalized Satisfiability Problems Modulo k. There are actually some errors in that version, they are corrected in the Thesis.
Chapter 6 contains the bulk of the results in the thesis. I expanded on it with my supervisor Mark Jerrum, and put it into a paper. The final version of that paper is available in the open source journal Theory of Computing as The Complexity of Parity Graph Homomorphism: An initial investigation.
The results in Chapter 7 don't exist anywhere except in this thesis. This contains some graph automorphism hardness results. Since graph automorphism is provably easier than graph isomorphism, and since graph isomorphism is now known to be solvable in quasi-polynomial time, these results are presumably no longer particularly interesting. The proofs that the problems are at least as easy as Graph Isomorphism are now more relevant, although they were the "easy bits".
Leslie Goldberg, Andreas and David Richerby did some work which extends the results in Chapter 6. That's on the Arxiv as The Complexity of Counting Homomorphisms to Cactus Graphs Modulo 2. Their work doesn't disprove the conjecture Mark and I make in our paper, but they rightly point out that we don't have a strong basis for it - it just feels like it should be the right answer. The same authors extended the conjecture to a much wider class of graphs called Square Free graphs (that's graphs which don't contain a 4-cycle). That's on the Arxiv as Counting Homomorphisms to Square-Free Graphs, Modulo 2.
Chapters 1-5 are in the Arxiv as The Complexity of Counting Solutions to Generalized Satisfiability Problems Modulo k. There are actually some errors in that version, they are corrected in the Thesis.
Chapter 6 contains the bulk of the results in the thesis. I expanded on it with my supervisor Mark Jerrum, and put it into a paper. The final version of that paper is available in the open source journal Theory of Computing as The Complexity of Parity Graph Homomorphism: An initial investigation.
The results in Chapter 7 don't exist anywhere except in this thesis. This contains some graph automorphism hardness results. Since graph automorphism is provably easier than graph isomorphism, and since graph isomorphism is now known to be solvable in quasi-polynomial time, these results are presumably no longer particularly interesting. The proofs that the problems are at least as easy as Graph Isomorphism are now more relevant, although they were the "easy bits".
Leslie Goldberg, Andreas and David Richerby did some work which extends the results in Chapter 6. That's on the Arxiv as The Complexity of Counting Homomorphisms to Cactus Graphs Modulo 2. Their work doesn't disprove the conjecture Mark and I make in our paper, but they rightly point out that we don't have a strong basis for it - it just feels like it should be the right answer. The same authors extended the conjecture to a much wider class of graphs called Square Free graphs (that's graphs which don't contain a 4-cycle). That's on the Arxiv as Counting Homomorphisms to Square-Free Graphs, Modulo 2.
