Conference Agenda

Overview and details of the sessions of this conference. Please select a date or location to show only sessions at that day or location. Please select a single session for detailed view (with abstracts and downloads if available).

 
Session Overview
Session
MS129, part 2: Sparsity in polynomial systems and applications
Time:
Saturday, 13/Jul/2019:
3:00pm - 5:00pm

Location: Unitobler, F022
104 seats, 126m^2

Presentations
3:00pm - 5:00pm

Sparsity 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.