Campus Event Calendar

Event Entry

What and Who

Improved sublinear algorithms for testing permutation freeness

Nithin Varma
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Tuesday, 11 July 2023
30 Minutes
E1 4


Given a permutation pi of length k, an array A is pi-free if there are no k array values that, when considered from left to right, have the same relative order as that of the permutation. For example, the array A has is (2,1)-free if there are no two indices i < j such that A[i] > A[j] and the array is (1,3,2)-free if there are no three indices i < j < v such that A[j] > A[v] > A[i]. In particular, the set of (2,1)-free arrays are simply the set of all sorted arrays.

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


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

527 278 8807
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at

Roohani Sharma, 07/10/2023 16:31
Roohani Sharma, 07/09/2023 14:35
Roohani Sharma, 06/21/2023 10:23 -- Created document.