Research Project on Proof Complexity and SAT Solving
Principal Investigator
Jakob Nordström
Researchers
BSc and MSc Students

Aleix Sacrest Gascón,
Universitat Politècnica de Catalunya,
Barcelona, Spain,
research intern JanuaryJune 2017

Thomas Magnard, École normale supérieure (ENS), Paris, France,
research intern MarchJuly 2015

Gustav Sennton, KTH, 2014
(MSc thesis
On Conflict Driven Clause Learning
— a Comparison Between Theory and Practice
with additional files containing all
plots
and
tables)
Group Alumni
LongTerm Visitors
(Visitors for one month or more.)

Massimo Lauria,
Universitat Politècnica de Catalunya,
AugustOctober 2016

Alexander Razborov,
University of Chicago,
MarchApril 2015

Ilario Bonacina,
Sapienza – Università di Roma,
JanuaryMay 2014

Navid Talebanfard,
Aarhus University, JanuaryMarch 2014

Yuval Filmus,
University of Toronto,
NovemberDecember 2012

Bangsheng Tang,
Tsinghua University,
JanuaryFebruary 2012

Chris Beck,
Princeton University,
JanuaryFebruary 2012

Trinh Huynh,
University of Washington and ETH Zurich,
AugustSeptember 2011
ShortTerm Visitors

Or Meir,
University of Haifa,
May 2018

Daniela Ritirc,
Johannes Kepler Universität Linz,
April 2018

Avishay Tal,
Stanford University,
April 2018

Aleksandar Zeljic,
Uppsala University
March 2018

Janne Kokkala, Aalto University,
March 2018

Annie Raymond,
University of Massachusetts Amherst,
March 2018

Jo Devriendt,
Katholieke Universiteit Leuven,
March 2018

Thomas Watson,
University of Memphis,
December 2017

Johannes Klaus Fichte,
Technische Universität Wien,
NovemberDecember 2017

Bart Bogaerts,
Katholieke Universiteit Leuven,
November 2017

Romain Wallon,
Université d'Artois,
September 2017

Robert Robere,
University of Toronto,
MayJune 2017

Igor Carboni Oliveira,
Charles University,
MarchApril 2017

Aaron Potechin,
Institute for Advanced Study,
March 2017

Ciaran McCreesh,
University of Glasgow,
March 2017

Martina Seidl,
Johannes Kepler Universität Linz,
January 2017

Pavel Pudlák,
Institute of Mathematics of the Czech Academy of Sciences,
November 2016

Sagnik Mukhopadhyay,
Tata Institute of Fundamental Research, Mumbai,
October 2016

Joël Alwen,
Institute of Science and Technology Austria,
April 2016

Laurent Simon,
Université de Bordeaux,
April 2016

Florent Capelli,
Université
Paris Diderot,
March 2016

Priyank Kalla,
University of Utah,
March 2016

Karem Sakallah,
University of Michigan and Qatar Computing Research Institute,
March 2016

Kristin Yvonne Rozier,
University of Cincinnati,
December 2015

Armin Biere,
Johannes Kepler Universität Linz,
December 2015

LiYang Tan,
Toyota Technological Institute at Chicago,
October 2015

Jesús Giráldez Crú,
Artificial Intelligence Research Institute
(IIIACSIC), Barcelona,
May 2015

Thore Husfeldt,
Lund University and
IT University of Copenhagen,
May 2015

Ilario Bonacina,
Sapienza – Università di Roma,
April 2015

Michael Forbes,
Simons Institute for the Theory of Computing at UC Berkeley,
November 2014

Marijn Heule,
University of Texas at Austin,
October 2014

Benjamin Rossman,
National Institute of Informatics, Tokyo,
June 2014

Janne H. Korhonen,
University of Helsinki,
April 2014

Igor Shinkar,
Weizmann Institute of Science,
April 2014

Prahladh Harsha,
Tata Institute of Fundamental Research, Mumbai,
March 2014

Jan Johannsen,
LudwigMaximiliansUniversität München,
March 2014

Siu Man Chan,
Princeton University,
December 2013

Daniel Le Berre,
Université d'Artois,
November 2013

Klas Markström,
Umeå University,
November 2013

