It is shown that there exists $f : \{0,1\}^{n/2} \times \{0,1\}^{n/2} \to \{0,1\}$ in E$^\mathbf{NP}$ such that for every $2^{n/2} \times 2^{n/2}$ matrix $M$ of rank $\le \rho$ we have $\P_{x,y}[f(x,y)\ne M_{x,y}] \ge 1/2-2^{-\Omega(k)}$, whenever $\log \rho \leq \delta n/k(\log n + k)$ for a sufficiently small $\delta > 0$.
This generalizes recent results which bound below the probability by $1/2-\Omega(1)$ or apply to constant-depth circuits.

Added "infinitely often" and comparison with concurrent work, several other minor changes.

It is shown that there exists $f : \{0,1\}^{n/2} \times \{0,1\}^{n/2} \to \{0,1\}$ in E$^\mathbf{NP}$ such that for every $2^{n/2} \times 2^{n/2}$ matrix $M$ of rank $\le \rho$ we have $\P_{x,y}[f(x,y)\ne M_{x,y}] \ge 1/2-2^{-\Omega(k)}$, where $k \leq \Theta(\sqrt{n})$ and $\log \rho \leq \delta n/k(\log n + k)$ for a sufficiently small $\delta > 0$.
This generalizes recent results which bound below the probability by $1/2-\Omega(1)$ or apply to constant-depth circuits.
The result is a step towards obtaining data-structure lower bounds for E$^\mathbf{NP}$: they would follow from a better trade-off between the probability bound and $\rho$.