9 citations · 15 across the 11 of their papers we have counts for
15 papers · 1 filter
Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases
Massimo Lauria, Jakob Nordström
We consider the graph -colouring problem encoded as a set of polynomial equations in the standard way over -valued variables. We prove that there are bounded-degree graphs…
Hardness of Approximation in PSPACE and Separation Results for Pebble Games
Siu Man Chan, Massimo Lauria, Jakob Nordström +1
We consider the pebble game on DAGs with bounded fan-in introduced in [Paterson and Hewitt '70] and the reversible version of this game in [Bennett '89], and study the question of…
Clique Is Hard on Average for Regular Resolution
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende +3
We prove that for regular resolution requires length to establish that an Erdős-Rényi graph with appropriately chosen edge density does not contain a…
KRW Composition Theorems via Lifting
Susanna F. de Rezende, Or Meir, Jakob Nordström +2
One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., ). Karchmer, Raz…
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
Susanna F. de Rezende, Or Meir, Jakob Nordström +1
We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph can be reversibly pebbl…
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
Susanna F. de Rezende, Or Meir, Jakob Nordström +3
We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget wit…
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
Susanna F. de Rezende, Jakob Nordström, Kilian Risse +1
We show exponential lower bounds on resolution proof length for pigeonhole principle (PHP) formulas and perfect matching formulas over highly unbalanced, sparse expander graphs, th…
Supercritical Space-Width Trade-offs for Resolution
Christoph Berkholz, Jakob Nordström
We show that there are CNF formulas which can be refuted in resolution in both small space and small width, but for which any small-width proof must have space exceeding by far the…
A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds
Mladen Mikša, Jakob Nordström
We study the problem of obtaining lower bounds for polynomial calculus (PC) and polynomial calculus resolution (PCR) on proof degree, and hence by [Impagliazzo et al. '99] also on…
Tight Size-Degree Bounds for Sums-of-Squares Proofs
Massimo Lauria, Jakob Nordström
We exhibit families of -CNF formulas over variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) but require SOS proofs of size $n^…
From Small Space to Small Width in Resolution
Yuval Filmus, Massimo Lauria, Mladen Mikša +2
In 2003, Atserias and Dalmau resolved a major open question about the resolution proof system by establishing that the space complexity of CNF formulas is always an upper bound on…
Narrow Proofs May Be Maximally Long
Albert Atserias, Massimo Lauria, Jakob Nordström
We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size n^Omega(w). This shows that the simple co…
Separations of Matroid Freeness Properties
Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström +1
Properties of Boolean functions on the hypercube invariant with respect to linear transformations of the domain are among the most well-studied properties in the context of propert…
On the Relative Strength of Pebbling and Resolution
Jakob Nordström
The last decade has seen a revival of interest in pebble games in the context of proof complexity. Pebbling has proven a useful tool for studying resolution-based proof systems whe…
Towards an Optimal Separation of Space and Length in Resolution
Jakob Nordström, Johan Håstad
Most state-of-the-art satisfiability algorithms today are variants of the DPLL procedure augmented with clause learning. The main bottleneck for such algorithms, other than the obv…