Spring 2021

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

Apr. 12Apr. 16, 2021

Add to Calendar


Sam Buss (UC San Diego; chair), Ramamohan Paturi (UC San Diego), Toniann Pitassi (University of Toronto)

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.

All events take place in the Calvin Lab auditorium.

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