[{"date_updated":"2025-10-27T08:00:13Z","intvolume":"       351","type":"conference","citation":{"chicago":"Henzinger, Monika, and Roodabeh Safavi Hemami. “Securing Dynamic Data: A Primer on Differentially Private Data Structures.” In <i>33rd Annual European Symposium on Algorithms</i>, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.2\">https://doi.org/10.4230/LIPIcs.ESA.2025.2</a>.","ama":"Henzinger M, Safavi Hemami R. Securing dynamic data: A primer on differentially private data structures. In: <i>33rd Annual European Symposium on Algorithms</i>. Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.2\">10.4230/LIPIcs.ESA.2025.2</a>","apa":"Henzinger, M., &#38; Safavi Hemami, R. (2025). Securing dynamic data: A primer on differentially private data structures. In <i>33rd Annual European Symposium on Algorithms</i> (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.2\">https://doi.org/10.4230/LIPIcs.ESA.2025.2</a>","ista":"Henzinger M, Safavi Hemami R. 2025. Securing dynamic data: A primer on differentially private data structures. 33rd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 351, 2.","mla":"Henzinger, Monika, and Roodabeh Safavi Hemami. “Securing Dynamic Data: A Primer on Differentially Private Data Structures.” <i>33rd Annual European Symposium on Algorithms</i>, vol. 351, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.2\">10.4230/LIPIcs.ESA.2025.2</a>.","ieee":"M. Henzinger and R. Safavi Hemami, “Securing dynamic data: A primer on differentially private data structures,” in <i>33rd Annual European Symposium on Algorithms</i>, Warsaw, Poland, 2025, vol. 351.","short":"M. Henzinger, R. Safavi Hemami, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025."},"article_processing_charge":"No","OA_type":"gold","language":[{"iso":"eng"}],"publication_status":"published","date_published":"2025-10-01T00:00:00Z","date_created":"2025-10-26T23:01:34Z","year":"2025","_id":"20533","license":"https://creativecommons.org/licenses/by/4.0/","department":[{"_id":"MoHe"}],"file_date_updated":"2025-10-27T07:57:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"content_type":"application/pdf","creator":"dernst","access_level":"open_access","file_name":"2025_LIPIcs.ESA_Henzinger.pdf","relation":"main_file","file_size":770227,"date_updated":"2025-10-27T07:57:00Z","file_id":"20541","success":1,"date_created":"2025-10-27T07:57:00Z","checksum":"094e0466d90664fbea397b469a60acbb"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773959"]},"title":"Securing dynamic data: A primer on differentially private data structures","has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"quality_controlled":"1","ddc":["000"],"OA_place":"publisher","article_number":"2","abstract":[{"lang":"eng","text":"We give an introduction into differential privacy in the dynamic setting, called the continual observation setting."}],"conference":{"start_date":"2025-09-15","name":"ESA: European Symposium on Algorithms","location":"Warsaw, Poland","end_date":"2025-09-17"},"status":"public","alternative_title":["LIPIcs"],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication":"33rd Annual European Symposium on Algorithms","oa":1,"day":"01","month":"10","author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","first_name":"Roodabeh","last_name":"Safavi Hemami","full_name":"Safavi Hemami, Roodabeh"}],"doi":"10.4230/LIPIcs.ESA.2025.2","corr_author":"1","oa_version":"Published Version","volume":351,"scopus_import":"1"},{"department":[{"_id":"MoHe"}],"file_date_updated":"2025-10-27T08:03:36Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["2509.05157"]},"file":[{"relation":"main_file","file_name":"2025_LIPIcs.ESA_HenzingerM.pdf","file_size":934846,"content_type":"application/pdf","access_level":"open_access","creator":"dernst","file_id":"20542","success":1,"date_created":"2025-10-27T08:03:36Z","checksum":"d2daf9a467e96fb5e7084a8a85321776","date_updated":"2025-10-27T08:03:36Z"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773959"]},"title":"Efficient contractions of dynamic graphs - with applications","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","type":"conference","intvolume":"       351","date_updated":"2025-10-27T08:05:46Z","acknowledgement":"Monika Henzinger and Evangelos Kosinas: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant https://www.doi.org/10.55776/Z422 and grant https://www.doi.org/10.55776/I5982. Harald Räcke and Robin Münk: This project has received funding from the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 498605858.","publication_status":"published","language":[{"iso":"eng"}],"article_processing_charge":"No","OA_type":"gold","citation":{"mla":"Henzinger, Monika, et al. “Efficient Contractions of Dynamic Graphs - with Applications.” <i>33rd Annual European Symposium on Algorithms</i>, vol. 351, 36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.36\">10.4230/LIPIcs.ESA.2025.36</a>.","ista":"Henzinger M, Kosinas E, Münk R, Räcke H. 2025. Efficient contractions of dynamic graphs - with applications. 33rd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms vol. 351, 36.","apa":"Henzinger, M., Kosinas, E., Münk, R., &#38; Räcke, H. (2025). Efficient contractions of dynamic graphs - with applications. In <i>33rd Annual European Symposium on Algorithms</i> (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.36\">https://doi.org/10.4230/LIPIcs.ESA.2025.36</a>","ama":"Henzinger M, Kosinas E, Münk R, Räcke H. Efficient contractions of dynamic graphs - with applications. In: <i>33rd Annual European Symposium on Algorithms</i>. Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.36\">10.4230/LIPIcs.ESA.2025.36</a>","chicago":"Henzinger, Monika, Evangelos Kosinas, Robin Münk, and Harald Räcke. “Efficient Contractions of Dynamic Graphs - with Applications.” In <i>33rd Annual European Symposium on Algorithms</i>, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.36\">https://doi.org/10.4230/LIPIcs.ESA.2025.36</a>.","ieee":"M. Henzinger, E. Kosinas, R. Münk, and H. Räcke, “Efficient contractions of dynamic graphs - with applications,” in <i>33rd Annual European Symposium on Algorithms</i>, Warsaw, Poland, 2025, vol. 351.","short":"M. Henzinger, E. Kosinas, R. Münk, H. Räcke, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025."},"date_created":"2025-10-26T23:01:34Z","year":"2025","date_published":"2025-10-01T00:00:00Z","_id":"20534","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"oa":1,"day":"01","publication":"33rd Annual European Symposium on Algorithms","month":"10","author":[{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"},{"first_name":"Evangelos","id":"4c7f9625-dbbc-11ee-9d86-bdcc2db5a949","last_name":"Kosinas","full_name":"Kosinas, Evangelos"},{"first_name":"Robin","last_name":"Münk","full_name":"Münk, Robin"},{"first_name":"Harald","last_name":"Räcke","full_name":"Räcke, Harald"}],"doi":"10.4230/LIPIcs.ESA.2025.36","oa_version":"Published Version","corr_author":"1","volume":351,"scopus_import":"1","project":[{"name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020","grant_number":"101019564"},{"grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"quality_controlled":"1","ddc":["000"],"ec_funded":1,"OA_place":"publisher","article_number":"36","abstract":[{"text":"A non-trivial minimum cut (NMC) sparsifier is a multigraph Ĝ that preserves all non-trivial minimum cuts of a given undirected graph G. We introduce a flexible data structure for fully dynamic graphs that can efficiently provide an NMC sparsifier upon request at any point during the sequence of updates. We employ simple dynamic forest data structures to achieve a fast from-scratch construction of the sparsifier at query time. Based on the strength of the adversary and desired type of time bounds, the data structure comes with different guarantees. Specifically, let G be a fully dynamic simple graph with n vertices and minimum degree δ. Then our data structure supports an insertion/deletion of an edge to/from G in n^o(1) worst-case time. Furthermore, upon request, it can return w.h.p. an NMC sparsifier of G that has O(n/δ) vertices and O(n) edges, in Ô(n) time. The probabilistic guarantees hold against an adaptive adversary. Alternatively, the update and query times can be improved to Õ(1) and Õ(n) respectively, if amortized-time guarantees are sufficient, or if the adversary is oblivious. Throughout the paper, we use Õ to hide polylogarithmic factors and Ô to hide subpolynomial (i.e., n^o(1)) factors.\r\nWe discuss two applications of our new data structure. First, it can be used to efficiently report a cactus representation of all minimum cuts of a fully dynamic simple graph. Building this cactus for the NMC sparsifier instead of the original graph allows for a construction time that is sublinear in the number of edges. Against an adaptive adversary, we can with high probability output the cactus representation in worst-case Ô(n) time. Second, our data structure allows us to efficiently compute the maximal k-edge-connected subgraphs of undirected simple graphs, by repeatedly applying a minimum cut algorithm on the NMC sparsifier. Specifically, we can compute with high probability the maximal k-edge-connected subgraphs of a simple graph with n vertices and m edges in Õ(m+n²/k) time. This improves the best known time bounds for k = Ω(n^{1/8}) and naturally extends to the case of fully dynamic graphs.","lang":"eng"}],"status":"public","conference":{"start_date":"2025-09-15","name":"ESA: European Symposium on Algorithms","end_date":"2025-09-17","location":"Warsaw, Poland"}},{"oa":1,"day":"01","publication":"33rd Annual European Symposium on Algorithms","arxiv":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","alternative_title":["LIPIcs"],"volume":351,"scopus_import":"1","project":[{"grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020"},{"name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422"},{"grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions"}],"oa_version":"Published Version","corr_author":"1","doi":"10.4230/LIPIcs.ESA.2025.91","author":[{"full_name":"Dhulipala, Laxman","last_name":"Dhulipala","first_name":"Laxman"},{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"full_name":"Li, George Z.","last_name":"Li","first_name":"George Z."},{"last_name":"Liu","first_name":"Quanquan C.","full_name":"Liu, Quanquan C."},{"full_name":"Sricharan, A. R.","last_name":"Sricharan","first_name":"A. R."},{"id":"a2117c59-cee4-11ed-b9d0-874ecf0f8ac5","first_name":"Leqi","last_name":"Zhu","full_name":"Zhu, Leqi"}],"month":"10","ec_funded":1,"OA_place":"publisher","ddc":["000"],"quality_controlled":"1","status":"public","conference":{"name":"ESA: European Symposium on Algorithms","start_date":"2025-09-15","end_date":"2025-09-17","location":"Warsaw, Poland"},"article_number":"91","abstract":[{"text":"Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the k-core decomposition problem, the classic peeling algorithm iteratively removes a vertex if its induced degree falls below a threshold. The sparse vector technique (SVT) is generally used to transform non-private threshold queries into private ones with only a small additive loss in accuracy. However, a naive application of SVT in the graph setting leads to an amplification of the error by a factor of n due to composition, as SVT is applied to every vertex. In this paper, we resolve this problem by formulating a novel generalized sparse vector technique which we call the Multidimensional AboveThreshold (MAT) Mechanism which generalizes SVT (applied to vectors with one dimension) to vectors with multiple dimensions. When applied to vectors with n dimensions, we solve a number of important graph problems with better bounds than previous work.\r\nSpecifically, we apply our MAT mechanism to obtain a set of improved bounds for a variety of problems including k-core decomposition, densest subgraph, low out-degree ordering, and vertex coloring. We give a tight local edge differentially private (LEDP) algorithm for k-core decomposition that results in an approximation with O(ε^{-1} log n) additive error and no multiplicative error in O(n) rounds. We also give a new (2+η)-factor multiplicative, O(ε^{-1} log n) additive error algorithm in O(log² n) rounds for any constant η > 0. Both of these results are asymptotically tight against our new lower bound of Ω(log n) for any constant-factor approximation algorithm for k-core decomposition. Our new algorithms for k-core decomposition also directly lead to new algorithms for the related problems of densest subgraph and low out-degree ordering. Finally, we give novel LEDP differentially private defective coloring algorithms that use number of colors given in terms of the arboricity of the graph.","lang":"eng"}],"file":[{"date_updated":"2025-10-27T06:58:43Z","checksum":"19146e935b5b6ad5d33c8d08280ad8e7","date_created":"2025-10-27T06:58:43Z","file_id":"20539","success":1,"creator":"dernst","access_level":"open_access","content_type":"application/pdf","file_size":870317,"file_name":"2025_LIPIcs.ESA_Dhulipala.pdf","relation":"main_file"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["2508.02182"]},"department":[{"_id":"MoHe"}],"file_date_updated":"2025-10-27T06:58:43Z","has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"title":"Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism","publication_identifier":{"isbn":["9783959773959"],"issn":["1868-8969"]},"year":"2025","date_created":"2025-10-26T23:01:35Z","date_published":"2025-10-01T00:00:00Z","publication_status":"published","article_processing_charge":"No","citation":{"ieee":"L. Dhulipala, M. Henzinger, G. Z. Li, Q. C. Liu, A. R. Sricharan, and L. Zhu, “Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism,” in <i>33rd Annual European Symposium on Algorithms</i>, Warsaw, Poland, 2025, vol. 351.","short":"L. Dhulipala, M. Henzinger, G.Z. Li, Q.C. Liu, A.R. Sricharan, L. Zhu, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","apa":"Dhulipala, L., Henzinger, M., Li, G. Z., Liu, Q. C., Sricharan, A. R., &#38; Zhu, L. (2025). Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism. In <i>33rd Annual European Symposium on Algorithms</i> (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.91\">https://doi.org/10.4230/LIPIcs.ESA.2025.91</a>","ama":"Dhulipala L, Henzinger M, Li GZ, Liu QC, Sricharan AR, Zhu L. Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism. In: <i>33rd Annual European Symposium on Algorithms</i>. Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.91\">10.4230/LIPIcs.ESA.2025.91</a>","chicago":"Dhulipala, Laxman, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, and Leqi Zhu. “Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism.” In <i>33rd Annual European Symposium on Algorithms</i>, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.91\">https://doi.org/10.4230/LIPIcs.ESA.2025.91</a>.","mla":"Dhulipala, Laxman, et al. “Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism.” <i>33rd Annual European Symposium on Algorithms</i>, vol. 351, 91, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.91\">10.4230/LIPIcs.ESA.2025.91</a>.","ista":"Dhulipala L, Henzinger M, Li GZ, Liu QC, Sricharan AR, Zhu L. 2025. Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism. 33rd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 351, 91."},"OA_type":"gold","language":[{"iso":"eng"}],"acknowledgement":"Monika Henzinger and A. R. Sricharan: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation\r\nprogramme (MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant DOI\r\n10.55776/Z422 and grant DOI 10.55776/I5982. Laxman Dhulipala and George Z. Li: supported by NSF award number CNS-2317194. Quanquan C. Liu: supported by a Google Academic Research Award and by an NSF award number CCF-2453323.","type":"conference","intvolume":"       351","date_updated":"2025-10-27T07:02:06Z","_id":"20535"}]