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