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

Event Details
  • Date/Time:
    • Monday September 10, 2012
      1:00 pm
  • Location: MiRC 102A
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact

ndongi@cc.gatech.edu

Summaries

Summary Sentence: No summary sentence submitted.

Full Summary: No summary paragraph submitted.


Title: 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

Additional Information

In Campus Calendar
No
Groups

School of Computer Science, ARC

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