Programs
Spring 2021

Satisfiability: Theory, Practice, and Beyond

Jan. 12May 14, 2021

In an age of ubiquitous computing, computational complexity theory is the science that studies what problems can be efficiently solved by computation. Since the founding work of the 1970s, an influential line of research has zoomed in on NP-complete problems, with the satisfiability problem for Boolean logic formulas (SAT) at its head, which turned out to be exactly the right notion to capture literally thousands of important applied problems in different fields. Based on the assumption of the hardness of NP, whose validity is one of the famous Millennium Prize Problems, a rich mathematical theory has been developed for establishing conditional results that state that all these problems are infeasible to solve, in the worst case.

The trouble is that real problems are not worst-case. The last two decades have seen the development of exceedingly efficient algorithms for many of these problems, perhaps most impressively in the form of so-called SAT solvers for logic formulas. Traditional complexity analysis claiming exponential lower bounds is arguably not very relevant in this setting, but this also means that we lack tools to understand how these algorithms can perform so well and why they sometimes spectacularly fail.

This program will bring together leading theoreticians and practitioners that work on SAT and its generalizations, and approach it from all possible angles: complexity theory, logic, computational algebra, optimization, SAT solving, constraint programming, random instances, SAT modulo theories (SMT), etc. The goal is to develop a better mathematical understanding of real-world efficient computation, and to work towards further algorithmic progress on problems that are currently beyond reach. So far, theoretical and applied research in these areas has developed mostly separately, but several joint workshops in recent years showed that the communities are eager for more interaction. This program is hence an opportunity for a longer-term collaboration and exchange of ideas between theoreticians and practitioners, that has potential for significant long-term impact in mathematics, computer science, and industry. This semester program could provide a decisive contribution in building a joint community of researchers working on constructing efficient algorithms and analyzing the computational complexity of applied problems.

sympa [at] lists.simons.berkeley.edu (body: subscribe%20sat2021announcements%40lists.simons.berkeley.edu) (Click here to subscribe to our announcements email list for this program).

Organizers:

Albert Atserias (Universitat Politècnica de Catalunya; chair), Sam Buss (UC San Diego), Vijay Ganesh (University of Waterloo), Antonina Kolokolova (Memorial University of Newfoundland), Jakob Nordström (University of Copenhagen & Lund University)

Long-Term Participants (including Organizers):

Carlos Ansotegui (Universitat de Lleida), Albert Atserias (Universitat Politècnica de Catalunya; chair), Gilles Audemard (Universite d'Artois), Paul Beame (University of Washington), Christoph Berkholz (Humboldt-Universität zu Berlin), Olaf Beyersdorff (Friedrich-Schiller University of Jena), Nikolaj Bjorner (Microsoft Research), María Luisa Bonet Carbonell (Universitat Politecnica de Catalunya), Curtis Bright (University of Windsor), Sam Buss (UC San Diego), Yijia Chen (Fudan University & Shanghai Jiaotong University), Adnan Darwiche (UC Los Angeles), Anuj Dawar (University of Cambridge), Nicola Galesi (Sapienza - Università di Roma), Vijay Ganesh (University of Waterloo), Ambros Gleixner (Zuse Institute Berlin), Marijn Heule (Carnegie Mellon University), Neil Immerman (University of Massachusetts Amherst), Russell Impagliazzo (UC San Diego), Matti Järvisalo (University of Helsinki), Jan Johannsen (Ludwig-Maximilians-Universität München), Valentine Kabanets (Simon Fraser University), Phokion G. Kolaitis (UC Santa Cruz & IBM Almaden Research Center), Antonina Kolokolova (Memorial University of Newfoundland), Oliver Kullmann (Swansea University), Massimo Lauria (Sapienza - Università di Roma), Jordi Levy Diaz (Artificial Intelligence Research Institute & Spanish National Research Council), Kevin Leyton-Brown (University of British Columbia), Meena Mahajan (The Institute of Mathematical Sciences), Susan Margulies (United States Naval Academy), Joao Marques-Silva (University of Toulouse), Ciaran McCreesh (University of Glasgow), Kuldeep Singh Meel (National University of Singapore), Jakob Nordström (University of Copenhagen & Lund University), Mohan Paturi (UC San Diego), Toni Pitassi (University of Toronto), Pavel Pudlák (Czech Academy of Sciences), Robert Robere (McGill University), Barna Saha (UC Berkeley), Karem Sakallah (University of Michigan), Rahul Santhanam (University of Oxford), Dana Scott (UC Berkeley & Carnegie Mellon University), Martina Seidl (Johannes Kepler University Linz), Laurent Simon (Bordeaux INP), Dmitry Sokolov (Steklov Institute of Mathematics), Stefan Szeider (TU Wien), Evgenia Ternovska (Simon Fraser University), Neil Thapen (Czech Academy of Sciences), Marc Vinyals (Technion - Israel Institute of Technology), Ryan Williams (Massachusetts Institute of Technology)

Research Fellows:

Susanna de Rezende (Czech Academy of Sciences), Katalin Fazekas (Johannes Kepler University Linz), Johannes Fichte (TU Dresden; Google Research Fellow), Noah Fleming (University of Toronto; MV Raghunathan Research Fellow), Stephan Gocht (Lund University; Ripple UBRI Research Fellow), Andrea Lincoln (UC Berkeley; NTT Research Fellow), Joanna Ochremiak (CNRS), Ralf Rothenberger (University of Potsdam; Microsoft Research Fellow)

Visiting Graduate Students and Postdocs:

Jaroslav Bendik (National University of Singapore), Benjamin Böhm (Friedrich-Schiller University of Jena), Ilario Bonacina (Universitat Politècnica de Catalunya), Chris Cameron (University of British Columbia), Jonathan Chung (University of Waterloo), Akhil Dixit (UC Santa Cruz), Nick Fischer (Max-Planck-Institut für Informatik), Lukás Folwarczný (Charles University Prague), Aman Goel (University of Michigan), Priyanka Golia (National University of Singapore), Mohit Gurumukhani (UC San Diego), Markus Hecher (TU Wien), Rakeeb Hossain (University of Waterloo), Erfan Khaniki (Charles University Prague), Marvin Künnemann (Max-Planck-Institut für Informatik), Ian Li (University of Waterloo), Sibylle Möhle (Johannes Kepler University Linz), Sasank Mouli (UC San Diego), Soham Mukherjee (University of Waterloo), Saeed Nejati (University of Waterloo), Oleksii Omelchenko (Simon Fraser University), Ján Pich (Oxford University), Yash Pralhad Pote (National University of Singapore), Kilian Risse (KTH Royal Institute of Technology), André Schidler (TU Wien), Joe Scott (University of Waterloo), Mate Soos (National University of Singapore), Navid Talebanfard (Czech Academy of Sciences), Nikhil Vyas (Massachusetts Institute of Technology), Krystopher Weeton (UC San Diego), Jack Wesley (UC Davis)

Workshops

Feb. 1Feb. 5, 2021

Organizers:

Albert Atserias (Universitat Politècnica de Catalunya; chair), Sam Buss (UC San Diego), Vijay Ganesh (University of Waterloo), Antonina Kolokolova (Memorial University of Newfoundland), Jakob Nordström (University of Copenhagen & Lund University)
Feb. 9, 2021May 11, 2021

Organizers:

Jakob Nordström (University of Copenhagen & Lund University; chair), Nikolaj Bjorner (Microsoft Research), Adnan Darwiche (UC Los Angeles), Ambros Gleixner (Zuse Institute Berlin), Kuldeep Singh Meel (National University of Singapore), Martina Seidl (Johannes Kepler University Linz)
Feb. 10, 2021May 12, 2021

Organizers:

Antonina Kolokolova (Memorial University of Newfoundland; co-chair), Moshe Vardi (Rice University; co-chair), María Luisa Bonet Carbonell (Universitat Politecnica de Catalunya), Vijay Ganesh (University of Waterloo), Marijn Heule (Carnegie Mellon University), Kevin Leyton-Brown (University of British Columbia)
Feb. 11, 2021May 13, 2021

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)

