{"72828":{"#nid":"72828","#data":{"type":"event","title":"ARC Colloquium: Atri Rudra, University at Buffalo","body":[{"value":"\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003EGroup testing was formalized by Dorfman in his 1943 paper and was originally used in WW-II to identify soldiers with syphilis. The main insight in this application is that blood samples from different soldiers can be combined to check if at least one of soldiers in the pool has the disease. Since then group testing has found numerous applications in many areas such as (computational) biology, combinatorics and (theoretical) computer science.\u003C\/p\u003E\u003Cp\u003ETheory of error-correcting codes, or coding theory, was born in the works of Shannon in 1948 and Hamming in 1950. Codes are ubiquitous in our daily life and have also found numerous applications in theoretical computer science in general and computational complexity in particular.\u003C\/p\u003E\u003Cp\u003EKautz and Singleton connected these two areas in their 1964 paper by using \u0022code concatenation\u0022 to design good group testing schemes. All of the (asymptotically) best know explicit constructions of group testing schemes use the code concatenation paradigm. In this talk, we will focus on the \u0022decoding\u0022 problem for group testing: i.e. given the outcomes of the tests on the pools, identify the infected soldiers. Recent applications of group testing in data stream algorithm require sub-linear time decoding, which is not guaranteed by the traditional constructions.\u003C\/p\u003E\u003Cp\u003EWe will show that recent developments in list decoding of codes lead in a modular way to sub-linear time decodable group testing schemes. \u003C\/p\u003E\u003Cp\u003EAll the connections above use tools from coding theory to construct group testing schemes. We will also very briefly talk about our recent work that uses results from group testing to obtain results in coding theory. \u003C\/p\u003E\u003Cp\u003EThe talk will be self contained and is based on joint works with Piotr Indyk, Hung Ngo, Ely Porat and Steve Uurtamo. \u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Group Testing and Coding Theory"}],"uid":"27263","created_gmt":"2011-11-16 12:56:07","changed_gmt":"2016-10-08 01:56:41","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2010-11-22T12:30:00-05:00","event_time_end":"2010-11-22T12:30:00-05:00","event_time_end_last":"2010-11-22T12:30:00-05:00","gmt_time_start":"2010-11-22 17:30:00","gmt_time_end":"2010-11-22 17:30:00","gmt_time_end_last":"2010-11-22 17: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":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EElizabeth Ndongi\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}