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.

The schedule will be updated regularly.

Speaker: Matías Bender

Polynomial system solving is one of the oldest and most important problem in computational mathematics and has many applications in computer science. It is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. In this talk, we focus on exploiting the structure related to the sparsity of the supports of the polynomials; that is, we take advantage of the fact that the polynomials only have a few monomials with non-zero coefficients. Our objective is to solve sparse systems faster than the worst case estimates that assume that all the terms are present. We develop algorithms for mixed sparse polynomial systems, that is, systems where the sparsity structure of the polynomials (Newton polytope) is different. We elaborate on two domains of elimination theory: sparse resultants and Gröbner bases. We work on each domain independently, but we also combine them to introduce new algorithms showing for the first time their relation in the sparse setting. We build on the multigraded Castelnuovo-Mumford regularity to develop this relation. We use resultants to propose "optimal" algorithms to solve families of mixed multilinear systems and, for a more general setting, we use Gröbner bases to solve sparse systems avoiding useless computations. The complexity of our algorithms depends on the sparsity structure of the systems (Newton polytopes). Finally, we introduce quasi-optimal algorithms to decompose binary forms.

Speaker: Philipp Reichenbach

Finding polynomial-time algorithms for the null-cone membership problem is nowadays one of the striving problems in Computational Invariant Theory. In their very recent work [1] Peter Bürgisser et. al. propose analytic 1st and 2nd order methods for solving the null-cone membership problem. Moreover, they provide a complexity analysis of these methods and the main complexity parameter is the so-called weight margin, see [1, Theorems 4.3 and 5.6]. This is a purely discrete measure, that only depends on the weights of the underlying group action.
In this talk we will explain for concrete group actions lower resp. upper bounds on the weight margin. With these bounds we can conclude, when the algorithms provide polynomial resp. at best exponential running time. To do so, we first motivate the null-cone problem, introduce the weight margin and state some complexity results from [1]. Afterwards, we present some bounds on the weight margin and focus on the proof ideas for the upper bounds.
The presented lower bounds are taken from [1], while the upper bounds are ongoing joint work with Cole Franks.

Literature:
[1] P. Bürgisser, C. Franks, A. Garg, R. Oliveira, M. Walter and A. Wigderson. Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes. arXiv 1910.12375v1. 2019.

Speaker: Oliver Gräfvert

I will discuss the problem of fitting a variety, coming from a class of varieties, to a configuration of points in space. I will analyse the complexity of this problem using the Euclidean distance degree of an associated variety called the hypothesis variety. For the problem of fitting an n-sphere to a configuration of points, we give a closed formula of the complexity in a special case. For the general case we conjecture a generalization of this formula supported by numerical experiments.

Speaker: Alperen Ergür

We present a homotopy continuation algorithm for finding real zeros of sparse polynomial systems. The algorithm is based on numerically tracking Viro's patchworking method. It also uses basics of the theory of A-discriminants. Two aspects of the algorithm might be contrasted: on one hand it operates completely over the reals and tracks optimal number of solution paths, on the other hand it solves polynomial systems with certain concavity conditions on the coefficients (a.k.a. patchworked polynomial systems). This is joint work with Timo de Wolff, and it relies on superb coding skills of Sascha Timme.

Speaker: Dirk Kussin

It is well-known that complex smooth projective curves correspond to compact Riemann surfaces. Similarly, real smooth projective curves correspond to the so-called Klein surfaces [1]. The real (=boundary) points form so-called ovals. Ernst Witt [2] studied Klein surfaces with an even number of marked points on each of its ovals. We show that this leads to noncommutative real smooth projective curves, which we call Witt curves. We then consider those curves of Euler characteristic zero (or genus one), the noncommutative real elliptic curves. Prominent commutative examples are the Klein bottle, the Moebius band and the annulus, but there are also not-commutative ones. We will show that the Klein bottle has a (noncommutative) Witt curve as a so-called Fourier-Mukai partner. (This is part of [3].)

Literature:
[1] N. L. Alling and N. Greenleaf, Foundations of the theory of Klein surfaces, Lecture Notes in Mathematics, 219, Springer-Verlag, Berlin-New York, 1971.
[2] E. Witt, Zerlegung reeller algebraischer Funktionen in Quadrate. Schiefkörper über reellem Funktionenkörper, J. Reine Angew. Math., 171 (1934), 4–11.
[3] D. Kussin, Weighted noncommutative regular projective curves, J. Noncommut. Geom. 10 (2016), 1465-1540.

Speaker: Simon Telen

We consider the problem of solving a system of algebraic equations with complex coefficients. We propose robust numerical linear algebra methods for tackling this problem. In order to do so, we define Truncated Normal Forms (TNFs), which provide a general framework for constructing rewriting rules modulo the ideal generated by the input polynomials. We give explicit algorithms for the case where the equations are generic with respect to their degrees or to their Newton polytopes. Several numerical experiments illustrate the effectiveness of the approach. This is joint work with Bernard Mourrain and Marc Van Barel.

Speaker: Daniele Agostini

The Schottky problem asks to recognize Jacobians amongst all abelian varieties and it is one of the central questions in algebraic geometry since the time of Riemann. We will present the state of the art about this problem and we will explain a recent joint work with Lynn Chua where we give a solution to the weak Schottky problem for genus five Jacobians with a vanishing theta null. We will also emphasize how to make this result effective using the software Julia.