Sample-Based Distance-Approximation for Subsequence-Freeness.

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 Trans Comput Theory 14(4):1–31, 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 error parameter δ . Our main result is a sample-based distribution-free algorithm whose sample complexity is O ~ (k 2 / δ 2) . 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. [ABSTRACT FROM AUTHOR]