{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,13]],"date-time":"2024-01-13T00:37:08Z","timestamp":1705106228645},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"For a permutation $\\pi:[k] \\to [k]$, a function $f:[n] \\to \\mathbb{R}$\ncontains a $\\pi$-appearance if there exists $1 \\leq i_1 < i_2 < \\dots < i_k\n\\leq n$ such that for all $s,t \\in [k]$, $f(i_s) < f(i_t)$ if and only if\n$\\pi(s) < \\pi(t)$. The function is $\\pi$-free if it has no $\\pi$-appearances.\nIn this paper, we investigate the problem of testing whether an input function\n$f$ is $\\pi$-free or whether $f$ differs on at least $\\varepsilon n$ values\nfrom every $\\pi$-free function. This is a generalization of the well-studied\nmonotonicity testing and was first studied by Newman, Rabinovich,\nRajendraprasad and Sohler (Random Structures and Algorithms 2019). We show that\nfor all constants $k \\in \\mathbb{N}$, $\\varepsilon \\in (0,1)$, and permutation\n$\\pi:[k] \\to [k]$, there is a one-sided error $\\varepsilon$-testing algorithm\nfor $\\pi$-freeness of functions $f:[n] \\to \\mathbb{R}$ that makes\n$\\tilde{O}(n^{o(1)})$ queries. We improve significantly upon the previous best\nupper bound $O(n^{1 - 1\/(k-1)})$ by Ben-Eliezer and Canonne (SODA 2018). Our\nalgorithm is adaptive, while the earlier best upper bound is known to be tight\nfor nonadaptive algorithms.<\/jats:p>","DOI":"10.46298\/theoretics.24.1","type":"journal-article","created":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T10:55:12Z","timestamp":1705056912000},"source":"Crossref","is-referenced-by-count":0,"title":["Strongly Sublinear Algorithms for Testing Pattern Freeness"],"prefix":"10.46298","volume":"Volume 3","author":[{"given":"Ilan","family":"Newman","sequence":"first","affiliation":[]},{"given":"Nithin","family":"Varma","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2024,1,12]]},"container-title":["TheoretiCS"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/theoretics.episciences.org\/12865\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/theoretics.episciences.org\/12865\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T10:55:13Z","timestamp":1705056913000},"score":1,"resource":{"primary":{"URL":"https:\/\/theoretics.episciences.org\/10131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,12]]},"references-count":0,"URL":"http:\/\/dx.doi.org\/10.46298\/theoretics.24.1","relation":{"has-preprint":[{"id-type":"arxiv","id":"2106.04856v4","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2106.04856","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2106.04856","asserted-by":"subject"}]},"ISSN":["2751-4838"],"issn-type":[{"value":"2751-4838","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,12]]}}}