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