{"151091":{"#nid":"151091","#data":{"type":"event","title":"ARC Colloquium: Shachar Lovett, Institute of Advanced Study, Princeton, NJ","body":[{"value":"\u003Cp\u003E\u003Cbr \/\u003E\u003Cstrong\u003ETitle: Constructive Discrepancy Minimization by Walking on The Edges\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EMinimizing 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\u0026nbsp;$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\u0026nbsp;in nature, and did not give an efficient algorithm to find such a coloring.\u003C\/p\u003E\u003Cp\u003ERecently, a breakthrough work of Bansal (FOCS 2010) gave an efficient algorithm which finds such a coloring. His algorithm was based on an\u0026nbsp;SDP relaxation of the discrepancy problem and a clever rounding procedure. In this work we give a new randomized algorithm to find a \u003Cbr \/\u003Ecoloring as in Spencer\u0027s result based on a restricted random walk we call Edge-Walk. Our algorithm and its analysis use only basic linear algebra and is \u0022truly\u0022 constructive in that it does not appeal to the existential arguments,giving a new proof of Spencer\u0027s theorem and the partial coloring lemma.\u003C\/p\u003E\u003Cp\u003EJoint work with Raghu Meka\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2012-09-04 08:36:09","changed_gmt":"2016-10-08 01:59:45","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-09-10T14:00:00-04:00","event_time_end":"2012-09-10T14:00:00-04:00","event_time_end_last":"2012-09-10T14:00:00-04:00","gmt_time_start":"2012-09-10 18:00:00","gmt_time_end":"2012-09-10 18:00:00","gmt_time_end_last":"2012-09-10 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}