8
$\begingroup$

This question is related to a previous unanswered question of mine. Please see that question for background.

When Håstad proved that computing tensor rank is NP-complete, the rank in question was allowed to be part of the input. Specifically, given a Boolean formula with $n$ variables and $m$ clauses, Håstad constructed a tensor that has rank exactly $4n+2m$ if the formula is satisfiable and has some larger rank otherwise.

What if we fix the bound on the rank to some constant? For example...

What is the complexity of deciding if a tensor has rank at most 3?

The tensor should be defined over an infinite field, otherwise the problem is trivial (...only a finite number of things to check). Answers for the natural infinite fields $\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{C}$ would be best. I am personally interested in this question using the complex numbers.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

Testing for constant border-rank can be done in polynomial-time, I'm pretty sure, if you're talking about tensors of fixed arity. More precisely, testing for border-rank $\leq r$ in $\mathbb{C}^{d_1} \otimes \dotsb \otimes \mathbb{C}^{d_k}$ can be done in something like $k(d_1 d_2 \dotsb d_k)^{2(r+1)}$ evaluations of $(r+1) \times (r+1)$ determinants plus some additional constant work (constant depending on $r$). Update 2022-02-10: work of order $f(r) \cdot \prod_{i} \binom{d_i}{r}$, so for $k,r$ constant, this is still polynomial in the $\{d_i\}$.

Theorem 3.7.1.1 of Landsberg's tensor book ("Inheritance") says that the equations for the variety of tensors of border-rank $\leq r$ in $\mathbb{C}^{d_1} \otimes \mathbb{C}^{d_2} \otimes \dotsb \otimes \mathbb{C}^{d_k}$ are given by the equations for border-rank $r$ in $\mathbb{C}^r \otimes \mathbb{C}^r \otimes \dotsb \otimes \mathbb{C}^r$ (Update 2022-02-10: applied by choosing $r$ out of the $d_i$ coordinates in all possible ways) together with all $(r+1) \times (r+1)$ minors of flattenings. Since $r = O(1)$, there are only finitely polynomially many equations of the former type.

Border-rank 1 = rank 1, and more generally rank $\leq r$ implies border-rank $\leq r$. But border-rank 2 can have rank anywhere from $2$ to the arity $k$, and border-rank $3$ in arity 3 can have ranks 3, 4, or 5. Beyond that I don't know about testing for rank.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Yes, fixed arity. This book looks great. The naive system of polynomial equations to check for rank at most $r$ (for arity $k$ and $d = d_1 = \dotsb d_k$) has $d r$ variables in $d^k$ equations, each of degree $k$ with $r$ monomials. Are the equations for the variety of tensors of border-rank $\le r$ significantly simpler than this? $\endgroup$
    – Tyson Williams
    Commented Oct 25, 2013 at 21:53
  • $\begingroup$ If you're talking about the naive equations you get by expressing a variable rank-r tensor and then setting it = to your tensor $T$, then there's a key difference. In that setting, you setup a system of equations that depend on $T$, and then check if the system has a solution. In the equations for border-rank I was talking about, you simply plug the coordinates of your tensor into the equations and make sure they all evaluate to zero. For fixed $r$ and $k$, the only equations that aren't of O(1) size are determinants, so are easy to evaluate. $\endgroup$
    – Joshua Grochow
    Commented Oct 26, 2013 at 15:07
  • $\begingroup$ Note: checking if a system of equations over $\mathbb{Z}$ has a solution in $\mathbb{C}$ is in PSPACE unconditionally and in PH assuming the generalized Riemann hypothesis. In the Blum-Shub-Smale model (or even the usual Boolean model, if working over finite fields), solving systems of equations is NP-complete. So this seems much harder than merely evaluating equations, as in the case of border-rank. $\endgroup$
    – Joshua Grochow
    Commented Oct 26, 2013 at 15:09
  • $\begingroup$ For others reading this question, the first two chapters of Landsberg's book are available online. $\endgroup$
    – Tyson Williams
    Commented Oct 30, 2013 at 20:09
  • $\begingroup$ Oh, the "naive system of polynomials" I spoke about in my first comment is for checking symmetric (aka Waring) rank. $\endgroup$
    – Tyson Williams
    Commented Nov 1, 2013 at 1:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.