{"542021":{"#nid":"542021","#data":{"type":"event","title":"ARC Talk: David Woodruff - IBM","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EDavid Woodruff - IBM\u003Cbr \/\u003E\u003C\/strong\u003E\u003Cstrong\u003ETuesday, June 7, 2016\u003Cbr \/\u003E\u003C\/strong\u003E\u003Cstrong\u003EKlaus Conference Room 2100 - 2:00 pm\u003C\/strong\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003Cbr \/\u003E\u003C\/strong\u003EAn Optimal Algorithm for Finding L2 Heavy Hitters\u003Cbr \/\u003E\u003Cbr \/\u003E\u003Cstrong\u003EAbstract:\u003Cbr \/\u003E\u003C\/strong\u003EWe consider the problem of finding the most frequent items in a stream of items from a universe of size n. Namely, we consider returning all l_2-heavy hitters, i.e., those items j for which f_j \u0026gt;= eps sqrt{F_2}, where f_j is the number of occurrences of item j, and F_2 = sum_i f_i^2 is the second moment of the stream. In 2002, Charikar, Chen, and Farach-Colton suggested the CountSketch data structure, which solves this using log^2 n bits of space (for constant eps). The only known lower bound is log n bits. Using Gaussian processes, we show it is possible to achieve an optimal log n bits of space. Our technique resolves a number of other questions in data streams.\u003C\/p\u003E\u003Cp\u003EBased on work with Vladimir Braverman, Stephen Chestnut, and Nikita Ivkin (STOC \u002716) and work with Vladimir Braverman, Stephen Chestnut, Nikita Ivkin, Jelani Nelson, and Zhengyu Wang.\u003Cbr \/\u003E\u003Cbr \/\u003EHost: Santosh Vempala\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 2100 at 2 pm"}],"uid":"27466","created_gmt":"2016-06-06 09:20:02","changed_gmt":"2017-04-13 21:15:40","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-06-07T15:00:00-04:00","event_time_end":"2016-06-07T16:00:00-04:00","event_time_end_last":"2016-06-07T16:00:00-04:00","gmt_time_start":"2016-06-07 19:00:00","gmt_time_end":"2016-06-07 20:00:00","gmt_time_end_last":"2016-06-07 20:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"}],"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":"78771","name":"Public"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}