Woźniakowski's conjecture on the exponent of tractability of star discrepancy

Let

α:=sup{αc,k0 N,dN P[0,1]d: P=N  DN(P)cdkNα}.\overline{\alpha}:=\sup\left\{\alpha\mid \exists c,k\geq 0\ \forall N,d\in\mathbb{N}\ \exists P\subset[0,1]^d:\ |P|=N\ \wedge\ D_N^*(P)\leq c\frac{d^k}{N^\alpha}\right\}.

Here DN(P)D_N^*(P) denotes the star discrepancy of an NN-point set PP.

Woźniakowski's conjecture.

α=12.\overline{\alpha}=\frac{1}{2}.

This conjecture concerns the optimal dependence on the number of points in high-dimensional star discrepancy bounds. The paper states that the known bounds give 1/2α<0.93731/2\leq\overline{\alpha}<0.9373, and that the problem remains unsolved.

Sources & referencesView supporting material

Primary source

Michael Gnewuch and Nils Hebbinghaus, “Discrepancy Bounds for a Class of Negatively Dependent Random Points Including Latin Hypercube Samples”, arXiv:2102.04451 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.