Pagh's problem

Algorithm for set intersection

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 {\displaystyle k} subsets X 1 , X 2 , … , X k {\displaystyle X_{1},X_{2},\dots ,X_{k}} over a universe U = { 1 , … , k } {\displaystyle U=\{1,\dots ,k\}} .

We must accept updates of the following kind: Given a pointer to two subsets X 1 {\displaystyle X_{1}} and X 2 {\displaystyle X_{2}} , create a new subset X 1 ∩ X 2 {\displaystyle X_{1}\cap X_{2}} .

After each update, we must output whether the new subset is empty or not.

References

  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.