Jakob Nordström / Some presentations

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.

  • 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. PDF
  • Proofs, Proof Logging, Trust, and Certification. Brief talk given at the Dagstuhl seminar Extending the Synergies Between SAT and Description Logics, September 2021. PDF
  • Pseudo-Boolean 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. PDF (Also available in video)
  • Pseudo-Boolean 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 PDF (with video) and slides for the longer version PDF (with pre-recorded 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. PDF
  • Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. Brief talk given at the Algorithms and Complexity Section at the University of Copenhagen, December 2019. PDF
  • 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. PDF
  • Learn to Relax: Integrating Integer Linear Programming with Conflict-Driven Search. Talk given at Imperial College London, December 2019. PDF
  • Solving Exponentially Hard Problems in Linear Time(?). Talk in the DIKU Bits series at the University of Copenhagen, December 2019 PDF
  • Subgraph Isomorphism Meets Cutting Planes. Talk given at the NordConsNet 2019 workshop, May 2019. PDF
  • Using Pseudo-Width to Prove Lower Bounds for Highly Overconstrained Formulas. Talk given at the Dagstuhl seminar Computational Complexity of Discrete Problems, March 2019. PDF
  • 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. PDF
  • 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. PDF (Also available in video)
  • Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. Talk given at the University of Copenhagen, September 2018. PDF
  • Divide and Conquer: Towards Faster Conflict-Driven Pseudo-Boolean Solving. Talk given at the University of Copenhagen, September 2018. PDF
  • Towards Faster Conflict-Driven Pseudo-Boolean Solving. Survey talk given at the workshop Theory and Practice of Satisfiability Solving at Casa Matemática Oaxaca, August 2018. PDF (Also available in video)
  • Seeking Practical CDCL Insights from Theoretical SAT Benchmarks. Brief talk given at IJCAI-ECAI '18 in Stockholm, Sweden, July 2018. PDF
  • Reasoning in Propositional Logic Using Gröbner Bases. Talk given at Lund University, May 2018. Handwritten notes PDF
  • Beyond Satisfaction: Towards an Understanding of Real-World Efficient Computation Brief talk given at the SRA ICT TNG Research Challenge Day at KTH, May 2018. PDF
  • Solving Logic Formulas in Linear Time (At Least Surprisingly Often) Brief talk given at the University of Copenhagen, April 2018. PDF
  • Supercritical Space-Width Trade-offs for Resolution. Talk given at the Dagstuhl seminar Proof Complexity, January-February 2018. PDF
  • Lower Bound Techniques for Nullstellensatz and Polynomial Calculus. Survey talk given at the Dagstuhl seminar Proof Complexity, January-February 2018. Handwritten notes PDF
  • Understanding Conflict-Driven SAT Solving Through the Lens of Proof Complexity. Talk given at Lund University, November 2017, and in the KTH Theory reading group, November 2017. PDF
  • Proof Complexity Lower Bounds from Graph Expansion and Combinatorial Games. Talk given at IT University of Copenhagen, October 2017. PDF
  • Using Combinatorial Benchmarks to Probe the Reasoning Power of Pseudo-Boolean Solvers. Brief talk given at the Pragmatics of Constraint Reasoning workshop in Melbourne, Australia, August 2017. PDF
  • A Generalized Method for Resolution and Polynomial Calculus Lower Bounds. Talk given at the Dagstuhl seminar Computational Complexity of Discrete Problems, March 2017. PDF
  • Understanding Conflict-Driven 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. PDF
  • 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. PDF
  • Supercritical Space-Width Trade-offs for Resolution. Talk given at the Dagstuhl seminar SAT and Interactions, September 2016, and at Rutgers University, New Jersey, USA, October 2016. PDF
  • Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers. Brief talk given at SAT '16 in Bordeaux, France, July 2016. PDF
  • Seeking Practical CDCL Insights from Theoretical SAT Benchmarks. Brief talk given at the 7th Pragmatics of SAT workshop in Bordeaux, France, July 2016. PDF
  • On the Interplay Between Proof Complexity and SAT Solving. Tutorial-style talk given at the International Summer School on Satisfiability, Satisfiability Modulo Theories, and Automated Reasoning in Lisbon, Portugal, June 2016. PDF
  • 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. PDF
  • 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. PDF
  • 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. PDF (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. PDF
  • A Survey of Proof Complexity from a SAT Solving Perspective. Talk given at Uppsala University, November 2015. PDF
  • I skärningspunkten mellan beviskomplexitet och SAT-lösning. Docent (habilitation) lecture given at KTH Royal Institute of Technology, November 2015. PDF
  • A (Biased) Proof Complexity Survey for SAT Practitioners. Talk given at Université d'Artois in Lens, France, February 2015. PDF
  • Exploring Connections Between Proof Complexity and Practical Hardness of SAT. Talk given at Université d'Artois in Lens, France, February 2015. PDF
  • Time-Space Trade-offs 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. PDF
  • A (Biased) Proof Complexity Survey for SAT Practitioners. Invited talk given at SAT '14 in Vienna, Austria, July 2014. PDF
  • A (Biased) Survey of Space Complexity and Time-Space Trade-offs in Proof Complexity. Invited talk given at the proof complexity workshop at FLoC '14 in Vienna, Austria, July 2014. PDF
  • Narrow Proofs May Be Maximally Long. Talk given at the University of Chicago, May 2014. PDF
  • Mini-Tutorial 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. PDF (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. PDF
  • Rediscovering the Joys of Pebbling. Talk given in the KTH Theory reading group, April 2013. PDF
  • 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. PDF
  • Relating Proof Complexity Measures and Practical Hardness of SAT. Brief overview talk given at CP '12, October 2012. PDF
  • On the Virtue of Succinct Proofs: Amplifying Communication Complexity Hardness to Time-Space Trade-offs 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. PDF
  • On the Virtue of Succinct Proofs: Amplifying Communication Complexity Hardness to Time-Space Trade-offs in Proof Complexity. Brief overview talk given at STOC '12, May 2012. PDF
  • Understanding the Hardness of Proving Formulas in Propositional Logic. Updated version of a survey talk about SAT solving, proof complexity, and time-space trade-offs in resolution and other proof systems given at Stockholm University, November 2011. PDF
  • On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution. Brief talk given at ICALP '11, July 2011. PDF
  • 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, June-July 2011, and (slightly modified) at the Oberwolfach workshop Mathematical Logic: Proof Theory, Constructive Mathematics, November 2011. PDF
  • On the Semantics of Local Characterizations for Linear-Invariant Properties. Brief talk given at the Dagstuhl seminar on Computational Complexity of Discrete Problems, March 2011. PDF
  • On the Semantics of Local Characterizations for Linear-Invariant 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. PDF
  • Understanding the Hardness of Proving Formulas in Propositional Logic. Survey talk about SAT solving, proof complexity, and resolution time-space trade-offs given at Lund University, October 2010 PDF and in a slightly expanded and more technical version at the Complexity and Finite Models (CMF 2011) workshop in Paris, June 2011. PDF
  • Understanding Space in Proof Complexity: Separations and Trade-offs 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. PDF
  • Understanding Space in Proof Complexity: Separations and Trade-offs 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. PDF
  • 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. PDF
  • Understanding Space in Proof Complexity: Separations and Trade-offs 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. PDF 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. PDF
  • 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. PDF
  • Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions. Brief overwiev talk about the ECCC reports TR09-034 and TR09-047 given at the Barriers in Computational Complexity workshop in Princeton, USA, August 2009. PDF
  • Guest lectures about proof complexity in the MIT Advanced Complexity Theory course, April 2009. Handwritten lecture notes PDF and (mostly accurate) scribed notes for lecture 1 PDF and lecture 2. PDF
  • Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs. Talk about our FOCS '08 paper and ECCC report TR09-034 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. PDF
  • Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution. Brief overview talk given at FOCS '08, October 2008. PDF
  • 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. PDF
  • 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. PDF
  • Narrow Proofs May Be Spacious: Separating Space and Width in Resolution. Very detailed technical talk in the KTH Theory Group seminar series, June 2006. PDF
  • Narrow Proofs May Be Spacious: Separating Space and Width in Resolution. Brief overview talk given at STOC '06, May 2006. PDF
  • 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. PDF
  • 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. PDF
  • Stålmarck's Method versus Resolution: A Comparative Theoretical Study. Rather informal overview of the subject matter of my Master's thesis, November 2001. PDF
  • 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. PDF
Published by: Jakob Nordström <jn~at-sign~di~dot~ku~dot~dk>
Updated 2021-11-18