The Library
Testing periodicity
Tools
Lachish, Oded and Newman, Ilan (2011) Testing periodicity. Algorithmica, Volume 60 (Number 2). pp. 401420. doi:10.1007/s004530099351y
Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1007/s004530099351y
Abstract
We study the stringproperty of being periodic and having periodicity smaller than a given bound. Let I pound be a fixed alphabet and let p,n be integers such that P <= n/2 . A lengthn string over I pound, alpha=(alpha (1),aEuro broken vertical bar,alpha (n) ), has the property Period(p) if for every i,ja{1,aEuro broken vertical bar,n}, alpha (i) =alpha (j) whenever ia parts per thousand j (mod p). For an integer parameter the property Period(a parts per thousand currency signg) is the property of all strings that are in Period(p) for some pa parts per thousand currency signg. The property is also called Periodicity.
An epsilontest for a property P of lengthn strings is a randomized algorithm that for an input alpha distinguishes between the case that alpha is in P and the case where one needs to change at least an epsilonfraction of the letters of alpha to get a string in P. The query complexity of the epsilontest is the number of letter queries it makes for the worst case input string of length n. We study the query complexity of epsilontests for Period(a parts per thousand currency signg) as a function of the parameter g, when g varies from 1 to , while ignoring the exact dependence on the proximity parameter epsilon. We show that there exists an exponential phase transition in the query complexity around g=log n. That is, for every delta > 0 and ga parts per thousand yen(log n)(1+delta) , every twosided error, adaptive epsilontest for Period(a parts per thousand currency signg) has a query complexity that is polynomial in g. On the other hand, for , there exists a onesided error, nonadaptive epsilontest for Period(a parts per thousand currency signg), whose query complexity is polylogarithmic in g.
We also prove that the asymptotic query complexity of onesided error nonadaptive epsilontests for Periodicity is , ignoring the dependence on epsilon.
Item Type:  Journal Article  

Subjects:  Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software 

Divisions:  Faculty of Science > Computer Science  
Library of Congress Subject Headings (LCSH):  Periodic functions, Algorithms, Computational complexity  
Journal or Publication Title:  Algorithmica  
Publisher:  Springer Verlag  
ISSN:  01784617  
Official Date:  June 2011  
Dates: 


Volume:  Volume 60  
Number:  Number 2  
Page Range:  pp. 401420  
DOI:  10.1007/s004530099351y  
Status:  Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Restricted or Subscription Access  
Funder:  Israel Science Foundation (ISF)  
Grant number:  1011/06 (ISF) 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 