12 problems

Higher-moment convergence conjecture. All higher moments of the normalized variables in this convergence also converge to the corresponding moments of $N(0,\hat\gamma_t^2)$. The so…

Universal height lower-bound conjecture. For any permuton $cmu$ and $cvarepsilon>0$,

Let $P$ be a set of points in the plane. Write $\mathsf{SP}(P)$ for the minimum size of a set $Y\supseteq P$ such that every pair of points of $P$ is connected by a monotone axis-p…

Let $X\in[n]^m$ be an access sequence, and let $\operatorname{\mathsf{OPT}}(X)$ denote the cost of an optimal binary search tree serving $X$. A sequence is pattern-avoiding if it a…

A binary search tree algorithm is $O(1)$-competitive if its cost is at most a constant multiple of the cost of the optimum offline binary search tree on every access sequence. Dyna…

Consider an online binary search tree algorithm, and compare its cost on an access sequence with the cost of the optimum offline binary search tree. The sequence has length…

Let $\sigma$ be an access sequence on $[n]$, and let $\mathrm{OPT}(\sigma)$ be the minimum cost of serving $\sigma$ over all starting binary search trees. An algorithm is instance-…

A binary search tree (BST) algorithm is $O(1)$-competitive if its cost on every access sequence is at most a constant factor times the cost of the optimal offline BST algorithm, up…

Let $\mathcal{A}_{\{1\}}(n)$ be the Linial arrangement, and let $\mathcal{T}^{(1)}(n)$ denote the relevant class of trees. A binary search tree with $n$ nodes is a tree in…

Let ${\mathcal{A}}$ be an online binary search tree algorithm. Starting with any initial tree $T$ with $n$ elements, let $X$ be the preorder sequence of a binary search tree $T'$ t…

Let ${\mathcal{A}}$ be an online binary search tree algorithm. Starting with any initial tree $T$ with $n$ elements, consider any sequence of $n$ splits. A split at an element $x$…

Let ${\mathcal{A}}$ be an online binary search tree algorithm. Starting with any initial tree $T$ with $n$ elements, consider inserting or deleting the current minimum or maximum e…