We consider the problem of comparison-sorting an n-permutation S that avoids some k-
permutation π. Chalermsook, Goswami, Kozma, Mehlhorn, and Saranurak [CGK+ 15b] …

The extremal theory of forbidden 0-1 matrices studies the asymptotic growth of the function
Ex (P, n), which is the maximum weight of a matrix A∈{0, 1} n× n whose submatrices avoid a …

Search trees on trees (STTs) are a far-reaching generalization of binary search trees (BSTs),
allowing the efficient exploration of tree-structured domains.(BSTs are the special case in …

We consider the design of adaptive data structures for searching elements of a tree-
structured space. We use a natural generalization of the rotation-based online binary search …

We show that for any permutation π there exists an integer k π such that every permutation
avoiding π as a pattern factorises as the composition of at most k π separable permutations …

Permutation pattern-avoidance is a central concept of both enumerative and extremal
combinatorics. In this paper we study the effect of permutation pattern-avoidance on the …

We present a new connection between self-adjusting binary search trees (BSTs) and heaps,
two fundamental, extensively studied, and practically relevant families of data structures …

This paper studies a fundamental algorithmic problem related to the design of demand-
aware networks: networks whose topologies adjust toward the traffic patterns they serve, in …

Permutation patterns and pattern avoidance have been intensively studied in combinatorics
and computer science, going back at least to the seminal work of Knuth on stack-sorting …

Consider the task of performing a sequence of searches in a binary search tree. After each
search, an algorithm is allowed to arbitrarily restructure the tree, at a cost proportional to the …