Algebraic Complexity

Some of this work [2,3,4,5] was motivated by the formulation of the matrix multiplication problem in the setting of computing families of bilinear forms. Such a family determines a 3-tensor and this has a rank (a generalisation of matrix rank) that determines its complexity. During the 1970s there was some optimism within the algebraic complexity community that a general understanding of tensor rank would lead to a good (even practical) solution of the matrix multiplication problem and other similar problems of linear algebra. Sadly, although several advances on the matrix multiplication problem were made, the algorithms became increasingly complicated and impractical, and in the end most researchers gave up. My work was on the general theory rather than on the specific instance of matrix multiplication.

On the other hand [1,6,7,8] are concerned with algorithms for more specific problems and their titles describe the content pretty well.

Papers on algebraic complexity

  1. Mathematics in the service of computer programming, Math. Spectrum 10 (1977), 6-11.
  2. The complexity of group algebra computations, Theor. Comp. Sci. 5 (1977), 205-209.
  3. On the maximal multiplicative complexity of a family of bilinear forms, Linear Alg. and Appl. 27 (1979), 1-8 (with N.M. Stephens).
  4. Bounds on the ranks of some 3-tensors, Linear Alg. and Appl. 31 (1980) 19-31 (with S. Lloyd).
  5. The ranks of m x n x (mn-2) tensors, SIAM J. Computing 12 (1983), 611-615 (with S. Lloyd).
  6. How to compute the series expansions of sec x and tan x, Amer. Math. Monthly 93 (1986), 387-389.
  7. On the computation of group characters, J. Symbolic Computation 2 (1986), 45-50 (with R.A. Hassan).
  8. A practical algorithm for boolean matrix multiplication, Information Processing Letters 29 (1988) 37-38 (with N. Santoro).