Paper Info
Title
The Complexity of Tensor Rank.
Abstract
We show that determining the rank of a tensor over a field has the same complexity as deciding the existential theory of that field. This implies earlier -hardness results by Håstad (J. Algorithm. (4), 644–654 ). The hardness proof also implies an algebraic universality result.
Year
DOI
Venue
2018
https://doi.org/10.1007/s00224-017-9800-y
Theory Comput. Syst.
Keywords
DocType
Volume
Computational complexity,Existential theory of fields,Tensor rank
Journal
abs/1612.04338
Issue
ISSN
Citations 
5
1432-4350
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Marcus Schaefer1865.27
Daniel Stefankovic224328.65