Spring 2021

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

(Weekly event) Feb 11, 2021 to May 13, 2021 (ended)View all dates

All scheduled dates:

  • Thursday, Feb 11, 2021 (ended)
  • Thursday, Feb 18, 2021 (ended)
  • Thursday, Mar 4, 2021 (ended)
  • Thursday, Mar 11, 2021 (ended)
  • Thursday, Mar 18, 2021 (ended)
  • Thursday, Mar 25, 2021 (ended)
  • Thursday, Apr 1, 2021 (ended)
  • Thursday, Apr 8, 2021 (ended)
  • Thursday, Apr 15, 2021 (ended)
  • Thursday, Apr 22, 2021 (ended)
  • Thursday, Apr 29, 2021 (ended)
  • Thursday, May 6, 2021 (ended)
  • Thursday, May 13, 2021 (ended)

Add to Calendar


Albert Atserias (Universitat Politècnica de Catalunya; co-chair), Sam Buss (UC San Diego; co-chair), Paul Beame (University of Washington), Matti Järvisalo (University of Helsinki), Mohan Paturi (UC San Diego), Toni Pitassi (University of Toronto), Neil Thapen (Czech Academy of Sciences)

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 [at] with as much advance notice as possible.

Further details about this workshop will be posted in due course. Enquiries may be sent to the organizers workshop-sat2 [at] (at this address).