Improved sublinear algorithms for testing permutation freeness

The problem of testing pi-freeness is to distinguish, with constant probability, arrays that are pi-free from arrays that need to be modified in at least a constant fraction of their values to be pi-free. This problem, which is a generalization of the well-studied monotonicity testing problem, was first studied systematically by Newman, Rabinovich, Rajendraprasad and Sohler (Random Structures and Algorithms; 2019). They proved that for all permutations pi of length at most 3, one can test for pi-freeness in polylog n many queries, where n is the array length. For arbitrary permutations of length k > 3, they also described a simple testing algorithm that makes O(n^{1-1/k}) queries. Most of the followup work has focused on improving the query complexity of testing pi-freeness for monotone pi.

In this talk, I will present an algorithm with query complexity O(n^{o(1)}) that tests pi-freeness for arbitrary permutations of constant length, which significantly improves the state of the art. I will also give an overview of the analysis that involves several combinatorial ideas.

Joint work with Ilan Newman