Pagh's problem is a datastructure problem often used when studying lower bounds in computer science named after

Rasmus Pagh Rasmus Pagh is a Danish computer scientist and a professor of computer science at the University of Copenhagen. His main work is in algorithms and data structures, and he is particularly known for the cuckoo hashing algorithm and for co-founding ...

. 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.Henzinger, Monika, et al. "Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture." Proceedings of the forty-seventh annual ACM symposium on Theory of computing. 2015.

Definition

We are given as inputs

k

subsets

X_1, X_2, \dots, X_k

over a universe

U=\

. 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.

References

{{Reflist Problems in computer science