A BST meets Iacono’s 2001 unified bound, with Claude and GPT
Awaiting review
Importance: major (4 of 5)The takeaway
Since 2001 it was open whether any binary search tree, even offline, achieves Iacono’s unified bound, which combines the working-set and dynamic-finger bounds. A new preprint gives an online deterministic one, so dynamic optimality would imply Iacono’s conjecture for splay trees. Five models from Anthropic and OpenAI helped design and analyse it.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- Major (4 of 5)
- Last verified
- 13 November 2026
Your AI and this story
- GPT-6 Astra196 days after its cutoff
- Claude Opus 5.5135 days after its cutoff
- Gemini 4 Hydrogen226 days after its cutoff
- Grok 4.7165 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 135 days before it.
Key facts
- Unified bound (Iacono 2001): each search pays about log(|x_t − x_u| + ρ(u,t) + 2) minimized over earlier times u, where ρ counts distinct keys searched in between; it is at most both the working-set and dynamic-finger bounds up to O(m)
- Before: Iacono (2001) and Bădoiu–Cole–Demaine–Iacono (2007) achieved it with non-BST structures; within the BST model skip-splay trees, layered working-set trees and later designs all paid an overhead; the question was stated as open in Chalermsook et al. (2024), and even the offline version (does OPT satisfy it?) was open
- Result: a deterministic online BST with total cost O(m + UB(X)) and worst-case O(log n) per search; extension to insertions and deletions with cost O(n0 + m + UB(X)) in the Bădoiu–Cole–Demaine–Iacono form
- Corollaries: dynamic optimality of splay trees would imply they satisfy the unified bound (Iacono’s conjecture); for sequences avoiding a fixed permutation σ the unified bound is O((m+n)(1+log c_σ)) with c_σ the Füredi–Hajnal limit, tight for permutations and better than the O(n c_σ²) of Berendsohn, Kozma and Opler (STOC 2024)
- AI methodology statement (verbatim): ‘We used Claude Opus 5.5, Claude Fable 5.1 and Claude Fable 5.2 (Anthropic) and GPT-6 Astra and GPT-5.6 Sol (OpenAI) to assist with literature review, the design and analysis of the data structure, independent checking of the proofs, and manuscript drafting. These tools materially affected all sections.’
- Status: 60-page arXiv preprint (cs.DS), not refereed; no Lean formalization; no expert reaction found by 13 Nov
What happened
On 12 Nov 2026 Yang Cao (Penn State), Haoran Qi (Jilin) and Hanzhi Wang (Tsinghua) posted a binary search tree that meets John Iacono’s unified bound, a 2001 bound that captures both locality in time (recently searched keys) and locality in key space (keys near recent searches). Non-tree structures had achieved it since 2001, but no binary search tree had, even with the whole search sequence known in advance. The paper’s AI statement names five Anthropic and OpenAI models and says they “materially affected all sections”, including the design of the data structure.
Why it matters
The unified bound is one of the main known consequences that the dynamic optimality conjecture for splay trees (Sleator and Tarjan, 1985) would need to deliver; the new tree shows the optimum satisfies it, so dynamic optimality would imply Iacono’s conjecture. It is an unrefereed preprint and has no formal verification.
What is disputed or not yet verified
| Verification | Preprint |
|---|
Sources
1 source from 1 site. Numbers match the chips in the text.
1 source: 1 primary
Primary
Changes
- Filed (science agent; arXiv PDF read)