[{"year":"2026","article_number":"29:1-29:15","project":[{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","ddc":["000"],"article_processing_charge":"Yes","date_published":"2026-05-27T00:00:00Z","volume":367,"intvolume":"       367","author":[{"first_name":"Timothy M.","full_name":"Chan, Timothy M.","last_name":"Chan"},{"last_name":"Chang","full_name":"Chang, Hsien Chih","first_name":"Hsien Chih"},{"full_name":"Gao, Jie","last_name":"Gao","first_name":"Jie"},{"first_name":"Sándor","last_name":"Kisfaludi-Bak","full_name":"Kisfaludi-Bak, Sándor"},{"first_name":"Hung","last_name":"Le","full_name":"Le, Hung"},{"id":"af77956b-e859-11ef-8dc9-d301b898e32f","full_name":"Zheng, Da Wei","last_name":"Zheng","first_name":"Da Wei"}],"alternative_title":["LIPIcs"],"_id":"22004","external_id":{"arxiv":["2603.21790"]},"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.","scopus_import":"1","das_tickbox":"0","status":"public","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"file":[{"success":1,"access_level":"open_access","content_type":"application/pdf","relation":"main_file","checksum":"ffff03934cc182757d6db82d88f896e6","file_id":"22114","date_created":"2026-06-22T08:34:11Z","file_name":"2026_LIPIcSSoCG_Chan.pdf","date_updated":"2026-06-22T08:34:11Z","file_size":918197,"creator":"dernst"}],"citation":{"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 <i>42nd International Symposium on Computational Geometry</i>, New Brunswick, NJ, United States, 2026, vol. 367.","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: <i>42nd International Symposium on Computational Geometry</i>. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.29\">10.4230/LIPIcs.SoCG.2026.29</a>","apa":"Chan, T. M., Chang, H. C., Gao, J., Kisfaludi-Bak, S., Le, H., &#38; Zheng, D. W. (2026). Charting the diameter computation landscape of intersection graphs in 3D and above. In <i>42nd International Symposium on Computational Geometry</i> (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.29\">https://doi.org/10.4230/LIPIcs.SoCG.2026.29</a>","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 <i>42nd International Symposium on Computational Geometry</i>, Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.29\">https://doi.org/10.4230/LIPIcs.SoCG.2026.29</a>.","mla":"Chan, Timothy M., et al. “Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above.” <i>42nd International Symposium on Computational Geometry</i>, vol. 367, 29:1-29:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.29\">10.4230/LIPIcs.SoCG.2026.29</a>.","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.","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."},"arxiv":1,"oa_version":"Published Version","quality_controlled":"1","language":[{"iso":"eng"}],"corr_author":"1","month":"05","publication_status":"published","department":[{"_id":"MoHe"}],"day":"27","doi":"10.4230/LIPIcs.SoCG.2026.29","file_date_updated":"2026-06-22T08:34:11Z","type":"conference","date_updated":"2026-06-22T08:37:44Z","abstract":[{"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.","lang":"eng"}],"publication":"42nd International Symposium on Computational Geometry","date_created":"2026-06-14T22:01:44Z","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959774185"]},"keyword":["Graph Diameter","Geometric Intersection Graphs","Unit Ball Graphs"],"conference":{"name":"SoCG: Symposium on Computational Geometry","start_date":"2026-06-02","location":"New Brunswick, NJ, United States","end_date":"2026-06-05"},"oa":1,"has_accepted_license":"1","OA_place":"publisher","title":"Charting the diameter computation landscape of intersection graphs in 3D and above","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"gold"},{"title":"Counting perfect matchings in Dirac hypergraphs","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"hybrid","article_type":"original","OA_place":"publisher","has_accepted_license":"1","oa":1,"publication":"Combinatorica","date_created":"2026-02-08T23:02:49Z","publication_identifier":{"issn":["0209-9683"],"eissn":["1439-6912"]},"abstract":[{"text":"One of the foundational theorems of extremal graph theory is Dirac’s theorem, which\r\nsays that if an n-vertex graph G has minimum degree at least n/2, then G has a\r\nHamilton cycle, and therefore a perfect matching (if n is even). Later work by Sárközy,\r\nSelkow and Szemerédi showed that in fact Dirac graphs have many Hamilton cycles\r\nand perfect matchings, culminating in a result of Cuckler and Kahn that gives a precise\r\ndescription of the numbers of Hamilton cycles and perfect matchings in a Dirac graph\r\nG (in terms of an entropy-like parameter of G). In this paper we extend Cuckler\r\nand Kahn’s result to perfect matchings in hypergraphs. For positive integers d < k,\r\nand for n divisible by k, let md (k, n) be the minimum d-degree that ensures the\r\nexistence of a perfect matching in an n-vertex k-uniform hypergraph. In general, it is\r\nan open question to determine (even asymptotically) the values of md (k, n), but we are\r\nnonetheless able to prove an analogue of the Cuckler–Kahn theorem, showing that if\r\nan n-vertex k-uniform hypergraph G has minimum d-degree at least (1+γ )md (k, n)\r\n(for any constantγ > 0), then the number of perfect matchings in G is controlled by\r\nan entropy-like parameter of G. This strengthens cruder estimates arising from work\r\nof Kang–Kelly–Kühn–Osthus–Pfenninger and Pham–Sah–Sawhney–Simkin.","lang":"eng"}],"type":"journal_article","date_updated":"2026-02-16T09:55:17Z","file_date_updated":"2026-02-16T09:52:38Z","PlanS_conform":"1","department":[{"_id":"MaKw"},{"_id":"MoHe"}],"publication_status":"published","day":"01","doi":"10.1007/s00493-025-00194-8","corr_author":"1","month":"02","oa_version":"Published Version","language":[{"iso":"eng"}],"quality_controlled":"1","arxiv":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"citation":{"ama":"Kwan MA, Safavi Hemami R, Wang Y. Counting perfect matchings in Dirac hypergraphs. <i>Combinatorica</i>. 2026;46. doi:<a href=\"https://doi.org/10.1007/s00493-025-00194-8\">10.1007/s00493-025-00194-8</a>","apa":"Kwan, M. A., Safavi Hemami, R., &#38; Wang, Y. (2026). Counting perfect matchings in Dirac hypergraphs. <i>Combinatorica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00493-025-00194-8\">https://doi.org/10.1007/s00493-025-00194-8</a>","ieee":"M. A. Kwan, R. Safavi Hemami, and Y. Wang, “Counting perfect matchings in Dirac hypergraphs,” <i>Combinatorica</i>, vol. 46. Springer Nature, 2026.","ista":"Kwan MA, Safavi Hemami R, Wang Y. 2026. Counting perfect matchings in Dirac hypergraphs. Combinatorica. 46, 5.","short":"M.A. Kwan, R. Safavi Hemami, Y. Wang, Combinatorica 46 (2026).","mla":"Kwan, Matthew Alan, et al. “Counting Perfect Matchings in Dirac Hypergraphs.” <i>Combinatorica</i>, vol. 46, 5, Springer Nature, 2026, doi:<a href=\"https://doi.org/10.1007/s00493-025-00194-8\">10.1007/s00493-025-00194-8</a>.","chicago":"Kwan, Matthew Alan, Roodabeh Safavi Hemami, and Yiting Wang. “Counting Perfect Matchings in Dirac Hypergraphs.” <i>Combinatorica</i>. Springer Nature, 2026. <a href=\"https://doi.org/10.1007/s00493-025-00194-8\">https://doi.org/10.1007/s00493-025-00194-8</a>."},"file":[{"date_created":"2026-02-16T09:52:38Z","file_id":"21228","file_name":"2026_Combinatorica_Kwan.pdf","date_updated":"2026-02-16T09:52:38Z","creator":"dernst","file_size":539646,"access_level":"open_access","success":1,"content_type":"application/pdf","checksum":"47b0031d90b0e6b9a843f422a1486089","relation":"main_file"}],"status":"public","acknowledgement":"We would like to thank the referees for a number of helpful comments and suggestions, which have substantially improved the paper. Open access funding provided by Institute of Science and Technology (IST Austria).","scopus_import":"1","external_id":{"arxiv":["2408.09589"]},"_id":"21159","author":[{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","last_name":"Kwan","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567"},{"first_name":"Roodabeh","full_name":"Safavi Hemami, Roodabeh","id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","last_name":"Safavi Hemami"},{"id":"1917d194-076e-11ed-97cd-837255f88785","full_name":"Wang, Yiting","last_name":"Wang","first_name":"Yiting","orcid":"0000-0002-2856-767X"}],"intvolume":"        46","volume":46,"date_published":"2026-02-01T00:00:00Z","article_processing_charge":"Yes (via OA deal)","ddc":["510"],"publisher":"Springer Nature","year":"2026","article_number":"5"},{"abstract":[{"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 𝑗-tree decomposition of [Madry FOCS’10], achieving a poly-logarithmic approximation factor to the graph’s cut structure and supporting edge updates in 𝑂⁡(𝑛𝜀) amortized update time, for any arbitrarily small constant 𝜀 ∈(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.","lang":"eng"}],"publication":"Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms","date_created":"2026-04-12T22:01:51Z","publication_identifier":{"issn":["10719040"],"eissn":["15579468"],"isbn":["9781611978971"]},"type":"conference","date_updated":"2026-05-04T11:54:09Z","OA_place":"repository","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Dynamic hierarchical j-tree decomposition and its applications","OA_type":"green","conference":{"name":"SODA: Symposium on Discrete Algorithms"},"oa":1,"status":"public","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2601.09139","open_access":"1"}],"citation":{"ama":"Goranci G, Henzinger M, Kiss P, Momeni A, Zöcklein G. Dynamic hierarchical j-tree decomposition and its applications. In: <i>Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms</i>. Vol 2026-January. Society for Industrial and Applied Mathematics; 2026:1128-1180. doi:<a href=\"https://doi.org/10.1137/1.9781611978971.45\">10.1137/1.9781611978971.45</a>","apa":"Goranci, G., Henzinger, M., Kiss, P., Momeni, A., &#38; Zöcklein, G. (2026). Dynamic hierarchical j-tree decomposition and its applications. In <i>Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms</i> (Vol. 2026–January, pp. 1128–1180). Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611978971.45\">https://doi.org/10.1137/1.9781611978971.45</a>","ieee":"G. Goranci, M. Henzinger, P. Kiss, A. Momeni, and G. Zöcklein, “Dynamic hierarchical j-tree decomposition and its applications,” in <i>Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms</i>, 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.” <i>Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms</i>, vol. 2026–January, Society for Industrial and Applied Mathematics, 2026, pp. 1128–80, doi:<a href=\"https://doi.org/10.1137/1.9781611978971.45\">10.1137/1.9781611978971.45</a>.","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.","chicago":"Goranci, Gramoz, Monika Henzinger, Peter Kiss, Ali Momeni, and Gernot Zöcklein. “Dynamic Hierarchical J-Tree Decomposition and Its Applications.” In <i>Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms</i>, 2026–January:1128–80. Society for Industrial and Applied Mathematics, 2026. <a href=\"https://doi.org/10.1137/1.9781611978971.45\">https://doi.org/10.1137/1.9781611978971.45</a>."},"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.","scopus_import":"1","month":"01","publication_status":"published","department":[{"_id":"MoHe"}],"ec_funded":1,"day":"07","doi":"10.1137/1.9781611978971.45","arxiv":1,"oa_version":"Preprint","quality_controlled":"1","language":[{"iso":"eng"}],"volume":"2026-January","external_id":{"arxiv":["2601.09139"]},"_id":"21719","author":[{"last_name":"Goranci","full_name":"Goranci, Gramoz","first_name":"Gramoz"},{"first_name":"Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","last_name":"Henzinger"},{"first_name":"Peter","last_name":"Kiss","full_name":"Kiss, Peter"},{"full_name":"Momeni, Ali","last_name":"Momeni","first_name":"Ali"},{"last_name":"Zöcklein","full_name":"Zöcklein, Gernot","id":"45d5e826-47af-11f1-84e5-ba87c23fe681","first_name":"Gernot"}],"project":[{"grant_number":"101019564","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982"}],"publisher":"Society for Industrial and Applied Mathematics","year":"2026","date_published":"2026-01-07T00:00:00Z","article_processing_charge":"No","page":"1128-1180"},{"_id":"21720","external_id":{"arxiv":["2512.13105"]},"author":[{"id":"888a098e-fcac-11ee-aff7-d347be57b725","full_name":"El-Hayek, Antoine","last_name":"El-Hayek","first_name":"Antoine","orcid":"0000-0003-4268-7368"},{"orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"first_name":"Jason","last_name":"Li","full_name":"Li, Jason"}],"intvolume":"      2026","volume":2026,"date_published":"2026-01-07T00:00:00Z","article_processing_charge":"No","page":"613-663","publisher":"Society for Industrial and Applied Mathematics","project":[{"name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"year":"2026","OA_place":"repository","OA_type":"green","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time","conference":{"name":"SODA: Symposium on Discrete Algorithms","start_date":"2026-01-11","location":"Vancouver, Canada","end_date":"2026-01-14"},"oa":1,"abstract":[{"text":"We present an exact fully-dynamic minimum cut algorithm that runs in 𝑛𝑜⁡(1) deterministic update time when the minimum cut size is at most 2Θ⁡(log3/4−𝑐⁡𝑛) for any 𝑐 >0, improving on the previous algorithm of Jin, Sun, and Thorup (SODA 2024) whose minimum cut size limit is (log⁡𝑛)𝑜⁡(1). Combined with graph sparsification, we obtain the first (1 +𝜖)-approximate fully-dynamic minimum cut algorithm on weighted graphs, for any 𝜖 ≥2−Θ⁡(log3/4−𝑐⁡𝑛), in 𝑛𝑜⁡(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).","lang":"eng"}],"publication_identifier":{"eissn":["1557-9468"],"eisbn":["9781611978971"],"issn":["1071-9040"]},"publication":"Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms","date_created":"2026-04-12T22:01:51Z","date_updated":"2026-05-04T11:36:47Z","type":"conference","month":"01","day":"07","ec_funded":1,"doi":"10.1137/1.9781611978971.25","publication_status":"published","department":[{"_id":"MoHe"},{"_id":"GradSch"}],"arxiv":1,"language":[{"iso":"eng"}],"oa_version":"Preprint","quality_controlled":"1","status":"public","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2512.13105","open_access":"1"}],"citation":{"ama":"El-Hayek A, Henzinger M, Li J. Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time. In: <i>Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms</i>. Vol 2026. Society for Industrial and Applied Mathematics; 2026:613-663. doi:<a href=\"https://doi.org/10.1137/1.9781611978971.25\">10.1137/1.9781611978971.25</a>","apa":"El-Hayek, A., Henzinger, M., &#38; Li, J. (2026). Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time. In <i>Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms</i> (Vol. 2026, pp. 613–663). Vancouver, Canada: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611978971.25\">https://doi.org/10.1137/1.9781611978971.25</a>","ieee":"A. El-Hayek, M. Henzinger, and J. Li, “Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time,” in <i>Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms</i>, 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.","chicago":"El-Hayek, Antoine, Monika Henzinger, and Jason Li. “Deterministic and Exact Fully-Dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time.” In <i>Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms</i>, 2026:613–63. Society for Industrial and Applied Mathematics, 2026. <a href=\"https://doi.org/10.1137/1.9781611978971.25\">https://doi.org/10.1137/1.9781611978971.25</a>.","mla":"El-Hayek, Antoine, et al. “Deterministic and Exact Fully-Dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time.” <i>Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms</i>, vol. 2026, Society for Industrial and Applied Mathematics, 2026, pp. 613–63, doi:<a href=\"https://doi.org/10.1137/1.9781611978971.25\">10.1137/1.9781611978971.25</a>.","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."},"scopus_import":"1","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."},{"author":[{"first_name":"Gramoz","full_name":"Goranci, Gramoz","last_name":"Goranci"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","first_name":"Monika H"},{"last_name":"Räcke","full_name":"Räcke, Harald","first_name":"Harald"},{"first_name":"A.","full_name":"Sricharan, A.","last_name":"Sricharan"}],"_id":"21280","external_id":{"arxiv":["2502.09105"]},"alternative_title":["LIPIcs"],"volume":334,"intvolume":"       334","article_processing_charge":"No","page":"91:1-91:20","date_published":"2025-06-30T00:00:00Z","year":"2025","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020"},{"name":"Efficient algorithms","grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775"}],"ddc":["000"],"conference":{"location":"Aarhus, Denmark","end_date":"2025-07-11","name":"ICALP: Automata, Languages and Programming","start_date":"2025-07-08"},"oa":1,"has_accepted_license":"1","OA_place":"publisher","OA_type":"gold","title":"Incremental approximate maximum flow via residual graph sparsification","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2026-02-18T09:02:33Z","date_updated":"2026-02-18T09:06:12Z","type":"conference","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."}],"publication_identifier":{"isbn":["9783959773720"]},"date_created":"2026-02-17T08:26:06Z","publication":"52nd International Colloquium on Automata, Languages, and Programming","arxiv":1,"oa_version":"Published Version","language":[{"iso":"eng"}],"quality_controlled":"1","corr_author":"1","month":"06","doi":"10.4230/lipics.icalp.2025.91","day":"30","ec_funded":1,"department":[{"_id":"MoHe"}],"publication_status":"published","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.","scopus_import":"1","status":"public","file":[{"date_created":"2026-02-18T09:02:33Z","file_id":"21315","file_name":"2025_ICALP_Goranci.pdf","date_updated":"2026-02-18T09:02:33Z","file_size":944824,"creator":"dernst","success":1,"access_level":"open_access","content_type":"application/pdf","relation":"main_file","checksum":"c178cf554e44204b9f64ebd9b54cf7ba"}],"citation":{"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.” <i>52nd International Colloquium on Automata, Languages, and Programming</i>, vol. 334, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 91:1-91:20, doi:<a href=\"https://doi.org/10.4230/lipics.icalp.2025.91\">10.4230/lipics.icalp.2025.91</a>.","chicago":"Goranci, Gramoz, Monika Henzinger, Harald Räcke, and A. Sricharan. “Incremental Approximate Maximum Flow via Residual Graph Sparsification.” In <i>52nd International Colloquium on Automata, Languages, and Programming</i>, 334:91:1-91:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/lipics.icalp.2025.91\">https://doi.org/10.4230/lipics.icalp.2025.91</a>.","short":"G. Goranci, M. Henzinger, H. Räcke, A. Sricharan, in:, 52nd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 91:1-91:20.","apa":"Goranci, G., Henzinger, M., Räcke, H., &#38; Sricharan, A. (2025). Incremental approximate maximum flow via residual graph sparsification. In <i>52nd International Colloquium on Automata, Languages, and Programming</i> (Vol. 334, p. 91:1-91:20). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/lipics.icalp.2025.91\">https://doi.org/10.4230/lipics.icalp.2025.91</a>","ama":"Goranci G, Henzinger M, Räcke H, Sricharan A. Incremental approximate maximum flow via residual graph sparsification. In: <i>52nd International Colloquium on Automata, Languages, and Programming</i>. Vol 334. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025:91:1-91:20. doi:<a href=\"https://doi.org/10.4230/lipics.icalp.2025.91\">10.4230/lipics.icalp.2025.91</a>","ieee":"G. Goranci, M. Henzinger, H. Räcke, and A. Sricharan, “Incremental approximate maximum flow via residual graph sparsification,” in <i>52nd International Colloquium on Automata, Languages, and Programming</i>, Aarhus, Denmark, 2025, vol. 334, p. 91:1-91:20."},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"}},{"date_published":"2025-03-01T00:00:00Z","article_processing_charge":"No","page":"881-894","publisher":"Springer Nature","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020"},{"name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"year":"2025","external_id":{"isi":["001176048100003"],"arxiv":["2301.09217"]},"_id":"15121","author":[{"last_name":"Zheng","full_name":"Zheng, Da Wei","first_name":"Da Wei"},{"first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"}],"isi":1,"intvolume":"       210","volume":210,"corr_author":"1","month":"03","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"13236"}]},"day":"01","ec_funded":1,"doi":"10.1007/s10107-024-02066-3","department":[{"_id":"MoHe"}],"publication_status":"published","arxiv":1,"oa_version":"Preprint","language":[{"iso":"eng"}],"quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2301.09217"}],"status":"public","citation":{"ieee":"D. W. Zheng and M. Henzinger, “Multiplicative auction algorithm for approximate maximum weight bipartite matching,” <i>Mathematical Programming</i>, vol. 210. Springer Nature, pp. 881–894, 2025.","ama":"Zheng DW, Henzinger M. Multiplicative auction algorithm for approximate maximum weight bipartite matching. <i>Mathematical Programming</i>. 2025;210:881-894. doi:<a href=\"https://doi.org/10.1007/s10107-024-02066-3\">10.1007/s10107-024-02066-3</a>","apa":"Zheng, D. W., &#38; Henzinger, M. (2025). Multiplicative auction algorithm for approximate maximum weight bipartite matching. <i>Mathematical Programming</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10107-024-02066-3\">https://doi.org/10.1007/s10107-024-02066-3</a>","mla":"Zheng, Da Wei, and Monika Henzinger. “Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching.” <i>Mathematical Programming</i>, vol. 210, Springer Nature, 2025, pp. 881–94, doi:<a href=\"https://doi.org/10.1007/s10107-024-02066-3\">10.1007/s10107-024-02066-3</a>.","chicago":"Zheng, Da Wei, and Monika Henzinger. “Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching.” <i>Mathematical Programming</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s10107-024-02066-3\">https://doi.org/10.1007/s10107-024-02066-3</a>.","short":"D.W. Zheng, M. Henzinger, Mathematical Programming 210 (2025) 881–894.","ista":"Zheng DW, Henzinger M. 2025. Multiplicative auction algorithm for approximate maximum weight bipartite matching. Mathematical Programming. 210, 881–894."},"scopus_import":"1","acknowledgement":"The first author thanks Chandra Chekuri for useful discussions about this paper. This work was done in part at the University of Vienna. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.","OA_place":"repository","article_type":"original","OA_type":"green","title":"Multiplicative auction algorithm for approximate maximum weight bipartite matching","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"abstract":[{"text":"We present an auction algorithm using multiplicative instead of constant weight updates to compute a (1-E)-approximate maximum weight matching (MWM) in a bipartite graph with n vertices and m edges in time 0(mE-1), beating the running time of the fastest known approximation algorithm of Duan and Pettie [JACM ’14] that runs in 0(mE-1 log E-1). Our algorithm is very simple and it can be extended to give a dynamic data structure that maintains a (1-E)-approximate maximum weight matching under (1) one-sided vertex deletions (with incident edges) and (2) one-sided vertex insertions (with incident edges sorted by weight) to the other side. The total time time used is 0(mE-1), where m is the sum of the number of initially existing and inserted edges.","lang":"eng"}],"publication_identifier":{"issn":["0025-5610"],"eissn":["1436-4646"]},"publication":"Mathematical Programming","date_created":"2024-03-17T23:00:58Z","date_updated":"2025-09-09T12:39:58Z","type":"journal_article"},{"publisher":"Association for Computing Machinery","project":[{"grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"name":"Efficient algorithms","grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"year":"2025","date_published":"2025-01-20T00:00:00Z","page":"2951 - 2970","article_processing_charge":"No","intvolume":"         5","volume":5,"external_id":{"arxiv":["2412.02840"]},"_id":"19038","author":[{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"first_name":"Jalaj","last_name":"Upadhyay","full_name":"Upadhyay, Jalaj"}],"citation":{"ieee":"M. Henzinger and J. Upadhyay, “Improved differentially private continual observation using group algebra,” in <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, New Orleans, LA, United States, 2025, vol. 5, pp. 2951–2970.","ama":"Henzinger M, Upadhyay J. Improved differentially private continual observation using group algebra. In: <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 5. Association for Computing Machinery; 2025:2951-2970. doi:<a href=\"https://doi.org/10.1137/1.9781611978322.95\">10.1137/1.9781611978322.95</a>","apa":"Henzinger, M., &#38; Upadhyay, J. (2025). Improved differentially private continual observation using group algebra. In <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 5, pp. 2951–2970). New Orleans, LA, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1137/1.9781611978322.95\">https://doi.org/10.1137/1.9781611978322.95</a>","mla":"Henzinger, Monika, and Jalaj Upadhyay. “Improved Differentially Private Continual Observation Using Group Algebra.” <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 5, Association for Computing Machinery, 2025, pp. 2951–70, doi:<a href=\"https://doi.org/10.1137/1.9781611978322.95\">10.1137/1.9781611978322.95</a>.","chicago":"Henzinger, Monika, and Jalaj Upadhyay. “Improved Differentially Private Continual Observation Using Group Algebra.” In <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 5:2951–70. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1137/1.9781611978322.95\">https://doi.org/10.1137/1.9781611978322.95</a>.","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.","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."},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2412.02840"}],"status":"public","acknowledgement":"Monika Henzinger: This project has received funding from the European Research Council(ERC) under the European Union’s Horizon 2020 research and innovation programme (Grantagreement No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422,grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCEStiftung, 2020–2024.Jalaj Upadhyay’s research was funded by the Rutgers Decanal Grant no. 302918 and an unrestricted giftfrom Google. This work was done in part while visiting the Institute of Science and Technology Austria (ISTA).The authors would like to thank Sarvagya Upadhyay for the initial discussion and feedback on the early draft of the paper. The authors would like to thank the anonymous reviewers, Brendan McMahan and Abhradeep Thakurta for the discussions that helped improve the presentation of the final version of the paper.","scopus_import":"1","ec_funded":1,"doi":"10.1137/1.9781611978322.95","day":"20","publication_status":"published","department":[{"_id":"MoHe"}],"month":"01","quality_controlled":"1","oa_version":"Preprint","language":[{"iso":"eng"}],"arxiv":1,"publication_identifier":{"issn":["1071-9040"],"isbn":["979-833131200-8"]},"publication":"Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms","date_created":"2025-02-17T09:31:03Z","abstract":[{"lang":"eng","text":"Differentially private weighted prefix sum under continual observation is a crucial component in the production-level deployment of private next-word prediction for Gboard, which, according to Google, has over a billion users. More specifically, Google uses a differentially private mechanism to sum weighted gradients in its private follow-the-regularized leader algorithm. Apart from efficiency, the additive error of the private mechanism is crucial as multiplied with the square root of the model’s dimension d (with d ranging up to 10 trillion, for example, Switch Transformers or M6-10T), it determines the accuracy of the learning system. So, any improvement in leading constant matters significantly in practice. In this paper, we show a novel connection between mechanisms for continual weighted prefix sum and a concept in representation theory known as the group matrix introduced in correspondence between Dedekind and Frobenius (Sitzungsber. Preuss. Akad. Wiss. Berlin, 1897) and generalized by Schur (Journal für die reine und angewandte Mathematik, 1904). To the best of our knowledge, this is the first application of group algebra in the analysis of differentially private algorithms. Using this connection, we analyze a class of matrix norms known as factorization norms that give upper and lower bounds for the additive error under general ℓp-norms of the matrix mechanism. This allows us to give 1. the first efficient factorization that matches the best-known non-constructive upper bound on the factorization norm by Mathias (SIAM Journal of Matrix Analysis and Applications, 1993) for the matrix used in Google’s deployment, and also improves on the previous best-known constructive bound of Fichtenberger, Henzinger, and Upadhyay (ICML 2023) and Henzinger, Upadhyay, and Upadhyay (SODA 2023); thereby, partially resolving an open question in operator theory, 2. the first upper bound on the additive error for a large class of weight functions for weighted prefix sum problems, including the sliding window matrix (Bolot, Fawaz, Muthukrishnan, Nikolov, and Taft (ICDT 2013). We also improve the bound on factorizing the striped matrix used for outputting a synthetic graph that approximates all cuts (Fichtenberger, Henzinger, and Upadhyay (ICML 2023)); 3. a general improved upper bound on the factorization norms that depend on algebraic properties of the weighted sum matrices and that applies to a more general class of weighting functions than the ones considered in Henzinger, Upadhyay, and Upadhyay (SODA 2024). Using the known connection between these factorization norms and the ℓp-error of continual weighted sum, we give an upper bound on the ℓp-error for the continual weighted sum problem for p ≥ 2."}],"date_updated":"2025-04-14T13:50:49Z","type":"conference","OA_type":"green","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Improved differentially private continual observation using group algebra","OA_place":"repository","oa":1,"conference":{"start_date":"2025-01-12","name":"SODA: Symposium on Discrete Algorithms","end_date":"2025-01-15","location":"New Orleans, LA, United States"}},{"ddc":["000"],"project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422","name":"Efficient algorithms"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2025","article_number":"4","date_published":"2025-06-02T00:00:00Z","article_processing_charge":"No","intvolume":"       330","volume":330,"alternative_title":["LIPIcs"],"external_id":{"arxiv":["2310.01149"],"isi":["001532136900004"]},"_id":"19858","author":[{"full_name":"El-Hayek, Antoine","id":"888a098e-fcac-11ee-aff7-d347be57b725","last_name":"El-Hayek","orcid":"0000-0003-4268-7368","first_name":"Antoine"},{"full_name":"Hanauer, Kathrin","last_name":"Hanauer","first_name":"Kathrin"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","first_name":"Monika H"}],"isi":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"file":[{"creator":"dernst","file_size":995666,"date_updated":"2025-06-23T11:23:29Z","file_name":"2025_LIPIcs_ElHayek.pdf","date_created":"2025-06-23T11:23:29Z","file_id":"19872","checksum":"ad93a1e052adb29d7bfe8bd551bab193","relation":"main_file","content_type":"application/pdf","access_level":"open_access","success":1}],"citation":{"ieee":"A. El-Hayek, K. Hanauer, and M. Henzinger, “On b-matching and fully-dynamic maximum k-edge coloring,” in <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i>, Liverpool, United Kingdom, 2025, vol. 330.","ama":"El-Hayek A, Hanauer K, Henzinger M. On b-matching and fully-dynamic maximum k-edge coloring. In: <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i>. Vol 330. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2025.4\">10.4230/LIPIcs.SAND.2025.4</a>","apa":"El-Hayek, A., Hanauer, K., &#38; Henzinger, M. (2025). On b-matching and fully-dynamic maximum k-edge coloring. In <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i> (Vol. 330). Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2025.4\">https://doi.org/10.4230/LIPIcs.SAND.2025.4</a>","mla":"El-Hayek, Antoine, et al. “On B-Matching and Fully-Dynamic Maximum k-Edge Coloring.” <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i>, vol. 330, 4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2025.4\">10.4230/LIPIcs.SAND.2025.4</a>.","chicago":"El-Hayek, Antoine, Kathrin Hanauer, and Monika Henzinger. “On B-Matching and Fully-Dynamic Maximum k-Edge Coloring.” In <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i>, Vol. 330. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2025.4\">https://doi.org/10.4230/LIPIcs.SAND.2025.4</a>.","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.","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."},"status":"public","scopus_import":"1","acknowledgement":"This project has received funding from the European Research Council (ERC) under the\r\nEuropean Union’s Horizon 2020 research and innovation programme (MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024. This work was further supported by the Federal Ministry of Education and Research (BMBF) project, 6G-RIC: 6G Research and Innovation Cluster, grant 16KISK020K.","publication_status":"published","department":[{"_id":"MoHe"}],"ec_funded":1,"day":"02","doi":"10.4230/LIPIcs.SAND.2025.4","corr_author":"1","month":"06","oa_version":"Published Version","quality_controlled":"1","language":[{"iso":"eng"}],"arxiv":1,"publication":"4th Symposium on Algorithmic Foundations of Dynamic Networks","date_created":"2025-06-22T22:02:06Z","publication_identifier":{"isbn":["9783959773683"],"issn":["1868-8969"]},"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."}],"type":"conference","date_updated":"2025-09-30T13:37:28Z","file_date_updated":"2025-06-23T11:23:29Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","title":"On b-matching and fully-dynamic maximum k-edge coloring","OA_type":"gold","OA_place":"publisher","has_accepted_license":"1","oa":1,"conference":{"name":"SAND: Symposium on Algorithmic Foundations of Dynamic Networks","start_date":"2025-06-09","location":"Liverpool, United Kingdom","end_date":"2025-06-11"}},{"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.","citation":{"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.","mla":"El-Hayek, Antoine, et al. “Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation.” <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2025, pp. 750–84, doi:<a href=\"https://doi.org/10.1137/1.9781611978322.22\">10.1137/1.9781611978322.22</a>.","chicago":"El-Hayek, Antoine, Monika Henzinger, and Jason Li. “Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation.” In <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 750–84. Society for Industrial and Applied Mathematics, 2025. <a href=\"https://doi.org/10.1137/1.9781611978322.22\">https://doi.org/10.1137/1.9781611978322.22</a>.","ista":"El-Hayek A, Henzinger M, Li J. 2025. Fully dynamic approximate minimum cut in subpolynomial time per operation. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 750–784.","ieee":"A. El-Hayek, M. Henzinger, and J. Li, “Fully dynamic approximate minimum cut in subpolynomial time per operation,” in <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, New Orleans, LA, United States, 2025, pp. 750–784.","ama":"El-Hayek A, Henzinger M, Li J. Fully dynamic approximate minimum cut in subpolynomial time per operation. In: <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2025:750-784. doi:<a href=\"https://doi.org/10.1137/1.9781611978322.22\">10.1137/1.9781611978322.22</a>","apa":"El-Hayek, A., Henzinger, M., &#38; Li, J. (2025). Fully dynamic approximate minimum cut in subpolynomial time per operation. In <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 750–784). New Orleans, LA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611978322.22\">https://doi.org/10.1137/1.9781611978322.22</a>"},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2412.15069"}],"status":"public","oa_version":"Preprint","language":[{"iso":"eng"}],"quality_controlled":"1","arxiv":1,"publication_status":"published","department":[{"_id":"MoHe"}],"ec_funded":1,"doi":"10.1137/1.9781611978322.22","day":"07","corr_author":"1","month":"01","type":"conference","date_updated":"2025-12-29T12:30:04Z","publication":"Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms","date_created":"2025-07-10T13:08:57Z","publication_identifier":{"eisbn":["9781611978322"]},"abstract":[{"text":"Dynamically maintaining the minimum cut in a graph G under edge insertions and deletion is a fundamental problem in dynamic graph algorithms for which no conditional lower bound on the time per operation exists. In an n-node graph the best known (1 + o (1))-approximate algorithm takes  update time [14]. If the minimum cut is guaranteed to be (log n )o (1), a deterministic exact algorithm with n o (1) update time exists [8].\r\nWe present the first fully dynamic algorithm for (1 + o (1))-approximate minimum cut with n o(1) update time. Our main technical contribution is to show that it suffices to consider small-volume cuts in suitably contracted graphs.","lang":"eng"}],"oa":1,"conference":{"start_date":"2025-01-12","name":"SODA: Symposium on Discrete Algorithms","end_date":"2025-01-15","location":"New Orleans, LA, United States"},"title":"Fully dynamic approximate minimum cut in subpolynomial time per operation","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"green","OA_place":"repository","year":"2025","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"grant_number":"Z00422","name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"publisher":"Society for Industrial and Applied Mathematics","page":"750-784","article_processing_charge":"No","date_published":"2025-01-07T00:00:00Z","author":[{"last_name":"El-Hayek","full_name":"El-Hayek, Antoine","id":"888a098e-fcac-11ee-aff7-d347be57b725","orcid":"0000-0003-4268-7368","first_name":"Antoine"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"full_name":"Li, Jason","last_name":"Li","first_name":"Jason"}],"_id":"19982","external_id":{"arxiv":["2412.15069"]}},{"publisher":"Association for Computing Machinery","project":[{"grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"ddc":["000"],"year":"2025","date_published":"2025-06-13T00:00:00Z","article_processing_charge":"Yes (via OA deal)","_id":"20051","external_id":{"arxiv":["2505.02765"],"isi":["001525534800066"]},"author":[{"last_name":"El-Hayek","full_name":"El-Hayek, Antoine","id":"888a098e-fcac-11ee-aff7-d347be57b725","orcid":"0000-0003-4268-7368","first_name":"Antoine"},{"full_name":"Elsässer, Robert","last_name":"Elsässer","first_name":"Robert"},{"full_name":"Schmid, Stefan","last_name":"Schmid","first_name":"Stefan"}],"isi":1,"status":"public","citation":{"mla":"El-Hayek, Antoine, et al. “An Almost Tight Lower Bound for Plurality Consensus with Undecided State Dynamics in the Population Protocol Model.” <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2025, doi:<a href=\"https://doi.org/10.1145/3732772.3733505\">10.1145/3732772.3733505</a>.","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.","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 <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3732772.3733505\">https://doi.org/10.1145/3732772.3733505</a>.","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.","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 <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Huatulco, Mexico, 2025.","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: <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2025. doi:<a href=\"https://doi.org/10.1145/3732772.3733505\">10.1145/3732772.3733505</a>","apa":"El-Hayek, A., Elsässer, R., &#38; Schmid, S. (2025). An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model. In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>. Huatulco, Mexico: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3732772.3733505\">https://doi.org/10.1145/3732772.3733505</a>"},"file":[{"file_id":"20115","date_created":"2025-08-04T09:10:55Z","file_name":"2025_PODC_ElHayek.pdf","date_updated":"2025-08-04T09:10:55Z","file_size":2200347,"creator":"dernst","success":1,"access_level":"open_access","content_type":"application/pdf","relation":"main_file","checksum":"52976d226f3f691aa519d71c1c718fa5"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"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).","corr_author":"1","month":"06","doi":"10.1145/3732772.3733505","ec_funded":1,"day":"13","department":[{"_id":"MoHe"}],"publication_status":"published","arxiv":1,"language":[{"iso":"eng"}],"oa_version":"Published Version","quality_controlled":"1","abstract":[{"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).","lang":"eng"}],"publication_identifier":{"isbn":[" 9798400718854"]},"date_created":"2025-07-21T08:16:15Z","publication":"Proceedings of the ACM Symposium on Principles of Distributed Computing","file_date_updated":"2025-08-04T09:10:55Z","date_updated":"2025-10-16T13:08:45Z","type":"conference","OA_place":"publisher","OA_type":"hybrid","title":"An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2025-06-16","name":"PODC: Symposium on Principles of Distributed Computing","end_date":"2025-06-20","location":"Huatulco, Mexico"},"oa":1,"has_accepted_license":"1"},{"OA_place":"publisher","OA_type":"hybrid","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols","conference":{"end_date":"2025-06-20","location":"Huatulco, Mexico","start_date":"2025-06-16","name":"PODC: Symposium on Principles of Distributed Computing"},"oa":1,"has_accepted_license":"1","abstract":[{"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.","lang":"eng"}],"publication_identifier":{"isbn":["9798400718854"]},"publication":"Proceedings of the ACM Symposium on Principles of Distributed Computing","date_created":"2025-07-21T08:17:04Z","file_date_updated":"2025-08-05T07:32:01Z","date_updated":"2026-02-16T11:46:37Z","type":"conference","month":"06","corr_author":"1","doi":"10.1145/3732772.3733512","day":"13","ec_funded":1,"publication_status":"published","department":[{"_id":"MoHe"}],"language":[{"iso":"eng"}],"oa_version":"Published Version","quality_controlled":"1","status":"public","file":[{"access_level":"open_access","success":1,"content_type":"application/pdf","checksum":"e99679ffb28877b7cea4d54860302790","relation":"main_file","date_created":"2025-08-05T07:32:01Z","file_id":"20123","file_name":"2025_PODC_Breitkopf.pdf","date_updated":"2025-08-05T07:32:01Z","creator":"dernst","file_size":549706}],"citation":{"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 <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Huatulco, Mexico, 2025, pp. 549–552.","apa":"Breitkopf, T.-L., Dallot, J., El-Hayek, A., &#38; Schmid, S. (2025). Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols. In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i> (pp. 549–552). Huatulco, Mexico: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3732772.3733512\">https://doi.org/10.1145/3732772.3733512</a>","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: <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2025:549-552. doi:<a href=\"https://doi.org/10.1145/3732772.3733512\">10.1145/3732772.3733512</a>","mla":"Breitkopf, Tom-Lukas, et al. “Brief Announcement: Minimizing Energy Solves Relative Majority with a Cubic Number of States in Population Protocols.” <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2025, pp. 549–52, doi:<a href=\"https://doi.org/10.1145/3732772.3733512\">10.1145/3732772.3733512</a>.","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 <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, 549–52. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3732772.3733512\">https://doi.org/10.1145/3732772.3733512</a>.","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.","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."},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"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). ","external_id":{"isi":["001525534800069"]},"_id":"20052","isi":1,"author":[{"first_name":"Tom-Lukas","full_name":"Breitkopf, Tom-Lukas","last_name":"Breitkopf"},{"first_name":"Julien","full_name":"Dallot, Julien","last_name":"Dallot"},{"full_name":"El-Hayek, Antoine","id":"888a098e-fcac-11ee-aff7-d347be57b725","last_name":"El-Hayek","orcid":"0000-0003-4268-7368","first_name":"Antoine"},{"full_name":"Schmid, Stefan","last_name":"Schmid","first_name":"Stefan"}],"date_published":"2025-06-13T00:00:00Z","article_processing_charge":"No","page":"549-552","publisher":"Association for Computing Machinery","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer"}],"ddc":["000"],"year":"2025"},{"date_published":"2025-05-01T00:00:00Z","page":"1990-1998","article_processing_charge":"No","publisher":"ML Research Press","project":[{"grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422","name":"Efficient algorithms"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982"},{"grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"year":"2025","_id":"20301","external_id":{"arxiv":["2302.11341"]},"alternative_title":["PMLR"],"author":[{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"full_name":"Sricharan, A. R.","last_name":"Sricharan","first_name":"A. R."},{"full_name":"Steiner, Teresa Anna","last_name":"Steiner","first_name":"Teresa Anna"}],"intvolume":"       258","volume":258,"day":"01","ec_funded":1,"publication_status":"published","department":[{"_id":"MoHe"}],"month":"05","quality_controlled":"1","language":[{"iso":"eng"}],"oa_version":"Preprint","arxiv":1,"citation":{"ieee":"M. Henzinger, A. R. Sricharan, and T. A. Steiner, “Differentially private continual release of histograms and related queries,” in <i>The 28th International Conference on Artificial Intelligence and Statistics</i>, Mai Khao, Thailand, 2025, vol. 258, pp. 1990–1998.","apa":"Henzinger, M., Sricharan, A. R., &#38; Steiner, T. A. (2025). Differentially private continual release of histograms and related queries. In <i>The 28th International Conference on Artificial Intelligence and Statistics</i> (Vol. 258, pp. 1990–1998). Mai Khao, Thailand: ML Research Press.","ama":"Henzinger M, Sricharan AR, Steiner TA. Differentially private continual release of histograms and related queries. In: <i>The 28th International Conference on Artificial Intelligence and Statistics</i>. Vol 258. ML Research Press; 2025:1990-1998.","short":"M. Henzinger, A.R. Sricharan, T.A. Steiner, in:, The 28th International Conference on Artificial Intelligence and Statistics, ML Research Press, 2025, pp. 1990–1998.","mla":"Henzinger, Monika, et al. “Differentially Private Continual Release of Histograms and Related Queries.” <i>The 28th International Conference on Artificial Intelligence and Statistics</i>, vol. 258, ML Research Press, 2025, pp. 1990–98.","chicago":"Henzinger, Monika, A. R. Sricharan, and Teresa Anna Steiner. “Differentially Private Continual Release of Histograms and Related Queries.” In <i>The 28th International Conference on Artificial Intelligence and Statistics</i>, 258:1990–98. ML Research Press, 2025.","ista":"Henzinger M, Sricharan AR, Steiner TA. 2025. Differentially private continual release of histograms and related queries. The 28th International Conference on Artificial Intelligence and Statistics. AISTATS: Conference on Artificial Intelligence and Statistics, PMLR, vol. 258, 1990–1998."},"status":"public","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2302.11341"}],"scopus_import":"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.","OA_type":"green","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Differentially private continual release of histograms and related queries","OA_place":"repository","oa":1,"conference":{"name":"AISTATS: Conference on Artificial Intelligence and Statistics","start_date":"2025-05-03","location":"Mai Khao, Thailand","end_date":"2025-05-05"},"publication_identifier":{"eissn":["2640-3498"]},"publication":"The 28th International Conference on Artificial Intelligence and Statistics","date_created":"2025-09-07T22:01:35Z","abstract":[{"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}). ","lang":"eng"}],"date_updated":"2025-09-09T07:09:22Z","type":"conference"},{"month":"10","corr_author":"1","publication_status":"published","department":[{"_id":"MoHe"}],"doi":"10.4230/LIPIcs.ESA.2025.2","day":"01","oa_version":"Published Version","language":[{"iso":"eng"}],"quality_controlled":"1","status":"public","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"file":[{"file_id":"20541","date_created":"2025-10-27T07:57:00Z","file_name":"2025_LIPIcs.ESA_Henzinger.pdf","date_updated":"2025-10-27T07:57:00Z","creator":"dernst","file_size":770227,"access_level":"open_access","success":1,"content_type":"application/pdf","checksum":"094e0466d90664fbea397b469a60acbb","relation":"main_file"}],"citation":{"ista":"Henzinger M, Safavi Hemami R. 2025. Securing dynamic data: A primer on differentially private data structures. 33rd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 351, 2.","chicago":"Henzinger, Monika, and Roodabeh Safavi Hemami. “Securing Dynamic Data: A Primer on Differentially Private Data Structures.” In <i>33rd Annual European Symposium on Algorithms</i>, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.2\">https://doi.org/10.4230/LIPIcs.ESA.2025.2</a>.","mla":"Henzinger, Monika, and Roodabeh Safavi Hemami. “Securing Dynamic Data: A Primer on Differentially Private Data Structures.” <i>33rd Annual European Symposium on Algorithms</i>, vol. 351, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.2\">10.4230/LIPIcs.ESA.2025.2</a>.","short":"M. Henzinger, R. Safavi Hemami, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","ama":"Henzinger M, Safavi Hemami R. Securing dynamic data: A primer on differentially private data structures. In: <i>33rd Annual European Symposium on Algorithms</i>. Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.2\">10.4230/LIPIcs.ESA.2025.2</a>","apa":"Henzinger, M., &#38; Safavi Hemami, R. (2025). Securing dynamic data: A primer on differentially private data structures. In <i>33rd Annual European Symposium on Algorithms</i> (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.2\">https://doi.org/10.4230/LIPIcs.ESA.2025.2</a>","ieee":"M. Henzinger and R. Safavi Hemami, “Securing dynamic data: A primer on differentially private data structures,” in <i>33rd Annual European Symposium on Algorithms</i>, Warsaw, Poland, 2025, vol. 351."},"scopus_import":"1","OA_place":"publisher","title":"Securing dynamic data: A primer on differentially private data structures","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"gold","conference":{"name":"ESA: European Symposium on Algorithms","start_date":"2025-09-15","location":"Warsaw, Poland","end_date":"2025-09-17"},"oa":1,"has_accepted_license":"1","abstract":[{"lang":"eng","text":"We give an introduction into differential privacy in the dynamic setting, called the continual observation setting."}],"publication":"33rd Annual European Symposium on Algorithms","date_created":"2025-10-26T23:01:34Z","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773959"]},"file_date_updated":"2025-10-27T07:57:00Z","type":"conference","date_updated":"2025-10-27T08:00:13Z","date_published":"2025-10-01T00:00:00Z","article_processing_charge":"No","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","ddc":["000"],"year":"2025","article_number":"2","alternative_title":["LIPIcs"],"_id":"20533","author":[{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Safavi Hemami","id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","full_name":"Safavi Hemami, Roodabeh","first_name":"Roodabeh"}],"intvolume":"       351","volume":351},{"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"citation":{"short":"M. Henzinger, E. Kosinas, R. Münk, H. Räcke, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","mla":"Henzinger, Monika, et al. “Efficient Contractions of Dynamic Graphs - with Applications.” <i>33rd Annual European Symposium on Algorithms</i>, vol. 351, 36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.36\">10.4230/LIPIcs.ESA.2025.36</a>.","chicago":"Henzinger, Monika, Evangelos Kosinas, Robin Münk, and Harald Räcke. “Efficient Contractions of Dynamic Graphs - with Applications.” In <i>33rd Annual European Symposium on Algorithms</i>, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.36\">https://doi.org/10.4230/LIPIcs.ESA.2025.36</a>.","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.","ieee":"M. Henzinger, E. Kosinas, R. Münk, and H. Räcke, “Efficient contractions of dynamic graphs - with applications,” in <i>33rd Annual European Symposium on Algorithms</i>, Warsaw, Poland, 2025, vol. 351.","apa":"Henzinger, M., Kosinas, E., Münk, R., &#38; Räcke, H. (2025). Efficient contractions of dynamic graphs - with applications. In <i>33rd Annual European Symposium on Algorithms</i> (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.36\">https://doi.org/10.4230/LIPIcs.ESA.2025.36</a>","ama":"Henzinger M, Kosinas E, Münk R, Räcke H. Efficient contractions of dynamic graphs - with applications. In: <i>33rd Annual European Symposium on Algorithms</i>. Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.36\">10.4230/LIPIcs.ESA.2025.36</a>"},"file":[{"access_level":"open_access","success":1,"checksum":"d2daf9a467e96fb5e7084a8a85321776","relation":"main_file","content_type":"application/pdf","file_name":"2025_LIPIcs.ESA_HenzingerM.pdf","date_created":"2025-10-27T08:03:36Z","file_id":"20542","creator":"dernst","file_size":934846,"date_updated":"2025-10-27T08:03:36Z"}],"status":"public","scopus_import":"1","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.","department":[{"_id":"MoHe"}],"publication_status":"published","ec_funded":1,"day":"01","doi":"10.4230/LIPIcs.ESA.2025.36","corr_author":"1","month":"10","oa_version":"Published Version","language":[{"iso":"eng"}],"quality_controlled":"1","arxiv":1,"date_created":"2025-10-26T23:01:34Z","publication":"33rd Annual European Symposium on Algorithms","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773959"]},"abstract":[{"text":"A non-trivial minimum cut (NMC) sparsifier is a multigraph Ĝ that preserves all non-trivial minimum cuts of a given undirected graph G. We introduce a flexible data structure for fully dynamic graphs that can efficiently provide an NMC sparsifier upon request at any point during the sequence of updates. We employ simple dynamic forest data structures to achieve a fast from-scratch construction of the sparsifier at query time. Based on the strength of the adversary and desired type of time bounds, the data structure comes with different guarantees. Specifically, let G be a fully dynamic simple graph with n vertices and minimum degree δ. Then our data structure supports an insertion/deletion of an edge to/from G in n^o(1) worst-case time. Furthermore, upon request, it can return w.h.p. an NMC sparsifier of G that has O(n/δ) vertices and O(n) edges, in Ô(n) time. The probabilistic guarantees hold against an adaptive adversary. Alternatively, the update and query times can be improved to Õ(1) and Õ(n) respectively, if amortized-time guarantees are sufficient, or if the adversary is oblivious. Throughout the paper, we use Õ to hide polylogarithmic factors and Ô to hide subpolynomial (i.e., n^o(1)) factors.\r\nWe discuss two applications of our new data structure. First, it can be used to efficiently report a cactus representation of all minimum cuts of a fully dynamic simple graph. Building this cactus for the NMC sparsifier instead of the original graph allows for a construction time that is sublinear in the number of edges. Against an adaptive adversary, we can with high probability output the cactus representation in worst-case Ô(n) time. Second, our data structure allows us to efficiently compute the maximal k-edge-connected subgraphs of undirected simple graphs, by repeatedly applying a minimum cut algorithm on the NMC sparsifier. Specifically, we can compute with high probability the maximal k-edge-connected subgraphs of a simple graph with n vertices and m edges in Õ(m+n²/k) time. This improves the best known time bounds for k = Ω(n^{1/8}) and naturally extends to the case of fully dynamic graphs.","lang":"eng"}],"type":"conference","date_updated":"2025-10-27T08:05:46Z","file_date_updated":"2025-10-27T08:03:36Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Efficient contractions of dynamic graphs - with applications","OA_type":"gold","OA_place":"publisher","has_accepted_license":"1","oa":1,"conference":{"name":"ESA: European Symposium on Algorithms","start_date":"2025-09-15","location":"Warsaw, Poland","end_date":"2025-09-17"},"ddc":["000"],"project":[{"call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"grant_number":"Z00422","name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2025","article_number":"36","date_published":"2025-10-01T00:00:00Z","article_processing_charge":"No","intvolume":"       351","volume":351,"_id":"20534","external_id":{"arxiv":["2509.05157"]},"author":[{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","first_name":"Monika H"},{"first_name":"Evangelos","full_name":"Kosinas, Evangelos","id":"4c7f9625-dbbc-11ee-9d86-bdcc2db5a949","last_name":"Kosinas"},{"last_name":"Münk","full_name":"Münk, Robin","first_name":"Robin"},{"first_name":"Harald","last_name":"Räcke","full_name":"Räcke, Harald"}]},{"arxiv":1,"oa_version":"Published Version","language":[{"iso":"eng"}],"quality_controlled":"1","corr_author":"1","month":"10","day":"01","doi":"10.4230/LIPIcs.ESA.2025.91","ec_funded":1,"publication_status":"published","department":[{"_id":"MoHe"}],"scopus_import":"1","acknowledgement":"Monika Henzinger and A. R. Sricharan: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation\r\nprogramme (MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant DOI\r\n10.55776/Z422 and grant DOI 10.55776/I5982. Laxman Dhulipala and George Z. Li: supported by NSF award number CNS-2317194. Quanquan C. Liu: supported by a Google Academic Research Award and by an NSF award number CCF-2453323.","status":"public","file":[{"checksum":"19146e935b5b6ad5d33c8d08280ad8e7","relation":"main_file","content_type":"application/pdf","access_level":"open_access","success":1,"creator":"dernst","file_size":870317,"date_updated":"2025-10-27T06:58:43Z","file_name":"2025_LIPIcs.ESA_Dhulipala.pdf","file_id":"20539","date_created":"2025-10-27T06:58:43Z"}],"citation":{"chicago":"Dhulipala, Laxman, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, and Leqi Zhu. “Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism.” In <i>33rd Annual European Symposium on Algorithms</i>, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.91\">https://doi.org/10.4230/LIPIcs.ESA.2025.91</a>.","mla":"Dhulipala, Laxman, et al. “Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism.” <i>33rd Annual European Symposium on Algorithms</i>, vol. 351, 91, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.91\">10.4230/LIPIcs.ESA.2025.91</a>.","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.","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.","ieee":"L. Dhulipala, M. Henzinger, G. Z. Li, Q. C. Liu, A. R. Sricharan, and L. Zhu, “Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism,” in <i>33rd Annual European Symposium on Algorithms</i>, Warsaw, Poland, 2025, vol. 351.","ama":"Dhulipala L, Henzinger M, Li GZ, Liu QC, Sricharan AR, Zhu L. Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism. In: <i>33rd Annual European Symposium on Algorithms</i>. Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.91\">10.4230/LIPIcs.ESA.2025.91</a>","apa":"Dhulipala, L., Henzinger, M., Li, G. Z., Liu, Q. C., Sricharan, A. R., &#38; Zhu, L. (2025). Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism. In <i>33rd Annual European Symposium on Algorithms</i> (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.91\">https://doi.org/10.4230/LIPIcs.ESA.2025.91</a>"},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"conference":{"name":"ESA: European Symposium on Algorithms","start_date":"2025-09-15","location":"Warsaw, Poland","end_date":"2025-09-17"},"has_accepted_license":"1","oa":1,"OA_place":"publisher","OA_type":"gold","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism","file_date_updated":"2025-10-27T06:58:43Z","date_updated":"2025-10-27T07:02:06Z","type":"conference","abstract":[{"text":"Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the k-core decomposition problem, the classic peeling algorithm iteratively removes a vertex if its induced degree falls below a threshold. The sparse vector technique (SVT) is generally used to transform non-private threshold queries into private ones with only a small additive loss in accuracy. However, a naive application of SVT in the graph setting leads to an amplification of the error by a factor of n due to composition, as SVT is applied to every vertex. In this paper, we resolve this problem by formulating a novel generalized sparse vector technique which we call the Multidimensional AboveThreshold (MAT) Mechanism which generalizes SVT (applied to vectors with one dimension) to vectors with multiple dimensions. When applied to vectors with n dimensions, we solve a number of important graph problems with better bounds than previous work.\r\nSpecifically, we apply our MAT mechanism to obtain a set of improved bounds for a variety of problems including k-core decomposition, densest subgraph, low out-degree ordering, and vertex coloring. We give a tight local edge differentially private (LEDP) algorithm for k-core decomposition that results in an approximation with O(ε^{-1} log n) additive error and no multiplicative error in O(n) rounds. We also give a new (2+η)-factor multiplicative, O(ε^{-1} log n) additive error algorithm in O(log² n) rounds for any constant η > 0. Both of these results are asymptotically tight against our new lower bound of Ω(log n) for any constant-factor approximation algorithm for k-core decomposition. Our new algorithms for k-core decomposition also directly lead to new algorithms for the related problems of densest subgraph and low out-degree ordering. Finally, we give novel LEDP differentially private defective coloring algorithms that use number of colors given in terms of the arboricity of the graph.","lang":"eng"}],"publication_identifier":{"isbn":["9783959773959"],"issn":["1868-8969"]},"publication":"33rd Annual European Symposium on Algorithms","date_created":"2025-10-26T23:01:35Z","article_processing_charge":"No","date_published":"2025-10-01T00:00:00Z","article_number":"91","year":"2025","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"grant_number":"Z00422","name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"ddc":["000"],"author":[{"last_name":"Dhulipala","full_name":"Dhulipala, Laxman","first_name":"Laxman"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","first_name":"Monika H"},{"last_name":"Li","full_name":"Li, George Z.","first_name":"George Z."},{"full_name":"Liu, Quanquan C.","last_name":"Liu","first_name":"Quanquan C."},{"last_name":"Sricharan","full_name":"Sricharan, A. R.","first_name":"A. R."},{"id":"a2117c59-cee4-11ed-b9d0-874ecf0f8ac5","full_name":"Zhu, Leqi","last_name":"Zhu","first_name":"Leqi"}],"external_id":{"arxiv":["2508.02182"]},"_id":"20535","alternative_title":["LIPIcs"],"volume":351,"intvolume":"       351"},{"type":"conference","date_updated":"2025-10-27T07:10:49Z","file_date_updated":"2025-10-27T07:09:41Z","date_created":"2025-10-26T23:01:35Z","publication":"19th International Symposium on Algorithms and Data Structures","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773980"]},"abstract":[{"text":"Uniquely represented (UR) data structures represent each logical state with a unique storage state. We study the problem of maintaining a dynamic set of n keys from a totally ordered universe in this context. UR structures are also called \"strongly history independent\" structures in the literature.\r\nWe introduce a two-layer data structure called (α,ε)-Randomized Block Search Tree (RBST) that is uniquely represented and suitable for external memory (EM). Though RBSTs naturally generalize the well-known binary Treaps, several new ideas are needed to analyze the expected search, update, and storage efficiency in terms of block-reads, block-writes, and blocks stored. We prove that searches have O(ε^{-1} + log_α n) block-reads, that dynamic updates perform O(ε^{-1} + log_α(n)/α) block-writes and O(ε^{-2}+(1+(ε^{-1}+log n)/α)log_α n) block-reads, and that (α, ε)-RBSTs have an asymptotic load-factor of at least (1-ε) for every ε ∈ (0,1/2].\r\nThus (α, ε)-RBSTs improve on the known, uniquely represented B-Treap [Golovin; ICALP'09]. Compared with non-UR structures, the RBST is also, to the best of our knowledge, the first external memory structure that is storage-efficient and has a non-amortized, write-efficient update bound.","lang":"eng"}],"oa":1,"has_accepted_license":"1","conference":{"start_date":"2025-08-11","name":"WADS: Algorithms and Data Structures Symposium","end_date":"2025-08-15","location":"Toronto, Canada"},"title":"B-Treaps revised: Write efficient randomized block search trees with high load","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_type":"gold","OA_place":"publisher","scopus_import":"1","acknowledgement":"This work was supported under the Australian Research Council Discovery Projects\r\nfunding scheme (project number DP180102870). This project has received funding from the\r\nEuropean Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564) “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project Z 422-N and project “Fast Algorithms for a Reactive Network Layer (ReactNet)” P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"file":[{"file_size":1081870,"creator":"dernst","date_updated":"2025-10-27T07:09:41Z","file_name":"2025_LIPIcs.WADS_Safavi.pdf","file_id":"20540","date_created":"2025-10-27T07:09:41Z","relation":"main_file","checksum":"196af33762831a78e87f4f95ecd8677b","content_type":"application/pdf","success":1,"access_level":"open_access"}],"citation":{"short":"R. Safavi Hemami, M.P. Seybold, in:, 19th International Symposium on Algorithms and Data Structures, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","chicago":"Safavi Hemami, Roodabeh, and Martin P. Seybold. “B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load.” In <i>19th International Symposium on Algorithms and Data Structures</i>, Vol. 349. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.WADS.2025.47\">https://doi.org/10.4230/LIPIcs.WADS.2025.47</a>.","mla":"Safavi Hemami, Roodabeh, and Martin P. Seybold. “B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load.” <i>19th International Symposium on Algorithms and Data Structures</i>, vol. 349, 47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.WADS.2025.47\">10.4230/LIPIcs.WADS.2025.47</a>.","ista":"Safavi Hemami R, Seybold MP. 2025. B-Treaps revised: Write efficient randomized block search trees with high load. 19th International Symposium on Algorithms and Data Structures. WADS: Algorithms and Data Structures Symposium, LIPIcs, vol. 349, 47.","ieee":"R. Safavi Hemami and M. P. Seybold, “B-Treaps revised: Write efficient randomized block search trees with high load,” in <i>19th International Symposium on Algorithms and Data Structures</i>, Toronto, Canada, 2025, vol. 349.","apa":"Safavi Hemami, R., &#38; Seybold, M. P. (2025). B-Treaps revised: Write efficient randomized block search trees with high load. In <i>19th International Symposium on Algorithms and Data Structures</i> (Vol. 349). Toronto, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.WADS.2025.47\">https://doi.org/10.4230/LIPIcs.WADS.2025.47</a>","ama":"Safavi Hemami R, Seybold MP. B-Treaps revised: Write efficient randomized block search trees with high load. In: <i>19th International Symposium on Algorithms and Data Structures</i>. Vol 349. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.WADS.2025.47\">10.4230/LIPIcs.WADS.2025.47</a>"},"status":"public","oa_version":"Published Version","language":[{"iso":"eng"}],"quality_controlled":"1","arxiv":1,"department":[{"_id":"MoHe"}],"publication_status":"published","ec_funded":1,"doi":"10.4230/LIPIcs.WADS.2025.47","day":"29","month":"08","corr_author":"1","volume":349,"intvolume":"       349","author":[{"first_name":"Roodabeh","full_name":"Safavi Hemami, Roodabeh","id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","last_name":"Safavi Hemami"},{"first_name":"Martin P.","full_name":"Seybold, Martin P.","last_name":"Seybold"}],"alternative_title":["LIPIcs"],"_id":"20536","external_id":{"arxiv":["2303.04722"]},"year":"2025","article_number":"47","ddc":["000"],"project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"grant_number":"Z00422","name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_processing_charge":"No","date_published":"2025-08-29T00:00:00Z"},{"ddc":["000"],"publisher":"ML Research Press","year":"2025","date_published":"2025-05-01T00:00:00Z","page":"53757-53790","article_processing_charge":"No","intvolume":"       267","volume":267,"alternative_title":["PMLR"],"_id":"20819","external_id":{"arxiv":["2506.05408"]},"author":[{"full_name":"Scott, Jonathan A","id":"e499926b-f6e0-11ea-865d-9c63db0031e8","last_name":"Scott","first_name":"Jonathan A"},{"orcid":"0000-0001-8622-7887","first_name":"Christoph","full_name":"Lampert, Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","last_name":"Lampert"},{"first_name":"David","last_name":"Saulpic","id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964","full_name":"Saulpic, David"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"citation":{"chicago":"Scott, Jonathan A, Christoph Lampert, and David Saulpic. “Differentially Private Federated K-Means Clustering with Server-Side Data.” In <i>42nd International Conference on Machine Learning</i>, 267:53757–90. ML Research Press, 2025.","short":"J.A. Scott, C. Lampert, D. Saulpic, in:, 42nd International Conference on Machine Learning, ML Research Press, 2025, pp. 53757–53790.","mla":"Scott, Jonathan A., et al. “Differentially Private Federated K-Means Clustering with Server-Side Data.” <i>42nd International Conference on Machine Learning</i>, vol. 267, ML Research Press, 2025, pp. 53757–90.","ista":"Scott JA, Lampert C, Saulpic D. 2025. Differentially private federated k-means clustering with server-side data. 42nd International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 267, 53757–53790.","ieee":"J. A. Scott, C. Lampert, and D. Saulpic, “Differentially private federated k-means clustering with server-side data,” in <i>42nd International Conference on Machine Learning</i>, Vancouver, Canada, 2025, vol. 267, pp. 53757–53790.","apa":"Scott, J. A., Lampert, C., &#38; Saulpic, D. (2025). Differentially private federated k-means clustering with server-side data. In <i>42nd International Conference on Machine Learning</i> (Vol. 267, pp. 53757–53790). Vancouver, Canada: ML Research Press.","ama":"Scott JA, Lampert C, Saulpic D. Differentially private federated k-means clustering with server-side data. In: <i>42nd International Conference on Machine Learning</i>. Vol 267. ML Research Press; 2025:53757-53790."},"file":[{"content_type":"application/pdf","relation":"main_file","checksum":"815b32b463023ca21e569c2158745c15","success":1,"access_level":"open_access","date_updated":"2025-12-16T12:38:29Z","file_size":746612,"creator":"dernst","file_id":"20829","date_created":"2025-12-16T12:38:29Z","file_name":"2025_ICML_Scott.pdf"}],"status":"public","acknowledgement":"This research was funded in part by the Austrian Science Fund (FWF) [10.55776/COE12] and supported by the Scientific Service Units (SSU) of ISTA through resources provided by Scientific Computing (SciComp).\r\n","scopus_import":"1","publication_status":"published","department":[{"_id":"ChLa"},{"_id":"MoHe"}],"day":"01","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"21198"}]},"month":"05","corr_author":"1","quality_controlled":"1","oa_version":"Published Version","language":[{"iso":"eng"}],"arxiv":1,"acknowledged_ssus":[{"_id":"ScienComp"}],"date_created":"2025-12-14T23:02:05Z","publication":"42nd International Conference on Machine Learning","publication_identifier":{"eissn":["2640-3498"]},"abstract":[{"text":"Clustering is a cornerstone of data analysis that is particularly suited to identifying coherent subgroups or substructures in unlabeled data, as are generated continuously in large amounts these days. However, in many cases traditional clustering methods are not applicable, because data are increasingly being produced and stored in a distributed way, e.g. on edge devices, and privacy concerns prevent it from being transferred to a central server. To address this challenge, we present FedDP-KMeans, a new algorithm for \r\n-means clustering that is fully-federated as well as differentially private. Our approach leverages (potentially small and out-of-distribution) server-side data to overcome the primary challenge of differentially private clustering methods: the need for a good initialization. Combining our initialization with a simple federated DP-Lloyds algorithm we obtain an algorithm that achieves excellent results on synthetic and real-world benchmark tasks. We also provide a theoretical analysis of our method that provides bounds on the convergence speed and cluster identification success.","lang":"eng"}],"type":"conference","date_updated":"2026-04-07T11:46:11Z","file_date_updated":"2025-12-16T12:38:29Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Differentially private federated k-means clustering with server-side data","OA_type":"gold","OA_place":"publisher","oa":1,"has_accepted_license":"1","conference":{"start_date":"2025-07-13","name":"ICML: International Conference on Machine Learning","end_date":"2025-07-19","location":"Vancouver, Canada"}},{"article_processing_charge":"No","page":"220-233","date_published":"2024-01-04T00:00:00Z","year":"2024","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422","name":"Efficient algorithms"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"},{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020"}],"publisher":"Society for Industrial and Applied Mathematics","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Saulpic","full_name":"Saulpic, David","id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964","first_name":"David"},{"first_name":"Leonhard","last_name":"Sidl","full_name":"Sidl, Leonhard","id":"8b563fd0-b441-11ee-9101-a3891c61efa6"}],"_id":"14769","external_id":{"arxiv":["2310.18034"]},"arxiv":1,"oa_version":"Preprint","quality_controlled":"1","language":[{"iso":"eng"}],"corr_author":"1","month":"01","publication_status":"published","department":[{"_id":"MoHe"}],"doi":"10.1137/1.9781611977929.17","ec_funded":1,"day":"04","acknowledgement":"This   project   has   received   funding   from   the   Euro-pean  Research  Council  (ERC)  under  the  EuropeanUnion’s  Horizon  2020  research  and  innovation  programme  (Grant  agreement  No.   101019564  “The  De-sign  of  Modern  Fully  Dynamic  Data  Structures  (Mo-DynStruct)”  and  the  Austrian  Science  Fund  (FWF)project Z 422-N, project “Static and Dynamic Hierar-chical  Graph  Decompositions”,  I  5982-N,  and  project“Fast  Algorithms  for  a  Reactive  Network  Layer  (Re-actNet)”, P 33775-N, with additional funding from thenetidee SCIENCE Stiftung, 2020–2024.D.  Sauplic  has  received  funding  from  the  Euro-pean  Union’s  Horizon  2020  research  and  innovation programme under the Marie Sklodowska-Curie    grant    agreementNo 101034413.","scopus_import":"1","status":"public","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2310.18034"}],"citation":{"ama":"Henzinger M, Saulpic D, Sidl L. Experimental evaluation of fully dynamic k-means via coresets. In: <i>2024 Proceedings of the Symposium on Algorithm Engineering and Experiments</i>. Society for Industrial and Applied Mathematics; 2024:220-233. doi:<a href=\"https://doi.org/10.1137/1.9781611977929.17\">10.1137/1.9781611977929.17</a>","apa":"Henzinger, M., Saulpic, D., &#38; Sidl, L. (2024). Experimental evaluation of fully dynamic k-means via coresets. In <i>2024 Proceedings of the Symposium on Algorithm Engineering and Experiments</i> (pp. 220–233). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977929.17\">https://doi.org/10.1137/1.9781611977929.17</a>","ieee":"M. Henzinger, D. Saulpic, and L. Sidl, “Experimental evaluation of fully dynamic k-means via coresets,” in <i>2024 Proceedings of the Symposium on Algorithm Engineering and Experiments</i>, Alexandria, VA, United States, 2024, pp. 220–233.","ista":"Henzinger M, Saulpic D, Sidl L. 2024. Experimental evaluation of fully dynamic k-means via coresets. 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments. ALENEX: Workshop on Algorithm Engineering and Experiments, 220–233.","mla":"Henzinger, Monika, et al. “Experimental Evaluation of Fully Dynamic K-Means via Coresets.” <i>2024 Proceedings of the Symposium on Algorithm Engineering and Experiments</i>, Society for Industrial and Applied Mathematics, 2024, pp. 220–33, doi:<a href=\"https://doi.org/10.1137/1.9781611977929.17\">10.1137/1.9781611977929.17</a>.","chicago":"Henzinger, Monika, David Saulpic, and Leonhard Sidl. “Experimental Evaluation of Fully Dynamic K-Means via Coresets.” In <i>2024 Proceedings of the Symposium on Algorithm Engineering and Experiments</i>, 220–33. Society for Industrial and Applied Mathematics, 2024. <a href=\"https://doi.org/10.1137/1.9781611977929.17\">https://doi.org/10.1137/1.9781611977929.17</a>.","short":"M. Henzinger, D. Saulpic, L. Sidl, in:, 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2024, pp. 220–233."},"conference":{"start_date":"2024-01-07","name":"ALENEX: Workshop on Algorithm Engineering and Experiments","end_date":"2024-01-08","location":"Alexandria, VA, United States"},"oa":1,"title":"Experimental evaluation of fully dynamic k-means via coresets","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","date_updated":"2025-04-14T13:50:50Z","abstract":[{"text":"For a set of points in Rd, the Euclidean k-means problems consists of finding k centers such that the sum of distances squared from each data point to its closest center is minimized. Coresets are one the main tools developed recently to solve this problem in a big data context. They allow to compress the initial dataset while preserving its structure: running any algorithm on the coreset provides a guarantee almost equivalent to running it on the full data. In this work, we study coresets in a fully-dynamic setting: points are added and deleted with the goal to efficiently maintain a coreset with which a k-means solution can be computed. Based on an algorithm from Henzinger and Kale [ESA'20], we present an efficient and practical implementation of a fully dynamic coreset algorithm, that improves the running time by up to a factor of 20 compared to our non-optimized implementation of the algorithm by Henzinger and Kale, without sacrificing more than 7% on the quality of the k-means solution.","lang":"eng"}],"publication":"2024 Proceedings of the Symposium on Algorithm Engineering and Experiments","date_created":"2024-01-09T16:22:47Z","publication_identifier":{"eisbn":["9781611977929"]}},{"file_date_updated":"2024-02-26T10:10:48Z","date_updated":"2025-09-04T12:06:25Z","type":"conference","abstract":[{"lang":"eng","text":"Oblivious routing is a well-studied paradigm that uses static precomputed routing tables for selecting routing paths within a network. Existing oblivious routing schemes with polylogarithmic competitive ratio for general networks are tree-based, in the sense that routing is performed according to a convex combination of trees. However, this restriction to trees leads to a construction that has time quadratic in the size of the network and does not parallelize well. \r\nIn this paper we study oblivious routing schemes based on electrical routing. In particular, we show that general networks with n vertices and m edges admit a routing scheme that has competitive ratio O(log² n) and consists of a convex combination of only O(√m) electrical routings. This immediately leads to an improved construction algorithm with time Õ(m^{3/2}) that can also be implemented in parallel with Õ(√m) depth."}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773096"]},"date_created":"2024-02-18T23:01:02Z","publication":"15th Innovations in Theoretical Computer Science Conference","conference":{"start_date":"2024-01-30","name":"ITCS: Innovations in Theoretical Computer Science","end_date":"2024-02-02","location":"Berkeley, CA, United States"},"oa":1,"has_accepted_license":"1","title":"Electrical flows for polylogarithmic competitive oblivious routing","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","acknowledgement":"Monika Henzinger and A. R. Sricharan: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation\r\nprogramme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) project Z\r\n422-N, project I 5982-N, and project P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nHarald Räcke: Research supported by German Research Foundation (DFG), grant 470029389\r\n(FlexNets), 2021-2024.\r\nSushant Sachdeva: SS’s work is supported by an Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant RGPIN-2018-06398 and a Sloan Research Fellowship.","scopus_import":"1","status":"public","file":[{"creator":"dernst","file_size":1054754,"date_updated":"2024-02-26T10:10:48Z","file_name":"2024_LIPICs_Goranci.pdf","file_id":"15030","date_created":"2024-02-26T10:10:48Z","checksum":"b89716aae6a5599f187897e39de1e53a","relation":"main_file","content_type":"application/pdf","access_level":"open_access","success":1}],"citation":{"ieee":"G. Goranci, M. Henzinger, H. Räcke, S. Sachdeva, and A. R. Sricharan, “Electrical flows for polylogarithmic competitive oblivious routing,” in <i>15th Innovations in Theoretical Computer Science Conference</i>, Berkeley, CA, United States, 2024, vol. 287.","ama":"Goranci G, Henzinger M, Räcke H, Sachdeva S, Sricharan AR. Electrical flows for polylogarithmic competitive oblivious routing. In: <i>15th Innovations in Theoretical Computer Science Conference</i>. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.55\">10.4230/LIPIcs.ITCS.2024.55</a>","apa":"Goranci, G., Henzinger, M., Räcke, H., Sachdeva, S., &#38; Sricharan, A. R. (2024). Electrical flows for polylogarithmic competitive oblivious routing. In <i>15th Innovations in Theoretical Computer Science Conference</i> (Vol. 287). Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.55\">https://doi.org/10.4230/LIPIcs.ITCS.2024.55</a>","chicago":"Goranci, Gramoz, Monika Henzinger, Harald Räcke, Sushant Sachdeva, and A. R. Sricharan. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.” In <i>15th Innovations in Theoretical Computer Science Conference</i>, Vol. 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.55\">https://doi.org/10.4230/LIPIcs.ITCS.2024.55</a>.","short":"G. Goranci, M. Henzinger, H. Räcke, S. Sachdeva, A.R. Sricharan, in:, 15th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","mla":"Goranci, Gramoz, et al. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.” <i>15th Innovations in Theoretical Computer Science Conference</i>, vol. 287, 55, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.55\">10.4230/LIPIcs.ITCS.2024.55</a>.","ista":"Goranci G, Henzinger M, Räcke H, Sachdeva S, Sricharan AR. 2024. Electrical flows for polylogarithmic competitive oblivious routing. 15th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 287, 55."},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"arxiv":1,"quality_controlled":"1","oa_version":"Published Version","language":[{"iso":"eng"}],"corr_author":"1","month":"01","doi":"10.4230/LIPIcs.ITCS.2024.55","ec_funded":1,"day":"24","publication_status":"published","department":[{"_id":"MoHe"}],"volume":287,"intvolume":"       287","author":[{"first_name":"Gramoz","last_name":"Goranci","full_name":"Goranci, Gramoz"},{"orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"last_name":"Räcke","full_name":"Räcke, Harald","first_name":"Harald"},{"full_name":"Sachdeva, Sushant","last_name":"Sachdeva","first_name":"Sushant"},{"first_name":"A. R.","last_name":"Sricharan","full_name":"Sricharan, A. R."}],"isi":1,"_id":"15008","external_id":{"arxiv":["2303.02491"],"isi":["001300389400055"]},"alternative_title":["LIPIcs"],"article_number":"55","year":"2024","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"grant_number":"Z00422","name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"ddc":["000"],"article_processing_charge":"No","date_published":"2024-01-24T00:00:00Z"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Dynamically maintaining the persistent homology of time series","oa":1,"conference":{"start_date":"2024-01-07","name":"SODA: Symposium on Discrete Algorithms","end_date":"2024-01-10","location":"Alexandria, VA, USA"},"publication":"Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","date_created":"2024-03-08T10:27:39Z","publication_identifier":{"eisbn":["9781611977912"]},"abstract":[{"text":"We present a dynamic data structure for maintaining the persistent homology of a time series of real numbers. The data structure supports local operations, including the insertion and deletion of an item and the cutting and concatenating of lists, each in time O(log n + k), in which n counts the critical items and k the changes in the augmented persistence diagram. To achieve this, we design a tailor-made tree structure with an unconventional representation, referred to as banana tree, which may be useful in its own right.","lang":"eng"}],"type":"conference","date_updated":"2026-04-07T12:58:47Z","department":[{"_id":"HeEd"},{"_id":"MoHe"}],"publication_status":"published","doi":"10.1137/1.9781611977912.11","day":"04","ec_funded":1,"related_material":{"record":[{"relation":"dissertation_contains","id":"15094","status":"public"}]},"corr_author":"1","month":"01","quality_controlled":"1","oa_version":"Preprint","language":[{"iso":"eng"}],"arxiv":1,"citation":{"ista":"Cultrera di Montesano S, Edelsbrunner H, Henzinger M, Ost L. 2024. Dynamically maintaining the persistent homology of time series. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SODA: Symposium on Discrete Algorithms, 243–295.","mla":"Cultrera di Montesano, Sebastiano, et al. “Dynamically Maintaining the Persistent Homology of Time Series.” <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)</i>, edited by David P. Woodruff, Society for Industrial and Applied Mathematics, 2024, pp. 243–95, doi:<a href=\"https://doi.org/10.1137/1.9781611977912.11\">10.1137/1.9781611977912.11</a>.","chicago":"Cultrera di Montesano, Sebastiano, Herbert Edelsbrunner, Monika Henzinger, and Lara Ost. “Dynamically Maintaining the Persistent Homology of Time Series.” In <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)</i>, edited by David P. Woodruff, 243–95. Society for Industrial and Applied Mathematics, 2024. <a href=\"https://doi.org/10.1137/1.9781611977912.11\">https://doi.org/10.1137/1.9781611977912.11</a>.","short":"S. Cultrera di Montesano, H. Edelsbrunner, M. Henzinger, L. Ost, in:, D.P. Woodruff (Ed.), Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, 2024, pp. 243–295.","apa":"Cultrera di Montesano, S., Edelsbrunner, H., Henzinger, M., &#38; Ost, L. (2024). Dynamically maintaining the persistent homology of time series. In D. P. Woodruff (Ed.), <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)</i> (pp. 243–295). Alexandria, VA, USA: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977912.11\">https://doi.org/10.1137/1.9781611977912.11</a>","ama":"Cultrera di Montesano S, Edelsbrunner H, Henzinger M, Ost L. Dynamically maintaining the persistent homology of time series. In: Woodruff DP, ed. <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)</i>. Society for Industrial and Applied Mathematics; 2024:243-295. doi:<a href=\"https://doi.org/10.1137/1.9781611977912.11\">10.1137/1.9781611977912.11</a>","ieee":"S. Cultrera di Montesano, H. Edelsbrunner, M. Henzinger, and L. Ost, “Dynamically maintaining the persistent homology of time series,” in <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)</i>, Alexandria, VA, USA, 2024, pp. 243–295."},"main_file_link":[{"url":"https://arxiv.org/abs/2311.01115","open_access":"1"}],"status":"public","scopus_import":"1","acknowledgement":"The  first  and  second  authors  are  funded  by  the  European  Research  Council  under  the European Union’s Horizon 2020 research and innovation programme, ERC grant no. 788183,“Alpha Shape Theory Extended (Alpha)”, by the Wittgenstein Prize, FWF grant no. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, FWF grant no. I 02979-N35.The third author received funding by the European Research Council under the European Union’s Horizon 2020research  and  innovation  programme,  ERC  grant  no.  101019564,  “The  Design  of  Modern  Fully  Dynamic  DataStructures (MoDynStruct)”, and by the Austrian Science Fund through the Wittgenstein Prize with FWF grant no. Z 422-N, and also by FWF grant no. I 5982-N, and by FWF grant no. P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.  The fourth author is funded by the Vienna Graduate School on Computational Optimization, FWF project no. W1260-N35.","external_id":{"arxiv":["2311.01115"]},"_id":"15093","author":[{"orcid":"0000-0001-6249-0832","first_name":"Sebastiano","last_name":"Cultrera di Montesano","full_name":"Cultrera di Montesano, Sebastiano","id":"34D2A09C-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert"},{"orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"first_name":"Lara","last_name":"Ost","full_name":"Ost, Lara"}],"editor":[{"first_name":"David P.","last_name":"Woodruff","full_name":"Woodruff, David P."}],"date_published":"2024-01-04T00:00:00Z","page":"243 - 295","article_processing_charge":"No","project":[{"name":"Alpha Shape Theory Extended","call_identifier":"H2020","grant_number":"788183","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Mathematics, Computer Science","grant_number":"Z00342"},{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"name":"Efficient algorithms","grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"publisher":"Society for Industrial and Applied Mathematics","year":"2024"}]