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