Date:

Mon, 06/05/201911:00-13:00

Location:

CS building, room B-500, Safra campus

Speaker: Omri Ben Eliezer, TAU

Title: Finding patterns in permutations

Abstract:

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.

Title: Finding patterns in permutations

Abstract:

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.