Pushing the Information-Theoretic Limits of Random Access Lists
summary
Provides a concrete improvement to Myers lists: a simple variant reduces pointer traversals from 3⌈lg n⌉−5 to 2⌈lg(n+1)⌉−3 and a more complex design uses skip layers and uncle pointers to reach (1+1/σ)⌊lg n⌋+σ+9 traversals for chosen σ, asymptotically approaching the information‑theoretic ⌈lg(n+1)⌉−1. The structure preserves O(1) cons/tail and two outgoing pointers per cell, relies on a tree view and recurrence analysis, and reports artifacts and proofs in the paper.
AI-written summary · about