Show icon Show search tips...
Hide icon Hide search tips...

[CCICADA-announce] DIMACS/CCICADA Interdisciplinary Seminar Series - April 8, 2013

Linda Casals lindac at dimacs.rutgers.edu
Thu Apr 4 08:56:55 EDT 2013


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

DIMACS/CCICADA Interdisciplinary Seminar Series Presents
               
*********************************************************************
Title: Constructive Discrepancy Minimization by Walking on the Edges

Speaker: Raghu Meka, DIMACS, Rutgers University and IAS

Date: Monday, April 8, 2013 11:00am - 12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University                 
             Busch Campus, Piscataway, NJ

*********************************************************************
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 6sqrt{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. 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 Shachar Lovett. 

DIMACS/CCICADA Interdisciplinary Series Calendar 2013-
See: http://dimacs.rutgers.edu/Seminars/interseminars12-13.html




More information about the Dimacs-ccicada-announce mailing list