Fachgebiet Algorithmische AlgebraKolloquium (Oberseminar)

# 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 Kolloquium usually takes place on Wednesday at 3pm sharp (German time). Our research group meets in MA 316 to follow the talk. However, several talks may have a hybrid format with an additional Zoom link.

The schedule will be updated regularly.

Planned Talks
Speaker
Title (Format)
Date
Starts
Peter Bürgisser
Integral geometry in nonarchimedean spaces (in person)
06.10.2021
10:15
Peter Bürgisser
Rigid Continuation Paths II: Structured Polynomial Systems (hybrid)
27.10.2021
15:00
Jonathan Leake
Lorentzian polynomials on cones and the Heron-Rota-Welsh conjecture (in person)
03.11.2021
15:00
Antonio Lerario
Hausdorff approximation and volume of tubes of singular algebraic sets (hybrid)
10.11.2021
10:15
Gorav Jindal

24.11.2021
15:00
Josué Tonelli-Cueto
What does the condition number of a real polynomial system tell us? Unexpected answers in the real world (hybrid)
07.12.2021
14:15
Amit Sinhababu
Factoring Polynomials given as Arithmetic Branching Programs (hybrid)
15.12.2021
15:00
Dominic Bunnett
Computing cohomology of quotient spaces (hybrid)
12.01.2022
15:00
Cordian Riener
#P-hardness of matrix immanants on restricted matrices (hybrid)
26.01.2022
15:00
Michael Walter
Near optimal sample complexity for matrix and tensor normal models via geodesic convexity (hybrid)
02.02.2022
15:00
Nutan Limaye
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
23.02.2022
15:00

## Abstracts

### Integral geometry in nonarchimedean spaces

Speaker: Peter Bürgisser

In a recent paper, Kulkarni and Lerario found a version of Poincare's formula of integral geometry for p-adic projective varieties. (SIAM J. Appl. Alg. Geo, 2021). We extend this result in various directions by developing a conceptual framework over nonarchimedan local fields that mirrors the approach over the reals quite closely. As an application, we obtain precise results on the expected number of p-adic zeros of random fewnomials.
The talk describes ongoing work with Kulkarni and Lerario.

### Rigid Continuation Paths II: Structured Polynomial Systems

Speaker: Peter Bürgisser

We study the average complexity of solving structured polynomial systems that are characterised by a low evaluation cost, as opposed to the dense random model previously used. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as black-box evaluation program. Secondly, we introduce a universal model of random polynomial systems withprescribed evaluation complexity L. Combining both, we show that we can compute an approximate zero of a random structured polynomial system with n equations of degree at most d in n variables with only poly(n,d) L operations with high probability. This exceeds the expectations implicit in Smale's 17th problem
This is joint work with Felipe Cucker and Pierre Lairez, see arxiv.org/abs/2010.10997.

### Lorentzian polynomials on cones and the Heron-Rota-Welsh conjecture

Speaker: Jonathan Leake

About 5 years ago, the Heron-Rota-Welsh conjecture (log-concavity of the coefficients of the reduced characteristic polynomial of a matroid) was proven by Adiprasito, Huh, and Katz via the development of a new combinatorial Hodge theory for matroids. In very recent work with Petter Brändén, we have given a new short "polynomial proof" of the Heron-Rota-Welsh conjecture. Our proof uses an extension of the theory of Lorentzian polynomials to convex cones, and in particular reproves the Hodge-Riemann relations of degree one for the Chow ring of a matroid. In this talk, I will briefly discuss the basics of Lorentzian (aka completely log-concave) polynomials as developed by Anari-Liu-Oveis Gharan-Vinzant and by Brändén-Huh in recent years, and then I will give an overview of our new proof of the Heron-Rota-Welsh conjecture, emphasizing newly developed tools in the theory of Lorentzian polynomials.

### Hausdorff approximation and volume of tubes of singular algebraic sets

Speaker: Antonio Lerario

I will discuss the problem of estimating the volume of the tube around an algebraic set (possibly singular) as a function of the dimension of the set and its degree. In particular I will show bounds for the volume of neighborhoods of algebraic sets, in the euclidean space or the sphere, in terms of the degree of the defining polynomials, the number of variables and the dimension of the algebraic set, without any smoothness assumption. This problem is related to numerical algebraic geometry, where sets of ill-contidioned inputs are typically described by (possibly singular) algebraic sets, and their neighborhoods describe bad-conditioned inputs. Our result generalizes previous work of Lotz on smooth complete intersections in the euclidean space and of Bürgisser, Cucker and Lotz on hypersurfaces in the sphere, and gives a complete solution to Problem 17 in the book titled "Condition" by Bürgisser and Cucker.

### Efficiently Computing Real Roots of Sparse Polynomials

Speaker: Gorav Jindal

Computing the (real) roots of polynomials is an important problem in mathematics and theoretical computer science. We propose an efficient algorithm to compute the real roots of a sparse polynomial having k non-zero real-valued coefficients. It is known that even for 4-nomials, one can not hope for a polynomial (in the input size) time algorithm for isolating the real roots. Therefore we propose a slightly relaxed notion of isolation of real roots. For a given positive integer L, our algorithm returns disjoint disks D_1,D_2,...,D_s with s < 2k, centered at the real axis and of radius less than 2^{-L} together with positive integers u_1,...,u_s such that each disk D_i contains exactly u_i roots of f counted with multiplicity. In addition, it is ensured that each real root of f is contained in one of the disks. If f has only simple real roots, our algorithm can also be used to isolate all real roots.The bit complexity of our algorithm is polynomial in k and log(n),and near-linear in L and t, where 2^{-t} and 2^t constitute lower and upper bounds on the absolute values of the non-zero coefficients of f, and n is the degree of f. For root isolation, the bit complexity is polynomial in k and log(n), and near-linear in t and log(1/q), where q denotes the separation of the real roots. By using our algorithm, it follows that the real roots of trinomials can be isolated in polynomial time.

