Seminar: April 12

Gabor Kun, DIMACS and IAS

An Analytic Approach to the Dichotomy Conjecture

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 (homomorphism) problem is tractable if H is bipartite and NP-complete 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.