Inhalt des Dokuments
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.
|Alperen Ergür ||Fewnomial Theory
|Philipp di Dio ||Shape
|no talk due to
|Cordian Riener ||Vandermonde
Varieties, Mirrored Spaces and the Homology of symmetric semialgebraic
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 ||Random points on algebraic manifolds||05.06.19||14:15|
|Ali Ulas Özgür Kisisel
||Real and Complex Line
|Visu Makam ||Singular tuples of
matrices is not a null cone||18.09.19||14:00|
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
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
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.
Random points on algebraic manifolds
Speaker: Paul Breiding 
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.
Real and Complex Line Arrangements
Speaker: Ali Ulas Özgür Kisisel 
The abstract is available as pdf-file .
Singular tuples of matrices is not a null cone
Speaker: Visu Makam 
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.