BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Mondays seminars - Constructive Algorithms for Discrepancy Mini
 mization 
DTSTART:20100315T161500
DTSTAMP:20260406T161425Z
UID:a8404633e2b76bf94ed173c2c69bf8440176f6907a9282b581064c4d
CATEGORIES:Conferences - Seminars
DESCRIPTION:Dr. Nikhil Bansal\, IBM Hawthorne\nAbstract \n\nThe problem of
  finding the minimum discrepancy coloring is the following: Given a collec
 tion of sets S1\,...\,Sm\, color the elements red and blue such that each 
 set is colored as evenly as possible. While several techniques have been d
 eveloped to show the existence of good colorings\, obtaining such coloring
 s algorithmically has been a long standing question.\n\nIn this talk\, we 
 will describe the first algorithmic results for the problem that essential
 ly match the known existential guarantees. Among other results\, we show h
 ow to efficiently construct an O(n^{1/2}) discrepancy coloring when m = O(
 n). This matches the celebrated "six standard deviations suffice" result o
 f Spencer up to constant factors.\n\nBiography \n\nNikhil Bansal is at the
  IBM T.J. Watson Research Center\, where he currently manages the Algorith
 ms group. His main research interests are in the area of design and analys
 is of algorithms\, with particular focus on approximation and online algor
 ithms for various combinatorial optimization problems. He has over 90 publ
 ications in this field and has received the IBM Research best paper award 
 in 2008. He obtained his PhD in 2003 from Carnegie Mellon University\, and
  his Bachelor's degree in 1999 from Indian Institute of Technology\, Mumba
 i. 
LOCATION:INM 202
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR