Sum-of-squares hierarchy lower bounds for symmetric formulations
From MaRDI portal
Publication:2191774
DOI10.1007/s10107-019-01398-9zbMath1445.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
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Sum-of-squares hierarchy lower bounds for symmetric formulations
