Massimo Lauria

collaborators

2 papers

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…