Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Boris Alexeev:

TR11-010 | 1st February 2011
Boris Alexeev, Michael Forbes, Jacob Tsimerman

Tensor Rank: Some Lower and Upper Bounds

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). ... more >>>

ISSN 1433-8092 | Imprint