{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T08:06:48Z","timestamp":1787731608770,"version":"build-2784847793"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,8,29]],"date-time":"2009-08-29T00:00:00Z","timestamp":1251504000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,6]]},"DOI":"10.1007\/s00453-009-9351-y","type":"journal-article","created":{"date-parts":[[2009,8,28]],"date-time":"2009-08-28T14:41:05Z","timestamp":1251470465000},"page":"401-420","source":"Crossref","is-referenced-by-count":4,"title":["Testing Periodicity"],"prefix":"10.1007","volume":"60","author":[{"given":"Oded","family":"Lachish","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2009,8,29]]},"reference":[{"issue":"3","key":"9351_CR1","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N. Alon","year":"1992","unstructured":"Alon, N., Goldreich, O., H\u00e5stad, J., Peralta, R.: Simple construction of almost k-wise independent random variables. Random Struct. Algorithms 3(3), 289\u2013304 (1992) and Addendum at same journal 4(1) 119\u2013120 (1993)","journal-title":"Random Struct. Algorithms"},{"key":"9351_CR2","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. Wiley, New York (2000)","edition":"2"},{"key":"9351_CR3","doi-asserted-by":"crossref","unstructured":"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\u201328 (2004)","DOI":"10.1007\/978-3-540-24698-5_6"},{"key":"9351_CR4","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1142\/9789812562494_0014","volume-title":"Current Trends in Theoretical Computer Science: The Challenge of the New Century","author":"E. Fischer","year":"2004","unstructured":"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\u2013264. World Scientific, Singapore (2004)"},{"key":"9351_CR5","doi-asserted-by":"crossref","unstructured":"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\u2013161 (2002)","DOI":"10.1145\/509907.509933"},{"key":"9351_CR6","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"S. Goldwasser","year":"1998","unstructured":"Goldwasser, S., Goldreich, O., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45, 653\u2013750 (1998)","journal-title":"J. ACM"},{"key":"9351_CR7","doi-asserted-by":"crossref","first-page":"199","DOI":"10.24033\/bsmf.545","volume":"24","author":"J. Hadamard","year":"1896","unstructured":"Hadamard, J.: Sur la distribution des z\u00e9ros de la fonction \u03b6(s) et ses cons\u00e9quences arithm\u00e9tiques. Bull. Soc. Math. France 24, 199\u2013220 (1896)","journal-title":"Bull. Soc. Math. France"},{"key":"9351_CR8","first-page":"363","volume-title":"VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases","author":"P. Indyk","year":"2000","unstructured":"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\u201314, 2000, Cairo, Egypt, pp. 363\u2013372. Morgan Kaufmann, San Mateo (2000)"},{"key":"9351_CR9","unstructured":"Krauthgamer, R., Sasson, O.: Property testing of data dimensionality. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 18\u201327 (2003)"},{"issue":"4","key":"9351_CR10","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: efficient construction and applications. SIAM J. Comput. 22(4), 838\u2013856 (1993)","journal-title":"SIAM J. Comput."},{"key":"9351_CR11","doi-asserted-by":"crossref","first-page":"693","DOI":"10.2307\/2321853","volume":"87","author":"D.J. Newman","year":"1980","unstructured":"Newman, D.J.: Simple analytic proof of the prime number theorem. Am. Math. Mon. 87, 693\u2013696 (1980)","journal-title":"Am. Math. Mon."},{"key":"9351_CR12","unstructured":"Poussin, V.: Recherces analytiques sur la th\u00e9orie des nombres premiers. Ann. Soc. Sci. Brux. (1897)"},{"key":"9351_CR13","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM J. Comput. 25, 252\u2013271 (1996)","journal-title":"SIAM J. Comput."},{"key":"9351_CR14","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/978-1-4615-0013-1_15","volume-title":"Handbook of Randomized Computing","author":"D. Ron","year":"2001","unstructured":"Ron, D.: Property testing (a tutorial). In: Handbook of Randomized Computing, pp. 597\u2013649. Kluwer Academic, Dordrecht (2001)"},{"key":"9351_CR15","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Probabilistic computations: Towards a unified measure of complexity. In: FOCS \u201917: Proceedings of the 17th Annual Symposium on Foundations of Computer Science, pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9351-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9351-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9351-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T22:21:18Z","timestamp":1739312478000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9351-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,29]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["9351"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9351-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8,29]]}}}