Seminars

View all Seminars  |  Download ICal for this event

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

Series: CSA Golden Jubilee Frontier Lecture Series

Speaker: Professor Pavol Hell Professor of Computing Science Simon Fraser University

Date/Time: Dec 06 16:00:00

Location: Faculty Hall, Indian Institute of Science

Abstract:
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.

Host Faculty: Prof. Shalabh Bhatnagar