Matrix-vector multiplication in sub-quadratic time (some preprocessing required)

We show that any n × n matrix A over any finite semiring can be preprocessed in O(n 2+ε) time, such that all subsequent vector multiplications with A can be performed in O(n²/(ε log n) 2) time, for all ε> 0. The approach is combinatorial and can be implemented on a pointer machine or a (log n)-word RAM. Some applications are described