Tight sum-of-squares lower bounds for binary polynomial optimization problems

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Integer programming (90C10) Semidefinite programming (90C22)

Cites work

A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
Complexity of Null- and Positivstellensatz proofs
Complexity of Positivstellensatz proofs for the knapsack
Dictionary learning and tensor decomposition via the sum-of-squares method
Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
Expander flows, geometric embeddings and graph partitioning
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
Global optimization with polynomials and the problem of moments
Hypercontractivity, sum-of-squares proofs, and their applications
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
Lower bounds on the size of semidefinite programming relaxations
On a representation of the matching polytope via semidefinite liftings
On the hardest problem formulations for the 0/1 Lasserre hierarchy
On the matrix-cut rank of polyhedra.
On the rank of mixed 0,1 polyhedra.
On the Shannon capacity of a graph
On the sum-of-squares degree of symmetric quadratic functions
Robust moment estimation and improved clustering via sum of squares
Sherali-Adams relaxations of the matching polytope
Sparse sums of squares on finite abelian groups and improved semidefinite lifts
Sum-of-squares bounds via Boolean function analysis
Sum-of-squares hierarchies for binary polynomial optimization
Sum-of-squares hierarchy lower bounds for symmetric formulations
Sum-of-squares Lower Bounds for Planted Clique
Sum-of-squares lower bounds for Sherrington-Kirkpatrick via planted affine planes
Summation of a certain series.
When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?

Cited in

(2)

On the bit size of sum-of-squares proofs for symmetric formulations
On the degree automatability of sum-of-squares proofs

This page was built for publication: Tight sum-of-squares lower bounds for binary polynomial optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6955741)