January 31, 2013:
A new version of the report,
“Sparse Matrix Computations over Small Fields: A
Simpler Block Lanczos Algorithm and Its Analysis”
is now available. All appendices have now been revised.
An error in Theorem 2.4 in the main body of the paper
has been corrected: While storage statements previously
stated were asymptotically correct the multiplicative
constant in the original statement of the theorem was not.
A more modest claim, providing an asymptotic bound on storage
requirements, is now provided.
The statement of Lemma 4.2 has been corrected —
to indicate that w1 = A⋅w, and not
A⋅w + b: The claim would be false without
this change.
Finally, a typographical error in the bounds on expectations
included in Lemma 6.1 has been corrected (the bounds
are actually significantly better than as indicated in the
original version of this report).