\(
\def\<#1>{\left<#1\right>}
\newcommand{\R}{\mathcal{R}}
\renewcommand{\deg}[2]{\mathrm{deg}_{#2}(#1)}
\newcommand{\kw}[1]{\mathfrak{c}(#1)}
\)

## 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