8

Is it known if tensor rank of three dimensional tensors lies in VNP (non deterministic valiant class)? If yes, what is known about high dimensional tensor rank?

In fact I am interested in much more simple problem. I would like to know if one can construct class non-zero polynomials $f_n$ which lies in VNP, in $n^3$ variables such that $f_i(T)=0$ if tensor rank of $T$ less than $n^{1.9}$. For simplicity let us assume that we are working over $\mathbb{C}$.

I would like to mention that it is O.K. if $f_i(T)=0$ for $T$ of high rank only what I need is that $f_i(T)=0$ for all small rank tensors.

Klim
  • 903
  • 4
  • 16

1 Answers1

9

The collection of tensors of a given rank, or even of tensors with rank at most $k$ is not a (Zariski-)closed set, so it cannot be described as the vanishing locus of any set of polynomials, regardless of their complexity. (However, over finite fields tensor-rank is $NP$-complete and over $\mathbb{Q}$ it is $NP$-hard but not known to be in $NP$. But these are the usual Boolean classes, not the Valiant analogues.)

The closure of the the set of tensors of rank at most $k$ is the set of tensors of border-rank at most $k$. Call a set of polynomials whose vanishing locus is the set of tensors of border-rank at most $k$ a system of (set-theoretic) defining equations for border rank at most $k$. Such defining equations are known for small $k$, but for most $k$ finding such defining equations is a long-standing open problem, related the border-rank and multiplicative complexity of matrix multiplication.

See Landsberg's Bulletin article Geometry and the complexity of matrix multiplication for an introduction and some references, and see Landsberg's recent book Tensors: Geometry and Applications (freely available introduction) for all that is known about defining equations for border-rank.

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
  • Thanks for answer. I would like just to note that it will be O.K. if $f(T)=0$ for $T$ of high rank I need only that $f(T)=0$ on all small rank tensors. – Klim Jul 11 '12 at 03:47
  • @Klim: Presumably you also want $f$ to be not the zero function... Beyond that, is there some additional nontriviality condition you want $f$ to have, for example, that $f$ depend on all $n^{3}$ of its inputs? (If so you might add that clarification to the question.) – Joshua Grochow Jul 11 '12 at 04:18
  • No $f$ may not depend on all its inputs. – Klim Jul 11 '12 at 05:09