Nearly Tight Lower Bound for Range Minimum Query via Probe-by-Probe Information Accounting

Abstract

We prove a nearly tight lower bound for succinct Range Minimum Query (RMQ) on an array of $n$ distinct integers. A query returns the position of the smallest entry in a specified subarray. For word size $\Theta (\log n)$, any cell-probe data structure answering queries in time $t$ requires $2n-1.5\log n+n/(\log n{)}^{O(t{\log }^{2}t)}$ bits of space. This improves the exponent $O(t^2{\log }^{2}t)$ in the lower bound of Liu and Yu (STOC 2020), leaving only a polylogarithmic gap in query time from the known upper bound across the redundancy range. The key ingredient is probe-by-probe information accounting. The previous analysis measures useful information at an "average" memory-access round of an adaptive query algorithm. For RMQ, the informative queries are database-dependent and unevenly distributed, making the conversion from this information to query savings lose a factor of $t$. We account for information across all memory accesses using an entropy telescoping argument. This gives a stronger progress bound within the existing published-bit round-elimination framework. The resulting viewpoint suggests a way to address similar averaging losses in other succinct lower bounds, although applications beyond RMQ remain open.

arXiv comment20 pages. To appear in Proceedings of the 38th ACM-SIAM Symposium on Discrete Algorithms (SODA 2027)