Colloquium Summer 2022

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.

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.

Speaker: Bharat Adsul

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.

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.

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.

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