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!

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: Joseph M. Landsberg

I will describe the largest possible symmetry groups of tensors satisfying natural genericity conditions motivated by complexity theory. The study was motivated by the complexity of matrix multiplication and the search for upper bounds, in light of work of Ambainus-Filmus-LeGall that says that the best tensor used for such upper bounds, the so-called big Coppersmith-Winograd tensor could not be used to prove the exponent is less than 2.3. The conjecture is that the exponent is two, i.e., it is nearly as easy to multiply large matrices as it is to add them. I will not assume any familiarity with matrix multiplication complexity.
This is joint work with A. Conner, F. Gesmundo, and E. Ventura.

Speaker: Joshua Grochow

We study the complexity of isomorphism problems for tensors, groups, and polynomials. These problems have been studied in multivariate cryptography, machine learning, quantum information, and computational group theory. We show that these problems are all polynomial-time equivalent. Our main technical result is a polynomial-time reduction from d-tensor isomorphism to 3-tensor isomorphism, which uses the Leavitt path algebra of a certain graph (quiver). In the context of quantum information, this result gives multipartite-to-tripartite entanglement transformation procedure, that preserves equivalence under stochastic local operations and classical communication (SLOCC). Based on joint work with Y. Qiao (ITCS '21, preprint of full version at arXiv:1907.00309) and with V. Futorny & V. V. Sergeichuk (Lin. Alg. Appl. 2019, arXiv preprint arXiv:1810.09219).

Speaker: Radu Curticapean

Immanants are matrix functionals that generalize determinants and permanents. Given an irreducible character χ_λ of S_n for some partition λ of n, the immanant associated with λ is a sum-product over permutations π in S_n, much like the determinant, but with χ_λ(π) playing the role of sgn(π).

Hartmann showed in 1985 that immanants can be evaluated in polynomial time for sign-ish characters. More precisely, for a partition λ of n with s parts, let b(λ) := n−s count the boxes to the right of the first column in the Young diagram of λ. The immanant associated with λ can be evaluated in n^O(b(λ)) time.

Since this initial result, complementing hardness results have been obtained for several families of immanants derived from partitions with unbounded b(λ). This includes permanents, immanants associated with hook characters, and other classes. In this talk, we complete the picture of hard immanant families: Under a standard assumption from parameterized complexity, we rule out polynomial-time algorithms for (well-behaved) immanant families with unbounded b(λ). For immanant families in which b(λ) even grows polynomially, we establish hardness for #P and VNP.

Available on arXiv: https://arxiv.org/abs/2102.04340

Speaker: Saugata Basu

In the talk I will describe recent work on proving upper 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 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.
Joint work with Antonio Lerario.

Speaker: Frank Sottile

Numerical homotopy methods for solving systems of polynomial equations may follow far more paths than solutions, if the equations possess extra structure. Devising methods to handle such structure has long been a focus in the area, with the most well-known being the polyhedral homotopies for sparse systems of polynomials. This method is optimal for square systems which achieve the BKK polyhedral bound.

Algebraic geometry is a source of systems that have rich structure, and which may be overdetermined. A particular well-studied class of such systems comes from the Schubert calculus on the Grassmannian. With Leykin, Martin del Campo, Vakil and Verschelde, we described and implemented the Littlewood-Richardson homotopy for Schubert calculus, which is based on Vakil's geometric Littlewood-Richardson rule. This has two independent implementations in Macaulay 2 and in PHCPack. My talk will sketch this background and explain the main features of this algorithm.

Speaker: Harm Derksen

Reutenauer and Fortin defined the commutative and non-commutative rank for a matrix whose entries are linear functions. I will discuss this notion and its connections to Geometric Invariant Theory, the notion of tensor rank and Algebraic Complexity Theory.
This is joint work with Visu Makam.

Speaker: Yairon Cid-Ruiz

This talk is devoted to the study of multigraded algebras and multigraded linear series. For a multigraded algebra A, we define and study its volume function, which computes the asymptotics of the Hilbert function of A. We relate the volume function to the volume of the fibers of the global Newton-Okounkov body of A. Unlike the classical case of standard multigraded algebras, the volume function is not a polynomial in general. However, in the case when the algebra A has a decomposable grading, we show that the volume function is a polynomial with non-negative coefficients. We then define mixed multiplicities in this case and provide a full characterization for their positivity. Furthermore, we apply our results on multigraded algebras to multigraded linear series.
Our work recovers and unifies recent developments on mixed multiplicities. In particular, we recover results on the existence of mixed multiplicities for (not necessarily Noetherian) graded families of ideals and on the positivity of the multidegrees of multiprojective varieties.
This talk is based on joint work with Fatemeh Mohammadi and Leonid Monin.

Speaker: Jean-Philippe Labbé

From a geometric point of view, Pauli's exclusion principle defines a hypersimplex. This convex polytope describes the compatibility of 1-fermion and N-fermion density matrices, therefore it coincides with the convex hull of the pure N-representable 1-fermion density matrices. By employing ideas from convex analysis and combinatorics, we present a comprehensive solution to the convex relaxation of the 1-body N-representability problem. In particular, we adapt and further develop tools such as symmetric polytopes, sweep polytopes, and Gale order. For both fermions and bosons, generalized exclusion principles are discovered. These exclusion principles are expressed as linear inequalities satisfying a hierarchy. The two families of polytopes resulting from these inequalities are part of the new class of so-called lineup polytopes.
This is joint work with physicists Julia Liebert, Christian Schilling and mathematicians Eva Philippe, Federico Castillo and Arnau Padrol.

Speaker: Mrinal Kumar

The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of zeroes of a multivariate polynomial on a product set. This lemma motivates the multiplicity codes of Kopparty, Saraf and Yekhanin, who showed how to use this lemma to construct high-rate locally-decodable codes. However, the algorithmic results about these codes crucially rely on the fact that the polynomials are evaluated on a vector space and not an arbitrary product set.
In this work, we show how to decode multivariate multiplicity codes of large multiplicities in polynomial time over finite product sets (over fields of large characteristic and zero characteristic). Previously such decoding algorithms were not known even for a positive fraction of errors. In contrast, our work goes all the way to the distance of the code and in particular exceeds both the unique decoding bound and the Johnson bound. For errors exceeding the Johnson bound, even combinatorial list-decodablity of these codes was not known.
Our algorithm is an application of the classical polynomial method directly to the multivariate setting. In particular, we do not rely on a reduction from the multivariate to the univariate case as is typical of many of the existing results on decoding codes based on multivariate polynomials.
Based on joint work with Siddharth Bhandari, Prahladh Harsha and Madhu Sudan.