Sie sind hier

# 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

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 by Visu Makam has been rescheduled.

Planned Talks
Speaker
Title
Date
Starts
Jonathan Leake
Log-concavity and Entropy via Polynomial Capacity
07.10.2020
14:00
Peter Bürgisser
Complexity of computing zeros of structured polynomial systems
18.11.2020
15:00
Matthias Christandl
Weighted Slice Rank and a Minimax Correspondence to Strassen's Spectra
02.12.2020
15:00
Mateusz Michalek
Algebraic methods to construct tensors
09.12.2020
15:00
Fulvio Gesmundo
Varieties of sums of powers, Stiefel manifolds and their degrees
16.12.2020
15:00
Visu Makam
Maximum likelihood estimation for tensor normal models
06.01.2021
15:00
Antonio Lerario
What is the degree of a smooth hypersurface?
13.01.2021
15:00
Paul Breiding
Sensitivity of low-rank matrix approximation and recovery
20.01.2021
15:00
tba
tba
27.01.2021
Kathlén Kohn
tba
03.02.2021
15:00
Josué Tonelli-Cueto
tba
10.02.2021
15:00
Harold Nieuwboer
tba
17.02.2021
15:00

## Abstracts

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

### 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

Slides: pdf-file

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.

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

### What is the degree of a smooth hypersurface?

Speaker: Antonio Lerario

Let Z be a smooth and compact hypersurface contained in a disk D in euclidean space. It is well known that Z can be approximated by an algebraic hypersurface, which is isotopic (and in particular diffeomorphic) to Z in the disk D. In this talk I will study the problem of giving an upper bound on the smallest degree of such algebraic approximation, in terms of the geometric data of Z (e.g. its reach and its diameter). To this end I will introduce a notion of condition number in the (infinite dimensional!) space of smooth functions and discuss a condition number theorem, relating it to the distance in the C^1 topology from the set of functions whose zero set is a singular hypersurface. The degree of the algebraic approximation can be bounded by this condition number.

This is based on a joint work with Michele Stecconi, available at https://arxiv.org/abs/2010.14553

### Sensitivity of low-rank matrix approximation and recovery

Speaker: Paul Breiding

We characterize the sensitivity of the output in low-rank matrix approximation with respect to perturbations in the input. The characterization is in terms of a condition number. We show that the condition number for low-rank approximation depends on the singular value gap of the input matrix. This complements prior results by Hackbusch and by Drineas and Ipsen on the sensitivity of low-rank matrix approximation. In addition, we characterize the sensitivity of approximating an incomplete matrix by a low-rank matrix. Incomplete means that some entries of the input matrix are not known or not accessible. We give an algorithm for computing the associated condition number and demonstrate in experiments how the rate of missing data affects it.

This is joint work with N. Vannieuwenhoven.