Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-010 | 1st February 2011 05:00

Tensor Rank: Some Lower and Upper Bounds

RSS-Feed




TR11-010
Authors: Boris Alexeev, Michael Forbes, Jacob Tsimerman
Publication: 1st February 2011 05:45
Downloads: 4284
Keywords: 


Abstract:

The results of Strassen and Raz show that good enough tensor rank lower bounds have implications for algebraic circuit/formula lower bounds.

We explore tensor rank lower and upper bounds, focusing on explicit tensors. For odd d, we construct field-independent explicit 0/1 tensors T:[n]^d->F with rank at least 2n^(floor(d/2))+n-Theta(d log n). This matches (over F_2) or improves (all other fields) known lower bounds for d=3 and improves (over any field) for odd d>3.

We also explore a natural class of tensors, which we call group tensors. For any group G, we define the group tensor T_G^d:G^d->F, by T_G^d(g_1,...,g_d)=1 iff g_1 x ... x g_d=1_G. We give two upper bounds for the rank of these tensors, the first using representation theory (for large fields) and the second using interpolation (over any field). Each show that group tensors have far from maximal rank, which is very different from the matrix case and thus eliminates many natural candidates for high tensor rank.

Monotone tensor rank is also considered. We give explicit 0/1 tensors T:[n]^d->F that have tensor rank at most dn but have monotone tensor rank exactly n^(d-1). This is a nearly optimal separation.



ISSN 1433-8092 | Imprint