{"283031":{"#nid":"283031","#data":{"type":"event","title":"ARC Colloquium: Atri Rudra - University at Buffalo, SUNY","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E A Tale of Two Join Algorithms\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EIn this talk we will talk about two new database join algorithms with provable optimality guarantees.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;We first present a recent algorithm (PODS 2012) that is the first provably optimal (worst-case) algorithm to compute database joins. As a special case, this join algorithm implies (i) The first algorithmic versions of some well-known geometric inequalities due to Loomis and Whitney (and their generalizations by Bollobas and Thomason); (ii) Algorithmically list recoverable codes that work with parameters that no known algorithmic list recovery result work with (e.g. those based on the Reed-Solomon codes) and an application of this result in designing sublinear time decodable compressed sensing schemes; (ii) Worst-case optimal algorithm to list all occurrences of any fixed hypergraph H in a given large hypergraph G.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;The second algorithm (PODS 2014) has stronger optimality guarantees: we present an adaptive join algorithm whose run time depends on the \u0022difficulty\u0022 of the data. We believe that this algorithm has more practical applications since worst-case optimal algorithms might have terrible performance on \u0022real data.\u0022 As a special case, we present an (almost) instance optimal algorithm (with respect to comparison based algorithms) for a large class of join queries (namely Fagin\u0027s \\beta-acyclic queries).\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;The talk will be self-contained and is based on join(t) works with Ngo, Nguyen, Porat and Re.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"A Tale of Two Join Algorithms"}],"uid":"27263","created_gmt":"2014-03-13 11:08:18","changed_gmt":"2017-04-13 21:22:56","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-03-24T18:30:00-04:00","event_time_end":"2014-03-24T18:30:00-04:00","event_time_end_last":"2014-03-24T18:30:00-04:00","gmt_time_start":"2014-03-24 22:30:00","gmt_time_end":"2014-03-24 22:30:00","gmt_time_end_last":"2014-03-24 22:30: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":""}}}