Spin systems on k -regular graphs with complex edge functions

Let k ≥ 1 be an integer and let h = [ h ( 0, 0 ) h ( 0, 1 ) h ( 1, 0 ) h ( 1, 1 ) ] 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 Z ( G ) = ∑ σ: V → { 0, 1 } ∏ { u, v } ∈ E h ( σ ( u ), σ ( v ) ). Z ( ⋅ ) 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.

Authors

• Jin-Yi Cai
• Michael Kowalczyk

Keywords

• Holant problem
• Partition function
• Dichotomy theorem
• Holographic algorithms
• Interpolation
• Counting complexity