2023-10-10
Talk in the Erdős Center Seminar about \(\delta\)-packings for finite VC-dimension set systems and applications
A \(\delta\)-packing of a set system \((X,F)\) is a sub-collection \(P\) of \(F\) such that both elements of any pair of \(P^2\) are at symmetric difference at least \(\delta\). We present an efficient algorithm to compute near-maximal \(\delta\)-packings of set systems with finite VC-dimension.
Set discrepancy is a basic problem for data approximation and optimization. The goal is to find a 2-coloring of \(X\) with minimum discrepancy between the two colors over each set in \(F\). We use our packing algorithm to improve the runtime of algorithms solving set discrepancy in the case of finite VC-dimension set systems.
Slides