{"72597":{"#nid":"72597","#data":{"type":"event","title":"Joint ARC and School of Math Colloquium by Avi Wigderson, Institute for Advanced Study, Princeton","body":[{"value":"\u003Cp\u003ETitle: The power and weakness of randomness (when you are short on time)\u003C\/p\u003E\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003EMan has grappled with the meaning and utility of randomness for centuries. Research in the Theory of Computation in the last thirty years has enriched this study considerably. I\u0027ll describe two main aspects of this research on randomness, demonstrating respectively its power and weakness for making algorithms faster. I will address the role of randomness in other computational settings, such as space bounded computation and probabilistic and zero-knowledge proofs.\u003C\/p\u003E\u003Cp\u003EThis is a joint ARC-SoM colloquium, and is in conjunction with the ARC Theory Day on November 11, 2011\u003C\/p\u003E\u003Cp\u003E4:30 pm - Klaus 1116 E \u0026amp; W\u003C\/p\u003E\u003Cp\u003ETitle: Local correction of codes and Euclidean Incidence Geometry\u003C\/p\u003E\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003EA classical theorem in Euclidean geometry asserts that if a set of points has the property that every line through two of them contains a third point, then they must all be on the same line. We prove several approximate versions of this theorem, which are motivated from questions about locally correctable codes and matrix rigidity. The proofs use an interesting combination of algebraic and analytic tools.\u003C\/p\u003E\u003Cp\u003EJoint work with Boaz Barak, Zeev Dvir and Amir Yehudayoff\u003C\/p\u003E\u003Cp\u003EAvi Wigderson Lecture \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/42025\u0022\u003EVideo\u003C\/a\u003E.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"The power and weakness of randomness (when you are short on time)"}],"uid":"27263","created_gmt":"2011-11-10 09:05:27","changed_gmt":"2016-10-08 01:56:37","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-11-10T10:00:00-05:00","event_time_end":"2011-11-10T10:00:00-05:00","event_time_end_last":"2011-11-10T10:00:00-05:00","gmt_time_start":"2011-11-10 15:00:00","gmt_time_end":"2011-11-10 15:00:00","gmt_time_end_last":"2011-11-10 15:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EPrasad Tetali, Director of ARC\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}