Pith. sign in

REVIEW 2 major objections 4 minor 2 cited by

Dynamic Optimality Refuted -- For Tournament Heaps

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Tournament heaps with any number of fingers have competitive ratio Ω(√log n) for modify-key sequences, refuting dynamic optimality for this model.

desk verdict A worthwhile separation result for tournament heaps, but Lemma 3.3 has a real gap in its visited-region argument that must be patched before the few-fingers lower bound holds. read the letter →

arxiv 1908.00563 v1 pith:M6LZMORP submitted 2019-08-01 cs.DS

J. Ian Munro , Richard Peng , Sebastian Wild , Lingyi Zhang This is my paper · ORCID
classification cs.DS
keywords heapsaccessfingersbinarymodificationstournamenttreescompetitive
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

Tournament heaps are binary trees where the keys live in the leaves and every internal node stores the smaller of its two children. To change a key, you walk from that leaf to the root and update the minimums along the way. This paper asks whether an online version of such a heap, one that discovers requests one at a time, can match a clairvoyant offline version that knows the whole request sequence in advance.

The model gives both versions a number k of 'fingers', pointers that can move around the tree, swap subtrees, or stitch pieces together. The main finding is a separation: there are request sequences where every online strategy pays at least roughly the square root of log n times more than an offline strategy, regardless of how many fingers are allowed. The lower bound comes from two regimes. With few fingers, a counting argument plus an adversarial-permutation lemma forces online cost about log n / log k per access while an offline algorithm serves the sequence in constant amortized time. With many fingers, a permutation can be served offline in about log_k n per access, but any online algorithm still must pay about log n for many accesses, giving a gap of about log k. Balancing these two gives the square root of log n.

The paper also supplies an offline algorithm that groups keys into buckets based on how soon they will be requested again. It serves any sequence with amortized cost O(log_k n + 2^{lg* n}) per access, which is close to the information-theoretic optimum. This shows the gap is real: offline strategies genuinely exploit the rearrangement power of tournament heaps.

Extended reading notes

Core claim

Theorem 1.2: For any value k = k(n), the competitive ratio of tournament heaps with k fingers is Ω(max{log_k(n), log k}) = Ω(√log n). If true, no online tournament heap, regardless of finger count, is dynamically optimal for modify-key sequences.

Load-bearing premise

The proof of the few-fingers lower bound depends on Lemma 3.2, the existence of an adversarial permutation, which is only sketched. Its small-tree reduction (Lemma 3.3) bounds the visited region as the union of 2k connected components, but fingers can jump via copy/move operations (Definition 1.1, items 2 and 3) multiple times within one execution, so the written justification is incomplete. If this lemma fails, the Ω(log n / log k) bound and hence the combined Ω(√log n) lower bound would collapse.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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 studies tournament-tree heaps, binary trees whose leaves store keys and whose internal nodes track subtree minima, in a pointer-machine model with k fingers. The main claim is a sharp separation between online and offline algorithms: Theorem 1.2 asserts that for every k, any online tournament heap has competitive ratio Ω(max{log_k n, log k}) = Ω(√log n) on modify-key/access sequences, and Theorem 1.3 gives an offline algorithm with k transient fingers achieving amortized cost O(log_k n + 2^{lg^* n}). The lower bound is built from an information-theoretic counting bound (Theorem 3.1), a Fredman-style adversarial-permutation argument for few fingers (Lemma 3.2 and Corollary 3.4), and an order-by-next argument for many fingers (Corollary 3.6). The offline upper bound is a bucketing scheme by recurrence time with iterated-logarithm recursion over bucket trees.

Significance. If the claimed separation is correct, it is a substantial contribution: it refutes dynamic optimality in a natural heap model with tunable rearrangement power, shows that fingers are strictly more powerful than static servers, and provides an efficiently computable offline algorithm that beats the online average case. The paper has several genuine strengths: Theorem 3.1 is a clean counting lower bound; the permutation subroutine of Lemma 3.5 is an elegant use of k-way mergesort with fingers; and the bucketed order-by-next algorithm of Section 4 is a nontrivial construction with no fitted parameters. The significance is, however, conditional: the few-fingers lower bound rests on Lemma 3.3, whose proof is incomplete, and the many-fingers lower bound of Corollary 3.6 is asserted rather than proved. These are load-bearing gaps in the main negative result, though both appear repairable.

