Edition of Sunday 15 November 2026

A Binary Search Tree with the Unified Bound

Comments on “A Binary Search Tree with the Unified Bound”

  • Other
  • Paper

Claim-checked. Scored by all three judges, and its checkable claims were compared with the sources it cites. How far stories are checked

Yang Cao, Haoran Qi and Hanzhi Wang give a deterministic online binary search tree that serves m searches in O(m + UB(X)), where UB is Iacono's unified bound, and each search in O(log n). Earlier trees paid an extra m log log n, and none was known to meet the bound even offline. The tree keeps recently searched key blocks at power-of-two scales in a biased search tree. It also gives O((m+n)(1+log c_σ)) on pattern-avoiding sequences and handles insertions and deletions. The results are theoretical and unreviewed.

Read the original at arxiv.org. The judges saw only its text, with the site, the author and link domains removed; they are shown again after ranking.

Why it ranked

No. 20 of 62 with a score of 0.60. The panel rated it highest on new information (0.95) and technical depth (0.93), lowest on practical relevance (0.38). The judges disagreed most on reader interest (spread 0.59), so the story is marked contested. Placed No. 20, No. 35 by score alone: the placement terms moved other stories past it.

AI judgeJudge 2claude-haiku-5-5
Theoretical CS paper giving a BST meeting the unified bound, resolving a long-open question; strong proof-based substance, but narrow practical reach for builders.
AI judgeJudge 3gpt-5.6-luna
A substantial theoretical computer science result gives the first deterministic online BST achieving the unified bound, with detailed algorithms, proofs, extensions, and strong implications for dynamic optimality. Its relevance is deep but concentrated among algorithms and data-structure specialists.

Each judge wrote its line after answering the rubric, with the site and the author still hidden. Every answer behind this is in the table under Score.

Score

0.60total under rubric v2.3Contestedjudges differ by 0.59 on reader interest

Judges’ mean answer per question, on a scale from 0 to 1. Questions marked minus count against the score.
  • Significance0.75
  • Reader interest0.66
  • Audience breadth0.39
  • Practical relevance0.38
  • Substantiated0.86
  • Technical depth0.93
  • New information0.95
  • Counts against: Promotional0.03
  • Counts against: Overclaim0.16

Each judge’s answer per question (0–1), their mean and spread, and what the question adds to the score (weight × mean).

QuestionJudge 1Judge 2Judge 3MeanSpreadWeightContribution (weight times mean)
SignificanceHow much does this change what people in tech know or can do?0.660.720.880.750.22+0.24+0.181
Reader interestWould a well-informed senior engineer or tech founder want to read this today, and likely pass it on?0.310.780.900.660.59 , above the contested threshold+0.26+0.172
Audience breadthHow many people who build technology does it concern?0.450.400.320.390.13+0.13+0.051
Practical relevanceHow useful is it to someone who builds software or tech products?0.290.300.550.380.26+0.22+0.084
SubstantiatedHow well is it backed? Consider whether it is the primary source, and whether its main claims come with data, code, a demo, a reproducible method or citations.0.900.850.820.860.08+0.05+0.043
Technical depthHow technically substantive is it?0.900.900.980.930.08+0.05+0.046
New informationDoes it contain information absent from the stories covered in the last 7 days (list provided)?0.910.950.980.950.07+0.05+0.047
PromotionalIs it mainly marketing with little substance (a press release, ad or sponsored post with no real information)? A launch post that carries real news is not promotional.0.050.020.010.030.04−0.19−0.005
OverclaimDo the headline or conclusions claim more than the body supports?0.200.200.080.160.12−0.11−0.018
Sum of contributions+0.602
Claim-check penalty0.000
Total, as published0.602

Spread is the highest minus the lowest judge answer. marks a spread above 0.40: the judges disagree, and the story is marked contested.

The badge for this ranking, for the author's page or anyone's: one line of HTML, and it links back here.

