Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:How hard is the tensor rank?
Speaker:Yaroslav Shitov
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 19 June 2018
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
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
Name(s):Christian Ikenmeyer
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
Created:Christian Ikenmeyer, 06/11/2018 01:16 PM Last modified:Uwe Brahm/MPII/DE, 06/19/2018 04:01 AM
  • Christian Ikenmeyer, 06/12/2018 10:11 PM
  • Christian Ikenmeyer, 06/11/2018 01:16 PM -- Created document.