Ramanujan Auditorium

A Graph Theorist's perspective on the Quest for Dichotomy

Pavol Hell

Simon Fraser University, Canada

The celebrated Feder-Vardi Dichotomy Conjecture for Constraint Satisfaction
has recently been established by Bulatov and by Zhuk. Because of the profound impact
the conjecture had on theoretical computer science, Feder and Vardi were jointly
awarded the Alonzo Church Award for 2019. The solution involved a beatiful blend
of graph theory, logic, and universal algebra, developed over a period of 25 years;
and these developments, in turn, have impacted all these fields.

I will present a personal account of how one graph-theorist perceived the events
and developments leading up to the formulation, and the solution, of the conjecture.