אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

A copy of a permutation pattern (say, 132) in a sequence of numbers is any subsequence whose values have the same relative order as in the pattern. (Say, for 132, the first element is smallest, the second is largest, and the third is in-between.).
 
Counting permutation patterns has a surprisingly rich set of connections and applications in ranking, statistics, combinatorics, fine-grained complexity, and parametrized complexity, especially for fixed small k. Here are three examples:
(i) Counting 4-cycles in sparse graphs is equivalent to counting 4-patterns [Dudek and Gawrychowski, 2020].
(ii) Many fundamental tests in nonparametric statistics amount to counting k-patterns for k up to 5.
(iii) The study of twin-width in parametrized complexity has originated from a breakthrough FPT algorithm of Guillemot and Marx [2013] for permutation pattern detection, which runs in linear time when k is fixed.
 
In this talk I will describe an algorithm for approximately counting all k-patterns for k up to 5 in near-linear time, deterministically, to within a (1+eps)-multiplicative error. This algorithm gives the first known (conditional) separation between exact and approximate counting in this domain. Interestingly, our algorithm leverages sublinear techniques from distribution testing, which to our knowledge have not been used in a pattern counting context before.
 
Joint work with Slobodan Mitrović (UC Davis) and Pranjal Srivastava (MIT).