Pith. sign in

REVIEW 3 major objections 3 minor 31 references

Dynamic Range Minimum Queries on the Ultra-Wide Word RAM

T0 review · 3 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Dynamic range minimum queries drop to O(log log log n) time per operation on the ultra-wide word RAM.

desk verdict A genuinely interesting O(log log log n) dynamic RMQ result on the UWRAM, but the arXiv write-up has two repairable correctness gaps (the lclear identity and missing query endpoints) that a referee should catch. read the letter →

arxiv 2411.16281 v3 pith:4GI5VPMH submitted 2024-11-25 cs.DS

Philip Bille , Inge Li G{o}rtz , Tord Stordalen , Máximo Pérez López This is my paper · ORCID
classification cs.DS
keywords dynamicrangeminimumultra-widewordRAMprefixword-levelparallelismscatteredmemoryaccesstreevectorprocessorsdatastructures
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Range minimum queries ask, given an array of w-bit integers, to return the smallest value in any subarray and to support changing one entry. On the ultra-wide word RAM, a model that idealizes modern vector processors with wide registers and scattered memory access, the paper claims both operations run in O(log log log n) time using O(n) space, an exponential improvement over the previous O(log log n) bound. The proof reduces the problem to computing prefix minima on word sequences of O(log n) words, then gives a recursive parallel prefix-minimum algorithm whose base case handles O(√w) words in constant time. If correct, this closes much of the gap between the word-RAM lower bound and what wide-vector hardware can actually deliver.

What carries the argument

The range minimum tree, reduced to prefix-minimum computations on word sequences stored in ultrawords, and a recursive parallel prefix-minimum algorithm that starts from a constant-time all-to-all comparison base case for sequences of O(√w) words and squares the block size b → b² each round. The base case relies on the left-clear operation, which smears the rightmost 0 of a bitstring to the left; the appendix implements it with the bit trick x & (x+1).

What would settle it

Evaluate the claimed identity lclear(x) = x & (x+1) on the 4-bit string 1011: the formula yields 1000, while the definition of left clear requires 0011, directly contradicting the proof of Theorem 7; a reader can verify this in any bitwise language.

Watch

Extended reading notes

Core claim

The paper claims to solve dynamic range minimum queries on the ultra-wide word RAM (UWRAM) with O(log log log n) time per rmq and update, using O(n) space and O(n) preprocessing time. The route is a reduction (Theorem 2): any algorithm computing prefix minima on word sequences of length O(log n) in time t(log n) yields a dynamic RMQ structure with the same bound. The reduction uses the classic range minimum tree, with blocks of size log n to compress space to linear. The technical heart is a new prefix-minimum algorithm for word sequences of length ℓ = O(w): it computes prefix minima of length O(√w) in constant time using all-to-all comparisons packed into ultrawords, then recursively combines b-way into b²-way prefix minima, doubling the block size each round, so O(log log ℓ) rounds suffice. Theorem 6 states the final prefix-minimum bound as O(log log log ℓ) (the introduction says O(log log ℓ)), and plugging it into the reduction gives Theorem 1.

Load-bearing premise

The whole construction rests on the claim that the 'left clear' bit operation can be done in constant time by the formula x & (x+1); that formula is wrong for some inputs, so the constant-time base case of the prefix-minimum algorithm is not currently proved.

Editorial extensions

