{"id":"bc53068f-17aa-4d7b-92ed-9e710342fe4f","arxiv_id":"2411.14387","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Wilber's Alternation bound is subadditive and the Funnel bound is superadditive under sequence composition, yielding optimality of Tango trees among Alternation-charging BST algorithms for all Alternation values.","lead":"The paper proves direct-sum theorems for Wilber's two main lower bounds on binary search tree access sequences, showing the Alternation bound composes subadditively and the Funnel bound composes superadditively. It uses this to amplify known hard sequences and to prove that Tango trees are optimal among algorithms that charge their cost to the Alternation bound, for every value of that bound.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 20's proof depends on an unverified geometric ordering claim; the given contradiction is inconclusive because it places a boundary point inside the rectangle.","rationale":"The reader identified the Funnel superadditivity theorem as the weakest assumption, specifically the geometric monotonicity claim about external funnel points occurring later than internal funnel points and the asserted no-double-counting step. My stress-test agrees: this is the single most load-bearing point because the Funnel half of Theorem 1 is the engine behind the hardness amplification and the Tango-tree optimality corollaries. The paper's own text says the proof is 'mostly by picture' and gives only a sketch. My analysis sharpens the concern: the one-paragraph contradiction in Section 5 is inconclusive because the point it places inside the rectangle lies on the rectangle's boundary (same range index as p), so the argument is valid only under a boundary-inclusive rectangle convention that the paper does not state. Under the more usual open-rectangle convention the ordering claim can fail; I sketched a concrete scenario. This does not prove Theorem 20 false, but it shows the proof as written is not rigorous, and the theorem could even be false under a specific interpretation. Since the equal-length gap in the Alternation theorem does not affect the applications, the Funnel issue is the true load-bearing concern. The reader's CONDITIONAL verdict remains appropriate: the gap is localized and potentially repairable, but a full proof or an independent verification is required before the central claims can be accepted. I therefore keep the verdict unchanged and propose a brute-force test that would settle whether the ordering claim and the superadditivity inequality actually hold on small instances.","tokens_in":20147,"tokens_out":16243,"duration_ms":156495,"concrete_test":"Write a small brute-force verifier (e.g., Python) that enumerates all composed sequences X = ~X(X^(1),...,X^(l)) over key sets with total n ≤ 4 and total length m ≤ 8, using the exact funnel definition in the paper (Definition 14, including the rectangle convention as written). For every point p, compute the external funnel points (mapped from G~X) and internal funnel points (mapped from G_{X^(j_x)}), and check whether all external y-coordinates exceed all internal y-coordinates. Independently compute Funnel(X), Funnel(~X), and sum_j Funnel(X^(j)), and test whether Funnel(X) ≥ Funnel(~X) + sum_j Funnel(X^(j)) − O(m) holds. Report the first counterexample to either the ordering claim or the inequality; a counterexample to the inequality would disprove Theorem 20, while a counterexample only to the ordering would show the current proof is invalid even if the theorem may be repairable.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The Funnel half of Theorem 1 (Theorem 20, Section 5) is the load-bearing lower-bound ingredient for Theorems 2, 3, and 5. Its proof asserts that for each accessed point p, every external funnel point occurs later in time than every internal funnel point, and uses this to argue that side-switches in the two constituent funnels are preserved without double-counting. The only justification is one contradiction paragraph: assuming an internal point (xI,tI) with tI > tE for an external point (xE,tE), it says (jxI,tI) lies inside the rectangle formed by (jx,t) and (jxE,tE) and thus blocks the external funnel point. But jxI = jx, so (jxI,tI) lies on the vertical boundary x = jx of that rectangle, not in its interior. Whether such a boundary point blocks the external funnel point depends entirely on a closed-versus-open rectangle convention, which the paper does not fix. Under the standard 'empty open rectangle' convention, boundary points do not block, and the claimed ordering is false: e.g., with l = 3, template ~X = (1,2,2,3,2), a left external funnel point from index 1 at time 1 can coexist with an internal funnel point in range 2 at time 2 for p = (2,5), since the intermediate point (2,2) lies on the same vertical line as p. Under a closed-rectangle convention the ordering may hold, but then the definition of the funnel bound and its relationship to Wilber's bound and to [27] needs re-examination. The proof further asserts 'there is no double counting' without a formal argument. Thus the Funnel superadditivity theorem is not established by the text; if the ordering claim fails, the proof strategy collapses, and if the theorem itself fails, the paper's main applications do. A second gap exists in Theorem 19, which is proved only under the equal-length assumption |X(1)|=...=|X(l)| (footnote 7), while Theorem 1 is stated without it; however, the hardness-amplification applications only use the equal-length case, so the Funnel issue is the more damaging one.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves direct-sum theorems for Wilber's Alternation and Funnel lower bounds for binary search trees. In Theorem 1 it claims that the Alternation bound is subadditive under sequence composition and the Funnel bound is superadditive, up to O(m) terms. The Alternation part is proved by decomposing a reference tree into a tree over the ranges and trees over individual ranges, and classifying preferred-child alternations into four types. The Funnel part is proved in Section 5 by a geometric argument that the funnel of a point in a composed sequence contains the external funnel from the template and the internal funnel from the corresponding sub-sequence. The paper then uses these direct-sum theorems to amplify the known Alternation/Funnel separation, obtaining sequences with amortized Alternation O(R) and amortized Funnel Omega(R log(log n / R)). From this it derives trade-offs between additive and multiplicative competitive ratios for any algorithm charging cost to the Alternation bound, and concludes that Tango trees are optimal among such algorithms for all values of Alt(X), including regimes where the competitive ratio is o(log log n). A parameterized BST algorithm in Appendix A provides a matching upper bound.","tokens_in":20445,"tokens_out":19369,"duration_ms":168842,"significance":"If correct, these are strong and useful results. The Alternation subadditivity is cleaner and stronger than the previously known approximate version, and the four-type classification in Section 3 is a nice structural contribution. The Funnel superadditivity, if established, would be a novel tensorization property for a bound that is conjectured to characterize OPT, and it directly enables the hardness amplification used in Theorems 2, 3, and 5. The Tango-optimality corollary is crisp and covers previously open regimes. The paper's main weakness is that the Funnel superadditivity proof is a sketch with a false geometric assertion, and the Alternation statement overclaims by omitting the equal-length assumption used in its proof. The applications in Section 4 are not machine-checked, but the derivations are explicit and the base separation sequence is taken from the published paper [27].","major_comments":[{"comment":"The proof of Funnel superadditivity is not rigorous and contains a key claim that is false under the standard open-rectangle convention. The text asserts that 'all points of the external funnel are later in time than all points of the internal funnel' and gives a contradiction argument placing (jxI,tI) inside the rectangle formed by (jx,t) and (jxE,tE). However, since jxI = jx, the point lies on the vertical boundary of that rectangle, not in its interior; whether boundary points block is convention-dependent and the paper does not fix a convention. Under the usual open-rectangle definition of funnel points, the assertion is false. For example, let S1={1}, S2={2,3}, S3={4}, template X~=(1,2,3,2), and inner sequences X^(1)=(1), X^(2)=(2,3), X^(3)=(4); the composed sequence is X=(1,2,4,3). In G_X~, for p=(2,4), the point (1,1) is a left external funnel point. In G_X, for p=(3,4), the point (2,2) is an internal left funnel point (from X^(2)) occurring at time 2, later than the external point at time 1. Moreover, (1,1) is not a funnel point of (3,4) in G_X because (2,2) lies in the rectangle (1,3)x(1,4). Thus the claimed inclusion of the external funnel in the combined funnel is false, and the subsequent 'no double counting' assertion is unsupported. Since Theorem 20 is the load-bearing lower-bound half of Theorem 1, this gap affects the Funnel inequalities in Theorems 2, 3, and 5. The proof must be replaced by a formal geometric argument, and the open/closed-rectangle convention must be fixed and checked against the definitions in Section 2 and against [27].","section":"Section 5, Theorem 20"},{"comment":"Theorem 1 states the Alternation subadditivity for arbitrary composed sequences, but Theorem 19 proves it only under the assumption |X^(1)| = ... = |X^(l)|, and the proof explicitly uses this assumption to bound type-3 alternations by l * max_j |X^(j)| = m. Without equal lengths, that bound can be much larger than O(m) (e.g., one very long sequence and many short ones), so the stated theorem is not justified. The applications in Section 4 compose equal-length copies, so the main results are likely unaffected, but the theorem as stated is stronger than what is proved. The authors should either prove the general case or add the equal-length hypothesis to Theorem 1 and adjust the abstract and introduction accordingly.","section":"Theorem 1 and Theorem 19"}],"minor_comments":[{"comment":"The amortized versions are defined with bars (Alt(X), Funnel(X)), but the theorems in Sections 3 and 4 use the same symbols without bars for what appear to be total quantities. This notational inconsistency could confuse readers; please use distinct notation throughout.","section":"Section 2, Definition 16"},{"comment":"There is a missing citation in 'there is an optimal algorithm for sorting pattern-avoiding sequences [?]' — the placeholder '[?]' should be replaced by the intended reference.","section":"Section 1.2"},{"comment":"In the charging argument for the second subcase of type 2, the sentence 'The access to x is the first time that the preferred child switches back from b's left child to b's right child after accessing y' appears garbled; it should refer to the access to x as the one that set the preferred child, and the subsequent switch as occurring at the access to y.","section":"Section 3.1.4, proof of Claim 23"},{"comment":"The padding step ('It is easy to see that this maintains the bounds') should be justified in a sentence or two: inserting each key in ascending order adds at most O(m) to the total Alternation and O(m) to the total Funnel, which preserves the amortized bounds because the original Funnel lower bound is Omega(log log n).","section":"Section 4.1, proof of Theorem 25"}],"recommendation":"major_revision","confidential_remarks":"The Funnel superadditivity gap is the central technical problem. The current proof is a picture proof with a demonstrably false ordering claim, so the paper cannot be accepted without a complete rewrite of Section 5. The rest of the paper is promising and the applications are clean; if the Funnel theorem is repaired (or if the lower-bound applications are reproved via another route), the paper would be a strong contribution. I also note that the base separation sequence is taken from [27], which has overlapping authors with this paper; this is acceptable since [27] is published, but the Funnel bound definitions in [27] and in this paper should be compared carefully when the proof is revised."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I'll cut to it. This paper proves exact subadditivity of the Alternation bound under composition and claims superadditivity of the Funnel bound; if both hold, the hardness amplification and Tango-tree optimality corollaries are clean consequences. The Alternation half (Theorem 19) is detailed and I believe correct: the four-type classification and charging argument work, and the proof is actually simpler than the approximate version from Chalermsook et al. The result is genuinely new and worth having on its own.\n\nThe Funnel half is a different story. Section 5 is explicitly a picture proof, and the two load-bearing claims are not established. First, the assertion that every external funnel point is later than every internal funnel point is justified by one contradiction paragraph, but the reasoning places (jxI, tI) on the right boundary of the rectangle, not in its interior. Whether such a boundary point blocks the external funnel point depends on a closed-vs-open rectangle convention that the paper never fixes. Under the standard open-rectangle definition the claimed ordering can fail; I can construct it with l=3 and a repeated index. Second, 'there is no double counting' is asserted without argument. Since Funnel superadditivity is what drives Theorems 2, 3, and 5, this is the paper's main vulnerability. I don't think the theorem is necessarily false, but the text does not prove it.\n\nThere is also a smaller mismatch: Theorem 1 is stated for arbitrary sequence lengths, but the proof of Theorem 19 assumes equal lengths (footnote 7). The applications only use the equal-length case, so this is minor, but the statement should be corrected.\n\nCredit where due: the base case is properly imported from [27], and the citation pattern is fine. The trade-off theorem (Theorem 3) and the Tango optimality argument are natural and would be airtight once the Funnel inequality is solid.\n\nWho should read this: anyone working on dynamic optimality or BST lower bounds. The Alternation result alone is a useful contribution. The paper deserves a serious referee, but the referee must make Section 5 the center of attention. I would send it to review, with the expectation of major revision.","headline":"Exact direct-sum theorems for Wilber's bounds are a real advance, but the Funnel bound half is under-proved as written; the paper should go to review.","tokens_in":21105,"tokens_out":4594,"would_cite":true,"duration_ms":46198,"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":"Wilber's two BST bounds now obey direct-sum laws","keywords":["binary search trees","dynamic optimality","Wilber bounds","Alternation bound","Funnel bound","direct-sum theorems","hardness amplification","Tango trees"],"falsifier":"Write a small program that, for two very short access sequences $X^{(1)}$ and $X^{(2)}$ and a template $\\tilde{X}$, computes $\\mathrm{Funnel}(X)$ exactly from the geometric definition and compares it to $\\mathrm{Funnel}(\\tilde{X})+\\mathrm{Funnel}(X^{(1)})+\\mathrm{Funnel}(X^{(2)})$; a single composed sequence where the former is smaller by more than a small constant would refute superadditivity, and in particular one should search for a point whose external and internal funnel points are interleaved in time, violating the ordering claim.","tokens_in":19942,"feed_emoji":"🌳","tokens_out":11802,"duration_ms":87536,"temperature":0.7,"pith_summary":"The paper establishes direct-sum theorems for Wilber's two classic lower bounds on access-sequence cost in the binary search tree (BST) model: the Alternation bound and the Funnel bound. For a sequence formed by interleaving smaller access sequences according to a template, it proves that the Alternation bound of the composed sequence is at most the Alternation of the template plus the Alternation of the components, up to a linear error term, while the Funnel bound is at least the sum of the components' Funnel bounds, again up to a linear error term. These additive-composition laws make it possible to amplify hardness: repeatedly composing a base sequence that separates the two bounds yields sequences with Alternation $O(R)$ and Funnel $\\Omega(R \\log(\\log n / R))$, for essentially the full range of $R$. As a corollary, any BST algorithm whose cost is charged to the Alternation bound must have multiplicative overhead at least $\\Omega(\\log(\\log n / \\beta(n)))$ when it also pays an additive $\\beta(n)$, which is tight and proves Tango trees optimally extract what the Alternation bound offers. The paper thus sharpens the evidence that the Funnel bound, which has long been conjectured to characterise optimal offline BST cost, is the more faithful lower bound.","feed_headline":"Wilber's two BST bounds now obey direct-sum laws","feed_subtitle":"Composing access sequences adds the bounds, enabling hardness amplification and proving Tango trees optimal.","key_machinery":"The central mechanism is the composition of access sequences, defined via a template sequence $\\tilde{X}$ over component indices that interleaves the component sequences $X^{(j)}$, mapping each component key to a distinct contiguous range of keys. For the Alternation bound, the load-bearing device is a decomposition of any reference tree $T$ into a template tree $\\tilde{T}$ over the component indices and component trees $T_j$ over each component's keys; alternations are then partitioned into four types, with the extra types bounded by $O(|X|)$ via charging to individual accesses or to template nodes. For the Funnel bound, the load-bearing device is the geometric view of access sequences as point sets: for each point, its left and right funnel points are shown to split into an external funnel (from the template's geometry) and an internal funnel (from the component's geometry), with the ordering property that all external funnel points occur later than all internal funnel points, so the side-switch counts of the two inherited funnels add without cancellation.","core_discovery":"The paper's central claim, Theorem 1, is a pair of composition inequalities. Let $X = \\tilde{X}(X^{(1)},\\ldots,X^{(\\ell)})$ be the composed sequence obtained by interleaving component sequences according to a template sequence $\\tilde{X}$. Then $\\mathrm{Alt}(X) \\le \\mathrm{Alt}(\\tilde{X}) + \\sum_j \\mathrm{Alt}(X^{(j)}) + O(|X|)$ and $\\mathrm{Funnel}(X) \\ge \\mathrm{Funnel}(\\tilde{X}) + \\sum_j \\mathrm{Funnel}(X^{(j)}) - O(|X|)$. The first inequality is proved by decomposing an arbitrary reference tree into a template tree and component trees, then classifying every preferred-child alternation into one of four types: those that match an alternation in a component tree, those that match an alternation in the template tree, and two types that can be charged to individual accesses or to template nodes, bounding the extras by $O(|X|)$. The second inequality is proved geometrically: the funnel of a point in the composed sequence contains both an 'external funnel' inherited from the template and an 'internal funnel' inherited from the component, all external funnel points are later than all internal funnel points, and side-switches in either inherited funnel produce distinct side-switches in the combined funnel, so no double counting occurs. Using the base separation [27] as a seed, iterated composition yields Theorem 2's sequences, and these in turn give the Tango-optimality statements.","pith_inferences":["The composition machinery may extend to stronger lower bounds such as the Guillotine Bound or the Independent Rectangle bound, since they subsume Wilber's bounds and share the geometric point-set framework.","If the Funnel bound is truly superadditive, then any future BST algorithm that charges its operational cost to the Funnel bound could be composed in a black-box way, potentially yielding new $o(\\log \\log n)$-competitive algorithms for sequences where Funnel is large.","The hardness-amplified sequences are natural test cases for empirical comparisons of BST algorithms: they are easy for Alternation-based algorithms but difficult with respect to the Funnel structure.","A computational search over small composed sequences could test the geometric ordering claim; a violation would indicate that the Funnel superadditivity proof needs a different argument, though the Alternation subadditivity result would stand on its own."],"forward_implications":["There exist access sequences over $n$ keys with Alternation $O(R)$ and Funnel $\\Omega(R \\log(\\log n / R))$ for every power of two $R \\le \\log n / K$, giving an arbitrarily large separation between the two bounds.","Every BST algorithm with cost $\\alpha(n)\\,\\mathrm{Alt}(X) + \\beta(n)$ must have $\\alpha(n) = \\Omega(\\log(\\log n / \\beta(n)))$, and a simple parameterized Tango-style algorithm matches this trade-off.","Tango trees are optimal among all algorithms that charge their cost to the Alternation bound, for every value of $\\mathrm{Alt}(X)$, including the regime where the competitive ratio is $o(\\log \\log n)$.","Superadditivity of the Funnel bound means that $\\mathrm{Funnel}$ behaves like a true complexity measure under composition, strengthening the conjecture that $\\mathrm{Funnel}(X)$ is within a constant factor of the optimal offline cost $\\mathrm{OPT}(X)$.","Subadditivity of the Alternation bound is the first strong direct-sum theorem for that bound, improving on the known approximate version."],"supporting_citations":[{"why":"introduces the Alternation and Funnel lower bounds that the paper's direct-sum theorems concern.","marker":"[43]"},{"why":"proves the base separation between Alternation and Funnel that the composition construction amplifies.","marker":"[27]"},{"why":"defines the composition of access sequences and proves subadditivity of the optimal offline cost for composed sequences.","marker":"[9]"},{"why":"establishes the earlier approximate subadditivity of the Alternation bound, which this paper strengthens to an exact subadditivity.","marker":"[6]"},{"why":"introduces Tango trees, whose optimality among Alternation-bound-based algorithms is the main corollary.","marker":"[16]"},{"why":"introduces the dynamic optimality conjecture and splay trees, the motivating problem for all BST lower bounds.","marker":"[40]"},{"why":"supplies the geometric view of access sequences as point sets, used throughout the proofs and especially for the Funnel bound.","marker":"[15]"}],"fun_headline_variants":["Composing BST sequences amplifies hardness","Direct-sum laws for Wilber's bounds proven","Tango trees optimal for all Alternation values","New composition theorems for Wilber bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The superadditivity of the Funnel bound depends on a geometric ordering claim — that for each accessed point, every external funnel point appears later in time than every internal funnel point, and the inherited side-switches do not collide — which the paper sketches as 'mostly by picture' rather than proves in full.","fun_headline_variants_meta":{"raw":{"variants":["Composing BST sequences amplifies hardness","Direct-sum laws for Wilber's bounds proven","Tango trees optimal for all Alternation values","New composition theorems for Wilber bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000327,"raw_usage":{"total_tokens":1945,"prompt_tokens":1179,"completion_tokens":766,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":795,"completion_tokens_details":{"reasoning_tokens":711}},"tokens_in":795,"tokens_out":766,"duration_ms":7277,"temperature":1.0,"reasoning_tokens":711,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:14:54.526397+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Write a small program that, for two very short access sequences $X^{(1)}$ and $X^{(2)}$ and a template $\\tilde{X}$, computes $\\mathrm{Funnel}(X)$ exactly from the geometric definition and compares it to $\\mathrm{Funnel}(\\tilde{X})+\\mathrm{Funnel}(X^{(1)})+\\mathrm{Funnel}(X^{(2)})$; a single composed sequence where the former is smaller by more than a small constant would refute superadditivity, and in particular one should search for a point whose external and internal funnel points are interleaved in time, violating the ordering claim.","supporting_citations":[{"cited_title":"The landscape of bounds for binary search trees","cited_arxiv_id":"1603.04892","evidence_quote":"defines the composition of access sequences and proves subadditivity of the optimal offline cost for composed sequences."},{"cited_title":"Pinning down the strong wilber 1 bound for binary search trees","cited_arxiv_id":null,"evidence_quote":"establishes the earlier approximate subadditivity of the Alternation bound, which this paper strengthens to an exact subadditivity."}],"review_version":1}