### Inhalt des Dokuments

# 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 [1] (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.

Speaker | Title | Date | Starts |
---|---|---|---|

Jonathan Leake [2] | Log-concavity and Entropy via Polynomial
Capacity | 07.10.2020 | 14:00 |

Peter Bürgisser [3] | Complexity
of computing zeros of structured polynomial systems | 18.11.2020 | 15:00 |

Matthias Christandl [4] | Weighted
Slice Rank and a Minimax Correspondence to Strassen's
Spectra | 02.12.2020 | 15:00 |

Mateusz Michalek [5] | Algebraic
methods to construct tensors | 09.12.2020 | 15:00 |

Fulvio Gesmundo [6] | Varieties of
sums of powers, Stiefel manifolds and their degrees | 16.12.2020 | 15:00 |

Visu Makam [7] | Maximum likelihood
estimation for tensor normal models | 06.01.2021 | 15:00 |

Antonio Lerario [8] | What is the
degree of a smooth hypersurface? | 13.01.2021 | 15:00 |

Paul Breiding [9] | Sensitivity of
low-rank matrix approximation and recovery | 20.01.2021 | 15:00 |

Kathlén Kohn [10] | The Maximum
Likelihood Degree of Linear Spaces of Symmetric Matrices | 03.02.2021 | 15:00 |

Josué Tonelli-Cueto [11] | Towards
Finite Expectation in the Numerical Computation of the Homology of
Semialgebraic Sets | 10.02.2021 | 15:00 |

Harold Nieuwboer [12] | Interior-point methods for unconstrained geometric
programming and commutative scaling | 17.02.2021 | 15:00 |

Mahmut Levent Doğan [13] | Polynomial Time Algorithms in Invariant Theory for Torus
Actions | 24.02.2021 | 15:00 |

Philipp Reichenbach [14] | Barriers
for Scaling Algorithms in Invariant Theory | 10.03.2021 | 15:00 |

### Log-concavity and Entropy via Polynomial Capacity

**Speaker: **Jonathan Leake
[15]

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
[16]

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

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

**Speaker:** Matthias Christandl
[18]

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 [19]

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 $ntimes 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
[20]

**Slides:** pdf-file [21]

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 [22]

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
[23]

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 [24]

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

**Speaker:**
Paul Breiding [25]

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 [26]

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
[27]

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 [28]

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 [29].

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

**Speaker:** Mahmut Levent Doğan
[30]

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 [31].

### Barriers for Scaling Algorithms in Invariant Theory

**Speaker:** Philipp Reichenbach
[32]

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 [33].

g/fachgebiet_algorithmische_algebra/v_menue/members/phi

lipp_reichenbach/

g/fachgebiet_algorithmische_algebra/v_menue/members/pro

f_dr_peter_buergisser/

ns/475476

me.html

g/fachgebiet_algorithmische_algebra/v_menue/members/dr_

paul_breiding/

lg/fachgebiet_algorithmische_algebra/v_menue/members/ma

hmut_levent_dogan/

lg/fachgebiet_algorithmische_algebra/v_menue/members/ph

ilipp_reichenbach/

lg/fachgebiet_algorithmische_algebra/v_menue/members/pr

of_dr_peter_buergisser/

rgisser/abstracts/abstractTalkNov18.pdf

ons/475476

rgisser/presentationGesmundo.pdf

ome.html

lg/fachgebiet_algorithmische_algebra/v_menue/members/dr

_paul_breiding/

lg/fachgebiet_algorithmische_algebra/v_menue/members/ma

hmut_levent_dogan/

lg/fachgebiet_algorithmische_algebra/v_menue/members/ph

ilipp_reichenbach/