5 problems

Let $R_{(b,k)}$ denote the rate of a $(b,k)$-hashing scheme, with integers $b\geq k>3$. For $j$ in the range $2\leq j\leq k-2$, let $b^{\underline{j+1}}$ denote the falling factori…

Let $k,n$ be positive integers. For each $j\in\{1,\ldots,k\}$, let $S_j$ be the collection of subsets $L\subseteq[n]^k$ such that $|L|=n$ and no two distinct elements of $L$ have t…

Let $q$ and $k$ be integers. Theorem 3.2 states that, for every $q\geq k^2$ and $k\geq 4$, the bound of Corollary 3.1 improves the general-code bound of Kőrner and Marton. Comparis…

Yao's conjecture. Every greedy open-addressed hash table must have worst-case expected probe complexity at least

Ullman's conjecture. The amortized expected probe complexity of every greedy algorithm should be at least order $Theta(\log \delta^{-1})$; equivalently, uniform probing is asymptot…