Strongly Sublinear Algorithms for Testing Pattern Freeness

For a permutation π:[k] → [k], a function f:[n] → ℝ contains a π-appearance if there exists 1 ≤ i1 < i2 < dots < ik ≤ n such that for all s,t ∈ [k], f(is) < f(it) 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 varepsilon 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 (Random Structures and Algorithms 2019). We show that for all constants k ∈ mathbbN, varepsilon ∈ (0,1), and permutation π:[k] → [k], there is a one-sided error varepsilon-testing algorithm for π-freeness of functions f:[n] → ℝ that makes tildeO(no(1)) queries. We improve significantly upon the previous best upper bound O(n1 - 1/(k-1)) by Ben-Eliezer and Canonne (SODA 2018). Our algorithm is adaptive, while the earlier best upper bound is known to be tight for nonadaptive algorithms.