Jump to content

Pagh's problem

From Wikipedia, the free encyclopedia

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

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