比利时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
****************************