Title:  An analytic proof of the Hell-Nesetril

Speaker:  Gabor Kun, DIMACS

Abstract:

The dichotomy conjecture of Feder and Vardi states
that every Constraint Satisfaction Problem is either tractable
or NP-complete. The nicest proved case is the Hell-Nesetril theorem:
the H-coloring (homomrphism) problem is tractable if H is bipartite
and NP-complet else. We show an analytic approach to the dichotomy
conjecture.
We give a transparent proof of the Hell-Nesetril theorem
demonstrating this approach. Joint work with Mario Szegedy.