Albert Atserias,
Universitat Politècnica de Catalunya,
August 2013

Christoph Berkholz,
RWTH Aachen University,
April 2013

Dominik Scheder,
Aarhus University,
February 2013

Nicola Galesi
and
Ilario Bonacina,
Sapienza – Università di Roma,
February 2013

Alexander Dreyer
and
Thanh Hung Nguyen,
Fraunhofer Institute for Industrial Mathematics ITWM,
November 2012

Troy Lee,
Centre for Quantum Technologies,
October 2012

Joshua Brody,
Aarhus University,
September 2012

Rustan Leino,
Microsoft Research Redmond,
March 2012.

Matti Järvisalo,
University of Helsinki,
December 2011

Noga RonZewi,
Technion – Israel Institute of Technology,
December 2011

Arkadev Chattopadhyay,
University of Toronto,
September 2011

Rahul Santhanam,
University of Edinburgh,
September 2011

Arie Matsliah,
IBM Research Haifa
and
Technion – Israel Institute of Technology,
August 2011

Stanislav Živný
,
University of Oxford,
May 2011

Iddo Tzameret,
Tsinghua University,
May 2011
Brief Description of Project
The purpose of this research project is to explore one of the most
significant problems in all of computer science, namely that of
proving logic formulas. This is a problem of immense importance both
theoretically and practically.
On the one hand, this computational task is believed to be intractable
in general, and deciding whether this is so is one of the famous
million dollar Millennium Problems (the P vs. NP
problem).
On the other hand, today socalled SAT solvers are routinely and
successfully used to solve largescale realworld formulas in a wide
range of application areas (such as hardware and software
verification, electronic design automation, artificial intelligence
research, cryptography, bioinformatics, operations research, and
railway signalling systems, just to name a few examples).
During the last 1520 years there have been dramatic — and
surprising — developments in SAT solving technology that have
improved realworld performance by many orders of magnitude. But
perhaps even more surprisingly, the best SAT solvers today are still
based on relatively simple methods from the early 1960s (albeit with
many clever optimizations), searching for proofs in the socalled
resolution proof system. While such solvers can often handle formulas
with millions of variables, there are also known tiny formulas with
just a few hundred variables that cause even the very best solvers to
stumble. The fundamental questions of when SAT solvers perform well or
badly, and what properties of the formulas influence SAT solver
performance, remain very poorly understood. Other practical SAT
solving issues, such as how to optimize memory management and how to
exploit parallelization on modern multicore architectures, are even
less well studied and understood from a theoretical point of view.
Proof complexity studies formal systems for reasoning about logic
formulas. This field has deep connections to fundamental questions in
computational complexity, but another important motivation is the
connection to SAT solving. All SAT solvers explicitly or implicitly
define a system in which proofs are searched for, and proof complexity
can be seen to analyse the potential and limitations of such proof systems (and
thereby of the algorithms using them).
During the last couple of decades other
mathematical methods of reasoning than resolution have been studied
and have been shown to be much stronger than resolution, in particular
methods based on algebra and geometry. It is an intriguing fact,
however, that so far attempts to harness the power of such methods
have conspicuously failed to deliver any significant improvements in
practical performance. And while resolution is a reasonably
wellunderstood proof system, even very basic questions about these
stronger algebraic and geometric methods remain wide open.
In this project, we aim to advance the frontiers of proof complexity,
and also hope to leverage this research to shed light on questions
related to SAT solving. In one direction, we are interested in
understanding what makes formulas hard or easy in practice by
combining theoretical study and practical experiments, and also in
gaining theoretical insights into other crucial but poorly understood
issues in SAT solving. Another intriguing direction is to explore the
possibility of basing SAT solvers on stronger proof systems than are
currently being used. In order to do so, however, a crucial first
step, and the main direction of the project, is to obtain a better
understanding of candidate proof systems such as, e.g., polynomial calculus
and cutting planes. In this context there are a number of wellknown
open questions in proof complexity that we want to attack and solve,
such as proving lower bounds on proof size and proof space as well as
timespace tradeoffs. Also, making progress on any other longstanding
open questions in proof complexity is always of interest. Finally, it
should be mentioned that proof complexity has turned out to have deep,
and sometimes surprising, connections to other areas in theoretical
computer science such as, for example, circuit complexity,
communication complexity, and hardness of approximation. Therefore,
the project could potentially also involve research in these or other
related areas.
Funding
This project is funded by a Starting Independent Researcher Grant
from the European Research Council
as well as by a
Junior Researcher Position Grant
and a
Breakthrough Research Grant
from the Swedish Research Council.
Workshops
Workshops, seminar weeks, et cetera coorganized by Jakob Nordström
in connection with this project:

Theory
and Practice of Satisfiability Solving,
Casa Matemática Oaxaca (affiliated with BIRS),
August 2631, 2018.

5th Swedish Summer School in
Computer Science (S^{3}CS 2018),
August 511, 2018,
with lectures by
Ronald de Wolf
and
Oded Regev.

Proof complexity,
Schloss Dagstuhl – Leibniz Center for Informatics,
January 28 – February2, 2018
(see
workshop report).

Proof Complexity and Beyond,
Mathematisches Forschungsinstitut Oberwolfach, August 1319, 2017.

4th Swedish Summer School in
Computer Science (S^{3}CS 2017),
July 1622, 2017,
with lectures by
Benjamin Rossman
and
Ryan Williams.

Theoretical Foundations of SAT Solving,
Fields Institute, Toronto, August 1519, 2016.

3rd Swedish Summer School in
Computer Science (S^{3}CS 2016),
June 26 – July 2, 2016,
with lectures by
Michael Mitzenmacher
and
Sergei Vassilvitskii.

2nd Swedish Summer School in
Computer Science (S^{3}CS 2015),
June 28 – July 4, 2015,
with lectures by
Venkatesan Guruswami
and
Sergey Yekhanin.

Theory
and Practice of SAT Solving,
Schloss Dagstuhl – Leibniz Center for Informatics,
April 1924, 2015
(see
workshop report).

Swedish Summer School in
Computer Science (S^{3}CS 2014),
June 29 – July 5, 2014,
with lectures by
Boaz Barak
and
Ryan O'Donnell.

Theoretical
Foundations of Applied SAT Solving,
Banff International Research Station,
January 1924, 2014
(see
video
of all presentations,
the
workshop report,
and a
Communications
of the ACM editorial about the workshop).
Publications
Below follows a list of publications, sorted in reverse chronological
order, resulting from this project. As a general rule, these papers
are copyright by their respective publishers but are free for personal
use.
Please note that the list below is updated somewhat infrequently.
See
www.csc.kth.se/~jakobn/research/
for a full list of Jakob Nordström's publications
(which is updated much more frequently).
2017

Massimo Lauria and Jakob Nordström.
Graph Colouring is Hard for Algorithms Based on
Hilbert's Nullstellensatz and Gröbner Bases.
Submitted, 2017.

