Here the authors wrongly assume that pβ 2 + ǫ−β ≥
√ǫ holds, whereas the truth is pβ 2 + ǫ − β ≤
√ǫ always.

Observe that this glitch is easy to fix locally, however this change is minor and the modified claim would still be false. Since for all 0 ≤ y ≤ 1 we have that √1 + y ≥ 1 + y/3, from β ≥ 1 it follows that pβ 2 + ǫ − β ≥ ǫ/3. Plugging the latter estimate into the "proof" of Theorem 3 would result in a modified claim where the original probability of error, exp(−
√ǫ 4η
), is replaced with **exp(**− ǫ 12η
). Updating the numeric constants in the first section of this note would show that the new claim still contradicts Alon's lower bound. To justify observe that counter example is based on a constant ǫ and the modified claim would still lack the necessary **Ω(log** n) dependency in its target dimensionality.