major comments (2)
  1. [Section 3.2, Lemma 3.3] The small-tree reduction is not established. The proof claims that the region visited by one execution is the union of k connected subtrees, one per finger, 'before potentially jumping,' but operations 2 and 3 of Definition 1.1 allow a finger to copy the location of F0 and move to it repeatedly, so a single finger can visit many disconnected components within one access. The visited region therefore need not be the union of only k components. The subsequent step of arbitrarily connecting components into T' is also unjustified, because operation 5 requires the replaced child pointer to be null, and the arbitrary attachments may consume exactly the null slots on which S1 and S2 rely. Since Lemma 3.3 supplies the bound on the number of witness trees used in the counting argument of Lemma 3.2, the Ω(log n / log k) bound of Corollary 3.4 is not proven as written. The claim may be salvageable by counting distinct finger positions rather than connected regions, but the present proof is incomplete at a load-bearing point.
  2. [Section 3.3, Corollary 3.6] The large-k lower bound is asserted rather than proved. The sentence 'Since we always start at the root, in any tree with n nodes, there is a node whose cost is at least Ω(log n)' only states that some deep node exists at each time; it does not give an adversary argument showing that an online algorithm with k transient fingers can be forced to pay Ω(log n) on every access of a single sequence. The proof also invokes Lemma 3.7, which is a statement about persistent fingers, while the corollary concerns transient fingers, and it does not specify the hard access sequence for which the offline optimum is O(log_k n) per access. Because Corollary 3.6 supplies the Ω(log k) half of Theorem 1.2 for large k, the 'any number of fingers' claim is incomplete.
minor comments (4)
  1. [Section 4, Algorithm 1, step 3b] The bucket index is off by one relative to the definition of B_j: buckets are defined by B_j = [2^{j-1}, 2^j), so a recurrence time of 1 should map to B_1, but the pseudocode sets j = floor(lg r), which gives j = 0 for r = 1. The index formula should be floor(lg r) + 1, or the interval definition should be shifted.
  2. [Section 3.2, proof of Corollary 3.4] The offline argument says that after transforming the tree, 'all future accesses can then be served by simply rotating one edge at the root each,' but the model of Definition 1.1 has no rotation operation; the intended simulation with swaps and detaches should be spelled out.
  3. [Section 3.2, proof of Lemma 3.2] The final inequality is printed as 'lg W(t) < b!', but the preceding line gives lg W(t) < (1-ε)b lg b, and the intended conclusion is W(t) < b! (equivalently, lg W(t) < lg(b!)); the printed form is dimensionally wrong and should be corrected.
  4. [Section 3.3, Lemma 3.5] The proof sketch relies on finding edge separators that break the tree into k pieces of size O(n/k) and then recursing, but no implementation details are given for how these separators are found and how the pieces are reattached using the operations of Definition 1.1. A more formal description would strengthen the paper, since this lemma is used in both the offline upper bound and the many-fingers lower bound.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the lower and upper bounds are derived from counting arguments and self-contained algorithms; the self-citation to Munro ESA 2000 is motivational only.

full rationale

The paper's central claims are derived by self-contained combinatorial arguments, not by importing the conclusions. Theorem 1.2 follows from Corollary 3.4 (few fingers) and Corollary 3.6 (many fingers). Corollary 3.4 is based on Lemma 3.2, whose proof is a counting argument over witness quadruples (T,I,S1,S2) bounded by Lemma 3.3; Lemma 3.3 is proved by restricting to the visited region of the two operation sequences. Even if that proof has a correctness gap (the visited region need not be a union of k connected subtrees because fingers can jump and copy repeatedly), the claim is not assumed anywhere; it is an independent structural assertion. Corollary 3.6 follows from Lemma 3.5 (k-way mergesort rearrangement) and Lemma 3.7 (ball-counting in a binary tree). The offline algorithm of Theorem 4.1 is fully specified in Algorithm 1 and verified by the invariant Lemma 4.2; its sorting subroutine Lemma 3.5 is proved by a recurrence. The citations to Martínez-Roura and Munro (ESA 2000) appear in the abstract and related work as motivation for 'order-by-next' bucketing, but the actual bucket algorithm and its analysis do not rely on any result from those papers; in particular, the self-citation [30] is not load-bearing. There is no fitted parameter renamed as a prediction, no self-citation chain invoked to force a unique choice, and no result that reduces by definition to its input.

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

