ARC Colloquium: Shachar Lovett, Institute of Advanced Study, Princeton, NJ

Event Details
  • Date/Time:
    • Monday September 10, 2012 - Tuesday September 11, 2012
      1:00 pm - 12:59 pm
  • Location: MiRC 102A
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:


Summary Sentence: No summary sentence submitted.

Full Summary: No summary paragraph submitted.

Title: Constructive Discrepancy Minimization by Walking on The Edges


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

Additional Information

In Campus Calendar

School of Computer Science, ARC

Invited Audience
No audiences were selected.
No keywords were submitted.
  • Created By: Elizabeth Ndongi
  • Workflow Status: Published
  • Created On: Sep 4, 2012 - 4:36am
  • Last Updated: Oct 7, 2016 - 9:59pm