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 $\boldsymbol{X}_1,\ldots,\boldsymbol{X}_N$ with $k=O(d(1+\log(1+N/d)))$ satisfy the Monte Carlo bound $D_N^*(\boldsymbol{X}_1,\ldots,\boldsymbol{X}_N) =O(\sqrt{d/N})$ with probability at least $u$. Consequently, $N=O(d\varepsilon^{-2})$ and $k=O(d(1+\log\varepsilon^{-1}))$ suffice to attain discrepancy at most $\varepsilon$. 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.