Sum of Squares Bounds for the Empty Integral Hull Problem

DOI10.1145/3597066.3597098OpenAlexW4383213608WikidataQ131124559 ScholiaQ131124559MaRDI QIDQ6081967

Adam Kurpisz, Unnamed Author

Publication date: 3 November 2023

Published in: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3597066.3597098

zbMATH Keywords

combinatorial optimizationcontinued fractionssum-of-squarestri-diagonal matricesBoolean analysis

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computational aspects in algebraic geometry (14Qxx) Real algebraic and real-analytic geometry (14Pxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
• Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
• Noisy tensor completion via the sum-of-squares hierarchy
• Sum-of-squares hierarchy lower bounds for symmetric formulations
• Connecting optimization with spectral analysis of tri-diagonal matrices
• On the Matrix-Cut Rank of Polyhedra
• Sum-of-squares Lower Bounds for Planted Clique
• Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
• Lower Bounds on the Size of Semidefinite Programming Relaxations
• On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy
• Class of global minimum bounds of polynomial functions
• On the Shannon capacity of a graph
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems.
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• Sum of squares lower bounds for refuting any CSP
• Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube
• Analysis of Boolean Functions
• CSP gaps and reductions in the lasserre hierarchy
• Robust moment estimation and improved clustering via sum of squares
• The Power of Sherali--Adams Relaxations for General-Valued CSPs
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• On the sum-of-squares degree of symmetric quadratic functions
• Computation of the Lasserre Ranks of Some Polytopes
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
• 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
• Expander flows, geometric embeddings and graph partitioning
• Sum-of-squares hierarchies for binary polynomial optimization
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Complexity of Positivstellensatz proofs for the knapsack
• Complexity of Null- and Positivstellensatz proofs

This page was built for publication: Sum of Squares Bounds for the Empty Integral Hull Problem