Theoretical computer science · data structures · online algorithms · binary search trees

Dynamic Optimality Conjecture for Splay Trees

Collaboration beta

Does the simple splay operation serve every binary-search-tree access sequence within a constant factor of the best offline rearrangement? A source-reported accounting reduction sharpens the open question but does not prove it.

{cost}_{splay} (X; T_{0}) \leq C {OPT}_{root} (X; T_{0}) + O (n)

Known results and sources

Dynamic optimality asks whether splaying always stays within a universal constant factor of the best offline BST execution from the same starting tree.

Research problem

Exact mathematical statement

Fix an initial binary search tree $T_0$ on ordered keys and an access sequence $X$ . Splay and an offline comparator start from the same $T_0$ . On each request the comparator touches the root-to-request path, may rearrange exactly those path keys into a legal BST rooted at the requested key, and must preserve every hanging component internally. If $\operatorname{OPT}_{\mathrm{root}}(X;T_0)$ is the minimum touched-node cost in that model, the question is whether a universal constant $C$ satisfies

\operatorname{cost}_{\mathrm{splay}}(X;T_0)\le C\,\operatorname{OPT}_{\mathrm{root}}(X;T_0)+O(n)

for every $n,T_0,X$ .

Problem infographic

Problem at a glance

A wordless landscape starts from one binary search tree and splits the same three access pulses into parallel cyan splay and gold offline-comparator histories, with violet hanging subtrees preserved and an open bracket leaving their accumulated touched-node costs unresolved. — Dynamic optimality compares two executions from the same initial tree: online splaying and the best legal offline touched-path rearrangements. Whether their total costs stay within a universal constant factor, up to a linear allowance, remains open.

Current mathematical picture

Where work on Dynamic Optimality Conjecture for Splay Trees stands

Open conjecture

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureUncompressed all-interval potential with a pointwise update bound

For the Section 3.1 odd-spine reversal family, the comparator path has length k while d_S(x) + Delta Phi = (k^2 + 3k)/2, giving quadratic rather than linear recharge. The source leaves open history-sensitive lifetime harvesting or ownership that prevents nested duplicate charges.

Route status · Narrowed route

Main reductionCorrected master inequality

After charging comparator-hit persistent ancestors directly, the source reports sum rho_t <= |A_0| + 2K + P_off.

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeConstruct a nonforking owner for off-path same-side scan occurrences.Task status · Ready to work on

Research-record correctionResearch-record correction

We corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Dynamic Optimality Conjecture for Splay Trees in numbers

929retained lines of mathematical investigation929 in the current working snapshot

Argument development: 745 · 80%
Explored or eliminated routes: 28 · 3%
Computational analysis: 25 · 3%
Open obligations: 49 · 5%
Definitions and setup: 82 · 9%

9selected mapped statements1routes investigated3open questions3contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byDaniel D. Sleator and Robert E. TarjanProposed1985Status checkedAug 13, 2026

Source recordedAug 13, 2026

Recommended next task

Construct a nonforking owner for off-path same-side scan occurrences.

Suggested move: Assign each monotone witness advance to an ordered gap or untouched-component boundary and prove that reserve moves through every legal comparator path rearrangement without being copied across nested tokens.

What would count as progress

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

13 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

1 recorded

Narrowed routeUncompressed all-interval potential with a pointwise update bound

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

3 featured tasks

Construct a nonforking owner for off-path same-side scan occurrences.Suggested move: Assign each monotone witness advance to an ordered gap or untouched-component boundary and prove that reserve moves through every legal comparator path rearrangement without being copied across nested tokens.

Ready to work on

Bound aggregate congestion of turn certificates.Suggested move: Map every off-path turn to its forced comparator edge crossing and prove a universal multiplicity bound over the laminar family of fixed token intervals.

Ready to work on

Audit the exact model, imported dependencies, and finite evidence independently.Suggested move: Supply an accepted sequential-access citation or proof, check the root-child case expansions and model conversion, and reproduce only the needed finite searches in a clean bounded implementation rather than executing submitted code.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 13, 2026

Current statusOpen conjecture

Open. The checked peer-reviewed literature describes dynamic optimality as unresolved and develops O(log log n)-competitive algorithms, stronger lower bounds, simulation embeddings, and group-access frameworks rather than a proof that splay trees are constant-competitive. The private 2026 source reports a corrected reduction but is not external evidence and does not change this status.

[5][8]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2025
Peer reviewedRysgaard and Wild's MFCS paper explicitly described dynamic optimality as still open for both Splay and GreedyBST while contrasting the question with other adaptive-search models.[8]
2024
Peer reviewedThe group-access framework gave stronger access bounds and an online simulation theorem, proposed as a route toward improved competitiveness for Splay and Greedy.[7]
2023
Peer reviewedChalermsook, Chuzhoy, and Saranurak proved large separations for Wilber-1-style bounds while describing dynamic optimality as wide open; Sadeh and Kaplan proved new lower bounds for the distinct Greedy Future candidate.[5][6]
2019
Peer reviewedLevy and Tarjan developed simulation embeddings and the subsequence-property route, explicitly presenting it as a program toward the still-open splay conjecture rather than a solution.[4]

Mathematical neighborhood

Related results and reusable starting points

Current focusDynamic Optimality Conjecture for splay trees

Weaker or relaxed formO(log log n)-competitive online binary search trees

Tango trees achieve O(log log n) competitiveness rather than the universal constant factor sought for splay trees; this is the benchmark upper bound reported in the checked literature.

[3][5]

Dependency or reductionWilber lower bounds for optimal BST cost

Wilber-style lower bounds are central comparators for dynamic BST algorithms, but the 2023 separation results show that several such bounds do not by themselves characterize the optimal cost within a constant factor.

