A Graph-Theorist’s Perspective on the Quest for Dichotomy

Date & Time: 06/12/2019, 4:00 pm
Venue: Faculty Hall, Indian Institute of Science

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 beautiful blend of graph theory, logic, and universal algebra, developed over a period of 25 years; these developments, in turn, impacted all these fields. I will present a personal account of how a graph-theorist perceived the events and developments leading up to the formulation, and the solution, of the conjecture. I will focus on the impact on graph theory, but briefly mention the other fields as well.

Speaker Bio:
Pavol Hell is a Canadian computer scientist, born in Czechoslovakia. He is a professor of computing science at Simon Fraser University. His interests are in algorithmic graph theory and complexity of graph problems. He has over 200 journal and conference publications, and has supervised almost 20 PhD students, and many MSc students, over his career. He is a Fellow of the Society of Industrial and Applied Mathematics, and a Managing Editor of the Journal of Graph Theory.

Scroll Up