This is a joint work with Prof. Michael Sagraloff( Max-Planck-Institut für Informatik and University of Applied Sciences Landshut).

### What does the condition number of a real polynomial system tell us? Unexpected answers in the real world

Speaker: Josué Tonelli-Cueto

The condition number of a real polynomial system measures the numerical stability of the system. However, what does this number tell us? In this talk, we will see how this condition number does not control only the numerical stability, but several fundamental algebraic-geometric invariants such as the separation bound and the number of zeros. The latter will have dramatic consequences on the relationship between a polynomial system's number of real zeros and its numerical stability—this phenomenon stands in contrast to the complex setting. This is joint work with Elias Tsigaridas.

### Factoring Polynomials given as Arithmetic Branching Programs

Speaker: Amit Sinhababu

A basic problem in computational algebra is polynomial factoring: Given a polynomial, compute all its irreducible factors. In a classic result, Erich Kaltofen proved that if a multivariate polynomial of degree d is given as an arithmetic circuit of size s, then all its factors can be computed by arithmetic circuits of size poly(s,d).In other words, the algebraic complexity class VP is closed under factors. This result has applications in algebraic complexity, for example in derandomization of polynomial identity testing using explicit hard polynomials.
A natural direction to extend Kaltofen's result is to prove analogous factor size bounds in various other models of computing polynomials. Recent works in this area focused on models like constant depth circuits, arithmetic formulas, arithmetic branching programs. Kaltofen's proof does not extend to these models.
In this work, we show poly(s) factor size upper bound for the model of arithmetic branching programs (ABP) using the well-known technique of Hensel lifting. In this talk, I would give a brief survey of the earlier works and present the main ideas of our proof and discuss some of the open questions.

Joint work with Thomas Thierauf, Aalen University.

### Computing cohomology of quotient spaces

Speaker: Dominic Bunnett

In this talk we shall give an overview of Kirwan’s method of computing cohomology of quotient spaces. Suppose that we have a reductive group G acting on a projective manifold X. Using the moment map for the action of G on X, one defines a Morse-like function. This Morse-like function allows us to compute topological information of the GIT quotient space X//G. The overview will be example-led and we primarily consider the action of SL_{n+1} on the space of homogenous d-forms, following early work of Kirwan. Time permitting, we will discuss the recent work of [Berczi, Kirwan] and [Hamilton] concerning how one generalises when the group acting is non-reductive. This is the case when considering symmetries of weighted homogenous d-forms (joint work with J. Jackson).

### #P-hardness of matrix immanants on restricted matrices

Speaker: Cordian Riener

The determinant is a function from $n\times n$ matrices one encounters in linear algebra. Permanents are less known and are obtained by neglecting the \emph{signum} before each term of the determinant. The sharp difference of computational complexity of these two seemingly similar functions has been shown by Valiant in 1979. Immanants are matrix functions that generalise both determinants and permanents: They are obtained by replacing the signum with another character of the symmetric group. Immanents constitute therefore a family of matrix functions bridging from the determinant, which is obtained by the sign character and which can be evaluated in polynomial time to the #P hard permanent, which is obtained through the trivial character.
The question, where on the way between the determinant and the permanent “easy” turns into “hard” has been initiated by Hartmann in the 1980 and improved by Barvinok and Bürgisser. Recently, Curticapean has completed this picture by providing a complete complete dichotomy result. In this talk we are going to examine what can be said if one restricts to the class of 0-1 matrices. In this context we show #P hardness for a large class of immanents. In particular, we characterise a class of partitions $\lambda$ such that it is #P hard to compute the $\lambda$-immanent of adjacency matrices of edge-weighted, planar, directed graphs.
This is joint work with Istvan Miklos.

### Near optimal sample complexity for matrix and tensor normal models via geodesic convexity

Speaker: Michael Walter

Matrix and tensor normal models are Gaussian models where the covariance matrix is a Kronecker product of lower-dimensional factors. They are frequently used in statistics to model matrix- or tensor-valued data. We show non-asymptotic bounds for the error achieved by the maximum likelihood estimator (MLE) in several natural metrics. In contrast to existing bounds, our results do not rely on the factors being well-conditioned or sparse. In the same regimes as our sample complexity bounds, we show that an iterative procedure to compute the MLE known as the flip-flop algorithm converges linearly with high probability. Our main tool is geodesic strong convexity in the geometry of the positive-definite matrices induced by the Fisher information metric. This strong convexity in turn is linked to the expansion of certain random quantum channels. If time permits we also comment on numerical evidence that combining the flip-flop algorithm with a simple shrinkage estimator can improve performance in the undersampled regime.
Joint work with C. Franks, R. Oliveira and A. Ramachandran.

### Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

Speaker: Nutan Limaye

Every multivariate polynomial P(X) can be written as a sum of monomials, i.e. a sum of products of variables and field constants. In general, the size of such an expression is the number of monomials that have a non-zero coefficient in P.

What happens if we add another layer of complexity, and consider sums of products of sums (of variables and field constants) expressions? Now, it becomes unclear how to prove that a given polynomial P(X) does not have small expressions. In this result, we solve exactly this problem.

More precisely, we prove that certain explicit polynomials have no polynomial-sized "Sigma-Pi-Sigma" (sums of products of sums) representations. We can also show similar results for Sigma-Pi-Sigma-Pi, Sigma-Pi-Sigma-Pi-Sigma and so on for all "constant-depth" expressions.

The talk is based on a joint work of Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas.