Jakob Nordström

According to our database, Jakob Nordström authored at least 85 papers between 2006 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Pseudo-Boolean Proof Logging for Optimal Classical Planning.

Simon Dold, Malte Helmert, Jakob Nordström, Gabriele Röger, Tanja Schindler

CoRR, April, 2025

Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds.

Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals

Theory Comput., 2025

Truly Supercritical Trade-Offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman.

Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordström, Shuo Pang

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Practically Feasible Proof Logging for Pseudo-Boolean Optimization.

Wietze Koops, Daniel Le Berre, Magnus O. Myreen, Jakob Nordström, Andy Oertel, Yong Kiam Tan, Marc Vinyals

Proceedings of the 31st International Conference on Principles and Practice of Constraint Programming, 2025

2024

Certified MaxSAT Preprocessing.

Hannes Ihalainen, Andy Oertel, Yong Kiam Tan, Jeremias Berg, Matti Järvisalo, Jakob Nordström

CoRR, 2024

Certified MaxSAT Preprocessing.

Hannes Ihalainen, Andy Oertel, Yong Kiam Tan, Jeremias Berg, Matti Järvisalo, Magnus O. Myreen, Jakob Nordström

Proceedings of the Automated Reasoning - 12th International Joint Conference, 2024

Proof Logging for the Circuit Constraint.

Matthew J. McIlree, Ciaran McCreesh, Jakob Nordström

Proceedings of the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2024

Certifying MIP-Based Presolve Reductions for 0-1 Integer Linear Programs.

Alexander Hoen, Andy Oertel, Ambros M. Gleixner, Jakob Nordström

Proceedings of the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 2024

Pseudo-Boolean Reasoning About States and Transitions to Certify Dynamic Programming and Decision Diagram Algorithms.

Emir Demirovic, Ciaran McCreesh, Matthew J. McIlree, Jakob Nordström, Andy Oertel, Konstantin Sidorov

Proceedings of the 30th International Conference on Principles and Practice of Constraint Programming, 2024

Certifying Without Loss of Generality Reasoning in Solution-Improving Maximum Satisfiability.

Jeremias Berg, Bart Bogaerts, Jakob Nordström, Andy Oertel, Tobias Paxian, Dieter Vandesande

Proceedings of the 30th International Conference on Principles and Practice of Constraint Programming, 2024

End-to-End Verification for Subgraph Solving.

Stephan Gocht, Ciaran McCreesh, Magnus O. Myreen, Jakob Nordström, Andy Oertel, Yong Kiam Tan

Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

2023

Certified Dominance and Symmetry Breaking for Combinatorial Optimisation.

Bart Bogaerts, Stephan Gocht, Ciaran McCreesh, Jakob Nordström

J. Artif. Intell. Res., 2023

Certified CNF Translations for Pseudo-Boolean Solving (Extended Abstract).

Stephan Gocht, Ruben Martins, Jakob Nordström, Andy Oertel

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz.

Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, Kilian Risse

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning.

Gioni Mexi, Timo Berthold, Ambros M. Gleixner, Jakob Nordström

Proceedings of the 29th International Conference on Principles and Practice of Constraint Programming, 2023

Certified Core-Guided MaxSAT Solving.

Jeremias Berg, Bart Bogaerts, Jakob Nordström, Andy Oertel, Dieter Vandesande

Proceedings of the Automated Deduction - CADE 29, 2023

2022

Theory and Practice of SAT and Combinatorial Solving (Dagstuhl Seminar 22411).

Olaf Beyersdorff, Armin Biere, Vijay Ganesh, Jakob Nordström, Andy Oertel

Dagstuhl Reports, October, 2022

Certified CNF Translations for Pseudo-Boolean Solving.

Stephan Gocht, Ruben Martins, Jakob Nordström, Andy Oertel

Proceedings of the 25th International Conference on Theory and Applications of Satisfiability Testing, 2022

Adding Dual Variables to Algebraic Reasoning for Gate-Level Multiplier Verification.

Daniela Kaufmann, Paul Beame, Armin Biere, Jakob Nordström

Proceedings of the 2022 Design, Automation & Test in Europe Conference & Exhibition, 2022

An Auditable Constraint Programming Solver.

Stephan Gocht, Ciaran McCreesh, Jakob Nordström

Proceedings of the 28th International Conference on Principles and Practice of Constraint Programming, 2022

Certified Symmetry and Dominance Breaking for Combinatorial Optimisation.

Bart Bogaerts, Stephan Gocht, Ciaran McCreesh, Jakob Nordström

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021

Proof Complexity and SAT Solving.

Sam Buss, Jakob Nordström

