--- OA_place: repository OA_type: green _id: '21719' abstract: - lang: eng text: "We develop a new algorithmic framework for designing approximation algorithms for cut-based optimization problems on capacitated undirected graphs that undergo edge insertions and deletions. Specifically, our framework dynamically maintains a variant of the hierarchical \U0001D457-tree decomposition of [Madry FOCS’10], achieving a poly-logarithmic approximation factor to the graph’s cut structure and supporting edge updates in \U0001D442⁡(\U0001D45B\U0001D700) amortized update time, for any arbitrarily small constant \U0001D700 ∈(0,1).\r\nConsequently, we obtain new trade-offs between approximation and update/query time for fundamental cut-based optimization problems in the fully dynamic setting, including all-pairs minimum cuts, sparsest cut, multi-way cut, and multi-cut. For the last three problems, these trade-offs give the first fully-dynamic algorithms achieving poly-logarithmic approximation in sub-linear time per operation.\r\nThe main technical ingredient behind our dynamic hierarchy is a dynamic cut-sparsifier algorithm that can handle vertex splits with low recourse. This is achieved by white-boxing the dynamic cut sparsifier construction of [Abraham et al. FOCS’16], based on forest packing, together with new structural insights about the maintenance of these forests under vertex splits. Given the versatility of cut sparsification in both the static and dynamic graph algorithms literature, we believe this construction may be of independent interest." acknowledgement: "Monika Henzinger: Funded by the European union. Views and opinions expressed\r\nare however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. 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/I5982. For open access purposes, the author has applied a CC BY public copyright license to any author accepted manuscript version arising from this submission.\r\nPeter Kiss: This research was funded in whole or in part by the Austrian Science Fund (FWF)\r\n10.55776/ESP6088024." article_processing_charge: No arxiv: 1 author: - first_name: Gramoz full_name: Goranci, Gramoz last_name: Goranci - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Peter full_name: Kiss, Peter last_name: Kiss - first_name: Ali full_name: Momeni, Ali last_name: Momeni - first_name: Gernot full_name: Zöcklein, Gernot id: 45d5e826-47af-11f1-84e5-ba87c23fe681 last_name: Zöcklein citation: ama: 'Goranci G, Henzinger M, Kiss P, Momeni A, Zöcklein G. Dynamic hierarchical j-tree decomposition and its applications. In: Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms. Vol 2026-January. Society for Industrial and Applied Mathematics; 2026:1128-1180. doi:10.1137/1.9781611978971.45' apa: Goranci, G., Henzinger, M., Kiss, P., Momeni, A., & Zöcklein, G. (2026). Dynamic hierarchical j-tree decomposition and its applications. In Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms (Vol. 2026–January, pp. 1128–1180). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611978971.45 chicago: Goranci, Gramoz, Monika Henzinger, Peter Kiss, Ali Momeni, and Gernot Zöcklein. “Dynamic Hierarchical J-Tree Decomposition and Its Applications.” In Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms, 2026–January:1128–80. Society for Industrial and Applied Mathematics, 2026. https://doi.org/10.1137/1.9781611978971.45. ieee: G. Goranci, M. Henzinger, P. Kiss, A. Momeni, and G. Zöcklein, “Dynamic hierarchical j-tree decomposition and its applications,” in Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms, 2026, vol. 2026–January, pp. 1128–1180. ista: 'Goranci G, Henzinger M, Kiss P, Momeni A, Zöcklein G. 2026. Dynamic hierarchical j-tree decomposition and its applications. Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2026–January, 1128–1180.' mla: Goranci, Gramoz, et al. “Dynamic Hierarchical J-Tree Decomposition and Its Applications.” Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms, vol. 2026–January, Society for Industrial and Applied Mathematics, 2026, pp. 1128–80, doi:10.1137/1.9781611978971.45. short: G. Goranci, M. Henzinger, P. Kiss, A. Momeni, G. Zöcklein, in:, Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2026, pp. 1128–1180. conference: name: 'SODA: Symposium on Discrete Algorithms' date_created: 2026-04-12T22:01:51Z date_published: 2026-01-07T00:00:00Z date_updated: 2026-05-04T11:54:09Z day: '07' department: - _id: MoHe doi: 10.1137/1.9781611978971.45 ec_funded: 1 external_id: arxiv: - '2601.09139' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2601.09139 month: '01' oa: 1 oa_version: Preprint page: 1128-1180 project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions publication: Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms publication_identifier: eissn: - '15579468' isbn: - '9781611978971' issn: - '10719040' publication_status: published publisher: Society for Industrial and Applied Mathematics quality_controlled: '1' scopus_import: '1' status: public title: Dynamic hierarchical j-tree decomposition and its applications type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 2026-January year: '2026' ... --- OA_place: repository OA_type: green _id: '21720' abstract: - lang: eng text: "We present an exact fully-dynamic minimum cut algorithm that runs in \U0001D45B\U0001D45C⁡(1) deterministic update time when the minimum cut size is at most 2Θ⁡(log3/4−\U0001D450⁡\U0001D45B) for any \U0001D450 >0, improving on the previous algorithm of Jin, Sun, and Thorup (SODA 2024) whose minimum cut size limit is (log⁡\U0001D45B)\U0001D45C⁡(1). Combined with graph sparsification, we obtain the first (1 +\U0001D716)-approximate fully-dynamic minimum cut algorithm on weighted graphs, for any \U0001D716 ≥2−Θ⁡(log3/4−\U0001D450⁡\U0001D45B), in \U0001D45B\U0001D45C⁡(1) randomized update time.\r\nOur main technical contribution is a deterministic local minimum cut algorithm, which replaces the randomized LocalKCut procedure from El-Hayek, Henzinger, and Li (SODA 2025)." acknowledgement: Funded by the European union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. 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/I5982. For open access purposes, the author has applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission. article_processing_charge: No arxiv: 1 author: - first_name: Antoine full_name: El-Hayek, Antoine id: 888a098e-fcac-11ee-aff7-d347be57b725 last_name: El-Hayek orcid: 0000-0003-4268-7368 - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Jason full_name: Li, Jason last_name: Li citation: ama: 'El-Hayek A, Henzinger M, Li J. Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time. In: Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms. Vol 2026. Society for Industrial and Applied Mathematics; 2026:613-663. doi:10.1137/1.9781611978971.25' apa: 'El-Hayek, A., Henzinger, M., & Li, J. (2026). Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time. In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms (Vol. 2026, pp. 613–663). Vancouver, Canada: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611978971.25' chicago: El-Hayek, Antoine, Monika Henzinger, and Jason Li. “Deterministic and Exact Fully-Dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time.” In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, 2026:613–63. Society for Industrial and Applied Mathematics, 2026. https://doi.org/10.1137/1.9781611978971.25. ieee: A. El-Hayek, M. Henzinger, and J. Li, “Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time,” in Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, Vancouver, Canada, 2026, vol. 2026, pp. 613–663. ista: 'El-Hayek A, Henzinger M, Li J. 2026. Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time. Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2026, 613–663.' mla: El-Hayek, Antoine, et al. “Deterministic and Exact Fully-Dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time.” Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, vol. 2026, Society for Industrial and Applied Mathematics, 2026, pp. 613–63, doi:10.1137/1.9781611978971.25. short: A. El-Hayek, M. Henzinger, J. Li, in:, Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2026, pp. 613–663. conference: end_date: 2026-01-14 location: Vancouver, Canada name: 'SODA: Symposium on Discrete Algorithms' start_date: 2026-01-11 date_created: 2026-04-12T22:01:51Z date_published: 2026-01-07T00:00:00Z date_updated: 2026-05-04T11:36:47Z day: '07' department: - _id: MoHe - _id: GradSch doi: 10.1137/1.9781611978971.25 ec_funded: 1 external_id: arxiv: - '2512.13105' intvolume: ' 2026' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2512.13105 month: '01' oa: 1 oa_version: Preprint page: 613-663 project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions publication: Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms publication_identifier: eisbn: - '9781611978971' eissn: - 1557-9468 issn: - 1071-9040 publication_status: published publisher: Society for Industrial and Applied Mathematics quality_controlled: '1' scopus_import: '1' status: public title: Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 2026 year: '2026' ... --- OA_place: publisher OA_type: gold _id: '19858' 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." 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." alternative_title: - LIPIcs article_number: '4' article_processing_charge: No arxiv: 1 author: - first_name: Antoine full_name: El-Hayek, Antoine id: 888a098e-fcac-11ee-aff7-d347be57b725 last_name: El-Hayek orcid: 0000-0003-4268-7368 - first_name: Kathrin full_name: Hanauer, Kathrin last_name: Hanauer - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 citation: ama: 'El-Hayek A, Hanauer K, Henzinger M. On b-matching and fully-dynamic maximum k-edge coloring. In: 4th Symposium on Algorithmic Foundations of Dynamic Networks. Vol 330. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.SAND.2025.4' apa: 'El-Hayek, A., Hanauer, K., & Henzinger, M. (2025). On b-matching and fully-dynamic maximum k-edge coloring. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (Vol. 330). Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SAND.2025.4' chicago: El-Hayek, Antoine, Kathrin Hanauer, and Monika Henzinger. “On B-Matching and Fully-Dynamic Maximum k-Edge Coloring.” In 4th Symposium on Algorithmic Foundations of Dynamic Networks, Vol. 330. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.SAND.2025.4. ieee: A. El-Hayek, K. Hanauer, and M. Henzinger, “On b-matching and fully-dynamic maximum k-edge coloring,” in 4th Symposium on Algorithmic Foundations of Dynamic Networks, 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.' mla: El-Hayek, Antoine, et al. “On B-Matching and Fully-Dynamic Maximum k-Edge Coloring.” 4th Symposium on Algorithmic Foundations of Dynamic Networks, vol. 330, 4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.SAND.2025.4. 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. conference: end_date: 2025-06-11 location: Liverpool, United Kingdom name: 'SAND: Symposium on Algorithmic Foundations of Dynamic Networks' start_date: 2025-06-09 corr_author: '1' date_created: 2025-06-22T22:02:06Z date_published: 2025-06-02T00:00:00Z date_updated: 2025-09-30T13:37:28Z day: '02' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.SAND.2025.4 ec_funded: 1 external_id: arxiv: - '2310.01149' isi: - '001532136900004' file: - access_level: open_access checksum: ad93a1e052adb29d7bfe8bd551bab193 content_type: application/pdf creator: dernst date_created: 2025-06-23T11:23:29Z date_updated: 2025-06-23T11:23:29Z file_id: '19872' file_name: 2025_LIPIcs_ElHayek.pdf file_size: 995666 relation: main_file success: 1 file_date_updated: 2025-06-23T11:23:29Z has_accepted_license: '1' intvolume: ' 330' isi: 1 language: - iso: eng month: '06' oa: 1 oa_version: Published Version project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' 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 - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer publication: 4th Symposium on Algorithmic Foundations of Dynamic Networks publication_identifier: isbn: - '9783959773683' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: On b-matching and fully-dynamic maximum k-edge coloring tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 volume: 330 year: '2025' ... --- OA_place: repository OA_type: green _id: '19982' abstract: - lang: eng 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." 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. article_processing_charge: No arxiv: 1 author: - first_name: Antoine full_name: El-Hayek, Antoine id: 888a098e-fcac-11ee-aff7-d347be57b725 last_name: El-Hayek orcid: 0000-0003-4268-7368 - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Jason full_name: Li, Jason last_name: Li citation: ama: 'El-Hayek A, Henzinger M, Li J. Fully dynamic approximate minimum cut in subpolynomial time per operation. In: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2025:750-784. doi:10.1137/1.9781611978322.22' apa: 'El-Hayek, A., Henzinger, M., & Li, J. (2025). Fully dynamic approximate minimum cut in subpolynomial time per operation. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 750–784). New Orleans, LA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611978322.22' chicago: El-Hayek, Antoine, Monika Henzinger, and Jason Li. “Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation.” In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 750–84. Society for Industrial and Applied Mathematics, 2025. https://doi.org/10.1137/1.9781611978322.22. ieee: A. El-Hayek, M. Henzinger, and J. Li, “Fully dynamic approximate minimum cut in subpolynomial time per operation,” in Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, United States, 2025, pp. 750–784. 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.' mla: El-Hayek, Antoine, et al. “Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation.” Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2025, pp. 750–84, doi:10.1137/1.9781611978322.22. 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. conference: end_date: 2025-01-15 location: New Orleans, LA, United States name: 'SODA: Symposium on Discrete Algorithms' start_date: 2025-01-12 corr_author: '1' date_created: 2025-07-10T13:08:57Z date_published: 2025-01-07T00:00:00Z date_updated: 2025-12-29T12:30:04Z day: '07' department: - _id: MoHe doi: 10.1137/1.9781611978322.22 ec_funded: 1 external_id: arxiv: - '2412.15069' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2412.15069 month: '01' oa: 1 oa_version: Preprint page: 750-784 project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' 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 - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer publication: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms publication_identifier: eisbn: - '9781611978322' publication_status: published publisher: Society for Industrial and Applied Mathematics quality_controlled: '1' status: public title: Fully dynamic approximate minimum cut in subpolynomial time per operation type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2025' ... --- OA_place: publisher OA_type: hybrid _id: '20051' abstract: - lang: eng text: "We revisit the majority problem in the population protocol communication model, as first studied by Angluin et al. (Distributed Computing 2008). We consider a more general version of this problem known as plurality consensus, which has already been studied intensively in the literature. In this problem, each node in a system of n nodes, has initially one of k different opinions, and they need to agree on the (relative) majority opinion. In particular, we consider the important and intensively studied model of Undecided State Dynamics.\r\nOur main contribution is an almost tight lower bound on the stabilization time: we prove that there exists an initial configuration, even with bias \\Delta = \\omega(\\sqrt{n\\log n}), where stabilization requires \\Omega(kn\\log \\frac {\\sqrt n} {k \\log n}) interactions, or equivalently, \\Omega(k\\log \\frac {\\sqrt n} {k \\log n}) parallel time for any k = o\\left(\\frac {\\sqrt n}{\\log n}\\right). This bound is tight for any k \\le n^{\\frac 1 2 - \\epsilon}, where \\epsilon >0 can be any small constant, as Amir et al.~(PODC'23) gave a O(k\\log n) parallel time upper bound for k = O\\left(\\frac {\\sqrt n} {\\log ^2 n}\\right)." acknowledgement: "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/I5862,grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with\r\nadditional funding from the netidee SCIENCE Stiftung, 2020–2024\r\nand the German Research Foundation (DFG), grant 470029389\r\n(FlexNets)." article_processing_charge: Yes (via OA deal) arxiv: 1 author: - first_name: Antoine full_name: El-Hayek, Antoine id: 888a098e-fcac-11ee-aff7-d347be57b725 last_name: El-Hayek orcid: 0000-0003-4268-7368 - first_name: Robert full_name: Elsässer, Robert last_name: Elsässer - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid citation: ama: 'El-Hayek A, Elsässer R, Schmid S. An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model. In: Proceedings of the ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery; 2025. doi:10.1145/3732772.3733505' apa: 'El-Hayek, A., Elsässer, R., & Schmid, S. (2025). An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model. In Proceedings of the ACM Symposium on Principles of Distributed Computing. Huatulco, Mexico: Association for Computing Machinery. https://doi.org/10.1145/3732772.3733505' chicago: El-Hayek, Antoine, Robert Elsässer, and Stefan Schmid. “An Almost Tight Lower Bound for Plurality Consensus with Undecided State Dynamics in the Population Protocol Model.” In Proceedings of the ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, 2025. https://doi.org/10.1145/3732772.3733505. ieee: A. El-Hayek, R. Elsässer, and S. Schmid, “An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model,” in Proceedings of the ACM Symposium on Principles of Distributed Computing, Huatulco, Mexico, 2025. ista: 'El-Hayek A, Elsässer R, Schmid S. 2025. An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model. Proceedings of the ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing.' mla: El-Hayek, Antoine, et al. “An Almost Tight Lower Bound for Plurality Consensus with Undecided State Dynamics in the Population Protocol Model.” Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2025, doi:10.1145/3732772.3733505. short: A. El-Hayek, R. Elsässer, S. Schmid, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2025. conference: end_date: 2025-06-20 location: Huatulco, Mexico name: 'PODC: Symposium on Principles of Distributed Computing' start_date: 2025-06-16 corr_author: '1' date_created: 2025-07-21T08:16:15Z date_published: 2025-06-13T00:00:00Z date_updated: 2025-10-16T13:08:45Z day: '13' ddc: - '000' department: - _id: MoHe doi: 10.1145/3732772.3733505 ec_funded: 1 external_id: arxiv: - '2505.02765' isi: - '001525534800066' file: - access_level: open_access checksum: 52976d226f3f691aa519d71c1c718fa5 content_type: application/pdf creator: dernst date_created: 2025-08-04T09:10:55Z date_updated: 2025-08-04T09:10:55Z file_id: '20115' file_name: 2025_PODC_ElHayek.pdf file_size: 2200347 relation: main_file success: 1 file_date_updated: 2025-08-04T09:10:55Z has_accepted_license: '1' isi: 1 language: - iso: eng month: '06' oa: 1 oa_version: Published Version project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _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 publication: Proceedings of the ACM Symposium on Principles of Distributed Computing publication_identifier: isbn: - ' 9798400718854' publication_status: published publisher: Association for Computing Machinery quality_controlled: '1' status: public title: An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2025' ... --- OA_place: publisher OA_type: hybrid _id: '20052' abstract: - lang: eng text: "This paper revisits a fundamental distributed computing problem in the population protocol model. Provided n agents each starting with an input color in [k], the relative majority problem asks to find the predominant color. In the population protocol model, at each time step, a scheduler selects two agents that first learn each other's states and then update their states based on what they learned.\r\nWe present the Circles protocol that solves the relative majority problem with k3 states. It is always-correct under weakly fair scheduling. Not only does it improve upon the best known upper bound of O(k7), but it also shows a strikingly simpler design inspired by energy minimization in chemical settings." acknowledgement: '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/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024 and the German Research Foundation (DFG), grant 470029389 (FlexNets). ' article_processing_charge: No author: - first_name: Tom-Lukas full_name: Breitkopf, Tom-Lukas last_name: Breitkopf - first_name: Julien full_name: Dallot, Julien last_name: Dallot - first_name: Antoine full_name: El-Hayek, Antoine id: 888a098e-fcac-11ee-aff7-d347be57b725 last_name: El-Hayek orcid: 0000-0003-4268-7368 - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid citation: ama: 'Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols. In: Proceedings of the ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery; 2025:549-552. doi:10.1145/3732772.3733512' apa: 'Breitkopf, T.-L., Dallot, J., El-Hayek, A., & Schmid, S. (2025). Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols. In Proceedings of the ACM Symposium on Principles of Distributed Computing (pp. 549–552). Huatulco, Mexico: Association for Computing Machinery. https://doi.org/10.1145/3732772.3733512' chicago: 'Breitkopf, Tom-Lukas, Julien Dallot, Antoine El-Hayek, and Stefan Schmid. “Brief Announcement: Minimizing Energy Solves Relative Majority with a Cubic Number of States in Population Protocols.” In Proceedings of the ACM Symposium on Principles of Distributed Computing, 549–52. Association for Computing Machinery, 2025. https://doi.org/10.1145/3732772.3733512.' ieee: 'T.-L. Breitkopf, J. Dallot, A. El-Hayek, and S. Schmid, “Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols,” in Proceedings of the ACM Symposium on Principles of Distributed Computing, Huatulco, Mexico, 2025, pp. 549–552.' ista: 'Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. 2025. Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols. Proceedings of the ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 549–552.' mla: 'Breitkopf, Tom-Lukas, et al. “Brief Announcement: Minimizing Energy Solves Relative Majority with a Cubic Number of States in Population Protocols.” Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2025, pp. 549–52, doi:10.1145/3732772.3733512.' short: T.-L. Breitkopf, J. Dallot, A. El-Hayek, S. Schmid, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2025, pp. 549–552. conference: end_date: 2025-06-20 location: Huatulco, Mexico name: 'PODC: Symposium on Principles of Distributed Computing' start_date: 2025-06-16 corr_author: '1' date_created: 2025-07-21T08:17:04Z date_published: 2025-06-13T00:00:00Z date_updated: 2026-02-16T11:46:37Z day: '13' ddc: - '000' department: - _id: MoHe doi: 10.1145/3732772.3733512 ec_funded: 1 external_id: isi: - '001525534800069' file: - access_level: open_access checksum: e99679ffb28877b7cea4d54860302790 content_type: application/pdf creator: dernst date_created: 2025-08-05T07:32:01Z date_updated: 2025-08-05T07:32:01Z file_id: '20123' file_name: 2025_PODC_Breitkopf.pdf file_size: 549706 relation: main_file success: 1 file_date_updated: 2025-08-05T07:32:01Z has_accepted_license: '1' isi: 1 language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: 549-552 project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _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 publication: Proceedings of the ACM Symposium on Principles of Distributed Computing publication_identifier: isbn: - '9798400718854' publication_status: published publisher: Association for Computing Machinery quality_controlled: '1' status: public title: 'Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2025' ... --- OA_place: repository OA_type: green _id: '20301' 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}). " 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." alternative_title: - PMLR article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: A. R. full_name: Sricharan, A. R. last_name: Sricharan - first_name: Teresa Anna full_name: Steiner, Teresa Anna last_name: Steiner citation: ama: 'Henzinger M, Sricharan AR, Steiner TA. Differentially private continual release of histograms and related queries. In: The 28th International Conference on Artificial Intelligence and Statistics. Vol 258. ML Research Press; 2025:1990-1998.' apa: 'Henzinger, M., Sricharan, A. R., & Steiner, T. A. (2025). Differentially private continual release of histograms and related queries. In The 28th International Conference on Artificial Intelligence and Statistics (Vol. 258, pp. 1990–1998). Mai Khao, Thailand: ML Research Press.' chicago: Henzinger, Monika, A. R. Sricharan, and Teresa Anna Steiner. “Differentially Private Continual Release of Histograms and Related Queries.” In The 28th International Conference on Artificial Intelligence and Statistics, 258:1990–98. ML Research Press, 2025. ieee: M. Henzinger, A. R. Sricharan, and T. A. Steiner, “Differentially private continual release of histograms and related queries,” in The 28th International Conference on Artificial Intelligence and Statistics, Mai Khao, Thailand, 2025, vol. 258, pp. 1990–1998. 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.' mla: Henzinger, Monika, et al. “Differentially Private Continual Release of Histograms and Related Queries.” The 28th International Conference on Artificial Intelligence and Statistics, vol. 258, ML Research Press, 2025, pp. 1990–98. 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. conference: end_date: 2025-05-05 location: Mai Khao, Thailand name: 'AISTATS: Conference on Artificial Intelligence and Statistics' start_date: 2025-05-03 date_created: 2025-09-07T22:01:35Z date_published: 2025-05-01T00:00:00Z date_updated: 2025-09-09T07:09:22Z day: '01' department: - _id: MoHe ec_funded: 1 external_id: arxiv: - '2302.11341' intvolume: ' 258' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2302.11341 month: '05' oa: 1 oa_version: Preprint page: 1990-1998 project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' 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 - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer publication: The 28th International Conference on Artificial Intelligence and Statistics publication_identifier: eissn: - 2640-3498 publication_status: published publisher: ML Research Press quality_controlled: '1' scopus_import: '1' status: public title: Differentially private continual release of histograms and related queries type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 258 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '20534' abstract: - lang: eng 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." 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.' article_number: '36' article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Evangelos full_name: Kosinas, Evangelos id: 4c7f9625-dbbc-11ee-9d86-bdcc2db5a949 last_name: Kosinas - first_name: Robin full_name: Münk, Robin last_name: Münk - first_name: Harald full_name: Räcke, Harald last_name: Räcke citation: ama: 'Henzinger M, Kosinas E, Münk R, Räcke H. Efficient contractions of dynamic graphs - with applications. In: 33rd Annual European Symposium on Algorithms. Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.ESA.2025.36' apa: 'Henzinger, M., Kosinas, E., Münk, R., & Räcke, H. (2025). Efficient contractions of dynamic graphs - with applications. In 33rd Annual European Symposium on Algorithms (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2025.36' chicago: Henzinger, Monika, Evangelos Kosinas, Robin Münk, and Harald Räcke. “Efficient Contractions of Dynamic Graphs - with Applications.” In 33rd Annual European Symposium on Algorithms, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.ESA.2025.36. ieee: M. Henzinger, E. Kosinas, R. Münk, and H. Räcke, “Efficient contractions of dynamic graphs - with applications,” in 33rd Annual European Symposium on Algorithms, 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.' mla: Henzinger, Monika, et al. “Efficient Contractions of Dynamic Graphs - with Applications.” 33rd Annual European Symposium on Algorithms, vol. 351, 36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.ESA.2025.36. 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. conference: end_date: 2025-09-17 location: Warsaw, Poland name: 'ESA: European Symposium on Algorithms' start_date: 2025-09-15 corr_author: '1' date_created: 2025-10-26T23:01:34Z date_published: 2025-10-01T00:00:00Z date_updated: 2025-10-27T08:05:46Z day: '01' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.ESA.2025.36 ec_funded: 1 external_id: arxiv: - '2509.05157' file: - access_level: open_access checksum: d2daf9a467e96fb5e7084a8a85321776 content_type: application/pdf creator: dernst date_created: 2025-10-27T08:03:36Z date_updated: 2025-10-27T08:03:36Z file_id: '20542' file_name: 2025_LIPIcs.ESA_HenzingerM.pdf file_size: 934846 relation: main_file success: 1 file_date_updated: 2025-10-27T08:03:36Z has_accepted_license: '1' intvolume: ' 351' language: - iso: eng month: '10' oa: 1 oa_version: Published Version project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' 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 publication: 33rd Annual European Symposium on Algorithms publication_identifier: isbn: - '9783959773959' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Efficient contractions of dynamic graphs - with applications tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 351 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '20535' 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." 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." alternative_title: - LIPIcs article_number: '91' article_processing_charge: No arxiv: 1 author: - first_name: Laxman full_name: Dhulipala, Laxman last_name: Dhulipala - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: George Z. full_name: Li, George Z. last_name: Li - first_name: Quanquan C. full_name: Liu, Quanquan C. last_name: Liu - first_name: A. R. full_name: Sricharan, A. R. last_name: Sricharan - first_name: Leqi full_name: Zhu, Leqi id: a2117c59-cee4-11ed-b9d0-874ecf0f8ac5 last_name: Zhu citation: 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: 33rd Annual European Symposium on Algorithms. Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.ESA.2025.91' apa: 'Dhulipala, L., Henzinger, M., Li, G. Z., Liu, Q. C., Sricharan, A. R., & Zhu, L. (2025). Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism. In 33rd Annual European Symposium on Algorithms (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2025.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 33rd Annual European Symposium on Algorithms, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.ESA.2025.91. 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 33rd Annual European Symposium on Algorithms, 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.' mla: Dhulipala, Laxman, et al. “Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism.” 33rd Annual European Symposium on Algorithms, vol. 351, 91, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.ESA.2025.91. 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. conference: end_date: 2025-09-17 location: Warsaw, Poland name: 'ESA: European Symposium on Algorithms' start_date: 2025-09-15 corr_author: '1' date_created: 2025-10-26T23:01:35Z date_published: 2025-10-01T00:00:00Z date_updated: 2025-10-27T07:02:06Z day: '01' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.ESA.2025.91 ec_funded: 1 external_id: arxiv: - '2508.02182' file: - access_level: open_access checksum: 19146e935b5b6ad5d33c8d08280ad8e7 content_type: application/pdf creator: dernst date_created: 2025-10-27T06:58:43Z date_updated: 2025-10-27T06:58:43Z file_id: '20539' file_name: 2025_LIPIcs.ESA_Dhulipala.pdf file_size: 870317 relation: main_file success: 1 file_date_updated: 2025-10-27T06:58:43Z has_accepted_license: '1' intvolume: ' 351' language: - iso: eng month: '10' oa: 1 oa_version: Published Version project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' 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 publication: 33rd Annual European Symposium on Algorithms publication_identifier: isbn: - '9783959773959' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 351 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '20536' 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." 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." alternative_title: - LIPIcs article_number: '47' article_processing_charge: No arxiv: 1 author: - first_name: Roodabeh full_name: Safavi Hemami, Roodabeh id: 72ed2640-8972-11ed-ae7b-f9c81ec75154 last_name: Safavi Hemami - first_name: Martin P. full_name: Seybold, Martin P. last_name: Seybold citation: ama: 'Safavi Hemami R, Seybold MP. B-Treaps revised: Write efficient randomized block search trees with high load. In: 19th International Symposium on Algorithms and Data Structures. Vol 349. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.WADS.2025.47' apa: 'Safavi Hemami, R., & Seybold, M. P. (2025). B-Treaps revised: Write efficient randomized block search trees with high load. In 19th International Symposium on Algorithms and Data Structures (Vol. 349). Toronto, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.WADS.2025.47' chicago: 'Safavi Hemami, Roodabeh, and Martin P. Seybold. “B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load.” In 19th International Symposium on Algorithms and Data Structures, Vol. 349. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.WADS.2025.47.' ieee: 'R. Safavi Hemami and M. P. Seybold, “B-Treaps revised: Write efficient randomized block search trees with high load,” in 19th International Symposium on Algorithms and Data Structures, 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.' mla: 'Safavi Hemami, Roodabeh, and Martin P. Seybold. “B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load.” 19th International Symposium on Algorithms and Data Structures, vol. 349, 47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.WADS.2025.47.' short: R. Safavi Hemami, M.P. Seybold, in:, 19th International Symposium on Algorithms and Data Structures, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. conference: end_date: 2025-08-15 location: Toronto, Canada name: 'WADS: Algorithms and Data Structures Symposium' start_date: 2025-08-11 corr_author: '1' date_created: 2025-10-26T23:01:35Z date_published: 2025-08-29T00:00:00Z date_updated: 2025-10-27T07:10:49Z day: '29' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.WADS.2025.47 ec_funded: 1 external_id: arxiv: - '2303.04722' file: - access_level: open_access checksum: 196af33762831a78e87f4f95ecd8677b content_type: application/pdf creator: dernst date_created: 2025-10-27T07:09:41Z date_updated: 2025-10-27T07:09:41Z file_id: '20540' file_name: 2025_LIPIcs.WADS_Safavi.pdf file_size: 1081870 relation: main_file success: 1 file_date_updated: 2025-10-27T07:09:41Z has_accepted_license: '1' intvolume: ' 349' language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _id: 34def286-11ca-11ed-8bc3-da5948e1613c grant_number: Z00422 name: Efficient algorithms - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer publication: 19th International Symposium on Algorithms and Data Structures publication_identifier: isbn: - '9783959773980' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: 'B-Treaps revised: Write efficient randomized block search trees with high load' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 349 year: '2025' ... --- OA_place: repository OA_type: green _id: '19038' 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. 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.' article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Jalaj full_name: Upadhyay, Jalaj last_name: Upadhyay citation: ama: 'Henzinger M, Upadhyay J. Improved differentially private continual observation using group algebra. In: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 5. Association for Computing Machinery; 2025:2951-2970. doi:10.1137/1.9781611978322.95' apa: 'Henzinger, M., & Upadhyay, J. (2025). Improved differentially private continual observation using group algebra. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 5, pp. 2951–2970). New Orleans, LA, United States: Association for Computing Machinery. https://doi.org/10.1137/1.9781611978322.95' chicago: Henzinger, Monika, and Jalaj Upadhyay. “Improved Differentially Private Continual Observation Using Group Algebra.” In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 5:2951–70. Association for Computing Machinery, 2025. https://doi.org/10.1137/1.9781611978322.95. ieee: M. Henzinger and J. Upadhyay, “Improved differentially private continual observation using group algebra,” in Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, United States, 2025, vol. 5, pp. 2951–2970. 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.” Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 5, Association for Computing Machinery, 2025, pp. 2951–70, doi:10.1137/1.9781611978322.95. 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. conference: end_date: 2025-01-15 location: New Orleans, LA, United States name: 'SODA: Symposium on Discrete Algorithms' start_date: 2025-01-12 date_created: 2025-02-17T09:31:03Z date_published: 2025-01-20T00:00:00Z date_updated: 2025-04-14T13:50:49Z day: '20' department: - _id: MoHe doi: 10.1137/1.9781611978322.95 ec_funded: 1 external_id: arxiv: - '2412.02840' intvolume: ' 5' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2412.02840 month: '01' oa: 1 oa_version: Preprint page: 2951 - 2970 project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' 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 - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer publication: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms publication_identifier: isbn: - 979-833131200-8 issn: - 1071-9040 publication_status: published publisher: Association for Computing Machinery quality_controlled: '1' scopus_import: '1' status: public title: Improved differentially private continual observation using group algebra type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 5 year: '2025' ... --- OA_place: repository OA_type: green _id: '15121' abstract: - lang: eng text: We present an auction algorithm using multiplicative instead of constant weight updates to compute a (1-E)-approximate maximum weight matching (MWM) in a bipartite graph with n vertices and m edges in time 0(mE-1), beating the running time of the fastest known approximation algorithm of Duan and Pettie [JACM ’14] that runs in 0(mE-1 log E-1). Our algorithm is very simple and it can be extended to give a dynamic data structure that maintains a (1-E)-approximate maximum weight matching under (1) one-sided vertex deletions (with incident edges) and (2) one-sided vertex insertions (with incident edges sorted by weight) to the other side. The total time time used is 0(mE-1), where m is the sum of the number of initially existing and inserted edges. acknowledgement: The first author thanks Chandra Chekuri for useful discussions about this paper. This work was done in part at the University of Vienna. 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 from the Austrian Science Fund (FWF) project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024. article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Da Wei full_name: Zheng, Da Wei last_name: Zheng - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 citation: ama: Zheng DW, Henzinger M. Multiplicative auction algorithm for approximate maximum weight bipartite matching. Mathematical Programming. 2025;210:881-894. doi:10.1007/s10107-024-02066-3 apa: Zheng, D. W., & Henzinger, M. (2025). Multiplicative auction algorithm for approximate maximum weight bipartite matching. Mathematical Programming. Springer Nature. https://doi.org/10.1007/s10107-024-02066-3 chicago: Zheng, Da Wei, and Monika Henzinger. “Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching.” Mathematical Programming. Springer Nature, 2025. https://doi.org/10.1007/s10107-024-02066-3. ieee: D. W. Zheng and M. Henzinger, “Multiplicative auction algorithm for approximate maximum weight bipartite matching,” Mathematical Programming, vol. 210. Springer Nature, pp. 881–894, 2025. ista: Zheng DW, Henzinger M. 2025. Multiplicative auction algorithm for approximate maximum weight bipartite matching. Mathematical Programming. 210, 881–894. mla: Zheng, Da Wei, and Monika Henzinger. “Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching.” Mathematical Programming, vol. 210, Springer Nature, 2025, pp. 881–94, doi:10.1007/s10107-024-02066-3. short: D.W. Zheng, M. Henzinger, Mathematical Programming 210 (2025) 881–894. corr_author: '1' date_created: 2024-03-17T23:00:58Z date_published: 2025-03-01T00:00:00Z date_updated: 2025-09-09T12:39:58Z day: '01' department: - _id: MoHe doi: 10.1007/s10107-024-02066-3 ec_funded: 1 external_id: arxiv: - '2301.09217' isi: - '001176048100003' intvolume: ' 210' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2301.09217 month: '03' oa: 1 oa_version: Preprint page: 881-894 project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer publication: Mathematical Programming publication_identifier: eissn: - 1436-4646 issn: - 0025-5610 publication_status: published publisher: Springer Nature quality_controlled: '1' related_material: record: - id: '13236' relation: earlier_version status: public scopus_import: '1' status: public title: Multiplicative auction algorithm for approximate maximum weight bipartite matching type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 210 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '21280' 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. 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." alternative_title: - LIPIcs article_processing_charge: No arxiv: 1 author: - first_name: Gramoz full_name: Goranci, Gramoz last_name: Goranci - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Harald full_name: Räcke, Harald last_name: Räcke - first_name: A. full_name: Sricharan, A. last_name: Sricharan citation: ama: 'Goranci G, Henzinger M, Räcke H, Sricharan A. Incremental approximate maximum flow via residual graph sparsification. In: 52nd International Colloquium on Automata, Languages, and Programming. Vol 334. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025:91:1-91:20. doi:10.4230/lipics.icalp.2025.91' apa: 'Goranci, G., Henzinger, M., Räcke, H., & Sricharan, A. (2025). Incremental approximate maximum flow via residual graph sparsification. In 52nd International Colloquium on Automata, Languages, and Programming (Vol. 334, p. 91:1-91:20). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.icalp.2025.91' chicago: Goranci, Gramoz, Monika Henzinger, Harald Räcke, and A. Sricharan. “Incremental Approximate Maximum Flow via Residual Graph Sparsification.” In 52nd International Colloquium on Automata, Languages, and Programming, 334:91:1-91:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/lipics.icalp.2025.91. ieee: G. Goranci, M. Henzinger, H. Räcke, and A. Sricharan, “Incremental approximate maximum flow via residual graph sparsification,” in 52nd International Colloquium on Automata, Languages, and Programming, Aarhus, Denmark, 2025, vol. 334, p. 91:1-91:20. 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.' mla: Goranci, Gramoz, et al. “Incremental Approximate Maximum Flow via Residual Graph Sparsification.” 52nd International Colloquium on Automata, Languages, and Programming, vol. 334, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 91:1-91:20, doi:10.4230/lipics.icalp.2025.91. 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. conference: end_date: 2025-07-11 location: Aarhus, Denmark name: 'ICALP: Automata, Languages and Programming' start_date: 2025-07-08 corr_author: '1' date_created: 2026-02-17T08:26:06Z date_published: 2025-06-30T00:00:00Z date_updated: 2026-02-18T09:06:12Z day: '30' ddc: - '000' department: - _id: MoHe doi: 10.4230/lipics.icalp.2025.91 ec_funded: 1 external_id: arxiv: - '2502.09105' file: - access_level: open_access checksum: c178cf554e44204b9f64ebd9b54cf7ba content_type: application/pdf creator: dernst date_created: 2026-02-18T09:02:33Z date_updated: 2026-02-18T09:02:33Z file_id: '21315' file_name: 2025_ICALP_Goranci.pdf file_size: 944824 relation: main_file success: 1 file_date_updated: 2026-02-18T09:02:33Z has_accepted_license: '1' intvolume: ' 334' language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: 91:1-91:20 project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' 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 - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer publication: 52nd International Colloquium on Automata, Languages, and Programming publication_identifier: isbn: - '9783959773720' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Incremental approximate maximum flow via residual graph sparsification tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 334 year: '2025' ... --- _id: '18115' abstract: - lang: eng 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." 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." alternative_title: - PMLR article_processing_charge: No arxiv: 1 author: - first_name: Kyriakos full_name: Axiotis, Kyriakos last_name: Axiotis - first_name: Vincent full_name: Cohen-Addad, Vincent last_name: Cohen-Addad - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Sammy full_name: Jerome, Sammy last_name: Jerome - first_name: Vahab full_name: Mirrokni, Vahab last_name: Mirrokni - first_name: David full_name: Saulpic, David id: f8e48cf0-b0ff-11ed-b0e9-b4c35598f964 last_name: Saulpic - first_name: David P. full_name: Woodruff, David P. last_name: Woodruff - first_name: Michael full_name: Wunder, Michael last_name: Wunder citation: ama: 'Axiotis K, Cohen-Addad V, Henzinger M, et al. Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond. In: Proceedings of the 41st International Conference on Machine Learning. Vol 235. ML Research Press; 2024:2086-2107.' 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 Proceedings of the 41st International Conference on Machine Learning (Vol. 235, pp. 2086–2107). Vienna, Austria: ML Research Press.' 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 Proceedings of the 41st International Conference on Machine Learning, 235:2086–2107. ML Research Press, 2024.' ieee: 'K. Axiotis et al., “Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond,” in Proceedings of the 41st International Conference on Machine Learning, Vienna, Austria, 2024, vol. 235, pp. 2086–2107.' 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.' mla: 'Axiotis, Kyriakos, et al. “Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond.” Proceedings of the 41st International Conference on Machine Learning, vol. 235, ML Research Press, 2024, pp. 2086–107.' 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. conference: end_date: 2024-07-27 location: Vienna, Austria name: 'ICML: International Conference on Machine Learning' start_date: 2024-07-21 date_created: 2024-09-22T22:01:44Z date_published: 2024-09-01T00:00:00Z date_updated: 2025-04-14T13:50:50Z day: '01' department: - _id: MoHe ec_funded: 1 external_id: arxiv: - '2402.17327' intvolume: ' 235' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2402.17327 month: '09' oa: 1 oa_version: Published Version page: 2086-2107 project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' 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 - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer - _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c call_identifier: H2020 grant_number: '101034413' name: 'IST-BRIDGE: International postdoctoral program' publication: Proceedings of the 41st International Conference on Machine Learning publication_identifier: eissn: - 2640-3498 publication_status: published publisher: ML Research Press quality_controlled: '1' scopus_import: '1' status: public title: 'Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 235 year: '2024' ... --- _id: '18116' abstract: - lang: eng 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.' 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.' alternative_title: - PMLR article_processing_charge: No arxiv: 1 author: - first_name: Max Dupré full_name: La Tour, Max Dupré last_name: La Tour - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: David full_name: Saulpic, David id: f8e48cf0-b0ff-11ed-b0e9-b4c35598f964 last_name: Saulpic citation: ama: 'La Tour MD, Henzinger M, Saulpic D. Making old things new: A unified algorithm for differentially private clustering. In: Proceedings of the 41st International Conference on Machine Learning. Vol 235. ML Research Press; 2024:12046-12086.' apa: 'La Tour, M. D., Henzinger, M., & Saulpic, D. (2024). Making old things new: A unified algorithm for differentially private clustering. In Proceedings of the 41st International Conference on Machine Learning (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 Proceedings of the 41st International Conference on Machine Learning, 235:12046–86. ML Research Press, 2024.' ieee: 'M. D. La Tour, M. Henzinger, and D. Saulpic, “Making old things new: A unified algorithm for differentially private clustering,” in Proceedings of the 41st International Conference on Machine Learning, Vienna, Austria, 2024, vol. 235, pp. 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.' mla: 'La Tour, Max Dupré, et al. “Making Old Things New: A Unified Algorithm for Differentially Private Clustering.” Proceedings of the 41st International Conference on Machine Learning, vol. 235, ML Research Press, 2024, pp. 12046–86.' 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. conference: end_date: 2024-07-27 location: Vienna, Austria name: 'ICML: International Conference on Machine Learning' start_date: 2024-07-21 corr_author: '1' date_created: 2024-09-22T22:01:44Z date_published: 2024-09-01T00:00:00Z date_updated: 2025-04-14T13:50:50Z day: '01' department: - _id: MoHe ec_funded: 1 external_id: arxiv: - '2406.11649' intvolume: ' 235' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2406.11649 month: '09' oa: 1 oa_version: Published Version page: 12046-12086 project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' 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 - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer - _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c call_identifier: H2020 grant_number: '101034413' name: 'IST-BRIDGE: International postdoctoral program' publication: Proceedings of the 41st International Conference on Machine Learning publication_identifier: eissn: - 2640-3498 publication_status: published publisher: ML Research Press quality_controlled: '1' scopus_import: '1' status: public title: 'Making old things new: A unified algorithm for differentially private clustering' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 235 year: '2024' ... --- _id: '18156' 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]. 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." alternative_title: - LIPIcs article_number: '40' article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: A. R. full_name: Sricharan, A. R. last_name: Sricharan - first_name: Teresa Anna full_name: Steiner, Teresa Anna last_name: Steiner citation: ama: 'Henzinger M, Sricharan AR, Steiner TA. Private counting of distinct elements in the turnstile model and extensions. In: International Conference on Approximation Algorithms for Combinatorial Optimization Problems . Vol 317. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.APPROX/RANDOM.2024.40' apa: 'Henzinger, M., Sricharan, A. R., & Steiner, T. A. (2024). Private counting of distinct elements in the turnstile model and extensions. In International Conference on Approximation Algorithms for Combinatorial Optimization Problems (Vol. 317). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40' chicago: Henzinger, Monika, A. R. Sricharan, and Teresa Anna Steiner. “Private Counting of Distinct Elements in the Turnstile Model and Extensions.” In International Conference on Approximation Algorithms for Combinatorial Optimization Problems , Vol. 317. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40. ieee: M. Henzinger, A. R. Sricharan, and T. A. Steiner, “Private counting of distinct elements in the turnstile model and extensions,” in International Conference on Approximation Algorithms for Combinatorial Optimization Problems , London, United Kingdom, 2024, vol. 317. 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.' mla: Henzinger, Monika, et al. “Private Counting of Distinct Elements in the Turnstile Model and Extensions.” International Conference on Approximation Algorithms for Combinatorial Optimization Problems , vol. 317, 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.APPROX/RANDOM.2024.40. 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: end_date: 2024-08-30 location: London, United Kingdom name: 'APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems' start_date: 2024-08-27 corr_author: '1' date_created: 2024-09-29T22:01:38Z date_published: 2024-09-16T00:00:00Z date_updated: 2025-12-02T13:47:16Z day: '16' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.APPROX/RANDOM.2024.40 ec_funded: 1 external_id: arxiv: - '2408.11637' isi: - '001545634500040' file: - access_level: open_access checksum: c08b41c896e4d8c69570044808b40e0b content_type: application/pdf creator: dernst date_created: 2024-10-01T10:07:14Z date_updated: 2024-10-01T10:07:14Z file_id: '18166' file_name: 2024_LIPICs_HenzingerM.pdf file_size: 973917 relation: main_file success: 1 file_date_updated: 2024-10-01T10:07:14Z has_accepted_license: '1' intvolume: ' 317' isi: 1 language: - iso: eng month: '09' oa: 1 oa_version: Published Version project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' 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 - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer publication: 'International Conference on Approximation Algorithms for Combinatorial Optimization Problems ' publication_identifier: isbn: - '9783959773485' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Private counting of distinct elements in the turnstile model and extensions tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 317 year: '2024' ... --- OA_place: publisher OA_type: gold _id: '18308' abstract: - lang: eng text: We study in this paper the problem of maintaining a solution to k-median and k-means clustering in a fully dynamic setting. To do so, we present an algorithm to efficiently maintain a coreset, a compressed version of the dataset, that allows easy computation of a clustering solution at query time. Our coreset algorithm has near-optimal update time of Õ(k) in general metric spaces, which reduces to Õ(d) in the Euclidean space ℝ^d. The query time is O(k²) in general metrics, and O(kd) in ℝ^d. To maintain a constant-factor approximation for k-median and k-means clustering in Euclidean space, this directly leads to an algorithm with update time Õ(d), and query time Õ(kd + k²). To maintain a O(polylog k)-approximation, the query time is reduced to Õ(kd). 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 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\nDavid Saulpic: Work partially done while at ISTA. Received funding from the European Union’s\r\nHorizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 101034413. This work was partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR)." alternative_title: - LIPIcs article_number: '100' article_processing_charge: Yes arxiv: 1 author: - first_name: Max Dupré full_name: La Tour, Max Dupré last_name: La Tour - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: David full_name: Saulpic, David id: f8e48cf0-b0ff-11ed-b0e9-b4c35598f964 last_name: Saulpic citation: ama: 'La Tour MD, Henzinger M, Saulpic D. Fully dynamic k-means coreset in near-optimal update time. In: 32nd Annual European Symposium on Algorithms. Vol 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.ESA.2024.100' apa: 'La Tour, M. D., Henzinger, M., & Saulpic, D. (2024). Fully dynamic k-means coreset in near-optimal update time. In 32nd Annual European Symposium on Algorithms (Vol. 308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2024.100' chicago: La Tour, Max Dupré, Monika Henzinger, and David Saulpic. “Fully Dynamic K-Means Coreset in near-Optimal Update Time.” In 32nd Annual European Symposium on Algorithms, Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ESA.2024.100. ieee: M. D. La Tour, M. Henzinger, and D. Saulpic, “Fully dynamic k-means coreset in near-optimal update time,” in 32nd Annual European Symposium on Algorithms, London, United Kingdom, 2024, vol. 308. ista: 'La Tour MD, Henzinger M, Saulpic D. 2024. Fully dynamic k-means coreset in near-optimal update time. 32nd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 308, 100.' mla: La Tour, Max Dupré, et al. “Fully Dynamic K-Means Coreset in near-Optimal Update Time.” 32nd Annual European Symposium on Algorithms, vol. 308, 100, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ESA.2024.100. short: M.D. La Tour, M. Henzinger, D. Saulpic, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. conference: end_date: 2024-09-04 location: London, United Kingdom name: 'ESA: European Symposium on Algorithms' start_date: 2024-09-02 corr_author: '1' date_created: 2024-10-13T22:01:50Z date_published: 2024-09-23T00:00:00Z date_updated: 2025-12-02T13:49:11Z day: '23' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.ESA.2024.100 ec_funded: 1 external_id: arxiv: - '2406.19926' isi: - '001545622400100' file: - access_level: open_access checksum: 8e8c0b13049f11bb0133dfac22e32718 content_type: application/pdf creator: dernst date_created: 2024-10-21T09:41:48Z date_updated: 2024-10-21T09:41:48Z file_id: '18454' file_name: 2024_LIPICs_DuprelaTour.pdf file_size: 873561 relation: main_file success: 1 file_date_updated: 2024-10-21T09:41:48Z has_accepted_license: '1' intvolume: ' 308' isi: 1 language: - iso: eng month: '09' oa: 1 oa_version: Published Version project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' 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 - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer - _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c call_identifier: H2020 grant_number: '101034413' name: 'IST-BRIDGE: International postdoctoral program' publication: 32nd Annual European Symposium on Algorithms publication_identifier: isbn: - '9783959773386' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Fully dynamic k-means coreset in near-optimal update time tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 308 year: '2024' ... --- OA_place: repository OA_type: free access _id: '18503' abstract: - lang: eng 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." 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. article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Jason full_name: Li, Jason last_name: Li - first_name: Satish full_name: Rao, Satish last_name: Rao - first_name: Di full_name: Wang, Di last_name: Wang citation: ama: 'Henzinger M, Li J, Rao S, Wang D. Deterministic near-linear time minimum cut in weighted graphs. In: 35th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2024:3089-3139. doi:10.1137/1.9781611977912.111' apa: 'Henzinger, M., Li, J., Rao, S., & Wang, D. (2024). Deterministic near-linear time minimum cut in weighted graphs. In 35th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 3089–3139). Alexandria, VA,  United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977912.111' chicago: Henzinger, Monika, Jason Li, Satish Rao, and Di Wang. “Deterministic Near-Linear Time Minimum Cut in Weighted Graphs.” In 35th Annual ACM-SIAM Symposium on Discrete Algorithms, 3089–3139. Society for Industrial and Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977912.111. ieee: M. Henzinger, J. Li, S. Rao, and D. Wang, “Deterministic near-linear time minimum cut in weighted graphs,” in 35th Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, VA,  United States, 2024, pp. 3089–3139. 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.' mla: Henzinger, Monika, et al. “Deterministic Near-Linear Time Minimum Cut in Weighted Graphs.” 35th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2024, pp. 3089–139, doi:10.1137/1.9781611977912.111. 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. conference: end_date: 2024-01-10 location: Alexandria, VA, United States name: 'SODA: Symposium on Discrete Algorithms' start_date: 2024-01-07 corr_author: '1' date_created: 2024-11-04T10:54:21Z date_published: 2024-01-04T00:00:00Z date_updated: 2025-06-24T12:09:26Z day: '04' department: - _id: MoHe doi: 10.1137/1.9781611977912.111 ec_funded: 1 external_id: arxiv: - '2401.05627' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.48550/arXiv.2401.05627 month: '01' oa: 1 oa_version: Preprint page: 3089-3139 project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' 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 - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer publication: 35th Annual ACM-SIAM Symposium on Discrete Algorithms publication_identifier: eisbn: - '9781611977912' publication_status: published publisher: Society for Industrial and Applied Mathematics quality_controlled: '1' scopus_import: '1' status: public title: Deterministic near-linear time minimum cut in weighted graphs type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2024' ... --- OA_place: publisher OA_type: gold _id: '18557' abstract: - lang: eng text: Broadcast and Consensus are most fundamental tasks in distributed computing. These tasks are particularly challenging in dynamic networks where communication across the network links may be unreliable, e.g., due to mobility or failures. Over the last years, researchers have derived several impossibility results and high time complexity lower bounds for these tasks. Specifically for the setting where in each round of communication the adversary is allowed to choose one rooted tree along which the information is disseminated, there is a lower as well as an upper bound that is linear in the number n of nodes for Broadcast and for n ≥ 3 the adversary can guarantee that Consensus never happens. This setting is called the oblivious message adversary for rooted trees. Also note that if the adversary is allowed to choose a graph that does not contain a rooted tree, then it can guarantee that Broadcast and Consensus will never happen. However, such deterministic adversarial models may be overly pessimistic, as many processes in real-world settings are stochastic in nature rather than worst-case. This paper studies Broadcast on stochastic dynamic networks and shows that the situation is very different to the deterministic case. In particular, we show that if information dissemination occurs along random rooted trees and directed Erdős–Rényi graphs, Broadcast completes in O(log n) rounds of communication with high probability. The fundamental insight in our analysis is that key variables are mutually independent. We then study two adversarial models, (a) one with Byzantine nodes and (b) one where an adversary controls the edges. (a) Our techniques without Byzantine nodes are general enough so that they can be extended to Byzantine nodes. (b) In the spirit of smoothed analysis, we introduce the notion of randomized oblivious message adversary, where in each round, an adversary picks k ≤ 2n/3 edges to appear in the communication network, and then a graph (e.g. rooted tree or directed Erdős–Rényi graph) is chosen uniformly at random among the set of all such graphs that include these edges. We show that Broadcast completes in a finite number of rounds, which is, e.g., O(k+log n) rounds in rooted trees. We then extend these results to All-to-All Broadcast, and Consensus, and give lower bounds that show that most of our upper bounds are tight. acknowledgement: "Antoine El-Hayek: This project has received funding from the Austrian Science Fund\r\n(FWF) grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung,\r\n2020–2024.\r\nMonika Henzinger: This project has received funding from the European Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation programme (MoDynStruct,\r\nNo. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI\r\n10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE\r\nStiftung, 2020–2024.\r\nStefan Schmid: This project has received funding from the German Research Foundation (DFG),\r\nSPP 2378 (project ReNO), 2023-2027." alternative_title: - LIPIcs article_number: '21' article_processing_charge: Yes arxiv: 1 author: - first_name: Antoine full_name: El-Hayek, Antoine id: 888a098e-fcac-11ee-aff7-d347be57b725 last_name: El-Hayek orcid: 0000-0003-4268-7368 - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid citation: ama: 'El-Hayek A, Henzinger M, Schmid S. Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. In: 38th International Symposium on Distributed Computing. Vol 319. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.DISC.2024.21' apa: 'El-Hayek, A., Henzinger, M., & Schmid, S. (2024). Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. In 38th International Symposium on Distributed Computing (Vol. 319). Madrid, Spain: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2024.21' chicago: El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Broadcast and Consensus in Stochastic Dynamic Networks with Byzantine Nodes and Adversarial Edges.” In 38th International Symposium on Distributed Computing, Vol. 319. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.DISC.2024.21. ieee: A. El-Hayek, M. Henzinger, and S. Schmid, “Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges,” in 38th International Symposium on Distributed Computing, Madrid, Spain, 2024, vol. 319. ista: 'El-Hayek A, Henzinger M, Schmid S. 2024. Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. 38th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 319, 21.' mla: El-Hayek, Antoine, et al. “Broadcast and Consensus in Stochastic Dynamic Networks with Byzantine Nodes and Adversarial Edges.” 38th International Symposium on Distributed Computing, vol. 319, 21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.DISC.2024.21. short: A. El-Hayek, M. Henzinger, S. Schmid, in:, 38th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. conference: end_date: 2024-11-01 location: Madrid, Spain name: 'DISC: Symposium on Distributed Computing' start_date: 2024-10-28 corr_author: '1' date_created: 2024-11-17T23:01:47Z date_published: 2024-10-24T00:00:00Z date_updated: 2025-12-02T13:51:28Z day: '24' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.DISC.2024.21 ec_funded: 1 external_id: arxiv: - '2302.11988' isi: - '001542467600021' file: - access_level: open_access checksum: d6c8277331cafa188c33ba1717206cf4 content_type: application/pdf creator: dernst date_created: 2024-11-18T08:02:45Z date_updated: 2024-11-18T08:02:45Z file_id: '18561' file_name: 2024_LIPIcs_ElHayek.pdf file_size: 809666 relation: main_file success: 1 file_date_updated: 2024-11-18T08:02:45Z has_accepted_license: '1' intvolume: ' 319' isi: 1 language: - iso: eng month: '10' oa: 1 oa_version: Published Version project: - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' 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 publication: 38th International Symposium on Distributed Computing publication_identifier: isbn: - '9783959773522' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 319 year: '2024' ... --- OA_place: publisher OA_type: hybrid _id: '18906' 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." 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." article_processing_charge: Yes (in subscription journal) author: - first_name: Kathrin full_name: Hanauer, Kathrin last_name: Hanauer - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Robin full_name: Münk, 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 citation: ama: 'Hanauer K, Henzinger M, Münk R, Räcke H, Vötsch M. Expander hierarchies for normalized cuts on graphs. In: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM; 2024:1016-1027. doi:10.1145/3637528.3671978' apa: 'Hanauer, K., Henzinger, M., Münk, R., Räcke, H., & Vötsch, M. (2024). Expander hierarchies for normalized cuts on graphs. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 1016–1027). Barcelona, Spain: ACM. https://doi.org/10.1145/3637528.3671978' chicago: Hanauer, Kathrin, Monika Henzinger, Robin Münk, Harald Räcke, and Maximilian Vötsch. “Expander Hierarchies for Normalized Cuts on Graphs.” In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 1016–27. ACM, 2024. https://doi.org/10.1145/3637528.3671978. ieee: K. Hanauer, M. Henzinger, R. Münk, H. Räcke, and M. Vötsch, “Expander hierarchies for normalized cuts on graphs,” in Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Barcelona, Spain, 2024, pp. 1016–1027. 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.' mla: Hanauer, Kathrin, et al. “Expander Hierarchies for Normalized Cuts on Graphs.” Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, ACM, 2024, pp. 1016–27, doi:10.1145/3637528.3671978. 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. conference: end_date: 2024-08-29 location: Barcelona, Spain name: 'KDD: Knowledge Discovery and Data Mining' start_date: 2024-08-05 date_created: 2025-01-27T13:20:26Z date_published: 2024-09-01T00:00:00Z date_updated: 2025-09-09T12:04:56Z day: '01' ddc: - '000' department: - _id: MoHe doi: 10.1145/3637528.3671978 ec_funded: 1 external_id: isi: - '001324524201013' file: - access_level: open_access checksum: 1265d5cf6aa5f94157631651723c4a2b content_type: application/pdf creator: dernst date_created: 2025-01-27T13:25:23Z date_updated: 2025-01-27T13:25:23Z file_id: '18907' file_name: 2024_ACMKDD_Hanauer.pdf file_size: 1450331 relation: main_file success: 1 file_date_updated: 2025-01-27T13:25:23Z has_accepted_license: '1' isi: 1 language: - iso: eng month: '09' oa: 1 oa_version: Published Version page: 1016-1027 project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' 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 publication: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining publication_identifier: isbn: - '9798400704901' publication_status: published publisher: ACM quality_controlled: '1' scopus_import: '1' status: public title: Expander hierarchies for normalized cuts on graphs tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 year: '2024' ...