Spring 2021

Classifying the Complexity of SAT and CSP: Are we there yet?

Thursday, April 8th, 2021, 9:30 am10:30 am

Add to Calendar


Andrei Krokhin (Durham University)



I will take you on an express tour of the mathematical and philosophical developments in the complexity classification quest for SAT and CSP. The route includes many landmarks such as Schaefer, Feder-Vardi, Jeavons, and Bulatov-Zhuk. At the end of the tour I will discuss where we are with this quest now.