@inproceedings{p25-soda,
  author = "Peyman Afshani and Nodari Sitchinava",
  title  = "A cell-probe lower bound for the predecessor search problem in {PRAM}",
  booktitle = "Proceedings of the 36th ACM-SIAM Symposium on Discrete Algorithms",
  series = "SODA '25",
  pages = "3998-4008",
  year = 2025,
  month = 1,
  doi = "10.1137/1.9781611978322.136",
  abstract = "We study the predecessor search problem in the classical PRAM model of computation.  In this problem, the input is a set of $n$ $\ell$-bit integers and the goal is to store the input in a data structure of size $S(n)$ such that given a query value $q$, the predecessor of $q$ can be found efficiently.  This is a very classical problem with an extensive history.

    We prove a lower bound for this problem in the strongest CRCW PRAM model.  A simplified version of the lower bound states that in a $K$-processor PRAM model with $O(\log n)$-bit registers, the query requires $\Omega(\log_K \log n)$ worst-case time under the realistic setting where the space is near-linear."
}