In page 5, footnote 4, it should say b_i = |S_i| H_0(S_i).
In page 6, line 11 of Section 4, the last term for ceil(n/b) is wrong. The total number of partitions, sigma^k.
In page 8, line -3 of Section 6, O(n) should be o(n).
In page 11, line 11, c C[i] should have been c C_i.