8
$\begingroup$

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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Klim
    Commented Jul 11, 2012 at 3:47
  • $\begingroup$ @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.) $\endgroup$
    – Joshua Grochow
    Commented Jul 11, 2012 at 4:18
  • $\begingroup$ No $f$ may not depend on all its inputs. $\endgroup$
    – Klim
    Commented Jul 11, 2012 at 5:09

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.