Inhalt des Dokuments
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.
|Joseph M. Landsberg ||Tensors with maximal symmetries||14.04.2021||15:00|
|Joshua Grochow ||On the
Complexity of Isomorphism Problems for Tensors, Groups, and
Polynomials: Tensor Isomorphism-Completeness||28.04.2021||15:00|
|Radu Curticapean ||The
complexity of immanants||05.05.2021||15:00|
approximations and volume of tubes of singular algebraic
|Frank Sottile||The Optimal
|Harm Derksen||The Non-Commutative
Rank of a Linear Matrix||09.06.2021||15:00|
algebras and multigraded linear series||16.06.2021||15:00|
polytopes and applications in quantum physics||23.06.2021||15:00|
|Mrinal Kumar||Algorithms for
Decoding Multivariate Multiplicity Codes over Product
Tensors with maximal symmetries
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.
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials: Tensor Isomorphism-Completeness
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 ).
The complexity of immanants
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 
Hausdorff approximations and volume of tubes of singular algebraic sets
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.
The Optimal Littlewood-Richardson Homotopy
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.
The Non-Commutative Rank of a Linear Matrix
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.
Multigraded algebras and multigraded linear series
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.
Lineup polytopes and applications in quantum physics
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.
Algorithms for Decoding Multivariate Multiplicity Codes over Product Sets
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.