Let be a set system with and . A ±1-coloring is a mapping . The discrepancy of a set system is defined as
– Spencer ’85, Six standard deviations suffice, .
If every element appears in at most sets,
– Beck-Fiala ’81, “Integer-making” theorems, .
– Srinivasan ’97, Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems, .
– Banaszczyk ’98, Balancing vectors and Gaussian measures of n-dimensional convex bodies, .
– Bansal ’10, Constructive algorithms for discrepancy minimization.