16965

Video URL

https://simons.berkeley.edu/talks/sat-centered-complexity-theory

SAT-Centered Complexity Theory

(2021). SAT-Centered Complexity Theory. The Simons Institute for the Theory of Computing. https://simons.berkeley.edu/talks/sat-centered-complexity-theory

SAT-Centered Complexity Theory. The Simons Institute for the Theory of Computing, Feb. 01, 2021, https://simons.berkeley.edu/talks/sat-centered-complexity-theory 

          @misc{ scivideos_16965,
            doi = {},
            url = {https://simons.berkeley.edu/talks/sat-centered-complexity-theory},
            author = {},
            keywords = {},
            language = {en},
            title = {SAT-Centered Complexity Theory},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2021},
            month = {feb},
            note = {16965 see, \url{https://scivideos.org/index.php/Simons-Institute/16965}}
          }
Valentine Kabanets (Simon Fraser University)
Talk number16965
Source RepositorySimons Institute
Subject

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.