swe flag På svenska
bild
School of
Computer Science
and Communication
KTH / CSC / Theory Group / Jakob Nordström / Publications and presentations

Publications and Presentations

On this webpage you find my research papers, survey papers, PhD thesis, Master's thesis, slides for some presentations and miscellaneous other stuff.

Research Papers

  • Christoph Berkholz and Jakob Nordström. Supercritical Space-Width Trade-offs for Resolution. To appear in Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP '16), July 2016. PDF PS
  • Jan Elffers, Jan Johannsen, Massimo Lauria, Thomas Magnard, Jakob Nordström, and Marc Vinyals. Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers. To appear in Proceedings of the 19th International Conference on Theory and Applications of Satisfiability Testing (SAT '16), July 2016. PDF PS
  • Christoph Berkholz and Jakob Nordström. Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. To appear in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '16), July 2016. PDF PS
  • 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 466-485, October 2015. PDF PS
  • Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, and Neil Thapen. Space Complexity in Polynomial Calculus. SIAM Journal on Computing, volume 44, issue 4, pages 1119-1153, August 2015. PDF PS
  • 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. PDF PS
  • Massimo Lauria and Jakob Nordström. Tight Size-Degree Bounds for Sums-of-Squares Proofs. In Proceedings of the 30th Annual Computational Complexity Conference (CCC '15), Leibniz International Proceedings in Informatics (LIPIcs), volume 33, pages 448-466, June 2015. PDF PS
  • 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 467-487, June 2015. PDF PS
  • Mladen Mikša and Jakob Nordström. A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds. Technical Report TR15-078, Electronic Colloquium on Computational Complexity (ECCC), May 2015. PDF PS
  • Massimo Lauria and Jakob Nordström. Tight Size-Degree Bounds for Sums-of-Squares Proofs. Technical Report TR15-053, Electronic Colloquium on Computational Complexity (ECCC), April 2015. PDF PS
  • Albert Atserias, Massimo Lauria, and Jakob Nordström. Narrow Proofs May Be Maximally Long. Technical Report TR14-118, Electronic Colloquium on Computational Complexity (ECCC), September 2014. PDF PS
  • 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 121-137, July 2014. PDF PS
  • 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 286-297, June 2014. PDF PS
  • 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 300-311, March 2014. PDF PS
  • 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 437-448, July 2013. PDF PS
  • Chris Beck, Jakob Nordström, and Bangsheng Tang. Some Trade-off Results for Polynomial Calculus (Extended Abstract). In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC '13), pages 813-822, June 2013. PDF PS
  • 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 471-557, May 2013. PDF PS
  • 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), Lecture Notes in Computer Science, volume 7514, pages 316-331, October 2012. PDF PS
  • Yuval Filmus, Massimo Lauria, Jakob Nordström, Neil Thapen, and Noga Ron-Zewi. Space Complexity in Polynomial Calculus (Extended Abstract). In Proceedings of the 27th Annual IEEE Conference on Computational Complexity (CCC '12), pages 334-344, June 2012. PDF PS
  • Trinh Huynh and Jakob Nordström. On the Virtue of Succinct Proofs: Amplifying Communication Complexity Hardness to Time-Space Trade-offs in Proof Complexity (Extended Abstract). In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC '12), pages 233-248, May 2012. PDF PS
  • Jakob Nordström. On the Relative Strength of Pebbling and Resolution. ACM Transactions on Computational Logic, volume 13, issue 2, article 16, April 2012. PDF PS
  • Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, and Ning Xie. On the Semantics of Local Characterizations for Linear-Invariant Properties. Manuscript, 2011. PDF PS
  • Jakob Nordström and Alexander Razborov. On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution. In Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP '11), Lecture Notes in Computer Science, volume 6755, pages 642-653, July 2011. PDF PS
  • Eli Ben-Sasson and Jakob Nordström. Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions (Extended Abstract). In Proceedings of the 2nd Symposium on Innovations in Computer Science (ICS '11), pages 401-416, January 2011. PDF PS
  • Eli Ben-Sasson and Jakob Nordström. Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions. Technical Report TR10-125, Electronic Colloquium on Computational Complexity (ECCC), August 2010. PDF PS This is a merged and updated version of the two ECCC technical reports TR09-034 and TR09-047, which two papers it subsumes.
  • Jakob Nordström. On the Relative Strength of Pebbling and Resolution (Extended Abstract). In Proceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC '10), pages 151-162, June 2010. PDF PS
  • Jakob Nordström. A Simplified Way of Proving Trade-off Results for Resolution. Information Processing Letters, volume 109, number 18, pages 1030-1035, August 2009. PDF PS
  • Jakob Nordström. Narrow Proofs May Be Spacious: Separating Space and Width in Resolution. SIAM Journal on Computing, volume 39, issue 1, pages 59-121, May 2009. (Special issue on STOC '06.) PDF PS
  • Eli Ben-Sasson and Jakob Nordström. Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution. Technical Report TR09-002, Electronic Colloquium on Computational Complexity (ECCC), January 2009. PDF PS
  • Eli Ben-Sasson and Jakob Nordström. Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS '08), pages 709-718, October 2008. PDF PS
  • Jakob Nordström and Johan Håstad. Towards an Optimal Separation of Space and Length in Resolution (Extended Abstract). In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC '08), pages 701-710, May 2008. PDF PS
  • Jakob Nordström. Narrow Proofs May Be Spacious: Separating Space and Width in Resolution (Extended Abstract). In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC '06), pages 507-516, May 2006. Co-winner of the Danny Lewin Best Student Paper Award. PDF PS

Survey Papers

  • Jakob Nordström. New Wine into Old Wineskins: A Survey of Some Pebbling Classics with Supplemental Results. Manuscript in preparation. To appear in Foundations and Trends in Theoretical Computer Science. Current draft version available for download—comments are welcome. PDF PS
  • Jakob Nordström. On the Interplay Between Proof Complexity and SAT Solving. ACM SIGLOG News, volume 2, number 3, pages 19-44, July 2015. PDF PS
  • 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 1-6, July 2014. PDF PS
  • Jakob Nordström. Pebble Games, Proof Complexity, and Time-Space Trade-offs. Logical Methods in Computer Science, volume 9, issue 3, article 15, September 2013. PDF PS

PhD Thesis

Jakob Nordström. Short Proofs May Be Spacious: Understanding Space in Resolution. PhD thesis, Royal Institute of Technology, Stockholm, Sweden, May 2008. Received the Ackermann Award 2009 for outstanding dissertations in Logic in Computer Science from the European Association for Computer Science Logic. PDF PS

Master's Thesis

Jakob Nordström. Stålmarck's Method Versus Resolution: A Comparative Theoretical Study. Master's thesis TRITA-NA-E0184, Stockholm University, Stockholm, Sweden, 2001. PDF PS

Some Presentations

  • 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. 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
  • 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 (Also available in video from Harvard.)
  • 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 (Also available in video from the Center for Computational Intractability.)
  • 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 (Also available in audio from the Isaac Newton Institute)
  • 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

Miscellaneous

  • [in Swedish] Jakob Nordström. Kort populärvetenskaplig sammanfattning av min doktorsavhandling. Försök till kort (knappt 2 sidor) sammanfattning av ungefär vad min doktorsavhandling handlar om och varför man är intresserad av att undersöka den typen av frågor, september 2009. PDF PS
  • [in Swedish] Jakob Nordström. Om formler, bevis och andra komplexa saker. Något förkortad och översatt version av inledningskapitlet i min doktorsavhandling Short Proofs May Be Spacious: Understanding Space in Resolution, maj 2008. PDF PS
Published by: Jakob Nordström <jakobn~at-sign~kth~dot~se>
Updated 2016-05-20