### Inhalt des Dokuments

# Kolloquium (Oberseminar)

In our Kolloquium on algorithmic mathematics and complexity theory, guests and members of the group present current topics about their research.

If you are interested in (some of) the talks you are welcome to join us. (For students: Please note that you **cannot** earn any ECTS!)

## Schedule

Usually the talks are on **Wednesdays**,** **start at **14:15 **and last **60-90 minutes**. If not stated otherwise, the Kolloquium takes place in **MA 316**.

Speaker | Title | Date | Starts |
---|---|---|---|

Alperen Ergür | Fewnomial Theory on Average | 17.04.19 | 14:15 |

Philipp di Dio | Shape Reconstruction from Moments | 24.04.19 | 14:15 |

no talk due to holiday | 01.05.19 | ||

Cordian Riener | Vandermonde Varieties, Mirrored Spaces and the Homology of symmetric semialgebraic sets | 08.05.19 | 14:15 |

no talk | 15.05.19 | ||

Felipe Cucker | Computing the Homology of Semialgebraic Sets. II: General Formulas | 22.05.19 | 14:15 |

Peter Bürgisser | Efficient algorithms for moment polytopes and the null cone problem from invariant theory | 29.05.19 | 14:15 |

Paul Breiding | TBA | 05.06.19 | 14:15 |

Ali Ulas Özgür Kisisel | TBA | 12.06.19 | 14:15 |

The schedule will be updated regularly.

### Fewnomial Theory on Average

**Speaker:** Alperen Ergür

If a univariate polynomial has t nonzero terms then it has at most (t-1) many positive real zeros said René Descartes in his La Géométrie around 1637. Since then it's an intriguing puzzle to find the correct multivariate generalization of Descartes' rule. Around 1980, Askold G. Khovanskii showed that a system of real polynomials with n variables and t nonzero terms has at most exponentially many non-degenerate positive real zeros in terms of t. A conjecture attributed to Anatoli Kushnirenko claims that the correct upper bound is of order t^n. This remains open even for n=2! We show that Kushnirenko's prediction holds true for random sparse polynomial systems with Gaussian coefficients of arbitrary variance.

This is joint work with Peter Bürgisser and Josue Tonelli-Cueto.

### Shape Reconstruction from Moments

**Speaker:** Philipp di Dio

Based on recent advances in the theory of moments, especially the Caratheodory numbers, we present the latest results on shape reconstruction from moments based on a new and unified method, the derivatives of moments. Our approach simplifies old and gives new results.

This is joint work with Mario Kummer.

### Vandermonde Varieties, Mirrored Spaces and the Homology of symmetric semialgebraic sets

**Speaker:** Cordian Riener

The abstract is available as pdf-file.

### Computing the Homology of Semialgebraic Sets. II: General Formulas

**Speaker:** Felipe Cucker

This talk will be based on the preprint of the same title (arXiv:1903.10710), which is joint work with Peter Bürgisser and Josue Tonelli Cueto.

We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of semialgebraic sets given by Boolean formulas. The algorithm works in weak exponential time. This means that outside a subset of data having exponentially small measure, the cost of the algorithm is single exponential in the size of the data. This extends the previous work of the authors in arXiv:1807.06435 to arbitrary semialgebraic sets.

All previous algorithms proposed for this problem have doubly exponential complexity (and this is so for almost all input data).

### Efficient algorithms for moment polytopes and the null cone problem from invariant theory

**Speaker:** Peter Bürgisser

Suppose a reductive group G acts linearly on a finite dimensional complex vector space V. The corresponding null cone, which may be thought of the set of ``singular objects'', consists of those vectors that cannot be distinguished from the zero vector by means of polynomial invariants. The null cone was introduced by Hilbert in his seminal work on invariant theory around 1900.

Quite surprisingly, the computational problem of testing membership to the null cone turned out to be of relevance for geometric complexity theory, quantum information theory, and other areas. Notably, a thorough study of the null cone for the simultanous left/right action on tuples of matrices was crucial for finding a deterministic polynomial time algorithm for verifying algebraic identies.

Despite the algebraic nature of the problem, numerical optimization algorithms seem to be the most efficient general methods for solving the null cone problem. This also applies to the related problem of testing membership to moment polytopes, which e.g., generalizes Horn's problem on the eigenvalues of sums of matrices.

The goal of the talk is to provide an overview on these developments.