BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20221007T120000Z
UID:c9d2e34d2c343acb0d21e3745a85c8df-340
DTSTAMP:19700101T120016Z
DESCRIPTION:Improved sublinear algorithms for testing permutation freeness
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/340/improved-sublinear-algorithms-for-testing-permutation-freeness/
SUMMARY: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: https://www.csa.iisc.ac.in/iisc-msr-seminar/
<br>
<br>
Microsoft teams link:
<a href="https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d">https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d</a>

Hosts: Rahul Madhavan and Rameesh Paul
DTSTART:20221007T120000Z
END:VEVENT
END:VCALENDAR