[Theory Lunch 02/05] Calvin Leng: Counting Small Permutation Patterns

Skip to first unread message

Haoming Li

Feb 4, 2021, 1:41:38 AM2/4/21
to usc-theo...@googlegroups.com, usc-t...@googlegroups.com
USC CS Theory Lunch:

Counting Small Permutation Patterns
Speaker: Calvin Leng (cl...@usc.edu)
Time: 02/05/21 12:00pm
Location: https://usc.zoom.us/j/94386654763


A permutation pattern occurrence is a subset of a permutation that obeys a certain relative ordering in its entries, which finds applications in many areas such as stack sorting, property testing, quasi-randomness, and non-parametric statistics. We count the number of pattern occurrences for fixed patterns. Specifically, we devise a framework that counts "most" size 4 patterns in near linear time, and specifically improves on the previously best quadratic time algorithm for computing the Bergsma-Dassios-Yanagimoto statistic, which is a fully consistent variant of Hoeffding's independent tests. We then provide a direct algorithm for computing the rest of the size 4 patterns in $O(n^{3/2})$ time. (https://arxiv.org/abs/1911.01414)

See rest of semester schedule at:
(under construction) https://viterbi-web.usc.edu/~cstheory/theory-lunch.html
Reply all
Reply to author
0 new messages