You are here:
» Optimal oblivious priority queues
About Aarhus University
Optimal oblivious priority queues
Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
- Zahra Jafargholi ,
- Kasper Green Larsen
- Mark Simkin
In this work, we present the first asymptotically optimal oblivious priority queue, which matches the lower bound of Jacob, Larsen, and Nielsen (SODA'19). Our construction is conceptually simple and statistically secure. We illustrate the power of our optimal oblivious priority queue by presenting a conceptually equally simple construction of statistically secure offline ORAMs with O(log n) bandwidth overhead.
| Original language | English |
|---|---|
| Title of host publication | ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 |
| Editors | Daniel Marx |
| Number of pages | 18 |
| Publisher | Association for Computing Machinery |
| Publication year | 2021 |
| Pages | 2366-2383 |
| ISBN (Electronic) | 9781611976465 |
| Publication status | Published - 2021 |
| Event | 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States Duration: 10 Jan 2021 → 13 Jan 2021 |
Conference
| Conference | 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 |
|---|---|
| Land | United States |
| By | Alexandria, Virtual |
| Periode | 10/01/2021 → 13/01/2021 |
| Sponsor | ACM Special Interest Group on Algorithms and Computation Theory (SIGACT), SIAM Activity Group on Discrete Mathematics |
| Series | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
|---|
Bibliographical note
Publisher Copyright:
© 2021 by SIAM
See relations at Aarhus University Citationformats
ID: 229267164