Talks
Spring 2021

SAT-Centered Complexity Theory
Monday, Feb. 1, 2021 8:30 am – 10:30 am PST
Speaker:
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.
Attachment | Size |
---|---|
![]() | 11.32 MB |
![]() | 11.78 MB |