Campus Event Calendar
Event Entry
What and Who
How hard is the tensor rank?
Yaroslav Shitov
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 19 June 2018
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We present a full description of the algorithmic complexity of computing the tensor rank. Namely, computing the rank of a tensor with respect to an integral domain is polynomial time equivalent to solving a system of polynomial equations over that domain. In particular, computing the rank of a tensor over the integers is an undecidable problem. Our proof uses a reduction from the minimal rank matrix completion problem, and if time allows, we will present a related technique that lead to counterexamples to Strassen's direct sum and Comon's conjectures.
Contact
Christian Ikenmeyer
--email hidden
passcode not visible
logged in users only
Christian Ikenmeyer, 06/12/2018 22:11
Christian Ikenmeyer, 06/11/2018 13:16 -- Created document.
Christian Ikenmeyer, 06/11/2018 13:16 -- Created document.