Improved Bounds for Testing Forbidden Order Patterns

A sequence $f\colon\{1,\dots,n\}\to\mathbb{R}$ contains a permutation $π$ of length $k$ if there exist $i_1<\dots<i_k$ such that, for all $x,y$, $f(i_x)<f(i_y)$ if and only if $π(x)<π(y)$; otherwise, $f$ is said to be $π$-free. In this work, we consider the problem of testing for $π$-freeness with one-sided error, continuing the investigation of [Newman et al., SODA'17]. We demonstrate a surprising behavior for non-adaptive tests with one-sided error: While a trivial sampling-based approach yields an $\varepsilon$-test for $π$-freeness making $Θ(\varepsilon^{-1/k} n^{1-1/k})$ queries, our lower bounds imply that this is almost optimal for most permutations! Specifically, for most permutations $π$ of length $k$, any non-adaptive one-sided $\varepsilon$-test requires $\varepsilon^{-1/(k-Θ(1))}n^{1-1/(k-Θ(1))}$ queries; furthermore, the permutations that are hardest to test require $Θ(\varepsilon^{-1/(k-1)}n^{1-1/(k-1)})$ queries, which is tight in $n$ and $\varepsilon$. Additionally, we show two hierarchical behaviors here. First, for any $k$ and $l\leq k-1$, there exists some $π$ of length $k$ that requires $\tildeΘ_{\varepsilon}(n^{1-1/l})$ non-adaptive queries. Second, we show an adaptivity hierarchy for $π=(1,3,2)$ by proving upper and lower bounds for (one- and two-sided) testing of $π$-freeness with $r$ rounds of adaptivity. The results answer open questions of Newman et al. and [Canonne and Gur, CCC'17].