If this is right

  • If Theorem 1 is correct, dynamic RMQ on the UWRAM takes O(log log log n) per operation, an exponential improvement over the O(log log n) bound obtained by previous UWRAM techniques.
  • The O(n) space and O(n) preprocessing mean the structure can be built once and then answer arbitrarily many updates and queries at the new speed.
  • The reduction is modular: any future improvement to prefix-minimum computation on word sequences automatically improves dynamic RMQ.
  • The same recursive b → b² prefix-minimum scheme may apply to other decomposable range queries, since it only needs componentwise comparisons and extracts.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The constant-time base case of Lemma 3 depends on the identity lclear(x) = x & (x+1), which is false for x = 1011 (binary): the formula yields 1000 while the required result is 0011. A different constant-time formula exists, so the main theorem is likely repairable, but the proof as written does not establish the base case.
  • The paper's own bounds are stated inconsistently, O(log log ℓ) in the introduction versus O(log log log ℓ) in Theorem 6; the abstract advertises the latter, and a reader should check which bound is intended.
  • If the base case is repaired, the recursive doubling of block sizes suggests the technique could extend to other models with wide registers or vector instructions, where the same all-to-all packing idea might give practical speedups for short sequences.
  • The O(n/log n) extra space beyond the input array means the data structure is compact enough for near-memory or cache-limited settings, though the paper does not analyze cache behavior.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper studies dynamic range minimum queries on the ultra-wide word RAM and claims an O(n)-space data structure supporting rmq and update in O(log log log n) time. The approach reduces RMQ to prefix-minimum computations on word sequences of length O(log n), then gives a recursive prefix-minimum algorithm for sequences of length O(w) that squares a block-size parameter each round, yielding O(log log L) time for the prefix-minimum routine, with the main theorem obtained by setting L = O(log n). The base case is a claimed constant-time prefix-minimum algorithm for sequences of length O(sqrt(w)) based on all-pairs comparisons and a bit-parallel 'left clear' operation.

Significance. If the proof is repaired, the result is significant: it improves the previously known O(log log n) bound for dynamic RMQ on the UWRAM by an exponential factor, and the recursive b to b-squared prefix-minimum scheme is an elegant use of ultraword parallelism. The paper is largely self-contained, gives explicit algorithms and reductions, and has no fitted parameters or circular dependencies; the main restrictions, such as precomputed constant word sequences, are stated openly. The two main technical concerns are the false 'left clear' identity in the appendix and the omitted endpoint values in the RMQ query; both are localized and appear repairable, but they are load-bearing for the stated theorems.

major comments (3)
  1. [Appendix A (Theorem 7); Section 5.1, Eq. (3)] Theorem 7 asserts that lclear(x) can be computed as x & (x+1), citing Knuth [22]. This identity is false: for x = 1011, the definition gives lclear(x) = 0011, while x & (x+1) = 1000. Since Eq. (3) in Section 5.1 computes D using this 'left clear' operation, and Lemma 3's constant-time base case is the foundation of Corollary 4, Lemma 5, and Theorem 6, the written proof does not establish the base case. A correct constant-time formula exists using (x ^ (x+1)) >> 1 with an explicit guard bit, with separate handling for all-ones blocks and for componentwise b-way application, but this construction must be supplied in the paper before the main theorem is justified.
  2. [Section 4.1] The rmq implementation computes min(W_Îr · W_Ĵl) from the extracted right and left path nodes and never takes the minimum with A[i] and A[j]. Section 3's algorithm explicitly includes the leaves i and j, and without them the query is wrong whenever the minimum is attained at an endpoint, including the case i = j. The fix is a constant-time addition of A[i] and A[j] to the final minimum, but as written Theorem 2's query operation is incorrect.
  3. [Section 5.2, Theorem 6] Theorem 6 states a bound of O(log log log L), but the surrounding derivation says the recursion runs for O(log log L) rounds, and the bound needed in Theorem 2 is t(L) = O(log log L) in order to obtain O(log log log n) in Theorem 1. Taken literally, the stated theorem would produce O(log log log log n) through the reduction. The statement should be corrected to O(log log L).
minor comments (3)
  1. [Section 5.1, Step 1] The definitions of the constant word sequences eA and bA are written in compressed notation that is easy to misread; an explicit formal definition in terms of their entries X⟨i,j⟩ would help the reader verify the shuffle patterns.
  2. [Figure 4] The rows corresponding to E, E′, E′′, and P are not labeled in the caption or the figure body; labeling them would make the three steps of Section 5.1 significantly easier to check.
  3. [Section 2.3] The notation '(10^{w-1})^w becomes (10^{cw-1})^w' is overloaded between bit lengths and repeated words; clarifying this notation would prevent confusion about the extended-precision masks.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the O(log log log n) dynamic RMQ bound is derived through a self-contained reduction to prefix-minimum computation; the false lclear identity in Appendix A is an internal correctness defect, not a circular step.