Proceedings of the Handbook of Satisfiability - Second Edition, 2021

Planning with Learned Binarized Neural Networks Benchmarks for MaxSAT Evaluation 2021.

Buser Say, Scott Sanner, Jo Devriendt, Jakob Nordström, Peter J. Stuckey

CoRR, 2021

Learn to relax: Integrating 0-1 integer linear programming with pseudo-Boolean conflict-driven search.

Jo Devriendt, Ambros M. Gleixner, Jakob Nordström

Constraints An Int. J., 2021

Automating algebraic proof systems is NP-hard.

Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Certifying CNF Encodings of Pseudo-Boolean Constraints (abstract).

Stephan Gocht, Jakob Nordström, Ruben Martins

Proceedings of the Proceedings Seventh Workshop on Proof eXchange for Theorem Proving, 2021

The Power of Negative Reasoning.

Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Dmitry Sokolov

Proceedings of the 36th Computational Complexity Conference, 2021

Certifying Parity Reasoning Efficiently Using Pseudo-Boolean Proofs.

Stephan Gocht, Jakob Nordström

Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

Cutting to the Core of Pseudo-Boolean Optimization: Combining Core-Guided Search with Cutting Planes Reasoning.

Jo Devriendt, Stephan Gocht, Emir Demirovic, Jakob Nordström, Peter J. Stuckey

Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020

Experimental Repository for "Cutting to the Core of Pseudo-Boolean Optimization: Combining Core-Guided Search with Cutting Planes Reasoning".

Jo Devriendt, Stephan Gocht, Emir Demirovic, Jakob Nordström, Peter J. Stuckey

Dataset, September, 2020

Simplified and Improved Separations Between Regular and General Resolution by Lifting.

Marc Vinyals, Jan Elffers, Jan Johannsen, Jakob Nordström

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2020, 2020

Trade-Offs Between Size and Degree in Polynomial Calculus.

Guillaume Lagarde, Jakob Nordström, Dmitry Sokolov, Joseph Swernofsky

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Subgraph Isomorphism Meets Cutting Planes: Solving With Certified Solutions.

Stephan Gocht, Ciaran McCreesh, Jakob Nordström

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, 2020

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity.

Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Marc Vinyals

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

KRW Composition Theorems via Lifting.

Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning.

Vincent Liew, Paul Beame, Jo Devriendt, Jan Elffers, Jakob Nordström

Proceedings of the 2020 Formal Methods in Computer Aided Design, 2020

Theoretical and Experimental Results for Planning with Learned Binarized Neural Network Transition Models.

Buser Say, Jo Devriendt, Jakob Nordström, Peter J. Stuckey

Proceedings of the Principles and Practice of Constraint Programming, 2020

Using Resolution Proofs to Analyse CDCL Solvers.

Janne I. Kokkala, Jakob Nordström

Proceedings of the Principles and Practice of Constraint Programming, 2020

Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems.

Stephan Gocht, Ross McBride, Ciaran McCreesh, Jakob Nordström, Patrick Prosser, James Trimble

Proceedings of the Principles and Practice of Constraint Programming, 2020

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs.

Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov

Proceedings of the 35th Computational Complexity Conference, 2020

A Cardinal Improvement to Pseudo-Boolean Solving.

Jan Elffers, Jakob Nordström

Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020

Justifying All Differences Using Pseudo-Boolean Reasoning.

Jan Elffers, Stephan Gocht, Ciaran McCreesh, Jakob Nordström

Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020

2019

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity.

Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna F. de Rezende

Electron. Colloquium Comput. Complex., 2019

On Division Versus Saturation in Pseudo-Boolean Solving.

Stephan Gocht, Jakob Nordström, Amir Yehudayoff

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2019

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling.

Susanna F. de Rezende, Jakob Nordström, Or Meir, Robert Robere

Proceedings of the 34th Computational Complexity Conference, 2019

2018

Proof Complexity (Dagstuhl Seminar 18051).

Albert Atserias, Jakob Nordström, Pavel Pudlák, Rahul Santhanam

Dagstuhl Reports, 2018

Clique is hard on average for regular resolution.

Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

In Between Resolution and Cutting Planes: A Study of Proof Systems for Pseudo-Boolean SAT Solving.

Marc Vinyals, Jan Elffers, Jesús Giráldez-Cru, Stephan Gocht, Jakob Nordström

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2018, 2018

Using Combinatorial Benchmarks to Probe the Reasoning Power of Pseudo-Boolean Solvers.

Jan Elffers, Jesús Giráldez-Cru, Jakob Nordström, Marc Vinyals

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2018, 2018

