TU Berlin

Fachgebiet Algorithmische AlgebraKolloquium (Oberseminar)

Inhalt des Dokuments

zur Navigation

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

Schedule

The talk by Matías Bender is postponed from July 1 at 2pm to July 8 at 3pm.

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.

Planned Talks
Speaker
Title
Date
Starts
Philipp Reichenbach
Invariant Theory and Gaussian Group Models
29.04.2020
14:00
Mario Kummer
Positive Ulrich sheaves
06.05.2020
14:00
Büşra Sert
A study on the chamber complex
13.05.2020
14:00
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 Geometry
17.06.2020
14:00
M. Levent Doğan
Invariant Theory of Quiver Representations
24.06.2020
14:00
Matías Bender
Toric Eigenvalue Methods for Solving Sparse Polynomial Systems
08.07.2020
15:00

Abstracts

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 decades.
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 precision.
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.

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe