Bounded independence for the inverse star discrepancy

We give a random-bit-efficient construction for the inverse star discrepancy. For every fixed $u\in (0,1)$, $k$-wise independent uniform points ${\mathit{X}}_1,\dots ,{\mathit{X}}_N$ with $k=O(d(1+\log (1+N\mathrm{/}d)))$ satisfy the Monte Carlo bound $D_N^{\ast }({\mathit{X}}_1,\dots ,{\mathit{X}}_N)=O(\sqrt{d\mathrm{/}N})$ with probability at least $u$. Consequently, $N=O(d{\epsilon }^{-2})$ and $k=O(d(1+\log {\epsilon }^{-1}))$ suffice to attain discrepancy at most $\epsilon$. The proof isolates the finitely many moments required by a chaining argument and gives explicit constants. A random vector-valued polynomial over a finite field realizes the required bounded independence on a grid using $O(d^2(1+\log (1+N\mathrm{/}d))\log N)$ random bits, rather than the $\mathrm{\Theta }(dN\log (dN))$ bits used by independent grid sampling.