Spring 2021

SAT-Centered Complexity Theory

Monday, Feb. 1, 2021 8:30 am10:30 am PST

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.