Spin systems on -regular graphs with complex edge functions

Abstract: Let be an integer and let be a complex-valued symmetric function on domain (i.e., where ). We introduce a new technique, called a syzygy, and prove a dichotomy theorem for the following class of problems, specified by and : given an arbitrary -regular graph , where the function is attached to each edge, compute . 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 and . The dependence on and is explicit. [Copyright &y& Elsevier]