# 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.