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. Usually, the talks have a hybrid format with an additional Zoom link.

The schedule will be updated regularly.

Planned Talks
Speaker
Title (Format)
Date
Starts
Chiara Meroni
The Zonoid Problem: discotopes
18.05.22
15:00
---
--- No talk ---
25.05.22
---
Pascal Koiran
Black Box Absolute Reconstruction for Sums of Powers of Linear Forms
01.06.22
15:00
Lie algebraic methods for orbit closures
08.06.2022
15:00
Pranjal Dutta
Exponential-gap fanin-hierarchy for border depth-3 circuits
14.06.2022
09:15
Rafael Oliveira
Radical Sylvester-Gallai theorem for cubics - and beyond
29.06.2022
15:00
Irit Dinur
cancelled
30.06.2022
15:00
---
--- No talk ---
06.07.2022
---
Matías Bender
Efficient Computation of Multi-parameter Persistence
13.07.2022
15:00
Carlos Améndola
postponed
20.07.2022
15:00

## Abstracts

### The Zonoid Problem: discotopes

Speaker: Chiara Meroni

A classical problem in convex geometry asks for a way to recognize zonoids. The latter are limits, in the Hausdorff metric, of Minkowski sums of segments. The Zonoid Problem is a hard problem from many points of view, but it is solved for the polytopal case. What happens more in general? I will discuss the theory and then focus on the family of discotopes. These are Minkowski sums of discs, hence they are semialgebraic zonoids. We will see how methods from algebraic geometry can be used to get information about the boundary of discotopes.

### Black Box Absolute Reconstruction for Sums of Powers of Linear Forms

Speaker: Pascal Koiran

We give the first (randomized) polynomial time algorithm for the following problem: given a homogeneous polynomial of degree d, decide if it can be written as a sum of d-th powers of linearly independent complex linear forms. This is joint work with Subhayan Saha. A preprint is available at arxiv.org/pdf/2110.05305.

### Lie algebraic methods for orbit closures

Consider a linear action of a group G on a vector space V and the resulting orbits (affine and projective) and their closures. A key question is: when is an orbit in the closure of another? Luna's theorem builds a tubular-model of the neighbourhood of an affine closed orbit starting with a normal slice and helps answer the key question by relating stabilizers in the neighbourhood.

We construct a Luna-style local model which is applicable at any point; however it is restricted to a neighbourhood of that point and supports only the associated Lie algebra action. We give an explicit description of this Lie algebra action. An important consequence is that Lie algebras of stabilizers of points in the neighbourhood are parameterized by subspaces of the Lie algebra of the stabilizer of the point under consideration. The local model also leads us to understand the projective orbit closures of matrices, for the conjugation action of GL(n) on matrices.

### Exponential-gap fanin-hierarchy for border depth-3 circuits

Speaker: Pranjal Dutta

Mulmuley and Sohoni (2001) proposed an ambitious program, the Geometric Complexity Theory (GCT), to prove P != NP and related conjectures using algebraic geometry and representation theory. Surprisingly, (Kumar ToCT’20) proved the universal power of the border of top-fanin-2 depth-3 circuits (Σ^[2]ΠΣ-bar); which is in complete contrast to its classical model.

In this talk, we outline our result: border of bounded-top-fanin depth-3 circuits is relatively easy-- it can be computed by a polynomial-size algebraic branching program (ABP). Our de-bordering paradigm will build on the technique called --DiDIL (divide, derive, induct, with limit). Further, we show a strongly-exponential separation between any two consecutive border classes, Σ^[k]ΠΣ-bar and Σ^[k+1]ΠΣ-bar, establishing an optimal hierarchy of constant top-fanin border depth-3 circuits.

This is based on two works - one with Prateek Dwivedi and Nitin Saxena, that appeared in FOCS'21 (pdf), and the other with Nitin Saxena, whose preprint is available.

### Radical Sylvester-Gallai theorem for cubics - and beyond

Speaker: Rafael Oliveira

In 1893, Sylvester asked a basic question in combinatorial geometry: given a finite set of distinct points $v_1, \ldots, v_m \in \R^N$ such that the line defined by any pair of distinct points $v_i, v_j$ contains a third point $v_k$ in the set, must all points in the set be collinear? This question was independently answered in the affirmative by Melchior and Gallai, and is now known as the Sylvester-Gallai theorem.

Generalizations of Sylvester's problem, which are known as Sylvester-Gallai type problems, have found applications in algebraic complexity theory (in Polynomial Identity Testing and reconstruction) and coding theory (Locally Correctable Codes). The underlying theme in all these types of questions is the following:

Are Sylvester-Gallai type configurations always low-dimensional?

In 2014, Gupta, motivated by such applications in algebraic complexity theory, proposed wide-ranging **non-linear** generalizations of Sylvester's question, with applications on the PIT problem.

In this talk, we will discuss these non-linear generalizations of Sylvester's conjecture, their intrinsic relation to algebraic computation, and a recent theorem proving that radical Sylvester-Gallai configurations for cubic polynomials must have small dimension.

Joint work with Akash Kumar Sengupta.

### Efficient Computation of Multi-parameter Persistence

Speaker: Matías Bender

Multi-parameter persistent homology is a tool in Topological Data Analysis to study, roughly speaking, the homology of point clouds. Carlsson, Singh, and Zomorodian showed how to compute this object using commutative algebra and Gröbner bases. However, in practice, the available Gröbner bases implementations can not deal with inputs of interest for TDA. For this reason, in this tak we introduce an efficient Gröbner bases algorithm to compute a minimal presentation of a multi-parameter persistent homology module, given a chain complex of free modules as input. Our approach extends previous work on this problem in the 2-parameter case, and draws on ideas underlying the F4 and F5 algorithms for Gröbner basis computation. In the $r$-parameter case, our algorithm computes a presentation for the homology of $C \xrightarrow{F} A \xrightarrow{G} B$ in $O(r^2 \, |A|^{r+1} + |A|^{r} \, |B| + |A|^{r-1} \, |B|^2 + r \, |A|^2 \, |C|)$ arithmetic operations, where $|\cdot|$ denotes the rank. We implement this approach in our new C++ software Muphasa. This talk in based on joint work with Oliver Gäfvert (Oxford) and Michael Lesnick (SUNY Albany).