Some Presentations
On this webpage you find a generous selection of slides (and
sometimes video recordings) for presentations that I have
given. Everything should be sorted (at least roughly) in reverse
chronological order.
Links go bad from time to time. If you discover anything that is
broken, I would be most grateful if you would
drop me a line.

Lectures on
Boolean Satisfiability (SAT) Solving
and
PseudoBoolean Solving
given on the
Logics in Computer Science
course at the
University of Copenhagen,
January 2022.

Leveraging Computational Complexity Theory for
Verifiably Correct Combinatorial Optimization.
Brief talk given at the
Digital Research Centre Denmark (DIREC) Workshop
in Nyborg, Denmark,
September 2021.

Proofs, Proof Logging, Trust, and Certification.
Brief talk given at the Dagstuhl seminar
Extending the Synergies Between SAT and Description Logics,
September 2021.

PseudoBoolean Solving: In Between SAT and ILP
Brief talk given at the
Theoretical Foundations of SAT/SMT Solving
workshop/seminar series at the
Simons Institute for the Theory of Computing,
March 2021.
(Also available in
video)

PseudoBoolean Solving and Optimization.
Tutorial given at the boot camp workshop for the
Satisfiability: Theory, Practice, and Beyond
program at the
Simons Institute for the Theory of Computing,
February 2021.
Slides for live talk
(with
video)
and slides for the longer version
(with prerecorded videos of
part I,
part II,
part III,
and
part IV
of the tutorial)

Subgraph Isomorphism Meets Cutting Planes:
Towards Verifiably Correct Constraint Programming.
Talk given at KU Leuven, September 2019,
and at the University of Copenhagen, January 2020.

Nullstellensatz SizeDegree Tradeoffs from Reversible Pebbling.
Brief talk given at the Algorithms and Complexity Section
at the University of Copenhagen,
December 2019.

On Division Versus Saturation in Cutting Planes.
Talk given at the
Lower Bounds in Computational Complexity Reunion
workshop at the
Simons Institute for the Theory of Computing,
December 2019.

Learn to Relax: Integrating Integer Linear Programming
with ConflictDriven Search.
Talk given at Imperial College London, December 2019.

Solving Exponentially Hard Problems in Linear Time(?).
Talk in the
DIKU Bits
series at the University of Copenhagen, December 2019

Subgraph Isomorphism Meets Cutting Planes.
Talk given at the
NordConsNet 2019 workshop,
May 2019.

Using PseudoWidth to Prove Lower Bounds
for Highly Overconstrained Formulas.
Talk given at the Dagstuhl seminar
Computational Complexity of Discrete Problems,
March 2019.

On Division Versus Saturation in Cutting Planes.
Talk given at the Dagstuhl seminar
Bringing CP, SAT and SMT together:
Next Challenges in Constraint Solving,
February 2019.

Proof Complexity Lower Bounds from Graph Expansion and Combinatorial Games.
Talk given at the
Algebraic Methods workshop at the
Simons Institute for the Theory of Computing,
December 2018.
(Also available in
video)

NearOptimal Lower Bounds on Quantifier Depth and
WeisfeilerLeman Refinement Steps.
Talk given at the University of Copenhagen,
September 2018.

Divide and Conquer:
Towards Faster ConflictDriven PseudoBoolean Solving.
Talk given at the University of Copenhagen,
September 2018.

Towards Faster ConflictDriven PseudoBoolean Solving.
Survey talk given at the workshop
Theory and Practice of Satisfiability Solving
at Casa Matemática Oaxaca,
August 2018.
(Also available in
video)

Seeking Practical CDCL Insights from Theoretical SAT Benchmarks.
Brief talk given at
IJCAIECAI '18
in Stockholm, Sweden, July 2018.

Reasoning in Propositional Logic Using Gröbner Bases.
Talk given at
Lund University,
May 2018.
Handwritten
notes

Beyond Satisfaction:
Towards an Understanding of RealWorld Efficient Computation
Brief talk given at the SRA ICT TNG Research Challenge Day at KTH,
May 2018.

Solving Logic Formulas in Linear Time (At Least Surprisingly Often)
Brief talk given at the University of Copenhagen,
April 2018.

Supercritical SpaceWidth Tradeoffs for Resolution.
Talk given at the Dagstuhl seminar
Proof Complexity,
JanuaryFebruary 2018.

Lower Bound Techniques for Nullstellensatz and Polynomial Calculus.
Survey talk given at the Dagstuhl seminar
Proof Complexity,
JanuaryFebruary 2018.
Handwritten
notes

Understanding ConflictDriven SAT Solving Through the
Lens of Proof Complexity.
Talk given at
Lund University,
November 2017,
and in the KTH Theory reading group,
November 2017.

Proof Complexity Lower Bounds from Graph Expansion and Combinatorial Games.
Talk given at
IT University of Copenhagen, October 2017.

Using Combinatorial Benchmarks to Probe the
Reasoning Power of PseudoBoolean Solvers.
Brief talk given at the
Pragmatics of Constraint Reasoning
workshop in Melbourne, Australia, August 2017.

A Generalized Method for Resolution and Polynomial Calculus Lower Bounds.
Talk given at the Dagstuhl seminar
Computational Complexity of Discrete Problems,
March 2017.

Understanding ConflictDriven SAT Solving
Through the Lens of Proof Complexity.
Survey talk given at the workshop
Theoretical Foundations of SAT Solving
at the Fields Institute in Toronto, Canada,
August 2016,
and at IIT Bombay in Mumbai, India, February 2017.

A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds.
Talk given at the workshop on proof complexity during the
Special Semester Program on Complexity Theory
in St. Petersburg, Russia, May 2016,
and at the Tata Institute of Fundamental Research, Mumbai, India,
February 2017.

Supercritical SpaceWidth Tradeoffs for Resolution.
Talk given at the Dagstuhl seminar
SAT and Interactions,
September 2016,
and at Rutgers University, New Jersey, USA,
October 2016.

Tradeoffs Between Time and Memory in a
Tighter Model of CDCL SAT Solvers.
Brief talk given at
SAT '16
in Bordeaux, France, July 2016.

Seeking Practical CDCL Insights from Theoretical SAT Benchmarks.
Brief talk given at the
7th Pragmatics of SAT
workshop in Bordeaux, France, July 2016.

On the Interplay Between Proof Complexity and SAT Solving.
Tutorialstyle talk
given at the
International Summer School on Satisfiability, Satisfiability
Modulo Theories, and Automated Reasoning
in Lisbon, Portugal, June 2016.

How Limited Interaction Hinders Real Communication
(and What It Means for Proof and Circuit Complexity).
Brief talk given at the
CCC 2016 Satellite Kyoto Workshop
in Kyoto, Japan, June 2016.

How Limited Interaction Hinders Real Communication
(and What It Means for Proof and Circuit Complexity).
Talk given at the
Workshop on Algorithms in Communication Complexity, Property Testing
and Combinatorics
at the Skolkovo Institute of Science and Technology,
in Moscow, Russia, April 2016.

On the Interplay Between Proof Complexity and SAT Solving.
Long survey talk given at the
National Research University Higher School of Economics
in Moscow, Russia, April 2016.
(Also available in
video.)

A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds.
Talk given at the program
Semidefinite and Matrix Methods for Optimization and Communication
at the Institute for Mathematical Sciences in Singapore, February 2016.

A Survey of Proof Complexity from a SAT Solving Perspective.
Talk given at Uppsala University, November 2015.

I skärningspunkten mellan beviskomplexitet och SATlösning.
Docent (habilitation) lecture given at
KTH Royal Institute of Technology, November 2015.

A (Biased) Proof Complexity Survey for SAT Practitioners.
Talk given at Université d'Artois in Lens, France,
February 2015.

Exploring Connections Between Proof Complexity
and Practical Hardness of SAT.
Talk given at Université d'Artois in Lens, France,
February 2015.

TimeSpace Tradeoffs in Proof Complexity (and SAT Solving?).
Talk given at the workshop
Algorithms, Complexity and Machine Learning:
A Tribute to Kurt Mehlhorn
at Chalmers University of Technology, Göteborg, October 2014.

A (Biased) Proof Complexity Survey for SAT Practitioners.
Invited talk given at SAT '14
in Vienna, Austria, July 2014.

A (Biased) Survey of Space Complexity and
TimeSpace Tradeoffs in Proof Complexity.
Invited talk given at the proof complexity workshop at
FLoC '14
in Vienna, Austria, July 2014.

Narrow Proofs May Be Maximally Long.
Talk given at the University of Chicago, May 2014.

MiniTutorial on Weak Proof Systems and Connections to SAT Solving.
Talk given at the workshop
Theoretical Foundations of Applied SAT Solving
at the Banff International Research Station in Canada, January 2014.
(Also available in
video
from BIRS.)

Relating Proof Complexity Measures and Practical Hardness of SAT.
Talk given at the
First Symposium on Structure in Hard Combinatorial Problems
in Vienna, Austria, May 2013.

Rediscovering the Joys of Pebbling.
Talk given in the KTH Theory reading group,
April 2013.

Relating Proof Complexity Measures and Practical Hardness of SAT.
Talk given at the Dagstuhl seminar
SAT Interactions,
November 2012,
and at the University of Toronto, January 2013.

Relating Proof Complexity Measures and Practical Hardness of SAT.
Brief overview talk given at
CP '12, October 2012.

On the Virtue of Succinct Proofs:
Amplifying Communication Complexity Hardness to
TimeSpace Tradeoffs in Proof Complexity.
Talk given at the
Limits of Theorem Proving workshop in Rome, Italy, September 2012,
and (slightly modified) in the KTH Theory reading group, October 2012,
and at the Tata Institute of Fundamental Research in Mumbai, India, March 2013.

On the Virtue of Succinct Proofs:
Amplifying Communication Complexity Hardness to
TimeSpace Tradeoffs in Proof Complexity.
Brief overview talk given at
STOC '12, May 2012.

Understanding the Hardness of Proving Formulas in Propositional Logic.
Updated version of a
survey talk about SAT solving, proof complexity, and timespace tradeoffs in resolution and other proof systems
given at Stockholm University,
November 2011.

