Finite Playground

To verify is human; to prove, divine.

Discrepancy theory

Leave a comment

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.

Author: hcsoso

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s