Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials

DOI10.1007/s10208-021-09496-xOpenAlexW3142079985MaRDI QIDQ2143214

Mareike Dressler, Timo de Wolff, Adam Kurpisz

Publication date: 31 May 2022

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10208-021-09496-x

zbMATH Keywords

sum of squarescertificatenonnegativitysum of nonnegative circuit polynomialshypercube optimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean programming (90C09) Semialgebraic sets and related spaces (14P10)

Related Items (1)

Sum of Squares Bounds for the Empty Integral Hull Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Amoebas, nonnegative polynomials and sums of squares supported on circuits
• Relative entropy optimization and its applications
• Forms derived from the arithmetic-geometric inequality
• Geometric algorithms and combinatorial optimization
• An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
• Sum-of-squares hierarchy lower bounds for symmetric formulations
• High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts
• There are significantly more nonnegative polynomials than sums of squares
• Global Optimization with Polynomials and the Problem of Moments
• Lectures on Modern Convex Optimization
• Approximation of the Stability Number of a Graph via Copositive Programming
• Convex Relaxations and Integrality Gaps
• 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
• Subexponential Algorithms for Unique Games and Related Problems
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
• Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
• Class of global minimum bounds of polynomial functions
• Polynomial algorithms in linear programming
• On the Shannon capacity of a graph
• Lectures on Polytopes
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Sum-of-squares proofs and the quest toward optimal algorithms
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• SOS Is Not Obviously Automatizable, Even Approximately
• Sum of squares lower bounds for refuting any CSP
• On the Bit Complexity of Sum-of-Squares Proofs
• MaxMin allocation via degree lower-bounded arborescences
• Robust moment estimation and improved clustering via sum of squares
• Ideals, Varieties, and Algorithms
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• A Positivstellensatz for Sums of Nonnegative Circuit Polynomials
• 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
• 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
• How to Sell Hyperedges: The Hypermatching Assignment Problem
• Expander flows, geometric embeddings and graph partitioning
• Complexity of Positivstellensatz proofs for the knapsack
• Complexity of Null- and Positivstellensatz proofs

This page was built for publication: Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials