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

About 5 years old · traced to

Let

α‾:=sup⁡{α∣∃c,k≥0 ∀N,d∈N ∃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.

References

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.