2026-07-24T17:51:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16439 2024-03-06T10:57:29Z ddc:004 open_access

Strongly Sublinear Algorithms for Testing Pattern Freeness Newman, Ilan Varma, Nithin Property testing Pattern freeness Sublinear algorithms For a permutation π:[k] → [k], a function f:[n] → ℝ contains a π-appearance if there exists 1 ≤ i₁ < i₂ < … < i_k ≤ n such that for all s,t ∈ [k], f(i_s) < f(i_t) if and only if π(s) < π(t). The function is π-free if it has no π-appearances. In this paper, we investigate the problem of testing whether an input function f is π-free or whether f differs on at least ε n values from every π-free function. This is a generalization of the well-studied monotonicity testing and was first studied by Newman, Rabinovich, Rajendraprasad and Sohler [Ilan Newman et al., 2019]. We show that for all constants k ∈ ℕ, ε ∈ (0,1), and permutation π:[k] → [k], there is a one-sided error ε-testing algorithm for π-freeness of functions f:[n] → ℝ that makes Õ(n^o(1)) queries. We improve significantly upon the previous best upper bound O(n^{1 - 1/(k-1)}) by Ben-Eliezer and Canonne [Omri Ben-Eliezer and Clément L. Canonne, 2018]. Our algorithm is adaptive, while the earlier best upper bound is known to be tight for nonadaptive algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ilan Newman and Nithin Varma 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.98 urn:nbn:de:0030-drops-164390 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.98 eng https://creativecommons.org/licenses/by/4.0/legalcode