full rationale

The derivation chain is self-contained: Theorem 1 is obtained by composing Theorem 2, which reduces dynamic RMQ to prefix minimum on word sequences of length O(log n), with the prefix-minimum algorithm of Section 5. Theorem 2 builds on a standard range minimum tree and constant-time LCA data structures ([1,4,21]), while Section 5 constructs prefix minima from first principles using only UWRAM instructions and packed word sequences of length O(w). No parameter is fitted to the answer, and no quantity called a prediction is defined in terms of the claimed result. The self-citations ([6]-[9]) supply UWRAM word-level-parallelism building blocks and the conference version of this same paper; none of them assumes Theorem 1 or the O(log log log n) bound, so they are not load-bearing in a circular sense. The manuscript's real defect is not circularity: Appendix A's Theorem 7 claims lclear(x) = x & (x+1) (citing Knuth [22]), but this identity is false (for example, x = 1011 gives 1000 rather than the required 0011), so Lemma 3's constant-time base case is not proven as written. Because a correct constant-time formula exists and the later recursion does not otherwise assume the target bound, this is a repairable correctness gap rather than a circular derivation.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper has no fitted parameters or invented physical entities. It relies on the UWRAM model's constant-time wide operations, standard LCA precomputation, and one internal lemma (left clear) whose proof is incorrect as written.

assumptions (4)
  • domain assumption UWRAM operations on O(w)-word sequences run in constant time
    Section 2 states componentwise operations, compress/spread, and scattered memory access are constant-time for length O(w), citing prior UWRAM work [7,8,17].
  • ad hoc to paper Left clear is computable in constant time
    Appendix A, Theorem 7; the given implementation x & (x+1) is incorrect, so this axiom is currently unproven in the text.
  • standard math LCA queries on a static tree can be answered in constant time with linear-space preprocessing
    Used in Section 4.1; cited to [1,4,21].
  • domain assumption The input word size satisfies w >= log n
    Section 2 assumes pointers fit in one word, so w >= log n; needed to fit O(log n)-length sequences into ultrawords.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Dynamic Range Minimum Queries on the Ultra-Wide Word RAM." pith.science (2026). https://pith.science/paper/4GI5VPMH

@misc{pith2026241116281,
  author       = {Pith},
  title        = {Pith review of: Dynamic Range Minimum Queries on the Ultra-Wide Word RAM},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4GI5VPMH}},
  note         = {Machine review of arXiv:2411.16281}
}
abstract

We consider the dynamic range minimum problem on the ultra-wide word RAM model of computation. This model extends the classic $w$-bit word RAM model with special ultrawords of length $w^2$ bits that support standard arithmetic and boolean operation and scattered memory access operations that can access $w$ (non-contiguous) locations in memory. The ultra-wide word RAM model captures (and idealizes) modern vector processor architectures. The goal in the dynamic range minimum problem is to maintain an array $A$ of $n$ $w$-bit integers subject to range minimum queries (given indices $i$ and $j$ return a smallest integer in the subarray $A[i..j]$) and updates (given index $i$ and integer $\alpha$ set $A[i] \leftarrow \alpha$). Our main result is a data structure that supports range minimum queries and updates in $O(\log \log \log n)$ time and uses $O(n/\log n)$ space in addition to the input array. This exponentially improves the time of existing techniques. Our result is based on a simple reduction to prefix minimum computations on sequences $O(\log n)$ words combined with a new parallel, recursive implementation of these.

Figures

Figures reproduced from arXiv: 2411.16281 by the authors.

