Each symmetric matrix A defines a graph homomorphism function Z_A on undirected graphs. The function Z_A is also called the partition function from statistical physics, and can encode many interesting graph properties including counting vertex covers and k-colorings. During the past fifteen years, a sequence of (explicit) dichotomy theorems have been established for Z_A over 0-1 valued matrices [Dyer and Greenhill], nonnegative matrices [Bulatov and Grohe], real matrices [Goldberg, Grohe, Jerrum and Thurley], and complex matrices [Cai, Chen and Lu]. In this lecture we will review the complexity classification of Z_A behind these dichotomies, and showcase some of the techniques developed in these works.

The complexity of counting graph homomorphisms, Dyer and Greenhill
http://onlinelibrary.wiley.com/doi/10.1002/1098-2418(200010/12)17:3/4%3C260::AID-RSA5%3E3.0.CO;2-W/abstract 
The complexity of partition functions, Bulatov and Grohe
http://www.sciencedirect.com/science/article/pii/S030439750500530X
A complexity dichotomy for partition functions with mixed signs, Goldberg, Grohe, Jerrum and Thurley
http://epubs.siam.org/doi/abs/10.1137/090757496
Graph homomorphisms with complex values: A dichotomy theorem, Cai, Chen and Lu
http://epubs.siam.org/doi/abs/10.1137/110840194

The second session of this mini course will take place on Wednesday, January 27 from 1:30 pm – 2:30 pm.