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 $\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 $Θ(dN\log(dN))$ bits used by independent grid sampling.

Disclosure

“, evaluation at the N distinct field elements determines each polynomial, so the coefficient space and the space of ordered grid outputs both have cardinality q k0 d . The bounds follow from N ≤ q < 2N , (3.7), and (3.8). Declaration of generative AI use The author used ChatGPT 5.6 Sol for literature searches, exploratory development of ideas, mathematical discussion, and assistance in preparing portions of the exposition and LaTeX source. All mathematical arguments, calculations, refe”

PDF page 9

Classification

Drafting limited passages

Multiplier

5

Verified

2026-08-23T05:18:13.600532Z

Structural counts