Shift finding in sub-linear time

Alexandr Andoni, Haitham Hassanieh, Piotr Indyk, Dina Katabi

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We study the following basic pattern matching problem. Consider a "code" sequence c consisting of n bits chosen uniformly at random, and a "signal" sequence x obtained by shifting c (modulo n) and adding noise. The goal is to efficiently recover the shift with high probability. The problem models tasks of interest in several applications, including GPS synchronization and motion estimation. We present an algorithm that solves the problem in time Õ(n(f/(1+f)), where Õ(Nf) is the running time of the best algorithm for finding the closest pair among N "random" sequences of length O(log N). A trivial bound of f = 2 leads to a simple algorithm with a running time of Õ(n2/3). The asymptotic running time can be further improved by plugging in recent more efficient algorithms for the closest pair problem. Our results also yield a sub-linear time algorithm for approximate pattern matching algorithm for a random signal (text), even for the case when the error between the signal and the code (pattern) is asymptotically as large as the code size. This is the first sublinear time algorithm for such error rates.

Original languageEnglish (US)
Title of host publicationProceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
PublisherAssociation for Computing Machinery
Number of pages9
ISBN (Print)9781611972511
StatePublished - 2013
Externally publishedYes
Event24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 - New Orleans, LA, United States
Duration: Jan 6 2013Jan 8 2013

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Country/TerritoryUnited States
CityNew Orleans, LA

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Shift finding in sub-linear time'. Together they form a unique fingerprint.

Cite this