Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-190 | 2nd November 2015 18:13

On the Beck-Fiala Conjecture for Random Set Systems

RSS-Feed




TR15-190
Authors: Esther Ezra, Shachar Lovett
Publication: 27th November 2015 15:38
Downloads: 830
Keywords: 


Abstract:

Motivated by the Beck-Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems $(X,\Sigma)$, where each element $x \in X$ lies in $t$ randomly selected sets of $\Sigma$, where $t$ is an integer parameter. We provide new bounds in two regimes of parameters. We show that when $|\Sigma| \ge |X|$ the hereditary discrepancy of $(X,\Sigma)$ is with high probability $O(\sqrt{t \log t})$; and when $|X| \gg |\Sigma|^t$ the hereditary discrepancy of $(X,\Sigma)$ is with high probability $O(1)$. The first bound combines the Lov{\'a}sz Local Lemma with a new argument based on partial matchings; the second follows from an analysis of the lattice spanned by sparse vectors.



ISSN 1433-8092 | Imprint