Years ago I attended a conference where they taught us that matrix multiplication can be represented by a tensor. The rank of the tensor is important, because putting it into minimal rank form minimizes multiplications, so this seems like an important computational problem.
At the time (in 2007) the rank of 3×3 matrix multiplication was not known. Is this currently known? If not, what are the best known bounds, and why is it so difficult to compute?
Federico Poloni's answer is up to date as far as I know, and his explanation of the difficulty is good, but here's another way to think about it. It's less concrete than his explanation, but perhaps useful.
The thing that confuses people is that matrix rank is not hard to compute. This is what we're used to, and it seems strange that computing tensor rank should be so much harder (for example, Håstad proved it is NP-hard). However, this is thinking about it backwards: tensor rank is the sort of thing we should expect to be hard, and the interesting part is that matrix rank is so much easier. The fundamental reason is symmetry. An $n \times n$ matrix involves $n^2$ parameters, and the general linear group is also $n^2$-dimensional, so it's reasonable to hope we can reduce every matrix to a simple canonical form by linear transformations. Indeed, we can reach row-echelon form, at which point we can simply read off the rank. By contrast, an $n \times n \times n$ tensor is $n^3$-dimensional, but there just isn't an equally large group acting on it. Instead, you still have quadratic-dimensional groups acting in several ways, which isn't nearly enough to reach any simple canonical form. Even after you mod out by all available symmetry, the dimension of the space of tensors is nearly as high as it was to start with, and you end up stuck.
For comparison, imagine trying to find the rank of a $9 \times 9$ matrix by a brute force search for rank-one summands, without using any simplifying transformations. That would be awful, and a $9 \times 9 \times 9$ tensor is far worse than that. Symmetry is our best tool by far, and when it is insufficient we don't have much to fall back on.
I think the best known result for the complexity of an exact algorithm for multiplying 3 by 3 matrices is 23 multiplications. Here is some recent work to find more algorithms since Laderman's 1976 result:
http://dl.acm.org/citation.cfm?id=2500627
They find inequivalent algorithms, but still require 23 multiplications.
One thing to clarify from Federico's post. To specify any 9x9x9 tensor, you need to specify at most 9*9*9 = 729 parameters. To specify a rank 1 9x9x9 tensor, you could specify 9+9+9 = 27 parameters, but because of scaling you actually only need to specify 8 + 8 + 8 + 1 = 25 parameters (specify three 9-dimensional vectors up to scale, take their tensor product and then rescale globally).
To specify a rank 19 tensor (as a sum of 19 rank one tensors) you need to specify 19*25 = 425 parameters. This is much less than Federico estimated, but still very large, and still not feasible to do a brute force search.
About approximate rank, Schönhage found an approximate algorithm for 3x3 matrix multiplication that only uses 21 multiplications.
http://epubs.siam.org/doi/abs/10.1137/0210032
The state of the art on lower bounds for rank and border rank for matrix multiplication (I think) is contained in these:
arxiv:1112.6007
arxiv:1206.1530
Stothers' thesis, from 2010, p. 18, lists 19 and 23 as the current lower and upper bounds. These are the same numbers that I have heard from some researchers in the field, and I don't think there has been any improvement since then.
Why is it a difficult problem? Simply because it is high-dimensional, non-convex optimization problem, with lots of local minima. To specify a rank-19 9x9x9 tensor, for instance, you need about 19x9x9x9 19x(9+9+9) entries (slightly less since you can normalize some things, actually), so that's the kind of dimensionality you are dealing with. Computers still can't deal reliably with this number of degrees of freedom for a problem like this. Even testing all possible decompositions with entries in $\{-1,0,1\}$ is not feasible.
Another difficulty for killing the problem numerically is that solutions can be "at infinity": for instance, let $T_\epsilon$ be the tensor such that $$ T(:,:,1)=\begin{bmatrix}1 & 0\\ 0 & 1 \end{bmatrix}, T(:,:,2)=\begin{bmatrix}0 & 1 \\ 0 & \epsilon \end{bmatrix}. $$
$T_0$ has rank $3$, but any $T_\epsilon$ with $\epsilon \neq 0$ has rank 2. The decomposition can be parametrized explicitly and contains some $\epsilon^{-1}$ entries. So if you run an optimization algorithm to find a rank-2 decomposition of $T_0$, the residual will converge to 0, but at the same time the single entries of the decomposition will diverge. In geometrical terms, the sets $S_\ell = \{T: \operatorname{rank} T \leq \ell \}$ are not closed, unlike in the matrix case.
EDIT: fixed error in number of degrees of freedom; see Luke Oeding's answer.
