Title: Graph Homomorphisms with Complex Values: A Dichotomy Theorem

Speaker: Xi Chen

Abstract:
The graph homomorphism problem has been studied intensively. Given an
m by m symmetric matrix A, the graph homomorphism function is defined as

Z_A(G) = \sum_{f:V \rightarrow [m]} \prod_{(u,v) \in E} A_{f(u),f(v)},

where G = (V,E) is any undirected graph. The function Z_A(G) can
encode many interesting graph properties, including counting vertex
covers and k-colorings. We study the computational complexity of
Z_A(G) for arbitrary complex valued matrices A.  Building on work by
Dyer and Greenhill, Bulatov and Grohe, and especially the recent
beautiful work by Goldberg, Grohe, Jerrum and Thurley, we prove a
complete dichotomy theorem for this problem.

Joint work with Jin-Yi Cai and Pinyan Lu.