2023-09-13
This work has not been published on its own and can be read in my PhD thesis.
Abstract
This work presents algorithms to compute \(\delta\)-coverings of set systems of VC-dimension \(d\). It is the first instance of a non-trivial algorithm to compute \(\delta\)-coverings of size matching the worst case lower bound \(O((\frac{n}{\delta})^d)\) given by Haussler. We give a generic algorithm with expected runtime \(O(\frac{mdn}{\delta}\log(\frac{n}{\delta}) + (\frac{n}{\delta})^{2d+2}\log^d(\frac{n}{\delta}))\) against \(O(\frac{mn^{d+1}}{\delta^d})\) for greedy covering where \(n\) is the number of elements and \(m\) the number of ranges of the set system. This improves on the work of Matousek, Welzl and Wernisch by removing the \(\log\) factor on the bound of the size of the \(\delta\)-covering obtained. We also present variants of our main algorithm for set systems with other geometric or combinatorial properties.
Our algorithms combined with Lovett and Meka's low-discrepancy algorithm give the first non-trivial algorithms to compute low-discrepancy colorings of finite VC-dimension set system using the same chaining method than Matousek.
Chapter 6 of my PhD manuscript