Complexity of matrix multiplication over $\mathbb F_2$

Question

I've been reading about theoretical bounds on the computational complexity of $n\times n$ matrix-matrix multiplication in floating-point arithmetic, about how the complexity is known to fall between $\mathcal O(n^2)$ and $\mathcal O(n^3)$, and how the exponent has been slowly whittled down over time by various researchers. It's currently unknown whether a $\mathcal O(n^2)$ algorithm is possible.

I was wondering about what the complexity of multiplying two bit-matrices over the finite field $\mathbb F_2$ (or other finite fields - my intuition tells me the complexity will be the same), but I haven't found any references online. Are there any known "tricks" for multiplying matrices in $\mathbb F_2^{n\times n}$ that makes it less expensive than multiplication in larger fields or in floating point? What current bounds are known? Is there a known $\mathcal O(n^2)$ algorithm? Can anyone provide any relevant references for these sort of questions?

Answer 1

In general, it is no more efficient to multiply over $\mathbb{F}_2$ compared to over $\mathbb{R}$ unless you have sparse matrices or special structure.

Even though there are efficient algorithms for certain arithmetic and polynomial operations over finite fields (and in particular $\mathbb{F}_2$ this efficiency does not seem to extend to make an asymptotic difference in the complexity of matrix multiplication.

See the answers in mathoverflow to a similar question for more details, I will quote a small part from there below:

For $\mathbb{F}_2$ (and other finite fields of characteristic $2$) there is a specialized library for computing with matrices over that structure.

It is called M4RI. In particular, a paper by developpers of the library: Martin Albrecht, Gregory Bard, William Hart. Algorithm 898: Efficient Multiplication of Dense Matrices over GF(2). ACM Transactions on Mathematical Software 2010.

Preprint at http://arxiv.org/abs/0811.1714.

Edit:

Thanks to @pcpthm for pointing this out, the claim below for the average complexity would not hold over $\mathbb{F}_2$ in such generality. Since the result over boolean algebras may still be of interest I will let the paragraph below stand.

However, due to the special structure of $\mathbb{F}_2,$ one can actually prove that on average matrix multiplication can be performed with complexity $O(n^{2+\varepsilon})$ elementary operations by a randomized algorithm, see this paper.