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] lists.simons.berkeley.edu (at this address).