Finding Needles in Exponential Haystacks

Let S₁,…,S_n be subsets of 1,…n. A quarter century ago I showed that there is a two-coloring of the vertices so that all sets have discrepancy at most K√n, K an absolute constant. The colors χ(j) are +1,-1 and discrepancy is the absolute value of the sum of the colors. In matrix terms, given an n by n matrix A with all coefficients in [-1,+1] there is a vector x with values -1,+1 so that Ax has L-infinity norm at most K√n].) I had long conjectured that there would not be an algorithm to find such a coloring. Very recently Nikhil Bansal (IBM) has found an algorithm, which I shall describe. At its heart it uses Semidefinite Programming. The colors χ(j) “float” in [-1,+1], each performing a discretized Brownian motion until being caught by the boundary. Unlike the recent Moser-Tardos work on the Lovasz Local Lemma, this does not provide a new proof – the known arguments are used to prove feasibility of certain Semidefinite Programs. Along the way, this provides a fresh view of the original argument via a “cost equation.”