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.

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

### The Maximum Likelihood Degree of Linear Spaces of Symmetric Matrices

Speaker: Kathlén Kohn

We study the maximum likelihood (ML) degree of multivariate Gaussian models that are described by linear conditions on the concentration matrix. We obtain new formulae for the ML degree, one via Schubert calculus, and another using Segre classes from intersection theory. This allows us to characterize the extreme cases on the ML degree spectrum: models with ML degree zero and models with maximal ML degree. It turns out that models with non-maximal ML degree are (up to Zariski closure) exactly those linear spaces for which strong duality in semidefinite programming fails. The subvariety of the Grassmannian formed by these linear spaces is a union of certain coisotropic hypersurfaces of determinantal varieties. We illustrate our results and the underlying geometry in the case of trivariate models: here we give a full, finite list of geometric types of linear subspaces in the space of symmetric 3x3 matrices incl. their ML degrees.

This talk is based on 3 joint works with 1) C. Améndola, L. Gustafsson, O. Marigliano, A. Seigal; 2) Y. Jiang, R. Winter; 3) S. Dye, F. Rydell, R. Sinn.

### Towards Finite Expectation in the Numerical Computation of the Homology of Semialgebraic Sets

Speaker: Josué Tonelli-Cueto

In algorithmic semialgebraic geometry, it remains an open problem to compute the homology groups of a semialgebraic set in a run-time that is singly-exponential in the number of variables. As of today, this can be done with high probability using the so-called grid method in a numerically stable way. However, the question remains: can we do such computation in a numerically stable way in expected singly-exponential time? In this talk, we describe one of the latest developments making the existing algorithms adaptive and trying to bring down their expected complexity to a finite estimate.

### Interior-point methods for unconstrained geometric programming and commutative scaling

Speaker: Harold Nieuwboer

Unconstrained geometric programs form a special class of convex programs with a wide variety of applications, including (but not limited to) finding maximum entropy distributions, maximum likelihood estimation for log-linear models, matrix scaling & balancing, and more generally commutative capacity and scaling problems. We show how to use interior-point methods to efficiently solve these programs, and analyze the complexity of the resulting algorithms using natural condition numbers associated with the Newton polytope of the geometric program.

This talk is based on joint work with Peter Bürgisser, Yinan Li and Michael Walter, and is available at arXiv:2008.12110.

### Polynomial Time Algorithms in Invariant Theory for Torus Actions

Speaker: Mahmut Levent Doğan

An action of a group on a vector space partitions the latter into a set of orbits. We consider three natural and useful algorithmic "isomorphism" or "classification" problems, namely, orbit equality, orbit closure intersection, and orbit closure containment. These capture and relate to a variety of problems within mathematics, physics and computer science, optimization and statistics. These orbit problems extend the more basic null cone problem, whose algorithmic complexity has seen significant progress in recent years.
In this talk, we study these problems by focusing on the actions of commutative groups (namely, tori). While the structural theory of commutative actions is well understood, no general efficient algorithms were known for the aforementioned problems. Following our recent paper with the same title, we will show that all three problems admit polynomial time algorithms. Our techniques are based on a combination of fundamental results in invariant theory, linear programming, and algorithmic lattice theory.

The talk is based on joint work with Peter Bürgisser, Visu Makam, Michael Walter and Avi Wigderson, see arXiv:2102.07727.

### Barriers for Scaling Algorithms in Invariant Theory

Speaker: Philipp Reichenbach

In recent years, Computational Invariant Theory has seen significant progress in optimization techniques: so-called scaling algorithms approximately minimize the norm along an orbit. Such algorithms also give rise to methods for deciding null-cone membership, i.e. whether zero is in the orbit closure. Both computational problems have versatile applications in mathematics, physics, statistics and computer science. The important case of operator scaling, i.e. the natural action of SL(n)^2 on tuples of 2-tensors (quadratic matrices), enjoyed several success stories. There are scaling algorithms that provide high-precision solutions in polynomial time and/or decide null-cone membership in polynomial time! However, in both counts current techniques are only known to run in exponential time for tensor scaling – that is, SL(n)^3 acts naturally on tuples of 3-tensors.
In this talk, we explain this dichotomy by providing bounds on two kinds of complexity parameters. First, an exponentially large diameter for tensor scaling prevents current methods to provide high precision solutions efficiently. Second, the complexity parameters weight margin and gap, which capture the required precision to decide null-cone membership, are exponentially small for tensor scaling. Furthermore, we mention exponentially small upper bounds on weight margin/gap for an action on quivers and for the natural SL(n) action on homogeneous polynomials.
These barriers strongly suggest that current methods do not suffice for tensor scaling and highly motivate the search for new scaling algorithms.

Based on joint work with Cole Franks, see arXiv:2102.06652.