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.