ECCC-Report TR04-092https://eccc.weizmann.ac.il/report/2004/092Comments and Revisions published for TR04-092en-usThu, 04 Nov 2004 17:33:50 +0200
Paper TR04-092
| Testing Periodicity |
Oded Lachish,
Ilan Newman
https://eccc.weizmann.ac.il/report/2004/092A 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.
Thu, 04 Nov 2004 17:33:50 +0200https://eccc.weizmann.ac.il/report/2004/092