Strongly Sublinear Algorithms for Testing Pattern Freeness

Abstract

For a permutation $\pi :[k]\to [k]$, a function $f:[n]\to \mathbb{R}$ contains a $\pi$-appearance if there exists $1\le i_1<i_2<\cdots <i_k\le n$ such that for all $s,t\in [k]$, $f(i_s)<f(i_t)$ if and only if $\pi (s)<\pi (t)$. The function is $\pi$-free if it has no $\pi$-appearances. In this paper, we investigate the problem of testing whether an input function $f$ is $\pi$-free or whether $f$ differs on at least $\epsilon n$ values from every $\pi$-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\in \mathbb{N}$, $\epsilon \in (0,1)$, and permutation $\pi :[k]\to [k]$, there is a one-sided error $\epsilon$-testing algorithm for $\pi$-freeness of functions $f:[n]\to \mathbb{R}$ that makes $\tilde{O}(n^{o(1)})$ queries. We improve significantly upon the previous best upper bound $O(n^{1-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.

28 pages, 2 figures; We thank anonymous reviewers for comments that helped us significantly improve the presentation

References in corpus (2)

• Adaptive Lower Bound for Testing Monotonicity on the Line
• Fast property testing and metrics for permutations