Figure 1
Figure 1. The layout of a word sequence X. 2.1 Instructions and Componentwise Operations Recall that ultrawords consist of w 2 bits. We often use ultrawords to store and manipulate small sequences of O(w) words. A word sequence X of length ℓ is a sequence of ℓ words (also called the components of X). We number the words from right to left starting from 0 and use the notation X⟨i⟩ to denote the ith word in X (see [PITH_FULL_I… view at source ↗
Figure 2
Figure 2. An example array A, with its range minimum tree. For a query rmq(1, 12), we illustrate with grey circles the right sequence vertices of i = 1 and the left sequence vertices of j = 12 of depth greater than d + 1 = 1. 4 From Range Minimum Queries to Prefix Minimum on the UWRAM In this section, we show that any UWRAM data structure that supports prefix minimum computations on word sequences of length O(log n) implies a… view at source ↗
Figure 3
Figure 3. Illustration of an update(5, α) query. We draw with grey circles the off-path sequence vertices. Note how the value of v10 should be min(v20, α), the value of v5 should be min(v10, v11) = min(v11, v20, α), and the value of v2 should be min(v4, v5) = min(v4, v11, v20, α), and so on. These values are the prefix minimum of the grey vertices and α. ˆJ l of I r and J l , respectively, that contains the nodes that have de… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Our prefix minimum algorithm, for w = 16 and a word sequence of length 4. Case 2: i and j are in different blocks. Let Bl , Bl+1, . . . , Br be the blocks covering the range from i to j and let i ′ and j ′ be the local indices in Bl and Br. We decompose the range into …
Figure 5
Figure 5. Figure 5: Illustration of Step 2 of Section 5.2: computing the 16-way prefix minimum of a word sequence b [PITH_FULL_IMAGE:figures/full_fig_p011_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [22]

    D. E. Knuth. The Art of Computer Programming, Volume 4. Pre-fascicle 1a: Bitwise Tricks and Techniques. 2008

    work page 2008

  2. [1]

    Alstrup, C

    S. Alstrup, C. Gavoille, H. Kaplan, and T. Rauhe. Nearest common ancestors: A survey and a new algorithm for a distributed environment. Theory Comput. Syst. , 37:441–456, 2004

    work page 2004

  3. [2]

    Alstrup, T

    S. Alstrup, T. Husfeldt, and T. Rauhe. Marked ancestor problems. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science , pages 534–543, 1998

    work page 1998

  4. [3]

    L. Arge, J. Fischer, P. Sanders, and N. Sitchinava. On (dynamic) range minimum queries in external memory. In Proc. 13th WADS, pages 37–48, 2013

    work page 2013

  5. [4]

    M. A. Bender and M. Farach-Colton. The LCA problem revisited. In Proceedings of the 4th Latin American Symposium on Theoretical Informatics , pages 88–94, 2000

    work page 2000

  6. [5]

    Berkman, D

    O. Berkman, D. Breslauer, Z. Galil, B. Schieber, and U. Vishkin. Highly parallelizable problems. In Proc. 21st STOC , pages 309–319, 1989

    work page 1989

  7. [6]

    Bille, I

    P. Bille, I. L. Gørtz, and F. R. Skjoldjensen. Partial sums on the ultra-wide word RAM. In Proc. 16 TAMC, 2020

    work page 2020

  8. [7]

    Bille, I

    P. Bille, I. L. Gørtz, and F. R. Skjoldjensen. Partial sums on the ultra-wide word RAM. Theor. Comput. Sci., 905:99–105, 2022

    work page 2022

Show all 31 references
  1. [8]

    Bille, I

    P. Bille, I. L. Gørtz, and T. Stordalen. Predecessor on the ultra-wide word RAM. Algorithmica, 86(5):1578–1599, 2024. 11

    2024

  2. [9]

    Bille, I

    P. Bille, I. L. Gørtz, T. Stordalen, and M. P´ erez L´ opez. Dynamic range minimum queries on the ultra-wide word RAM. In Proc. 50th SOFSEM , 2025

    2025

  3. [10]

    G. E. Blelloch. Prefix sums and their applications. In Synthesis of Parallel Algorithms . 1990

    1990

  4. [11]

    G. S. Brodal, S. Chaudhuri, and J. Radhakrishnan. The randomized complexity of maintaining the minimum. In Proc. 5th SWAT, pages 4–15, 1996

    1996

  5. [12]

    G. S. Brodal, P. Davoodi, M. Lewenstein, R. Raman, and S. R. Satti. Two dimensional range minimum queries and fibonacci lattices. Theoret. Comput. Sci. , 638:33–43, 2016

    2016

  6. [13]

    G. S. Brodal, P. Davoodi, and S. Srinivasa Rao. Path minima queries in dynamic weighted trees. In Proc. 12th WADS, pages 290–301, 2011

    2011

  7. [14]

    Chazelle and B

    B. Chazelle and B. Rosenberg. Computing partial sums in multidimensional arrays. In Proc. 5th SOCG, pages 131–139, 1989

    1989

  8. [15]

    T. Chen, R. Raghavan, J. N. Dale, and E. Iwata. Cell broadband engine architecture and its first implementation—a performance view. IBM J. Res. Dev. , 51(5):559–572, 2007

    2007

  9. [16]

    E. D. Demaine, G. M. Landau, and O. Weimann. On cartesian trees and range minimum queries. Algorithmica, 68:610–625, 2014

    2014

  10. [17]

    Farzan, A

    A. Farzan, A. L´ opez-Ortiz, P. K. Nicholson, and A. Salinger. Algorithms in the ultra-wide word model. In Proc. 12th TAMC, pages 335–346, 2015

    2015

  11. [18]

    Fischer and V

    J. Fischer and V. Heun. Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. , 40(2):465–492, 2011

    2011

  12. [19]

    H. N. Gabow, J. L. Bentley, and R. E. Tarjan. Scaling and related techniques for geometry problems. In Proc. 16th STOC , pages 135–143, 1984

    1984

  13. [20]

    T. Hagerup. Sorting and searching on the word ram. In Proc. 15th STACS, pages 366–398, 1998

    1998

  14. [21]

    Harel and R

    D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM J. Comput. , 13(2):338–355, 1984

    1984

  15. [23]

    R. E. Ladner and M. J. Fischer. Parallel prefix computation. J. ACM, 27(4):831–838, 1980

    1980

  16. [24]

    K. G. Larsen and R. Pagh. I/o-efficient data structures for colored range and prefix reporting. In Proc. 23rd SODA, pages 583–592, 2012

    2012

  17. [25]

    Lindholm, J

    E. Lindholm, J. Nickolls, S. Oberman, and J. Montrym. NVIDIA Tesla: A unified graphics and computing architecture. IEEE micro, 28(2):39–55, 2008

    2008

  18. [26]

    Pˇ atra¸ scu and E

    M. Pˇ atra¸ scu and E. D. Demaine. Logarithmic lower bounds in the cell-probe model.SIAM J. Comput. , 35(4):932–963, 2006. Announced at SODA 2004

    2006

  19. [27]

    Reinders

    J. Reinders. A VX-512 instructions. Intel Corporation, 2013

    2013

  20. [28]

    Sleator and R

    D. Sleator and R. E. Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci. , 26(3):362–391, 1983

    1983

  21. [29]

    Stephens et al

    N. Stephens et al. The ARM scalable vector extension. IEEE Micro, 37(2):26–39, 2017

    2017

  22. [30]

    A. C. Yao. On the complexity of maintaining partial sums. SIAM J. Comput. , 14(2):277–288, 1985

    1985

  23. [31]

    Yuan and M

    H. Yuan and M. J. Atallah. Data structures for range minimum queries in multidimensional arrays. In Proc. 21st SODA, pages 150–160, 2010. 12 A Implementing Left Clear We show how to implement the left clear operation. Let x be a bit string, and define rmz(x) to be the position...

    2010

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.