{"id":"ccc2a24f-e323-4546-b8f7-63dc33aa3245","arxiv_id":"2607.04509","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For any κ in [1, log log n], an m×n array admits an O(κ mn (log m + log log n))-bit 2D-RMQ encoding with O(log^{1/κ} n) query time.","lead":"The paper gives a space-time tradeoff for encoding an m-by-n array so any rectangle's maximum position can be answered without the original array. It nearly matches the known optimal space while keeping query time polylogarithmic rather than linear in the encoding size.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The manuscript supplies an explicit, fully combinatorial construction whose only non-standard ingredients are the active-set / origin definitions and the quarter-row decomposition. Both are proved carefully (Lemmas 4.2-4.6 and Observation 6.1). The space bound follows from a clean application of the log-sum inequality to pairwise-disjoint families of sets (or O(κ) such families after grouping by levels of D). The query algorithm makes a constant amount of progress per step measured by the child index of a fixed node of D, yielding the claimed O(log^{1/κ} n) bound. The interface between the reduction and the comparison structures is sealed by the short, self-contained Lemma 4.6. No hidden assumption, missing case, or circularity appears that would undermine Theorem 1.1. The reader's concern about Lemma 3.2 is therefore not load-bearing; the verdict ACCEPT with high confidence remains appropriate.","tokens_in":21262,"tokens_out":556,"duration_ms":5658,"concrete_test":"Independently re-derive the two-candidate reduction of Lemma 3.2 for a non-power-of-two height h, confirming that the two overlapping dyadic blocks R_top and R_bot cover the query rectangle and that the maximality argument still forces mutual visibility; then check that Lemma 4.6 maps those candidates into a co-active pair whose origins lie on a common root-to-leaf path of T. If both steps hold, the interface is sound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest_assumption (that Lemma 3.2 is not re-proved under the co-active machinery) does not threaten the central claim. Lemma 3.2 is proved independently in Section 3 by standard dyadic 1D-RMQ structures on rows, columns and power-of-two row blocks; mutual visibility of the two candidates is shown by a short maximality argument that never refers to origins or the tree T. Lemma 4.6 then verifies that any mutually visible pair is co-active, so the comparison structures of Sections 5-6 are applied only to pairs that the reduction actually produces. The space and query analyses of the baseline and full structures (Lemmas 5.4, 5.1, 5.3 and the O(κ) grouping by levels of D) rest solely on the log-sum inequality and standard rank/select encodings; they contain no circular dependence on the reduction. Consequently the trade-off of Theorem 1.1 stands.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies the encoding model for two-dimensional range maximum queries on an m\times n array (m≤n). It presents a family of encodings that, for every integer κ∈[1,loglogn], use O(κ mn(logm+loglogn)) bits and answer any axis-parallel range-maximum query in O(log^{1/κ}n) time (Theorem 1.1). The construction first reduces every query to a comparison of two mutually visible candidates via dyadic 1D-RMQ structures on rows, columns and power-of-two row blocks (Lemma 3.2). It then organises columns into a complete binary tree T, defines active sets and origins of points, and shows that the two candidates are always co-active. Co-active pairs are compared by a sequence of local ranking and lifting steps that move origins upward; a second τ-ary tree D on the depths of T (with τ=⌈log^{1/κ}n⌉) bounds the number of steps by O(τ). Both local primitives are realised by decomposing each active set into O(m) monotone quarter-rows and encoding them with standard rank/select and Elias-Fano structures. Space is controlled by the log-sum inequality applied level-wise on T and D.","tokens_in":21476,"tokens_out":804,"duration_ms":7376,"significance":"The result closes a long-standing gap between the O(mn min{m,logn})-bit constant-time encoding of Brodal et al. (Algorithmica 2012) and the asymptotically optimal but non-queryable O(mn logm)-bit encoding of Brodal et al. (ESA 2013). For any constant ε>0 one obtains near-optimal space with polylogarithmic query time; taking κ=loglogn recovers constant query time at a loglogn space factor. The argument is fully combinatorial, self-contained, and relies only on classical succinct primitives (1D RMQ, partial rank/select, Elias-Fano) together with the log-sum inequality. No machine-checked proofs or code are supplied, yet the derivation is transparent and the trade-off is clean. The work therefore constitutes a genuine advance in the encoding complexity of multidimensional range queries.","major_comments":[],"minor_comments":[{"comment":"In the statement of Theorem 1.1 and throughout Section 5 the query-time bound is written O(log^{1/κ}n); a short parenthetical remark that this is O(τ) with τ=⌈log^{1/κ}n⌉ would make the dependence on the arity of D immediately visible.","section":null},{"comment":"Figure 1 is helpful but the caption does not define the colours of the two paths in T; a one-sentence clarification would improve readability.","section":null},{"comment":"Lemma 2.4 (log-sum inequality) is proved in full; a citation to the classical form would suffice and free a few lines.","section":null},{"comment":"The phrase \"inherently sequential\" in the abstract and introduction is informal; replacing it by \"requires a linear scan of the encoding\" would be more precise.","section":null},{"comment":"A brief remark on whether the same trade-off extends to the indexing model (or why it does not) would help place the result in the broader literature.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is clean, the technical development is careful, and the gap it closes is well-known. I see no reason to delay acceptance; a light copy-edit for the minor points listed above is all that is needed."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper closes the long-standing gap between the O(1)-query O(mn min{m,log n}) encoding and the optimal-space but query-less O(mn log m) encoding for 2D RMQ. The new result is a continuous tradeoff: O(κ mn (log m + log log n)) bits and O(log^{1/κ} n) time for any κ ∈ [1, log log n]. That is the real contribution.\n\nWhat is new is the co-active/origin framework on the column tree, the second tree over depths that lets them control progress per lift, and the quarter-row decomposition that makes the local ranking and predecessor/successor primitives fit into the right entropy bounds. The baseline (κ=1) already gives near-optimal space with O(log n) queries; the full structure just multiplies space by O(κ) and drops the exponent. Space analysis is clean: repeated log-sum inequality plus standard rank/select and Elias-Fano. No free parameters, no circularity.\n\nThe reduction of Lemma 3.2 (two mutually visible candidates via dyadic row-block RMQs) sits outside the later machinery, but that is not a problem. It is proved independently by maximality, and Lemma 4.6 simply checks that those pairs are co-active, so the comparison structures only ever see legal inputs. The stress-test concern is therefore overstated; the central claim stands.\n\nSoft spots are minor. The log log n factor is still present even for constant κ, so the encoding is only near-optimal when n is not super-exponential in m. Construction time is not discussed, and there is no code. Citation pattern is appropriate and complete for the subfield.\n\nThis is for people who work on succinct geometric data structures or range queries. It is a solid theoretical advance that a serious editor should send to referees. I would bring it to reading group and expect to cite the tradeoff when the topic comes up.","headline":"Clean combinatorial tradeoff that finally bridges the 2012/2013 gap for 2D RMQ encodings; the co-active/origin + quarter-row machinery is new and the proofs hold up.","tokens_in":22167,"tokens_out":524,"would_cite":true,"duration_ms":5730,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P05","68W32"],"pacs":[],"model":"grok-4.5","headline":"Two-dimensional range-maximum encodings can be near-optimal in space and still answer queries in sub-logarithmic time.","keywords":["2D RMQ","range maximum queries","encoding model","succinct data structures","space-query trade-off","Cartesian-tree analogues","active points"],"falsifier":"Exhibit a family of m-by-n arrays and rectangles for which the two candidates returned by the dyadic-block reduction are not co-active, or for which no encoding of the claimed size can answer all rectangles in the claimed time, violating the stated trade-off.","tokens_in":22131,"feed_emoji":"📊","tokens_out":936,"duration_ms":13429,"temperature":0.7,"pith_summary":"Given an m-by-n array, the encoding problem asks for a compact representation that reports the position of the maximum in any axis-aligned rectangle without reading the original array. Prior work offered either constant-time queries at substantially super-optimal space, or asymptotically optimal O(mn log m) space with no proven efficient query procedure. This paper closes that gap with a single-parameter trade-off: for every integer kappa between 1 and log log n, an encoding of O(kappa mn (log m + log log n)) bits answers every query in O(log to the power 1/kappa of n) time. The result shows that near-optimal space need not force sequential decoding of the whole representation, and that query speed can be dialed continuously against a mild space multiplier.","feed_headline":"Near-optimal 2D range-max encodings with polylog queries","feed_subtitle":"A single parameter trades a log-log space factor for arbitrarily small polylog query time.","key_machinery":"Co-active pairs with origins in a binary column tree: every query is reduced to comparing two mutually visible points; each point is assigned an origin node, and a second tau-ary tree on depths organises local ranking and lifting structures so that each replacement moves the deeper origin across child blocks of a fixed ancestor, bounding the number of steps by the arity.","core_discovery":"For every integer kappa in [1, log log n] there exists a 2D-RMQ encoding of an m-by-n array that occupies O(kappa mn (log m + log log n)) bits and answers any range-maximum query in O(log^{1/kappa} n) time. In particular, constant kappa already yields near-optimal space whenever n is at most exponential in m, while kappa = log log n recovers constant query time at a log-log factor space cost.","pith_inferences":["The same depth-tree blocking idea may transfer to other encoding problems that currently possess only sequential optimal encodings (for example certain range top-k or range mode encodings).","If the O(mn log m) reduction itself can be made dynamic or partially dynamic, the whole trade-off would immediately yield dynamic near-optimal 2D RMQ encodings.","A matching lower-bound trade-off of the form “space O(mn log m + o(mn log log n)) forces super-constant query time” would settle whether the extra log-log factor is inherent."],"forward_implications":["Constant kappa already gives O(mn (log m + log log n))-bit encodings with polylogarithmic query time, asymptotically optimal whenever n is at most exponential in m.","Setting kappa = log log n recovers O(1) query time at only an O(log log n) multiplicative space blow-up over the information-theoretic lower bound.","The same co-active-origin and quarter-row machinery can be reused for other 2D range problems whose answers reduce to comparing structured pairs of points.","The gap between optimal encoding space and efficient support for 2D RMQ is no longer structural; only constant factors and lower-order terms remain open."],"fun_headline_variants":["Near-optimal 2D RMQ encodings with O(log^{1/κ} n) queries","Tunable near-optimal 2D range-max encodings via parameter κ","2D RMQ: near-optimal space and polylog time tradeoff","Efficient encodings for 2D RMQ in near-optimal space","κ-tuned 2D range maxima encodings with polylog queries"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"Every query rectangle can be answered by comparing exactly two mutually visible candidate points that a fixed O(mn log m)-bit preprocessing produces in constant time.","fun_headline_variants_meta":{"raw":{"variants":["Near-optimal 2D RMQ encodings with O(log^{1/κ} n) queries","Tunable near-optimal 2D range-max encodings via parameter κ","2D RMQ: near-optimal space and polylog time tradeoff","Efficient encodings for 2D RMQ in near-optimal space","κ-tuned 2D range maxima encodings with polylog queries"]},"model":"grok-4.5","effort":"low","cost_usd":0.007932,"raw_usage":{"total_tokens":1886,"prompt_tokens":798,"num_sources_used":0,"completion_tokens":90,"cost_in_usd_ticks":79320000,"prompt_tokens_details":{"text_tokens":798,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":998,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":798,"tokens_out":90,"duration_ms":21435,"temperature":1.0,"reasoning_tokens":998,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-11T18:21:44.144226+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit a family of m-by-n arrays and rectangles for which the two candidates returned by the dyadic-block reduction are not co-active, or for which no encoding of the claimed size can answer all rectangles in the claimed time, violating the stated trade-off.","supporting_citations":[],"review_version":1}