Massimo Lauria

activity

20132020

collaborators

Showing cs.CCShow all

3 papers · 1 filter

cs.CC2020

Clique Is Hard on Average for Regular Resolution

Albert Atserias, Ilario Bonacina, Susanna F. de Rezende +3

We prove that for $k ≪ 4 n$ regular resolution requires length $n^{Ω (k)}$ to establish that an Erdős-Rényi graph with appropriately chosen edge density does not contain a…

cs.CC2015

Tight Size-Degree Bounds for Sums-of-Squares Proofs

Massimo Lauria, Jakob Nordström

We exhibit families of $4$ -CNF formulas over $n$ variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) $d$ but require SOS proofs of size $n^…

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…