# Strongly Sublinear Algorithms for Testing Pattern Freeness

arXiv: https://arxiv.org/abs/2106.04856 · HTML: https://mlsanity.com/paper/2106.04856/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2021.

## Built on by (most cited first, 1 of 1)

- [Towards the methodology for solving the minimum enclosing ball and related problems](https://mlsanity.com/paper/2410.11063/) (2024)

## Abstract (arXiv)

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.