A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension

2013/07/30 by Esther Ezra, Ezra, Esther
Computer Science · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CG #cs.DS

paper · pdf · doi:10.48550/arxiv.1307.8139

arxiv created 2013/07/30 · arxiv updated 2013/08/01

Abstract

Let (X,§) be a set system on an n-point set X. The discrepancy of § is defined as the minimum of the largest deviation from an even split, over all subsets of S ∈ § and two-colorings χ on X. We consider the scenario where, for any subset X' ⊆ X of size m ≤ n and for any parameter 1 ≤ k ≤ m, the number of restrictions of the sets of § to X' of size at most k is only O(m^d₁ k^d-d₁), for fixed integers d > 0 and 1 ≤ d₁ ≤ d (this generalizes the standard notion of bounded primal shatter dimension when d₁ = d). In this case we show that there exists a coloring χ with discrepancy bound O^*(|S|^{1/2 - d₁/(2d)} n^{(d₁ - 1)/(2d)}), for each S ∈ §, where O^*(⋅) hides a polylogarithmic factor in n. This bound is tight up to a polylogarithmic factor \citeMat-95, Mat-99 and the corresponding coloring χ can be computed in expected polynomial time using the very recent machinery of Lovett and Meka for constructive discrepancy minimization \citeLM-12. Our bound improves and generalizes the bounds obtained from the machinery of Har-Peled and Sharir \citeHS-11 (and the follow-up work in \citeSZ-12) for points and halfspaces in d-space for d ≥ 3.

Related

• Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems
• Tighter Bounds for the Discrepancy of Boxes and Polytopes
• Algorithms for Discrepancy, Matchings, and Approximations: Fast, Simple, and Practical
• Set Systems and Families of Permutations with Small Traces
• An Algorithm for Komlós Conjecture Matching Banaszczyk's bound