Pagh's problem

Pagh's problem is a datastructure problem often used when studying lower bounds in computer science named after Rasmus Pagh. Mihai Pătrașcu was the first to give lower bounds for the problem. In 2021 it was shown that, given popular conjectures, the naive linear time algorithm is optimal.

Definition

We are given as inputs $k$ subsets $X_{1},X_{2},\dots ,X_{k}$ over a universe $U=\{1,\dots ,k\}$.

We must accept updates of the following kind: Given a pointer to two subsets $X_{1}$ and $X_{2}$, create a new subset $X_{1}\cap X_{2}$.

After each update, we must output whether the new subset is empty or not.