### DIMACS Theoretical Computer Science Seminar

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.