Workshops
Spring 2021

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

Feb. 11, 2021
Feb. 18, 2021
Feb. 25, 2021
Mar. 4, 2021
Mar. 11, 2021
Mar. 18, 2021
Mar. 25, 2021
Apr. 1, 2021
Apr. 8, 2021
Apr. 15, 2021
Apr. 22, 2021
Apr. 29, 2021
May 6, 2021
May 13, 2021

Add to Calendar

Organizers:

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 (PST) starting February 11. 

If you require accommodation for communication, please contact our Access Coordinator at simonsevents [at] berkeley.edu 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] lists.simons.berkeley.edu (at this address).