Ranked #20 on Rubric, 15 Nov 2026
<a href="https://rubric.hrih.si/editions/2026-11-15/20/"><img src="https://rubric.hrih.si/badge/2026-11-15/20.svg" alt="Ranked #20 on Rubric, 15 Nov 2026" width="245" height="28"></a>

Claim check

Claim check: 8 no source given. Each claim is compared with the source the article itself cites; a flag is published only when both checkers agree.

  1. No source givenFirst, only or fastest

    The authors give a deterministic online BST that serves every sequence of m searches on n keys at total cost O(m+UB(X)), and every single search at cost O(log n).

    The article gives no link or citation for it.

    The article says

    “it serves every sequence $X$ of $m$ searches on $n$ keys at total cost $O(m+\mathrm{UB}(X))$ , and every single search at cost $O(\log n)$”

    The source says

    No source to compare with.

  2. No source givenFirst, only or fastest

    Previously, no BST was known to satisfy the unified bound, even offline.

    The article gives no link or citation for it.

    The article says

    “Previously, no BST was known to satisfy the unified bound, even offline”

    The source says

    No source to compare with.

  3. No source givenNumber

    The unified bound is O((m+n)(1+log c_sigma)) on every sequence of searches that avoids a fixed permutation sigma, where c_sigma is the Füredi–Hajnal limit.

    The article gives no link or citation for it.

    The article says

    “the unified bound is $O((m+n)(1+\log c_{\sigma}))$ on every sequence of searches that avoids a fixed permutation $\sigma$”

    The source says

    No source to compare with.

  4. No source givenNumber

    The new bound improves the previous upper bound O(n c_sigma^2) on the optimal cost for pattern-avoiding permutations, due to Berendsohn, Kozma and Opler.

    The article gives no link or citation for it.

    The article says

    “it improves the previous upper bound $O(nc_{\sigma}^{2})$ on the optimal cost, due to Berendsohn, Kozma and Opler [STOC 2024”

    The source says

    No source to compare with.

  5. No source givenCausal conclusion

    The dynamic optimality conjecture implies Iacono's conjecture that splay trees satisfy the unified bound.

    The article gives no link or citation for it.

    The article says

    “the dynamic optimality conjecture implies Iacono’s conjecture that splay trees satisfy the unified bound”

    The source says

    No source to compare with.

  6. No source givenNumber

    Before this work, the best bound for any online BST on all sigma-avoiding permutations was n·2^((1+o(1))α(n)) for fixed sigma, for Greedy.

    The article gives no link or citation for it.

    The article says

    “the best bound for any online BST on all $\sigma$ -avoiding permutations was $n\cdot 2^{(1+o(1))\alpha(n)}$ for fixed $\sigma$”

    The source says

    No source to compare with.

  7. No source givenNumber

    Previous BSTs for the unified bound (skip-splay trees, layered working-set trees with skip-splay, group-access trees) cost O(UB(X)+m log log n).

    The article gives no link or citation for it.

    The article says

    “cost $O(\mathrm{UB}(X)+m\log\log n)$ , with an additional $O(n\log n)$ in the case of [DILÖ13”

    The source says

    No source to compare with.

  8. No source givenQuote

    Derryberry's claim that the cache-splay tree achieves the unified bound was withdrawn.

    The article gives no link or citation for it.

    The article says

    “Demaine, Iacono, Langerman and Özkan reported that this claim was withdrawn”

    The source says

    No source to compare with.

Also covered by

No other coverage was clustered with this story.

Elsewhere

Elsewhere: HN 1 pts, not on front page

Discussion on Hacker News

Recorded for context only, checked 15 Nov 2026, 20:46 UTC. It played no part in the ranking.

Panel for this edition

Four AI agents ranked this edition: three judges scored every story blind to its site and author, and a fourth compared the top stories’ claims with the sources they cite. Summaries are written by AI.

Model versions are pinned for every edition. How ranking works describes rubric v2.3.

Comments

Readers’ comments on this story have a page of their own, ranked by a public rubric rather than by votes.

Comments on “A Binary Search Tree with the Unified Bound”

More on Rubric

From the last 7 editions, chosen by shared topic, score and date.