{"278451":{"#nid":"278451","#data":{"type":"event","title":"ARC Colloquium: Grigory Yaroslavtsev, Brown University","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E The Big Data Theory and Randomized Algorithms\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EAdvances in machine learning and developments in modern massive parallel computational systems motivate a large number of challenging questions for the theory of computing. How to make sense of massive amounts of noisy data? How to cluster billions of points and compare large images? How to design scalable algorithms for distributed systems?\u003C\/p\u003E\u003Cp\u003EI will present examples of settings in which these questions can be addressed through the design of randomized algorithms:\u003C\/p\u003E\u003Cul\u003E\u003Cli\u003ESublinear algorithms for testing properties of high-dimensional noisy data such (e.g. monotonicity, the Lipschitz property and convexity)\u003C\/li\u003E\u003Cli\u003EDistributed algorithms for geometric problems in Euclidean space (minimum cost spanning tree, Earth-Mover Distance)\u003C\/li\u003E\u003C\/ul\u003E\u003Cp\u003EThrough these examples I will illustrate how information-theoretic measures of performance such as query complexity and the number of rounds of communication play a key role in the design and analysis of such algorithms. I will show that even in the worst-case these fundamental problems can be solved almost optimally with respect to these measures. The information-theoretic nature is crucial here since lower bounds can be proved unconditionally, i.e. with no computational hardness assumptions.\u003C\/p\u003E\u003Cp\u003EThis talk will be primarily based on two papers which will appear in STOC\u201914 (joint work with Andoni, Berman, Nikolov, Onak and Raskhodnikova) as well as other work by the speaker.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"The Big Data Theory and Randomized Algorithms"}],"uid":"27263","created_gmt":"2014-02-24 13:46:06","changed_gmt":"2017-04-13 21:23:06","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-03-05T18:00:00-05:00","event_time_end":"2014-03-05T18:00:00-05:00","event_time_end_last":"2014-03-05T18:00:00-05:00","gmt_time_start":"2014-03-05 23:00:00","gmt_time_end":"2014-03-05 23:00:00","gmt_time_end_last":"2014-03-05 23:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"174045","name":"Graduate students"}],"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":""}}}