Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Approximate counting of permutation patterns
event speaker icon
Omri Ben-Eliezer (Technion)
event date icon
Wednesday, 20.11.2024, 12:45
event location icon
Taub 401

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).