TR04-092 Authors: Oded Lachish, Ilan Newman

Publication: 4th November 2004 17:33

Downloads: 2882

Keywords:

A string $\alpha\in\Sigma^n$ is called {\it p-periodic},

if for every $i,j \in \{1,\dots,n\}$, such that $i\equiv j \bmod p$,

$\alpha_i = \alpha_{j}$, where $\alpha_i$ is the $i$-th place of $\alpha$.

A string $\alpha\in\Sigma^n$ is said to be $period(\leq g)$,

if there exists $p\in \{1,\dots,g\}$ such that $\alpha$ is {\it p-periodic}.

An $\epsilon$

property tester for $period(\leq g)$ is a randomized algorithm, that

for an input $\alpha$ distinguishes between the case that $\alpha$ is in

$period(\leq g)$ and the case that

one needs to change at least $\epsilon$-fraction of the letters of

$\alpha$, so that it will become $period(\leq g)$. The complexity of

the tester is the number of letter-queries it makes to the input.

We study here the complexity of $\epsilon$ testers for $period(\leq g)$

when $g$ varies in the range $1,\dots,\frac{n}{2}$.

We show that there exists a surprising exponential phase

transition in the query complexity around $g=\log n$.

That is, for every $\delta > 0$ and for each $g$,

such that $g\geq (\log{n})^{1+\delta}$,

the number of queries required and sufficient for testing $period(\leq g)$

is polynomial in $g$.

On the other hand, for each $g\leq \frac{log{n}}{4}$, the number of

queries required and sufficient for testing $period(\leq g)$

is only poly-logarithmic in $g$.

We also prove an exact asymptotic

bound for testing general periodicity. Namely,

that 1-sided error, non adaptive $\epsilon$-testing

of periodicity ($period(\leq \frac{n}{2})$)

is $\Theta(\sqrt{n\log{n}})$ queries.