SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization

Adam Kurpisz, Aaron Potechin, Elias Wirth

Type: Article

Publication Date: 2025-02-06

Citations: 0

DOI: https://doi.org/10.1287/moor.2024.0422

View Publication

Locations

Mathematics of Operations Research - View

Similar Works

Action	Title	Year	Authors
+	SoS certification for symmetric quadratic functions and its connection to constrained boolean hypercube optimization	2021	Adam Kurpisz Aaron Potechin Elias Samuel Wirth
+	SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization	2021	Adam Kurpisz Aaron Potechin Elias Samuel Wirth
+	Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials	2018	Mareike Dressler Adam Kurpisz Timo de Wolff
+	Optimization over the Boolean Hypercube via Sums of Nonnegative Circuit Polynomials.	2018	Mareike Dressler Adam Kurpisz Timo de Wolff
+ PDF Chat	Optimization Over the Boolean Hypercube Via Sums of Nonnegative Circuit Polynomials	2021	Mareike Dressler Adam Kurpisz Timo de Wolff
+	New Dependencies of Hierarchies in Polynomial Optimization	2019	Adam Kurpisz Timo de Wolff
+	On the sum-of-squares degree of symmetric quadratic functions	2016	Troy Lee Anupam Prakash Ronald de Wolf Henry Yuen
+	New Dependencies of Hierarchies in Polynomial Optimization	2019	Adam Kurpisz Timo de Wolff
+ PDF Chat	Relaxations for binary polynomial optimization via signed certificates	2024	Liding Xu Leo Liberti
+	Sum-Of-Squares Bounds via Boolean Function Analysis	2019	Adam Kurpisz
+	Symmetric Sums of Squares over $k$-Subset Hypercubes	2016	Annie Raymond James Saunderson Mohit Singh Rekha R. Thomas
+	Symmetric Sums of Squares over $k$-Subset Hypercubes	2016	Annie Raymond James Saunderson Mohit Singh Rekha R. Thomas
+	New SDP Roundings and Certifiable Approximation for Cubic Optimization	2023	Jun-Ting Hsieh Pravesh K. Kothari Lucas Pesenti Luca Trevisan
+ PDF Chat	New Dependencies of Hierarchies in Polynomial Optimization	2019	Adam Kurpisz Timo de Wolff
+ PDF Chat	Error bounds for polynomial optimization over the hypercube using putinar type representations	2014	Victor Magron
+	High Degree Sum of Squares Proofs, Bienstock-Zuckerberg hierarchy and Chvatal-Gomory cuts	2017	Monaldo Mastrolilli
+	On the Bit Complexity of Sum-of-Squares Proofs	2017	Prasad Raghavendra Benjamin Weitz
+ PDF Chat	High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts	2020	Monaldo Mastrolilli
+	High Degree Sum of Squares Proofs, Bienstock-Zuckerberg hierarchy and Chvatal-Gomory cuts	2017	Monaldo Mastrolilli
+	Sums of Squares on the Hypercube	2014	Grigoriy Blekherman João Gouveia James Pfeiffer

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (51)

Action	Title	Year	Authors
+ PDF Chat	Sparse sum-of-squares certificates on finite abelian groups	2015	Hamza Fawzi James Saunderson Pablo A. Parrilo
+	An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs	2001	Jean B. Lasserre
+ PDF Chat	Complexity of Semi-algebraic Proofs	2002	Dima Grigoriev Edward Hirsch Dmitrii V. Ṗasechnik
+ PDF Chat	Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming	1995	Michel X. Goemans David P. Williamson
+ PDF Chat	Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method	2015	Boaz Barak Jonathan A. Kelner David Steurer
+	The Chebyshev polynomials	1974	T. J. Rivlin
+ PDF Chat	A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming	2003	Monique Laurent
+	On the Shannon capacity of a graph	1979	László Lovász
+	Complexity of Null- and Positivstellensatz proofs	2001	Dima Grigoriev Nicolai Vorobjov
+ PDF Chat	Some NP-complete problems in quadratic and nonlinear programming	1987	Katta G. Murty Santosh N. Kabadi