Theory Seminar, Wednesday Jan 22: Omri Ben-Eliezer (Technion) - Approximate counting of permutation patterns

[Arnold Filtser]

Hi all,

Next week (Wed Jan 22, at 12) we will meet for our theory seminar.

Location: Building 503 room 226.

See you all there,

Arnold

https://theory.cs.biu.ac.il/

Speaker: Omri Ben-Eliezer (Technion)
Title: Approximate counting of permutation patterns
Abstract: 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 parameterized 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), https://arxiv.org/pdf/2411.04718

[Arnold Filtser]

This happens tomorrow!