A Fourier-Analytic Approach for the Discrepancy of Random Set Systems

DOI10.1137/1.9781611975482.156zbMath1434.05151arXiv1806.04484OpenAlexW2808598845MaRDI QIDQ5236346

Rebecca Hoberg, Thomas Rothvoß

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1806.04484

zbMATH Keywords

discrepancy boundsBeck-Fiala conjecturediscrepancy of set systems

Mathematics Subject Classification ID

Extremal set theory (05D05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (5)

The Phase Transition of Discrepancy in Random Hypergraphs ⋮ MAX CUT in weighted random intersection graphs and discrepancy of sparse random set systems ⋮ The discrepancy of random rectangular matrices ⋮ Discrepancy theory and related algorithms ⋮ On the discrepancy of random matrices with many columns

This page was built for publication: A Fourier-Analytic Approach for the Discrepancy of Random Set Systems