Discrepancy Without Partial Colorings

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 such that the sum of every set is O( √ n) in absolute value. All existing proofs of this result recursively construct “partial colorings”, which assign ±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.