# 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):
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

In Campus Calendar
No
Groups
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