Those interested in participating in this program should send email to the organizers sat2021 [at] lists.simons.berkeley.edu (at this address).

 Subscribe to the program calendar.

Internal Program Activities

Monday, February 8 11:00 am12:00 pm
Wednesday, January 27 10:30 am11:00 am
Thursday, April 15 11:00 am12:00 pm
Monday, February 8 11:00 am12:00 pm
Wednesday, January 27 10:30 am11:00 am
Monday, February 8 11:00 am12:00 pm
Wednesday, January 27 10:30 am11:00 am
Monday, February 8 11:00 am12:00 pm
Wednesday, January 27 10:30 am11:00 am
Monday, February 8 11:00 am12:00 pm

Past Internal Program Activities

Thursday, April 8 11:00 am12:00 pm
Wednesday, January 27 10:30 am11:00 am
Monday, February 8 11:00 am12:00 pm
Thursday, April 1 11:00 am12:00 pm
Wednesday, January 27 10:30 am11:00 am
Monday, February 8 11:00 am12:00 pm
Thursday, March 25 11:00 am12:00 pm
Wednesday, January 27 10:30 am11:00 am
Monday, February 8 11:00 am12:00 pm
Wednesday, January 27 10:30 am11:00 am
Monday, February 8 11:00 am12:00 pm
Thursday, March 11 11:00 am12:00 pm
Wednesday, January 27 10:30 am11:00 am
Monday, February 8 11:00 am12:00 pm
Thursday, March 4 11:00 am12:00 pm
Wednesday, January 27 10:30 am11:00 am
Monday, February 8 11:00 am12:00 pm
Wednesday, January 27 10:30 am11:00 am
Monday, February 8 11:00 am12:00 pm
Thursday, February 18 11:00 am12:00 pm
Wednesday, January 27 10:30 am11:00 am
Monday, February 8 11:00 am12:00 pm
Thursday, February 11 11:00 am12:00 pm
Wednesday, January 27 10:30 am11:00 am
Monday, February 8 11:00 am12:00 pm
Thursday, February 4 11:00 am12:00 pm
Wednesday, January 27 10:30 am11:00 am
Wednesday, January 27 10:30 am11:00 am
Thursday, January 21 8:30 am9:30 am
Wednesday, January 20 9:00 am10:30 am
Tuesday, January 19 8:00 am9:00 am
Thursday, January 14 9:00 am11:00 am