5 problems

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…

Let $x\in\mathbb{F}_2^n$. In the systematic model, the data structure stores $r$ precomputed bits of $x$ together with additional stored bits, and a query algorithm answers each of…

Hierarchical-counter lower-bound conjecture. There is no space-optimal hierarchical counter over $\mathbb{Z}_{m_1}\times \mathbb{Z}_{m_2}\times \mathbb{Z}_{m_3}$ unless $m_2$ and…

Let a list consist of $n$ numbers. The 3SUM problem asks whether three numbers in the list sum to zero. 3SUM conjecture. There is no algorithm solving 3SUM in time $O(n^{1.999})$.…