Pagh's problem

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

References

^ Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply strong lower bounds for dynamic problems." 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. IEEE, 2014.
^ Chen, Lijie, et al. "Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures." 16th Scandinavian Symposium and Workshops on Algorithm Theory. 2018.
^ Patrascu, Mihai. "Towards polynomial lower bounds for dynamic problems." Proceedings of the forty-second ACM symposium on Theory of computing. 2010.
^ 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.

[1] Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply strong lower bounds for dynamic problems." 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. IEEE, 2014.

[2] Chen, Lijie, et al. "Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures." 16th Scandinavian Symposium and Workshops on Algorithm Theory. 2018.

[3] Patrascu, Mihai. "Towards polynomial lower bounds for dynamic problems." Proceedings of the forty-second ACM symposium on Theory of computing. 2010.

[4] 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.

[1]

[2]

[3]

[4]