On the discrepancy of random low degree set systems

2018/10/08 by Bansal, Nikhil, Meka, Raghu · 3 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1810.03374

Abstract

Motivated by the celebrated Beck-Fiala conjecture, we consider the random setting where there are n elements and m sets and each element lies in t randomly chosen sets. In this setting, Ezra and Lovett showed an O((t log t)^1/2) discrepancy bound in the regime when n ≤ m and an O(1) bound when n ≫ m^t. In this paper, we give a tight O(√(t)) bound for the entire range of n and m, under a mild assumption that t = Ω(log log m)². The result is based on two steps. First, applying the partial coloring method to the case when n = m log^O(1) m and using the properties of the random set system we show that the overall discrepancy incurred is at most O(√(t)). Second, we reduce the general case to that of n ≤ m log^O(1)m using LP duality and a careful counting argument.

Cited by

• A threshold for online balancing of sparse i.i.d. vectors
• Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
• An Improved Bound for the Beck-Fiala Conjecture

Related

• A Fourier-Analytic Approach for the Discrepancy of Random Set Systems
• On the Beck-Fiala Conjecture for Random Set Systems
• An Improved Bound for the Beck-Fiala Conjecture
• Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems
• An improvement of the Beck-Fiala theorem