Pith. sign in

REVIEW 2 major objections 4 minor 43 references

Hardness Amplification for Dynamic Binary Search Trees

T0 review · 2 major / 4 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 Wilber's two BST bounds now obey direct-sum laws

desk verdict 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. read the letter →

arxiv 2411.14387 v1 pith:7KQJTIEU submitted 2024-11-21 cs.DS

Shunhua Jiang , Victor Lecomte , Omri Weinstein , Sorrachai Yingchareonthawornchai This is my paper · ORCID
classification cs.DS
keywords binarysearchtreesdynamicoptimalityWilberboundsAlternationboundFunneldirect-sumtheoremshardnessamplificationTango
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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

2 major / 4 minor

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.

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 (2)
  1. [Section 5, Theorem 20] 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].
  2. [Theorem 1 and Theorem 19] 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.
minor comments (4)
  1. [Section 2, Definition 16] 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.
  2. [Section 1.2] 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.
  3. [Section 3.1.4, proof of Claim 23] 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.
  4. [Section 4.1, proof of Theorem 25] 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).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the direct-sum inequalities are proved from the definitions of Wilber's bounds, and the hardness amplification is an honest induction on a published base-case separation.

full rationale

The claimed derivation chain is not circular. Theorem 19 (subadditivity of Alternation) is proved by decomposing an arbitrary reference tree T into a template tree ~T and per-range trees T_j, classifying each preferred-child alternation into four types, and charging types 2 and 3 to O(m) events; no step defines Alt(X) in terms of Alt(~X)+sum_j Alt(X^j). Theorem 20 (superadditivity of Funnel) is asserted through a geometric containment argument: it claims the funnel of a composed point contains the mapped external and internal funnels and that side-switches do not double-count. That argument is only sketched, and the ordering assertion ("all points of the external funnel are later in time than all points of the internal funnel") may indeed be underproved because the contradicting point (jx_I,tI) lies on the boundary x=jx; however, this is a soundness/completeness concern about the proof, not a circular reduction, since Funnel(X) is not defined in terms of Funnel(~X)+sum_j Funnel(X^j) and no fitted constant or predicted quantity is being reused as an input. Theorem 2 then applies the two proved inequalities inductively, with the base-case sequence Y_n taken from Lecomte and Weinstein [27]. The self-citation is real and load-bearing for the base case, but the cited theorem is a separate published result with its own proof and stated assumptions; it does not presuppose the direct-sum theorems, the amplification construction, or the Tango-optimality conclusions of this paper. Theorems 3 and 5 are standard lower-bound consequences of Theorem 2 combined with the known Funnel lower bound on OPT. There are no fitted parameters, no prediction that is a renamed fit, and no ansatz smuggled in by citation. The central claims therefore stand or fall on the validity of the proofs, particularly the geometric lemma in Section 5, but that is a correctness risk rather than circularity.

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

No fitted parameters are used; the constants C_O, C_Omega, and K are chosen universally large and are not fitted to data. The central proofs rely on two external inputs: the lower-bound status of Wilber's bounds and the base separation of [27]. No new entities are postulated.

assumptions (3)
  • domain assumption Wilber's Alternation and Funnel bounds are lower bounds on OPT(X), i.e., Funnel(X) is within constants below OPT(X).
    Used in Section 4.2 to replace OPT(Y) by Omega(Funnel(Y)) in the lower-bound derivations. This is a standard fact from [43], not proved in the paper.
  • domain assumption Base separation sequence Y_n exists with Alt(Y_n)=O(1) and Funnel(Y_n)=Omega(log log n).
    Theorem 24 is quoted from [27], Lecomte and Weinstein, ESA 2020, and used as the base case for the induction in Theorem 25. The proof is not reproduced in this paper.
  • domain assumption Composition is applied to equal-length component sequences, and repeated templates preserve amortized bounds.
    The proof of Theorem 19 explicitly assumes |X^(1)|=...=|X^(l)|, and Theorem 25 uses sqrt(n) identical copies. The text says the assumption is for simplicity, but no removal argument is supplied.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Hardness Amplification for Dynamic Binary Search Trees." pith.science (2026). https://pith.science/paper/7KQJTIEU

