Bounded independence for the inverse star discrepancy

Abstract

We give a random-bit-efficient construction for the inverse star discrepancy. For every fixed $u\in (0,1)$, $k$-wise independent uniform points ${\mathbf{X}}_1,\dots ,{\mathbf{X}}_N$ with $k=O(d(1+\log (1+N/d)))$ satisfy the Monte Carlo bound $D_N^{\ast }({\mathbf{X}}_1,\dots ,{\mathbf{X}}_N)=O(\sqrt{d/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/d))\log N)$ random bits, rather than the $\Theta (dN\log (dN))$ bits used by independent grid sampling.