Exact mat-mat-mul is fine and all (congrats to the authors), but I'm much more interested in approximate mat-vec-mul. Specifically: (1) Pre-process an nxn matr

Exact mat-mat-mul is fine and all (congrats to the authors), but I'm much more interested in approximate mat-vec-mul. Specifically: (1) Pre-process an nxn matrix m into f(m). Any transformation is allowed, but to work well on all matrices and input vectors it's not possible to rely solely on compression techniques (random sampling, low-rank+sparse approximation, ...). (2) Compute an approximation of m@v via some computation g(f(m), v) in less than O(n^2) time (ideally being able to trade off accuracy for speed). Above a certain performance threshold, this necessarily means you only use a part of f(m) for any one vector v. There's a zero-error O(n) solution that computes a hash table of all possible matrix-vector products, so I'll be picky and add the constraint that pre-processing time/space are "reasonable".