Pagh's problem
 | This article needs more citations. (June 2021) |
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
[edit]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.
References
[edit]- ↑ 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.