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 talk on March 25 is canceled due to the spread of Corona virus.

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. 

Speaker: Elise Walker

Homotopies are useful numerical methods for solving systems of polynomial equations. Embedded toric degenerations are one source for homotopy algorithms. In particular, if a projective variety has a toric degeneration, then linear sections of that variety can be optimally computed using the polyhedral homotopy. Any variety whose coordinate ring has a finite Khovanskii basis is known to have a toric degeneration. We provide embeddings for this Khovanskii toric degeneration to compute general linear sections of the variety. This is joint work with Michael Burr and Frank Sottile.

Speaker: Thomas Yahl

Solutions to sparse polynomial systems are identified with fibres of a branched cover determined by the support of the equations. A sparse system is decomposable if this branched cover factors as a composition of nontrivial branched covers on an open set. Work of A. Esterov is used to determine exactly when a sparse system is decomposable. This leads to a method of solving sparse polynomial systems by factoring the branched cover and iteratively computing fibres of each factor as solutions to simpler polynomial systems.

Speaker: Frank Sottile

In 1870 Jordan explained how Galois theory can be applied to problems from enumerative geometry, with the group encoding intrinsic structure of the problem. Earlier Hermite showed the equivalence of Galois groups with geometric monodromy groups, and in 1979 Harris initiated the modern study of Galois groups of enumerative problems. He posited that a Galois group should be `as large as possible' in that it will be the largest group preserving internal symmetry in the geometric problem.

I will describe this background and discuss some work in a long-term project to compute, study, and use Galois groups of geometric problems, including those that arise in applications of algebraic geometry. A main focus is to understand Galois groups in the Schubert calculus, a well-understood class of geometric problems that has long served as a laboratory for testing new ideas in enumerative geometry.

Speaker: Alexander Heaton

A well-known combinatorial algorithm can decide generic rigidity in the plane by determining if the graph is of Pollaczek-Geiringer-Laman type. Methods from matroid theory have been used to prove other interesting results, again under the assumption of generic configurations. However, configurations arising in applications may not be generic. We present Theorem 7 and its corresponding Algorithm 1 which decide if a configuration is epsilon-locally rigid, a notion we define. This provides a partial answer to a problem discussed in the 2011 paper of Hauenstein, Sommese, and Wampler. The theorem and algorithm use results from a 2012 paper of Hauenstein. We also present Algorithm 2 which uses numerical algebraic geometry to find nearby valid configurations which are not obtained by rigid motions. When successful, this method demonstrates the failure of local rigidity by explicitly constructing a sequence of configurations which are a discrete-time sample of a continuous flex. This is joint work with Andrew Frohmader.