Massimo Lauria

activity

20132023

most citedFrom Small Space to Small Width in Resolution

9 citations · 13 across the 8 of their papers we have counts for

collaborators

Showing 2013Show all

2 papers · 1 filter

cs.CC2013★ 1 cited

Short $Res^{*} (polylog)$ refutations if and only if narrow $Res$ refutations

Massimo Lauria

In this note we show that any $k$ -CNF which can be refuted by a quasi-polynomial $Res^{*} (polylog)$ refutation has a "narrow" refutation in $Res$ (i.e., of…

cs.CC2013

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 $n$ vertices is $c$ -Ramsey if it does not contain either a clique or an independent set of size $c lo g n$ . We define a CNF formula which expresses this pr…

Short Res∗(polylog) refutations if and only if narrow Res refutations

The complexity of proving that a graph is Ramsey

Short $Res^{*} (polylog)$ refutations if and only if narrow $Res$ refutations