Combinatorics: Omri Ben Eliezer (TAU) "Finding patterns in permutations"

Mon, 06/05/201911:00-13:00
CS building, room B-500, Safra campus
Speaker: Omri Ben Eliezer, TAU
Title: Finding patterns in permutations
For two permutations sigma and pi, we say that sigma contains a copy of
pi, if there is a subset (not necessarily consecutive) of elements in sigma,
whose relative order is the same as in pi. For example, if pi = (1,2,3),
then a copy of pi in sigma amounts to an increasing subsequence in sigma
of length 3.
As shown by Guillemot and Marx, a copy of a constant length pi can be
found in sigma in linear time. However, how quickly can one find such a
pattern if guaranteed that sigma contains *many* disjoint copies of pi?
It was shown by Newman, Rabinovich, Rajendraprasad and Sohler that the
answer to this question is heavily dependent on the structure of the
pattern and the amount of adaptivity of the algorithm. In this talk,
I will focus on non-adaptive algorithms, proving some tight upper and
lower bounds and demonstrating several surprising phenomena.
Based on joint works with Clement Canonne, Shoham Letzter, and Erik Waingarten.