Theorem 4.25: correction

In the definition of the matrix $B$ one should take "or" instead of "and". That is, $B$ agrees with $A$ on all entries $(i,j)$ with $i\in I$ or $j\in J$, and has $0$'s elsewhere. The upper bound on Frobenius norm $\|B\|_F$ of $B$ [which I wrongly denoted by $W(B)$] is then larger: \[ x^TBy\leq \|B\|\leq \|B\|_F\leq \sqrt{pn+pn-p^2}\leq \sqrt{2pn}\,. \] So, \[ a^TAb=x^TAy-x^TBy\geq \frac{n}{\sqrt{r}}-\sqrt{2pn}\,. \] Set now $p:=n/(8r)$. Then \[ u^TAv=p\cdot a^TAb\geq p\cdot \frac{n}{\sqrt{r}}-p\cdot \sqrt{2pn}=\frac{n^2}{16r^{3/2}}\,, \] and the resulting lower bound on the discrepancy is $1/4$ this number: \[ \mathrm{disc}(A)\geq \frac{n^2}{64 r^{3/2}}\,. \]

S. Jukna, 13.05.2020