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!)

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: Alperen Ergür [8]

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.

Speaker: Philipp di Dio [9]

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.

Speaker: Cordian Riener [10]

The abstract is available as pdf-file [11].

Speaker: Felipe Cucker

This talk will be based on the preprint of the same title (arXiv:1903.10710 [12]), 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 [13] to arbitrary semialgebraic sets. 
All previous algorithms proposed for this problem have doubly exponential complexity (and this is so for almost all input data).

Speaker: Peter Bürgisser [14]

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.

Speaker: Paul Breiding [15]

Consider the set of solutions to a system of polynomial equations in many variables. An algebraic manifold is an open submanifold of such a set. I will discuss a new method for computing integrals and sampling from distributions on algebraic manifolds. This method is based on intersecting the manifold with linear spaces. It produces i.i.d. samples, works in the presence of multiple connected components, and is simple to implement. I discuss applications to computational statistical physics and topological data analysis.
This is joint work with Orlando Marigliano from MPI Leipzig.

Speaker: Ali Ulas Özgür Kisisel [16]

The abstract is available as pdf-file [17].

Speaker: Visu Makam [18]

The following multi-determinantal algebraic variety plays a central role in algebra, algebraic geometry and computational complexity theory: SING(n,m), consisting of all m-tuples of n x n matrices which span only singular matrices. In particular, an efficient deterministic algorithm testing membership in SING(n,m) will imply super-polynomial circuit lower bounds, a holy grail of the theory of computation.
A sequence of recent works suggests such efficient algorithms for memberships in a general class of algebraic varieties, namely the null cones of linear group actions. Can this be used for the problem above? Our main result is negative: SING(n,m) is not the null cone of any reductive group action! This stands in stark contrast to a non-commutative analog of this variety, and points to an inherent structural difficulty of SING(n,m).
This is joint work with Avi Wigderson.