  Given a set system (V,S), V={1,...,n} and S={S1,...,Sm}, the minimum
discrepancy problem is to find a 2-coloring of V, such that each set is colored
as evenly as possible. In this paper we give the first polynomial time
algorithms for discrepancy minimization that achieve bounds similar to those
known existentially using the so-called Entropy Method. We also give a first
approximation-like result for discrepancy. The main idea in our algorithms is
to produce a coloring over time by letting the color of the elements perform a
random walk (with tiny increments) starting from 0 until they reach $-1$ or
$+1$. At each time step the random hops for various elements are correlated
using the solution to a semidefinite program, where this program is determined
by the current state and the entropy method.
