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.