Graph homomorphism (Lov\'{a}sz 1967) has been studied intensively by many researchers over the decades. In the physics community it is called Partition Function. The problem can be stated as follows:

Given an $m \times m$ symmetric matrix $A$ over the complex field, compute the function $Z_A(\cdot)$, where for an arbitrary input graph $G$, \[ Z_A(G) = \sum_{\xi:V(G)\rightarrow [m]} \prod_{(u,v)\in E(G)} A_{\xi(u),\xi(v)}.\]

The problem encompasses many combinatorial counting problems such as counting vertex covers, graph colorings etc. We prove a complexity dichotomy theorem, that the problem is either computable in P or \#P-hard, depending in $A$. The complex field affords much possibility for cancelations and thus non-trivial polynomial time algorithms. Indeed Fourier matrices and character sums play a major role. In the complex domain, there are also natural connections to holographic algorithms. Due to the complexity of the proof, we will only be able to give a rough outline.

Joint work with Xi Chen of Princeton and Pinyan Lu of Tsinghua. Paper available on http://arxiv.org/abs/0903.4728 (111 pages.)