--- OA_place: publisher OA_type: gold _id: '22004' abstract: - lang: eng text: "Recent research on computing the diameter of geometric intersection graphs has made significant strides, primarily focusing on the 2D case [Duraj et al., 2024; Hsien-Chih Chang et al., 2024; Chan et al., 2025] where truly subquadratic-time algorithms were given for simple objects such as unit-disks and (axis-aligned) squares. However, in three or higher dimensions, there is no known truly subquadratic-time algorithm for any intersection graph of non-trivial objects, even basic ones such as unit balls or (axis-aligned) unit cubes. This was partially explained by the pioneering work of Bringmann et al. [Karl Bringmann et al., 2022] which gave several truly subquadratic lower bounds, notably for unit balls or unit cubes in 3D when the graph diameter Δ is at least Ω(log n), hinting at a pessimistic outlook for the complexity of the diameter problem in higher dimensions. In this paper, we substantially extend the landscape of diameter computation for objects in three and higher dimensions, giving a few positive results. Our highlighted findings include: \r\n1) A truly subquadratic-time algorithm for deciding if the diameter of unit cubes in 3D is at most 3 (Diameter-3 hereafter), the first algorithm of its kind for objects in 3D or higher dimensions. Our algorithm is based on a novel connection to pseudolines, which is of independent interest. \r\n2) A truly subquadratic time lower bound for Diameter-3 of unit balls in 3D under the Orthogonal Vector (OV) hypothesis, giving the first separation between unit balls and unit cubes in the small diameter regime. Previously, computing the diameter for both objects was known to be quadratic hard when the diameter is Ω(log n) [Karl Bringmann et al., 2022]. \r\n3) A near-linear-time algorithm for Diameter-2 of unit cubes in 3D, generalizing the previous result for unit squares in 2D [Karl Bringmann et al., 2022]. \r\n4) A truly subquadratic-time algorithm and lower bound for Diameter-2 and Diameter-3 of rectangular boxes (of arbitrary dimension and sizes), respectively." acknowledgement: "Timothy M. Chan: Supported by NSF grant CCF-2224271.\r\nHsien-Chih Chang: Supported by NSF CAREER award CCF-2443017.\r\nJie Gao: Supported by NSF DMS-2220271, DMS-2311064, IIS-2229876, CCF-2118953, CNS-2515159.\r\nSándor Kisfaludi-Bak: Supported by the Research Council of Finland, Grant 363444.\r\nHung Le: Supported by an NSF grant CCF-2517033 and an NSF CAREER Award CCF-2237288. Da Wei Zheng: This project has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 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." alternative_title: - LIPIcs article_number: 29:1-29:15 article_processing_charge: Yes arxiv: 1 author: - first_name: Timothy M. full_name: Chan, Timothy M. last_name: Chan - first_name: Hsien Chih full_name: Chang, Hsien Chih last_name: Chang - first_name: Jie full_name: Gao, Jie last_name: Gao - first_name: Sándor full_name: Kisfaludi-Bak, Sándor last_name: Kisfaludi-Bak - first_name: Hung full_name: Le, Hung last_name: Le - first_name: Da Wei full_name: Zheng, Da Wei id: af77956b-e859-11ef-8dc9-d301b898e32f last_name: Zheng citation: ama: 'Chan TM, Chang HC, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. Charting the diameter computation landscape of intersection graphs in 3D and above. In: 42nd International Symposium on Computational Geometry. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.SoCG.2026.29' apa: 'Chan, T. M., Chang, H. C., Gao, J., Kisfaludi-Bak, S., Le, H., & Zheng, D. W. (2026). Charting the diameter computation landscape of intersection graphs in 3D and above. In 42nd International Symposium on Computational Geometry (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2026.29' chicago: Chan, Timothy M., Hsien Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng. “Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above.” In 42nd International Symposium on Computational Geometry, Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.SoCG.2026.29. ieee: T. M. Chan, H. C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, and D. W. Zheng, “Charting the diameter computation landscape of intersection graphs in 3D and above,” in 42nd International Symposium on Computational Geometry, New Brunswick, NJ, United States, 2026, vol. 367. ista: 'Chan TM, Chang HC, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. 2026. Charting the diameter computation landscape of intersection graphs in 3D and above. 42nd International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 367, 29:1-29:15.' mla: Chan, Timothy M., et al. “Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above.” 42nd International Symposium on Computational Geometry, vol. 367, 29:1-29:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.SoCG.2026.29. short: T.M. Chan, H.C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D.W. Zheng, in:, 42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. conference: end_date: 2026-06-05 location: New Brunswick, NJ, United States name: 'SoCG: Symposium on Computational Geometry' start_date: 2026-06-02 corr_author: '1' das_tickbox: '0' date_created: 2026-06-14T22:01:44Z date_published: 2026-05-27T00:00:00Z date_updated: 2026-06-22T08:37:44Z day: '27' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.SoCG.2026.29 external_id: arxiv: - '2603.21790' file: - access_level: open_access checksum: ffff03934cc182757d6db82d88f896e6 content_type: application/pdf creator: dernst date_created: 2026-06-22T08:34:11Z date_updated: 2026-06-22T08:34:11Z file_id: '22114' file_name: 2026_LIPIcSSoCG_Chan.pdf file_size: 918197 relation: main_file success: 1 file_date_updated: 2026-06-22T08:34:11Z fulldoi: https://doi.org/10.4230/LIPIcs.SoCG.2026.29 has_accepted_license: '1' intvolume: ' 367' keyword: - Graph Diameter - Geometric Intersection Graphs - Unit Ball Graphs language: - iso: eng month: '05' oa: 1 oa_version: Published Version project: - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions publication: 42nd International Symposium on Computational Geometry publication_identifier: eissn: - 1868-8969 isbn: - '9783959774185' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Charting the diameter computation landscape of intersection graphs in 3D and above 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: 367 year: '2026' ... --- 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' fulldoi: https://doi.org/10.1137/1.9781611978971.45 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: publisher OA_type: gold PlanS_conform: '1' _id: '22318' abstract: - lang: eng text: "Many intended uses of differential privacy involve a continual mechanism that is set up to run continuously\r\nover a long period of time, making more statistical releases as either queries come in or the dataset is updated.\r\nIn this paper, we give the first general treatment of privacy against adaptive adversaries for mechanisms that\r\nsupport dataset updates and a variety of queries, all arbitrarily interleaved. It also models a very general notion\r\nof neighboring, that includes both event-level and user-level privacy. We prove several concurrent composition\r\ntheorems for continual mechanisms, which ensure privacy even when an adversary can interleave its queries\r\nand dataset updates to the different composed mechanisms. Previous concurrent composition theorems for\r\ndifferential privacy were only for the case when the dataset is static, with no adaptive updates. We also give\r\nthe first interactive and continual generalizations of the “parallel composition theorem” for noninteractive\r\ndifferential privacy. Specifically, we show that the analogue of the noninteractive parallel composition theorem\r\nholds if either there are no adaptive dataset updates or each of the composed mechanisms satisfies pure\r\ndifferential privacy, but it fails to hold for composing approximately differentially private mechanisms with\r\ndataset updates. Thus, we prove a tight new composition theorem for this case. In addition, we prove concurrent\r\nfilter compositions theorems for the scenarios in which the privacy parameters are adaptively chosen. We\r\nextend these results to other measures of differential privacy, including Rényi DP and \U0001D453 -DP.\r\nWe then formalize a set of general conditions on a continual mechanism M that runs multiple continual submechanisms such that the privacy guarantees of M follow directly using the above concurrent composition\r\ntheorems on the sub-mechanisms, without further privacy loss. This enables us to give a simpler and modular\r\nprivacy analysis of a recent continual histogram mechanism of Henzinger, Sricharan, and Steiner. In the\r\ncase of approximate DP, ours is the first proof that shows that its privacy holds against adaptive adversaries.\r\nWe also provide a framework that simplifies the analysis of local differential privacy when the protocol\r\nincludes multi-round server-user interactions. Using this result, we simplify the privacy analysis of the core\r\ndecomposition protocol of Dhulipala, Henzinger, Li, Liu, Sricharan, and Zhu [5]." acknowledgement: "1Salil Vadhan was supported by NSF grant BCS-2218803, a grant from the Sloan Foundation, and\r\na Simons Investigator Award. Work began while a Visiting Researcher at the Bocconi University\r\nDepartment of Computing Sciences, supported by Luca Trevisan’s ERC Project GA-834861.\r\n2Monika Henzinger and Roodabeh Safavi were supported by the European Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation programme (Grant agreement\r\nNo. 101019564), and the Austrian Science Fund (FWF) under grants DOI 10.55776/Z422, DOI\r\n10.55776/I5982, and DOI 10.55776/P33775. For open access purposes, the author has applied a CC BY\r\npublic copyright license to any author-accepted manuscript version arising from this submission.\r\nViews and opinions expressed are however those of the author(s)\r\nonly and do not necessarily reflect those of the European Union\r\nor the European Research Council Executive Agency. Neither the\r\nEuropean Union nor the granting authority can be held responsible for them." article_processing_charge: Yes article_type: original 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: Roodabeh full_name: Safavi Hemami, Roodabeh id: 72ed2640-8972-11ed-ae7b-f9c81ec75154 last_name: Safavi Hemami - first_name: Salil full_name: Vadhan, Salil last_name: Vadhan citation: ama: Henzinger M, Safavi Hemami R, Vadhan S. Concurrent composition for differentially private continual mechanisms. Proceedings of the ACM on Management of Data. 2026;4(2):1-26. doi:10.1145/3801895 apa: Henzinger, M., Safavi Hemami, R., & Vadhan, S. (2026). Concurrent composition for differentially private continual mechanisms. Proceedings of the ACM on Management of Data. Association for Computing Machinery. https://doi.org/10.1145/3801895 chicago: Henzinger, Monika, Roodabeh Safavi Hemami, and Salil Vadhan. “Concurrent Composition for Differentially Private Continual Mechanisms.” Proceedings of the ACM on Management of Data. Association for Computing Machinery, 2026. https://doi.org/10.1145/3801895. ieee: M. Henzinger, R. Safavi Hemami, and S. Vadhan, “Concurrent composition for differentially private continual mechanisms,” Proceedings of the ACM on Management of Data, vol. 4, no. 2. Association for Computing Machinery, pp. 1–26, 2026. ista: Henzinger M, Safavi Hemami R, Vadhan S. 2026. Concurrent composition for differentially private continual mechanisms. Proceedings of the ACM on Management of Data. 4(2), 1–26. mla: Henzinger, Monika, et al. “Concurrent Composition for Differentially Private Continual Mechanisms.” Proceedings of the ACM on Management of Data, vol. 4, no. 2, Association for Computing Machinery, 2026, pp. 1–26, doi:10.1145/3801895. short: M. Henzinger, R. Safavi Hemami, S. Vadhan, Proceedings of the ACM on Management of Data 4 (2026) 1–26. corr_author: '1' das_tickbox: '0' date_created: 2026-07-13T14:59:14Z date_published: 2026-06-01T00:00:00Z date_updated: 2026-07-16T09:14:49Z day: '01' ddc: - '000' department: - _id: MoHe doi: 10.1145/3801895 ec_funded: 1 external_id: arxiv: - '2411.03299' file: - access_level: open_access checksum: c6c5e256d02b90682c0690c3bee94040 content_type: application/pdf creator: dernst date_created: 2026-07-16T09:09:53Z date_updated: 2026-07-16T09:09:53Z file_id: '22345' file_name: 2026_ACMMgmtData_Henzinger.pdf file_size: 655405 relation: main_file success: 1 file_date_updated: 2026-07-16T09:09:53Z fulldoi: https://doi.org/10.1145/3801895 has_accepted_license: '1' intvolume: ' 4' issue: '2' keyword: - differential privacy - concurrent composition - continual release - continual observation - data streaming - continual mechanisms - concurrent parallel composition - concurrent filter composition language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: 1-26 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 - _id: 34def286-11ca-11ed-8bc3-da5948e1613c grant_number: Z00422 name: Efficient algorithms publication: Proceedings of the ACM on Management of Data publication_identifier: issn: - 2836-6573 publication_status: published publisher: Association for Computing Machinery quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: Concurrent composition for differentially private continual mechanisms 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: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 4 year: '2026' ... --- OA_place: publisher OA_type: gold _id: '22327' abstract: - lang: eng text: "Population protocols are a model of distributed computing where\r\n\U0001D45B agents, each a simple finite-state machine, interact in pairs to\r\nsolve a common task against a (adversarial) interaction scheduler.\r\nThis model was intensively studied in recent years; in particular,\r\nthe problem of relative majority received much attention: Each\r\nagent starts with an input opinion (or color) out of \U0001D458 possibilities,\r\nand the goal is for each agent to eventually output the color with\r\nthe largest support in the population. Before our work, the state\r\ncomplexity (the minimum number of states required per agent) was\r\nonly known to be between Ω(\U0001D458\r\n2\r\n) and\U0001D442(\U0001D458\r\n7\r\n). Our main contribution\r\nis a population protocol that solves the relative majority problem\r\nwith \U0001D458\r\n3\r\nstates. We achieve this result with a new protocol called\r\nCircles. While prior approaches in the literature relied on duels of\r\nagents to find the majority color — an approach that proved effective\r\nfor the case with two colors — Circles partitions the agents into\r\ncircular linked lists of decreasing sizes, with the property that no\r\ntwo agents with the same initial color lie in the same circle. We\r\nshow that Circles always correctly computes the desired structure\r\nagainst the most adversarial of schedulers (weakly fair). We then\r\nshow that a trivial extension of Circles solves the relative majority\r\nproblem. We extend our protocol to handle various tie-breaking\r\nmechanisms or to support the case where the agents do not share a\r\nprior ordering of the colors. Finally, we show that a modification of\r\nCircles solves the ranking problem with 2 · \U0001D458^4\r\nstates, where each\r\nagent must output the rank of its initial color in the population." acknowledgement: "Funded by the European union. Views and opinions expressed are\r\nhowever those of the author(s) only and do not necessarily reflect\r\nthose of the European Union or the European Research Council\r\nExecutive Agency. Neither the European Union nor the granting authority can be held responsible for them. This project has received\r\nfunding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme\r\n(MoDynStruct, No. 101019564) and the Austrian Science\r\nFund (FWF) grant DOI 10.55776/I5982. For open access purposes,\r\nthe author has applied a CC BY public copyright license to any\r\nauthor-accepted manuscript version arising from this submission." article_processing_charge: Yes arxiv: 1 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. Ranking opinions with few states in population protocols. In: Proceedings of the ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery; 2026:414-424. doi:10.1145/3796701.3815913' apa: 'Breitkopf, T.-L., Dallot, J., El-Hayek, A., & Schmid, S. (2026). Ranking opinions with few states in population protocols. In Proceedings of the ACM Symposium on Principles of Distributed Computing (pp. 414–424). Egham, United Kingdom: Association for Computing Machinery. https://doi.org/10.1145/3796701.3815913' chicago: Breitkopf, Tom-Lukas, Julien Dallot, Antoine El-Hayek, and Stefan Schmid. “Ranking Opinions with Few States in Population Protocols.” In Proceedings of the ACM Symposium on Principles of Distributed Computing, 414–24. Association for Computing Machinery, 2026. https://doi.org/10.1145/3796701.3815913. ieee: T.-L. Breitkopf, J. Dallot, A. El-Hayek, and S. Schmid, “Ranking opinions with few states in population protocols,” in Proceedings of the ACM Symposium on Principles of Distributed Computing, Egham, United Kingdom, 2026, pp. 414–424. ista: 'Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. 2026. Ranking opinions with few states in population protocols. Proceedings of the ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 414–424.' mla: Breitkopf, Tom-Lukas, et al. “Ranking Opinions with Few States in Population Protocols.” Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2026, pp. 414–24, doi:10.1145/3796701.3815913. 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, 2026, pp. 414–424. conference: end_date: 2026-07-10 location: Egham, United Kingdom name: 'PODC: Symposium on Principles of Distributed Computing' start_date: 2026-07-06 corr_author: '1' das_tickbox: '0' date_created: 2026-07-14T05:40:17Z date_published: 2026-07-01T00:00:00Z date_updated: 2026-07-22T07:49:22Z day: '01' ddc: - '000' department: - _id: MoHe - _id: GradSch doi: 10.1145/3796701.3815913 ec_funded: 1 external_id: arxiv: - '2605.18707' file: - access_level: open_access checksum: e56da70c1b2e7e663d2d8106cf07a30a content_type: application/pdf creator: dernst date_created: 2026-07-16T11:18:44Z date_updated: 2026-07-16T11:18:44Z file_id: '22353' file_name: 2026_ACMPODC_Breitkopf.pdf file_size: 702140 relation: main_file success: 1 file_date_updated: 2026-07-16T11:18:44Z fulldoi: https://doi.org/10.1145/3796701.3815913 has_accepted_license: '1' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: 414 - 424 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 ACM Symposium on Principles of Distributed Computing publication_identifier: isbn: - '9798400725128' publication_status: published publisher: Association for Computing Machinery quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: Ranking opinions with few 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: 8b945eb4-e2f2-11eb-945a-df72226e66a9 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-07-24T12:48:29Z day: '07' department: - _id: MoHe - _id: GradSch doi: 10.1137/1.9781611978971.25 ec_funded: 1 external_id: arxiv: - '2512.13105' fulldoi: https://doi.org/10.1137/1.9781611978971.25 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' related_material: record: - id: '22281' relation: dissertation_contains status: public 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: '22405' abstract: - lang: eng text: "Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainly depends on the object types: for unit disks and squares in 2D, the problem is solvable in truly subquadratic time [Chan et al., 2025], while for other objects, including unit segments and equilateral triangles in 2D or unit balls and axis-parallel unit cubes in 3D, there is no truly subquadratic time algorithm under the Orthogonal Vector (OV) hypothesis [Bringmann et al., 2022]. \r\nWe undertake a comprehensive study of computing the diameter of geometric intersection graphs for various types of objects. We discover many new irregularities, showing that the landscape is extremely nuanced: the source of hardness is a combination of the object type, the true diameter value, and how the objects intersect with each other. Our highlighted results for the 2D case include: \r\n1) The diameter of non-degenerate, axis-aligned line segments can be computed in truly subquadratic time. Previous hardness result [Bringmann et al., 2022] for line segments applies only to degenerate instances. On the other hand, for the degenerate case, we show that a truly subquadratic time algorithm exists when the true diameter is constant. \r\n2) An almost-linear-time algorithm for unit-square graphs of constant diameter. Previous algorithms [Duraj et al., 2024; Chan et al., 2025] rely on succinct representation assuming bounded VC-dimension; for such a strategy Ω(n^{7/4}) time is an inherent barrier. \r\n3) An Õ(n^{4/3})-time algorithm to decide if the diameter of a unit-disk graph is at most 2. This improves upon the recent algorithm with running time Õ(n^{2-1/9}) [Chan et al., 2025]. \r\n4) Deciding if the diameter of intersection graphs of fat triangles or line segments is at most 2 is truly subquadratic-hard under fine-grained complexity assumptions. Previous lower bounds [Bringmann et al., 2022] only hold when deciding if diameter is at most 3. Our findings are presented in a pair of papers. This paper focuses solely on the 2D case, while the companion paper is devoted to higher-dimensional cases." acknowledgement: "Timothy M. Chan: Supported by NSF grant CCF-2224271.\r\nHsien-Chih Chang: Supported by NSF CAREER award CCF-2443017.\r\nJie Gao: Supported by NSF DMS-2220271, DMS-2311064, IIS-2229876, CCF-2118953, CNS-2515159.\r\nSándor Kisfaludi-Bak: Supported by the Research Council of Finland, Grant 363444.\r\nHung Le: Supported by an NSF grant CCF-2517033 and an NSF CAREER Award CCF-2237288.\r\nDa Wei Zheng: This project has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982. For open access purposes, the author has applied a CC BY public copyright\r\nlicense to any author-accepted manuscript version arising from this submission.\r\n" article_number: 54:1-54:22 article_processing_charge: No arxiv: 1 author: - first_name: Timothy M. full_name: Chan, Timothy M. last_name: Chan orcid: 0000-0002-8093-0675 - first_name: Hsien-Chih full_name: Chang, Hsien-Chih last_name: Chang orcid: 0000-0001-6714-7988 - first_name: Jie full_name: Gao, Jie last_name: Gao orcid: 0000-0001-5083-6082 - first_name: Sándor full_name: Kisfaludi-Bak, Sándor last_name: Kisfaludi-Bak orcid: 0000-0002-6856-2902 - first_name: Hung full_name: Le, Hung last_name: Le orcid: 0000-0001-8223-9944 - first_name: Da Wei full_name: Zheng, Da Wei id: af77956b-e859-11ef-8dc9-d301b898e32f last_name: Zheng citation: ama: 'Chan TM, Chang H-C, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. Charting the landscape of diameter computation on geometric intersection graphs in the plane. In: 53rd International Colloquium on Automata, Languages, and Programming. Vol 374. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPICS.ICALP.2026.54' apa: 'Chan, T. M., Chang, H.-C., Gao, J., Kisfaludi-Bak, S., Le, H., & Zheng, D. W. (2026). Charting the landscape of diameter computation on geometric intersection graphs in the plane. In 53rd International Colloquium on Automata, Languages, and Programming (Vol. 374). Egham, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2026.54' chicago: Chan, Timothy M., Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng. “Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane.” In 53rd International Colloquium on Automata, Languages, and Programming, Vol. 374. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPICS.ICALP.2026.54. ieee: T. M. Chan, H.-C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, and D. W. Zheng, “Charting the landscape of diameter computation on geometric intersection graphs in the plane,” in 53rd International Colloquium on Automata, Languages, and Programming, Egham, United Kingdom, 2026, vol. 374. ista: 'Chan TM, Chang H-C, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. 2026. Charting the landscape of diameter computation on geometric intersection graphs in the plane. 53rd International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming vol. 374, 54:1-54:22.' mla: Chan, Timothy M., et al. “Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane.” 53rd International Colloquium on Automata, Languages, and Programming, vol. 374, 54:1-54:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPICS.ICALP.2026.54. short: T.M. Chan, H.-C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D.W. Zheng, in:, 53rd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. conference: end_date: 2026-07-10 location: Egham, United Kingdom name: 'ICALP: Automata, Languages and Programming' start_date: 2026-07-07 corr_author: '1' das_tickbox: '0' date_created: 2026-07-27T05:53:08Z date_published: 2026-07-01T00:00:00Z date_updated: 2026-08-12T09:03:26Z day: '01' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPICS.ICALP.2026.54 external_id: arxiv: - '2605.10692' file: - access_level: open_access checksum: 1e66eba4cfe4e74ab28108b1ca0bb956 content_type: application/pdf creator: dernst date_created: 2026-07-27T06:20:41Z date_updated: 2026-07-27T06:20:41Z file_id: '22407' file_name: 2026_LIPIcSICALP_Chan.pdf file_size: 1440497 relation: main_file success: 1 file_date_updated: 2026-07-27T06:20:41Z fulldoi: https://doi.org/10.4230/LIPICS.ICALP.2026.54 has_accepted_license: '1' intvolume: ' 374' keyword: - String graphs - Fine-grained complexity - Theory of computation → Computational geometry language: - iso: eng month: '07' oa: 1 oa_version: Published Version project: - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions publication: 53rd International Colloquium on Automata, Languages, and Programming publication_identifier: eissn: - 1868-8969 - '9783959774284' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: Charting the landscape of diameter computation on geometric intersection graphs in the plane 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: 374 year: '2026' ... --- OA_place: publisher OA_type: gold PlanS_conform: '1' _id: '22716' 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: "M. Henzinger: This project has received funding from the European Research Council (ERC) under the European Union’s\r\nHorizon 2020 research and innovation programme (MoDynStruct, No. 101019564) and the Austrian Science Fund\r\n(FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the\r\nnetidee SCIENCE Stiftung, 2020–2024. Views and opinions expressed are those of the author(s) only and do not necessarily\r\nreflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor\r\nthe granting authority can be held responsible for them" article_number: '31' article_processing_charge: Yes article_type: original 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. R. full_name: Sricharan, A. R. last_name: Sricharan citation: ama: Goranci G, Henzinger M, Räcke H, Sricharan AR. Incremental approximate maximum flow via residual graph sparsification. ACM Transactions on Algorithms. 2026;22(3). doi:10.1145/3816252 apa: Goranci, G., Henzinger, M., Räcke, H., & Sricharan, A. R. (2026). Incremental approximate maximum flow via residual graph sparsification. ACM Transactions on Algorithms. ACM. https://doi.org/10.1145/3816252 chicago: Goranci, Gramoz, Monika Henzinger, Harald Räcke, and A. R. Sricharan. “Incremental Approximate Maximum Flow via Residual Graph Sparsification.” ACM Transactions on Algorithms. ACM, 2026. https://doi.org/10.1145/3816252. ieee: G. Goranci, M. Henzinger, H. Räcke, and A. R. Sricharan, “Incremental approximate maximum flow via residual graph sparsification,” ACM Transactions on Algorithms, vol. 22, no. 3. ACM, 2026. ista: Goranci G, Henzinger M, Räcke H, Sricharan AR. 2026. Incremental approximate maximum flow via residual graph sparsification. ACM Transactions on Algorithms. 22(3), 31. mla: Goranci, Gramoz, et al. “Incremental Approximate Maximum Flow via Residual Graph Sparsification.” ACM Transactions on Algorithms, vol. 22, no. 3, 31, ACM, 2026, doi:10.1145/3816252. short: G. Goranci, M. Henzinger, H. Räcke, A.R. Sricharan, ACM Transactions on Algorithms 22 (2026). corr_author: '1' das_tickbox: '0' date_created: 2026-08-16T22:01:43Z date_published: 2026-07-06T00:00:00Z date_updated: 2026-08-20T06:28:01Z day: '06' ddc: - '000' department: - _id: MoHe doi: 10.1145/3816252 ec_funded: 1 external_id: arxiv: - '2502.09105' file: - access_level: open_access checksum: 97969d26dab25c3a35be3ae4dd0fd9ee content_type: application/pdf creator: dernst date_created: 2026-08-20T06:19:51Z date_updated: 2026-08-20T06:19:51Z file_id: '22740' file_name: 2026_TransactionsAlgorithms_Goranci.pdf file_size: 2272512 relation: main_file success: 1 file_date_updated: 2026-08-20T06:19:51Z fulldoi: https://doi.org/10.1145/3816252 has_accepted_license: '1' intvolume: ' 22' issue: '3' language: - iso: eng month: '07' 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: ACM Transactions on Algorithms publication_identifier: eissn: - 1549-6333 issn: - 1549-6325 publication_status: published publisher: ACM quality_controlled: '1' related_material: record: - id: '21280' relation: earlier_version status: public researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: yes 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: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 22 year: '2026' ... --- OA_place: publisher OA_type: gold _id: '22914' abstract: - lang: eng text: "We present the first truly subquadratic time algorithm to compute diameter and eccentricities in real-weighted directed graphs with constant distance VC-dimension and strongly sublinear-sized balanced separators. For real-weighted K_h-minor-free digraphs, this runs in O(n^{2-1/(2h-2)} polylog(n)) time.\r\nPrior to this work, truly subquadratic time computation of diameter was only known for real-weighted planar graphs, while extensions to broader classes like minor-free graphs were restricted to unweighted settings. In particular, existing algorithms that use VC-dimension [Ducoffe, Habib, Viennot; SICOMP 2022] [Le, Wulff-Nilsen; SODA 2024] [Chan, Chang, Gao, Le, Kisfaludi-Bak, Zheng; FOCS 2025] work with small integer weights, but do not naturally generalize to real weights. We overcome this barrier by introducing a randomized search-to-decision reduction, demonstrating that VC-dimension is a sufficiently powerful tool in the real-weighted regime." acknowledgement: "This project has received funding from the Austrian Science Fund (FWF)\r\ngrant DOI 10.55776/I5982. For open access purposes, the author has applied a CC BY public\r\ncopyright license to any author-accepted manuscript version arising from this submission. Thanks to Jie Gao for feedback on a preliminary version of the manuscript" alternative_title: - LIPIcs article_number: 61:1-61:12 article_processing_charge: Yes arxiv: 1 author: - first_name: Da Wei full_name: Zheng, Da Wei id: af77956b-e859-11ef-8dc9-d301b898e32f last_name: Zheng citation: ama: 'Zheng DW. Real-weighted diameter and eccentricities of minor-free and bounded VC-dimension graphs in truly subquadratic time. In: 34th Annual European Symposium on Algorithms. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.ESA.2026.61' apa: 'Zheng, D. W. (2026). Real-weighted diameter and eccentricities of minor-free and bounded VC-dimension graphs in truly subquadratic time. In 34th Annual European Symposium on Algorithms (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2026.61' chicago: Zheng, Da Wei. “Real-Weighted Diameter and Eccentricities of Minor-Free and Bounded VC-Dimension Graphs in Truly Subquadratic Time.” In 34th Annual European Symposium on Algorithms, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.ESA.2026.61. ieee: D. W. Zheng, “Real-weighted diameter and eccentricities of minor-free and bounded VC-dimension graphs in truly subquadratic time,” in 34th Annual European Symposium on Algorithms, L’Aquila, Italy, 2026, vol. 388. ista: 'Zheng DW. 2026. Real-weighted diameter and eccentricities of minor-free and bounded VC-dimension graphs in truly subquadratic time. 34th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 61:1-61:12.' mla: Zheng, Da Wei. “Real-Weighted Diameter and Eccentricities of Minor-Free and Bounded VC-Dimension Graphs in Truly Subquadratic Time.” 34th Annual European Symposium on Algorithms, vol. 388, 61:1-61:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.ESA.2026.61. short: D.W. Zheng, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. conference: end_date: 2026-09-04 location: L’Aquila, Italy name: 'ESA: European Symposium on Algorithms' start_date: 2026-08-31 corr_author: '1' das_tickbox: '0' date_created: 2026-09-13T22:01:52Z date_published: 2026-08-25T00:00:00Z date_updated: 2026-09-17T09:31:02Z day: '25' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.ESA.2026.61 external_id: arxiv: - '2607.01926' file: - access_level: open_access checksum: 574f50435b092a72041c7365cac3d280 content_type: application/pdf creator: dernst date_created: 2026-09-17T09:28:04Z date_updated: 2026-09-17T09:28:04Z file_id: '22942' file_name: 2026_LIPIcsESA_Zheng.pdf file_size: 760002 relation: main_file success: 1 file_date_updated: 2026-09-17T09:28:04Z fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.61 has_accepted_license: '1' intvolume: ' 388' keyword: - Diameter - eccentricities - minor-free graphs - real weights - VC-dimension language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions publication: 34th Annual European Symposium on Algorithms publication_identifier: eissn: - 1868-8969 isbn: - '9783959774451' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: Real-weighted diameter and eccentricities of minor-free and bounded VC-dimension graphs in truly subquadratic 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: 388 year: '2026' ... --- OA_place: publisher OA_type: gold _id: '22918' abstract: - lang: eng text: "Given a weighted digraph G, a (t,g,μ)-DAG cover is a collection of g dominating DAGs D_1,… ,D_g such that all distances are approximately preserved: for every pair (u,v) of vertices, min_id_{D_i}(u,v) ≤ t⋅ d_G(u,v), and the total number of non-G edges is bounded by |(∪_i D_i)⧵ G| ≤ μ. Assadi, Hoppenworth, and Wein [STOC 25] and Filtser [SODA 26] studied DAG covers for general digraphs. This paper initiates the study of Steiner DAG cover, where the DAGs are allowed to contain Steiner points. \r\nWe obtain Steiner DAG covers on the important classes of planar digraphs and low-treewidth digraphs. Specifically, we show that any digraph with treewidth tw admits a (1,2,Õ(n⋅tw))-Steiner DAG cover. For planar digraphs we provide a (1+ε,2,Õ_ε(n))-Steiner DAG cover.\r\nWe also demonstrate a stark difference between Steiner and non-Steiner DAG covers. As a lower bound, we show that any non-Steiner DAG cover for graphs with treewidth 1 with stretch t < 2 and sub-quadratic number of extra edges requires Ω(log n) DAGs." acknowledgement: "This work was initiated at Dagstuhl Seminar 25212: Metric Sketching and\r\nDynamic Algorithms for Geometric and Topological Graphs. We thank the organizers and other\r\nparticipants for a productive environment.\r\nujoy Bhore: Work supported in part by ANRF ARG-MATRICS, Grant 002465.\r\nHsien-Chih Chang: Supported by the U.S. National Science Foundation Grant No. CCF-2443017.\r\nJonathan Conroy: Supported by the U.S. National Science Foundation Grant No. CCF-2443017.\r\nArnold Filtser: This research was supported by the ISRAEL SCIENCE FOUNDATION (grant No.\r\n1042/22).\r\nEunjin Oh: Supported by Institute of Information & Communications Technology Planning &\r\nEvaluation (IITP) grant funded by the Korea government (MSIT) (No. RS-2024-00440239, Sublinear\r\nScalable Algorithms for Large-Scale Data Analysis) and the National Research Foundation of Korea\r\n(NRF) grant funded by the Korea government (MSIT) (No. RS-2024-00358505).\r\nNicole Wein: Supported by NSF CAREER award 2541910.\r\nDa Wei Zheng: This project has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982. For open access purposes, the author has applied a CC BY public copyright\r\nlicense to any author-accepted manuscript version arising from this submission." alternative_title: - LIPIcs article_number: 94:1-94:18 article_processing_charge: Yes arxiv: 1 author: - first_name: Sujoy full_name: Bhore, Sujoy last_name: Bhore - first_name: Hsien Chih full_name: Chang, Hsien Chih last_name: Chang - first_name: Jonathan full_name: Conroy, Jonathan last_name: Conroy - first_name: Arnold full_name: Filtser, Arnold last_name: Filtser - first_name: Eunjin full_name: Oh, Eunjin last_name: Oh - first_name: Nicole full_name: Wein, Nicole last_name: Wein - first_name: Da Wei full_name: Zheng, Da Wei id: af77956b-e859-11ef-8dc9-d301b898e32f last_name: Zheng citation: ama: 'Bhore S, Chang HC, Conroy J, et al. DAG covers for structured graphs: The Steiner point effect. In: 34th Annual European Symposium on Algorithms. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.ESA.2026.94' apa: 'Bhore, S., Chang, H. C., Conroy, J., Filtser, A., Oh, E., Wein, N., & Zheng, D. W. (2026). DAG covers for structured graphs: The Steiner point effect. In 34th Annual European Symposium on Algorithms (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2026.94' chicago: 'Bhore, Sujoy, Hsien Chih Chang, Jonathan Conroy, Arnold Filtser, Eunjin Oh, Nicole Wein, and Da Wei Zheng. “DAG Covers for Structured Graphs: The Steiner Point Effect.” In 34th Annual European Symposium on Algorithms, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.ESA.2026.94.' ieee: 'S. Bhore et al., “DAG covers for structured graphs: The Steiner point effect,” in 34th Annual European Symposium on Algorithms, L’Aquila, Italy, 2026, vol. 388.' ista: 'Bhore S, Chang HC, Conroy J, Filtser A, Oh E, Wein N, Zheng DW. 2026. DAG covers for structured graphs: The Steiner point effect. 34th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 94:1-94:18.' mla: 'Bhore, Sujoy, et al. “DAG Covers for Structured Graphs: The Steiner Point Effect.” 34th Annual European Symposium on Algorithms, vol. 388, 94:1-94:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.ESA.2026.94.' short: S. Bhore, H.C. Chang, J. Conroy, A. Filtser, E. Oh, N. Wein, D.W. Zheng, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. conference: end_date: 2026-09-04 location: L’Aquila, Italy name: 'ESA: European Symposium on Algorithms' start_date: 2026-08-31 corr_author: '1' das_tickbox: '0' date_created: 2026-09-13T22:01:53Z date_published: 2026-08-25T00:00:00Z date_updated: 2026-09-17T10:27:46Z day: '25' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.ESA.2026.94 external_id: arxiv: - '2604.04186' file: - access_level: open_access checksum: 2082683b3b72865c6a795305e5d61276 content_type: application/pdf creator: dernst date_created: 2026-09-17T10:09:22Z date_updated: 2026-09-17T10:09:22Z file_id: '22948' file_name: 2026_LIPIcsESA_Bhore.pdf file_size: 1123327 relation: main_file success: 1 file_date_updated: 2026-09-17T10:09:22Z fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.94 has_accepted_license: '1' intvolume: ' 388' keyword: - Directed graphs - DAG (directed acyclic graphs) - distortion - metric embeddings - planar graph - treewidth language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions publication: 34th Annual European Symposium on Algorithms publication_identifier: isbn: - '9783959774451' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: yes title: 'DAG covers for structured graphs: The Steiner point effect' 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: 388 year: '2026' ... --- OA_place: publisher OA_type: gold _id: '22245' abstract: - lang: eng text: "A single-commodity congestion approximator for a graph is a compact data structure that approximately predicts the edge congestion required to route any set of single-commodity flow demands in a network. A hierarchical congestion approximator (HCA) consists of a laminar family of cuts in the graph and has numerous applications in approximating cut and flow problems in graphs, designing efficient routing schemes, and managing distributed networks.\r\nThere is a tradeoff between the running time for computing an HCA and its approximation quality. The best polynomial-time construction in an n-node graph gives an HCA with approximation quality O(log1.5n loglogn). Among near-linear time algorithms, the best previous result achieves approximation quality O(log4 n). We improve upon the latter result by giving the first near-linear time algorithm for computing an HCA with approximation quality O(log2 n loglogn). Additionally, our algorithm can be implemented in the parallel setting with polylogarithmic span and near-linear work, achieving the same approximation quality. This improves upon the best previous such algorithm, which has an O(log9n) approximation quality. We also present a lower bound of Ω(logn) for the approximation guarantee of hierarchical congestion approximators.\r\nCrucial for achieving a near-linear running time is a new partitioning routine that, unlike previous such routines, manages to avoid recursing on large subgraphs. To achieve the improved approximation quality, we introduce the new concept of border routability of a cut and provide an improved sparsest cut oracle for general vertex weights." acknowledgement: "We thank Evangelos Kosinas for helpful discussions on this topic.\r\nFunded by the European Union. Views and opinions expressed\r\nare however those of the author(s) only and do not necessarily\r\nreflect those of the European Union or the European Research\r\nCouncil Executive Agency. Neither the European Union nor the\r\ngranting authority can be held responsible for them.\r\nThis project has received funding from the European Research\r\nCouncil (ERC) under the European Union’s Horizon 2020 research\r\nand innovation programme (MoDynStruct, No. 101019564)\r\nand the Austrian Science Fund (FWF) grant DOI 10.55776/I5982. For\r\nopen access purposes, the author has applied a CC BY public copyright license to any author-accepted manuscript version arising\r\nfrom this submission.\r\nThis project has received funding from the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 498605858." article_processing_charge: Yes 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: 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, Münk R, Räcke H. An improved quality hierarchical congestion approximator in near-linear time. In: 58th Annual ACM Symposium on Theory of Computing. ACM; 2026:1417-1428. doi:10.1145/3798129.3800851' apa: 'Henzinger, M., Münk, R., & Räcke, H. (2026). An improved quality hierarchical congestion approximator in near-linear time. In 58th Annual ACM Symposium on Theory of Computing (pp. 1417–1428). Salt Lake City, UT, United States: ACM. https://doi.org/10.1145/3798129.3800851' chicago: Henzinger, Monika, Robin Münk, and Harald Räcke. “An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time.” In 58th Annual ACM Symposium on Theory of Computing, 1417–28. ACM, 2026. https://doi.org/10.1145/3798129.3800851. ieee: M. Henzinger, R. Münk, and H. Räcke, “An improved quality hierarchical congestion approximator in near-linear time,” in 58th Annual ACM Symposium on Theory of Computing, Salt Lake City, UT, United States, 2026, pp. 1417–1428. ista: 'Henzinger M, Münk R, Räcke H. 2026. An improved quality hierarchical congestion approximator in near-linear time. 58th Annual ACM Symposium on Theory of Computing. STOC: Symposium on the Theory of Computing, 1417–1428.' mla: Henzinger, Monika, et al. “An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time.” 58th Annual ACM Symposium on Theory of Computing, ACM, 2026, pp. 1417–28, doi:10.1145/3798129.3800851. short: M. Henzinger, R. Münk, H. Räcke, in:, 58th Annual ACM Symposium on Theory of Computing, ACM, 2026, pp. 1417–1428. conference: end_date: 2026-06-26 location: Salt Lake City, UT, United States name: 'STOC: Symposium on the Theory of Computing' start_date: 2026-06-22 corr_author: '1' das_tickbox: '0' date_created: 2026-07-05T22:01:36Z date_published: 2026-06-09T00:00:00Z date_updated: 2026-09-17T12:39:36Z day: '09' ddc: - '000' department: - _id: MoHe doi: 10.1145/3798129.3800851 ec_funded: 1 external_id: arxiv: - '2511.03716' file: - access_level: open_access checksum: 2bef46be8da6d19a641697bb0d8ade65 content_type: application/pdf creator: dernst date_created: 2026-07-06T06:57:16Z date_updated: 2026-07-06T06:57:16Z file_id: '22250' file_name: 2026_STOC_HenzingerMo.pdf file_size: 919005 relation: main_file success: 1 file_date_updated: 2026-07-06T06:57:16Z fulldoi: https://doi.org/10.1145/3798129.3800851 has_accepted_license: '1' keyword: - Congestion Approximators - Hierarchical Graph Decompositions language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: 1417-1428 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: 58th Annual ACM Symposium on Theory of Computing publication_identifier: isbn: - '9798400725364' issn: - 0737-8017 publication_status: published publisher: ACM quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: An improved quality hierarchical congestion approximator in near-linear 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 year: '2026' ... --- OA_place: publisher _id: '22281' abstract: - lang: eng text: "In this thesis, we took a look at networks, and more specifically, at networks that change over time, whether those are networks in the distributed algorithms sense of the word, or the graph algorithm sense. \r\n\r\nIn distributed algorithms, we looked at two main problems. First, the broadcast problem: given n agents, each agent is tasked to forward a (unique) message to every other agent. Agents collaborate and can copy and forward all messages they have received up until that point. Broadcast is achieved when one agent has successfully broadcast its message to everyone else. We studied the case where the communication network is controlled by an adversary, under the condition that the graph is rooted in every round of communication. We show that the adversary can delay broadcast for at most l\r\n(1 + √\r\n2)n\r\nm\r\n rounds, improving on the $O(n\\log\\log n)$ previous upper bound~\\cite{fugger2020radius}, and asymptotically matching the $\\sim 1.5n$ lower bound~\\cite{schwarz2017linear}.\r\n\r\nWe then looked at the stochastic version of the problem: here, the adversary -- parametrized by $k$ where $k=0$ signifies that the adversary has no control, and $k=n$ that the adversary has full control -- can choose parts of the graph, and the graph is then completed stochastically. Here, we are able to look at a stronger version of broadcast: instead of having $n$ messages trying to be broadcast in parallel, we can assume that only one message needs to be broadcasted. We show the bound $\\Theta(k+\\log n)$.\r\n\r\nThen, we looked at undecided states dynamics in population protocols: given a population of $n$ agents, where each initially holds an opinion among $k$ different ones. In each round, two agents are chosen uniformly at random, and can interact. If they have different opinions, they forget their opinions and become undecided. If one of them is undecided while the other has an opinion, they undecided agent copies they opinion of the decided one. The question is then, how many interactions does it take for the whole population to share the same opinion? We show a $\\Omega(kn\\log \\frac {\\sqrt n} {k \\log n})$ lower bound \ for any $k = o\\left(\\frac {\\sqrt n}{\\log n}\\right)$.\r\nThis is tight for any $ k \\le n^{\\frac 1 2 - \\epsilon}$, where $\\epsilon >0$ can be any small constant, matching the known $O(kn\\log n)$ upper bound for $k = O\\left(\\frac {\\sqrt n} {\\log ^2 n}\\right)$~\\cite{DBLP:conf/podc/AmirABBHKL23}.\r\n\r\nFinally, in dynamic algorithms, we study the minimum cut problem: we are given a graph, whose vertex set we want to partition into two subsets such that the number of edges crossing from one subset to the other is minimized. Then, the graph can be updated via edge insertions or deletions, and we must update the solution without recomputing everything from scratch. We present an exact fully-dynamic minimum cut algorithm that runs in $n^{o(1)}$ deterministic update time when the minimum cut size is at most $2^{\\Theta(\\log^{3/4-c}n)}$ for any $c>0$, improving on the previous algorithm~\\cite{DBLP:conf/soda/JinST24} whose minimum cut size limit is $(\\log n)^{o(1)}$. Using sparsification and randomization techniques, we are able to extend this to all values of the minimum cut in weighted graphs, at the cost of a $(1+o(1))$-approximation ratio." 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)\r\n\"The Design and Evaluation of Modern Fully Dynamic Data Structures\" , from the\r\nAustrian Science Fund (FWF) grant DOI 10.55776/I5982 \"Static and Dynamic Hierarchical\r\nGraph Decompositions\", and from the Austrian Science Fund (FWF) and netIDEE SCIENCE\r\nproject P 33775-N, \"Fast Algorithms for a Reactive Network Layer\".\r\n" alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Antoine full_name: El-Hayek, Antoine id: 888a098e-fcac-11ee-aff7-d347be57b725 last_name: El-Hayek orcid: 0000-0003-4268-7368 citation: ama: 'El-Hayek A. Handling updates and failures: Dynamic graph algorithms and distributed computing on dynamic networks. 2026. doi:10.15479/AT-ISTA-22281' apa: 'El-Hayek, A. (2026). Handling updates and failures: Dynamic graph algorithms and distributed computing on dynamic networks. Institute of Science and Technology Austria. https://doi.org/10.15479/AT-ISTA-22281' chicago: 'El-Hayek, Antoine. “Handling Updates and Failures: Dynamic Graph Algorithms and Distributed Computing on Dynamic Networks.” Institute of Science and Technology Austria, 2026. https://doi.org/10.15479/AT-ISTA-22281.' ieee: 'A. El-Hayek, “Handling updates and failures: Dynamic graph algorithms and distributed computing on dynamic networks,” Institute of Science and Technology Austria, 2026.' ista: 'El-Hayek A. 2026. Handling updates and failures: Dynamic graph algorithms and distributed computing on dynamic networks. Institute of Science and Technology Austria.' mla: 'El-Hayek, Antoine. Handling Updates and Failures: Dynamic Graph Algorithms and Distributed Computing on Dynamic Networks. Institute of Science and Technology Austria, 2026, doi:10.15479/AT-ISTA-22281.' short: 'A. El-Hayek, Handling Updates and Failures: Dynamic Graph Algorithms and Distributed Computing on Dynamic Networks, Institute of Science and Technology Austria, 2026.' corr_author: '1' date_created: 2026-07-13T09:39:59Z date_published: 2026-07-13T00:00:00Z date_updated: 2026-10-21T08:05:35Z day: '13' ddc: - '000' degree_awarded: PhD department: - _id: GradSch - _id: MoHe doi: 10.15479/AT-ISTA-22281 doi_confirm: '1' ec_funded: 1 file: - access_level: open_access checksum: 923e4ca769c9ef2f6b0b005444faf462 content_type: application/pdf creator: aelhayek date_created: 2026-07-17T11:39:47Z date_updated: 2026-07-17T11:39:47Z file_id: '22356' file_name: 2026_El-Hayek_Antoine_Thesis.pdf file_size: 5465973 relation: main_file success: 1 - access_level: closed checksum: 262689f9df27dd6c2c7c7861f1de7329 content_type: application/x-zip-compressed creator: aelhayek date_created: 2026-07-17T11:40:34Z date_updated: 2026-07-20T11:29:38Z file_id: '22357' file_name: 2026_El-Hayek_Antoine_Thesis.zip file_size: 9116107 relation: source_file file_date_updated: 2026-07-20T11:29:38Z fulldoi: https://doi.org/10.15479/AT-ISTA-22281 has_accepted_license: '1' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: '244' 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_identifier: issn: - 2663-337X publication_status: published publisher: Institute of Science and Technology Austria publisher_comment: Sections 2.4 and 7.1 and chapter 6 are not CC-BY 4.0, they are All Rights Reserved. related_material: record: - id: '20051' relation: part_of_dissertation status: public - id: '19982' relation: part_of_dissertation status: public - id: '21720' relation: part_of_dissertation status: public - id: '22374' relation: part_of_dissertation status: public - id: '22373' relation: part_of_dissertation status: public - id: '18557' relation: part_of_dissertation status: public status: public supervisor: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 title: 'Handling updates and failures: Dynamic graph algorithms and distributed computing on dynamic networks' 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: dissertation user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9 year: '2026' ... --- 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' fulldoi: https://doi.org/10.1137/1.9781611978322.95 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: 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 fulldoi: https://doi.org/10.4230/LIPIcs.SAND.2025.4 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: 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 fulldoi: https://doi.org/10.1145/3732772.3733512 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 fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2025.36 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 fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2025.91 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: 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: 2026-07-24T12:48:28Z 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 fulldoi: https://doi.org/10.1145/3732772.3733505 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' related_material: record: - id: '22281' relation: dissertation_contains status: public 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: 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: 2026-07-24T12:48:28Z day: '07' department: - _id: MoHe doi: 10.1137/1.9781611978322.22 ec_funded: 1 external_id: arxiv: - '2412.15069' fulldoi: https://doi.org/10.1137/1.9781611978322.22 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' related_material: record: - id: '22281' relation: dissertation_contains status: public 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: 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-08-20T06:28:00Z 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 fulldoi: https://doi.org/10.4230/lipics.icalp.2025.91 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' related_material: record: - id: '22716' relation: later_version status: public 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' ...