{"69737":{"#nid":"69737","#data":{"type":"event","title":"CSE Seminar: Amihood Amir","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ECSE Seminar: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E\u0026nbsp;\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EBy: \u003C\/strong\u003E\u003Cstrong\u003EAmihood Amir\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EBar Ilan University and Johns Hopkins University\u003C\/p\u003E\u003Cp\u003EDate: Friday, September 9, 2011\u003C\/p\u003E\u003Cp\u003ETime: 2:00pm - 3:30pm \u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ELocation: \u003C\/strong\u003EKlaus 2447 \u003Cstrong\u003E\u0026nbsp;\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EFor more information please contact\u0026nbsp;Dr. Alberto Apostolico at \u003Ca href=\u0022mailto:axa@cc.gatech.edu\u0022\u003Eaxa@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ECycle Detection and Correction \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EAssume that a natural cyclic phenomenon has been measured, but the data is corrupted by errors. The type of corruption is application-dependent and may be caused by measurement errors, or natural features of the phenomenon. We assume that an appropriate metric exists, which measures the amount of corruption experienced. We study the problem of recovering the corrupted cycle under various error models, formally called the period recovery problem. Specifically, we identify a metric property which we call pseudo-locality and study the period recovery problem under pseudo-local metrics. Examples of pseudo-local metrics are the Hamming distance, the swap distance, and the interchange (or Cayley) distance. We show that for pseudo-local metrics, periodicity is a powerful property allowing detecting the original cycle and correcting the data, under suitable conditions. Some surprising features of our algorithm are that we can efficiently identify the corrupted period, up to number of possibilities logarithmic in the length of the data string, even for metrics whose calculation is NP-hard. \u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EJoint work with Estrella Eisenberg, Avivit Levy, Ely Porat, and Natalie Shapira \u003C\/p\u003E\u003Cp\u003E~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\u0026nbsp;\u003C\/p\u003E\u003Cp\u003ETo receive future announcements, please sign up to the cse-seminar email list:\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/cse-seminar\u0022\u003Ehttps:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/cse-seminar\u003C\/a\u003E\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":"Cycle Detection and Correction"}],"uid":"27439","created_gmt":"2011-08-31 13:10:52","changed_gmt":"2016-10-08 01:55:34","author":"Lometa Mitchell","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-09-09T15:00:00-04:00","event_time_end":"2011-09-09T16:30:00-04:00","event_time_end_last":"2011-09-09T16:30:00-04:00","gmt_time_start":"2011-09-09 19:00:00","gmt_time_end":"2011-09-09 20:30:00","gmt_time_end_last":"2011-09-09 20:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"37041","name":"Computational Science and Engineering"},{"id":"47223","name":"College of Computing"},{"id":"50877","name":"School of Computational Science and Engineering"}],"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\u003EFor more information please contact\u0026nbsp;Dr. Alberto Apostolico at \u003Ca href=\u0022mailto:axa@cc.gatech.edu\u0022\u003Eaxa@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}