Publication:2191774

DOI10.1007/978-3-319-33461-5_30zbMath1445.90056arXiv1407.1746OpenAlexW2945452012WikidataQ127830866 ScholiaQ127830866MaRDI QIDQ2191774

Samuli Leppänen, Monaldo Mastrolilli, Adam Kurpisz

Publication date: 26 June 2020

Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.1746

zbMATH Keywords

integrality gapsum-of-squares hierarchy

Mathematics Subject Classification ID

Semidefinite programming (90C22) Integer programming (90C10) Linear programming (90C05)

Related Items (15)

Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem ⋮ Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ The poset of Specht ideals for hyperoctahedral groups ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ The Spectrum of the Grigoriev–Laurent Pseudomoments ⋮ Unnamed Item ⋮ Symmetric sums of squares over \(k\)-subset hypercubes ⋮ Symmetric matrices whose entries are linear functions ⋮ A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian ⋮ Lift \& project systems performing on the partial-vertex-cover polytope ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Symmetric ideals, Specht polynomials and solutions to symmetric systems of equations ⋮ High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sums of squares on the hypercube
• Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
• Global Optimization with Polynomials and the Problem of Moments
• On a Representation of the Matching Polytope Via Semidefinite Liftings
• On the Matrix-Cut Rank of Polyhedra
• Convex Relaxations and Integrality Gaps
• Sum-of-squares Lower Bounds for Planted Clique
• Sum of Squares Lower Bounds from Pairwise Independence
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy
• Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
• A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem
• Primal-Dual Schema for Capacitated Covering Problems
• On Column-Restricted and Priority Covering Integer Programs
• On the power of unique 2-prover 1-round games
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Faces for a linear inequality in 0–1 variables
• Sum-of-squares proofs and the quest toward optimal algorithms
• Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems.
• Subset Algebra Lift Operators for 0-1 Integer Programming
• Semidefinite Optimization and Convex Algebraic Geometry
• CSP gaps and reductions in the lasserre hierarchy
• On the sum-of-squares degree of symmetric quadratic functions
• Computation of the Lasserre Ranks of Some Polytopes
• Hypercontractivity, sum-of-squares proofs, and their applications
• When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Complexity of Positivstellensatz proofs for the knapsack

This page was built for publication: Sum-of-squares hierarchy lower bounds for symmetric formulations