[{"author":[{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"last_name":"Safavi Hemami","full_name":"Safavi Hemami, Roodabeh","first_name":"Roodabeh","id":"72ed2640-8972-11ed-ae7b-f9c81ec75154"},{"full_name":"Vadhan, Salil","first_name":"Salil","last_name":"Vadhan"}],"article_processing_charge":"Yes","issue":"2","OA_type":"gold","volume":4,"project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422","name":"Efficient algorithms"}],"publisher":"Association for Computing Machinery","year":"2026","das_tickbox":"0","has_accepted_license":"1","keyword":["differential privacy","concurrent composition","continual release","continual observation","data streaming","continual mechanisms","concurrent parallel composition","concurrent filter composition"],"language":[{"iso":"eng"}],"title":"Concurrent composition for differentially private continual mechanisms","month":"06","researchdata_availability":"no","status":"public","doi":"10.1145/3801895","department":[{"_id":"MoHe"}],"quality_controlled":"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"},"corr_author":"1","citation":{"mla":"Henzinger, Monika, et al. “Concurrent Composition for Differentially Private Continual Mechanisms.” <i>Proceedings of the ACM on Management of Data</i>, vol. 4, no. 2, Association for Computing Machinery, 2026, pp. 1–26, doi:<a href=\"https://doi.org/10.1145/3801895\">10.1145/3801895</a>.","chicago":"Henzinger, Monika, Roodabeh Safavi Hemami, and Salil Vadhan. “Concurrent Composition for Differentially Private Continual Mechanisms.” <i>Proceedings of the ACM on Management of Data</i>. Association for Computing Machinery, 2026. <a href=\"https://doi.org/10.1145/3801895\">https://doi.org/10.1145/3801895</a>.","ista":"Henzinger M, Safavi Hemami R, Vadhan S. 2026. Concurrent composition for differentially private continual mechanisms. Proceedings of the ACM on Management of Data. 4(2), 1–26.","ieee":"M. Henzinger, R. Safavi Hemami, and S. Vadhan, “Concurrent composition for differentially private continual mechanisms,” <i>Proceedings of the ACM on Management of Data</i>, vol. 4, no. 2. Association for Computing Machinery, pp. 1–26, 2026.","apa":"Henzinger, M., Safavi Hemami, R., &#38; Vadhan, S. (2026). Concurrent composition for differentially private continual mechanisms. <i>Proceedings of the ACM on Management of Data</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3801895\">https://doi.org/10.1145/3801895</a>","ama":"Henzinger M, Safavi Hemami R, Vadhan S. Concurrent composition for differentially private continual mechanisms. <i>Proceedings of the ACM on Management of Data</i>. 2026;4(2):1-26. doi:<a href=\"https://doi.org/10.1145/3801895\">10.1145/3801895</a>","short":"M. Henzinger, R. Safavi Hemami, S. Vadhan, Proceedings of the ACM on Management of Data 4 (2026) 1–26."},"intvolume":"         4","publication":"Proceedings of the ACM on Management of Data","publication_status":"published","OA_place":"publisher","page":"1-26","type":"journal_article","oa":1,"date_published":"2026-06-01T00:00:00Z","date_updated":"2026-07-16T09:14:49Z","file":[{"date_created":"2026-07-16T09:09:53Z","relation":"main_file","file_name":"2026_ACMMgmtData_Henzinger.pdf","access_level":"open_access","checksum":"c6c5e256d02b90682c0690c3bee94040","file_size":655405,"creator":"dernst","content_type":"application/pdf","date_updated":"2026-07-16T09:09:53Z","success":1,"file_id":"22345"}],"file_date_updated":"2026-07-16T09:09:53Z","_id":"22318","ec_funded":1,"acknowledgement":"1Salil Vadhan was supported by NSF grant BCS-2218803, a grant from the Sloan Foundation, and\r\na Simons Investigator Award. Work began while a Visiting Researcher at the Bocconi University\r\nDepartment of Computing Sciences, supported by Luca Trevisan’s ERC Project GA-834861.\r\n2Monika Henzinger and Roodabeh Safavi were supported by the European Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation programme (Grant agreement\r\nNo. 101019564), and the Austrian Science Fund (FWF) under grants DOI 10.55776/Z422, DOI\r\n10.55776/I5982, and DOI 10.55776/P33775. For open access purposes, the author has applied a CC BY\r\npublic copyright license to any author-accepted manuscript version arising from this submission.\r\nViews and opinions expressed are however those of the author(s)\r\nonly and do not necessarily reflect those of the European Union\r\nor the European Research Council Executive Agency. Neither the\r\nEuropean Union nor the granting authority can be held responsible for them.","scopus_import":"1","PlanS_conform":"1","oa_version":"Published Version","arxiv":1,"publication_identifier":{"issn":["2836-6573"]},"day":"01","date_created":"2026-07-13T14:59:14Z","external_id":{"arxiv":["2411.03299"]},"ddc":["000"],"abstract":[{"text":"Many intended uses of differential privacy involve a continual mechanism that is set up to run continuously\r\nover a long period of time, making more statistical releases as either queries come in or the dataset is updated.\r\nIn this paper, we give the first general treatment of privacy against adaptive adversaries for mechanisms that\r\nsupport dataset updates and a variety of queries, all arbitrarily interleaved. It also models a very general notion\r\nof neighboring, that includes both event-level and user-level privacy. We prove several concurrent composition\r\ntheorems for continual mechanisms, which ensure privacy even when an adversary can interleave its queries\r\nand dataset updates to the different composed mechanisms. Previous concurrent composition theorems for\r\ndifferential privacy were only for the case when the dataset is static, with no adaptive updates. We also give\r\nthe first interactive and continual generalizations of the “parallel composition theorem” for noninteractive\r\ndifferential privacy. Specifically, we show that the analogue of the noninteractive parallel composition theorem\r\nholds if either there are no adaptive dataset updates or each of the composed mechanisms satisfies pure\r\ndifferential privacy, but it fails to hold for composing approximately differentially private mechanisms with\r\ndataset updates. Thus, we prove a tight new composition theorem for this case. In addition, we prove concurrent\r\nfilter compositions theorems for the scenarios in which the privacy parameters are adaptively chosen. We\r\nextend these results to other measures of differential privacy, including Rényi DP and 𝑓 -DP.\r\nWe then formalize a set of general conditions on a continual mechanism M that runs multiple continual submechanisms such that the privacy guarantees of M follow directly using the above concurrent composition\r\ntheorems on the sub-mechanisms, without further privacy loss. This enables us to give a simpler and modular\r\nprivacy analysis of a recent continual histogram mechanism of Henzinger, Sricharan, and Steiner. In the\r\ncase of approximate DP, ours is the first proof that shows that its privacy holds against adaptive adversaries.\r\nWe also provide a framework that simplifies the analysis of local differential privacy when the protocol\r\nincludes multi-round server-user interactions. Using this result, we simplify the privacy analysis of the core\r\ndecomposition protocol of Dhulipala, Henzinger, Li, Liu, Sricharan, and Zhu [5].","lang":"eng"}],"supplementarymaterial":"no","article_type":"original","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"article_processing_charge":"No","author":[{"first_name":"Gramoz","full_name":"Goranci, Gramoz","last_name":"Goranci"},{"last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Räcke","first_name":"Harald","full_name":"Räcke, Harald"},{"first_name":"A.","full_name":"Sricharan, A.","last_name":"Sricharan"}],"OA_type":"gold","year":"2025","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"name":"Efficient algorithms","grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982"},{"name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"volume":334,"department":[{"_id":"MoHe"}],"doi":"10.4230/lipics.icalp.2025.91","status":"public","month":"06","language":[{"iso":"eng"}],"title":"Incremental approximate maximum flow via residual graph sparsification","has_accepted_license":"1","alternative_title":["LIPIcs"],"intvolume":"       334","citation":{"mla":"Goranci, Gramoz, et al. “Incremental Approximate Maximum Flow via Residual Graph Sparsification.” <i>52nd International Colloquium on Automata, Languages, and Programming</i>, vol. 334, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 91:1-91:20, doi:<a href=\"https://doi.org/10.4230/lipics.icalp.2025.91\">10.4230/lipics.icalp.2025.91</a>.","ista":"Goranci G, Henzinger M, Räcke H, Sricharan A. 2025. Incremental approximate maximum flow via residual graph sparsification. 52nd International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 334, 91:1-91:20.","apa":"Goranci, G., Henzinger, M., Räcke, H., &#38; Sricharan, A. (2025). Incremental approximate maximum flow via residual graph sparsification. In <i>52nd International Colloquium on Automata, Languages, and Programming</i> (Vol. 334, p. 91:1-91:20). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/lipics.icalp.2025.91\">https://doi.org/10.4230/lipics.icalp.2025.91</a>","ieee":"G. Goranci, M. Henzinger, H. Räcke, and A. Sricharan, “Incremental approximate maximum flow via residual graph sparsification,” in <i>52nd International Colloquium on Automata, Languages, and Programming</i>, Aarhus, Denmark, 2025, vol. 334, p. 91:1-91:20.","chicago":"Goranci, Gramoz, Monika Henzinger, Harald Räcke, and A. Sricharan. “Incremental Approximate Maximum Flow via Residual Graph Sparsification.” In <i>52nd International Colloquium on Automata, Languages, and Programming</i>, 334:91:1-91:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/lipics.icalp.2025.91\">https://doi.org/10.4230/lipics.icalp.2025.91</a>.","short":"G. Goranci, M. Henzinger, H. Räcke, A. Sricharan, in:, 52nd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 91:1-91:20.","ama":"Goranci G, Henzinger M, Räcke H, Sricharan A. Incremental approximate maximum flow via residual graph sparsification. In: <i>52nd International Colloquium on Automata, Languages, and Programming</i>. Vol 334. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025:91:1-91:20. doi:<a href=\"https://doi.org/10.4230/lipics.icalp.2025.91\">10.4230/lipics.icalp.2025.91</a>"},"corr_author":"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"},"conference":{"start_date":"2025-07-08","location":"Aarhus, Denmark","end_date":"2025-07-11","name":"ICALP: Automata, Languages and Programming"},"quality_controlled":"1","date_published":"2025-06-30T00:00:00Z","oa":1,"page":"91:1-91:20","type":"conference","OA_place":"publisher","publication_status":"published","publication":"52nd International Colloquium on Automata, Languages, and Programming","scopus_import":"1","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, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024. Harald Räcke: This project has received funding from the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 498605858 and 470029389.","ec_funded":1,"_id":"21280","date_updated":"2026-02-18T09:06:12Z","file_date_updated":"2026-02-18T09:02:33Z","file":[{"access_level":"open_access","checksum":"c178cf554e44204b9f64ebd9b54cf7ba","file_name":"2025_ICALP_Goranci.pdf","relation":"main_file","date_created":"2026-02-18T09:02:33Z","file_id":"21315","success":1,"content_type":"application/pdf","date_updated":"2026-02-18T09:02:33Z","creator":"dernst","file_size":944824}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We give an algorithm that, with high probability, maintains a (1-ε)-approximate s-t maximum flow in undirected, uncapacitated n-vertex graphs undergoing m edge insertions in Õ(m+ n F^*/ε) total update time, where F^{*} is the maximum flow on the final graph. This is the first algorithm to achieve polylogarithmic amortized update time for dense graphs (m = Ω(n²)), and more generally, for graphs where F^* = Õ(m/n). At the heart of our incremental algorithm is the residual graph sparsification technique of Karger and Levine [SICOMP '15], originally designed for computing exact maximum flows in the static setting. Our main contributions are (i) showing how to maintain such sparsifiers for approximate maximum flows in the incremental setting and (ii) generalizing the cut sparsification framework of Fung et al. [SICOMP '19] from undirected graphs to balanced directed graphs."}],"ddc":["000"],"external_id":{"arxiv":["2502.09105"]},"date_created":"2026-02-17T08:26:06Z","day":"30","publication_identifier":{"isbn":["9783959773720"]},"arxiv":1,"oa_version":"Published Version"},{"conference":{"name":"SODA: Symposium on Discrete Algorithms","start_date":"2025-01-12","location":"New Orleans, LA, United States","end_date":"2025-01-15"},"quality_controlled":"1","citation":{"ama":"Henzinger M, Upadhyay J. Improved differentially private continual observation using group algebra. In: <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 5. Association for Computing Machinery; 2025:2951-2970. doi:<a href=\"https://doi.org/10.1137/1.9781611978322.95\">10.1137/1.9781611978322.95</a>","short":"M. Henzinger, J. Upadhyay, in:, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, 2025, pp. 2951–2970.","chicago":"Henzinger, Monika, and Jalaj Upadhyay. “Improved Differentially Private Continual Observation Using Group Algebra.” In <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 5:2951–70. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1137/1.9781611978322.95\">https://doi.org/10.1137/1.9781611978322.95</a>.","ieee":"M. Henzinger and J. Upadhyay, “Improved differentially private continual observation using group algebra,” in <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, New Orleans, LA, United States, 2025, vol. 5, pp. 2951–2970.","apa":"Henzinger, M., &#38; Upadhyay, J. (2025). Improved differentially private continual observation using group algebra. In <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 5, pp. 2951–2970). New Orleans, LA, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1137/1.9781611978322.95\">https://doi.org/10.1137/1.9781611978322.95</a>","ista":"Henzinger M, Upadhyay J. 2025. Improved differentially private continual observation using group algebra. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 5, 2951–2970.","mla":"Henzinger, Monika, and Jalaj Upadhyay. “Improved Differentially Private Continual Observation Using Group Algebra.” <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 5, Association for Computing Machinery, 2025, pp. 2951–70, doi:<a href=\"https://doi.org/10.1137/1.9781611978322.95\">10.1137/1.9781611978322.95</a>."},"intvolume":"         5","publication":"Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms","publication_status":"published","OA_place":"repository","page":"2951 - 2970","type":"conference","oa":1,"date_published":"2025-01-20T00:00:00Z","date_updated":"2025-04-14T13:50:49Z","_id":"19038","ec_funded":1,"acknowledgement":"Monika Henzinger: This project has received funding from the European Research Council(ERC) under the European Union’s Horizon 2020 research and innovation programme (Grantagreement No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422,grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCEStiftung, 2020–2024.Jalaj Upadhyay’s research was funded by the Rutgers Decanal Grant no. 302918 and an unrestricted giftfrom Google. This work was done in part while visiting the Institute of Science and Technology Austria (ISTA).The authors would like to thank Sarvagya Upadhyay for the initial discussion and feedback on the early draft of the paper. The authors would like to thank the anonymous reviewers, Brendan McMahan and Abhradeep Thakurta for the discussions that helped improve the presentation of the final version of the paper.","scopus_import":"1","arxiv":1,"oa_version":"Preprint","publication_identifier":{"isbn":["979-833131200-8"],"issn":["1071-9040"]},"day":"20","external_id":{"arxiv":["2412.02840"]},"date_created":"2025-02-17T09:31:03Z","abstract":[{"lang":"eng","text":"Differentially private weighted prefix sum under continual observation is a crucial component in the production-level deployment of private next-word prediction for Gboard, which, according to Google, has over a billion users. More specifically, Google uses a differentially private mechanism to sum weighted gradients in its private follow-the-regularized leader algorithm. Apart from efficiency, the additive error of the private mechanism is crucial as multiplied with the square root of the model’s dimension d (with d ranging up to 10 trillion, for example, Switch Transformers or M6-10T), it determines the accuracy of the learning system. So, any improvement in leading constant matters significantly in practice. In this paper, we show a novel connection between mechanisms for continual weighted prefix sum and a concept in representation theory known as the group matrix introduced in correspondence between Dedekind and Frobenius (Sitzungsber. Preuss. Akad. Wiss. Berlin, 1897) and generalized by Schur (Journal für die reine und angewandte Mathematik, 1904). To the best of our knowledge, this is the first application of group algebra in the analysis of differentially private algorithms. Using this connection, we analyze a class of matrix norms known as factorization norms that give upper and lower bounds for the additive error under general ℓp-norms of the matrix mechanism. This allows us to give 1. the first efficient factorization that matches the best-known non-constructive upper bound on the factorization norm by Mathias (SIAM Journal of Matrix Analysis and Applications, 1993) for the matrix used in Google’s deployment, and also improves on the previous best-known constructive bound of Fichtenberger, Henzinger, and Upadhyay (ICML 2023) and Henzinger, Upadhyay, and Upadhyay (SODA 2023); thereby, partially resolving an open question in operator theory, 2. the first upper bound on the additive error for a large class of weight functions for weighted prefix sum problems, including the sliding window matrix (Bolot, Fawaz, Muthukrishnan, Nikolov, and Taft (ICDT 2013). We also improve the bound on factorizing the striped matrix used for outputting a synthetic graph that approximates all cuts (Fichtenberger, Henzinger, and Upadhyay (ICML 2023)); 3. a general improved upper bound on the factorization norms that depend on algebraic properties of the weighted sum matrices and that applies to a more general class of weighting functions than the ones considered in Henzinger, Upadhyay, and Upadhyay (SODA 2024). Using the known connection between these factorization norms and the ℓp-error of continual weighted sum, we give an upper bound on the ℓp-error for the continual weighted sum problem for p ≥ 2."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Upadhyay","full_name":"Upadhyay, Jalaj","first_name":"Jalaj"}],"article_processing_charge":"No","OA_type":"green","volume":5,"project":[{"call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422","name":"Efficient algorithms"},{"grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"publisher":"Association for Computing Machinery","year":"2025","title":"Improved differentially private continual observation using group algebra","language":[{"iso":"eng"}],"month":"01","status":"public","department":[{"_id":"MoHe"}],"doi":"10.1137/1.9781611978322.95","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2412.02840","open_access":"1"}]},{"department":[{"_id":"MoHe"}],"doi":"10.4230/LIPIcs.SAND.2025.4","status":"public","month":"06","language":[{"iso":"eng"}],"title":"On b-matching and fully-dynamic maximum k-edge coloring","has_accepted_license":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2025","project":[{"name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422","name":"Efficient algorithms"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer"}],"volume":330,"OA_type":"gold","article_processing_charge":"No","author":[{"last_name":"El-Hayek","id":"888a098e-fcac-11ee-aff7-d347be57b725","first_name":"Antoine","orcid":"0000-0003-4268-7368","full_name":"El-Hayek, Antoine"},{"last_name":"Hanauer","first_name":"Kathrin","full_name":"Hanauer, Kathrin"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","abstract":[{"lang":"eng","text":"Given a graph G that undergoes a sequence of edge insertions and deletions, we study the Maximum k-Edge Coloring problem (MkEC): Having access to k different colors, color as many edges of G as possible such that no two adjacent edges share the same color. While this problem is different from simply maintaining a b-matching with b = k, the two problems are related. However, maximum b-matching can be solved efficiently in the static setting, whereas MkEC is NP-hard and even APX-hard for k ≥ 2. \r\nWe present new results on both problems: For b-matching, we show a new integrality gap result and we adapt Wajc’s matching sparsification scheme [David Wajc, 2020] for the case where b is a constant.\r\nUsing these as basis, we give three new algorithms for the dynamic MkEC problem: Our MatchO algorithm builds on the dynamic (2+ε)-approximation algorithm of Bhattacharya, Gupta, and Mohan [Sayan Bhattacharya et al., 2017] for b-matching and achieves a (2+ε)(k+1)/k-approximation in O(poly(log n, ε^-1)) update time against an oblivious adversary. Our MatchA algorithm builds on the dynamic (7+ε)-approximation algorithm by Bhattacharya, Henzinger, and Italiano [Sayan Bhattacharya et al., 2015] for fractional b-matching and achieves a (7+ε)(3k+3)/(3k-1)-approximation in O(poly(log n, ε^-1)) update time against an adaptive adversary. Moreover, our reductions use the dynamic b-matching algorithm as a black box, so any future improvement in the approximation ratio for dynamic b-matching will automatically translate into a better approximation ratio for our algorithms. Finally, we present a greedy algorithm with O(Δ+k) update time, which guarantees a 2.16 approximation factor."}],"ddc":["000"],"external_id":{"arxiv":["2310.01149"],"isi":["001532136900004"]},"date_created":"2025-06-22T22:02:06Z","day":"02","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773683"]},"arxiv":1,"oa_version":"Published Version","scopus_import":"1","ec_funded":1,"acknowledgement":"This project has received funding from the European Research Council (ERC) under the\r\nEuropean Union’s Horizon 2020 research and innovation programme (MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024. This work was further supported by the Federal Ministry of Education and Research (BMBF) project, 6G-RIC: 6G Research and Innovation Cluster, grant 16KISK020K.","_id":"19858","file":[{"content_type":"application/pdf","success":1,"date_updated":"2025-06-23T11:23:29Z","file_id":"19872","file_size":995666,"creator":"dernst","checksum":"ad93a1e052adb29d7bfe8bd551bab193","access_level":"open_access","date_created":"2025-06-23T11:23:29Z","file_name":"2025_LIPIcs_ElHayek.pdf","relation":"main_file"}],"date_updated":"2025-09-30T13:37:28Z","file_date_updated":"2025-06-23T11:23:29Z","date_published":"2025-06-02T00:00:00Z","oa":1,"type":"conference","OA_place":"publisher","publication_status":"published","publication":"4th Symposium on Algorithmic Foundations of Dynamic Networks","article_number":"4","alternative_title":["LIPIcs"],"intvolume":"       330","citation":{"apa":"El-Hayek, A., Hanauer, K., &#38; Henzinger, M. (2025). On b-matching and fully-dynamic maximum k-edge coloring. In <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i> (Vol. 330). Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2025.4\">https://doi.org/10.4230/LIPIcs.SAND.2025.4</a>","ieee":"A. El-Hayek, K. Hanauer, and M. Henzinger, “On b-matching and fully-dynamic maximum k-edge coloring,” in <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i>, Liverpool, United Kingdom, 2025, vol. 330.","ista":"El-Hayek A, Hanauer K, Henzinger M. 2025. On b-matching and fully-dynamic maximum k-edge coloring. 4th Symposium on Algorithmic Foundations of Dynamic Networks. SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 330, 4.","chicago":"El-Hayek, Antoine, Kathrin Hanauer, and Monika Henzinger. “On B-Matching and Fully-Dynamic Maximum k-Edge Coloring.” In <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i>, Vol. 330. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2025.4\">https://doi.org/10.4230/LIPIcs.SAND.2025.4</a>.","mla":"El-Hayek, Antoine, et al. “On B-Matching and Fully-Dynamic Maximum k-Edge Coloring.” <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i>, vol. 330, 4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2025.4\">10.4230/LIPIcs.SAND.2025.4</a>.","short":"A. El-Hayek, K. Hanauer, M. Henzinger, in:, 4th Symposium on Algorithmic Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","ama":"El-Hayek A, Hanauer K, Henzinger M. On b-matching and fully-dynamic maximum k-edge coloring. In: <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i>. Vol 330. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2025.4\">10.4230/LIPIcs.SAND.2025.4</a>"},"isi":1,"corr_author":"1","quality_controlled":"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"},"conference":{"name":"SAND: Symposium on Algorithmic Foundations of Dynamic Networks","location":"Liverpool, United Kingdom","end_date":"2025-06-11","start_date":"2025-06-09"}},{"OA_type":"green","author":[{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Sricharan","full_name":"Sricharan, A. R.","first_name":"A. R."},{"last_name":"Steiner","first_name":"Teresa Anna","full_name":"Steiner, Teresa Anna"}],"article_processing_charge":"No","status":"public","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2302.11341"}],"department":[{"_id":"MoHe"}],"language":[{"iso":"eng"}],"title":"Differentially private continual release of histograms and related queries","month":"05","publisher":"ML Research Press","year":"2025","volume":258,"project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422","name":"Efficient algorithms"},{"grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"page":"1990-1998","type":"conference","OA_place":"repository","date_published":"2025-05-01T00:00:00Z","oa":1,"publication":"The 28th International Conference on Artificial Intelligence and Statistics","publication_status":"published","citation":{"mla":"Henzinger, Monika, et al. “Differentially Private Continual Release of Histograms and Related Queries.” <i>The 28th International Conference on Artificial Intelligence and Statistics</i>, vol. 258, ML Research Press, 2025, pp. 1990–98.","chicago":"Henzinger, Monika, A. R. Sricharan, and Teresa Anna Steiner. “Differentially Private Continual Release of Histograms and Related Queries.” In <i>The 28th International Conference on Artificial Intelligence and Statistics</i>, 258:1990–98. ML Research Press, 2025.","ista":"Henzinger M, Sricharan AR, Steiner TA. 2025. Differentially private continual release of histograms and related queries. The 28th International Conference on Artificial Intelligence and Statistics. AISTATS: Conference on Artificial Intelligence and Statistics, PMLR, vol. 258, 1990–1998.","apa":"Henzinger, M., Sricharan, A. R., &#38; Steiner, T. A. (2025). Differentially private continual release of histograms and related queries. In <i>The 28th International Conference on Artificial Intelligence and Statistics</i> (Vol. 258, pp. 1990–1998). Mai Khao, Thailand: ML Research Press.","ieee":"M. Henzinger, A. R. Sricharan, and T. A. Steiner, “Differentially private continual release of histograms and related queries,” in <i>The 28th International Conference on Artificial Intelligence and Statistics</i>, Mai Khao, Thailand, 2025, vol. 258, pp. 1990–1998.","ama":"Henzinger M, Sricharan AR, Steiner TA. Differentially private continual release of histograms and related queries. In: <i>The 28th International Conference on Artificial Intelligence and Statistics</i>. Vol 258. ML Research Press; 2025:1990-1998.","short":"M. Henzinger, A.R. Sricharan, T.A. Steiner, in:, The 28th International Conference on Artificial Intelligence and Statistics, ML Research Press, 2025, pp. 1990–1998."},"alternative_title":["PMLR"],"intvolume":"       258","conference":{"end_date":"2025-05-05","location":"Mai Khao, Thailand","start_date":"2025-05-03","name":"AISTATS: Conference on Artificial Intelligence and Statistics"},"quality_controlled":"1","date_created":"2025-09-07T22:01:35Z","external_id":{"arxiv":["2302.11341"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"We study privately releasing column sums of a d-dimensional table with entries from a universe χ undergoing T row updates, called histogram under continual release. Our mechanisms give better additive ℓ∞-error than existing mechanisms for a large class of queries and input streams. Our first contribution is an output-sensitive mechanism in the insertions-only model (χ = {0, 1}) for maintaining (i) the histogram or (ii) queries that do not require maintaining the entire histogram, such as the maximum or minimum column sum, the median, or any quantiles. The mechanism has an additive error of O(d log2 (dq∗) + log T) whp, where q∗ is the maximum output value over all time steps on this dataset. The mechanism does not require q∗ as input. This breaks the Ω(d log T) bound of prior work when q∗ ≪ T. Our second contribution is a mechanism for the turnstile model that admits negative entry updates (χ = {−1, 0, 1}). This mechanism has an additive error of O(d log2(dK) + log T) whp, where K is the number of times two consecutive data rows differ, and the mechanism does not require K as input. This is useful when monitoring inputs that only vary under unusual circumstances. For d = 1 this gives the first\r\nprivate mechanism with error O(log2 K + log T) for continual counting in the turnstile model, improving on the O(log2 n + log T) error bound by Dwork et al. (2015), where n is the number of ones in the stream, as well as allowing negative entries, while Dwork et al. (2015) can only handle nonnegative entries (χ = {0, 1}). "}],"oa_version":"Preprint","arxiv":1,"day":"01","publication_identifier":{"eissn":["2640-3498"]},"acknowledgement":"MH: 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 DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024. TAS: This work was supported by a research grant (VIL51463)\r\nfrom VILLUM FONDEN.","ec_funded":1,"scopus_import":"1","date_updated":"2025-09-09T07:09:22Z","_id":"20301"},{"oa_version":"Published Version","arxiv":1,"day":"01","publication_identifier":{"isbn":["9783959773959"],"issn":["1868-8969"]},"external_id":{"arxiv":["2509.05157"]},"date_created":"2025-10-26T23:01:34Z","ddc":["000"],"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"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2025-10-27T08:03:36Z","date_updated":"2025-10-27T08:05:46Z","file":[{"relation":"main_file","file_name":"2025_LIPIcs.ESA_HenzingerM.pdf","date_created":"2025-10-27T08:03:36Z","access_level":"open_access","checksum":"d2daf9a467e96fb5e7084a8a85321776","file_size":934846,"creator":"dernst","file_id":"20542","date_updated":"2025-10-27T08:03:36Z","success":1,"content_type":"application/pdf"}],"_id":"20534","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.","ec_funded":1,"scopus_import":"1","publication":"33rd Annual European Symposium on Algorithms","article_number":"36","publication_status":"published","OA_place":"publisher","type":"conference","oa":1,"date_published":"2025-10-01T00:00:00Z","quality_controlled":"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"},"conference":{"start_date":"2025-09-15","location":"Warsaw, Poland","end_date":"2025-09-17","name":"ESA: European Symposium on Algorithms"},"corr_author":"1","citation":{"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.","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>","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>.","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>","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.","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.","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>."},"intvolume":"       351","has_accepted_license":"1","title":"Efficient contractions of dynamic graphs - with applications","language":[{"iso":"eng"}],"month":"10","status":"public","department":[{"_id":"MoHe"}],"doi":"10.4230/LIPIcs.ESA.2025.36","volume":351,"project":[{"grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"name":"Efficient algorithms","grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions"}],"year":"2025","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","OA_type":"gold","author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"full_name":"Kosinas, Evangelos","first_name":"Evangelos","id":"4c7f9625-dbbc-11ee-9d86-bdcc2db5a949","last_name":"Kosinas"},{"last_name":"Münk","full_name":"Münk, Robin","first_name":"Robin"},{"last_name":"Räcke","first_name":"Harald","full_name":"Räcke, Harald"}],"article_processing_charge":"No"},{"OA_type":"gold","article_processing_charge":"No","author":[{"last_name":"Dhulipala","full_name":"Dhulipala, Laxman","first_name":"Laxman"},{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger"},{"last_name":"Li","first_name":"George Z.","full_name":"Li, George Z."},{"last_name":"Liu","first_name":"Quanquan C.","full_name":"Liu, Quanquan C."},{"last_name":"Sricharan","first_name":"A. R.","full_name":"Sricharan, A. R."},{"last_name":"Zhu","full_name":"Zhu, Leqi","first_name":"Leqi","id":"a2117c59-cee4-11ed-b9d0-874ecf0f8ac5"}],"month":"10","title":"Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism","language":[{"iso":"eng"}],"has_accepted_license":"1","department":[{"_id":"MoHe"}],"doi":"10.4230/LIPIcs.ESA.2025.91","status":"public","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"volume":351,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2025","publication_status":"published","article_number":"91","publication":"33rd Annual European Symposium on Algorithms","date_published":"2025-10-01T00:00:00Z","oa":1,"type":"conference","OA_place":"publisher","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","conference":{"start_date":"2025-09-15","end_date":"2025-09-17","location":"Warsaw, Poland","name":"ESA: European Symposium on Algorithms"},"alternative_title":["LIPIcs"],"intvolume":"       351","citation":{"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>.","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>","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.","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.","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>.","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.","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>"},"corr_author":"1","day":"01","publication_identifier":{"isbn":["9783959773959"],"issn":["1868-8969"]},"arxiv":1,"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","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."}],"ddc":["000"],"external_id":{"arxiv":["2508.02182"]},"date_created":"2025-10-26T23:01:35Z","_id":"20535","date_updated":"2025-10-27T07:02:06Z","file":[{"relation":"main_file","file_name":"2025_LIPIcs.ESA_Dhulipala.pdf","date_created":"2025-10-27T06:58:43Z","access_level":"open_access","checksum":"19146e935b5b6ad5d33c8d08280ad8e7","creator":"dernst","file_size":870317,"file_id":"20539","success":1,"date_updated":"2025-10-27T06:58:43Z","content_type":"application/pdf"}],"file_date_updated":"2025-10-27T06:58:43Z","scopus_import":"1","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.","ec_funded":1},{"publication_status":"published","article_number":"47","publication":"19th International Symposium on Algorithms and Data Structures","oa":1,"date_published":"2025-08-29T00:00:00Z","OA_place":"publisher","type":"conference","conference":{"start_date":"2025-08-11","end_date":"2025-08-15","location":"Toronto, Canada","name":"WADS: Algorithms and Data Structures Symposium"},"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","intvolume":"       349","alternative_title":["LIPIcs"],"corr_author":"1","citation":{"mla":"Safavi Hemami, Roodabeh, and Martin P. Seybold. “B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load.” <i>19th International Symposium on Algorithms and Data Structures</i>, vol. 349, 47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.WADS.2025.47\">10.4230/LIPIcs.WADS.2025.47</a>.","chicago":"Safavi Hemami, Roodabeh, and Martin P. Seybold. “B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load.” In <i>19th International Symposium on Algorithms and Data Structures</i>, Vol. 349. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.WADS.2025.47\">https://doi.org/10.4230/LIPIcs.WADS.2025.47</a>.","ieee":"R. Safavi Hemami and M. P. Seybold, “B-Treaps revised: Write efficient randomized block search trees with high load,” in <i>19th International Symposium on Algorithms and Data Structures</i>, Toronto, Canada, 2025, vol. 349.","ista":"Safavi Hemami R, Seybold MP. 2025. B-Treaps revised: Write efficient randomized block search trees with high load. 19th International Symposium on Algorithms and Data Structures. WADS: Algorithms and Data Structures Symposium, LIPIcs, vol. 349, 47.","apa":"Safavi Hemami, R., &#38; Seybold, M. P. (2025). B-Treaps revised: Write efficient randomized block search trees with high load. In <i>19th International Symposium on Algorithms and Data Structures</i> (Vol. 349). Toronto, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.WADS.2025.47\">https://doi.org/10.4230/LIPIcs.WADS.2025.47</a>","ama":"Safavi Hemami R, Seybold MP. B-Treaps revised: Write efficient randomized block search trees with high load. In: <i>19th International Symposium on Algorithms and Data Structures</i>. Vol 349. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.WADS.2025.47\">10.4230/LIPIcs.WADS.2025.47</a>","short":"R. Safavi Hemami, M.P. Seybold, in:, 19th International Symposium on Algorithms and Data Structures, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025."},"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773980"]},"day":"29","oa_version":"Published Version","arxiv":1,"abstract":[{"lang":"eng","text":"Uniquely represented (UR) data structures represent each logical state with a unique storage state. We study the problem of maintaining a dynamic set of n keys from a totally ordered universe in this context. UR structures are also called \"strongly history independent\" structures in the literature.\r\nWe introduce a two-layer data structure called (α,ε)-Randomized Block Search Tree (RBST) that is uniquely represented and suitable for external memory (EM). Though RBSTs naturally generalize the well-known binary Treaps, several new ideas are needed to analyze the expected search, update, and storage efficiency in terms of block-reads, block-writes, and blocks stored. We prove that searches have O(ε^{-1} + log_α n) block-reads, that dynamic updates perform O(ε^{-1} + log_α(n)/α) block-writes and O(ε^{-2}+(1+(ε^{-1}+log n)/α)log_α n) block-reads, and that (α, ε)-RBSTs have an asymptotic load-factor of at least (1-ε) for every ε ∈ (0,1/2].\r\nThus (α, ε)-RBSTs improve on the known, uniquely represented B-Treap [Golovin; ICALP'09]. Compared with non-UR structures, the RBST is also, to the best of our knowledge, the first external memory structure that is storage-efficient and has a non-amortized, write-efficient update bound."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["2303.04722"]},"date_created":"2025-10-26T23:01:35Z","ddc":["000"],"_id":"20536","file_date_updated":"2025-10-27T07:09:41Z","date_updated":"2025-10-27T07:10:49Z","file":[{"file_size":1081870,"creator":"dernst","file_id":"20540","success":1,"content_type":"application/pdf","date_updated":"2025-10-27T07:09:41Z","file_name":"2025_LIPIcs.WADS_Safavi.pdf","relation":"main_file","date_created":"2025-10-27T07:09:41Z","checksum":"196af33762831a78e87f4f95ecd8677b","access_level":"open_access"}],"scopus_import":"1","acknowledgement":"This work was supported under the Australian Research Council Discovery Projects\r\nfunding scheme (project number DP180102870). This project has received funding from the\r\nEuropean Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564) “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project Z 422-N and project “Fast Algorithms for a Reactive Network Layer (ReactNet)” P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.","ec_funded":1,"OA_type":"gold","article_processing_charge":"No","author":[{"last_name":"Safavi Hemami","id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","first_name":"Roodabeh","full_name":"Safavi Hemami, Roodabeh"},{"first_name":"Martin P.","full_name":"Seybold, Martin P.","last_name":"Seybold"}],"month":"08","has_accepted_license":"1","title":"B-Treaps revised: Write efficient randomized block search trees with high load","language":[{"iso":"eng"}],"department":[{"_id":"MoHe"}],"doi":"10.4230/LIPIcs.WADS.2025.47","status":"public","project":[{"name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564"},{"name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"}],"volume":349,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2025"},{"article_processing_charge":"No","author":[{"last_name":"El-Hayek","first_name":"Antoine","id":"888a098e-fcac-11ee-aff7-d347be57b725","full_name":"El-Hayek, Antoine","orcid":"0000-0003-4268-7368"},{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"last_name":"Li","full_name":"Li, Jason","first_name":"Jason"}],"OA_type":"green","year":"2025","publisher":"Society for Industrial and Applied Mathematics","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"name":"Efficient algorithms","grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer"}],"doi":"10.1137/1.9781611978322.22","department":[{"_id":"MoHe"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2412.15069"}],"status":"public","month":"01","title":"Fully dynamic approximate minimum cut in subpolynomial time per operation","language":[{"iso":"eng"}],"corr_author":"1","citation":{"mla":"El-Hayek, Antoine, et al. “Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation.” <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2025, pp. 750–84, doi:<a href=\"https://doi.org/10.1137/1.9781611978322.22\">10.1137/1.9781611978322.22</a>.","chicago":"El-Hayek, Antoine, Monika Henzinger, and Jason Li. “Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation.” In <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 750–84. Society for Industrial and Applied Mathematics, 2025. <a href=\"https://doi.org/10.1137/1.9781611978322.22\">https://doi.org/10.1137/1.9781611978322.22</a>.","ista":"El-Hayek A, Henzinger M, Li J. 2025. Fully dynamic approximate minimum cut in subpolynomial time per operation. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 750–784.","apa":"El-Hayek, A., Henzinger, M., &#38; Li, J. (2025). Fully dynamic approximate minimum cut in subpolynomial time per operation. In <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 750–784). New Orleans, LA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611978322.22\">https://doi.org/10.1137/1.9781611978322.22</a>","ieee":"A. El-Hayek, M. Henzinger, and J. Li, “Fully dynamic approximate minimum cut in subpolynomial time per operation,” in <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, New Orleans, LA, United States, 2025, pp. 750–784.","ama":"El-Hayek A, Henzinger M, Li J. Fully dynamic approximate minimum cut in subpolynomial time per operation. In: <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2025:750-784. doi:<a href=\"https://doi.org/10.1137/1.9781611978322.22\">10.1137/1.9781611978322.22</a>","short":"A. El-Hayek, M. Henzinger, J. Li, in:, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2025, pp. 750–784."},"quality_controlled":"1","conference":{"location":"New Orleans, LA, United States","end_date":"2025-01-15","start_date":"2025-01-12","name":"SODA: Symposium on Discrete Algorithms"},"oa":1,"date_published":"2025-01-07T00:00:00Z","OA_place":"repository","type":"conference","page":"750-784","publication_status":"published","publication":"Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms","acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union’sHorizon 2020 research and innovation programme (MoDynStruct, No. 101019564) and the Austrian Science Fund(FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024.","ec_funded":1,"related_material":{"record":[{"relation":"dissertation_contains","id":"22281","status":"public"}]},"_id":"19982","date_updated":"2026-07-24T12:48:28Z","abstract":[{"text":"Dynamically maintaining the minimum cut in a graph G under edge insertions and deletion is a fundamental problem in dynamic graph algorithms for which no conditional lower bound on the time per operation exists. In an n-node graph the best known (1 + o (1))-approximate algorithm takes  update time [14]. If the minimum cut is guaranteed to be (log n )o (1), a deterministic exact algorithm with n o (1) update time exists [8].\r\nWe present the first fully dynamic algorithm for (1 + o (1))-approximate minimum cut with n o(1) update time. Our main technical contribution is to show that it suffices to consider small-volume cuts in suitably contracted graphs.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["2412.15069"]},"date_created":"2025-07-10T13:08:57Z","publication_identifier":{"eisbn":["9781611978322"]},"day":"07","oa_version":"Preprint","arxiv":1},{"author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"last_name":"Saulpic","full_name":"Saulpic, David","first_name":"David","id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964"},{"id":"8b563fd0-b441-11ee-9101-a3891c61efa6","first_name":"Leonhard","full_name":"Sidl, Leonhard","last_name":"Sidl"}],"article_processing_charge":"No","year":"2024","publisher":"Society for Industrial and Applied Mathematics","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422","name":"Efficient algorithms"},{"grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer"},{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program"}],"status":"public","doi":"10.1137/1.9781611977929.17","department":[{"_id":"MoHe"}],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2310.18034","open_access":"1"}],"language":[{"iso":"eng"}],"title":"Experimental evaluation of fully dynamic k-means via coresets","month":"01","corr_author":"1","citation":{"ama":"Henzinger M, Saulpic D, Sidl L. Experimental evaluation of fully dynamic k-means via coresets. In: <i>2024 Proceedings of the Symposium on Algorithm Engineering and Experiments</i>. Society for Industrial and Applied Mathematics; 2024:220-233. doi:<a href=\"https://doi.org/10.1137/1.9781611977929.17\">10.1137/1.9781611977929.17</a>","short":"M. Henzinger, D. Saulpic, L. Sidl, in:, 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2024, pp. 220–233.","chicago":"Henzinger, Monika, David Saulpic, and Leonhard Sidl. “Experimental Evaluation of Fully Dynamic K-Means via Coresets.” In <i>2024 Proceedings of the Symposium on Algorithm Engineering and Experiments</i>, 220–33. Society for Industrial and Applied Mathematics, 2024. <a href=\"https://doi.org/10.1137/1.9781611977929.17\">https://doi.org/10.1137/1.9781611977929.17</a>.","ista":"Henzinger M, Saulpic D, Sidl L. 2024. Experimental evaluation of fully dynamic k-means via coresets. 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments. ALENEX: Workshop on Algorithm Engineering and Experiments, 220–233.","ieee":"M. Henzinger, D. Saulpic, and L. Sidl, “Experimental evaluation of fully dynamic k-means via coresets,” in <i>2024 Proceedings of the Symposium on Algorithm Engineering and Experiments</i>, Alexandria, VA, United States, 2024, pp. 220–233.","apa":"Henzinger, M., Saulpic, D., &#38; Sidl, L. (2024). Experimental evaluation of fully dynamic k-means via coresets. In <i>2024 Proceedings of the Symposium on Algorithm Engineering and Experiments</i> (pp. 220–233). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977929.17\">https://doi.org/10.1137/1.9781611977929.17</a>","mla":"Henzinger, Monika, et al. “Experimental Evaluation of Fully Dynamic K-Means via Coresets.” <i>2024 Proceedings of the Symposium on Algorithm Engineering and Experiments</i>, Society for Industrial and Applied Mathematics, 2024, pp. 220–33, doi:<a href=\"https://doi.org/10.1137/1.9781611977929.17\">10.1137/1.9781611977929.17</a>."},"quality_controlled":"1","conference":{"start_date":"2024-01-07","location":"Alexandria, VA, United States","end_date":"2024-01-08","name":"ALENEX: Workshop on Algorithm Engineering and Experiments"},"page":"220-233","type":"conference","oa":1,"date_published":"2024-01-04T00:00:00Z","publication":"2024 Proceedings of the Symposium on Algorithm Engineering and Experiments","publication_status":"published","ec_funded":1,"acknowledgement":"This   project   has   received   funding   from   the   Euro-pean  Research  Council  (ERC)  under  the  EuropeanUnion’s  Horizon  2020  research  and  innovation  programme  (Grant  agreement  No.   101019564  “The  De-sign  of  Modern  Fully  Dynamic  Data  Structures  (Mo-DynStruct)”  and  the  Austrian  Science  Fund  (FWF)project Z 422-N, project “Static and Dynamic Hierar-chical  Graph  Decompositions”,  I  5982-N,  and  project“Fast  Algorithms  for  a  Reactive  Network  Layer  (Re-actNet)”, P 33775-N, with additional funding from thenetidee SCIENCE Stiftung, 2020–2024.D.  Sauplic  has  received  funding  from  the  Euro-pean  Union’s  Horizon  2020  research  and  innovation programme under the Marie Sklodowska-Curie    grant    agreementNo 101034413.","scopus_import":"1","date_updated":"2025-04-14T13:50:50Z","_id":"14769","date_created":"2024-01-09T16:22:47Z","external_id":{"arxiv":["2310.18034"]},"abstract":[{"lang":"eng","text":"For a set of points in Rd, the Euclidean k-means problems consists of finding k centers such that the sum of distances squared from each data point to its closest center is minimized. Coresets are one the main tools developed recently to solve this problem in a big data context. They allow to compress the initial dataset while preserving its structure: running any algorithm on the coreset provides a guarantee almost equivalent to running it on the full data. In this work, we study coresets in a fully-dynamic setting: points are added and deleted with the goal to efficiently maintain a coreset with which a k-means solution can be computed. Based on an algorithm from Henzinger and Kale [ESA'20], we present an efficient and practical implementation of a fully dynamic coreset algorithm, that improves the running time by up to a factor of 20 compared to our non-optimized implementation of the algorithm by Henzinger and Kale, without sacrificing more than 7% on the quality of the k-means solution."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"oa_version":"Preprint","publication_identifier":{"eisbn":["9781611977929"]},"day":"04"},{"author":[{"last_name":"Goranci","first_name":"Gramoz","full_name":"Goranci, Gramoz"},{"last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"first_name":"Harald","full_name":"Räcke, Harald","last_name":"Räcke"},{"last_name":"Sachdeva","first_name":"Sushant","full_name":"Sachdeva, Sushant"},{"first_name":"A. R.","full_name":"Sricharan, A. R.","last_name":"Sricharan"}],"article_processing_charge":"No","volume":287,"project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"name":"Efficient algorithms","grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer"}],"year":"2024","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","language":[{"iso":"eng"}],"title":"Electrical flows for polylogarithmic competitive oblivious routing","has_accepted_license":"1","month":"01","status":"public","doi":"10.4230/LIPIcs.ITCS.2024.55","department":[{"_id":"MoHe"}],"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","conference":{"name":"ITCS: Innovations in Theoretical Computer Science","start_date":"2024-01-30","location":"Berkeley, CA, United States","end_date":"2024-02-02"},"isi":1,"citation":{"apa":"Goranci, G., Henzinger, M., Räcke, H., Sachdeva, S., &#38; Sricharan, A. R. (2024). Electrical flows for polylogarithmic competitive oblivious routing. In <i>15th Innovations in Theoretical Computer Science Conference</i> (Vol. 287). Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.55\">https://doi.org/10.4230/LIPIcs.ITCS.2024.55</a>","ista":"Goranci G, Henzinger M, Räcke H, Sachdeva S, Sricharan AR. 2024. Electrical flows for polylogarithmic competitive oblivious routing. 15th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 287, 55.","ieee":"G. Goranci, M. Henzinger, H. Räcke, S. Sachdeva, and A. R. Sricharan, “Electrical flows for polylogarithmic competitive oblivious routing,” in <i>15th Innovations in Theoretical Computer Science Conference</i>, Berkeley, CA, United States, 2024, vol. 287.","chicago":"Goranci, Gramoz, Monika Henzinger, Harald Räcke, Sushant Sachdeva, and A. R. Sricharan. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.” In <i>15th Innovations in Theoretical Computer Science Conference</i>, Vol. 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.55\">https://doi.org/10.4230/LIPIcs.ITCS.2024.55</a>.","mla":"Goranci, Gramoz, et al. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.” <i>15th Innovations in Theoretical Computer Science Conference</i>, vol. 287, 55, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.55\">10.4230/LIPIcs.ITCS.2024.55</a>.","short":"G. Goranci, M. Henzinger, H. Räcke, S. Sachdeva, A.R. Sricharan, in:, 15th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ama":"Goranci G, Henzinger M, Räcke H, Sachdeva S, Sricharan AR. Electrical flows for polylogarithmic competitive oblivious routing. In: <i>15th Innovations in Theoretical Computer Science Conference</i>. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.55\">10.4230/LIPIcs.ITCS.2024.55</a>"},"corr_author":"1","alternative_title":["LIPIcs"],"intvolume":"       287","article_number":"55","publication":"15th Innovations in Theoretical Computer Science Conference","publication_status":"published","type":"conference","date_published":"2024-01-24T00:00:00Z","oa":1,"file_date_updated":"2024-02-26T10:10:48Z","file":[{"file_size":1054754,"creator":"dernst","content_type":"application/pdf","date_updated":"2024-02-26T10:10:48Z","success":1,"file_id":"15030","date_created":"2024-02-26T10:10:48Z","file_name":"2024_LIPICs_Goranci.pdf","relation":"main_file","checksum":"b89716aae6a5599f187897e39de1e53a","access_level":"open_access"}],"date_updated":"2025-09-04T12:06:25Z","_id":"15008","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 (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) project Z\r\n422-N, project I 5982-N, and project P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nHarald Räcke: Research supported by German Research Foundation (DFG), grant 470029389\r\n(FlexNets), 2021-2024.\r\nSushant Sachdeva: SS’s work is supported by an Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant RGPIN-2018-06398 and a Sloan Research Fellowship.","ec_funded":1,"scopus_import":"1","arxiv":1,"oa_version":"Published Version","day":"24","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773096"]},"ddc":["000"],"date_created":"2024-02-18T23:01:02Z","external_id":{"isi":["001300389400055"],"arxiv":["2303.02491"]},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","abstract":[{"text":"Oblivious routing is a well-studied paradigm that uses static precomputed routing tables for selecting routing paths within a network. Existing oblivious routing schemes with polylogarithmic competitive ratio for general networks are tree-based, in the sense that routing is performed according to a convex combination of trees. However, this restriction to trees leads to a construction that has time quadratic in the size of the network and does not parallelize well. \r\nIn this paper we study oblivious routing schemes based on electrical routing. In particular, we show that general networks with n vertices and m edges admit a routing scheme that has competitive ratio O(log² n) and consists of a convex combination of only O(√m) electrical routings. This immediately leads to an improved construction algorithm with time Õ(m^{3/2}) that can also be implemented in parallel with Õ(√m) depth.","lang":"eng"}]},{"arxiv":1,"oa_version":"Preprint","day":"04","publication_identifier":{"eisbn":["9781611977912"]},"external_id":{"arxiv":["2311.01115"]},"date_created":"2024-03-08T10:27:39Z","abstract":[{"text":"We present a dynamic data structure for maintaining the persistent homology of a time series of real numbers. The data structure supports local operations, including the insertion and deletion of an item and the cutting and concatenating of lists, each in time O(log n + k), in which n counts the critical items and k the changes in the augmented persistence diagram. To achieve this, we design a tailor-made tree structure with an unconventional representation, referred to as banana tree, which may be useful in its own right.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-04-07T12:58:47Z","_id":"15093","acknowledgement":"The  first  and  second  authors  are  funded  by  the  European  Research  Council  under  the European Union’s Horizon 2020 research and innovation programme, ERC grant no. 788183,“Alpha Shape Theory Extended (Alpha)”, by the Wittgenstein Prize, FWF grant no. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, FWF grant no. I 02979-N35.The third author received funding by the European Research Council under the European Union’s Horizon 2020research  and  innovation  programme,  ERC  grant  no.  101019564,  “The  Design  of  Modern  Fully  Dynamic  DataStructures (MoDynStruct)”, and by the Austrian Science Fund through the Wittgenstein Prize with FWF grant no. Z 422-N, and also by FWF grant no. I 5982-N, and by FWF grant no. P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.  The fourth author is funded by the Vienna Graduate School on Computational Optimization, FWF project no. W1260-N35.","related_material":{"record":[{"relation":"dissertation_contains","id":"15094","status":"public"}]},"ec_funded":1,"scopus_import":"1","publication":"Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","publication_status":"published","page":"243 - 295","type":"conference","oa":1,"date_published":"2024-01-04T00:00:00Z","quality_controlled":"1","conference":{"name":"SODA: Symposium on Discrete Algorithms","start_date":"2024-01-07","location":"Alexandria, VA, USA","end_date":"2024-01-10"},"corr_author":"1","citation":{"ama":"Cultrera di Montesano S, Edelsbrunner H, Henzinger M, Ost L. Dynamically maintaining the persistent homology of time series. In: Woodruff DP, ed. <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)</i>. Society for Industrial and Applied Mathematics; 2024:243-295. doi:<a href=\"https://doi.org/10.1137/1.9781611977912.11\">10.1137/1.9781611977912.11</a>","short":"S. Cultrera di Montesano, H. Edelsbrunner, M. Henzinger, L. Ost, in:, D.P. Woodruff (Ed.), Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, 2024, pp. 243–295.","chicago":"Cultrera di Montesano, Sebastiano, Herbert Edelsbrunner, Monika Henzinger, and Lara Ost. “Dynamically Maintaining the Persistent Homology of Time Series.” In <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)</i>, edited by David P. Woodruff, 243–95. Society for Industrial and Applied Mathematics, 2024. <a href=\"https://doi.org/10.1137/1.9781611977912.11\">https://doi.org/10.1137/1.9781611977912.11</a>.","ista":"Cultrera di Montesano S, Edelsbrunner H, Henzinger M, Ost L. 2024. Dynamically maintaining the persistent homology of time series. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SODA: Symposium on Discrete Algorithms, 243–295.","apa":"Cultrera di Montesano, S., Edelsbrunner, H., Henzinger, M., &#38; Ost, L. (2024). Dynamically maintaining the persistent homology of time series. In D. P. Woodruff (Ed.), <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)</i> (pp. 243–295). Alexandria, VA, USA: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977912.11\">https://doi.org/10.1137/1.9781611977912.11</a>","ieee":"S. Cultrera di Montesano, H. Edelsbrunner, M. Henzinger, and L. Ost, “Dynamically maintaining the persistent homology of time series,” in <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)</i>, Alexandria, VA, USA, 2024, pp. 243–295.","mla":"Cultrera di Montesano, Sebastiano, et al. “Dynamically Maintaining the Persistent Homology of Time Series.” <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)</i>, edited by David P. Woodruff, Society for Industrial and Applied Mathematics, 2024, pp. 243–95, doi:<a href=\"https://doi.org/10.1137/1.9781611977912.11\">10.1137/1.9781611977912.11</a>."},"language":[{"iso":"eng"}],"title":"Dynamically maintaining the persistent homology of time series","month":"01","status":"public","doi":"10.1137/1.9781611977912.11","department":[{"_id":"HeEd"},{"_id":"MoHe"}],"main_file_link":[{"url":"https://arxiv.org/abs/2311.01115","open_access":"1"}],"project":[{"name":"Alpha Shape Theory Extended","call_identifier":"H2020","grant_number":"788183","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Mathematics, Computer Science"},{"name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"}],"publisher":"Society for Industrial and Applied Mathematics","year":"2024","author":[{"full_name":"Cultrera di Montesano, Sebastiano","orcid":"0000-0001-6249-0832","first_name":"Sebastiano","id":"34D2A09C-F248-11E8-B48F-1D18A9856A87","last_name":"Cultrera di Montesano"},{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","last_name":"Edelsbrunner"},{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Ost","full_name":"Ost, Lara","first_name":"Lara"}],"article_processing_charge":"No","editor":[{"first_name":"David P.","full_name":"Woodruff, David P.","last_name":"Woodruff"}]},{"date_created":"2024-03-31T22:01:13Z","external_id":{"arxiv":["2307.08970"]},"abstract":[{"text":"We study the problem of maintaining a differentially private decaying sum under continual observation. We give a unifying framework and an efficient algorithm for this problem for any sufficiently smooth function. Our algorithm is the first differentially private algorithm that does not have a multiplicative error for polynomially decaying weights. Our algorithm improves on all prior works on differentially private decaying sums under continual observation and recovers exactly the additive error for the special case of continual counting from Henzinger et al. (SODA 2023) as a corollary.\r\nOur algorithm is a variant of the matrix mechanism whose error depends on the γ2 and γF norm of the underlying matrix. We give a constructive proof for an almost exact upper bound on the γ2 and γF norm and an almost tight lower bound on the γ2 norm for a large class of lower-triangular matrices. This is the first non-trivial lower bound for lower-triangular matrices whose non-zero entries are not all the same. It includes matrices for all continual decaying sums problems, resulting in an upper bound on the additive error of any differentially private decaying sums algorithm under continual observation.\r\nWe also explore some implications of our result in discrepancy theory and operator algebra. Given the importance of the γ2 norm in computer science and the extensive work in mathematics, we believe our result will have further applications.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","arxiv":1,"publication_identifier":{"eisbn":["9781611977912"]},"day":"04","ec_funded":1,"acknowledgement":"This  project  has  received  funding  from  the  European  Research  Council  (ERC)under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No.101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and the AustrianScience Fund (FWF) project Z 422-N, project “Static and Dynamic Hierarchical Graph Decompositions”, I 5982-N, andproject “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the netideeSCIENCE  Stiftung,  2020–2024.   JU’s  research  was  funded  by  the  Decanal  Research  Grant.   We  thank  the  anonymousreviewers for their useful feedback and pointing us to the results in Matousek et al","scopus_import":"1","date_updated":"2025-04-14T13:50:49Z","_id":"15253","page":"995-1018","type":"conference","oa":1,"date_published":"2024-01-04T00:00:00Z","publication":"Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms","publication_status":"published","corr_author":"1","citation":{"mla":"Henzinger, Monika, et al. “A Unifying Framework for Differentially Private Sums under Continual Observation.” <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 2024, Society for Industrial and Applied Mathematics, 2024, pp. 995–1018, doi:<a href=\"https://doi.org/10.1137/1.9781611977912.38\">10.1137/1.9781611977912.38</a>.","apa":"Henzinger, M., Upadhyay, J., &#38; Upadhyay, S. (2024). A unifying framework for differentially private sums under continual observation. In <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 2024, pp. 995–1018). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977912.38\">https://doi.org/10.1137/1.9781611977912.38</a>","ieee":"M. Henzinger, J. Upadhyay, and S. Upadhyay, “A unifying framework for differentially private sums under continual observation,” in <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Alexandria, VA, United States, 2024, vol. 2024, pp. 995–1018.","ista":"Henzinger M, Upadhyay J, Upadhyay S. 2024. A unifying framework for differentially private sums under continual observation. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2024, 995–1018.","chicago":"Henzinger, Monika, Jalaj Upadhyay, and Sarvagya Upadhyay. “A Unifying Framework for Differentially Private Sums under Continual Observation.” In <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2024:995–1018. Society for Industrial and Applied Mathematics, 2024. <a href=\"https://doi.org/10.1137/1.9781611977912.38\">https://doi.org/10.1137/1.9781611977912.38</a>.","short":"M. Henzinger, J. Upadhyay, S. Upadhyay, in:, Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2024, pp. 995–1018.","ama":"Henzinger M, Upadhyay J, Upadhyay S. A unifying framework for differentially private sums under continual observation. In: <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 2024. Society for Industrial and Applied Mathematics; 2024:995-1018. doi:<a href=\"https://doi.org/10.1137/1.9781611977912.38\">10.1137/1.9781611977912.38</a>"},"intvolume":"      2024","quality_controlled":"1","conference":{"location":"Alexandria, VA, United States","end_date":"2024-01-10","start_date":"2024-01-07","name":"SODA: Symposium on Discrete Algorithms"},"status":"public","doi":"10.1137/1.9781611977912.38","department":[{"_id":"MoHe"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2307.08970"}],"title":"A unifying framework for differentially private sums under continual observation","language":[{"iso":"eng"}],"month":"01","year":"2024","publisher":"Society for Industrial and Applied Mathematics","volume":2024,"project":[{"name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer"}],"author":[{"last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Upadhyay","full_name":"Upadhyay, Jalaj","first_name":"Jalaj"},{"full_name":"Upadhyay, Sarvagya","first_name":"Sarvagya","last_name":"Upadhyay"}],"article_processing_charge":"No"},{"project":[{"call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422","name":"Efficient algorithms"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer"}],"year":"2024","publisher":"Society for Industrial and Applied Mathematics","language":[{"iso":"eng"}],"title":"Deterministic near-linear time minimum cut in weighted graphs","month":"01","status":"public","doi":"10.1137/1.9781611977912.111","department":[{"_id":"MoHe"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2401.05627"}],"author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"full_name":"Li, Jason","first_name":"Jason","last_name":"Li"},{"last_name":"Rao","full_name":"Rao, Satish","first_name":"Satish"},{"full_name":"Wang, Di","first_name":"Di","last_name":"Wang"}],"article_processing_charge":"No","OA_type":"free access","date_updated":"2025-06-24T12:09:26Z","_id":"18503","acknowledgement":"This project has received funding from the European Research Council(ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDyn-Struct)” and the Austrian Science Fund (FWF) project Z 422-N, project “Static and Dynamic Hierarchical Graph Decompositions”, I 5982-N, and project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.","ec_funded":1,"scopus_import":"1","arxiv":1,"oa_version":"Preprint","publication_identifier":{"eisbn":["9781611977912"]},"day":"04","date_created":"2024-11-04T10:54:21Z","external_id":{"arxiv":["2401.05627"]},"abstract":[{"text":"In 1996, Karger [Kar96] gave a startling randomized algorithm that finds a minimum-cut in a (weighted) graph in time O(m log3 n) which he termed near-linear time meaning linear (in the size of the input) times a polylogarthmic factor. In this paper, we give the first deterministic algorithm which runs in near-linear time for weighted graphs.\r\nPreviously, the breakthrough results of Kawarabayashi and Thorup [KT19] gave a near-linear time algorithm for simple graphs (which was improved to have running time O(m log2 n log log n) in [HRW20].) The main technique here is a clustering procedure that perfectly preserves minimum cuts. Recently, Li [Li21] gave an m1+o(1) deterministic minimum-cut algorithm for weighted graphs; this form of running time has been termed “almost-linear”. Li uses almost-linear time deterministic expander decompositions which do not perfectly preserve minimum cuts, but he can use these clusterings to, in a sense, “derandomize” the methods of Karger.\r\nIn terms of techniques, we provide a structural theorem that says there exists a sparse clustering that preserves minimum cuts in a weighted graph with o(1) error. In addition, we construct it deterministically in near linear time. This was done exactly for simple graphs in [KT19, HRW20] and with polylogarithmic error for weighted graphs in [Li21]. Extending the techniques in [KT19, HRW20] to weighted graphs presents significant challenges, and moreover, the algorithm can only polylogarithmically approximately preserve minimum cuts. A remaining challenge is to reduce the polylogarithmic-approximate clusterings to 1 + o(1/ log n)-approximate so that they can be applied recursively as in [Li21] over O(log n) many levels. This is an additional challenge that requires building on properties of tree-packings in the presence of a wide range of edge weights to, for example, find sources for local flow computations which identify minimum cuts that cross clusters.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","conference":{"name":"SODA: Symposium on Discrete Algorithms","location":"Alexandria, VA,  United States","end_date":"2024-01-10","start_date":"2024-01-07"},"corr_author":"1","citation":{"mla":"Henzinger, Monika, et al. “Deterministic Near-Linear Time Minimum Cut in Weighted Graphs.” <i>35th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2024, pp. 3089–139, doi:<a href=\"https://doi.org/10.1137/1.9781611977912.111\">10.1137/1.9781611977912.111</a>.","chicago":"Henzinger, Monika, Jason Li, Satish Rao, and Di Wang. “Deterministic Near-Linear Time Minimum Cut in Weighted Graphs.” In <i>35th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 3089–3139. Society for Industrial and Applied Mathematics, 2024. <a href=\"https://doi.org/10.1137/1.9781611977912.111\">https://doi.org/10.1137/1.9781611977912.111</a>.","ista":"Henzinger M, Li J, Rao S, Wang D. 2024. Deterministic near-linear time minimum cut in weighted graphs. 35th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 3089–3139.","ieee":"M. Henzinger, J. Li, S. Rao, and D. Wang, “Deterministic near-linear time minimum cut in weighted graphs,” in <i>35th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Alexandria, VA,  United States, 2024, pp. 3089–3139.","apa":"Henzinger, M., Li, J., Rao, S., &#38; Wang, D. (2024). Deterministic near-linear time minimum cut in weighted graphs. In <i>35th Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 3089–3139). Alexandria, VA,  United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977912.111\">https://doi.org/10.1137/1.9781611977912.111</a>","ama":"Henzinger M, Li J, Rao S, Wang D. Deterministic near-linear time minimum cut in weighted graphs. In: <i>35th Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2024:3089-3139. doi:<a href=\"https://doi.org/10.1137/1.9781611977912.111\">10.1137/1.9781611977912.111</a>","short":"M. Henzinger, J. Li, S. Rao, D. Wang, in:, 35th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2024, pp. 3089–3139."},"publication":"35th Annual ACM-SIAM Symposium on Discrete Algorithms","publication_status":"published","OA_place":"repository","page":"3089-3139","type":"conference","oa":1,"date_published":"2024-01-04T00:00:00Z"},{"citation":{"short":"K. Hanauer, M. Henzinger, R. Münk, H. Räcke, M. Vötsch, in:, Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, ACM, 2024, pp. 1016–1027.","ama":"Hanauer K, Henzinger M, Münk R, Räcke H, Vötsch M. Expander hierarchies for normalized cuts on graphs. In: <i>Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining</i>. ACM; 2024:1016-1027. doi:<a href=\"https://doi.org/10.1145/3637528.3671978\">10.1145/3637528.3671978</a>","apa":"Hanauer, K., Henzinger, M., Münk, R., Räcke, H., &#38; Vötsch, M. (2024). Expander hierarchies for normalized cuts on graphs. In <i>Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining</i> (pp. 1016–1027). Barcelona, Spain: ACM. <a href=\"https://doi.org/10.1145/3637528.3671978\">https://doi.org/10.1145/3637528.3671978</a>","ista":"Hanauer K, Henzinger M, Münk R, Räcke H, Vötsch M. 2024. Expander hierarchies for normalized cuts on graphs. Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. KDD: Knowledge Discovery and Data Mining, 1016–1027.","ieee":"K. Hanauer, M. Henzinger, R. Münk, H. Räcke, and M. Vötsch, “Expander hierarchies for normalized cuts on graphs,” in <i>Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining</i>, Barcelona, Spain, 2024, pp. 1016–1027.","chicago":"Hanauer, Kathrin, Monika Henzinger, Robin Münk, Harald Räcke, and Maximilian Vötsch. “Expander Hierarchies for Normalized Cuts on Graphs.” In <i>Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining</i>, 1016–27. ACM, 2024. <a href=\"https://doi.org/10.1145/3637528.3671978\">https://doi.org/10.1145/3637528.3671978</a>.","mla":"Hanauer, Kathrin, et al. “Expander Hierarchies for Normalized Cuts on Graphs.” <i>Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining</i>, ACM, 2024, pp. 1016–27, doi:<a href=\"https://doi.org/10.1145/3637528.3671978\">10.1145/3637528.3671978</a>."},"isi":1,"quality_controlled":"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"},"conference":{"start_date":"2024-08-05","location":"Barcelona, Spain","end_date":"2024-08-29","name":"KDD: Knowledge Discovery and Data Mining"},"OA_place":"publisher","page":"1016-1027","type":"conference","oa":1,"date_published":"2024-09-01T00:00:00Z","publication":"Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","publication_status":"published","acknowledgement":"Monika Henzinger: This project has received funding from the European Research\r\nCouncil (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nHarald Räcke, Robin Münk: This project has received funding from the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 498605858 and 470029389.","ec_funded":1,"scopus_import":"1","file":[{"date_created":"2025-01-27T13:25:23Z","relation":"main_file","file_name":"2024_ACMKDD_Hanauer.pdf","checksum":"1265d5cf6aa5f94157631651723c4a2b","access_level":"open_access","file_size":1450331,"creator":"dernst","date_updated":"2025-01-27T13:25:23Z","content_type":"application/pdf","success":1,"file_id":"18907"}],"file_date_updated":"2025-01-27T13:25:23Z","date_updated":"2025-09-09T12:04:56Z","_id":"18906","date_created":"2025-01-27T13:20:26Z","external_id":{"isi":["001324524201013"]},"ddc":["000"],"abstract":[{"lang":"eng","text":"Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their adoption in practice has been hindered due to their inherent intricacies and large hidden factors in their asymptotic running times. Here, we introduce the first practically efficient algorithm for computing expander decompositions and their hierarchies and demonstrate its effectiveness and utility by incorporating it as the core component in a novel solver for the normalized cut graph clustering objective.\r\nOur extensive experiments on a variety of large graphs show that our expander-based algorithm outperforms state-of-the-art solvers for normalized cut with respect to solution quality by a large margin on a variety of graph classes such as citation, e-mail, and social networks or web graphs while remaining competitive in running time."}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa_version":"Published Version","publication_identifier":{"isbn":["9798400704901"]},"day":"01","author":[{"first_name":"Kathrin","full_name":"Hanauer, Kathrin","last_name":"Hanauer"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"full_name":"Münk, Robin","first_name":"Robin","last_name":"Münk"},{"first_name":"Harald","full_name":"Räcke, Harald","last_name":"Räcke"},{"first_name":"Maximilian","full_name":"Vötsch, Maximilian","last_name":"Vötsch"}],"article_processing_charge":"Yes (in subscription journal)","OA_type":"hybrid","publisher":"ACM","year":"2024","project":[{"call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564"},{"name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"status":"public","department":[{"_id":"MoHe"}],"doi":"10.1145/3637528.3671978","has_accepted_license":"1","title":"Expander hierarchies for normalized cuts on graphs","language":[{"iso":"eng"}],"month":"09"},{"year":"2024","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564"},{"name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer"}],"volume":287,"department":[{"_id":"MoHe"}],"doi":"10.4230/LIPIcs.ITCS.2024.62","status":"public","month":"01","has_accepted_license":"1","language":[{"iso":"eng"}],"title":"On the complexity of algorithms with predictions for dynamic graph problems","article_processing_charge":"Yes","author":[{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger"},{"first_name":"Barna","full_name":"Saha, Barna","last_name":"Saha"},{"last_name":"Seybold","first_name":"Martin P.","full_name":"Seybold, Martin P."},{"last_name":"Ye","first_name":"Christopher","full_name":"Ye, Christopher"}],"OA_type":"gold","scopus_import":"1","ec_funded":1,"acknowledgement":"Henzinger, Monika: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) project Z 422-N, project I 5982-N, and project P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020-2024.\r\nSaha, Barna: This project is partially supported by NSF grants 1652303, 1909046, 2112533, and HDR TRIPODS Phase II grant 2217058.\r\nWe would like to thank Andrea Lincoln for many helpful discussions and insightful comments.","_id":"18928","file_date_updated":"2025-01-27T15:33:24Z","file":[{"access_level":"open_access","checksum":"15085a5b3697a408b92a4a7a27293927","relation":"main_file","file_name":"2024_LIPICs_HenzingerMo.pdf","date_created":"2025-01-27T15:33:24Z","file_id":"18929","date_updated":"2025-01-27T15:33:24Z","success":1,"content_type":"application/pdf","creator":"dernst","file_size":1084372}],"date_updated":"2025-09-09T12:11:33Z","abstract":[{"text":"Algorithms with predictions is a new research direction that leverages machine learned predictions for algorithm design. So far a plethora of recent works have incorporated predictions to improve on worst-case bounds for online problems. In this paper, we initiate the study of complexity of dynamic data structures with predictions, including dynamic graph algorithms. Unlike online algorithms, the goal in dynamic data structures is to maintain the solution efficiently with every update.\r\nWe investigate three natural models of prediction: (1) δ-accurate predictions where each predicted request matches the true request with probability δ, (2) list-accurate predictions where a true request comes from a list of possible requests, and (3) bounded delay predictions where the true requests are a permutation of the predicted requests. We give general reductions among the prediction models, showing that bounded delay is the strongest prediction model, followed by list-accurate, and δ-accurate.\r\nFurther, we identify two broad problem classes based on lower bounds due to the Online Matrix Vector (OMv) conjecture. Specifically, we show that locally correctable dynamic problems have strong conditional lower bounds for list-accurate predictions that are equivalent to the non-prediction setting, unless list-accurate predictions are perfect. Moreover, we show that locally reducible dynamic problems have time complexity that degrades gracefully with the quality of bounded delay predictions. We categorize problems with known OMv lower bounds accordingly and give several upper bounds in the delay model that show that our lower bounds are almost tight.\r\nWe note that concurrent work by v.d.Brand et al. [SODA '24] and Liu and Srinivas [arXiv:2307.08890] independently study dynamic graph algorithms with predictions, but their work is mostly focused on showing upper bounds.","lang":"eng"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","external_id":{"isi":["001300389400062"],"arxiv":["2307.16771"]},"date_created":"2025-01-27T15:33:42Z","ddc":["000"],"publication_identifier":{"isbn":["9783959773096"],"eissn":["1868-8969"]},"day":"24","arxiv":1,"oa_version":"Published Version","intvolume":"       287","alternative_title":["LIPIcs"],"corr_author":"1","isi":1,"citation":{"chicago":"Henzinger, Monika, Barna Saha, Martin P. Seybold, and Christopher Ye. “On the Complexity of Algorithms with Predictions for Dynamic Graph Problems.” In <i>15th Innovations in Theoretical Computer Science Conference</i>, 287:62:1-62:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.62\">https://doi.org/10.4230/LIPIcs.ITCS.2024.62</a>.","ieee":"M. Henzinger, B. Saha, M. P. Seybold, and C. Ye, “On the complexity of algorithms with predictions for dynamic graph problems,” in <i>15th Innovations in Theoretical Computer Science Conference</i>, Berkeley, CA, United States, 2024, vol. 287, p. 62:1-62:25.","ista":"Henzinger M, Saha B, Seybold MP, Ye C. 2024. On the complexity of algorithms with predictions for dynamic graph problems. 15th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 287, 62:1-62:25.","apa":"Henzinger, M., Saha, B., Seybold, M. P., &#38; Ye, C. (2024). On the complexity of algorithms with predictions for dynamic graph problems. In <i>15th Innovations in Theoretical Computer Science Conference</i> (Vol. 287, p. 62:1-62:25). Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.62\">https://doi.org/10.4230/LIPIcs.ITCS.2024.62</a>","mla":"Henzinger, Monika, et al. “On the Complexity of Algorithms with Predictions for Dynamic Graph Problems.” <i>15th Innovations in Theoretical Computer Science Conference</i>, vol. 287, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 62:1-62:25, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.62\">10.4230/LIPIcs.ITCS.2024.62</a>.","ama":"Henzinger M, Saha B, Seybold MP, Ye C. On the complexity of algorithms with predictions for dynamic graph problems. In: <i>15th Innovations in Theoretical Computer Science Conference</i>. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:62:1-62:25. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.62\">10.4230/LIPIcs.ITCS.2024.62</a>","short":"M. Henzinger, B. Saha, M.P. Seybold, C. Ye, in:, 15th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 62:1-62:25."},"quality_controlled":"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"},"conference":{"name":"ITCS: Innovations in Theoretical Computer Science","location":"Berkeley, CA, United States","end_date":"2024-02-02","start_date":"2024-01-30"},"oa":1,"date_published":"2024-01-24T00:00:00Z","OA_place":"publisher","type":"conference","page":"62:1-62:25","publication_status":"published","publication":"15th Innovations in Theoretical Computer Science Conference"},{"publication_identifier":{"issn":["1049-5258"]},"day":"20","oa_version":"Preprint","arxiv":1,"abstract":[{"text":"Differential privacy with gradual expiration models the setting where data items\r\narrive in a stream and at a given time t the privacy loss guaranteed for a data item\r\nseen at time (t − d) is εg(d), where g is a monotonically non-decreasing function.\r\nWe study the fundamental continual (binary) counting problem where each data\r\nitem consists of a bit, and the algorithm needs to output at each time step the sum of\r\nall the bits streamed so far. For a stream of length T and privacy without expiration\r\ncontinual counting is possible with maximum (over all time steps) additive error\r\nO(log2\r\n(T)/ε) and the best known lower bound is Ω(log(T)/ε); closing this gap\r\nis a challenging open problem.\r\nWe show that the situation is very different for privacy with gradual expiration by\r\ngiving upper and lower bounds for a large set of expiration functions g. Specifically,\r\nour algorithm achieves an additive error of O(log(T)/ε) for a large set of privacy\r\nexpiration functions. We also give a lower bound that shows that if C is the additive\r\nerror of any ε-DP algorithm for this problem, then the product of C and the privacy\r\nexpiration function after 2C steps must be Ω(log(T)/ε). Our algorithm matches\r\nthis lower bound as its additive error is O(log(T)/ε), even when g(2C) = O(1).\r\nOur empirical evaluation shows that we achieve a slowly growing privacy loss\r\nwith significantly smaller empirical privacy loss for large values of d than a natural\r\nbaseline algorithm.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["2406.03802"]},"date_created":"2025-04-06T22:01:32Z","_id":"19512","date_updated":"2025-05-14T11:33:22Z","scopus_import":"1","ec_funded":1,"acknowledgement":"Monika Henzinger: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024. Joel Daniel Andersson and Rasmus Pagh are affiliated with Basic Algorithms Research Copenhagen (BARC), supported by the VILLUM Foundation grant 16582, and are also supported by Providentia, a Data Science Distinguished Investigator grant from Novo Nordisk Fonden. Teresa Anna Steiner is supported by a research grant (VIL51463) from VILLUM FONDEN. This work was done while Teresa Anna Steiner was a Postdoc at the Technical University of Denmark. Jalaj Upadhyay’s research was funded by the Rutgers Decanal Grant no. 302918 and an unrestricted gift from Google.","publication_status":"published","publication":"38th Conference on Neural Information Processing Systems","oa":1,"date_published":"2024-12-20T00:00:00Z","OA_place":"repository","type":"conference","quality_controlled":"1","conference":{"name":"NeurIPS: Neural Information Processing Systems","start_date":"2024-12-09","end_date":"2024-12-15","location":"Vancouver, Canada"},"intvolume":"        37","alternative_title":["Advances in Neural Information Processing Systems"],"corr_author":"1","citation":{"ama":"Andersson JD, Henzinger M, Pagh R, Steiner TA, Upadhyay J. Continual counting with gradual privacy expiration. In: <i>38th Conference on Neural Information Processing Systems</i>. Vol 37. Neural Information Processing Systems Foundation; 2024.","short":"J.D. Andersson, M. Henzinger, R. Pagh, T.A. Steiner, J. Upadhyay, in:, 38th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2024.","mla":"Andersson, Joel Daniel, et al. “Continual Counting with Gradual Privacy Expiration.” <i>38th Conference on Neural Information Processing Systems</i>, vol. 37, Neural Information Processing Systems Foundation, 2024.","chicago":"Andersson, Joel Daniel, Monika Henzinger, Rasmus Pagh, Teresa Anna Steiner, and Jalaj Upadhyay. “Continual Counting with Gradual Privacy Expiration.” In <i>38th Conference on Neural Information Processing Systems</i>, Vol. 37. Neural Information Processing Systems Foundation, 2024.","apa":"Andersson, J. D., Henzinger, M., Pagh, R., Steiner, T. A., &#38; Upadhyay, J. (2024). Continual counting with gradual privacy expiration. In <i>38th Conference on Neural Information Processing Systems</i> (Vol. 37). Vancouver, Canada: Neural Information Processing Systems Foundation.","ieee":"J. D. Andersson, M. Henzinger, R. Pagh, T. A. Steiner, and J. Upadhyay, “Continual counting with gradual privacy expiration,” in <i>38th Conference on Neural Information Processing Systems</i>, Vancouver, Canada, 2024, vol. 37.","ista":"Andersson JD, Henzinger M, Pagh R, Steiner TA, Upadhyay J. 2024. Continual counting with gradual privacy expiration. 38th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 37."},"month":"12","language":[{"iso":"eng"}],"title":"Continual counting with gradual privacy expiration","department":[{"_id":"MoHe"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2406.03802"}],"status":"public","project":[{"grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422","name":"Efficient algorithms"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"volume":37,"year":"2024","publisher":"Neural Information Processing Systems Foundation","OA_type":"green","article_processing_charge":"No","author":[{"last_name":"Andersson","full_name":"Andersson, Joel Daniel","first_name":"Joel Daniel"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger"},{"first_name":"Rasmus","full_name":"Pagh, Rasmus","last_name":"Pagh"},{"last_name":"Steiner","full_name":"Steiner, Teresa Anna","first_name":"Teresa Anna"},{"full_name":"Upadhyay, Jalaj","first_name":"Jalaj","last_name":"Upadhyay"}]},{"project":[{"name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564"},{"name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"},{"grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020"}],"volume":235,"year":"2024","publisher":"ML Research Press","month":"09","language":[{"iso":"eng"}],"title":"Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2402.17327"}],"department":[{"_id":"MoHe"}],"status":"public","article_processing_charge":"No","author":[{"first_name":"Kyriakos","full_name":"Axiotis, Kyriakos","last_name":"Axiotis"},{"last_name":"Cohen-Addad","first_name":"Vincent","full_name":"Cohen-Addad, Vincent"},{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger"},{"last_name":"Jerome","full_name":"Jerome, Sammy","first_name":"Sammy"},{"first_name":"Vahab","full_name":"Mirrokni, Vahab","last_name":"Mirrokni"},{"last_name":"Saulpic","id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964","first_name":"David","full_name":"Saulpic, David"},{"full_name":"Woodruff, David P.","first_name":"David P.","last_name":"Woodruff"},{"last_name":"Wunder","full_name":"Wunder, Michael","first_name":"Michael"}],"_id":"18115","date_updated":"2026-06-18T18:00:19Z","scopus_import":"1","ec_funded":1,"acknowledgement":"Monika Henzinger: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024. This work was partially done while David Saulpic was at the Institute for Science and Technology, Austria (ISTA). David Sauplic has received funding from the European Union’s Horizon 2020 research and innovation programme under the\r\nMarie Sklodowska-Curie grant agreement No 101034413. Work was done while David Woodruff was visiting Google Research.","day":"01","publication_identifier":{"eissn":["2640-3498"]},"arxiv":1,"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"We study the data selection problem, whose aim is to select a small representative subset of data that can be used to efficiently train a machine learning model. We present a new data selection approach based on k-means clustering and sensitivity sampling. Assuming access to an embedding representation of the data with respect to which the model loss is Holder continuous, our approach provably allows selecting a set of “typical” k+1/ε2 elements whose average loss corresponds to the average loss of the whole dataset, up to a multiplicative (1±ε)\r\n factor and an additive ελΦk, where Φk represents the k-means cost for the input embeddings and λ is the Holder constant. We furthermore demonstrate the performance and scalability of our approach on fine-tuning foundation models and show that it outperforms state-of-the-art methods. We also show how it can be applied on linear regression, leading to a new sampling strategy that surprisingly matches the performance of leverage score sampling, while being conceptually simpler and more scalable.","lang":"eng"}],"ddc":["000"],"date_created":"2024-09-22T22:01:44Z","external_id":{"arxiv":["2402.17327"]},"quality_controlled":"1","conference":{"name":"ICML: International Conference on Machine Learning","location":"Vienna, Austria","end_date":"2024-07-27","start_date":"2024-07-21"},"alternative_title":["PMLR"],"intvolume":"       235","citation":{"ama":"Axiotis K, Cohen-Addad V, Henzinger M, et al. Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond. In: <i>Proceedings of the 41st International Conference on Machine Learning</i>. Vol 235. ML Research Press; 2024:2086-2107.","short":"K. Axiotis, V. Cohen-Addad, M. Henzinger, S. Jerome, V. Mirrokni, D. Saulpic, D.P. Woodruff, M. Wunder, in:, Proceedings of the 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 2086–2107.","chicago":"Axiotis, Kyriakos, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David P. Woodruff, and Michael Wunder. “Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond.” In <i>Proceedings of the 41st International Conference on Machine Learning</i>, 235:2086–2107. ML Research Press, 2024.","apa":"Axiotis, K., Cohen-Addad, V., Henzinger, M., Jerome, S., Mirrokni, V., Saulpic, D., … Wunder, M. (2024). Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond. In <i>Proceedings of the 41st International Conference on Machine Learning</i> (Vol. 235, pp. 2086–2107). Vienna, Austria: ML Research Press.","ista":"Axiotis K, Cohen-Addad V, Henzinger M, Jerome S, Mirrokni V, Saulpic D, Woodruff DP, Wunder M. 2024. Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond. Proceedings of the 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 2086–2107.","ieee":"K. Axiotis <i>et al.</i>, “Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond,” in <i>Proceedings of the 41st International Conference on Machine Learning</i>, Vienna, Austria, 2024, vol. 235, pp. 2086–2107.","mla":"Axiotis, Kyriakos, et al. “Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond.” <i>Proceedings of the 41st International Conference on Machine Learning</i>, vol. 235, ML Research Press, 2024, pp. 2086–107."},"publication_status":"published","publication":"Proceedings of the 41st International Conference on Machine Learning","date_published":"2024-09-01T00:00:00Z","oa":1,"type":"conference","page":"2086-2107"},{"arxiv":1,"oa_version":"Published Version","day":"01","publication_identifier":{"eissn":["2640-3498"]},"date_created":"2024-09-22T22:01:44Z","external_id":{"arxiv":["2406.11649"]},"ddc":["000"],"abstract":[{"text":"As a staple of data analysis and unsupervised learning, the problem of private clustering has been widely studied, under various privacy models. Centralized differential privacy is the first of them, and the problem has also been studied for the local and the shuffle variation. In each case, the goal is to design an algorithm that computes privately a clustering, with the smallest possible error. The study of each variation gave rise to new algorithm: the landscape of private clustering algorithm is therefore quite intricate. In this paper, we show that a 20 year-old algorithm can be slightly modified to work for any of those models. This provides a unified picture: while matching almost all previously known results, it allows us to improve some of them, and extend to a new privacy model, the continual observation setting, where the input is changing over time and the algorithm must output a new solution at each time step.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-06-18T18:01:02Z","_id":"18116","ec_funded":1,"acknowledgement":"Monika Henzinger: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024.This work was partially done while David Saulpic was at the Institute for Science and Technology, Austria (ISTA). David Sauplic has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 101034413.","scopus_import":"1","publication":"Proceedings of the 41st International Conference on Machine Learning","publication_status":"published","page":"12046-12086","type":"conference","oa":1,"date_published":"2024-09-01T00:00:00Z","quality_controlled":"1","conference":{"start_date":"2024-07-21","end_date":"2024-07-27","location":"Vienna, Austria","name":"ICML: International Conference on Machine Learning"},"corr_author":"1","citation":{"short":"M.D. La Tour, M. Henzinger, D. Saulpic, in:, Proceedings of the 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 12046–12086.","ama":"La Tour MD, Henzinger M, Saulpic D. Making old things new: A unified algorithm for differentially private clustering. In: <i>Proceedings of the 41st International Conference on Machine Learning</i>. Vol 235. ML Research Press; 2024:12046-12086.","ista":"La Tour MD, Henzinger M, Saulpic D. 2024. Making old things new: A unified algorithm for differentially private clustering. Proceedings of the 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 12046–12086.","ieee":"M. D. La Tour, M. Henzinger, and D. Saulpic, “Making old things new: A unified algorithm for differentially private clustering,” in <i>Proceedings of the 41st International Conference on Machine Learning</i>, Vienna, Austria, 2024, vol. 235, pp. 12046–12086.","apa":"La Tour, M. D., Henzinger, M., &#38; Saulpic, D. (2024). Making old things new: A unified algorithm for differentially private clustering. In <i>Proceedings of the 41st International Conference on Machine Learning</i> (Vol. 235, pp. 12046–12086). Vienna, Austria: ML Research Press.","chicago":"La Tour, Max Dupré, Monika Henzinger, and David Saulpic. “Making Old Things New: A Unified Algorithm for Differentially Private Clustering.” In <i>Proceedings of the 41st International Conference on Machine Learning</i>, 235:12046–86. ML Research Press, 2024.","mla":"La Tour, Max Dupré, et al. “Making Old Things New: A Unified Algorithm for Differentially Private Clustering.” <i>Proceedings of the 41st International Conference on Machine Learning</i>, vol. 235, ML Research Press, 2024, pp. 12046–86."},"intvolume":"       235","alternative_title":["PMLR"],"title":"Making old things new: A unified algorithm for differentially private clustering","language":[{"iso":"eng"}],"month":"09","status":"public","department":[{"_id":"MoHe"}],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2406.11649","open_access":"1"}],"volume":235,"project":[{"grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"name":"Efficient algorithms","grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"},{"call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413"}],"publisher":"ML Research Press","year":"2024","author":[{"last_name":"La Tour","first_name":"Max Dupré","full_name":"La Tour, Max Dupré"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger"},{"last_name":"Saulpic","full_name":"Saulpic, David","id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964","first_name":"David"}],"article_processing_charge":"No"},{"oa":1,"date_published":"2024-09-16T00:00:00Z","type":"conference","publication_status":"published","article_number":"40","publication":"International Conference on Approximation Algorithms for Combinatorial Optimization Problems ","intvolume":"       317","alternative_title":["LIPIcs"],"corr_author":"1","isi":1,"citation":{"mla":"Henzinger, Monika, et al. “Private Counting of Distinct Elements in the Turnstile Model and Extensions.” <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i>, vol. 317, 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40\">10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>.","chicago":"Henzinger, Monika, A. R. Sricharan, and Teresa Anna Steiner. “Private Counting of Distinct Elements in the Turnstile Model and Extensions.” In <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i>, Vol. 317. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40\">https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>.","ista":"Henzinger M, Sricharan AR, Steiner TA. 2024. Private counting of distinct elements in the turnstile model and extensions. International Conference on Approximation Algorithms for Combinatorial Optimization Problems . APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems, LIPIcs, vol. 317, 40.","apa":"Henzinger, M., Sricharan, A. R., &#38; Steiner, T. A. (2024). Private counting of distinct elements in the turnstile model and extensions. In <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i> (Vol. 317). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40\">https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>","ieee":"M. Henzinger, A. R. Sricharan, and T. A. Steiner, “Private counting of distinct elements in the turnstile model and extensions,” in <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i>, London, United Kingdom, 2024, vol. 317.","ama":"Henzinger M, Sricharan AR, Steiner TA. Private counting of distinct elements in the turnstile model and extensions. In: <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i>. Vol 317. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40\">10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>","short":"M. Henzinger, A.R. Sricharan, T.A. Steiner, in:, International Conference on Approximation Algorithms for Combinatorial Optimization Problems , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024."},"conference":{"name":"APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems","start_date":"2024-08-27","location":"London, United Kingdom","end_date":"2024-08-30"},"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","abstract":[{"lang":"eng","text":"Privately counting distinct elements in a stream is a fundamental data analysis problem with many applications in machine learning. In the turnstile model, Jain et al. [NeurIPS2023] initiated the study of this problem parameterized by the maximum flippancy of any element, i.e., the number of times that the count of an element changes from 0 to above 0 or vice versa. They give an item-level (ε,δ)-differentially private algorithm whose additive error is tight with respect to that parameterization. In this work, we show that a very simple algorithm based on the sparse vector technique achieves a tight additive error for item-level (ε,δ)-differential privacy and item-level ε-differential privacy with regards to a different parameterization, namely the sum of all flippancies. Our second result is a bound which shows that for a large class of algorithms, including all existing differentially private algorithms for this problem, the lower bound from item-level differential privacy extends to event-level differential privacy. This partially answers an open question by Jain et al. [NeurIPS2023]."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["2408.11637"],"isi":["001545634500040"]},"date_created":"2024-09-29T22:01:38Z","ddc":["000"],"publication_identifier":{"isbn":["9783959773485"],"issn":["1868-8969"]},"day":"16","oa_version":"Published Version","arxiv":1,"scopus_import":"1","ec_funded":1,"acknowledgement":"Monika Henzinger: This project has received funding from the European Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct,No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nTeresa Anna Steiner: Supported by a research grant (VIL51463) from VILLUM FONDEN.","_id":"18156","file":[{"file_name":"2024_LIPICs_HenzingerM.pdf","relation":"main_file","date_created":"2024-10-01T10:07:14Z","checksum":"c08b41c896e4d8c69570044808b40e0b","access_level":"open_access","creator":"dernst","file_size":973917,"file_id":"18166","date_updated":"2024-10-01T10:07:14Z","content_type":"application/pdf","success":1}],"file_date_updated":"2024-10-01T10:07:14Z","date_updated":"2025-12-02T13:47:16Z","article_processing_charge":"No","author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger"},{"last_name":"Sricharan","full_name":"Sricharan, A. R.","first_name":"A. R."},{"first_name":"Teresa Anna","full_name":"Steiner, Teresa Anna","last_name":"Steiner"}],"doi":"10.4230/LIPIcs.APPROX/RANDOM.2024.40","department":[{"_id":"MoHe"}],"status":"public","month":"09","has_accepted_license":"1","title":"Private counting of distinct elements in the turnstile model and extensions","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2024","project":[{"call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564"},{"grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"}],"volume":317}]