No free parameters are fitted; the paper is purely analytic. The assumptions are model definitions and algorithmic claims whose proofs are sketched in the text. No new physical or formal entities are introduced beyond the finger model already defined in Section 1.

assumptions (5)
  • domain assumption The tournament-tree model with k fingers (Definition 1.1) faithfully represents the cost of modify-key operations, with propagation to the root.
    Section 1 assumes worst-case propagation to the root; the model charges one per finger operation and requires an access to touch the root-to-leaf path.
  • domain assumption The initial tree is fixed and identical for online and offline algorithms.
    Used in Theorem 3.1 counting argument and in the competitive ratio definitions; standard in competitive analysis.
  • domain assumption Transient fingers reset after each access while persistent fingers persist.
    Definition 2.1; the offline algorithm uses transient fingers, the lower bounds allow persistent fingers, and the separation is robust to this choice.
  • domain assumption The rearrangement subroutine in Lemma 3.5 sorts elements by next-request time in O(n log_k n) operations using k fingers.
    The proof sketches a k-way mergesort on a tournament tree; this bound is load-bearing for the many-fingers offline upper bound and the Ω(log k) lower bound.
  • standard math Standard counting arguments for binary trees and permutations.
    Used in Theorem 3.1 and Lemma 3.2, e.g., the number of binary trees on 2t nodes is at most 4^{2t}.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Dynamic Optimality Refuted -- For Tournament Heaps." pith.science (2026). https://pith.science/paper/M6LZMORP

@misc{pith2026190800563,
  author       = {Pith},
  title        = {Pith review of: Dynamic Optimality Refuted -- For Tournament Heaps},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/M6LZMORP}},
  note         = {Machine review of arXiv:1908.00563}
}
abstract

