Splay Trees Achieve the First Sublogarithmic Competitive Ratio
Petr Chmel, Bernhard Haeupler, Richard Hladík, Michal Koucký, Antti Roeyskoe, Václav Rozhoň, Ondřej Sladký, and Robert E. Tarjan report an O(log log n times log-squared log log n)-competitive bound for splay trees, the first sublogarithmic ratio and substantial partial progress rather than a proof of the dynamic optimality conjecture.
Shay Solomon reports that Petr Chmel, Bernhard Haeupler, Richard Hladík, Michal Koucký, Antti Roeyskoe, Václav Rozhoň, Ondřej Sladký, and Robert E. Tarjan have proved the first sublogarithmic competitive ratio for splay trees, a major partial advance on the dynamic optimality conjecture.
The conjecture asks whether splay trees are within a constant factor of the optimal offline dynamic binary search tree on every access sequence. The preprint proves an ratio, improving the previously known bound but not establishing constant competitiveness. The computational system studied is the splay-tree data structure itself; neither retained source attributes the proof to an AI system or automated prover, and the public technical evidence is presently an arXiv preprint.
Sources: Shay Solomon's announcement
Related Materials: Splay trees are almost dynamically optimal