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.