arXiv preprint ·
Differentially Oblivious Priority Queues with Sublogarithmic Cost
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In this paper, we study exact online integer priority queues under differential obliviousness in the balls-and-bins model. Given a public upper bound $T$ on the number of operations and assuming that the priorities are bounded by a polynomial in $T$, we construct an $(\eps,δ)$-differentially oblivious priority queue supporting insertion and minimum extraction, which requires $\polylog(T)$ private memory. For constant $\varepsilon>0$ and $δ=\exp(-Θ(\log^2 T))$, our construction incurs $O(\log T/\log\log T)$ expected amortized total work per operation, which breaks the $Ω(\log T)$ barrier for fully oblivious priority queues~[Jacob et al., SODA'2019]. Further, we prove a matching lower bound for $(\eps,δ)$-differentially oblivious priority queues with $\varepsilon=O(1)$ and $δ=o(1)$, which indicates that our construction is asymptotically optimal in terms of total work.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Semidirect sums of tensors and the matrix multiplication exponent
Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities
State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron
Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product Bounds
Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion Constraints
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.