27 papers
Sums of squares in polynomial time
Nikolas Gärtner, Victor Magron, Frank Vallentin
In this paper, we analyze the bit complexity of deciding whether a given polynomial can be represented as a sum of squares of polynomials. We show that the weak membership problem…
Mixtures Closest to a Given Measure: A Semidefinite Programming Approach
SreÄko ÄuraÅ¡inoviÄ, Srećko Đurašinović, Jean-Bernard Lasserre +1
Mixture models, such as Gaussian mixture models, are widely used in machine learning to represent complex data distributions. A key challenge, especially in high-dimensional settin…
Convergence rates for polynomial optimization on set products
Victor Magron
We consider polynomial optimization problems on Cartesian products of basic compact semialgebraic sets. The solution of such problems can be approximated as closely as desired by h…
The bulk spectral gap is semi-decidable: a convergent family of certified upper bounds
Xiangling Xu, Matthias Schötz, Jie Wang +4
Determining spectral gaps in the thermodynamic limit is a central challenge in quantum many-body physics. Existing rigorous methods are largely limited to special settings, while v…
Quantitative semidefinite certificates for ground-state energies of Pauli Hamiltonians
Igor Klep, Nando Leijenhorst, Victor Magron
The -local Hamiltonian problem is a central model for quantum many-body systems and Hamiltonian complexity. Semidefinite programming and noncommutative sum-of-squares hierarchie…
Duality attainment and strict feasibility of the generalized moment problem and its relaxations
Sami Halaseh, Victor Magron, Mateusz Skomra
The generalized moment problem (GMP) is an infinite dimensional linear problem over the cone of finite nonnegative Borel measures. When a GMP instance involves finitely many polyno…