3:00pm - 5:00pmSparsity in polynomial systems and applications
Chair(s): Timo de Wolff (Technische Universität Berlin, Germany), Mareike Dressler (University of California, San Diego, CA, USA)
In this session we bring together researchers working in different areas involving sparsity in applications and sparse polynomial systems. The principle of sparsity is to represent a structure by functions, e.g., polynomials, with as few variables or terms as possible. It is ubiquitous in various areas and problems, where algebra and geometry play a key role. Recently, it has been succesfully applied to problems such as sparse interpolation, polynomial optimization, sparse elimination, fewnomial theory, or tensor decomposition.
This minisymposium provides an opportunity to learn about a selection of these recent developments and explore new potential applications of sparsity.
(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)
Filling a much-needed gap in the literature
Bruce Reznick
University of Illinois Urbana-Champaign, IL, USA
Many of the early examples in the study of psd forms which are not sos (such as the Motzkin form) arise from monomial substitution into the arithmetic-geometric inequality. Thirty years ago, the speaker gave a necessary and sufficient condition for such a form to be sos or not ({it Math. Ann.,} 283 (1989), 431-464 (MR 90i.11043)). He also announced that certain results would appear as part of the "in preparation" paper "Midpoint polytopes and the map $x_i mapsto x_i^k$". That paper never appeared, and this talk is an attempt to reconstruct the missing material.
Computing elimination ideals of likelihood equations
Xiaoxian Tang1, Timo de Wolff2, Rukai Zhao1
1Texas A&M University, TX, USA, 2Technische Universität Berlin, Germany
We develop a probabilistic algorithm for computing elimination ideals of likelihood equations. We show experimentally that it is far more efficient than directly computing Groebner bases or the known interpolation method for medium to large size models. Furthermore, we deduce discriminants of the elimination ideals, which play a central role in real root classification. In particular, we compute the discriminants of the 3 by 3 matrix model and one Jukes-Cantor model in phylogenetics (with sizes over 30 GB and 8 GB text files, respectively).
Nonnegative polynomials and circuit polynomials
Jie Wang
Peking University, China
The concept of sums of nonnegative circuit polynomials (SONC) was introduced as a new certificate of nonnegativity of polynomials, which was proved to be efficient in many cases. It is natural to ask which types of nonnegative polynomials admit SONC decompositions and how big the gap between the PSD cone and the SONC cone is. In this talk, we will consider these questions. Moreover, we clarify an important fact that every SONC polynomial decomposes into a sum of nonnegative circuit polynomials with the same support, which reveals the advantage of SONC decompositions for certifying nonnegativity of sparse polynomials compared with the classical SOS decompositions.
An Experimental Classification of Maximal Mediated Sets
Oguzhan Yürük, Timo de Wolff, Olivia Röhrig
Technische Universität Berlin, Germany
Maximal mediated sets (MMS), first introduced by Bruce Reznick, arise as a natural structure in the study of nonnegative polynomials supported on circuits. Due to Reznick's, de Wolff's, and Iliman's results, given a nonnegative polynomial $f$ supported on a circuit $C$ with vertex set $Delta$, $f$ is a sum of squares if and only if the non-vertex element of $C$ is in the MMS of $Delta$. In this project, we classify MMS experimentally. As a main theoretical result, we show that an MMS is determined by its underlying lattice. This is joint work with Olivia Röhrig and Timo de Wolff.