2026-08-17T08:42:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18096 2024-03-06T11:01:00Z ddc:004 open_access

Sample-Based Distance-Approximation for Subsequence-Freeness Cohen Sidon, Omer Ron, Dana Property Testing Distance Approximation In this work, we study the problem of approximating the distance to subsequence-freeness in the sample-based distribution-free model. For a given subsequence (word) w = w_1 … w_k, a sequence (text) T = t_1 … t_n is said to contain w if there exist indices 1 ≤ i_1 < … < i_k ≤ n such that t_{i_{j}} = w_j for every 1 ≤ j ≤ k. Otherwise, T is w-free. Ron and Rosin (ACM TOCT 2022) showed that the number of samples both necessary and sufficient for one-sided error testing of subsequence-freeness in the sample-based distribution-free model is Θ(k/ε). Denoting by Δ(T,w,p) the distance of T to w-freeness under a distribution p:[n] → [0,1], we are interested in obtaining an estimate Δ̂, such that |Δ̂ - Δ(T,w,p)| ≤ δ with probability at least 2/3, for a given distance parameter δ. Our main result is an algorithm whose sample complexity is Õ(k²/δ²). We first present an algorithm that works when the underlying distribution p is uniform, and then show how it can be modified to work for any (unknown) distribution p. We also show that a quadratic dependence on 1/δ is necessary. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Omer Cohen Sidon and Dana Ron 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.44 urn:nbn:de:0030-drops-180964 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.44 eng https://creativecommons.org/licenses/by/4.0/legalcode