### Page Content

## There is no English translation for this web page.

# 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 [1] | Fewnomial Theory
on Average | 17.04.19 | 14:15 |

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

no talk due to
holiday | 01.05.19 | ||

Cordian Riener [3] | 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 [4] | Efficient algorithms for moment polytopes and the null
cone problem from invariant theory | 29.05.19 | 14:15 |

Paul Breiding [5] | Random points on algebraic manifolds | 05.06.19 | 14:15 |

Ali Ulas Özgür Kisisel
[6] | Real and Complex Line
Arrangements | 12.06.19 | 14:15 |

Visu Makam [7] | Singular tuples of
matrices is not a null cone | 18.09.19 | 14:00 |

### Fewnomial Theory on Average

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

### Shape Reconstruction from Moments

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

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

**Speaker:** Cordian Riener
[10]

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

### 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 [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).

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

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

### Random points on algebraic manifolds

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

### Real and Complex Line Arrangements

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

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

### Singular tuples of matrices is not a null cone

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

g/fachgebiet_algorithmische_algebra/v_menue/members/dr_

alperen_erguer/parameter/en/font2/maxhilfe/

g/computeralgebra/v_menue/mitarbeiter/dr_philipp_j_di_d

io/parameter/en/font2/maxhilfe/

t_id=506531&p_dimension_id=88140

g/fachgebiet_algorithmische_algebra/v_menue/members/pro

f_dr_peter_buergisser/parameter/en/font2/maxhilfe/

g/fachgebiet_algorithmische_algebra/v_menue/members/dr_

paul_breiding/parameter/en/font2/maxhilfe/

?ssn=MTc2MTU4&action=Publications

g/fachgebiet_algorithmische_algebra/v_menue/members/dr_

alperen_erguer/parameter/en/font2/maxhilfe/

g/computeralgebra/v_menue/mitarbeiter/dr_philipp_j_di_d

io/parameter/en/font2/maxhilfe/

nt_id=506531&p_dimension_id=88140

rgisser/abstracts/RienerAbstract.pdf

lg/fachgebiet_algorithmische_algebra/v_menue/members/pr

of_dr_peter_buergisser/parameter/en/font2/maxhilfe/

lg/fachgebiet_algorithmische_algebra/v_menue/members/dr

_paul_breiding/parameter/en/font2/maxhilfe/

p?ssn=MTc2MTU4&action=Publications

rgisser/abstracts/Kisisel_Abstract.pdf