Pagh's problem

This article needs additional citations for verification. Please help by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources:  –  ·  ·  · scholar · JSTOR (June 2021) (Learn how and when to remove this template message)

Pagh's problem is a datastructure problem often used ^[1][2] 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.^[3] In 2021 it was shown that, given popular conjectures, the naive linear time algorithm is optimal.^[4]

Definition[]

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

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

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

References[]