@misc{pith2026241114387,
  author       = {Pith},
  title        = {Pith review of: Hardness Amplification for Dynamic Binary Search Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7KQJTIEU}},
  note         = {Machine review of arXiv:2411.14387}
}
abstract

We prove direct-sum theorems for Wilber's two lower bounds [Wilber, FOCS'86] on the cost of access sequences in the binary search tree (BST) model. These bounds are central to the question of dynamic optimality [Sleator and Tarjan, JACM'85]: the Alternation bound is the only bound to have yielded online BST algorithms beating $\log n$ competitive ratio, while the Funnel bound has repeatedly been conjectured to exactly characterize the cost of executing an access sequence using the optimal tree [Wilber, FOCS'86, Kozma'16], and has been explicitly linked to splay trees [Levy and Tarjan, SODA'19]. Previously, the direct-sum theorem for the Alternation bound was known only when approximation was allowed [Chalermsook, Chuzhoy and Saranurak, APPROX'20, ToC'24]. We use these direct-sum theorems to amplify the sequences from [Lecomte and Weinstein, ESA'20] that separate between Wilber's Alternation and Funnel bounds, increasing the Alternation and Funnel bounds while optimally maintaining the separation. As a corollary, we show that Tango trees [Demaine et al., FOCS'04] are optimal among any BST algorithms that charge their costs to the Alternation bound. This is true for any value of the Alternation bound, even values for which Tango trees achieve a competitive ratio of $o(\log \log n)$ instead of the default $O(\log \log n)$. Previously, the optimality of Tango trees was shown only for a limited range of Alternation bound [Lecomte and Weinstein, ESA'20].

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 24 canonical work pages

  1. [27]

    Settling the relationship between wilber's bounds for dynamic optimality

    Victor Lecomte and Omri Weinstein. Settling the relationship between wilber's bounds for dynamic optimality. In ESA , volume 173 of LIPIcs , pages 68:1--68:21. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2020. https://doi.org/10.4230/LIPIcs.ESA.2020.68 doi:10.4230/LIPIcs.ESA.2020.68

    doi:10.4230/lipics.esa.2020.68 2020

  2. [1]

    Self-organizing binary search trees

    Brian Allen and Ian Munro. Self-organizing binary search trees. J. ACM , 25(4):526--535, oct 1978. URL: http://doi.acm.org/10.1145/322092.322094, https://doi.org/10.1145/322092.322094 doi:10.1145/322092.322094

    arXiv 1978

  3. [2]

    Direct sums in randomized communication complexity

    Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. Direct sums in randomized communication complexity. Electron. Colloquium Comput. Complex. , TR09-044 , 2009. URL: https://eccc.weizmann.ac.il/report/2009/044, https://arxiv.org/abs/TR09-044 arXiv:TR09-044

    work page 2009

  4. [3]

    Optimization with pattern-avoiding input

    Benjamin Aram Berendsohn, L \' a szl \' o Kozma, and Michal Opler. Optimization with pattern-avoiding input. CoRR , abs/2310.04236, 2023. https://doi.org/10.48550/arXiv.2310.04236 doi:10.48550/arXiv.2310.04236

    work page doi:10.48550/arxiv.2310.04236 2023

  5. [4]

    Blelloch and Magdalen Dobson

    Guy E. Blelloch and Magdalen Dobson. The geometry of tree-based sorting. In ICALP , volume 261 of LIPIcs , pages 26:1--26:19. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.26 doi:10.4230/LIPIcs.ICALP.2023.26

    work page doi:10.4230/lipics.icalp.2023.26 2023

  6. [5]

    An O(log log n)-competitive binary search tree with optimal worst-case access times

    Prosenjit Bose, Karim Dou \" eb, Vida Dujmovic, and Rolf Fagerberg. An O(log log n)-competitive binary search tree with optimal worst-case access times. In Algorithm Theory - SWAT 2010, 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings , pages 38--49, 2010. https://doi.org/10.1007/978-3-642-13731-...

    work page doi:10.1007/978-3-642-13731-0 2010

  7. [6]

    Pinning down the strong wilber 1 bound for binary search trees

    Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak. Pinning down the strong wilber 1 bound for binary search trees. In APPROX-RANDOM , volume 176 of LIPIcs , pages 33:1--33:21. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2020. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.33 doi:10.4230/LIPIcs.APPROX/RANDOM.2020.33

    work page doi:10.4230/lipics.approx/random.2020.33 2020

  8. [7]

    Greedy is an almost optimal deque

    Parinya Chalermsook, Mayank Goswami, L \' a szl \' o Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. Greedy is an almost optimal deque. In WADS , volume 9214 of Lecture Notes in Computer Science , pages 152--165. Springer, 2015. https://doi.org/10.1007/978-3-319-21840-3_13 doi:10.1007/978-3-319-21840-3_13

    work page doi:10.1007/978-3-319-21840-3_13 2015

Show all 43 references
  1. [8]

    Pattern-avoiding access in binary search trees

    Parinya Chalermsook, Mayank Goswami, L \' a szl \' o Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. Pattern-avoiding access in binary search trees. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 1...

    2015 doi

  2. [9]

    The landscape of bounds for binary search trees

    Parinya Chalermsook, Mayank Goswami, L \'a szl \'o Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. The landscape of bounds for binary search trees. arXiv preprint arXiv:1603.04892 , 2016

    2016 arXiv

  3. [10]

    Improved pattern-avoidance bounds for greedy bsts via matrix decomposition

    Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Nidia Obscura Acosta, Akash Pareek, and Sorrachai Yingchareonthawornchai. Improved pattern-avoidance bounds for greedy bsts via matrix decomposition. In SODA , pages 509--534. SIAM , 2023. https://doi.org/10.1137/1.9781611...

    2023 doi

  4. [11]

    The group access bounds for binary search trees

    Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek, and Sorrachai Yingchareonthawornchai. The group access bounds for binary search trees. CoRR , abs/2312.15426, 2023. https://doi.org/10.48550/arXiv.2312.15426 doi:10.48550/arXiv.2312.15426

    2023 doi arXiv

  5. [12]

    New binary search tree bounds via geometric inversions

    Parinya Chalermsook and Wanchote Po Jiamjitrak. New binary search tree bounds via geometric inversions. In ESA , volume 173 of LIPIcs , pages 28:1--28:16. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2020. https://doi.org/10.4230/LIPIcs.ESA.2020.28 doi:10.4230/LIPIc...

    2020 doi

  6. [13]

    Sorting pattern-avoiding permutations via 0-1 matrices forbidding product patterns

    Parinya Chalermsook, Seth Pettie, and Sorrachai Yingchareonthawornchai. Sorting pattern-avoiding permutations via 0-1 matrices forbidding product patterns. In SODA , pages 133--149. SIAM , 2024. https://doi.org/10.1137/1.9781611977912.7 doi:10.1137/1.9781611977912.7

    2024 doi

  7. [14]

    On the dynamic finger conjecture for splay trees

    Richard Cole. On the dynamic finger conjecture for splay trees. part II: the proof. SIAM J. Comput. , 30(1):44--85, 2000. https://doi.org/10.1137/S009753979732699X doi:10.1137/S009753979732699X

    2000 doi

  8. [15]

    Demaine, Dion Harmon, John Iacono, Daniel M

    Erik D. Demaine, Dion Harmon, John Iacono, Daniel M. Kane, and Mihai Patrascu. The geometry of binary search trees. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009 , pages 496--505, 2009. URL: ht...

    2009

  9. [16]

    Demaine, Dion Harmon, John Iacono, and Mihai Patrascu

    Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Patrascu. Dynamic optimality - almost. SIAM J. Comput. , 37(1):240--251, 2007. https://doi.org/10.1137/S0097539705447347 doi:10.1137/S0097539705447347

    2007 doi

  10. [17]

    A lower bound framework for binary search trees with rotations

    Jonathan Derryberry, Daniel Dominic Sleator, and Chengwen Chris Wang. A lower bound framework for binary search trees with rotations. Technical report , 2005

    2005

  11. [18]

    On the sequential access theorem and deque conjecture for splay trees

    Amr Elmasry. On the sequential access theorem and deque conjecture for splay trees. Theor. Comput. Sci. , 314(3):459--466, 2004. https://doi.org/10.1016/j.tcs.2004.01.019 doi:10.1016/j.tcs.2004.01.019

    2004 doi

  12. [19]

    Upper bounds for maximally greedy binary search trees

    Kyle Fox. Upper bounds for maximally greedy binary search trees. In WADS , volume 6844 of Lecture Notes in Computer Science , pages 411--422. Springer, 2011. https://doi.org/10.1007/978-3-642-22300-6_35 doi:10.1007/978-3-642-22300-6_35

    2011 doi

  13. [20]

    On yao's xor-lemma

    Oded Goldreich, Noam Nisan, and Avi Wigderson. On yao's xor-lemma. In Oded Goldreich, editor, Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Gol...

    2011

  14. [21]

    Better analysis of greedy binary search tree on decomposable sequences

    Navin Goyal and Manoj Gupta. Better analysis of greedy binary search tree on decomposable sequences. Theor. Comput. Sci. , 776:19--42, 2019. https://doi.org/10.1016/j.tcs.2018.12.021 doi:10.1016/j.tcs.2018.12.021

    2019 doi

  15. [22]

    In pursuit of the dynamic optimality conjecture

    John Iacono. In pursuit of the dynamic optimality conjecture. In Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday , pages 236--250, 2013. https://doi.org/10.1007/978-3-642-40273-9\_16 doi:10.1007/97...

    2013 doi

  16. [23]

    Super-logarithmic depth lower bounds via the direct sum in communication complexity

    Mauricio Karchmer, Ran Raz, and Avi Wigderson. Super-logarithmic depth lower bounds via the direct sum in communication complexity. Comput. Complex. , 5(3/4):191--204, 1995. https://doi.org/10.1007/BF01206317 doi:10.1007/BF01206317

    1995 doi

  17. [24]

    Log-rank and lifting for and-functions

    Alexander Knop, Shachar Lovett, Sam McGuire, and Weiqiang Yuan. Log-rank and lifting for and-functions. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , page...

    2021

  18. [25]

    Binary search trees, rectangles and patterns

    L \'a szl \'o Kozma. Binary search trees, rectangles and patterns. 2016

    2016

  19. [26]

    Smooth heaps and a dual view of self-adjusting data structures

    L \' a szl \' o Kozma and Thatchaphol Saranurak. Smooth heaps and a dual view of self-adjusting data structures. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018 , pages 801--814, 2018. https://doi...

    2018

  20. [28]

    A direct product theorem for discrepancy

    Troy Lee, Adi Shraibman, and Robert Spalek. A direct product theorem for discrepancy. In CCC , pages 71--80. IEEE Computer Society, 2008. https://doi.org/10.1109/CCC.2008.25 doi:10.1109/CCC.2008.25

    2008 doi

  21. [29]

    Levy and Robert E

    Caleb C. Levy and Robert E. Tarjan. A new path from splay to dynamic optimality. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019 , pages 1311--1330. SIAM , 2019....

    2019 doi

  22. [30]

    Canonical forms for competitive binary search tree algorithms

    Joan Marie Lucas. Canonical forms for competitive binary search tree algorithms . Rutgers University, Department of Computer Science, Laboratory for Computer Science Research, 1988

    1988

  23. [31]

    Ian Munro

    J. Ian Munro. On the competitiveness of linear search. In Mike Paterson, editor, Algorithms - ESA 2000, 8th Annual European Symposium, Saarbr \" u cken, Germany, September 5-8, 2000, Proceedings , volume 1879 of Lecture Notes in Computer Science , pages 338--345. Springer, 200...

    2000 doi

  24. [32]

    Splay trees, davenport-schinzel sequences, and the deque conjecture

    Seth Pettie. Splay trees, davenport-schinzel sequences, and the deque conjecture. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms , pages 1115--1124, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347204

    2008

  25. [33]

    Higher lower bounds for near-neighbor and further rich problems

    Mihai P u a tra c s cu and Mikkel Thorup. Higher lower bounds for near-neighbor and further rich problems. SIAM J. Comput. , 39(2):730--741, 2009. https://doi.org/10.1137/070684859 doi:10.1137/070684859

    2009 doi

  26. [34]

    A counterexample to strong parallel repetition

    Ran Raz. A counterexample to strong parallel repetition. SIAM J. Comput. , 40(3):771--777, 2011. https://doi.org/10.1137/090747270 doi:10.1137/090747270

    2011 doi

  27. [35]

    Separation of the monotone NC hierarchy

    Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. Comb. , 19(3):403--435, 1999. https://doi.org/10.1007/s004930050062 doi:10.1007/s004930050062

    1999 doi

  28. [36]

    Dynamic binary search trees: Improved lower bounds for the greedy-future algorithm

    Yaniv Sadeh and Haim Kaplan. Dynamic binary search trees: Improved lower bounds for the greedy-future algorithm. In STACS , volume 254 of LIPIcs , pages 53:1--53:21. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2023. https://doi.org/10.4230/LIPIcs.STACS.2023.53 doi:...

    2023 doi

  29. [37]

    Towards proving strong direct product theorems

    Ronen Shaltiel. Towards proving strong direct product theorems. In Proceedings of the 16th Annual Conference on Computational Complexity , CCC '01, page 107, USA, 2001. IEEE Computer Society

    2001

  30. [38]

    Sherstov

    Alexander A. Sherstov. Strong direct product theorems for quantum communication and query complexity. SIAM J. Comput. , 41(5):1122--1165, 2012. https://doi.org/10.1137/110842661 doi:10.1137/110842661

    2012 doi

  31. [39]

    A counterexample to comon's conjecture

    Yaroslav Shitov. A counterexample to comon's conjecture. SIAM J. Appl. Algebra Geom. , 2(3):428--443, 2018. https://doi.org/10.1137/17M1131970 doi:10.1137/17M1131970

    2018 doi

  32. [40]

    Self-adjusting binary search trees

    Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. J. ACM , 32(3):652--686, jul 1985. URL: http://doi.acm.org/10.1145/3828.3835, https://doi.org/10.1145/3828.3835 doi:10.1145/3828.3835

    1985

  33. [41]

    On the deque conjecture for the splay algorithm

    Rajamani Sundar. On the deque conjecture for the splay algorithm. Comb. , 12(1):95--124, 1992. https://doi.org/10.1007/BF01191208 doi:10.1007/BF01191208

    1992 doi

  34. [42]

    O(log log n)-competitive dynamic binary search trees

    Chengwen Chris Wang, Jonathan Derryberry, and Daniel Dominic Sleator. O(log log n)-competitive dynamic binary search trees. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm , SODA '06, pages 374--383, Philadelphia, PA, USA, 2006. Society for In...

    2006

  35. [43]

    R. Wilber. Lower bounds for accessing binary search trees with rotations. SIAM J. Comput. , 18(1):56--67, feb 1989. URL: http://dx.doi.org/10.1137/0218004, https://doi.org/10.1137/0218004 doi:10.1137/0218004

    1989 doi

Pith tools

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