On the discrepancy of random low degree set systems

Nikhil Bansal, Raghu Meka

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)

Samenvatting

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((tlog t)1/2) discrepancy bound in the regime when n ≤ m and an O(1) bound when n mt. 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)2. The result is based on two steps. First, applying the partial coloring method to the case when n = mlogO(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 ≤ mlogO(1)m using LP duality and a careful counting argument.

Originele taal-2Engels
TitelProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
RedacteurenTimothy M. Chan
Plaats van productieNew York
UitgeverijAssociation for Computing Machinery, Inc
Pagina's2557-2564
Aantal pagina's8
ISBN van elektronische versie978-1-61197-548-2
DOI's
StatusGepubliceerd - 2019
Evenement30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, Verenigde Staten van Amerika
Duur: 6 jan 20199 jan 2019

Congres

Congres30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
LandVerenigde Staten van Amerika
StadSan Diego
Periode6/01/199/01/19

Vingerafdruk Duik in de onderzoeksthema's van 'On the discrepancy of random low degree set systems'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Bansal, N., & Meka, R. (2019). On the discrepancy of random low degree set systems. In T. M. Chan (editor), Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (blz. 2557-2564). Association for Computing Machinery, Inc. https://doi.org/10.1137/1.9781611975482.157