Finite Playground

To verify is human; to prove, divine.

Tag Archives: discrepancy


by Leave a comment

Discrepancy theory

Let (V,\mathcal{S}) be a set system with V = [n] and \mathcal{S} \subseteq 2^{[n]}. A ±1-coloring is a mapping \chi : [n] \to \{1,-1\}. The discrepancy of a set system (V,\mathcal{S}) is defined as

\displaystyle{\text{disc}(S) = \min_{\chi} \{\max_{S \in \mathcal{S}} |\chi(S)|} \},

where \chi(S) = \sum_{i \in S} \chi(i).

General bounds:
– Spencer ’85, Six standard deviations suffice, O(\sqrt{n \log (2|\mathcal{S}|/n)}).

If every element appears in at most t sets,
– Beck-Fiala ’81, “Integer-making” theorems, O(t).
– Srinivasan ’97, Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems, O(\sqrt{t} \log n).
– Banaszczyk ’98, Balancing vectors and Gaussian measures of n-dimensional convex bodies, O(\sqrt{t \log n}).

Constructive bounds:
– Bansal ’10, Constructive algorithms for discrepancy minimization.