direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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

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.

Planned Talks
Speaker
Title
Date
Starts
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

Abstracts

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

 

 

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.