{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T08:02:58Z","timestamp":1750492978575,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2022,3,23]],"date-time":"2022-03-23T00:00:00Z","timestamp":1647993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1146\/18"],"award-info":[{"award-number":["1146\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2022,3,31]]},"abstract":"\n In this work, we study the problem of testing subsequence-freeness. For a given subsequence (word)\n w<\/jats:italic>\n =\n w<\/jats:italic>\n 1<\/jats:sub>\n \u2026\n \n w\n k<\/jats:sub>\n <\/jats:italic>\n , a sequence (text)\n T<\/jats:italic>\n =\n t<\/jats:italic>\n 1<\/jats:sub>\n \u2026\n \n t\n n<\/jats:sub>\n <\/jats:italic>\n is said to contain\n w<\/jats:italic>\n if there exist indices 1 \u2264\n i<\/jats:italic>\n 1<\/jats:sub>\n < \u2026 <\n \n i\n k<\/jats:sub>\n <\/jats:italic>\n \u2264 n such that\n \n t\n ij<\/jats:sub>\n <\/jats:italic>\n =\n \n w\n j<\/jats:sub>\n <\/jats:italic>\n for every 1 \u2264\n j<\/jats:italic>\n \u2264\n k<\/jats:italic>\n . Otherwise,\n T<\/jats:italic>\n is\n w<\/jats:italic>\n -free. While a large majority of the research in property testing deals with algorithms that perform queries, here we consider\n sample-based<\/jats:italic>\n testing (with one-sided error). In the \u201cstandard\u201d sample-based model (i.e., under the uniform distribution), the algorithm is given samples (\n i<\/jats:italic>\n ,\n \n t\n i<\/jats:sub>\n <\/jats:italic>\n ) where\n i<\/jats:italic>\n is distributed uniformly independently at random. The algorithm should distinguish between the case that\n T<\/jats:italic>\n is\n w<\/jats:italic>\n -free, and the case that\n T<\/jats:italic>\n is \u03b5-far from being\n w<\/jats:italic>\n -free (i.e., more than an \u03b5-fraction of its symbols should be modified so as to make it\n w<\/jats:italic>\n -free). Freitag, Price, and Swartworth (Proceedings of RANDOM, 2017) showed that\n O<\/jats:italic>\n ((\n k<\/jats:italic>\n 2<\/jats:sup>\n log\n k<\/jats:italic>\n )\u03b5) samples suffice for this testing task. We obtain the following results.\n \n \n \u2013<\/jats:label>\n \n The number of samples sufficient for one-sided error sample-based testing (under the uniform distribution) is\n O<\/jats:italic>\n (\n k<\/jats:italic>\n \u03b5). This upper bound builds on a characterization that we present for the distance of a text\n T<\/jats:italic>\n from\n w<\/jats:italic>\n -freeness in terms of the maximum number of copies of\n w<\/jats:italic>\n in\n T<\/jats:italic>\n , where these copies should obey certain restrictions.\n <\/jats:p>\n <\/jats:list-item>\n \n \u2013<\/jats:label>\n \n We prove a matching lower bound, which holds for\n every<\/jats:italic>\n word\n w<\/jats:italic>\n . This implies that the above upper bound is tight.\n <\/jats:p>\n <\/jats:list-item>\n \n \u2013<\/jats:label>\n \n The same upper bound holds in the more general\n distribution-free<\/jats:italic>\n sample-based model. In this model, the algorithm receives samples (\n i<\/jats:italic>\n ,\n \n t\n i<\/jats:sub>\n <\/jats:italic>\n ) where\n i<\/jats:italic>\n is distributed according to an\n arbitrary<\/jats:italic>\n distribution\n p<\/jats:italic>\n (and the distance from\n w<\/jats:italic>\n -freeness is measured with respect to\n p<\/jats:italic>\n ).\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n We highlight the fact that while we require that the testing algorithm work for every distribution and when only provided with samples, the complexity we get matches a known lower bound for a special case of the seemingly easier problem of testing subsequence-freeness with one-sided error under the uniform distribution and with queries (Canonne et\u00a0al.,\n Theory of Computing<\/jats:italic>\n , 2019).\n <\/jats:p>","DOI":"10.1145\/3512750","type":"journal-article","created":{"date-parts":[[2022,3,24]],"date-time":"2022-03-24T22:26:31Z","timestamp":1648160791000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Optimal Distribution-Free Sample-Based Testing of Subsequence-Freeness with One-Sided Error"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6576-7200","authenticated-orcid":false,"given":"Dana","family":"Ron","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2707-6887","authenticated-orcid":false,"given":"Asaf","family":"Rosin","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}]}],"member":"320","published-online":{"date-parts":[[2022,3,23]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000292"},{"key":"e_1_3_3_3_2","doi-asserted-by":"crossref","unstructured":"Noga Alon Michael Krivelevich Ilan Newman and Mario Szegedy. 2001. Regular languages are testable with a constant number of queries. SIAM Journal on Computing 30 6 (2001) 1842\u20131862.","DOI":"10.1137\/S0097539700366528"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.64"},{"key":"e_1_3_3_5_2","first-page":"119:1\u2013119:17","volume-title":"Proceedings of the 48th International Colloquium Automata, Languages and Programming","author":"Bathie Gabriel","year":"2021","unstructured":"Gabriel Bathie and Tatiana Starikovskaya. 2021. Property testing of regular languages with applications to streaming property testing of visibly pushdown languages. In Proceedings of the 48th International Colloquium Automata, Languages and Programming. 119:1\u2013119:17."},{"key":"e_1_3_3_6_2","first-page":"11:1\u201311:20","volume-title":"Proceedings of the 10th Innovations in Theoretical Computer Science conference (ITCS)","author":"Ben-Eliezer Omri","year":"2019","unstructured":"Omri Ben-Eliezer. 2019. Testing local properties of arrays. In Proceedings of the 10th Innovations in Theoretical Computer Science conference (ITCS). 11:1\u201311:20."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.137"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.000-1"},{"key":"e_1_3_3_9_2","first-page":"9:1\u20139:14","volume-title":"Proceedings of the 44th International Colloquium Automata, Languages and Programming","author":"Ben-Eliezer Omri","year":"2017","unstructured":"Omri Ben-Eliezer, Simon Korman, and Daniel Reichman. 2017. Deleting and testing forbidden patterns in multi-dimensional arrays. In Proceedings of the 44th International Colloquium Automata, Languages and Programming. 9:1\u20139:14."},{"key":"e_1_3_3_10_2","first-page":"17:1\u201317:15","volume-title":"Proceedings of the 32nd International Symposium on Computational Geometry (SoCG)","author":"Berman Piotr","year":"2016","unstructured":"Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. 2016. Testing convexity of figures under the uniform distribution. In Proceedings of the 32nd International Symposium on Computational Geometry (SoCG). 17:1\u201317:15."},{"key":"e_1_3_3_11_2","first-page":"462:1\u2013462:14","volume-title":"Proceedings of the 43rd International Colloquium Automata, Languages and Programming","author":"Berman Piotr","year":"2016","unstructured":"Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. 2016. Tolerant testers of image properties. In Proceedings of the 43rd International Colloquium Automata, Languages and Programming. 462:1\u2013462:14."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451104"},{"key":"e_1_3_3_13_2","first-page":"2:1\u20132:13","volume-title":"Proceedings of the 34th IEEE Annual Conference on Computational Complexity (CCC)","author":"Bshouty Nader","year":"2019","unstructured":"Nader Bshouty. 2019. Almost optimal distribution-free junta testing. In Proceedings of the 34th IEEE Annual Conference on Computational Complexity (CCC). 2:1\u20132:13."},{"key":"e_1_3_3_14_2","first-page":"5:1\u20135:20","volume-title":"Proceedings of the 24th International Workshop on Randomization and Computation (RANDOM)","author":"Bshouty Nader","year":"2020","unstructured":"Nader Bshouty. 2020. Almost optimal testers for concise representations. In Proceedings of the 24th International Workshop on Randomization and Computation (RANDOM). 5:1\u20135:20."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.gs.2020.009"},{"key":"e_1_3_3_16_2","doi-asserted-by":"crossref","unstructured":"Cl\u00e9ment L. Canonne Elena Grigorescu Siyao Guo Akash Kumar and Karl Wimmer. 2019. Testing \\( k \\) -monotonicity: The rise and fall of boolean functions. Theory of Computing 15 1 (2019) 1\u201355.","DOI":"10.4086\/toc.2019.v015a001"},{"key":"e_1_3_3_17_2","first-page":"749","volume-title":"Proceedings of the 15th Annual ACM Symposium on the Theory of Computing (STOC)","author":"Chen Xi","year":"2018","unstructured":"Xi Chen, Zhengyang Liu, Rocco A. Servedio, Ying Sheng, and Jinyu Xie. 2018. Distribution-free junta testing. In Proceedings of the 15th Annual ACM Symposium on the Theory of Computing (STOC). 749\u2013759."},{"key":"e_1_3_3_18_2","first-page":"54","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Chen Xi","year":"2016","unstructured":"Xi Chen and Jinyu Xie. 2016. Tight bounds for the distribution-free testing of monotone conjuctions. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 54\u201371."},{"key":"e_1_3_3_19_2","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2009","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd. ed.). MIT Press and McGraw-Hill."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.78"},{"key":"e_1_3_3_21_2","first-page":"97","volume-title":"Proceedings of the 3rd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM)","author":"Dodis Yevgeniy","year":"1999","unstructured":"Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky. 1999. Improved bounds for testing monotonicity. In Proceedings of the 3rd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM). 97\u2013108."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2011.v007a011"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276757"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509977"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2154-3"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_3_27_2","first-page":"44:1\u201344:10","volume-title":"Proceedings of the 21st International Workshop on Randomization and Computation (RANDOM)","author":"Freitag Cody R.","year":"2017","unstructured":"Cody R. Freitag, Eric Price, and William J. Swartworth. 2017. Testing hereditary properties of sequences. In Proceedings of the 21st International Workshop on Randomization and Computation (RANDOM). 44:1\u201344:10."},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a010"},{"key":"e_1_3_3_29_2","doi-asserted-by":"crossref","unstructured":"Oded Goldreich. 2016. The uniform distribution is complete with respect to testing identity to a fixed distribution.ECCC TR16-015. To appear in the book: Computational Complexity and Property Testing LNCS 12050 pages 152\u2013172. 2020.","DOI":"10.1007\/978-3-030-43662-9_10"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781108135252"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070011"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2898355"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/050645804"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1656"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20840"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3155296"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/070701649"},{"key":"e_1_3_3_39_2","first-page":"27:1\u201327:19","volume-title":"Proceedings of the 24th International Workshop on Randomization and Computation (RANDOM)","author":"Ron Dana","year":"2020","unstructured":"Dana Ron and Asaf Rosin. 2020. Almost optimal distribution-free sample-based testing of \\( k \\) -modality. In Proceedings of the 24th International Workshop on Randomization and Computation (RANDOM). 27:1\u201327:19."},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.5555\/517168"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3512750","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3512750","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:28Z","timestamp":1750183768000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3512750"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,23]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3512750"],"URL":"https:\/\/doi.org\/10.1145\/3512750","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2022,3,23]]},"assertion":[{"value":"2021-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}