9 citations · 13 across the 8 of their papers we have counts for
11 papers
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…
Verification and generation of unrefinable partitions
Riccardo Aragona, Lorenzo Campioni, Roberto Civino +1
Unrefinable partitions are a subset of partitions into distinct parts which satisfy an additional unrefinability property. More precisely, being an unrefinable partition means that…
On the maximal part in unrefinable partitions of triangular numbers
Riccardo Aragona, Lorenzo Campioni, Roberto Civino +1
A partition into distinct parts is refinable if one of its parts can be replaced by two different integers which do not belong to the partition and whose sum is , and it is…
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…
Circular (Yet Sound) Proofs
Albert Atserias, Massimo Lauria
Proofs in propositional logic are typically presented as trees of derived formulas or, alternatively, as directed acyclic graphs of derived formulas. This distinction between tree-…
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…
Short refutations if and only if narrow refutations
Massimo Lauria
In this note we show that any -CNF which can be refuted by a quasi-polynomial refutation has a "narrow" refutation in (i.e., of…
The complexity of proving that a graph is Ramsey
Massimo Lauria, Pavel Pudlák, Vojtěch Rödl +1
We say that a graph with vertices is -Ramsey if it does not contain either a clique or an independent set of size . We define a CNF formula which expresses this pr…