Title: Testing periodicity
Speaker: Oded Lachish, University of Haifa
Date: October 4, 2004 3:30-4:30pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
A string $\alpha$ of length $n$ has period $p$ if for every $i \leq n-p,$ $\alpha_i = \alpha_{i+p}$ where $\alpha_i$ is the $i$-th place of $\alpha$. A string is said to be {\it periodic} if it has a period in $[n/2]$ and is said to have {\it short period} if it has a logarithmic length period.
We study here the complexity of $\epsilon$-testing whether a given string has a period that is at most $g$, for a given parameter $g$. We construct an $\epsilon$-test for general periodicity testing, namely to decide whether a given string has a period smaller than $g$. The test uses $O(\sqrt{g \log g})$ queries. We then show that there is a matching lower bound for a large enough $g$.
Our main result is a construction of an $\epsilon$-test for $short-period$ that uses only $poly(\log \log n)$ queries. This should be contrasted with the $O(\sqrt{\log n \cdot \log \log n})$ that is implied by the general $\epsilon$-test. Hence this exhibits an interesting exponential phase transition in the complexity curve for testing periods around $g= \log{n}$. We then show that any 1-sided error test for short-periodicity requires $\Omega({\sqrt{\log \log n}})$ queries.
All the algorithms that are presented are non-adaptive 1-sided error.