[2][5]

Related problemGreedy BST and structural routes to dynamic optimality

Greedy Future or Geometric Greedy, simulation embeddings, and group-access bounds are related candidate algorithms and proof frameworks. Results for them do not automatically establish the splay-tree conjecture.

[4][6]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

Formalization targetA formal model of binary search trees, ordered keys, root-based access paths, rotations or touched-path rearrangements, and exact execution cost.
Formalization targetA checked equivalence between the current work's root-based rearrangement model and the literature convention used in any public theorem statement.
Formalization targetFormal proofs of token-birth localization, splay no-birth, the corrected master inequality, and fixed-component epoch accounting.
Formalization targetA formalized sequential-access theorem and the complete root-child case analysis if those source-reported results are retained.
Formalization targetA proved nonforking ownership or bounded-congestion theorem for off-path scans and turns.

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

5 standing statements4 proposed statements3 open questions1 narrowed routes

Statements by mathematical role9 selected mapped statements

theorem candidate1 of 91
reduction3 of 93
lemma3 of 93
equivalence1 of 91
negative result1 of 91

Selected mathematical clusters1 mathematical clusters

Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.23 displayed rows · 1 route included

retained route statementIs splaying universally constant-competitive with the best offline BST execution?
retained route statementCurrent reductionintermediate
retained route statementClosing targetintermediate
retained route statementExact touched-path modelintermediate
retained route statementBinary token localizationintermediate
retained route statementCorrected master inequalityintermediate
retained route statementRoot-child comparison subclassintermediate
retained route statementMinimal recycling targetintermediate
retained route statementStatic-potential barriersintermediate
Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
Useful failureUncompressed all-interval potential with a pointwise update boundreported failure
Research targetConstruct a nonforking owner for off-path same-side scan occurrences.open
Research targetBound aggregate congestion of turn certificates.open
Research targetAudit the exact model, imported dependencies, and finite evidence independently.open
ComputationThe source reports finite enumerations of small BSTs, legal path rearrangements, token births, local inequalities, and regression families.Those finite checks have not been independently reproduced and do not prove the global conjecture. · reported unreproduced
Narrowed routeUncompressed all-interval potential with a pointwise update boundFor the Section 3.1 odd-spine reversal family, the comparator path has length k while d_S(x) + Delta Phi = (k^2 + 3k)/2, giving quadratic rather than linear recharge. The source leaves open history-sensitive lifetime harvesting or ownership that prevents nested duplicate charges.

How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeConstruct a nonforking owner for off-path same-side scan occurrences.

1 approach has already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointConstruct a nonforking owner for off-path same-side scan occurrences.

Dynamic Optimality Conjecture for Splay Trees · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Exact question and boundaries
Current routes and known obstacles
What a useful result should report

Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data

Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references8 cited works · next context review by Nov 13, 2026

The mathematical context was checked on Aug 13, 2026. Status can be refreshed sooner after a material result or claim.

1
Self-Adjusting Binary Search Treesoriginal source · Daniel D. Sleator, Robert E. Tarjan · Journal of the Association for Computing Machinery · 1985 · accessed Aug 13, 2026
2
Lower Bounds for Accessing Binary Search Trees with Rotationspeer reviewed result · Robert Wilber · SIAM Journal on Computing · 1989 · DOI 10.1137/0218004 · accessed Aug 13, 2026
3
Dynamic Optimality—Almostpeer reviewed result · Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu · SIAM Journal on Computing · 2007 · DOI 10.1137/S0097539705447347 · accessed Aug 13, 2026
4
A New Path from Splay to Dynamic Optimalitypeer reviewed result · Caleb Levy, Robert E. Tarjan · Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms · 2019 · DOI 10.1137/1.9781611975482.80 · accessed Aug 13, 2026
5
Pinning Down the Strong Wilber-1 Bound for Binary Search Treespeer reviewed result · Parinya Chalermsook, Julia Chuzhoy, Thatchaphol Saranurak · Theory of Computing · 2023 · DOI 10.4086/toc.2023.v019a008 · accessed Aug 13, 2026
6
Dynamic Binary Search Trees: Improved Lower Bounds for the Greedy-Future Algorithmpeer reviewed result · Yaniv Sadeh, Haim Kaplan · 40th International Symposium on Theoretical Aspects of Computer Science · 2023 · ARXIV 2301.03084 · DOI 10.4230/LIPIcs.STACS.2023.53 · accessed Aug 13, 2026
7
The Group Access Bounds for Binary Search Treespeer reviewed result · Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek, Sorrachai Yingchareonthawornchai · 51st International Colloquium on Automata, Languages, and Programming · 2024 · DOI 10.4230/LIPIcs.ICALP.2024.38 · accessed Aug 13, 2026
8
Lazy B-Treespeer reviewed result · Casper Moldrup Rysgaard, Sebastian Wild · 50th International Symposium on Mathematical Foundations of Computer Science · 2025 · ARXIV 2507.00277 · DOI 10.4230/LIPIcs.MFCS.2025.87 · accessed Aug 13, 2026

Important qualifications

The pass checked the original splay-tree source and a bounded set of primary publisher or proceedings pages through 2025; it is not an exhaustive bibliography or priority review.
The exact root-based touched-path model in the private packet was not assumed to be identical to every BST model in the literature; a constant-factor model-equivalence audit remains necessary.
No source in the bounded pass established a proof or disproof of splay dynamic optimality. The submitted 2026 packet was not treated as external authority.
No problem-level proof-assistant formalization or public machine-checkable certificate was identified. This scoped negative search does not establish nonexistence.
The private submitted Python verifier was not run, linked, or used as external computation evidence.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces