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!


Due to the current situation the Kolloquium will be held online. Usually it takes place Wednesday at 3pm sharp.

The schedule will be updated regularly.

The talk on November 25 by Visu Makam is cancelled! Likely, the talk will be rescheduled.

Planned Talks
Jonathan Leake
Log-concavity and Entropy via Polynomial Capacity
Peter Bürgisser
Complexity of computing zeros of structured polynomial systems
Visu Makam
Maximum likelihood estimation for tensor normal models
Matthias Christandl
Weighted Slice Rank and a Minimax Correspondence to Strassen's Spectra
Mateusz Michalek
Algebraic methods to construct tensors
Fulvio Gesmundo
Varieties of sums of powers, Stiefel manifolds and their degrees
Antonio Lerario


Log-concavity and Entropy via Polynomial Capacity

Speaker: Jonathan Leake

In this talk, we discuss a number of connections between the notion of polynomial capacity and other topics. In particular, we will discuss connections to the theory of stable and log-concave polynomials, with applications to inequalities and algorithms in combinatorics (matroids, graph matchings, contingency tables, matrix permanent, etc.). We will also discuss connections to maximum entropy distributions, and show how this relates to convex optimization and to the interpretation of capacity as the minimum norm over group orbits. This will be more of a survey-style talk, and will hopefully be accessible to anyone curious about these topics.

Complexity of computing zeros of structured polynomial systems

Speaker: Peter Bürgisser

The abstract can be found in the following pdf-file.

Maximum likelihood estimation for tensor normal models

Speaker: Visu Makam

In statistics, maximum likelihood estimation is a method of estimating the parameters of a probability distribution by maximizing a likelihood function, so that under the assumed statistical model the observed data is most probable. The point in the parameter space that maximizes the likelihood function is called a maximum likelihood estimate (MLE). One important question is to understand whether a given number of samples suffices to expect (almost surely) 1. a bounded likelihood function, 2. existence of an MLE and 3. existence of a unique MLE. For a collection of statistical models called Gaussian group models, connections to invariant theory, in particular the notions of stability, were discovered by Améndola, Kohn, Reichenbach and Seigal. In this talk, we will discuss tensor normal models, which correspond to tensor actions. Using castling transforms and results on stabilizers in general position, we completely determine for a given number of samples, whether we have almost sure boundedness of likelihood function, existence of MLE and its uniqueness.

This is joint work with Harm Derksen and Michael Walter.

Weighted Slice Rank and a Minimax Correspondence to Strassen's Spectra

Speaker: Matthias Christandl

Structural and computational understanding of tensors is the driving force behind faster matrix multiplication algorithms, the unraveling of quantum entanglement, and the breakthrough on the cap set problem. Strassen's asymptotic spectra program (SFCS 1986) characterizes optimal matrix multiplication algorithms through monotone functionals. Our work advances and makes novel connections among two recent developments in the study of tensors, namely the slice rank of tensors, a notion of rank for tensors that emerged from the resolution of the cap set problem (Ann.of Math. 2017), and the quantum functionals of tensors (STOC 2018), monotone functionals defined as optimizations over moment polytopes. More precisely, we introduce an extension of slice rank that we call weighted slice rank and we develop a minimax correspondence between the asymptotic weighted slice rank and the quantum functionals. Weighted slice rank encapsulates different notions of bipartiteness of quantum entanglement. The correspondence allows us to give a rank-type characterization of the quantum functionals. Moreover, whereas the original definition of the quantum functionals only works over the complex numbers, this new characterization can be extended to all fields. Thereby, in addition to gaining deeper understanding of Strassen's theory for the complex numbers, we obtain a proposal for quantum functionals over other fields. The finite field case is crucial for combinatorial and algorithmic problems where the field can be optimized over.

Algebraic methods to construct tensors

Speaker: Mateusz Michalek

We will present various approaches to constructing interesting tensors through algebraic methods. Our main motivation is the problem of fast matrix multiplication. In particular, we will show several new tensors that prove that one can multiply $n\times n$ matrices in time below $n^{2.5}$.

The talk is based on a joint work with Roser Homs Pons, Joachim Jelisiejew and Tim Seynnaeve.

Varieties of sums of powers, Stiefel manifolds and their degrees

Speaker: Fulvio Gesmundo

Varieties of sums of powers parameterize decompositions of a given homogeneous polynomial as sum of powers of linear forms: they have been studied since the nineteenth century and they are notoriously a difficult object to understand. Given a homogeneous polynomial, we introduce an alternative variety that records similar information as the variety of sums of powers. In the case of quadratic forms this object is identified with the classical Stiefel manifold, parametrizing the Parseval frames in a finite-dimensional vector space. I will present some recent work, joint with T. Brysiewicz, in which we computed the degree of these algebraic varieties.



Schnellnavigation zur Seite über Nummerneingabe