A Binary Search Tree with the Unified Bound
Comments on “A Binary Search Tree with the Unified Bound”
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.
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
- 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).
| Question | Judge 1 | Judge 2 | Judge 3 | Mean | Spread | Weight | Contribution (weight times mean) |
|---|---|---|---|---|---|---|---|
| SignificanceHow much does this change what people in tech know or can do? | 0.66 | 0.72 | 0.88 | 0.75 | 0.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.31 | 0.78 | 0.90 | 0.66 | 0.59 , above the contested threshold | +0.26 | +0.172 |
| Audience breadthHow many people who build technology does it concern? | 0.45 | 0.40 | 0.32 | 0.39 | 0.13 | +0.13 | +0.051 |
| Practical relevanceHow useful is it to someone who builds software or tech products? | 0.29 | 0.30 | 0.55 | 0.38 | 0.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.90 | 0.85 | 0.82 | 0.86 | 0.08 | +0.05 | +0.043 |
| Technical depthHow technically substantive is it? | 0.90 | 0.90 | 0.98 | 0.93 | 0.08 | +0.05 | +0.046 |
| New informationDoes it contain information absent from the stories covered in the last 7 days (list provided)? | 0.91 | 0.95 | 0.98 | 0.95 | 0.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.05 | 0.02 | 0.01 | 0.03 | 0.04 | −0.19 | −0.005 |
| OverclaimDo the headline or conclusions claim more than the body supports? | 0.20 | 0.20 | 0.08 | 0.16 | 0.12 | −0.11 | −0.018 |
| Sum of contributions | +0.602 | ||||||
| Claim-check penalty | 0.000 | ||||||
| Total, as published | 0.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.
<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.
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.
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.
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.
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.
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.
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.
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.
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
Recorded for context only, checked 15 Nov 2026, 20:46 UTC. It played no part in the ranking.