*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
CSE Seminar:
By: Amihood Amir
Bar Ilan University and Johns Hopkins University
Date: Friday, September 9, 2011
Time: 2:00pm - 3:30pm
Location: Klaus 2447
For more information please contact Dr. Alberto Apostolico at axa@cc.gatech.edu
Title:
Cycle Detection and Correction
Abstract:
Assume 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.
Joint work with Estrella Eisenberg, Avivit Levy, Ely Porat, and Natalie Shapira
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
To receive future announcements, please sign up to the cse-seminar email list:
https://mailman.cc.gatech.edu/mailman/listinfo/cse-seminar
