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. To do so, please write an email to Philipp Reichenbach  (reichenbach at tu-berlin.de).
For students: Please note that you cannot earn any ECTS!
Due to the current situation the Kolloquium will be held online. Usually it takes place Wednesday at 2pm sharp.
The schedule will be updated regularly. The first talk takes place on April 29.
|Philipp Reichenbach ||Invariant Theory and Gaussian Group Models||29.04.2020||14:00|
|Büşra Sert||A study on the
|Christian Ikenmeyer ||Implementing geometric complexity theory: On the
separation of orbit closures via symmetries||20.05.2020||14:00|
|Thibaut Verron ||Gröbner bases
for Tate algebras||27.05.2020||14:00|
|Paul Breiding ||Euclidean
Distance Degree and Mixed Volume||03.06.2020||14:00|
|Cole Franks ||Minimal length in
an orbit closure as a semiclassical limit||10.06.2020||15:00|
|Martin Lotz ||Phase Transitions in Euclidean Integral
Levent Doğan ||Invariant Theory of
|Matías Bender ||Toric
Eigenvalue Methods for Solving Sparse Polynomial
|Dominic Bunnett ||Geometric invariant theory for non-reductive
Invariant Theory and Gaussian Group Models
Speaker: Philipp Reichenbach 
The task of fitting data to a model is fundamental in statistics.
For this, a widespread approach is maximum likelihood estimation (ML
estimation), where one maximizes the likelihood of observing the data
as we range over the model.
In this talk we study Gaussian group models, which are multivariate Gaussian models induced by a subgroup of GL_m. This general approach covers common concepts like matrix normal models and graphical models of a transitive directed acyclic graph (TDAG). The group setting allows us to strongly link ML estimation to stability notions from invariant theory. Consequently one can transfer knowledge from invariant theory to statistics, and vice versa. In particular, some known results from statistics are recovered and even new results on the statistics side can be obtained.
Based on joint work with Carlos Améndola, Kathlén Kohn and Anna Seigal, arXiv:2003.13662 .
Positive Ulrich sheaves
Speaker: Mario Kummer
A widespread principle in real algebraic geometry is to find and use algebraic certificates for geometric statements. This covers for example writing a globally nonnegative polynomial as a sum of squares or expressing a polynomial with only real zeros as the minimal polynomial of a symmetric matrix. In the first part of the talk I will survey some classical results in this direction including Hilbert’s theorem on nonnegative ternary quartics and the solution of the Lax conjecture on plane hyperbolic curves due to Helton and Vinnikov. Then I will present a quite general result on so-called positive Ulrich sheaves and show how this implies all the aforementioned results. This is joint work with Christoph Hanselka.
A study on the chamber complex
Speaker: Büşra Sert
The notion of chamber (Minkowski cone, type cone) of a polytope has had an important role in several theories, such as Minkowski decomposition, the vector partition function, etc (McMullen, Emiris et al., Henk et al., Brion et al., Strumfels, Beck and others).
While the chamber of a polytope P gives us the cone of vectors
that change the half-space arrangement of P without changing its
normal fan, we are interested in finding all different normal fans we
can obtain by moving a given set of half-spaces. In this talk, we
present the chamber complex of a matrix, which gives us the collection
of all chambers we can obtain from it. Moreover, we describe an
algorithm to compute it.
This is joint work with Zafeirakis Zafeirakopoulos.
Implementing geometric complexity theory: On the separation of orbit closures via symmetries
Speaker: Christian Ikenmeyer 
Understanding the difference between group orbits and their
closures is a key difficulty in geometric complexity theory (GCT):
While the GCT program is set up to separate certain orbit closures,
many beautiful mathematical properties are only known for the group
orbits, in particular close relations with symmetry groups and
invariant spaces, while the orbit closures seem much more difficult to
understand. However, in order to prove lower bounds in algebraic
complexity theory, considering group orbits is not enough.
In this paper we tighten the relationship between the orbit of the power sum polynomial and its closure, so that we can separate this orbit closure from the orbit closure of the product of variables by just considering the symmetry groups of both polynomials and their representation theoretic decomposition coefficients. In a natural way our construction yields a multiplicity obstruction that is neither an occurrence obstruction, nor a so-called vanishing ideal occurrence obstruction. All multiplicity obstructions so far have been of one of these two types.
Our paper is the first implementation of the ambitious approach that was originally suggested in the first papers on geometric complexity theory by Mulmuley and Sohoni (SIAM J Comput 2001, 2008): Before our paper, all existence proofs of obstructions only took into account the symmetry group of one of the two polynomials (or tensors) that were to be separated. In our paper the multiplicity obstruction is obtained by comparing the representation theoretic decomposition coefficients of both symmetry groups.
Our proof uses a semi-explicit description of the coordinate ring of the orbit closure of the power sum polynomial in terms of Young tableaux, which enables its comparison to the coordinate ring of the orbit.
This is joint work with Umangathan Kandasamy.
Gröbner bases for Tate algebras
Speaker: Thibaut Verron 
Tate series are the central object of rigid geometry, which has
been introduced by John Tate in order to create a p-adic analogue to
the bridge between analytic and algebraic geometry in the classical
case. As such, their study has gained a lot of importance in the past
Tate series are defined as convergent power series with coefficients in a discrete valuation ring, and in a lot of respects, behave a lot more like polynomials than like power series. In this work, we defined a theory of Gröbner bases for such series, which allows to perform ideal arithmetic and computational algebraic geometry in this framework. The algorithms have been made available as a part of SageMath.
This is joint work with Xavier Caruso and Tristan Vaccon.
Euclidean Distance Degree and Mixed Volume
Speaker: Paul Breiding 
The Euclidean Distance Degree (EDD) of an algebraic variety V
counts the number of complex critical points of the distance function
from V to a generic fixed point outside of V.
The BKK-Theorem (due to Bernstein , Kushnirenko, and Khovanskii) says that the number of complex zeros of a generic sparse polynomial system is equal to the mixed volume of the Newton polytopes of the polynomials.
In this talk I want to discuss that the Lagrange multiplier equations of the EDD of a generic hypersurface are generic in the sense of BKK. In other words, for generic sparse polynomial f the EDD of Z(f) is equal to the mixed volume of the Lagrange multiplier equations for the EDD. This has impact on using polynomial homotopy continuation for computing the ED-critical points. (Joint work with Frank Sottile).
Minimal length in an orbit closure as a semiclassical limit
Speaker: Cole Franks 
Consider the action of a connected complex reductive group on a
finite-dimensional vector space. A fundamental result in invariant
theory states that the orbit closure of a vector v is separated from
the origin if and only if some homogeneous invariant polynomial is
nonzero on v. We refine this famous duality between orbit closures and
invariant polynomials by showing that the following two quantities
coincide: (1) the logarithm of the Euclidean distance between the
orbit closure and the origin and (2) the rate of exponential growth of
the 'invariant part' of the kth tensor power of v in the semiclassical
limit as k tends to infinity. We also provide generalizations of this
result to projections onto highest weight vectors and isotypical
components. Such semiclassical limits arise in the study of the
asymptotic behavior of multiplicities in representation theory, in
large deviations theory in classical and quantum statistics, and in a
conjecture in invariant theory due to Mathieu. Our formula implies
that they can be computed, in many cases efficiently, to arbitrary
This is joint work with Michael Walter.
Phase Transitions in Euclidean Integral Geometry
Speaker: Martin Lotz 
Intrinsic volumes are fundamental invariants of convex bodies that include the Euler characteristic and the volume. Important results in integral geometry relate the intrinsic volumes of random projections, intersections, and sums of convex bodies to those of the individual volumes. We present a new interpretation of these classic results, by showing that they exhibit sharp phase transition phenomena. For example, as the dimension of a subspace varies, the average intrinsic volume polynomial of the projection to the subspace is as large as possible or it is negligible, and the exact location of the transition can be expressed in terms of a summary parameter associated with the convex body. Similar phase transitions appear in related problems, including the rotation mean formula, the slicing (Crofton) formula, and the kinematic formula. These phenomena are explained by a new set of measure concentration inequalities for weighted intrinsic volumes of a convex body.
Invariant Theory of Quiver Representations
Speaker: M. Levent Doğan 
Invariant theory of matrix tuples has been subject to extensive
research. The description of invariants and effective algorithms for
the orbit closure intersection problem are known. The setting of
quiver representation leads to a natural generalization to group
actions on matrix tuples but the related algorithmic problems turn out
to be more difficult compared to the initial case.
In this talk, we’ll talk about quivers and their representations. We’ll describe invariants & semi-invariants of quivers and discuss the hardship of finding effective algorithms for the corresponding orbit closure intersection problems. As a last discussion, we’ll study the unitary action on quiver representations and its relation to the original problem of finding effective algorithms for the orbit closure intersection problem in the quiver case.
Toric Eigenvalue Methods for Solving Sparse Polynomial Systems
Speaker: Matías Bender 
In this talk, we introduce a symbolic-numerical algorithm to solve
(nearly) degenerate sparse polynomial systems. For that, we consider
the problem of computing homogeneous coordinates of points in a
zero-dimensional subscheme of a compact toric variety X. By working
over the Cox ring of X, our algorithm can handle input systems whose
solutions have multiplicities. We investigate the regularity of these
systems to provide complexity bounds for our approach, as well as
sharper bounds for weighted homogeneous, multihomogeneous and unmixed
sparse systems, among others. Additionally, we disprove a recent
conjecture regarding this regularity.
The talk is based on joint work with Simon Telen.
Geometric invariant theory for non-reductive groups
Speaker: Dominic Bunnett 
Geometric invariant theory was introduced by Mumford in the 60’s to understand the geometry of invariants which are quotient spaces in algebraic geometry. The only proviso being that the group acting is reductive. However, one encounters many non-reductive groups in the wild, groups whose invariant theory is important to understand.
I will explain what can go wrong when one has a non-reductive group in GIT and explain the theory of non-reductive GIT developed recently by Kirwan et. al. I will also give some examples of where this non-reductive GIT can be used.