Campus Event Calendar

AG 1

AG Audience

English

Note: We use this to send email in the morning.

30 Minutes

Saarbrücken

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

Zoom

527 278 8807

passcode not visible

logged in users only

If you wish to attend the talk online but do not have the zoom password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.

Roohani Sharma, 07/10/2023 16:31

Roohani Sharma, 07/09/2023 14:35

Roohani Sharma, 06/21/2023 10:23 -- Created document.

Roohani Sharma, 07/09/2023 14:35

Roohani Sharma, 06/21/2023 10:23 -- Created document.