2025-05-13
Abstract
In this article, we present a new discrepancy game between two players Alice and Bob. In this game they will play on a given set system and Alice will choose colorings of the ground set and Bob chooses ranges from the set system. Alice wants to minimize the discrepancy of the ranges given by Bob. We show that there exists a non-trivial strategy for Alice when the set system has finite VC-dimension. The strategy relies on the low-discrepancy algorithm of Lovett and Meka.
Preprint (HAL)