The thesis derives new approximation algorithms and conditional/unconditional lower bounds for CSPs, polynomial optimization over the sphere, and matrix p-to-q norms.
Convergence of SDP hierarchies for polynomial optimization on the hypersphere
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We show how to bound the accuracy of a family of semi-definite programming relaxations for the problem of polynomial optimization on the hypersphere. Our method is inspired by a set of results from quantum information known as quantum de Finetti theorems. In particular, we prove a de Finetti theorem for a special class of real symmetric matrices to establish the existence of approximate representing measures for moment matrix relaxations.
fields
cs.CC 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Some Applications and Limitations of Convex Optimization Hierarchies for Discrete and Continuous Optimization Problems
The thesis derives new approximation algorithms and conditional/unconditional lower bounds for CSPs, polynomial optimization over the sphere, and matrix p-to-q norms.