FIX to Bit-Parallel Witnesses and their Applications to Approximate String
There is an error in line -5 of page 11 (in the version of the paper linked
from this site). We say that, since a >= 1/s, it holds that
l >= 3 log_s m is a sufficient condition (where s
is called "sigma" in the paper). Unfortunately the inequality should be
a <= 1/s for this to hold.
Fortunately, the result is still valid. Since a
= 1/(s^(1-A) A^(2A) (1-A)^(2(1-A))),
being A called "alpha" in the paper, and the method works for
A < 1/2, and the formula is maximized for A = 1/2, it holds
1/s <= a <= 4/sqrt(s), and hence
log(1/a) = Theta(log s).