An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound
An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound
We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most $t$ sets. We give an efficient algorithm that finds a coloring with discrepancy $O((t \log n)^{1/2})$, matching the best known nonconstructive bound for the problem due to Banaszczyk. The …