@article {IOPORT.06110685,
    author       = {Cai, Jin-Yi and Kowalczyk, Michael},
    title        = {Spin systems on $k$-regular graphs with complex edge functions.},
    year         = {2012},
    journal      = {Theoretical Computer Science},
    volume       = {461},
    issn         = {0304-3975},
    pages        = {2-16},
    publisher    = {Elsevier Science Publishers, Amsterdam},
    doi          = {10.1016/j.tcs.2012.01.021},
    abstract     = {Summary: Let $k \geq 1$ be an integer and let $h=\left[ \matrix h(0,0) & h(0,1)\\ h(1,0) &h(1,1)\endmatrix \right]$ be a complex-valued symmetric function on domain $\{0,1\}$ (i.e., where $h(0,1)=h(1,0))$. We introduce a new technique, called a syzygy, and prove a dichotomy theorem for the following class of problems, specified by $k$ and $h$: given an arbitrary $k$-regular graph $G=(V,E)$, where the function $h$ is attached to each edge, compute ${\bold Z}(G) = \sum_{\sigma:V \to \{0,1\}} \prod_{\{u,v\} \in E} h(\sigma(u),\sigma(v)). \bold {Z}(\cdotp)$ is known as the partition function of the spin system, also known as counting graph homomorphisms on domain size two, and is a special case of Holant problems. The dichotomy theorem gives a complete classification of the computational complexity of this problem, depending on $k$ and $h$. The dependence on $k$ and $h$ is explicit.},
    identifier   = {06110685},
}