Seminars

View all Seminars  |  Download ICal for this event

Improved sublinear algorithms for testing permutation freeness

Series: Bangalore Theory Seminars

Speaker: Nithin Varma Chennai Mathematical Institute

Date/Time: Oct 07 16:00:00

Location: Microsoft Teams - ON-LINE

Abstract:
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 < k such that A[j] > A[k] > 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 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 was first studied systematically by Newman, Rabinovich, Rajendra Prasad and Sohler (Random Structures and Algorithms; 2019), where 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 permutations of length k > 3, they 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 a recent 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.
<br>
Joint work with Ilan Newman
<br>
Organizers Note: This paper had won the best paper award at ICALP 2022.
<br>
<br>
For more details please visit: Link
<br>
<br>
Microsoft teams link:
<a href="Link

Hosts: Rahul Madhavan and Rameesh Paul