FIX to Bit-Parallel Witnesses and their Applications to Approximate String Matching

Level: Small

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).