|
+
PDF
Chat
|
Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone
Circuits, and Weisfeiler-Leman
|
2024
|
Susanna F. de Rezende
Noah Fleming
Duri Andrea Janett
Jakob Nordström
Shuo Pang
|
|
+
PDF
Chat
|
Cut-based Conflict Analysis in Mixed Integer Programming
|
2024
|
Gioni Mexi
Felipe Serrano
Timo Berthold
Ambros Gleixner
Jakob Nordström
|
|
+
PDF
Chat
|
A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds
|
2024
|
Mladen Mikša
Jakob Nordström
|
|
+
PDF
Chat
|
Certified MaxSAT Preprocessing
|
2024
|
Hannes Ihalainen
Andy Oertel
Yong Kiam Tan
Jeremias Berg
Matti Järvisalo
Jakob Nordström
|
|
+
|
Certifying MIP-based Presolve Reductions for 0-1 Integer Linear Programs
|
2024
|
Alexander Hoen
Andy Oertel
Ambros Gleixner
Jakob Nordström
|
|
+
|
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
|
2023
|
Jonas Conneryd
Susanna F. de Rezende
Jakob Nordström
Shuo Pang
Kilian Risse
|
|
+
PDF
Chat
|
Certified Dominance and Symmetry Breaking for Combinatorial Optimisation
|
2023
|
Bart Bogaerts
Stephan Gocht
Ciaran McCreesh
Jakob Nordström
|
|
+
PDF
Chat
|
Near-optimal Lower Bounds on Quantifier Depth and Weisfeiler–Leman Refinement Steps
|
2023
|
Christoph Berkholz
Jakob Nordström
|
|
+
|
Hardness of Approximation in PSPACE and Separation Results for Pebble Games
|
2023
|
Siu Man Chan
Massimo Lauria
Jakob Nordström
Marc Vinyals
|
|
+
|
Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases
|
2023
|
Massimo Lauria
Jakob Nordström
|
|
+
|
Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning
|
2023
|
Gioni Mexi
Timo Berthold
Ambros Gleixner
Jakob Nordström
|
|
+
PDF
Chat
|
Certified Symmetry and Dominance Breaking for Combinatorial Optimisation
|
2022
|
Bart Bogaerts
Stephan Gocht
Ciaran McCreesh
Jakob Nordström
|
|
+
|
Certified Symmetry and Dominance Breaking for Combinatorial Optimisation
|
2022
|
Bart Bogaerts
Stephan Gocht
Ciaran McCreesh
Jakob Nordström
|
|
+
|
Certifying Parity Reasoning Efficiently Using Pseudo-Boolean Proofs
|
2022
|
Stephan Gocht
Jakob Nordström
|
|
+
PDF
Chat
|
Clique Is Hard on Average for Regular Resolution
|
2021
|
Albert Atserias
Ilario Bonacina
Susanna F. de Rezende
Massimo Lauria
Jakob Nordström
Alexander Razborov
|
|
+
PDF
Chat
|
Certifying Parity Reasoning Efficiently Using Pseudo-Boolean Proofs
|
2021
|
Stephan Gocht
Jakob Nordström
|
|
+
PDF
Chat
|
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
|
2021
|
Susanna F. de Rezende
Or Meir
Jakob Nordström
Robert Robere
|
|
+
|
Planning with Learned Binarized Neural Networks Benchmarks for MaxSAT Evaluation 2021
|
2021
|
Buser Say
Scott Sanner
Jo Devriendt
Jakob Nordström
Peter J. Stuckey
|
|
+
|
Clique Is Hard on Average for Regular Resolution
|
2020
|
Albert Atserias
Ilario Bonacina
Susanna F. de Rezende
Massimo Lauria
Jakob Nordström
Alexander Razborov
|
|
+
PDF
Chat
|
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
|
2020
|
Susanna F. de Rezende
Or Meir
Jakob Nordström
Toniann Pitassi
Robert Robere
Marc Vinyals
|
|
+
PDF
Chat
|
KRW Composition Theorems via Lifting
|
2020
|
Susanna F. de Rezende
Or Meir
Jakob Nordström
Toniann Pitassi
Robert Robere
|
|
+
|
Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphs
|
2020
|
Susanna F. de Rezende
Jakob Nordström
Kilian Risse
Dmitry Sokolov
|
|
+
|
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
|
2020
|
Susanna F. de Rezende
Or Meir
Jakob Nordström
Robert Robere
|
|
+
|
Trade-offs between size and degree in polynomial calculus
|
2020
|
Guillaume Lagarde
Jakob Nordström
Dmitry Sokolov
Joseph Swernofsky
|
|
+
PDF
Chat
|
Supercritical Space-Width Trade-offs for Resolution
|
2020
|
Christoph Berkholz
Jakob Nordström
|
|
+
|
Clique Is Hard on Average for Regular Resolution
|
2020
|
Albert Atserias
Ilario Bonacina
Susanna F. de Rezende
Massimo Lauria
Jakob Nordström
Alexander Razborov
|
|
+
|
KRW Composition Theorems via Lifting
|
2020
|
Susanna F. de Rezende
Or Meir
Jakob Nordström
Toniann Pitassi
Robert Robere
|
|
+
|
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
|
2020
|
Susanna F. de Rezende
Or Meir
Jakob Nordström
Robert Robere
|
|
+
|
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
|
2020
|
Susanna F. de Rezende
Or Meir
Jakob Nordström
Toniann Pitassi
Robert Robere
Marc Vinyals
|
|
+
|
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
|
2019
|
Susanna F. de Rezende
Jakob Nordström
Kilian Risse
Dmitry Sokolov
|
|
+
|
Nullstellensatz size-degree trade-offs from reversible pebbling
|
2019
|
Susanna F. de Rezende
Jakob Nordström
Or Meir
Robert Robere
|
|
+
|
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
|
2019
|
Susanna F. de Rezende
Jakob Nordström
Kilian Risse
Dmitry Sokolov
|
|
+
PDF
Chat
|
Clique is hard on average for regular resolution
|
2018
|
Albert Atserias
Ilario Bonacina
Susanna F. de Rezende
Massimo Lauria
Jakob Nordström
Alexander Razborov
|
|
+
PDF
Chat
|
Tight Size-Degree Bounds for Sums-of-Squares Proofs
|
2017
|
Massimo Lauria
Jakob Nordström
|
|
+
|
Supercritical Space-Width Trade-offs for Resolution
|
2016
|
Christoph Berkholz
Jakob Nordström
|
|
+
|
Supercritical space-width trade-offs for resolution
|
2016
|
Christoph Berkholz
Jakob Nordström
|
|
+
PDF
Chat
|
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
|
2016
|
Christoph Berkholz
Jakob Nordström
|
|
+
PDF
Chat
|
Narrow Proofs May Be Maximally Long
|
2016
|
Albert Atserias
Massimo Lauria
Jakob Nordström
|
|
+
|
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps
|
2016
|
Christoph Berkholz
Jakob Nordström
|
|
+
|
Supercritical Space-Width Trade-offs for Resolution
|
2016
|
Christoph Berkholz
Jakob Nordström
|
|
+
PDF
Chat
|
Hardness of Approximation in PSPACE and Separation Results for Pebble Games
|
2015
|
Siu Man Chan
Massimo Lauria
Jakob Nordström
Marc Vinyals
|
|
+
PDF
Chat
|
From Small Space to Small Width in Resolution
|
2015
|
Yuval Filmus
Massimo Lauria
Mladen Mikša
Jakob Nordström
Marc Vinyals
|
|
+
|
Tight size-degree bounds for sums-of-squares proofs
|
2015
|
Massimo Lauria
Jakob Nordström
|
|
+
|
A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds
|
2015
|
Mladen Mikša
Jakob Nordström
|
|
+
|
Tight Size-Degree Bounds for Sums-of-Squares Proofs
|
2015
|
Massimo Lauria
Jakob Nordström
|
|
+
|
Tight Size-Degree Bounds for Sums-of-Squares Proofs
|
2015
|
Massimo Lauria
Jakob Nordström
|
|
+
|
A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds
|
2015
|
Mladen Mikša
Jakob Nordström
|
|
+
|
From Small Space to Small Width in Resolution
|
2014
|
Yuval Filmus
Massimo Lauria
Mladen Mikša
Jakob Nordström
Marc Vinyals
|
|
+
|
Narrow Proofs May Be Maximally Long
|
2014
|
Albert Atserias
Massimo Lauria
Jakob Nordström
|
|
+
PDF
Chat
|
Narrow Proofs May Be Maximally Long
|
2014
|
Albert Atserias
Massimo Lauria
Jakob Nordström
|
|
+
|
Narrow Proofs May Be Maximally Long.
|
2014
|
Albert Atserias
Massimo Lauria
Jakob Nordström
|
|
+
|
Narrow Proofs May Be Maximally Long
|
2014
|
Albert Atserias
Massimo Lauria
Jakob Nordström
|
|
+
|
From Small Space to Small Width in Resolution
|
2014
|
Yuval Filmus
Massimo Lauria
Mladen Mikša
Jakob Nordström
Marc Vinyals
|
|
+
PDF
Chat
|
Pebble Games, Proof Complexity, and Time-Space Trade-offs
|
2013
|
Jakob Nordström
|
|
+
PDF
Chat
|
Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds
|
2013
|
Yuval Filmus
Massimo Lauria
Mladen Mikša
Jakob Nordström
Marc Vinyals
|
|
+
PDF
Chat
|
On the Relative Strength of Pebbling and Resolution
|
2012
|
Jakob Nordström
|
|
+
PDF
Chat
|
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution
|
2011
|
Jakob Nordström
Alexander Razborov
|
|
+
|
Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions
|
2010
|
Eli Ben‐Sasson
Jakob Nordström
|
|
+
PDF
Chat
|
On the Relative Strength of Pebbling and Resolution
|
2010
|
Jakob Nordström
|
|
+
|
On the Relative Strength of Pebbling and Resolution
|
2010
|
Jakob Nordström
|
|
+
|
Separations of Matroid Freeness Properties
|
2010
|
Arnab Bhattacharyya
Elena Grigorescu
Jakob Nordström
Ning Xie
|
|
+
|
On the Relative Strength of Pebbling and Resolution.
|
2010
|
Jakob Nordström
|
|
+
|
On the Relative Strength of Pebbling and Resolution
|
2010
|
Jakob Nordström
|
|
+
|
Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions
|
2010
|
Eli Ben‐Sasson
Jakob Nordström
|
|
+
|
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution
|
2009
|
Jakob Nordström
Alexander Razborov
|
|
+
|
Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution.
|
2009
|
Eli Ben‐Sasson
Jakob Nordström
|
|
+
|
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution
|
2009
|
Jakob Nordström
Alexander Razborov
|
|
+
PDF
Chat
|
Towards an optimal separation of space and length in resolution
|
2008
|
Jakob Nordström
Johan Håstad
|
|
+
|
Towards an Optimal Separation of Space and Length in Resolution
|
2008
|
Jakob Nordström
Johan Håstad
|
|
+
|
Understanding space in resolution: optimal lower bounds and exponential trade-offs
|
2008
|
Eli Ben‐Sasson
Jakob Nordström
|