50 Years of Satisfiability: The Centrality of SAT in the Theory of Computing

It has been nearly 50 years since the study of Satisfiability was initiated by the works of Cook, Karp and Levin. The ubiquity of NP-completeness caused the P versus NP question to become the defining central open question of Computational Complexity. This fundamental mathematical question remains open, but in the ensuing five decades, Satisfiability has become increasingly important in both theoretical and practical aspects of computer science.  This workshop will explore and reflect on the role of Satisfiability in theoretical computer science: some talks will cover "big picture" topics, but most talks will emphasize current and recent research. Topics to be covered include: Proof complexity, NP search hardness,  the hardness of approximability, including probabilistically checkable proofs (PCPs), fine-grained complexity, and connections between the feasibility or infeasibility of Satisfiability and the possibility of resolving the P versus NP question.

In response to the COVID-19 pandemic, Simons Institute events are currently taking place online. Please register to receive the Zoom webinar access details.

This workshop will take place every Thursday from 8:30 AM - 10:30 AM (PDT).

If you require accommodation for communication, please contact our Access Coordinator at simonsevents@berkeley.edu with as much advance notice as possible.