### DIMACS Theoretical Computer Science Seminar

Title: Graph Homomorphisms with Complex Values: A Dichotomy Theorem

Speaker: **Xi Chen**, Rutgers University

Date: Wednesday, November 26, 2008 11:00-12:00pm

Location: CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

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.