Tensor Rank: Some Lower and Upper Bounds

J. E. Hopcroft and L. R. Kerr, On minimizing the number of multiplications necessary for matrix multiplication , SIAM J. Appl. Math. 20

1971

Earlier work this paper cites.

Volker Strassen, Vermeidung von Divisionen , J. Reine Angew. Math. 264

1973

Earlier work this paper cites.

by same author, Die Berechnungskomplexität der symbolischen Differentiation von Interpolationspolynomen , Theor. Comput. Sci. 1

1975

Earlier work this paper cites.

Jean-Pierre Serre, Linear representations of finite groups , Springer-Verlag, New York, 1977, Translated from the second French edition by Leonard L. Scott, Graduate Texts in Mathematics, Vol. 42. MR 0450380 (56 #8675)

1977

Earlier work this paper cites.

Joseph Ja’Ja’, Optimal evaluation of pairs of bilinear forms , SIAM J. Comput. 8

1979

Earlier work this paper cites.

Mark R. Brown and David P. Dobkin, An improved lower bound on polynomial multiplication , IEEE Trans. Comput. 29

1980

Earlier work this paper cites.

L. G. Valiant, Negation can be exponentially powerful , Theoret. Comput. Sci. 12

1980

Earlier work this paper cites.

Walter Baur and Volker Strassen, The complexity of partial derivatives , Theoret. Comput. Sci. 22

1983

Earlier work this paper cites.

K. A. Kalorkoti, A lower bound for the formula size of rational functions , SIAM J. Comput. 14

1985

Cited alongside, same era.

A. M. Vershik and S. V. Kerov, Asymptotic behavior of the maximum and generic dimensions of irreducible representations of the symmetric group , Funktsional. Anal. i Prilozhen. 19

1985

Cited alongside, same era.

Joachim von zur Gathen, Algebraic complexity theory , Annual review of computer science, Vol. 3, Annual Reviews, Palo Alto, CA, 1988, pp. 317–347. MR 1001207 (91a:68150)

1988

Cited alongside, same era.

J. Håstad, Tensor rank is NP-complete , ICALP ’89: Proceedings of the 16th International Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci., vol. 372, Springer, Berlin, 1989, pp. 451–460, doi:10.1007/BFb0035776

1989

Cited alongside, same era.

by same author, Tensor rank is NP-complete , J. Algorithms 11

Markus Bläser, A 5 2 ​ n 2 \frac{5}{2}n^{2} -lower bound for the rank of n × n n\times n -matrix multiplication over arbitrary fields , 40th Annual Symposium on Foundations of Computer Science (New York, 1999), IEEE Computer Soc., Los Alamitos, CA, 1999, pp. 45–50, doi:10.1109/SFFCS.1999.814576

1999

Later among the works it cites.

J. H. van Lint, Introduction to coding theory , third ed., Graduate Texts in Mathematics, vol. 86, Springer-Verlag, Berlin, 1999. MR MR1664228 (2000a:94001)

1999

Later among the works it cites.

Amir Shpilka and Avi Wigderson, Depth-3 arithmetic formulae over fields of characteristic zero , Journal of Computational Complexity 10

2001

Later among the works it cites.

J. H. van Lint and R. M. Wilson, A course in combinatorics , second ed., Cambridge University Press, Cambridge, 2001. MR 1871828 (2002i:05001)

2001

Later among the works it cites.