9 citations · 15 across the 11 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.CC2015
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…
cs.CC2015
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^…