Reproduce “Differentially Oblivious Priority Queues with Sublogarithmic Cost” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Zimai Guo, Cheng Hong, Zhechen Li
The authors present an exact priority queue that inserts records and extracts the minimum while protecting access patterns with differential obliviousness. For polynomially bounded integer priorities, constant ε, and δ=exp(−Θ(log² T)), it uses polylogarithmic private memory and achieves O(log T/log log T) expected amortized total word-RAM work per operation. A probe lower bound applies to exact opaque-payload queues with polylogarithmic private space.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.