Finding Needles in Exponential Haystacks

Опубликовано 17 августа 2016, 21:18

Let S_1,...,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\sqrt{n}, K an absolute constant. The colors \chi(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\sqrt{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 \chi(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.'