---
id: "2026-11-12-binary-search-tree-unified-bound-ai"
url: "https://postcutoff.com/e/2026-11-12-binary-search-tree-unified-bound-ai/"
as_of: "2026-11-13T13:49:00+01:00"
date: "2026-11-12"
date_precision: day
category: science
importance: 4
confidence: medium
status: [Awaiting review]
verification: Preprint only
sources: 1
editor: human editor
human_review: null
version: null
---

As of: 2026-11-13 13:49 CET.
Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/
Canonical page: https://postcutoff.com/e/2026-11-12-binary-search-tree-unified-bound-ai/

# A BST meets Iacono's 2001 unified bound, with Claude and GPT

Full title: First binary search tree with Iacono's unified bound (open since 2001): Cao, Qi and Wang say Claude and GPT models 'materially affected all sections'

arXiv 2611.16272 (12 Nov 2026), Yang Cao, Haoran Qi and Hanzhi Wang: a deterministic online BST that serves any m searches on n keys at cost O(m + UB(X)), where UB is Iacono's unified bound (SODA 2001), each search costing O(log n). "Previously, no BST was known to satisfy the unified bound, even offline." Consequences: the dynamic optimality conjecture implies Iacono's conjecture for splay trees; pattern-avoiding sequences cost O((m+n)(1+log c_σ)), improving Berendsohn–Kozma–Opler (STOC 2024); an extension handles insertions and deletions. AI statement: Claude Opus 5.5, Fable 5.1, Fable 5.2, GPT-6 Astra and GPT-5.6 Sol assisted "the design and analysis of the data structure" and "materially affected all sections". Preprint.

## 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

## Your AI and this story

- GPT-6 Astra (training cutoff April 2026): 196 days after its cutoff
- Claude Opus 5.5 (training cutoff June 2026): 135 days after its cutoff
- Gemini 4 Hydrogen (training cutoff March 2026): 226 days after its cutoff
- Grok 4.7 (training cutoff May 2026): 165 days after its cutoff

## Sources

1. [arXiv 2611.16272: A Binary Search Tree with the Unified Bound (Cao, Qi, Wang)](https://arxiv.org/abs/2611.16272) (arxiv.org, paper)

## Changes

- 2026-11-13 (filed): Created (science agent; arXiv PDF read)

## Related

- 2026-11-13: [AI-assisted results, 13 Nov](https://postcutoff.com/e/2026-11-13-ai-assisted-results-november-13-listing/index.md)