Pagh's problem
Algorithm for set intersection
From Wikipedia, the free encyclopedia
Pagh's problem is a data structure 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 subsets over a universe .
We must accept updates of the following kind: Given a pointer to two subsets and , create a new subset .
After each update, we must output whether the new subset is empty or not.