Joël Alwen, Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals.
Cumulative Space in BlackWhite Pebbling and Resolution.
In
Proceedings of the 8th Innovations in
Theoretical Computer Science Conference (ITCS '17),
January 2017.
2016

Christoph Berkholz and Jakob Nordström.
Supercritical SpaceWidth Tradeoffs for Resolution.
Technical Report TR16203,
Electronic Colloquium on Computational Complexity (ECCC),
December 2016.

Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals.
How Limited Interaction Hinders Real Communication
(and What It Means for Proof and Circuit Complexity).
In
Proceedings of the 57th Annual IEEE Symposium on
Foundations of Computer Science (FOCS '16),
pages 295304, October 2016.

Christoph Berkholz and Jakob Nordström.
NearOptimal Lower Bounds on Quantifier Depth and
WeisfeilerLeman Refinement Steps.
Technical Report TR16135,
Electronic Colloquium on Computational Complexity (ECCC),
August 2016.

Christoph Berkholz and Jakob Nordström.
Supercritical SpaceWidth Tradeoffs for Resolution.
In
Proceedings of the 43rd International Colloquium on
Automata, Languages and Programming (ICALP '16),
Leibniz International Proceedings in Informatics (LIPIcs),
volume 55, pages 57:157:14, July 2016.

Jan Elffers, Jan Johannsen, Massimo Lauria, Thomas Magnard,
Jakob Nordström, and Marc Vinyals.
Tradeoffs Between Time and Memory in a Tighter Model of CDCL SAT Solvers.
In
Proceedings of the 19th International Conference on
Theory and Applications of Satisfiability Testing (SAT '16),
Lecture Notes in Computer Science, volume 9710,
pages 160176, July 2016.

Christoph Berkholz and Jakob Nordström.
NearOptimal Lower Bounds on Quantifier Depth and
WeisfeilerLeman Refinement Steps.
In
Proceedings of the 31st Annual ACM/IEEE Symposium on
Logic in Computer Science (LICS '16),
July 2016.

Massimo Lauria.
A Rank Lower Bound for Cutting Planes Proofs of
Ramsey's Theorem.
ACM Transactions on Computation Theory,
volume 8, issue 4, article 17, June 2016.

Albert Atserias, Massimo Lauria, and Jakob Nordström.
Narrow Proofs May Be Maximally Long.
In
ACM Transactions on Computational Logic,
volume 17, issue 3, article 19, May 2016.

Yuval Filmus, Pavel Hrubeš, and Massimo Lauria.
Semantic VersusSyntactic Cutting Planes.
In
Proceedings of the 33rd Symposium on Theoretical Aspects of
Computer Science (STACS '16),
pages 35:135:13, February 2016.

Massimo Lauria, Pavel Pudlák,
Vojtěch Rödl and Neil Thapen.
The complexity of proving that a graph is Ramsey.
Combinatorica, February 2016.
2015

Siu Man Chan, Massimo Lauria, Jakob Nordström, and Marc Vinyals.
Hardness of Approximation in PSPACE and Separation
Results for Pebble Games (Extended Abstract).
In
Proceedings of the 56th Annual IEEE Symposium on
Foundations of Computer Science (FOCS '15),
pages 466485,
October 2015.

Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga RonZewi, and Neil Thapen.
Space Complexity in Polynomial Calculus.
SIAM Journal on Computing,
volume 44, issue 4, pages 11191153, August 2015.

Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström, and Marc Vinyals.
From Small Space to Small Width in Resolution.
ACM Transactions on Computational Logic,
volume 16, issue 4, article 28, July 2015.

Jakob Nordström.
On the Interplay Between Proof Complexity and SAT Solving.
ACM SIGLOG News,
volume 2, number 3, pages 1944, July 2015.
(Lightly edited version with some typos fixed.)

Massimo Lauria and Jakob Nordström.
Tight SizeDegree Bounds for SumsofSquares Proofs.
In
Proceedings of the 30th Annual
Computational Complexity Conference (CCC '15),
Leibniz International Proceedings in Informatics (LIPIcs),
volume 33, pages 448466,
June 2015.

Mladen Mikša and Jakob Nordström.
A Generalized Method for Proving
Polynomial Calculus Degree Lower Bounds.
In
Proceedings of the 30th Annual
Computational Complexity Conference (CCC '15),
Leibniz International Proceedings in Informatics (LIPIcs),
volume 33, pages 467487,
June 2015.

Mladen Mikša and Jakob Nordström.
A Generalized Method for Proving
Polynomial Calculus Degree Lower Bounds.
Technical Report TR15078,
Electronic Colloquium on Computational Complexity (ECCC),
May 2015.

Massimo Lauria and Jakob Nordström.
Tight SizeDegree Bounds for
SumsofSquares Proofs.
Technical Report TR15053,
Electronic Colloquium on Computational Complexity (ECCC),
April 2015.
2014

Jakob Nordström.
A (Biased) Proof Complexity Survey for SAT Practitioners.
In
Proceedings of the 17th International Conference on
Theory and Applications of Satisfiability Testing (SAT '14),
Lecture Notes in Computer Science, volume 8561,
pages 16, July 2014.

Mladen Mikša and Jakob Nordström.
Long Proofs of (Seemingly) Simple Formulas.
In
Proceedings of the 17th International Conference on
Theory and Applications of Satisfiability Testing (SAT '14),
Lecture Notes in Computer Science, volume 8561,
pages 121137, July 2014.

Albert Atserias, Massimo Lauria, and Jakob Nordström.
Narrow Proofs May Be Maximally Long (Extended Abstract).
In
Proceedings of the 29th Annual IEEE Conference on Computational Complexity (CCC '14),
pages 286297, June 2014.

Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström, and Marc Vinyals.
From Small Space to Small Width in Resolution.
In
Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science
(STACS '14),
pages 300311, March 2014.
2013

Jakob Nordström.
Pebble Games, Proof Complexity, and TimeSpace Tradeoffs.
Logical Methods in Computer Science,
volume 9, issue 3, article 15, September 2013.

Olaf Beyersdorff, Nicola Galesi, and Massimo Lauria. A Characterization
of TreeLike Resolution Size. In Information Processing Letters,
volume 113, number 18,
pages 666671, September 2013.

Olaf Beyersdorff, Nicola Galesi, and Massimo Lauria. Parameterized
Complexity of DPLL Search Procedures In ACM Transactions on
Computational Logic,
volume 14, issue 3, article 23,
August 2013.

Massimo Lauria. A Rank Lower Bound for Cutting Planes Proofs of
Ramsey Theorem. In Proceedings of the 16th International
Conference on Theory and Applications of Satisfiability Testing (SAT '13),
pages 351364, July 2013.

Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström, and Marc Vinyals.
Towards an Understanding of Polynomial Calculus: New Separations and
Lower Bounds (Extended Abstract).
In
Proceedings of the 40th International Colloquium on
Automata, Languages and Programming (ICALP '13),
Lecture Notes in Computer Science, volume 7965,
pages 437448, July 2013.

Massimo Lauria, Pavel Pudlak, Vojtěch Rödl, and Neil Thapen. The
Complexity of Proving That a Graph Is Ramsey. In Proceedings of
the 40th International Colloquium on Automata, Languages and
Programming (ICALP '13),
Lecture Notes in Computer Science, volume 7965,
pages 684695, July 2013.

Chris Beck, Jakob Nordström, and Bangsheng Tang.
Some Tradeoff Results for Polynomial Calculus (Extended Abstract).
In
Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC '13),
pages 813822,
June 2013.

Jakob Nordström and Johan Håstad.
Towards an Optimal Separation of Space and Length in Resolution.
Theory of Computing,
volume 9, article 14, pages 471557, May 2013.
2012

Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga RonZewi, and Neil Thapen.
Space Complexity in Polynomial Calculus.
Technical Report TR12132,
Electronic Colloquium on Computational Complexity (ECCC),
October 2012.

Matti Järvisalo, Arie Matsliah, Jakob Nordström, and Stanislav Živný.
Relating Proof Complexity Measures and Practical Hardness of SAT.
In
Proceedings of the 18th International Conference on
Principles and Practice of Constraint Programming (CP '12),
pages 316331, October 2012.

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, and Alexander A.
Razborov. Parameterized Boundeddepth Frege Is Not Optimal. In
ACM Transaction on Computational Theory,
volume 4, issue 3, article 7,
September 2012.

Yuval Filmus, Massimo Lauria, Jakob Nordström, Neil Thapen, and Noga RonZewi.
Space Complexity in Polynomial Calculus (Extended Abstract).
In
Proceedings of the 27th Annual IEEE Conference on Computational Complexity (CCC '12),
pages 334344, June 2012.

Trinh Huynh and Jakob Nordström.
On the Virtue of Succinct Proofs:
Amplifying Communication Complexity Hardness to
TimeSpace Tradeoffs in Proof Complexity (Extended Abstract).
In
Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC '12),
pages 233248, May 2012.

Jakob Nordström.
On the Relative Strength of Pebbling and Resolution.
ACM Transactions on Computational Logic,
volume 13, issue 2, article 16, April 2012.
2011

Jakob Nordström and Alexander Razborov.
On Minimal Unsatisfiability and
TimeSpace Tradeoffs for kDNF Resolution.
In
Proceedings of the 38th International Colloquium on
Automata, Languages and Programming (ICALP '11),
Lecture Notes in Computer Science, volume 6755,
pages 642653, July 2011.

Eli BenSasson and Jakob Nordström.
Understanding Space in Proof Complexity: Separations and Tradeoffs via Substitutions (Extended Abstract).
In
Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS '11),
pages 401416, January 2011.
