# Space complexity of Coppersmith–Winograd algorithm

Coppersmith–Winograd algorithm is the asymptotically fastest known algorithm for multiplying two $n \times n$ square matrices. The running time of their algorithm is $O(n^{2.376})$ which is the best known so far. What is the space complexity of this algorithm ? Is it in $\Theta(n^2)$ ?

Yes, all algorithms which stem from Strassen's original algorithm (this includes most known $n^{3-\varepsilon}$ algorithms for matrix multiplication, but not all -- see the comments) have space complexity $\Theta(n^2)$. If you could find a $n^{3-\varepsilon}$ time algorithm with $poly(\log n)$ space complexity, this would be a great advance. One application would be a $2^{(1-\varepsilon)n}$ time, $poly(n)$ space algorithm for the Subset-Sum problem.
• Yeah, those too. My understanding is that they are doing a special kind of convolution (an FFT over a special group), but the convolution is over objects of size $\Theta(n^2)$. No small-space algorithms (with time complexity better than the obvious algorithm) are known for convolutions of vectors over integers, and I imagine it's only harder to get small-space convolutions over these groups. – Ryan Williams Sep 15 '10 at 3:51
• How can one have $poly(logn)$ space when it takes $2n^{2}$ space to store the entries of the matrices? – 1.. Oct 23 '10 at 2:10
• Because in the usual way in which space complexity is measured, the input is not counted towards the space bound. The input is treated as "read only", and we measure how much extra "read-write" memory is needed to compute the function. In this case, only $O(log n)$ extra space is sufficient when the input entries are bounded (e.g., 0 or 1) and you use $O(n^3)$ operations. – Ryan Williams Oct 23 '10 at 5:08