Pagh's problem

Pagh's problem is a datastructure problem often used

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. 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.Patrascu, Mihai. "Towards polynomial lower bounds for dynamic problems." Proceedings of the forty-second ACM symposium on Theory of computing. 2010.

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=\{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

Category:Problems in computer science