Abstract
We study the string-property of being periodic and having periodicity smaller than a given bound. Let Σ be a fixed alphabet and let p,n be integers such that \(p\leq \frac{n}{2}\) . A length-n string over Σ, α=(α 1,…,α n ), has the property Period(p) if for every i,j∈{1,…,n}, α i =α j whenever i≡j (mod p). For an integer parameter \(g\leq \frac{n}{2},\) the property Period(≤g) is the property of all strings that are in Period(p) for some p≤g. The property \(\mathit{Period}(\leq \frac{n}{2})\) is also called Periodicity.
An ε-test for a property P of length-n strings is a randomized algorithm that for an input α distinguishes between the case that α is in P and the case where one needs to change at least an ε-fraction of the letters of α to get a string in P. The query complexity of the ε-test is the number of letter queries it makes for the worst case input string of length n. We study the query complexity of ε-tests for Period(≤g) as a function of the parameter g, when g varies from 1 to \(\frac{n}{2}\) , while ignoring the exact dependence on the proximity parameter ε. We show that there exists an exponential phase transition in the query complexity around g=log n. That is, for every δ>0 and g≥(log n)1+δ, every two-sided error, adaptive ε-test for Period(≤g) has a query complexity that is polynomial in g. On the other hand, for \(g\leq \frac{\log{n}}{6}\) , there exists a one-sided error, non-adaptive ε-test for Period(≤g), whose query complexity is poly-logarithmic in g.
We also prove that the asymptotic query complexity of one-sided error non-adaptive ε-tests for Periodicity is \(\Theta(\sqrt{n\log n}\,)\) , ignoring the dependence on ε.
Similar content being viewed by others
References
Alon, N., Goldreich, O., Håstad, J., Peralta, R.: Simple construction of almost k-wise independent random variables. Random Struct. Algorithms 3(3), 289–304 (1992) and Addendum at same journal 4(1) 119–120 (1993)
Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. Wiley, New York (2000)
Ergun, F., Muthukrishnan, S., Sahinalp, C.: Sub-linear methods for detecting periodic trends in data streams. In: LATIN 2004, Proc. of the 6th Latin American Symposium on Theoretical Informatics, pp. 16–28 (2004)
Fischer, E.: The art of uninformed decisions: A primer to property testing. In: Paun, G., Rozenberg, G., Salomaa, A. (eds.) Current Trends in Theoretical Computer Science: The Challenge of the New Century, vol. I, pp. 229–264. World Scientific, Singapore (2004)
Gilbert, A.C., Guha, S., Indyk, P., Muthukrishnan, S., Strauss, M.: Near-optimal sparse Fourier representations via sampling. In: STOC 2002, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pp. 152–161 (2002)
Goldwasser, S., Goldreich, O., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45, 653–750 (1998)
Hadamard, J.: Sur la distribution des zéros de la fonction ζ(s) et ses conséquences arithmétiques. Bull. Soc. Math. France 24, 199–220 (1896)
Indyk, P., Koudas, N., Muthukrishnan, S.: Identifying representative trends in massive time series data sets using sketches. In: VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases, September 10–14, 2000, Cairo, Egypt, pp. 363–372. Morgan Kaufmann, San Mateo (2000)
Krauthgamer, R., Sasson, O.: Property testing of data dimensionality. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 18–27 (2003)
Naor, J., Naor, M.: Small-bias probability spaces: efficient construction and applications. SIAM J. Comput. 22(4), 838–856 (1993)
Newman, D.J.: Simple analytic proof of the prime number theorem. Am. Math. Mon. 87, 693–696 (1980)
Poussin, V.: Recherces analytiques sur la théorie des nombres premiers. Ann. Soc. Sci. Brux. (1897)
Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM J. Comput. 25, 252–271 (1996)
Ron, D.: Property testing (a tutorial). In: Handbook of Randomized Computing, pp. 597–649. Kluwer Academic, Dordrecht (2001)
Yao, A.C.: Probabilistic computations: Towards a unified measure of complexity. In: FOCS ’17: Proceedings of the 17th Annual Symposium on Foundations of Computer Science, pp. 222–227 (1977)
Author information
Authors and Affiliations
Corresponding author
Additional information
An initial report of these results was presented at Random05.
Research of I. Newman supported in part by an Israel Science Foundation grant number 1011/06.
Rights and permissions
About this article
Cite this article
Lachish, O., Newman, I. Testing Periodicity. Algorithmica 60, 401–420 (2011). https://doi.org/10.1007/s00453-009-9351-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-009-9351-y