We prove a separation between offline and online algorithms for finger-based tournament heaps undergoing key modifications. These heaps are implemented by binary trees with keys stored on leaves, and intermediate nodes tracking the min of their respective subtrees. They represent a natural starting point for studying self-adjusting heaps due to the need to access the root-to-leaf path upon modifications. We combine previous studies on the competitive ratios of unordered binary search trees by [Fredman WADS2011] and on order-by-next request by [Mart\'inez-Roura TCS2000] and [Munro ESA2000] to show that for any number of fingers, tournament heaps cannot handle a sequence of modify-key operations with competitive ratio in $o(\sqrt{\log{n}})$. Critical to this analysis is the characterization of the modifications that a heap can undergo upon an access. There are $\exp(\Theta(n \log{n}))$ valid heaps on $n$ keys, but only $\exp(\Theta(n))$ binary search trees. We parameterize the modification power through the well-studied concept of fingers: additional pointers the data structure can manipulate arbitrarily. Here we demonstrate that fingers can be significantly more powerful than servers moving on a static tree by showing that access to $k$ fingers allow an offline algorithm to handle any access sequence with amortized cost $O(\log_{k}(n) + 2^{\lg^{*}n})$.

Figures

Figures reproduced from arXiv: 1908.00563 by the authors.

Figure 1
Figure 1. The first step of the transformation, from path to row-major ordered matrix. The shaded nodes each consist of one or two internal nodes and a leaf with the stored key. 2. Next, extract out all the is for which we have to apply π to obtain Ci . We refer this subset as bI. In the tree, we rearrange the path containing the heads of the Bis so that all bI-blocks appears as a prefix; see [PITH_FULL_IMAGE:figures/full_fi… view at source ↗
Figure 2
Figure 2. Step 2 of the transformation: separating permuted and non-permuted blocks. In the example, the indices of permuted blocks is Ib= {2, 3, 5, . . .}. 3. Now we “transpose” this prefix into a “column-major” ordering: there is a path starting from the root containing all values of 1 ≤ j ≤ b, and all elements of the form [ib + j] for i ∈ bI are attached to j in a path; see [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Step 3 of the transformation: transposing the Ib rows. The transposed part is highlighted; the other blocks remain unchanged. 4. Now we apply π to the b first path heads, thereby applying π in parallel to all blocks in bI. The important observation is that it is the same permutation π that has to be applied to all paths, so we can do it in one shot after the above preparation. An arbitrary permutation of b nodes can… view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Step 4 of the transformation: Applying π in parallel to all Ib-blocks. This step only affects the first b paths; the other blocks remain unchanged. Lemma 3.5 (Permute): Using the operations given in Definition 1.1 on k fingers, any tourna￾ment tree on n keys can be rea…
Figure 5
Figure 5. Figure 5: Note that in terms of its interface to other buckets [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]
Figure 5
Figure 5. Figure 5: Sketch of representation of our (conceptual) buckets in the tournament tree, showing the queue and the two buffers. To the outside, the buckets look like a binary-tree node and can hence be arranged as a binary tree themselves. The shaded nodes each consist of one or t…
Figure 6
Figure 6. Figure 6: Illustration of a refresh operation with p = 2 steps. The picture shows the ranges of valid next-access times for elements in the sorted queue and buffers of Bj before and after the refresh; dots indicate times at which Bj is touched. Note that Bj cannot have been touc…
Figure 7
Figure 7. Figure 7: Transformation from standard BSTs to leaf-oriented trees (for a node with nonempty subtrees). When L and/or R are empty, special rules apply: If x is a leaf (both L and R are empty), it is mapped to a leaf with key x. If x is a unary node, it is mapped to a single inte…
Figure 8
Figure 8. Figure 8: Transformation from leaf-oriented trees to standard BSTs. x is the leftmost leaf in the right subtree of the root, which is removed from the recursive call s(R). Lemma B.2: Let V ′ j be any top-subtree in T ′ , containing the set of (leaves with) keys Kj . Then, there …

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Heaps and Their Working Sets

    cs.DS 2026-07 accept novelty 7.0 of 10

    Almost all heap working-set bounds are amortized-equivalent; a new recursive construction achieves the stronger stack-like bound with O(1) decrease-key and o(log* n) insert.

  2. Top-Down Mergesort with Sorted Check Has Mergecost $\le(\mathcal H+3)n$

    cs.DS 2026-08 conditional novelty 5.0 of 10

    Top-down Mergesort with a sorted check before each merge has merge cost M ≤ (H+3)n for any input, where H is the run-length entropy.

Reference graph

Works this paper leans on

37 extracted references · 22 canonical work pages · cited by 2 Pith papers

  1. [1]

    A polylogarithmic- competitive algorithm for the k-server problem

    Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Jo seph Naor. A polylogarithmic- competitive algorithm for the k-server problem. J. ACM , 62(5):40:1–40:49, 2015. doi:10.1145/2783434

    doi:10.1145/2783434 2015

  2. [2]

    Online computation and competitive analysis

    Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis . Cambridge University Press, 2005

    2005

  3. [3]

    Dyn amic optimality for skip lists and B-trees

    Prosenjit Bose, Karim Douïeb, and Stefan Langerman. Dyn amic optimality for skip lists and B-trees. In Symposium on Discrete Algorithms SODA 2008 , pages 1106–1114. SIAM, 2008. References 21

    work page 2008

  4. [4]

    Cohen, Yin Tat Lee, James R

    Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and Aleksander Madry. k- server via multiscale entropic regularization. In Symposium on Theory of Computing STOC 2018, pages 3–16, 2018. doi:10.1145/3188745.3188798

    arXiv 2018

  5. [5]

    Pattern-avoiding access in binary search trees

    Parinya Chalermsook, Mayank Goswami, László Kozma, Kur t Mehlhorn, and Thatchaphol Saranurak. Pattern-avoiding access in binary search trees . In Symposium on Foundations of Computer Science, FOCS 2015 , pages 410–423, 2015. doi:10.1109/FOCS.2015.32

    doi:10.1109/focs.2015.32 2015

  6. [6]

    Cohen, Rasmus Kyng, Gary L

    Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pa chocki, Richard Peng, Anup Rao, and Shen Chen Xu. Solving SDD linear systems in nearly m log1/2 n time. In Symposium on Theory of Computing STOC 2014 , pages 343–352, 2014

    work page 2014

  7. [7]

    Demaine, Dion Harmon, John Iacono, Daniel Kane, a nd Mihai Pˇ atraşcu

    Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, a nd Mihai Pˇ atraşcu. The geometry of binary search trees. In Symposium on Discrete Algorithms SODA 2009 , pages 496–505. SIAM, 2009

    work page 2009

  8. [8]

    Demaine, Dion Harmon, John Iacono, and Mihai Pˇ at raşcu

    Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Pˇ at raşcu. Dynamic optimality— almost. SIAM Journal on Computing , 37(1):240–251, January 2007. (see also FOCS 2004). doi:10.1137/s0097539705447347

    doi:10.1137/s0097539705447347 2007

Show all 37 references
  1. [9]

    Demaine, John Iacono, Stefan Langerman, and Özgü r Özkan

    Erik D. Demaine, John Iacono, Stefan Langerman, and Özgü r Özkan. Combining binary search trees. In International Colloquium on Automata, Languages, and Prog ramming ICALP 2013 , pages 388–399, 2013. doi:10.1007/978-3-642-39206-1_33

    2013 doi

  2. [10]

    Non-blocking binary search trees

    Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Fra nck van Breugel. Non-blocking binary search trees. In Symposium on Principles of distributed computing PODC 2010 . ACM Press,

    2010

  3. [11]

    Offline algorithms for dynamic minimum s panning tree problems

    David Eppstein. Offline algorithms for dynamic minimum s panning tree problems. Journal of Algorithms , 17(2):237–250, 1994

    1994

  4. [12]

    Michael L. Fredman. A priority queue transform. In Vitt er J.S. and Zaroliagis C.D., editors, International Workshop on Algorithm Engineering W AE 1999, pages 243–257. Springer, 1999. doi:10.1007/3-540-48318-7_20

    1999 doi

  5. [13]

    Michael L. Fredman. On the matter of dynamic optimality in an extended model for tree access operations. In International Symposium on Algorithms and Data Structures W ADS 2011, pages 423–437. Springer, 2011. doi:10.1007/978-3-642-22300-6_36

    2011 doi

  6. [14]

    Michael L. Fredman. Generalizing a theorem of Wilber on rotations in binary search trees to encompass unordered binary trees. Algorithmica, 62(3-4):863–878, April 2012. doi:10.1007/s00453-011-9489-2

    2012 doi

  7. [15]

    New bounds on optimal binary search trees

    Dion Harmon. New bounds on optimal binary search trees . PhD thesis, Massachusetts Institute of Technology, 2006

    2006

  8. [16]

    Introduction to online convex optimizatio n

    Elad Hazan. Introduction to online convex optimizatio n. Foundations and Trends in Opti- mization, 2(3-4):157–325, 2016. doi:10.1561/2400000013 . 22 References

    2016 doi

  9. [17]

    Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spann ing tree, 2-edge, and biconnectiv- ity

    Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup . Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spann ing tree, 2-edge, and biconnectiv- ity. Journal of the ACM , 48(4):723–760, 2001. (See also STOC 1998)

    2001

  10. [18]

    Key-independent optimality

    John Iacono. Key-independent optimality. Algorithmica, 42(1):3–10, February 2005. (see also ISAAC 2002). doi:10.1007/s00453-004-1136-8

    2005 doi

  11. [19]

    In pursuit of the dynamic optimality conje cture

    John Iacono. In pursuit of the dynamic optimality conje cture. In Brodnik A., López-Ortiz A., Raman V., and Viola A., editors, Space-Efficient Data Structures, Streams, and Algorithms , pages 236–250. Springer, 2013. doi:10.1007/978-3-642-40273-9_16

    2013 doi

  12. [20]

    Weighted dynamic fing er in binary search trees

    John Iacono and Stefan Langerman. Weighted dynamic fing er in binary search trees. In Symposium on Discrete Algorithms (SODA) 2016 , pages 672–691, Philadelphia, PA, January

    2016

  13. [21]

    Kelner, Lorenzo Orecchia, Aaron Sidford, a nd Zeyuan Allen Zhu

    Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, a nd Zeyuan Allen Zhu. A simple, combinatorial algorithm for solving SDD systems in nearly- linear time. In Symposium on theory of computing STOC 2013 , pages 911–920, New York, NY, USA, 2013. ACM

    2013

  14. [22]

    The art of computer programming, Volume III

    Donald Ervin Knuth. The art of computer programming, Volume III . Addison-Wesley, 2nd edition, 1998

    1998

  15. [23]

    Binary search trees, rectangles and patterns

    László Kozma. Binary search trees, rectangles and patterns . Dissertation (PhD thesis), Universität des Saarlandes, 2016. doi:10.22028/d291-26671

    2016 doi

  16. [24]

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

    László Kozma and Thatchaphol Saranurak. Smooth heaps a nd a dual view of self-adjusting data structures. In Symposium on Theory of Computation STOC 2018 . ACM Press, 2018. doi:10.1145/3188745.3188864

    2018

  17. [25]

    James R. Lee. Fusible HSTs and the randomized k-server c onjecture. In Symposium on Foundations of Computer Science FOCS 2018 . IEEE, October 2018. doi:10.1109/focs.2018.00049

    2018

  18. [26]

    A new path from splay to dyn amic optimality

    Caleb Levy and Robert Tarjan. A new path from splay to dyn amic optimality. In Symposium on Discrete Algorithms SODA 2019 , pages 1311–1330. SIAM, 2019. doi:10.1137/1.9781611975482.80

    2019 doi

  19. [27]

    Joan M. Lucas. Canonical forms for competitive binary s earch tree algorithms. Technical Report DCS-TR-250, Rutgers University, 1988

    1988

  20. [28]

    Com petitive algorithms for server problems

    Mark S Manasse, Lyle A McGeoch, and Daniel D Sleator. Com petitive algorithms for server problems. Journal of Algorithms , 11(2):208–230, 1990

    1990

  21. [29]

    On the competitiv eness of the move-to-front rule

    Conrado Martínez and Salvador Roura. On the competitiv eness of the move-to-front rule. Theoretical Computer Science , 242(1-2):313–325, July 2000. doi:10.1016/s0304-3975(98)00264-3

    doi

  22. [30]

    Ian Munro

    J. Ian Munro. On the competitiveness of linear search. I n ESA 2000, pages 338–345. Springer,

    2000

  23. [31]

    Offline dynamic higher connec- tivity, 2017

    Richard Peng, Bryce Sandlund, and Daniel Dominic Sleat or. Offline dynamic higher connec- tivity, 2017. arXiv:1708.03812 . A. Offline Algorithms Are Boring With Random Access 23

    2017 arXiv

  24. [32]

    Self-a djusting binary search trees

    Daniel Dominic Sleator and Robert Endre Tarjan. Self-a djusting binary search trees. Journal of the ACM , 32(3):652–686, July 1985. doi:10.1145/3828.3835

    1985

  25. [33]

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

    Chengwen Chris Wang, Jonathan Derryberry, and Daniel D ominic Sleator. O(log log n)- competitive dynamic binary search trees. In Symposium on Discrete algorithms (SODA) 2006, pages 374–383. Society for Industrial and Applied Mathema tics, 2006

    2006

  26. [34]

    Lower bounds for accessing binary searc h trees with rotations

    Robert Wilber. Lower bounds for accessing binary searc h trees with rotations. SIAM Journal on Computing , 18(1):56–67, February 1989. doi:10.1137/0218004 . A. Offline Algorithms Are Boring With Random Access As a side comment, we will consider the power of offline algorit hms whe...

    1989 doi

  27. [2000]

    doi:10.1007/3-540-45253-2_31

    doi

  28. [2010]

    doi:10.1145/1835698.1835736

  29. [2016]

    doi:10.1137/1.9781611974331.ch49

    SIAM. doi:10.1137/1.9781611974331.ch49

    doi

Pith tools

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