On Minimal Unsatisfiability and TimeSpace Tradeoffs for kDNF Resolution.
Brief talk given at
ICALP '11,
July 2011.

On Proof Complexity Lower Bounds and Possible Connections to SAT Solving.
Brief talk given at the
Synergies in Lower Bounds
workshop at Aarhus University, Denmark,
JuneJuly 2011,
and (slightly modified)
at the Oberwolfach workshop
Mathematical Logic: Proof Theory, Constructive Mathematics,
November 2011.

On the Semantics of Local Characterizations
for LinearInvariant Properties.
Brief talk given at the Dagstuhl seminar on
Computational Complexity of Discrete Problems,
March 2011.

On the Semantics of Local Characterizations
for LinearInvariant Properties.
Talk given
in the KTH Theory Group seminar series, November 2010,
and (slightly modified) at the
Technion – Israel Institute of Technology in Haifa, Israel,
December 2010.

Understanding the Hardness of Proving Formulas in Propositional Logic.
Survey talk about SAT solving, proof complexity, and resolution timespace tradeoffs
given at Lund University,
October 2010
and in a slightly expanded and more technical version at the
Complexity and Finite Models (CMF 2011) workshop
in Paris, June 2011.

Understanding Space in Proof Complexity: Separations and Tradeoffs via Substitutions.
Brief overview talk, with a slightly more applied angle, given at the
Propositional Proof Complexity: Theory and Practice workshop at
FLoC '10,
July 2010,
and (in a slightly shorter version) at
ICS '11,
January 2011.

Understanding Space in Proof Complexity: Separations and Tradeoffs via Substitutions.
Yet another survey talk
about my PhD thesis and some subsequent work,
but with a slightly more applied angle, given at the
International Workshop on Tractability
at Microsoft Research Cambridge, UK, July 2010.

On the Relative Strength of Pebbling and Resolution.
Brief overview talk given at
CCC '10,
June 2010,
and in the KTH Theory Group seminar series, October 2010.

Understanding Space in Proof Complexity: Separations and Tradeoffs via Substitutions.
Survey talk about my PhD thesis and some subsequent work given
in the CSAIL Theory of Computation Colloquium series,
April 2010 and then (slightly modified) at the University of Toronto and
at KTH, May 2010.
Yet another modified and updated version of this talk, but with the title
Understanding the Hardness of Proving Formulas in Propositional Logic,
was given at the proof complexity workshop
at the Banff International Research Station in Canada, October 2011.

Understanding Space in Proof Complexity.
Survey talk about my PhD thesis and some subsequent work given
at the Ackermann Award ceremony at
CSL '09,
September 2009.

Understanding Space in Proof Complexity: Separations and Tradeoffs via Substitutions.
Brief overwiev talk
about the ECCC reports
TR09034
and
TR09047
given at the Barriers in Computational Complexity workshop in Princeton, USA, August 2009.

Guest lectures about proof complexity
on the
Advanced Complexity Theory
course
at MIT,
April 2009.
Handwritten
lecture notes
and (mostly accurate)
scribed notes for lecture 1
and
lecture 2.

Understanding Space in Resolution: Optimal Lower Bounds and Exponential Tradeoffs.
Talkabout our
FOCS '08 paper
and
ECCC report TR09034
given at the Dagstuhl seminar on
Computational Complexity of Discrete Problems,
September 2008,
and (slightly modified) in the MIT CSAIL Algorithms and Complexity Seminar series, October 2008.

Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution.
Brief overview talk given at
FOCS '08,
October 2008.

Towards an Optimal Separation of Space and Length in Resolution.
Brief overview talk given at
STOC '08
and at the NORDITA
Physics of distributed information systems (PhysDIS)
workshop in Stockholm, May 2008.

Towards an Optimal Separation of Space and Length in Resolution.
Talk given at
the Technion – Israel Institute of Technology in Haifa
and
the Weizmann Institute of Science in Rehovot,
Israel, March 2008.
Some technical slides in the appendix.

Narrow Proofs May Be Spacious: Separating Space and Width in Resolution.
Very detailed technical talk in the KTH Theory Group seminar series, June 2006.

Narrow Proofs May Be Spacious: Separating Space and Width in Resolution.
Brief overview talk given at
STOC '06,
May 2006.

Narrow Proofs May Be Spacious: Separating Space and Width in Resolution.
Somewhat detailed talk given at
the Dagstuhl seminar on
Complexity of Boolean Functions in March 2006
and (slightly modified) at the Isaac Newton Institute Workshop
New Directions in Proof Complexity in Cambridge, UK, in April 2006.

Short Proofs Are Narrow (Well, Sort of), But Are They Tight?
Fairly technical talk about width and space in resolution
in the KTH Theory Group PhD student seminar series, April 2006.

Stålmarck's Method versus Resolution: A Comparative Theoretical Study.
Rather informal overview of the subject matter of my Master's thesis, November 2001.

Stålmarck's Method versus Resolution: A Comparative Theoretical Study.
More technical account of the most important results in my Master's thesis, November 2001.
