{"id":"7e0a8d4a-5f61-4c42-95fd-4a52510dda43","arxiv_id":"2411.16281","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Dynamic range minimum queries and updates can be solved in O(log log log n) time on the ultra-wide word RAM with O(n) space.","lead":"This paper presents a data structure for dynamic range minimum queries on the ultra-wide word RAM, answering queries and updates in O(log log log n) time. This is an exponential improvement over the previous O(log log n) bound on the same model.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3's constant-time base case depends on the left-clear identity lclear(x)=x&(x+1) in Appendix A, which is false; a correct formula exists, so the main theorem is likely repairable, but the proof as written does not establish it.","rationale":"The reader's conditional verdict is appropriate. My stress-test pass confirms the weakest point: the base case of the new prefix-minimum algorithm is not proven as written, because Appendix A asserts a false identity. I checked the example x=1011: lclear should be 0011 but x&(x+1)=1000. This is not a matter of a missing edge case; the identity is wrong for most inputs. Since Lemma 3 is the foundation of the recursive O(log log ℓ) result, the main theorem's proof is incomplete. However, the algorithmic idea is sound in the sense that a correct constant-time formula exists: lclear(x) = (x ^ (x+1)) >> 1, with a sentinel zero above the all-ones pattern. The b-way componentwise version is more delicate (a naive global shift would mix adjacent blocks), but guard-bit SWAR techniques from the cited literature should handle it. Thus I would not reject the paper; I would require the authors to replace Theorem 7's proof and state the endpoint fix. I additionally verified the reader's secondary point: Section 4.1's rmq returns min(W_Î^r · W_Ĵ^l) and never includes A[i] and A[j], although Section 3 says the endpoints are part of the answer. This breaks query correctness as written and must also be patched. The statement of Theorem 6 as O(log log log ℓ) is another text-level inconsistency: the recursive squaring b←b² gives O(log log ℓ) rounds. This should be corrected when the proof is revised. Because both defects are localized and repairable, the verdict remains CONDITIONAL rather than REJECT; if the authors provide the corrected lclear construction and endpoint inclusion, the main claim is credible.","tokens_in":12638,"tokens_out":20260,"duration_ms":190524,"concrete_test":"Enumerate all bitstrings of length m ≤ 16 and compare lclear(x) as defined in Appendix A with x & (x+1); this will exhibit mismatches such as x=1011. Then verify that ((x ^ (x+1)) >> 1), with a sentinel 0 at position m for x=1^m, matches lclear(x) for every x, and that this extends componentwise to b-way word sequences using the UWRAM compress/spread and guard-bit arithmetic. If the corrected formula passes on all patterns and can be implemented in constant time on the restricted UWRAM, the concern is resolved; if not, Lemma 3 needs a different proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central O(log log log n) bound rests on the constant-time prefix-minimum base case (Lemma 3, Section 5.1). Its Step 2 requires forming D from Eq. (3) using the 'left clear' operation, which Appendix A implements as lclear(x) = x & (x+1) (Theorem 7). That identity is false: for x=1011 the definition of lclear gives 0011 (smear the rightmost 0 to the left), while x & (x+1) = 1000. Consequently Theorem 7 does not prove that D can be computed in constant time, so Lemma 3, the O(log log ℓ) prefix-minimum recursion, and Theorem 1 lack their stated base case. The defect is not obviously fatal: lclear(x) = (x ^ (x+1)) >> 1 is correct when a 0 bit exists above the top bit, and with guard bits the same idea works componentwise on b-bit blocks. But the paper does not give this construction, and the all-ones case needs an explicit sentinel/guard-bit handling. As written, a false identity carries the base case.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12873,"tokens_out":13758,"duration_ms":124385,"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":[{"comment":"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.","section":"Appendix A (Theorem 7); Section 5.1, Eq. (3)"},{"comment":"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.","section":"Section 4.1"},{"comment":"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).","section":"Section 5.2, Theorem 6"}],"minor_comments":[{"comment":"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.","section":"Section 5.1, Step 1"},{"comment":"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.","section":"Figure 4"},{"comment":"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.","section":"Section 2.3"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely salvageable: the two load-bearing gaps are localized, and the correct left-clear formula is standard. I recommend major revision rather than rejection, with the understanding that the corrected componentwise left-clear construction must be checked carefully for all-ones blocks and cross-component carries, and that the RMQ endpoint omission is fixed in the reduced space version as well as in the direct version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real result, not a hallucination. The paper gives an O(log log log n)-time dynamic RMQ on the UWRAM, improving the O(log log n) you get from plugging in earlier partial-sum machinery. The reduction in Section 4 is clean: a range minimum tree traversal becomes a prefix-minimum computation on O(log n) word sequences, and the space is brought to O(n) by a block decomposition. The new technical core is a recursive b-to-b^2 prefix-minimum algorithm, with a constant-time base case for length O(sqrt(w)) that uses all-to-all comparisons in an ultraword. I found that part genuinely clever, and the block-doubling recursion is original. The citation pattern looks fine; the self-citations are to earlier UWRAM work that the paper actually builds on.\n\nBut two flaws are real and need to be fixed before I would cite the bound as proved.\n\nFirst, Appendix A's constant-time left-clear is wrong. The claim lclear(x) = x & (x+1) is false: for x = 1011 it gives 1000, whereas the definition gives 0011. The correct bit trick, (x ^ (x+1)) >> 1 with guard bits for the all-ones case, is not in the paper. Since Lemma 3's constant-time base case depends on this, the O(1) step that the recursion rests on is not established. I agree with the stress-test note that this looks repairable, but as written the proof doesn't go through.\n\nSecond, the RMQ implementation in Section 4.1 forgets A[i] and A[j]. Section 3's description says the answer includes the leaves i and j, but the query code only takes off-path nodes with depth > d+1. That is a straightforward bug, but it means the data structure does not answer the query it claims to.\n\nThere are also small typos: Theorem 6 says O(log log log l) where the text argues O(log log l), and the abstract's space bound does not match Theorem 1. Those do not shake my sense of the main theorem, but they mean the current version should not be taken at face value. The high-level design is sound and the flaws are localized, so my verdict is 'conditional,' matching the reader's.\n\nThis paper is for people who work on word-RAM data structures, especially the UWRAM line. It deserves a serious referee, and I would send it out rather than desk-reject. Expect revision, but the core contribution is worth referee time.","headline":"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.","tokens_in":13395,"tokens_out":3787,"would_cite":true,"duration_ms":150040,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Dynamic range minimum queries drop to O(log log log n) time per operation on the ultra-wide word RAM.","keywords":["dynamic range minimum","ultra-wide word RAM","prefix minimum","word-level parallelism","scattered memory access","range minimum tree","vector processors","data structures"],"falsifier":"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.","tokens_in":12447,"feed_emoji":"⚡","tokens_out":6558,"duration_ms":57733,"temperature":0.7,"pith_summary":"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.","feed_headline":"Range-minimum queries now run in O(log log log n) time","feed_subtitle":"A new reduction to prefix-minimum computation beats the previous O(log log n) bound on a model of vector processors.","key_machinery":"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).","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces the ultra-wide word RAM with ultrawords and scattered memory access, the model whose power the paper exploits.","marker":"[17]"},{"why":"Supplies the componentwise word-sequence operations and the partial-sums techniques that give the previous O(log log n) UWRAM bound and the constant-time building blocks.","marker":"[7]"},{"why":"Standard parallel prefix computation that the paper's recursive prefix-minimum algorithm improves upon from O(log ℓ) to O(log log log ℓ).","marker":"[23]"},{"why":"Cited as the source of the bit trick x & (x+1) used in the left-clear constant-time proof, the paper's weakest step.","marker":"[22]"},{"why":"Gives the Θ(log n / log log n) lower bound for dynamic RMQ on the word RAM, the baseline that motivates seeking UWRAM improvements.","marker":"[13]"}],"fun_headline_variants":["Triple-log speedup for dynamic range minima on ultra-wide RAM","Range minimum queries hit O(log log log n) on vector RAM","Ultrawide RAM slashes range-minimum time to O(log log log n)","O(log log log n) dynamic range minima via ultra-wide words"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Triple-log speedup for dynamic range minima on ultra-wide RAM","Range minimum queries hit O(log log log n) on vector RAM","Ultrawide RAM slashes range-minimum time to O(log log log n)","O(log log log n) dynamic range minima via ultra-wide words"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00082,"raw_usage":{"total_tokens":3610,"prompt_tokens":988,"completion_tokens":2622,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":604,"completion_tokens_details":{"reasoning_tokens":2544}},"tokens_in":604,"tokens_out":2622,"duration_ms":18819,"temperature":1.0,"reasoning_tokens":2544,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:20:04.444935+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Farzan, A","cited_arxiv_id":null,"evidence_quote":"Introduces the ultra-wide word RAM with ultrawords and scattered memory access, the model whose power the paper exploits."},{"cited_title":"Bille, I","cited_arxiv_id":null,"evidence_quote":"Supplies the componentwise word-sequence operations and the partial-sums techniques that give the previous O(log log n) UWRAM bound and the constant-time building blocks."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Standard parallel prefix computation that the paper's recursive prefix-minimum algorithm improves upon from O(log ℓ) to O(log log log ℓ)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Cited as the source of the bit trick x & (x+1) used in the left-clear constant-time proof, the paper's weakest step."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the Θ(log n / log log n) lower bound for dynamic RMQ on the word RAM, the baseline that motivates seeking UWRAM improvements."}],"review_version":1}