printable pdf
比利时vs摩洛哥足彩 ,
university of california san diego

****************************

math 269 - combinatorics

shachar lovett

cse, ucsd

constructive discrepancy minimization by walking on the edges

abstract:

minimizing the discrepancy of a set system is a fundamental problem in combinatorics. one of the cornerstones in this area is the celebrated six standard deviations result of spencer (ams 1985): in any system of $n$ sets in a universe of size $n$, there always exists a coloring which achieves discrepancy $6\sqrt{n}$. the original proof of spencer was existential in nature, and did not give an efficient algorithm to find such a coloring. recently, a breakthrough work of bansal (focs 2010) gave an efficient algorithm which finds such a coloring. his algorithm was based on an sdp relaxation of the discrepancy problem and a clever rounding procedure. in this work we give a new randomized algorithm to find a coloring as in spencer's result based on a restricted random walk we call edge-walk. our algorithm and its analysis use only basic linear algebra and is ``truly'' constructive in that it does not appeal to the existential arguments, giving a new proof of spencer's theorem and the partial coloring lemma. joint work with raghu meka

host: fan chung graham

january 22, 2013

3:00 pm

ap&m 7321

****************************