All reports by Author Monaldo Mastrolilli:

__
TR17-157
| 13th October 2017
__

Monaldo Mastrolilli#### High Degree Sum of Squares Proofs, Bienstock-Zuckerberg hierarchy and Chvatal-Gomory cuts

Revisions: 2

__
TR16-079
| 2nd May 2016
__

Adam Kurpisz, Samuli Lepp\"anen, Monaldo Mastrolilli#### Sum-of-squares hierarchy lower bounds for symmetric formulations

Monaldo Mastrolilli

Chvatal-Gomory (CG) cuts and the Bienstock-Zuckerberg hierarchy capture useful linear programs that the standard bounded degree Lasserre/Sum-of-Squares (SOS) hierarchy fails to capture.

In this paper we present a novel polynomial time SOS hierarchy for 0/1 problems with a custom subspace of high degree polynomials (not the standard subspace of low-degree ... more >>>

Adam Kurpisz, Samuli Lepp\"anen, Monaldo Mastrolilli

We introduce a method for proving Sum-of-Squares (SoS)/ Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study of the positive semidefiniteness to the analysis of ``well-behaved'' univariate polynomial inequalities.

We illustrate the technique on ... more >>>