LIPIcs.MFCS.2022.2.pdf
- Filesize: 0.49 MB
- 2 pages
Document
Modern Dynamic Data Structures (Invited Talk)
Author
Monika Henzinger 
-
Part of:
Volume:
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-08-22
File
Document Identifiers
Author Details
Cite AsGet BibTex
Monika Henzinger. Modern Dynamic Data Structures (Invited Talk). In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.2
https://doi.org/10.4230/LIPIcs.MFCS.2022.2
Abstract
We give an overview of differentially private dynamic data structure, aka differentially private algorithms under continual release.
Subject Classification
ACM Subject Classification
- Theory of computation → Design and analysis of algorithms
Keywords
- Differential privacy
- data structures
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur., 14(3):26:1-26:24, 2011. URL: https://doi.org/10.1145/2043621.2043626.
- Sergey Denisov, Brendan McMahan, Keith Rush, Adam Smith, and Abhradeep Thakurta. Improved differential privacy for sgd via optimal private linear operators on adaptive streams. arXiv preprint, 2022. URL: http://arxiv.org/abs/2202.08312.
-
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In TCC, pages 265-284, 2006.
-
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Proc. of the Forty-Second ACM Symp. on Theory of Computing (STOC'10), pages 715-724, 2010.
- Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211-407, 2014. URL: https://doi.org/10.1561/0400000042.
-
Hendrik Fichtenberger, Monika Henzinger, and Wolfgang Ost. Differentially private algorithms for graphs under continual observation. In 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), 2021.
- Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained complexity of differentially private continual observation using completely bounded norms. arXiv preprint, 2022. URL: http://arxiv.org/abs/2202.11205.
-
James Honaker. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London, UK, 2015.
- Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. The price of differential privacy under continual observation. arXiv preprint, 2021. URL: http://arxiv.org/abs/2112.00828.
- Shuang Song, Susan Little, Sanjay Mehta, Staal Vinterbo, and Kamalika Chaudhuri. Differentially private continual release of graph statistics. arXiv preprint, 2018. URL: http://arxiv.org/abs/1809.02575.