Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy

DOI10.48550/arXiv.2607.23571MaRDI QIDQ7284461zbMATH OpenarXivFDO

Authors Josef Dick

Publication date 26 July 2026

Published in arXiv

Tldr We prove that every polynomial estimate for the inverse star discrepancy must have exponent 2 on \ε, showing that the exponents in the known upper bound are individually optimal.

Full work available at URL https://doi.org/10.48550/arXiv.2607.23571

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25) Irregularities of distribution, discrepancy (11K38)

arXiv classification

math.NA

Cites work

• A generalized Faulhaber inequality, improved bracketing covers, and applications to discrepancy
• A lower bound for the discrepancy of a random point set
• An elementary proof of a lower bound for the inverse of the star discrepancy
• Covering numbers, dyadic chaining and discrepancy
• Discrepancy bounds for a class of negatively dependent random points including Latin hypercube samples
• Improving a constant in high-dimensional discrepancy estimates
• Irregularities of distributions and extremal sets in combinatorial complexity theory
• The inverse of the star-discrepancy depends linearly on the dimension

Cited in

(1)

• Bounded independence for the inverse star discrepancy

This page was built for publication: Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7284461)