Discrepancy Without Partial Colorings
Nicholas J. A. Harvey, Roy Schwartz, Mohit Singh · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2014
Spencer's theorem asserts that, for any family of n subsets of ground set of size n, the elements of the ground set can be "colored" by the values +1 or -1 such that the sum of every set is O(sqrt(n)) in absolute value. All existing proofs of this result recursively construct "partial colorings", which assign +1 or -1 values to half of the ground set. We devise the first algorithm for Spencer's theorem that directly computes a coloring, without recursively computing partial colorings.