Page 91 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 91
COMPUTATIONAL ASPECTS OF COMMUTATIVE AND NONCOMMUTATIVE
POSITIVE POLYNOMIALS (MS-77)
Quantum de Finetti theorems and Reznick’s Positivstellensatz
Ion Nechita, ion.nechita@univ-tlse3.fr
CNRS, Toulouse University, France
Coauthors: Alexander Müller-Hermes, David Reeb
We present a proof of Reznick’s quantitative Positivstellensatz using ideas from Quantum In-
formation Theory. This result gives tractable conditions for a positive polynomial to be written
as a sum of squares. We relate such results to de Finetti theorems in Quantum Information.
Tensor Decompositions on Simplicial Complexes: Existence and
Applications
Tim Netzer, tim.netzer@uibk.ac.at
University of Innsbruck, Austria
Coauthors: Gemma De las Cuevas, Matt Hoogsteder Riera, Andreas Klingler
Inspired by the tensor network approach from theoretical quantum physics, we develop a frame-
work to define and analyze invariant decompositions of elements of tensor product spaces. We
define an invariant decomposition with indices arranged on a simplicial complex, which is ex-
plicitly invariant under a given group action. Several versions of such decompositions also
allow to cover positivity of the involved objects. We prove that these decompositions exists
for all invariant/positive tensors, after possibly enriching the structure of the simplicial com-
plex. The approach cannot only be applied to tensor products of matrices (as done in quantum
physics), but to multivariate polynomials as well. This yields new types of decompositions and
complexity measures for polynomials, containing certificates for positivity and symmetries.
Dual nonnegativity certificates and efficient algorithms for rational
sum-of-squares decompositions
Dávid Papp, dpapp@ncsu.edu
North Carolina State University, United States
Coauthor: Maria L. Macaulay
We study the problem of computing rational weighted sum-of-squares (WSOS) certificates for
positive polynomials over a compact semialgebraic set. In the first part of the talk, we introduce
the concept of dual cone certificates, which allows us to interpret vectors from the dual of
the WSOS cone as rigorous nonnegativity certificates. Every polynomial in the interior of the
WSOS cone admits a full-dimensional cone of dual certificates; as a result, rational WSOS
certificates can be constructed from numerically computed dual certificates at little additional
cost. In the second part of the talk, we use this theory to develop an almost entirely numerical
hybrid algorithm for computing the optimal WSOS lower bound of a given polynomial along
with a rational dual certificate, with a polynomial-time computational cost per iteration and
linear rate of convergence. As a special case, we obtain a new polynomial-time algorithm for
certifying the nonnegativity of strictly positive polynomials over an interval.
89
POSITIVE POLYNOMIALS (MS-77)
Quantum de Finetti theorems and Reznick’s Positivstellensatz
Ion Nechita, ion.nechita@univ-tlse3.fr
CNRS, Toulouse University, France
Coauthors: Alexander Müller-Hermes, David Reeb
We present a proof of Reznick’s quantitative Positivstellensatz using ideas from Quantum In-
formation Theory. This result gives tractable conditions for a positive polynomial to be written
as a sum of squares. We relate such results to de Finetti theorems in Quantum Information.
Tensor Decompositions on Simplicial Complexes: Existence and
Applications
Tim Netzer, tim.netzer@uibk.ac.at
University of Innsbruck, Austria
Coauthors: Gemma De las Cuevas, Matt Hoogsteder Riera, Andreas Klingler
Inspired by the tensor network approach from theoretical quantum physics, we develop a frame-
work to define and analyze invariant decompositions of elements of tensor product spaces. We
define an invariant decomposition with indices arranged on a simplicial complex, which is ex-
plicitly invariant under a given group action. Several versions of such decompositions also
allow to cover positivity of the involved objects. We prove that these decompositions exists
for all invariant/positive tensors, after possibly enriching the structure of the simplicial com-
plex. The approach cannot only be applied to tensor products of matrices (as done in quantum
physics), but to multivariate polynomials as well. This yields new types of decompositions and
complexity measures for polynomials, containing certificates for positivity and symmetries.
Dual nonnegativity certificates and efficient algorithms for rational
sum-of-squares decompositions
Dávid Papp, dpapp@ncsu.edu
North Carolina State University, United States
Coauthor: Maria L. Macaulay
We study the problem of computing rational weighted sum-of-squares (WSOS) certificates for
positive polynomials over a compact semialgebraic set. In the first part of the talk, we introduce
the concept of dual cone certificates, which allows us to interpret vectors from the dual of
the WSOS cone as rigorous nonnegativity certificates. Every polynomial in the interior of the
WSOS cone admits a full-dimensional cone of dual certificates; as a result, rational WSOS
certificates can be constructed from numerically computed dual certificates at little additional
cost. In the second part of the talk, we use this theory to develop an almost entirely numerical
hybrid algorithm for computing the optimal WSOS lower bound of a given polynomial along
with a rational dual certificate, with a polynomial-time computational cost per iteration and
linear rate of convergence. As a special case, we obtain a new polynomial-time algorithm for
certifying the nonnegativity of strictly positive polynomials over an interval.
89
