Nithin Varma, Chennai Mathematical Institute, India

Abstract

An array of length n has a pi-appearance for a permutation pi: [k] --> [k] if there are k indices x_1 < x_2 < ..  < x_k such that the array value at x_{pi(i)} is greater than the array value at x_{pi(j)} if pi(i) > pi(j) for all i, j in [k]. The array is pi-free otherwise. The well-studied problem of testing if an array is sorted can be viewed as testing for (2,1)-freeness. In the talk, I present a recent algorithm to test pi-freeness using n^{o(1)} queries for permutations of arbitrary constant length. Our algorithm is a major improvement to the previous state of the art testers that had query complexity O(n^{1 - 1/{k-1}). Joint work with Ilan Newman.

Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://theory.cs.rutgers.edu/theory_seminar