Spring 2021

SAT-Centered Complexity Theory

Monday, February 1st, 2021 8:30 am10:30 am

Add to Calendar


Valentine Kabanets (Simon Fraser University)

From the early 1970s until now, SAT has been the central problem in Complexity Theory, inspiring many research directions. In the tutorial, I hope to show why SAT is such a favorite with complexity theorists, by talking about classical and modern results that involve SAT or its close relatives.  We'll talk about NP-completeness, polynomial-time hierarchy, interactive proofs, PCPs, as well as (circuit) lower bounds, Exponential-Time Hypothesis, and learning.