Irregularities of Distributions and Extremal Sets in Combinatorial Complexity Theory

Christoph Aistleitner () and Aicke Hinrichs ()
Additional contact information
Christoph Aistleitner: Institute of Analysis and Number Theory, TU Graz
Aicke Hinrichs: University Linz, Institute of Analysis

A chapter in Contemporary Computational Mathematics - A Celebration of the 80th Birthday of Ian Sloan, 2018, pp 59-74 from Springer

Abstract: Abstract In 2004 the second author of the present paper proved that a point set in [0, 1]d which has star-discrepancy at most ε must necessarily consist of at least cabs dε −1 points. Equivalently, every set of n points in [0, 1]d must have star-discrepancy at least cabs dn −1. The original proof of this result uses methods from Vapnik–Chervonenkis theory and from metric entropy theory. In the present paper we give an elementary combinatorial proof for the same result, which is based on identifying a sub-box of [0, 1]d which has approximately d elements of the point set on its boundary. Furthermore, we show that a point set for which no such box exists is rather irregular, and must necessarily have a large star-discrepancy.

Keywords: Vapnik-Chervonenkis Theory; Elementary Combinatorial Proof; Entropy Theory; Cheap Proof; Sauer-Shelah Lemma (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-319-72456-0_3

Ordering information: This item can be ordered from
http://www.springer.com/9783319724560

DOI: 10.1007/978-3-319-72456-0_3

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().