22 septembre 2025
Carola Doerr (CNRS, LIP6)The $L_{\infty}$ star discrepancy is a very well-studied measure used to quantify the uniformity of a point set distribution. Constructing optimal point sets for this measure is seen as a very hard problem in the discrepancy community. Indeed, provably optimal point sets were known, up to now, only for up to 6 points in dimension 2 and up to two points in higher dimensions.
In this talk, we will present different approaches to construct low discrepancy point sets. We first introduce mathematical programming formulations to construct point sets with optimal $L_{\infty}$ star discrepancy values in dimension 2 for up to 21 points and up to 8 points in dimension 3. We show that these optimal sets have a far lower discrepancy than the previous references. More importantly, they present a very different structure. [PAMS: doi.org/10.1090/bproc/254]
We will then discuss extensions of this approach to obtain good, but not provably optimal, point sets and show that there is much room for improvement over state-of-the-art constructions. We also show that additional symmetry requirements can be satisfied at very small loss in discrepancy value.
Finally, we will discuss some recent advances using graph neural networks by Rusch et al. [PNAS: https://www.pnas.org/doi/10.1073/pnas.2409913121] and how we outperform these constructions using classic optimization approaches [PNAS: https://www.pnas.org/doi/abs/10.1073/pnas.2424464122].
The presentation is based on joint work with François Clément (University of Washington, US), Kathrin Klamroth (University of Wuppertal, Germany), and Luís Paquete (University of Coimbra, Portugal).