Divide and Conquer: Towards Faster Pseudo-Boolean Solving.

Jan Elffers, Jakob Nordström

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Seeking Practical CDCL Insights from Theoretical SAT Benchmarks.

Jan Elffers, Jesús Giráldez-Cru, Stephan Gocht, Jakob Nordström, Laurent Simon

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

2017

CNFgen: A Generator of Crafted Benchmarks.

Massimo Lauria, Jan Elffers, Jakob Nordström, Marc Vinyals

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28, 2017

Cumulative Space in Black-White Pebbling and Resolution.

Joël Alwen, Susanna F. de Rezende, Jakob Nordström, Marc Vinyals

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases.

Massimo Lauria, Jakob Nordström

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers.

Jan Elffers, Jan Johannsen, Massimo Lauria, Thomas Magnard, Jakob Nordström, Marc Vinyals

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2016, 2016

Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps.

Christoph Berkholz, Jakob Nordström

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

Supercritical Space-Width Trade-Offs for Resolution.

Christoph Berkholz, Jakob Nordström

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity).

Susanna F. de Rezende, Jakob Nordström, Marc Vinyals

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

On the interplay between proof complexity and SAT solving.

Jakob Nordström

ACM SIGLOG News, 2015

Theory and Practice of SAT Solving (Dagstuhl Seminar 15171).

Armin Biere, Vijay Ganesh, Martin Grohe, Jakob Nordström, Ryan Williams

Dagstuhl Reports, 2015

Hardness of Approximation in PSPACE and Separation Results for Pebble Games.

Siu Man Chan, Massimo Lauria, Jakob Nordström, Marc Vinyals

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds.

Mladen Miksa, Jakob Nordström

Proceedings of the 30th Conference on Computational Complexity, 2015

Tight Size-Degree Bounds for Sums-of-Squares Proofs.

Massimo Lauria, Jakob Nordström

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

From Small Space to Small Width in Resolution.

Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science, 2014

A (Biased) Proof Complexity Survey for SAT Practitioners.

Jakob Nordström

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2014, 2014

Long Proofs of (Seemingly) Simple Formulas.

Mladen Miksa, Jakob Nordström

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2014, 2014

Narrow Proofs May Be Maximally Long.

Albert Atserias, Massimo Lauria, Jakob Nordström

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

Pebble Games, Proof Complexity, and Time-Space Trade-offs.

Jakob Nordström

Log. Methods Comput. Sci., 2013

Some trade-off results for polynomial calculus: extended abstract.

Chris Beck, Jakob Nordström, Bangsheng Tang

Proceedings of the Symposium on Theory of Computing Conference, 2013

Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds - (Extended Abstract).

Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity.

Trinh Huynh, Jakob Nordström

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Relating Proof Complexity Measures and Practical Hardness of SAT.

Matti Järvisalo, Arie Matsliah, Jakob Nordström, Stanislav Zivný

Proceedings of the Principles and Practice of Constraint Programming, 2012

Space Complexity in Polynomial Calculus.

Yuval Filmus, Massimo Lauria, Jakob Nordström, Neil Thapen, Noga Ron-Zewi

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions.

Eli Ben-Sasson, Jakob Nordström

Proceedings of the Innovations in Computer Science, 2011

On Minimal Unsatisfiability and Time-Space Trade-offs for <i>k</i>-DNF Resolution.

Jakob Nordström, Alexander A. Razborov

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Separations of Matroid Freeness Properties.

Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie

Electron. Colloquium Comput. Complex., 2010

On the Relative Strength of Pebbling and Resolution.

Jakob Nordström

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution.

Jakob Nordström, Alexander A. Razborov

Electron. Colloquium Comput. Complex., 2009

A Space Hierarchy for k-DNF Resolution.

Eli Ben-Sasson, Jakob Nordström

Electron. Colloquium Comput. Complex., 2009

2008

Short Proofs May Be Spacious : Understanding Space in Resolution.

Jakob Nordström

PhD thesis, 2008

Towards an optimal separation of space and length in resolution.

Jakob Nordström, Johan Håstad

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution.

Eli Ben-Sasson, Jakob Nordström

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Understanding space in resolution: optimal lower bounds and exponential trade-offs.

Eli Ben-Sasson, Jakob Nordström

Proceedings of the Computational Complexity of Discrete Problems, 14.09. - 19.09.2008, 2008

2007

A Simplified Way of Proving Trade-off Results for Resolution.

Jakob Nordström

Electron. Colloquium Comput. Complex., 2007

2006

Narrow proofs may be spacious: separating space and width in resolution.

Jakob Nordström

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006