Jakob Nordström

ORCID

Publication Activity (10 Years)

Years Active: 2005-2024
Publications (10 Years): 78

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

SAT

Royal Institute of Technology, Stockholm, Sweden (PHD)

Education History

Royal Institute of Technology, Stockholm, Sweden

PHD

Publications

Matthew J. McIlree, Ciaran McCreesh, Jakob Nordström
Proof Logging for the Circuit Constraint. CPAIOR (2) (2024)
Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere
KRW Composition Theorems via Lifting. Comput. Complex. 33 (1) (2024)
Stephan Gocht, Ciaran McCreesh, Magnus O. Myreen, Jakob Nordström, Andy Oertel, Yong Kiam Tan
End-to-End Verification for Subgraph Solving. AAAI (2024)
Alexander Hoen, Andy Oertel, Ambros M. Gleixner, Jakob Nordström
Certifying MIP-Based Presolve Reductions for 0-1 Integer Linear Programs. CPAIOR (1) (2024)
Emir Demirovic, Ciaran McCreesh, Matthew J. McIlree, Jakob Nordström, Andy Oertel, Konstantin Sidorov
Pseudo-Boolean Reasoning About States and Transitions to Certify Dynamic Programming and Decision Diagram Algorithms. CP (2024)
Hannes Ihalainen, Andy Oertel, Yong Kiam Tan, Jeremias Berg, Matti Järvisalo, Magnus O. Myreen, Jakob Nordström
Certified MaxSAT Preprocessing. IJCAR (1) (2024)
Jeremias Berg, Bart Bogaerts, Jakob Nordström, Andy Oertel, Tobias Paxian, Dieter Vandesande
Certifying Without Loss of Generality Reasoning in Solution-Improving Maximum Satisfiability. CP (2024)
Hannes Ihalainen, Andy Oertel, Yong Kiam Tan, Jeremias Berg, Matti Järvisalo, Jakob Nordström
Certified MaxSAT Preprocessing. CoRR (2024)
Christoph Berkholz, Jakob Nordström
Near-optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. J. ACM 70 (5) (2023)
Bart Bogaerts, Stephan Gocht, Ciaran McCreesh, Jakob Nordström
Certified Dominance and Symmetry Breaking for Combinatorial Optimisation. J. Artif. Intell. Res. 77 (2023)
Stephan Gocht, Ruben Martins, Jakob Nordström, Andy Oertel
Certified CNF Translations for Pseudo-Boolean Solving (Extended Abstract). IJCAI (2023)
Gioni Mexi, Timo Berthold, Ambros M. Gleixner, Jakob Nordström
Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning. CP (2023)
Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström, Shuo Pang, Kilian Risse
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz. FOCS (2023)
Jeremias Berg, Bart Bogaerts, Jakob Nordström, Andy Oertel, Dieter Vandesande
Certified Core-Guided MaxSAT Solving. CADE (2023)
Siu Man Chan, Massimo Lauria, Jakob Nordström, Marc Vinyals
Hardness of Approximation in PSPACE and Separation Results for Pebble Games. CoRR (2023)
Gioni Mexi, Timo Berthold, Ambros M. Gleixner, Jakob Nordström
Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning. CoRR (2023)
Massimo Lauria, Jakob Nordström
Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases. CoRR (2023)
Stephan Gocht, Jakob Nordström
Certifying Parity Reasoning Efficiently Using Pseudo-Boolean Proofs. CoRR (2022)
Olaf Beyersdorff, Armin Biere, Vijay Ganesh, Jakob Nordström, Andy Oertel
Theory and Practice of SAT and Combinatorial Solving (Dagstuhl Seminar 22411). Dagstuhl Reports 12 (10) (2022)
Stephan Gocht, Ciaran McCreesh, Jakob Nordström
An Auditable Constraint Programming Solver. CP (2022)
Bart Bogaerts, Stephan Gocht, Ciaran McCreesh, Jakob Nordström
Certified Symmetry and Dominance Breaking for Combinatorial Optimisation. AAAI (2022)
Stephan Gocht, Ruben Martins, Jakob Nordström, Andy Oertel
Certified CNF Translations for Pseudo-Boolean Solving. SAT (2022)
Bart Bogaerts, Stephan Gocht, Ciaran McCreesh, Jakob Nordström
Certified Symmetry and Dominance Breaking for Combinatorial Optimisation. CoRR (2022)
Daniela Kaufmann, Paul Beame, Armin Biere, Jakob Nordström
Adding Dual Variables to Algebraic Reasoning for Gate-Level Multiplier Verification. DATE (2022)
Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov
Automating algebraic proof systems is NP-hard. STOC (2021)
Buser Say, Scott Sanner, Jo Devriendt, Jakob Nordström, Peter J. Stuckey
Planning with Learned Binarized Neural Networks Benchmarks for MaxSAT Evaluation 2021. CoRR (2021)
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
Clique Is Hard on Average for Regular Resolution. J. ACM 68 (4) (2021)
Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Dmitry Sokolov
The Power of Negative Reasoning. Computational Complexity Conference (2021)
Jo Devriendt, Ambros M. Gleixner, Jakob Nordström
Learn to relax: Integrating 0-1 integer linear programming with pseudo-Boolean conflict-driven search. Constraints An Int. J. 26 (1) (2021)
Jo Devriendt, Stephan Gocht, Emir Demirovic, Jakob Nordström, Peter J. Stuckey
Cutting to the Core of Pseudo-Boolean Optimization: Combining Core-Guided Search with Cutting Planes Reasoning. AAAI (2021)
Susanna F. de Rezende, Or Meir, Jakob Nordström, Robert Robere
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. Comput. Complex. 30 (1) (2021)
Susanna F. de Rezende, Jakob Nordström, Marc Vinyals
How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity). Electron. Colloquium Comput. Complex. 28 (2021)
Stephan Gocht, Jakob Nordström
Certifying Parity Reasoning Efficiently Using Pseudo-Boolean Proofs. AAAI (2021)
Stephan Gocht, Jakob Nordström, Ruben Martins
Certifying CNF Encodings of Pseudo-Boolean Constraints (abstract). PxTP (2021)
Stephan Gocht, Ciaran McCreesh, Jakob Nordström
Subgraph Isomorphism Meets Cutting Planes: Solving With Certified Solutions. IJCAI (2020)
Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere
KRW Composition Theorems via Lifting. FOCS (2020)
Vincent Liew, Paul Beame, Jo Devriendt, Jan Elffers, Jakob Nordström
Verifying Properties of Bit-vector Multiplication Using Cutting Planes Reasoning. FMCAD (2020)
Stephan Gocht, Ross McBride, Ciaran McCreesh, Jakob Nordström, Patrick Prosser, James Trimble
Certifying Solvers for Clique and Maximum Common (Connected) Subgraph Problems. CP (2020)
Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Marc Vinyals
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. CoRR (2020)
Janne I. Kokkala, Jakob Nordström
Using Resolution Proofs to Analyse CDCL Solvers. CP (2020)
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
Clique Is Hard on Average for Regular Resolution. CoRR (2020)
Buser Say, Jo Devriendt, Jakob Nordström, Peter J. Stuckey
Theoretical and Experimental Results for Planning with Learned Binarized Neural Network Transition Models. CP (2020)
Or Meir, Jakob Nordström, Robert Robere, Susanna F. de Rezende
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. Electron. Colloquium Comput. Complex. 27 (2020)
Marc Vinyals, Jan Elffers, Jan Johannsen, Jakob Nordström
Simplified and Improved Separations Between Regular and General Resolution by Lifting. SAT (2020)
Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna F. de Rezende
Automating Algebraic Proof Systems is NP-Hard. Electron. Colloquium Comput. Complex. 27 (2020)
Jan Elffers, Jakob Nordström
A Cardinal Improvement to Pseudo-Boolean Solving. AAAI (2020)
Christoph Berkholz, Jakob Nordström
Supercritical Space-Width Trade-offs for Resolution. SIAM J. Comput. 49 (1) (2020)
Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Marc Vinyals
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. FOCS (2020)
Susanna F. de Rezende, Or Meir, Jakob Nordström, Robert Robere
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. CoRR (2020)
Jan Elffers, Stephan Gocht, Ciaran McCreesh, Jakob Nordström
Justifying All Differences Using Pseudo-Boolean Reasoning. AAAI (2020)
Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere
KRW Composition Theorems via Lifting. CoRR (2020)
Guillaume Lagarde, Jakob Nordström, Dmitry Sokolov, Joseph Swernofsky
Trade-Offs Between Size and Degree in Polynomial Calculus. ITCS (2020)
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. Computational Complexity Conference (2020)
Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere
KRW Composition Theorems via Lifting. Electron. Colloquium Comput. Complex. 27 (2020)
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. CoRR (2019)
Susanna F. de Rezende, Jakob Nordström, Or Meir, Robert Robere
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. Computational Complexity Conference (2019)
Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. Electron. Colloquium Comput. Complex. 26 (2019)
Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna F. de Rezende
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. Electron. Colloquium Comput. Complex. 26 (2019)
Stephan Gocht, Jakob Nordström, Amir Yehudayoff
On Division Versus Saturation in Pseudo-Boolean Solving. IJCAI (2019)
Jan Elffers, Jesús Giráldez-Cru, Stephan Gocht, Jakob Nordström, Laurent Simon
Seeking Practical CDCL Insights from Theoretical SAT Benchmarks. IJCAI (2018)
Jan Elffers, Jesús Giráldez-Cru, Jakob Nordström, Marc Vinyals
Using Combinatorial Benchmarks to Probe the Reasoning Power of Pseudo-Boolean Solvers. SAT (2018)
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
Clique is hard on average for regular resolution. STOC (2018)
Jan Elffers, Jakob Nordström
Divide and Conquer: Towards Faster Pseudo-Boolean Solving. IJCAI (2018)
Marc Vinyals, Jan Elffers, Jesús Giráldez-Cru, Stephan Gocht, Jakob Nordström
In Between Resolution and Cutting Planes: A Study of Proof Systems for Pseudo-Boolean SAT Solving. SAT (2018)
Albert Atserias, Jakob Nordström, Pavel Pudlák, Rahul Santhanam
Proof Complexity (Dagstuhl Seminar 18051). Dagstuhl Reports 8 (1) (2018)
Joël Alwen, Susanna F. de Rezende, Jakob Nordström, Marc Vinyals
Cumulative Space in Black-White Pebbling and Resolution. ITCS (2017)
Massimo Lauria, Jan Elffers, Jakob Nordström, Marc Vinyals
CNFgen: A Generator of Crafted Benchmarks. SAT (2017)
Massimo Lauria, Jakob Nordström
Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases. Computational Complexity Conference (2017)
Massimo Lauria, Jakob Nordström
Tight Size-Degree Bounds for Sums-of-Squares Proofs. Comput. Complex. 26 (4) (2017)
Christoph Berkholz, Jakob Nordström
Supercritical Space-Width Trade-offs for Resolution. Electron. Colloquium Comput. Complex. 23 (2016)
Christoph Berkholz, Jakob Nordström
Supercritical Space-Width Trade-Offs for Resolution. ICALP (2016)
Susanna F. de Rezende, Jakob Nordström, Marc Vinyals
How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity). FOCS (2016)
Christoph Berkholz, Jakob Nordström
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. LICS (2016)
Christoph Berkholz, Jakob Nordström
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. CoRR (2016)
Christoph Berkholz, Jakob Nordström
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. Electron. Colloquium Comput. Complex. 23 (2016)
Christoph Berkholz, Jakob Nordström
Supercritical Space-Width Trade-offs for Resolution. CoRR (2016)
Jan Elffers, Jan Johannsen, Massimo Lauria, Thomas Magnard, Jakob Nordström, Marc Vinyals
Trade-offs Between Time and Memory in a Tighter Model of CDCL SAT Solvers. SAT (2016)
Albert Atserias, Massimo Lauria, Jakob Nordström
Narrow Proofs May Be Maximally Long. ACM Trans. Comput. Log. 17 (3) (2016)
Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen
Space Complexity in Polynomial Calculus. SIAM J. Comput. 44 (4) (2015)
Jakob Nordström
On the interplay between proof complexity and SAT solving. ACM SIGLOG News 2 (3) (2015)
Siu Man Chan, Massimo Lauria, Jakob Nordström, Marc Vinyals
Hardness of Approximation in PSPACE and Separation Results for Pebble Games. FOCS (2015)
Mladen Miksa, Jakob Nordström
A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds. Computational Complexity Conference (2015)
Armin Biere, Vijay Ganesh, Martin Grohe, Jakob Nordström, Ryan Williams
Theory and Practice of SAT Solving (Dagstuhl Seminar 15171). Dagstuhl Reports 5 (4) (2015)
Mladen Miksa, Jakob Nordström
A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds. Electron. Colloquium Comput. Complex. 22 (2015)
Mladen Miksa, Jakob Nordström
A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds. CoRR (2015)
Massimo Lauria, Jakob Nordström
Tight Size-Degree Bounds for Sums-of-Squares Proofs. Computational Complexity Conference (2015)
Massimo Lauria, Jakob Nordström
Tight Size-Degree Bounds for Sums-of-Squares Proofs. Electron. Colloquium Comput. Complex. 22 (2015)
Massimo Lauria, Jakob Nordström
Tight Size-Degree Bounds for Sums-of-Squares Proofs. CoRR (2015)
Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals
From Small Space to Small Width in Resolution. ACM Trans. Comput. Log. 16 (4) (2015)
Jakob Nordström
A (Biased) Proof Complexity Survey for SAT Practitioners. SAT (2014)
Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals
From Small Space to Small Width in Resolution. CoRR (2014)
Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals
From Small Space to Small Width in Resolution. Electron. Colloquium Comput. Complex. 21 (2014)
Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals
From Small Space to Small Width in Resolution. STACS (2014)
Albert Atserias, Massimo Lauria, Jakob Nordström
Narrow Proofs May Be Maximally Long. Computational Complexity Conference (2014)
Mladen Miksa, Jakob Nordström
Long Proofs of (Seemingly) Simple Formulas. SAT (2014)
Albert Atserias, Massimo Lauria, Jakob Nordström
Narrow Proofs May Be Maximally Long. CoRR (2014)
Albert Atserias, Massimo Lauria, Jakob Nordström
Narrow Proofs May Be Maximally Long. Electron. Colloquium Comput. Complex. 21 (2014)
Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals
Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds - (Extended Abstract). ICALP (1) (2013)
Chris Beck, Jakob Nordström, Bangsheng Tang
Some trade-off results for polynomial calculus: extended abstract. STOC (2013)
Jakob Nordström
Pebble Games, Proof Complexity, and Time-Space Trade-offs. Log. Methods Comput. Sci. 9 (3) (2013)

Jakob Nordström.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Jakob Nordström