[{"month":"05","date_updated":"2026-06-22T08:37:44Z","fulldoi":"https://doi.org/10.4230/LIPIcs.SoCG.2026.29","file_date_updated":"2026-06-22T08:34:11Z","publication":"42nd International Symposium on Computational Geometry","date_created":"2026-06-14T22:01:44Z","OA_place":"publisher","has_accepted_license":"1","title":"Charting the diameter computation landscape of intersection graphs in 3D and above","keyword":["Graph Diameter","Geometric Intersection Graphs","Unit Ball Graphs"],"file":[{"date_created":"2026-06-22T08:34:11Z","content_type":"application/pdf","checksum":"ffff03934cc182757d6db82d88f896e6","file_id":"22114","success":1,"creator":"dernst","relation":"main_file","access_level":"open_access","file_name":"2026_LIPIcSSoCG_Chan.pdf","file_size":918197,"date_updated":"2026-06-22T08:34:11Z"}],"external_id":{"arxiv":["2603.21790"]},"das_tickbox":"0","OA_type":"gold","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"27","author":[{"full_name":"Chan, Timothy M.","first_name":"Timothy M.","last_name":"Chan"},{"first_name":"Hsien Chih","last_name":"Chang","full_name":"Chang, Hsien Chih"},{"last_name":"Gao","first_name":"Jie","full_name":"Gao, Jie"},{"last_name":"Kisfaludi-Bak","first_name":"Sándor","full_name":"Kisfaludi-Bak, Sándor"},{"first_name":"Hung","last_name":"Le","full_name":"Le, Hung"},{"first_name":"Da Wei","last_name":"Zheng","id":"af77956b-e859-11ef-8dc9-d301b898e32f","full_name":"Zheng, Da Wei"}],"arxiv":1,"volume":367,"quality_controlled":"1","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.","doi":"10.4230/LIPIcs.SoCG.2026.29","date_published":"2026-05-27T00:00:00Z","alternative_title":["LIPIcs"],"_id":"22004","year":"2026","status":"public","publication_identifier":{"isbn":["9783959774185"],"eissn":["1868-8969"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","intvolume":" 367","conference":{"start_date":"2026-06-02","name":"SoCG: Symposium on Computational Geometry","location":"New Brunswick, NJ, United States","end_date":"2026-06-05"},"citation":{"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.","chicago":"Chan, Timothy M., Hsien Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng. “Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above.” In 42nd International Symposium on Computational Geometry, Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.SoCG.2026.29.","ieee":"T. M. Chan, H. C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, and D. W. Zheng, “Charting the diameter computation landscape of intersection graphs in 3D and above,” in 42nd International Symposium on Computational Geometry, New Brunswick, NJ, United States, 2026, vol. 367.","mla":"Chan, Timothy M., et al. “Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above.” 42nd International Symposium on Computational Geometry, vol. 367, 29:1-29:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.SoCG.2026.29.","ama":"Chan TM, Chang HC, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. Charting the diameter computation landscape of intersection graphs in 3D and above. In: 42nd International Symposium on Computational Geometry. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.SoCG.2026.29","apa":"Chan, T. M., Chang, H. C., Gao, J., Kisfaludi-Bak, S., Le, H., & Zheng, D. W. (2026). Charting the diameter computation landscape of intersection graphs in 3D and above. In 42nd International Symposium on Computational Geometry (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2026.29"},"oa_version":"Published Version","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"corr_author":"1","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"}],"language":[{"iso":"eng"}],"article_processing_charge":"Yes","project":[{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"department":[{"_id":"MoHe"}],"scopus_import":"1","oa":1,"article_number":"29:1-29:15","ddc":["000"]},{"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa_version":"Published Version","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"}],"corr_author":"1","publication_status":"published","publisher":"Springer Nature","publication_identifier":{"issn":["0209-9683"],"eissn":["1439-6912"]},"citation":{"apa":"Kwan, M. A., Safavi Hemami, R., & Wang, Y. (2026). Counting perfect matchings in Dirac hypergraphs. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-025-00194-8","ama":"Kwan MA, Safavi Hemami R, Wang Y. Counting perfect matchings in Dirac hypergraphs. Combinatorica. 2026;46. doi:10.1007/s00493-025-00194-8","ieee":"M. A. Kwan, R. Safavi Hemami, and Y. Wang, “Counting perfect matchings in Dirac hypergraphs,” Combinatorica, vol. 46. Springer Nature, 2026.","chicago":"Kwan, Matthew Alan, Roodabeh Safavi Hemami, and Yiting Wang. “Counting Perfect Matchings in Dirac Hypergraphs.” Combinatorica. Springer Nature, 2026. https://doi.org/10.1007/s00493-025-00194-8.","mla":"Kwan, Matthew Alan, et al. “Counting Perfect Matchings in Dirac Hypergraphs.” Combinatorica, vol. 46, 5, Springer Nature, 2026, doi:10.1007/s00493-025-00194-8.","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)."},"intvolume":" 46","_id":"21159","PlanS_conform":"1","date_published":"2026-02-01T00:00:00Z","status":"public","year":"2026","volume":46,"quality_controlled":"1","doi":"10.1007/s00493-025-00194-8","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).","ddc":["510"],"article_processing_charge":"Yes (via OA deal)","oa":1,"article_number":"5","scopus_import":"1","department":[{"_id":"MaKw"},{"_id":"MoHe"}],"language":[{"iso":"eng"}],"title":"Counting perfect matchings in Dirac hypergraphs","has_accepted_license":"1","date_created":"2026-02-08T23:02:49Z","publication":"Combinatorica","OA_place":"publisher","date_updated":"2026-02-16T09:55:17Z","fulldoi":"https://doi.org/10.1007/s00493-025-00194-8","file_date_updated":"2026-02-16T09:52:38Z","month":"02","author":[{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","full_name":"Kwan, Matthew Alan","orcid":"0000-0002-4003-7567","first_name":"Matthew Alan","last_name":"Kwan"},{"id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","full_name":"Safavi Hemami, Roodabeh","first_name":"Roodabeh","last_name":"Safavi Hemami"},{"last_name":"Wang","first_name":"Yiting","id":"1917d194-076e-11ed-97cd-837255f88785","orcid":"0000-0002-2856-767X","full_name":"Wang, Yiting"}],"day":"01","arxiv":1,"type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["2408.09589"]},"OA_type":"hybrid","article_type":"original","file":[{"file_id":"21228","content_type":"application/pdf","checksum":"47b0031d90b0e6b9a843f422a1486089","date_created":"2026-02-16T09:52:38Z","file_size":539646,"date_updated":"2026-02-16T09:52:38Z","file_name":"2026_Combinatorica_Kwan.pdf","access_level":"open_access","relation":"main_file","success":1,"creator":"dernst"}]},{"language":[{"iso":"eng"}],"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","grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions"}],"article_processing_charge":"No","oa":1,"scopus_import":"1","department":[{"_id":"MoHe"}],"volume":"2026-January","quality_controlled":"1","doi":"10.1137/1.9781611978971.45","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.","_id":"21719","date_published":"2026-01-07T00:00:00Z","status":"public","year":"2026","publisher":"Society for Industrial and Applied Mathematics","ec_funded":1,"publication_status":"published","publication_identifier":{"issn":["10719040"],"isbn":["9781611978971"],"eissn":["15579468"]},"conference":{"name":"SODA: Symposium on Discrete Algorithms"},"citation":{"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.","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.","ieee":"G. Goranci, M. Henzinger, P. Kiss, A. Momeni, and G. Zöcklein, “Dynamic hierarchical j-tree decomposition and its applications,” in Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms, 2026, vol. 2026–January, pp. 1128–1180.","chicago":"Goranci, Gramoz, Monika Henzinger, Peter Kiss, Ali Momeni, and Gernot Zöcklein. “Dynamic Hierarchical J-Tree Decomposition and Its Applications.” In Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms, 2026–January:1128–80. Society for Industrial and Applied Mathematics, 2026. https://doi.org/10.1137/1.9781611978971.45.","mla":"Goranci, Gramoz, et al. “Dynamic Hierarchical J-Tree Decomposition and Its Applications.” Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms, vol. 2026–January, Society for Industrial and Applied Mathematics, 2026, pp. 1128–80, doi:10.1137/1.9781611978971.45.","ama":"Goranci G, Henzinger M, Kiss P, Momeni A, Zöcklein G. Dynamic hierarchical j-tree decomposition and its applications. In: Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms. Vol 2026-January. Society for Industrial and Applied Mathematics; 2026:1128-1180. doi:10.1137/1.9781611978971.45","apa":"Goranci, G., Henzinger, M., Kiss, P., Momeni, A., & Zöcklein, G. (2026). Dynamic hierarchical j-tree decomposition and its applications. In Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms (Vol. 2026–January, pp. 1128–1180). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611978971.45"},"oa_version":"Preprint","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"}],"external_id":{"arxiv":["2601.09139"]},"OA_type":"green","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"1128-1180","author":[{"first_name":"Gramoz","last_name":"Goranci","full_name":"Goranci, Gramoz"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H"},{"first_name":"Peter","last_name":"Kiss","full_name":"Kiss, Peter"},{"last_name":"Momeni","first_name":"Ali","full_name":"Momeni, Ali"},{"id":"45d5e826-47af-11f1-84e5-ba87c23fe681","full_name":"Zöcklein, Gernot","last_name":"Zöcklein","first_name":"Gernot"}],"day":"07","arxiv":1,"month":"01","fulldoi":"https://doi.org/10.1137/1.9781611978971.45","date_updated":"2026-05-04T11:54:09Z","publication":"Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms","date_created":"2026-04-12T22:01:51Z","OA_place":"repository","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2601.09139","open_access":"1"}],"title":"Dynamic hierarchical j-tree decomposition and its applications"},{"language":[{"iso":"eng"}],"article_processing_charge":"No","oa":1,"department":[{"_id":"MoHe"}],"scopus_import":"1","ddc":["500","000"],"quality_controlled":"1","doi":"10.1145/3798129.3800917","acknowledgement":"Hsien-Chih Chang and Jonathan Conroy are supported by the U.S.\r\nNational Science Foundation CAREER Award under the Grant No.\r\nCCF-2443017.","_id":"22246","date_published":"2026-06-09T00:00:00Z","status":"public","year":"2026","publication_status":"published","publisher":"Association for Computing Machinery","publication_identifier":{"issn":["0737-8017"],"isbn":["9798400725364"]},"conference":{"name":"STOC: Symposium on the Theory of Computing","start_date":"2026-06-22","end_date":"2026-06-26","location":"Salt Lake City, UT, United States"},"citation":{"ista":"Chang HC, Conroy J, Tan Z, Zheng DW. 2026. Cutting planarians: Planar emulators for string graphs. 58th Annual ACM Symposium on Theory of Computing. STOC: Symposium on the Theory of Computing, 2140–2151.","short":"H.C. Chang, J. Conroy, Z. Tan, D.W. Zheng, in:, 58th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2026, pp. 2140–2151.","chicago":"Chang, Hsien Chih, Jonathan Conroy, Zihan Tan, and Da Wei Zheng. “Cutting Planarians: Planar Emulators for String Graphs.” In 58th Annual ACM Symposium on Theory of Computing, 2140–51. Association for Computing Machinery, 2026. https://doi.org/10.1145/3798129.3800917.","mla":"Chang, Hsien Chih, et al. “Cutting Planarians: Planar Emulators for String Graphs.” 58th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2026, pp. 2140–51, doi:10.1145/3798129.3800917.","ieee":"H. C. Chang, J. Conroy, Z. Tan, and D. W. Zheng, “Cutting planarians: Planar emulators for string graphs,” in 58th Annual ACM Symposium on Theory of Computing, Salt Lake City, UT, United States, 2026, pp. 2140–2151.","ama":"Chang HC, Conroy J, Tan Z, Zheng DW. Cutting planarians: Planar emulators for string graphs. In: 58th Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 2026:2140-2151. doi:10.1145/3798129.3800917","apa":"Chang, H. C., Conroy, J., Tan, Z., & Zheng, D. W. (2026). Cutting planarians: Planar emulators for string graphs. In 58th Annual ACM Symposium on Theory of Computing (pp. 2140–2151). Salt Lake City, UT, United States: Association for Computing Machinery. https://doi.org/10.1145/3798129.3800917"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa_version":"Published Version","corr_author":"1","abstract":[{"text":"In this paper we construct distance sketches for intersection graphs of arbitrary path-connected regions in the plane (known as the string graphs) in the constant and 1+ε distortion regimes. Furthermore, the distance sketches themselves are planar graphs. First, we show that every unweighted string graph G has an O(1)-distortion planar emulator: that is, there exists an edge-weighted planar graph H containing every vertex in G, such that every pair of vertices (u,v) satisfies δG(u,v) ≤ δH(u,v) ≤ O(1) · δG(u,v). Furthermore, we show that for any constant ε > 0, there is an edge-weighted planar graph H′ such that every pair of vertices (u,v) satisfies δG(u,v) ≤ δH′(u,v) ≤ (1+ε) · δG(u,v) + O(ε−4polylogn). No previous constructions of sparse distance sketches were known even for intersection graphs of simple shapes like axis-parallel rectangles or fat convex polygons.\r\nAs applications, we construct the first (1+ε, +O(1)) mixed-distortion tree cover and distance oracle for arbitrary string graphs, as well as the first additive +(εΔ+O(1))-distortion embedding of string graphs G with diameter Δ into graphs of constant treewidth O(ε−4).","lang":"eng"}],"file":[{"date_created":"2026-07-06T10:23:09Z","file_id":"22253","content_type":"application/pdf","checksum":"c184596a3e18fee912caef4c7751a96d","access_level":"open_access","relation":"main_file","creator":"dernst","success":1,"file_size":2015699,"file_name":"2026_STOC_Chang.pdf","date_updated":"2026-07-06T10:23:09Z"}],"external_id":{"arxiv":["2510.21700"]},"OA_type":"gold","das_tickbox":"0","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"2140-2151","day":"09","author":[{"full_name":"Chang, Hsien Chih","last_name":"Chang","first_name":"Hsien Chih"},{"last_name":"Conroy","first_name":"Jonathan","full_name":"Conroy, Jonathan"},{"last_name":"Tan","first_name":"Zihan","full_name":"Tan, Zihan"},{"id":"af77956b-e859-11ef-8dc9-d301b898e32f","full_name":"Zheng, Da Wei","last_name":"Zheng","first_name":"Da Wei"}],"arxiv":1,"month":"06","fulldoi":"https://doi.org/10.1145/3798129.3800917","date_updated":"2026-07-06T10:25:23Z","supplementarymaterial":"no","researchdata_availability":"no","file_date_updated":"2026-07-06T10:23:09Z","date_created":"2026-07-05T22:01:37Z","publication":"58th Annual ACM Symposium on Theory of Computing","OA_place":"publisher","title":"Cutting planarians: Planar emulators for string graphs","has_accepted_license":"1"},{"scopus_import":"1","department":[{"_id":"MoHe"}],"oa":1,"article_processing_charge":"Yes","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"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422","name":"Efficient algorithms"}],"language":[{"iso":"eng"}],"ddc":["000"],"year":"2026","status":"public","date_published":"2026-06-01T00:00:00Z","_id":"22318","PlanS_conform":"1","acknowledgement":"1Salil Vadhan was supported by NSF grant BCS-2218803, a grant from the Sloan Foundation, and\r\na Simons Investigator Award. Work began while a Visiting Researcher at the Bocconi University\r\nDepartment of Computing Sciences, supported by Luca Trevisan’s ERC Project GA-834861.\r\n2Monika Henzinger and Roodabeh Safavi were supported by the European Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation programme (Grant agreement\r\nNo. 101019564), and the Austrian Science Fund (FWF) under grants DOI 10.55776/Z422, DOI\r\n10.55776/I5982, and DOI 10.55776/P33775. For open access purposes, the author has applied a CC BY\r\npublic copyright license to any author-accepted manuscript version arising from this submission.\r\nViews and opinions expressed are however those of the author(s)\r\nonly and do not necessarily reflect those of the European Union\r\nor the European Research Council Executive Agency. Neither the\r\nEuropean Union nor the granting authority can be held responsible for them.","doi":"10.1145/3801895","quality_controlled":"1","volume":4,"corr_author":"1","abstract":[{"lang":"eng","text":"Many intended uses of differential privacy involve a continual mechanism that is set up to run continuously\r\nover a long period of time, making more statistical releases as either queries come in or the dataset is updated.\r\nIn this paper, we give the first general treatment of privacy against adaptive adversaries for mechanisms that\r\nsupport dataset updates and a variety of queries, all arbitrarily interleaved. It also models a very general notion\r\nof neighboring, that includes both event-level and user-level privacy. We prove several concurrent composition\r\ntheorems for continual mechanisms, which ensure privacy even when an adversary can interleave its queries\r\nand dataset updates to the different composed mechanisms. Previous concurrent composition theorems for\r\ndifferential privacy were only for the case when the dataset is static, with no adaptive updates. We also give\r\nthe first interactive and continual generalizations of the “parallel composition theorem” for noninteractive\r\ndifferential privacy. Specifically, we show that the analogue of the noninteractive parallel composition theorem\r\nholds if either there are no adaptive dataset updates or each of the composed mechanisms satisfies pure\r\ndifferential privacy, but it fails to hold for composing approximately differentially private mechanisms with\r\ndataset updates. Thus, we prove a tight new composition theorem for this case. In addition, we prove concurrent\r\nfilter compositions theorems for the scenarios in which the privacy parameters are adaptively chosen. We\r\nextend these results to other measures of differential privacy, including Rényi DP and 𝑓 -DP.\r\nWe then formalize a set of general conditions on a continual mechanism M that runs multiple continual submechanisms such that the privacy guarantees of M follow directly using the above concurrent composition\r\ntheorems on the sub-mechanisms, without further privacy loss. This enables us to give a simpler and modular\r\nprivacy analysis of a recent continual histogram mechanism of Henzinger, Sricharan, and Steiner. In the\r\ncase of approximate DP, ours is the first proof that shows that its privacy holds against adaptive adversaries.\r\nWe also provide a framework that simplifies the analysis of local differential privacy when the protocol\r\nincludes multi-round server-user interactions. Using this result, we simplify the privacy analysis of the core\r\ndecomposition protocol of Dhulipala, Henzinger, Li, Liu, Sricharan, and Zhu [5]."}],"oa_version":"Published Version","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"intvolume":" 4","citation":{"ama":"Henzinger M, Safavi Hemami R, Vadhan S. Concurrent composition for differentially private continual mechanisms. Proceedings of the ACM on Management of Data. 2026;4(2):1-26. doi:10.1145/3801895","apa":"Henzinger, M., Safavi Hemami, R., & Vadhan, S. (2026). Concurrent composition for differentially private continual mechanisms. Proceedings of the ACM on Management of Data. Association for Computing Machinery. https://doi.org/10.1145/3801895","mla":"Henzinger, Monika, et al. “Concurrent Composition for Differentially Private Continual Mechanisms.” Proceedings of the ACM on Management of Data, vol. 4, no. 2, Association for Computing Machinery, 2026, pp. 1–26, doi:10.1145/3801895.","ieee":"M. Henzinger, R. Safavi Hemami, and S. Vadhan, “Concurrent composition for differentially private continual mechanisms,” Proceedings of the ACM on Management of Data, vol. 4, no. 2. Association for Computing Machinery, pp. 1–26, 2026.","chicago":"Henzinger, Monika, Roodabeh Safavi Hemami, and Salil Vadhan. “Concurrent Composition for Differentially Private Continual Mechanisms.” Proceedings of the ACM on Management of Data. Association for Computing Machinery, 2026. https://doi.org/10.1145/3801895.","short":"M. Henzinger, R. Safavi Hemami, S. Vadhan, Proceedings of the ACM on Management of Data 4 (2026) 1–26.","ista":"Henzinger M, Safavi Hemami R, Vadhan S. 2026. Concurrent composition for differentially private continual mechanisms. Proceedings of the ACM on Management of Data. 4(2), 1–26."},"publication_identifier":{"issn":["2836-6573"]},"ec_funded":1,"publisher":"Association for Computing Machinery","publication_status":"published","OA_type":"gold","das_tickbox":"0","external_id":{"arxiv":["2411.03299"]},"keyword":["differential privacy","concurrent composition","continual release","continual observation","data streaming","continual mechanisms","concurrent parallel composition","concurrent filter composition"],"article_type":"original","file":[{"date_updated":"2026-07-16T09:09:53Z","file_size":655405,"file_name":"2026_ACMMgmtData_Henzinger.pdf","creator":"dernst","success":1,"access_level":"open_access","relation":"main_file","checksum":"c6c5e256d02b90682c0690c3bee94040","content_type":"application/pdf","file_id":"22345","date_created":"2026-07-16T09:09:53Z"}],"arxiv":1,"day":"01","author":[{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger"},{"id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","full_name":"Safavi Hemami, Roodabeh","last_name":"Safavi Hemami","first_name":"Roodabeh"},{"last_name":"Vadhan","first_name":"Salil","full_name":"Vadhan, Salil"}],"page":"1-26","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","file_date_updated":"2026-07-16T09:09:53Z","researchdata_availability":"no","date_updated":"2026-07-16T09:14:49Z","fulldoi":"https://doi.org/10.1145/3801895","supplementarymaterial":"no","issue":"2","month":"06","has_accepted_license":"1","title":"Concurrent composition for differentially private continual mechanisms","OA_place":"publisher","publication":"Proceedings of the ACM on Management of Data","date_created":"2026-07-13T14:59:14Z"},{"intvolume":" 4","citation":{"ista":"Aryanfard B, Henzinger M, Saulpic D, Sricharan AR. 2026. Improved lower bounds for privacy under continual release. Proceedings of the ACM on Management of Data. 4(2), 1–27.","short":"B. Aryanfard, M. Henzinger, D. Saulpic, A.R. Sricharan, Proceedings of the ACM on Management of Data 4 (2026) 1–27.","ama":"Aryanfard B, Henzinger M, Saulpic D, Sricharan AR. Improved lower bounds for privacy under continual release. Proceedings of the ACM on Management of Data. 2026;4(2):1-27. doi:10.1145/3801903","apa":"Aryanfard, B., Henzinger, M., Saulpic, D., & Sricharan, A. R. (2026). Improved lower bounds for privacy under continual release. Proceedings of the ACM on Management of Data. Association for Computing Machinery. https://doi.org/10.1145/3801903","chicago":"Aryanfard, Bardiya, Monika Henzinger, David Saulpic, and A. R. Sricharan. “Improved Lower Bounds for Privacy under Continual Release.” Proceedings of the ACM on Management of Data. Association for Computing Machinery, 2026. https://doi.org/10.1145/3801903.","mla":"Aryanfard, Bardiya, et al. “Improved Lower Bounds for Privacy under Continual Release.” Proceedings of the ACM on Management of Data, vol. 4, no. 2, Association for Computing Machinery, 2026, pp. 1–27, doi:10.1145/3801903.","ieee":"B. Aryanfard, M. Henzinger, D. Saulpic, and A. R. Sricharan, “Improved lower bounds for privacy under continual release,” Proceedings of the ACM on Management of Data, vol. 4, no. 2. Association for Computing Machinery, pp. 1–27, 2026."},"publication_identifier":{"issn":["2836-6573"]},"publisher":"Association for Computing Machinery","publication_status":"published","ec_funded":1,"corr_author":"1","abstract":[{"text":"We study the problem of continually releasing statistics of an evolving dataset under differential privacy. In the event-level setting, we show the first polynomial lower bounds on the additive error for insertions-only graph problems such as maximum matching, degree histogram and k-core number computation. These results represent an exponential improvement on the polylogarithmic lower bounds of Fichtenberger, Henzinger and Ost [ESA 2021] for the former two problems, and are the first lower bounds in the continual release setting for the latter problem. Our results run counter to the intuition that the difference between insertions-only vs fully dynamic updates causes the gap between polylogarithmic and polynomial additive error. Indeed, we show that for estimating the size of the maximum matching or k-core number of a vertex, allowing small multiplicative approximations is what brings the additive error down to polylogarithmic. We complement these results with improved upper bounds on the additive error when no multiplicative approximation is allowed.\r\nBeyond graphs, our techniques also show that polynomial additive error is unavoidable for the Simultaneous Norm Estimation problem in the insertions-only setting. When multiplicative approximations are allowed, we circumvent this lower bound by giving the first continual mechanism with polylogarithmic additive error under (1 + ζ) multiplicative approximations, for any ζ > 0, for estimating all monotone symmetric norms simultaneously.\r\nIn the item-level setting, we show polynomial lower bounds on the product of the multiplicative and the additive error of continual mechanisms for a large range of graph problems. To the best of our knowledge, these are the first lower bounds shown for any differentially private mechanism under continual release with multiplicative error. To obtain these results, we prove a new lower bound on the product of multiplicative and additive error for the 1-Way-Marginals problem, and give reductions from 1-Way-Marginals to our desired graph problems. This generalizes the prior results of Hardt and Talwar [STOC 2010] and Bun, Ullman and Vadhan [STOC 2014, SIAM J. Comput. 2018], who gave lower bounds on the additive error for the special case of mechanisms with no multiplicative error.","lang":"eng"}],"oa_version":"Published Version","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"acknowledgement":"Bardiya Aryanfard and Monika Henzinger were supported by the European Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation programme (Grant agreement\r\nNo. 101019564). For open access purposes, the author has applied a CC BY public copyright\r\nlicense to any author-accepted manuscript version arising from this submission. Funded by the\r\nEuropean union. Views and opinions expressed are however those of the author(s) only and do\r\nnot necessarily reflect those of the European Union or the European Research Council Executive\r\nAgency. Neither the European Union nor the granting authority can be held responsible for them","doi":"10.1145/3801903","quality_controlled":"1","volume":4,"year":"2026","status":"public","date_published":"2026-06-01T00:00:00Z","_id":"22322","PlanS_conform":"1","ddc":["000"],"language":[{"iso":"eng"}],"department":[{"_id":"MoHe"},{"_id":"GradSch"}],"scopus_import":"1","oa":1,"project":[{"grant_number":"101019564","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"}],"article_processing_charge":"Yes","OA_place":"publisher","publication":"Proceedings of the ACM on Management of Data","date_created":"2026-07-14T05:33:58Z","has_accepted_license":"1","title":"Improved lower bounds for privacy under continual release","issue":"2","month":"06","file_date_updated":"2026-07-16T09:29:08Z","researchdata_availability":"no","supplementarymaterial":"no","fulldoi":"https://doi.org/10.1145/3801903","date_updated":"2026-07-16T09:30:31Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","arxiv":1,"author":[{"full_name":"Aryanfard, Bardiya","id":"1e8f4084-31df-11ee-b195-f706b4b77091","first_name":"Bardiya","last_name":"Aryanfard"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger","first_name":"Monika H"},{"last_name":"Saulpic","first_name":"David","full_name":"Saulpic, David","id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964"},{"full_name":"Sricharan, A. R.","first_name":"A. R.","last_name":"Sricharan"}],"day":"01","page":"1-27","article_type":"original","file":[{"date_created":"2026-07-16T09:29:08Z","file_id":"22349","checksum":"21a48a620e415a31a3874077c55bc6c3","content_type":"application/pdf","creator":"dernst","success":1,"access_level":"open_access","relation":"main_file","date_updated":"2026-07-16T09:29:08Z","file_size":934963,"file_name":"2026_ACMMgmtData_Aryanfard.pdf"}],"OA_type":"gold","das_tickbox":"0","external_id":{"arxiv":["2512.15981"]}},{"OA_place":"publisher","publication":"Proceedings of the Annual ACM Symposium on Principles of Distributed Computing","date_created":"2026-07-19T22:01:47Z","title":"Order statistics in population protocols via simple dynamics","has_accepted_license":"1","month":"07","researchdata_availability":"no","file_date_updated":"2026-07-21T07:31:29Z","fulldoi":"https://doi.org/10.1145/3796701.3815922","supplementarymaterial":"no","date_updated":"2026-07-21T07:34:49Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","page":"425-436","day":"01","author":[{"full_name":"D'Archivio, Niccolò","last_name":"D'Archivio","first_name":"Niccolò"},{"full_name":"Almahmoud, Hind","first_name":"Hind","last_name":"Almahmoud"},{"first_name":"Emanuele","last_name":"Natale","full_name":"Natale, Emanuele"},{"full_name":"Mallmann-Trenn, Frederik","id":"68748c44-84d5-11f1-b4f6-ca083374e553","last_name":"Mallmann-Trenn","first_name":"Frederik"}],"file":[{"content_type":"application/pdf","checksum":"e8208393a016d8e71d7b26c402045488","file_id":"22379","date_created":"2026-07-21T07:31:29Z","file_name":"2026_ACMPODC_dArchivio.pdf","date_updated":"2026-07-21T07:31:29Z","file_size":824239,"success":1,"creator":"dernst","relation":"main_file","access_level":"open_access"}],"das_tickbox":"0","OA_type":"gold","citation":{"short":"N. D’Archivio, H. Almahmoud, E. Natale, F. Mallmann-Trenn, in:, Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2026, pp. 425–436.","ista":"D’Archivio N, Almahmoud H, Natale E, Mallmann-Trenn F. 2026. Order statistics in population protocols via simple dynamics. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 425–436.","apa":"D’Archivio, N., Almahmoud, H., Natale, E., & Mallmann-Trenn, F. (2026). Order statistics in population protocols via simple dynamics. In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing (pp. 425–436). Egham, United Kingdom: Association for Computing Machinery. https://doi.org/10.1145/3796701.3815922","ama":"D’Archivio N, Almahmoud H, Natale E, Mallmann-Trenn F. Order statistics in population protocols via simple dynamics. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery; 2026:425-436. doi:10.1145/3796701.3815922","ieee":"N. D’Archivio, H. Almahmoud, E. Natale, and F. Mallmann-Trenn, “Order statistics in population protocols via simple dynamics,” in Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Egham, United Kingdom, 2026, pp. 425–436.","mla":"D’Archivio, Niccolò, et al. “Order Statistics in Population Protocols via Simple Dynamics.” Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2026, pp. 425–36, doi:10.1145/3796701.3815922.","chicago":"D’Archivio, Niccolò, Hind Almahmoud, Emanuele Natale, and Frederik Mallmann-Trenn. “Order Statistics in Population Protocols via Simple Dynamics.” In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, 425–36. Association for Computing Machinery, 2026. https://doi.org/10.1145/3796701.3815922."},"conference":{"name":"PODC: Symposium on Principles of Distributed Computing","start_date":"2026-07-06","end_date":"2026-07-10","location":"Egham, United Kingdom"},"publication_status":"published","publisher":"Association for Computing Machinery","publication_identifier":{"isbn":["9798400725128"]},"abstract":[{"text":"We study simple dynamics in the population protocol model, in\r\nwhich 𝑛 agents start with totally ordered initial opinions 𝑥1, 𝑥2, . . . ,\r\n𝑥𝑛 and, in each round, a randomly chosen agent changes its opinion\r\nas a function of the opinion of other randomly chosen agents. Such\r\ndynamics often converge to consensus on a single fixation value 𝑋ˆ.\r\nThis paper asks how to control the distribution of 𝑋ˆ as a randomised\r\nchoice among the initial opinions by designing suitable simple\r\ndynamics. Writing the sorted initial values as 𝑥(1) ≤ · · · ≤ 𝑥(𝑛)\r\n,\r\nwe design two protocols that realise natural target laws over order\r\nstatistics.\r\nFirst, for a parameter 𝑝 ∈ (0, 1), our geometric protocol biases\r\ntoward larger opinions and satisfies P\r\n\r\n𝑋ˆ = 𝑥(𝑘)\r\n\r\n∝ 𝑝\r\n𝑛−𝑘\r\n, for\r\n𝑘 = 1, . . . , 𝑛. Equivalently, P\r\n\r\n𝑋ˆ = 𝑥(𝑘)\r\n\r\n= (1 − 𝑝)𝑝\r\n𝑛−𝑘\r\n/(1 − 𝑝\r\n𝑛\r\n).\r\nSecond, our binomial protocol assigns a shifted binomial law to the\r\nranks in ascending order: if 𝐾 −1 ∼ Bin(𝑛−1, 1−𝑝), then 𝑋ˆ = 𝑥(𝐾)\r\n,\r\ni.e., P\r\n\r\n𝑋ˆ = 𝑥(𝑘)\r\n\r\n=\r\n𝑛−1\r\n𝑘−1\r\n\u0001\r\n𝑝\r\n𝑛−𝑘\r\n(1 − 𝑝)\r\n𝑘−1\r\n, for 𝑘 = 1, . . . , 𝑛.\r\nApplications of this include computing the Top-𝑘 values for\r\nsmall 𝑘 on general interaction graphs. A central contribution of\r\nthis work is that, in contrast to most population protocols, we can\r\ncharacterise the fixation distribution in closed form. This is enabled\r\nby a novel analysis technique, which also yields applications: we\r\nderive new results for the Median protocol that extend the state of\r\nthe art.","lang":"eng"}],"corr_author":"1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa_version":"Published Version","doi":"10.1145/3796701.3815922","acknowledgement":"This work has been supported by the AID INRIA-DGA project\r\nn°2023000872 “BioSwarm”, the French government National Research Agency (ANR) through the UCA JEDI (ANR-15-IDEX-01),\r\nthe EUR DS4H (ANR-17-EURE-004) and the 3IA Cote d’Azur Investments ANR-23-IACL-0001, and EPSRC grant EP/W005573/1","quality_controlled":"1","status":"public","year":"2026","_id":"22368","date_published":"2026-07-01T00:00:00Z","ddc":["000"],"language":[{"iso":"eng"}],"oa":1,"scopus_import":"1","department":[{"_id":"MoHe"}],"article_processing_charge":"No"},{"abstract":[{"text":"We study the Undecided-State Dynamics (USD), a fundamental consensus process in which each vertex holds one of k decided opinions or the undecided state. We consider both the gossip model and the population protocol model. Prior work established tight bounds on the consensus time of this process only for the regime \r\nk\r\n=\r\nO\r\n(\r\nn\r\n/\r\n(\r\nlog\r\n\r\nn\r\n)\r\n2\r\n)\r\n (for the population protocol model) and k = O((n/log n)1/3) (for the gossip model), often under restrictive assumptions on the initial configuration.\r\nIn this paper, we obtain the first consensus-time guarantees for USD that hold for arbitrary 2 ≤ k ≤ n and for arbitrary initial configurations in both the gossip model and the population protocol model. In the gossip model, USD reaches consensus within \r\nO\r\n~\r\n(\r\nmin\r\n{\r\nk\r\n,\r\nn\r\n}\r\n)\r\n synchronous rounds with probability 1 - p⊥ - n-c, where p⊥ is the gossip-specific probability of collapsing to the all-undecided state in the first round. In the population protocol model, USD reaches consensus within \r\nO\r\n~\r\n(\r\nmin\r\n{\r\nk\r\nn\r\n,\r\nn\r\n3\r\n/\r\n2\r\n}\r\n)\r\n asynchronous interactions with high probability. We also present lower bounds that match the upper bounds up to polylogarithmic factors for a specific initial configuration and show that our upper bounds are essentially optimal.","lang":"eng"}],"corr_author":"1","oa_version":"Published Version","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"citation":{"short":"C. Cooper, F. Mallmann-Trenn, T. Radzik, N. Shimizu, T. Shiraga, in:, Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2026, pp. 77–87.","ista":"Cooper C, Mallmann-Trenn F, Radzik T, Shimizu N, Shiraga T. 2026. Undecided state dynamics with many opinions. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 77–87.","chicago":"Cooper, Colin, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, and Takeharu Shiraga. “Undecided State Dynamics with Many Opinions.” In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, 77–87. Association for Computing Machinery, 2026. https://doi.org/10.1145/3796701.3815920.","mla":"Cooper, Colin, et al. “Undecided State Dynamics with Many Opinions.” Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2026, pp. 77–87, doi:10.1145/3796701.3815920.","ieee":"C. Cooper, F. Mallmann-Trenn, T. Radzik, N. Shimizu, and T. Shiraga, “Undecided state dynamics with many opinions,” in Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Egham, United Kingdom, 2026, pp. 77–87.","ama":"Cooper C, Mallmann-Trenn F, Radzik T, Shimizu N, Shiraga T. Undecided state dynamics with many opinions. In: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery; 2026:77-87. doi:10.1145/3796701.3815920","apa":"Cooper, C., Mallmann-Trenn, F., Radzik, T., Shimizu, N., & Shiraga, T. (2026). Undecided state dynamics with many opinions. In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing (pp. 77–87). Egham, United Kingdom: Association for Computing Machinery. https://doi.org/10.1145/3796701.3815920"},"conference":{"start_date":"2026-07-06","name":"PODC: Symposium on Principles of Distributed Computing","location":"Egham, United Kingdom","end_date":"2026-07-10"},"publication_identifier":{"isbn":["9798400725128"]},"publisher":"Association for Computing Machinery","publication_status":"published","year":"2026","status":"public","date_published":"2026-07-01T00:00:00Z","_id":"22367","acknowledgement":"Nobutaka Shimizu is supported by JSPS KAKENHI Grant Number\r\n23K16837. Takeharu Shiraga is supported by JSPS KAKENHI Grant\r\nNumber 23K16840, and JST CRONOS Grant Number JPMJCS24K2.\r\nColin Cooper is supported by a Mercator Fellowship from DFG\r\nProject 491453517 at the University of Hamburg. We thank the\r\nanonymous reviewers for their helpful comments and suggestions.","doi":"10.1145/3796701.3815920","quality_controlled":"1","ddc":["000"],"scopus_import":"1","department":[{"_id":"MoHe"}],"oa":1,"article_processing_charge":"No","language":[{"iso":"eng"}],"has_accepted_license":"1","title":"Undecided state dynamics with many opinions","OA_place":"publisher","date_created":"2026-07-19T22:01:47Z","publication":"Proceedings of the Annual ACM Symposium on Principles of Distributed Computing","file_date_updated":"2026-07-21T07:51:58Z","researchdata_availability":"no","fulldoi":"https://doi.org/10.1145/3796701.3815920","date_updated":"2026-07-21T07:54:01Z","supplementarymaterial":"no","month":"07","arxiv":1,"author":[{"full_name":"Cooper, Colin","first_name":"Colin","last_name":"Cooper"},{"first_name":"Frederik","last_name":"Mallmann-Trenn","full_name":"Mallmann-Trenn, Frederik","id":"68748c44-84d5-11f1-b4f6-ca083374e553"},{"last_name":"Radzik","first_name":"Tomasz","full_name":"Radzik, Tomasz"},{"last_name":"Shimizu","first_name":"Nobutaka","full_name":"Shimizu, Nobutaka"},{"last_name":"Shiraga","first_name":"Takeharu","full_name":"Shiraga, Takeharu"}],"day":"01","page":"77-87","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","OA_type":"gold","das_tickbox":"1","external_id":{"arxiv":["2603.02636"]},"keyword":["consensus dynamics","undecided state dynamics","gossip model","population protocol model"],"file":[{"file_size":709077,"file_name":"2026_ACMPODC_Cooper.pdf","date_updated":"2026-07-21T07:51:58Z","creator":"dernst","success":1,"relation":"main_file","access_level":"open_access","content_type":"application/pdf","checksum":"9ada61feba1e93fd72867a5ba4ee8bb8","file_id":"22380","date_created":"2026-07-21T07:51:58Z"}]},{"month":"07","date_updated":"2026-07-22T07:49:22Z","fulldoi":"https://doi.org/10.1145/3796701.3815913","supplementarymaterial":"no","researchdata_availability":"no","file_date_updated":"2026-07-16T11:18:44Z","date_created":"2026-07-14T05:40:17Z","publication":"Proceedings of the ACM Symposium on Principles of Distributed Computing","OA_place":"publisher","title":"Ranking opinions with few states in population protocols","has_accepted_license":"1","file":[{"success":1,"creator":"dernst","relation":"main_file","access_level":"open_access","file_name":"2026_ACMPODC_Breitkopf.pdf","date_updated":"2026-07-16T11:18:44Z","file_size":702140,"date_created":"2026-07-16T11:18:44Z","checksum":"e56da70c1b2e7e663d2d8106cf07a30a","content_type":"application/pdf","file_id":"22353"}],"external_id":{"arxiv":["2605.18707"]},"das_tickbox":"0","OA_type":"gold","type":"conference","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","page":"414 - 424","day":"01","author":[{"full_name":"Breitkopf, Tom-Lukas","first_name":"Tom-Lukas","last_name":"Breitkopf"},{"last_name":"Dallot","first_name":"Julien","full_name":"Dallot, Julien"},{"id":"888a098e-fcac-11ee-aff7-d347be57b725","full_name":"El-Hayek, Antoine","orcid":"0000-0003-4268-7368","first_name":"Antoine","last_name":"El-Hayek"},{"full_name":"Schmid, Stefan","first_name":"Stefan","last_name":"Schmid"}],"arxiv":1,"quality_controlled":"1","doi":"10.1145/3796701.3815913","acknowledgement":"Funded by the European union. Views and opinions expressed are\r\nhowever those of the author(s) only and do not necessarily reflect\r\nthose of the European Union or the European Research Council\r\nExecutive Agency. Neither the European Union nor the granting authority can be held responsible for them. This project has received\r\nfunding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme\r\n(MoDynStruct, No. 101019564) and the Austrian Science\r\nFund (FWF) grant DOI 10.55776/I5982. For open access purposes,\r\nthe author has applied a CC BY public copyright license to any\r\nauthor-accepted manuscript version arising from this submission.","_id":"22327","date_published":"2026-07-01T00:00:00Z","status":"public","year":"2026","publisher":"Association for Computing Machinery","publication_status":"published","ec_funded":1,"publication_identifier":{"isbn":["9798400725128"]},"citation":{"ama":"Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. Ranking opinions with few states in population protocols. In: Proceedings of the ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery; 2026:414-424. doi:10.1145/3796701.3815913","apa":"Breitkopf, T.-L., Dallot, J., El-Hayek, A., & Schmid, S. (2026). Ranking opinions with few states in population protocols. In Proceedings of the ACM Symposium on Principles of Distributed Computing (pp. 414–424). Egham, United Kingdom: Association for Computing Machinery. https://doi.org/10.1145/3796701.3815913","ieee":"T.-L. Breitkopf, J. Dallot, A. El-Hayek, and S. Schmid, “Ranking opinions with few states in population protocols,” in Proceedings of the ACM Symposium on Principles of Distributed Computing, Egham, United Kingdom, 2026, pp. 414–424.","mla":"Breitkopf, Tom-Lukas, et al. “Ranking Opinions with Few States in Population Protocols.” Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2026, pp. 414–24, doi:10.1145/3796701.3815913.","chicago":"Breitkopf, Tom-Lukas, Julien Dallot, Antoine El-Hayek, and Stefan Schmid. “Ranking Opinions with Few States in Population Protocols.” In Proceedings of the ACM Symposium on Principles of Distributed Computing, 414–24. Association for Computing Machinery, 2026. https://doi.org/10.1145/3796701.3815913.","short":"T.-L. Breitkopf, J. Dallot, A. El-Hayek, S. Schmid, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2026, pp. 414–424.","ista":"Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. 2026. Ranking opinions with few states in population protocols. Proceedings of the ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 414–424."},"conference":{"name":"PODC: Symposium on Principles of Distributed Computing","start_date":"2026-07-06","end_date":"2026-07-10","location":"Egham, United Kingdom"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa_version":"Published Version","abstract":[{"lang":"eng","text":"Population protocols are a model of distributed computing where\r\n𝑛 agents, each a simple finite-state machine, interact in pairs to\r\nsolve a common task against a (adversarial) interaction scheduler.\r\nThis model was intensively studied in recent years; in particular,\r\nthe problem of relative majority received much attention: Each\r\nagent starts with an input opinion (or color) out of 𝑘 possibilities,\r\nand the goal is for each agent to eventually output the color with\r\nthe largest support in the population. Before our work, the state\r\ncomplexity (the minimum number of states required per agent) was\r\nonly known to be between Ω(𝑘\r\n2\r\n) and𝑂(𝑘\r\n7\r\n). Our main contribution\r\nis a population protocol that solves the relative majority problem\r\nwith 𝑘\r\n3\r\nstates. We achieve this result with a new protocol called\r\nCircles. While prior approaches in the literature relied on duels of\r\nagents to find the majority color — an approach that proved effective\r\nfor the case with two colors — Circles partitions the agents into\r\ncircular linked lists of decreasing sizes, with the property that no\r\ntwo agents with the same initial color lie in the same circle. We\r\nshow that Circles always correctly computes the desired structure\r\nagainst the most adversarial of schedulers (weakly fair). We then\r\nshow that a trivial extension of Circles solves the relative majority\r\nproblem. We extend our protocol to handle various tie-breaking\r\nmechanisms or to support the case where the agents do not share a\r\nprior ordering of the colors. Finally, we show that a modification of\r\nCircles solves the ranking problem with 2 · 𝑘^4\r\nstates, where each\r\nagent must output the rank of its initial color in the population."}],"corr_author":"1","language":[{"iso":"eng"}],"article_processing_charge":"Yes","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":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"oa":1,"scopus_import":"1","department":[{"_id":"MoHe"},{"_id":"GradSch"}],"ddc":["000"]},{"year":"2026","status":"public","date_published":"2026-07-13T00:00:00Z","alternative_title":["ISTA Thesis"],"_id":"22281","acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct, No. 101019564)\r\n\"The Design and Evaluation of Modern Fully Dynamic Data Structures\" , from the\r\nAustrian Science Fund (FWF) grant DOI 10.55776/I5982 \"Static and Dynamic Hierarchical\r\nGraph Decompositions\", and from the Austrian Science Fund (FWF) and netIDEE SCIENCE\r\nproject P 33775-N, \"Fast Algorithms for a Reactive Network Layer\".\r\n","doi":"10.15479/AT-ISTA-22281","doi_confirm":"1","abstract":[{"text":"In this thesis, we took a look at networks, and more specifically, at networks that change over time, whether those are networks in the distributed algorithms sense of the word, or the graph algorithm sense. \r\n\r\nIn distributed algorithms, we looked at two main problems. First, the broadcast problem: given n agents, each agent is tasked to forward a (unique) message to every other agent. Agents collaborate and can copy and forward all messages they have received up until that point. Broadcast is achieved when one agent has successfully broadcast its message to everyone else. We studied the case where the communication network is controlled by an adversary, under the condition that the graph is rooted in every round of communication. We show that the adversary can delay broadcast for at most l\r\n(1 + √\r\n2)n\r\nm\r\n rounds, improving on the $O(n\\log\\log n)$ previous upper bound~\\cite{fugger2020radius}, and asymptotically matching the $\\sim 1.5n$ lower bound~\\cite{schwarz2017linear}.\r\n\r\nWe then looked at the stochastic version of the problem: here, the adversary -- parametrized by $k$ where $k=0$ signifies that the adversary has no control, and $k=n$ that the adversary has full control -- can choose parts of the graph, and the graph is then completed stochastically. Here, we are able to look at a stronger version of broadcast: instead of having $n$ messages trying to be broadcast in parallel, we can assume that only one message needs to be broadcasted. We show the bound $\\Theta(k+\\log n)$.\r\n\r\nThen, we looked at undecided states dynamics in population protocols: given a population of $n$ agents, where each initially holds an opinion among $k$ different ones. In each round, two agents are chosen uniformly at random, and can interact. If they have different opinions, they forget their opinions and become undecided. If one of them is undecided while the other has an opinion, they undecided agent copies they opinion of the decided one. The question is then, how many interactions does it take for the whole population to share the same opinion? We show a $\\Omega(kn\\log \\frac {\\sqrt n} {k \\log n})$ lower bound for any $k = o\\left(\\frac {\\sqrt n}{\\log n}\\right)$.\r\nThis is tight for any $ k \\le n^{\\frac 1 2 - \\epsilon}$, where $\\epsilon >0$ can be any small constant, matching the known $O(kn\\log n)$ upper bound for $k = O\\left(\\frac {\\sqrt n} {\\log ^2 n}\\right)$~\\cite{DBLP:conf/podc/AmirABBHKL23}.\r\n\r\nFinally, in dynamic algorithms, we study the minimum cut problem: we are given a graph, whose vertex set we want to partition into two subsets such that the number of edges crossing from one subset to the other is minimized. Then, the graph can be updated via edge insertions or deletions, and we must update the solution without recomputing everything from scratch. We present an exact fully-dynamic minimum cut algorithm that runs in $n^{o(1)}$ deterministic update time when the minimum cut size is at most $2^{\\Theta(\\log^{3/4-c}n)}$ for any $c>0$, improving on the previous algorithm~\\cite{DBLP:conf/soda/JinST24} whose minimum cut size limit is $(\\log n)^{o(1)}$. Using sparsification and randomization techniques, we are able to extend this to all values of the minimum cut in weighted graphs, at the cost of a $(1+o(1))$-approximation ratio.","lang":"eng"}],"corr_author":"1","oa_version":"Published Version","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"citation":{"short":"A. El-Hayek, Handling Updates and Failures: Dynamic Graph Algorithms and Distributed Computing on Dynamic Networks, Institute of Science and Technology Austria, 2026.","ista":"El-Hayek A. 2026. Handling updates and failures: Dynamic graph algorithms and distributed computing on dynamic networks. Institute of Science and Technology Austria.","chicago":"El-Hayek, Antoine. “Handling Updates and Failures: Dynamic Graph Algorithms and Distributed Computing on Dynamic Networks.” Institute of Science and Technology Austria, 2026. https://doi.org/10.15479/AT-ISTA-22281.","mla":"El-Hayek, Antoine. Handling Updates and Failures: Dynamic Graph Algorithms and Distributed Computing on Dynamic Networks. Institute of Science and Technology Austria, 2026, doi:10.15479/AT-ISTA-22281.","ieee":"A. El-Hayek, “Handling updates and failures: Dynamic graph algorithms and distributed computing on dynamic networks,” Institute of Science and Technology Austria, 2026.","apa":"El-Hayek, A. (2026). Handling updates and failures: Dynamic graph algorithms and distributed computing on dynamic networks. Institute of Science and Technology Austria. https://doi.org/10.15479/AT-ISTA-22281","ama":"El-Hayek A. Handling updates and failures: Dynamic graph algorithms and distributed computing on dynamic networks. 2026. doi:10.15479/AT-ISTA-22281"},"publication_identifier":{"issn":["2663-337X"]},"publisher":"Institute of Science and Technology Austria","publication_status":"published","ec_funded":1,"department":[{"_id":"GradSch"},{"_id":"MoHe"}],"oa":1,"project":[{"name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775"}],"article_processing_charge":"No","language":[{"iso":"eng"}],"degree_awarded":"PhD","ddc":["000"],"file_date_updated":"2026-07-20T11:29:38Z","publisher_comment":"Sections 2.4 and 7.1 and chapter 6 are not CC-BY 4.0, they are All Rights Reserved.","date_updated":"2026-07-24T12:48:29Z","fulldoi":"https://doi.org/10.15479/AT-ISTA-22281","month":"07","has_accepted_license":"1","title":"Handling updates and failures: Dynamic graph algorithms and distributed computing on dynamic networks","OA_place":"publisher","date_created":"2026-07-13T09:39:59Z","supervisor":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger"}],"file":[{"date_created":"2026-07-17T11:39:47Z","file_id":"22356","content_type":"application/pdf","checksum":"923e4ca769c9ef2f6b0b005444faf462","creator":"aelhayek","success":1,"relation":"main_file","access_level":"open_access","date_updated":"2026-07-17T11:39:47Z","file_size":5465973,"file_name":"2026_El-Hayek_Antoine_Thesis.pdf"},{"relation":"source_file","access_level":"closed","creator":"aelhayek","date_updated":"2026-07-20T11:29:38Z","file_name":"2026_El-Hayek_Antoine_Thesis.zip","file_size":9116107,"date_created":"2026-07-17T11:40:34Z","content_type":"application/x-zip-compressed","checksum":"262689f9df27dd6c2c7c7861f1de7329","file_id":"22357"}],"author":[{"id":"888a098e-fcac-11ee-aff7-d347be57b725","full_name":"El-Hayek, Antoine","orcid":"0000-0003-4268-7368","first_name":"Antoine","last_name":"El-Hayek"}],"day":"13","page":"244","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","related_material":{"record":[{"status":"public","id":"20051","relation":"part_of_dissertation"},{"id":"18557","status":"public","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","id":"19982","status":"public"},{"status":"public","id":"21720","relation":"part_of_dissertation"},{"status":"public","id":"22374","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","id":"22373","status":"public"}]},"type":"dissertation"},{"OA_type":"green","external_id":{"arxiv":["2512.13105"]},"related_material":{"record":[{"status":"public","id":"22281","relation":"dissertation_contains"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","arxiv":1,"page":"613-663","author":[{"last_name":"El-Hayek","first_name":"Antoine","id":"888a098e-fcac-11ee-aff7-d347be57b725","orcid":"0000-0003-4268-7368","full_name":"El-Hayek, Antoine"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger"},{"full_name":"Li, Jason","first_name":"Jason","last_name":"Li"}],"day":"07","month":"01","fulldoi":"https://doi.org/10.1137/1.9781611978971.25","date_updated":"2026-07-24T12:48:29Z","OA_place":"repository","publication":"Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms","date_created":"2026-04-12T22:01:51Z","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2512.13105","open_access":"1"}],"title":"Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time","language":[{"iso":"eng"}],"oa":1,"scopus_import":"1","department":[{"_id":"MoHe"},{"_id":"GradSch"}],"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":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions"}],"article_processing_charge":"No","doi":"10.1137/1.9781611978971.25","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.","volume":2026,"quality_controlled":"1","status":"public","year":"2026","_id":"21720","date_published":"2026-01-07T00:00:00Z","citation":{"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.","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.","mla":"El-Hayek, Antoine, et al. “Deterministic and Exact Fully-Dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time.” Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, vol. 2026, Society for Industrial and Applied Mathematics, 2026, pp. 613–63, doi:10.1137/1.9781611978971.25.","ieee":"A. El-Hayek, M. Henzinger, and J. Li, “Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time,” in Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, Vancouver, Canada, 2026, vol. 2026, pp. 613–663.","chicago":"El-Hayek, Antoine, Monika Henzinger, and Jason Li. “Deterministic and Exact Fully-Dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time.” In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, 2026:613–63. Society for Industrial and Applied Mathematics, 2026. https://doi.org/10.1137/1.9781611978971.25.","ama":"El-Hayek A, Henzinger M, Li J. Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time. In: Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms. Vol 2026. Society for Industrial and Applied Mathematics; 2026:613-663. doi:10.1137/1.9781611978971.25","apa":"El-Hayek, A., Henzinger, M., & Li, J. (2026). Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time. In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms (Vol. 2026, pp. 613–663). Vancouver, Canada: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611978971.25"},"conference":{"start_date":"2026-01-11","name":"SODA: Symposium on Discrete Algorithms","location":"Vancouver, Canada","end_date":"2026-01-14"},"intvolume":" 2026","ec_funded":1,"publication_status":"published","publisher":"Society for Industrial and Applied Mathematics","publication_identifier":{"issn":["1071-9040"],"eisbn":["9781611978971"],"eissn":["1557-9468"]},"abstract":[{"lang":"eng","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)."}],"oa_version":"Preprint"},{"ddc":["000"],"oa":1,"article_number":"54:1-54:22","scopus_import":"1","department":[{"_id":"MoHe"}],"project":[{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"article_processing_charge":"No","language":[{"iso":"eng"}],"corr_author":"1","abstract":[{"text":"Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainly depends on the object types: for unit disks and squares in 2D, the problem is solvable in truly subquadratic time [Chan et al., 2025], while for other objects, including unit segments and equilateral triangles in 2D or unit balls and axis-parallel unit cubes in 3D, there is no truly subquadratic time algorithm under the Orthogonal Vector (OV) hypothesis [Bringmann et al., 2022]. \r\nWe undertake a comprehensive study of computing the diameter of geometric intersection graphs for various types of objects. We discover many new irregularities, showing that the landscape is extremely nuanced: the source of hardness is a combination of the object type, the true diameter value, and how the objects intersect with each other. Our highlighted results for the 2D case include: \r\n1) The diameter of non-degenerate, axis-aligned line segments can be computed in truly subquadratic time. Previous hardness result [Bringmann et al., 2022] for line segments applies only to degenerate instances. On the other hand, for the degenerate case, we show that a truly subquadratic time algorithm exists when the true diameter is constant. \r\n2) An almost-linear-time algorithm for unit-square graphs of constant diameter. Previous algorithms [Duraj et al., 2024; Chan et al., 2025] rely on succinct representation assuming bounded VC-dimension; for such a strategy Ω(n^{7/4}) time is an inherent barrier. \r\n3) An Õ(n^{4/3})-time algorithm to decide if the diameter of a unit-disk graph is at most 2. This improves upon the recent algorithm with running time Õ(n^{2-1/9}) [Chan et al., 2025]. \r\n4) Deciding if the diameter of intersection graphs of fat triangles or line segments is at most 2 is truly subquadratic-hard under fine-grained complexity assumptions. Previous lower bounds [Bringmann et al., 2022] only hold when deciding if diameter is at most 3. Our findings are presented in a pair of papers. This paper focuses solely on the 2D case, while the companion paper is devoted to higher-dimensional cases.","lang":"eng"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa_version":"Published Version","conference":{"name":"ICALP: Automata, Languages and Programming","start_date":"2026-07-07","end_date":"2026-07-10","location":"Egham, United Kingdom"},"citation":{"mla":"Chan, Timothy M., et al. “Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane.” 53rd International Colloquium on Automata, Languages, and Programming, vol. 374, 54:1-54:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPICS.ICALP.2026.54.","chicago":"Chan, Timothy M., Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng. “Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane.” In 53rd International Colloquium on Automata, Languages, and Programming, Vol. 374. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPICS.ICALP.2026.54.","ieee":"T. M. Chan, H.-C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, and D. W. Zheng, “Charting the landscape of diameter computation on geometric intersection graphs in the plane,” in 53rd International Colloquium on Automata, Languages, and Programming, Egham, United Kingdom, 2026, vol. 374.","apa":"Chan, T. M., Chang, H.-C., Gao, J., Kisfaludi-Bak, S., Le, H., & Zheng, D. W. (2026). Charting the landscape of diameter computation on geometric intersection graphs in the plane. In 53rd International Colloquium on Automata, Languages, and Programming (Vol. 374). Egham, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2026.54","ama":"Chan TM, Chang H-C, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. Charting the landscape of diameter computation on geometric intersection graphs in the plane. In: 53rd International Colloquium on Automata, Languages, and Programming. Vol 374. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPICS.ICALP.2026.54","ista":"Chan TM, Chang H-C, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. 2026. Charting the landscape of diameter computation on geometric intersection graphs in the plane. 53rd International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming vol. 374, 54:1-54:22.","short":"T.M. Chan, H.-C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D.W. Zheng, in:, 53rd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026."},"intvolume":" 374","publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_identifier":{"eissn":["1868-8969","9783959774284"]},"status":"public","year":"2026","_id":"22405","date_published":"2026-07-01T00:00:00Z","doi":"10.4230/LIPICS.ICALP.2026.54","acknowledgement":"Timothy M. Chan: Supported by NSF grant CCF-2224271.\r\nHsien-Chih Chang: Supported by NSF CAREER award CCF-2443017.\r\nJie Gao: Supported by NSF DMS-2220271, DMS-2311064, IIS-2229876, CCF-2118953, CNS-2515159.\r\nSándor Kisfaludi-Bak: Supported by the Research Council of Finland, Grant 363444.\r\nHung Le: Supported by an NSF grant CCF-2517033 and an NSF CAREER Award CCF-2237288.\r\nDa Wei Zheng: This project has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982. For open access purposes, the author has applied a CC BY public copyright\r\nlicense to any author-accepted manuscript version arising from this submission.\r\n","volume":374,"quality_controlled":"1","arxiv":1,"day":"01","author":[{"last_name":"Chan","first_name":"Timothy M.","orcid":"0000-0002-8093-0675","full_name":"Chan, Timothy M."},{"first_name":"Hsien-Chih","last_name":"Chang","orcid":"0000-0001-6714-7988","full_name":"Chang, Hsien-Chih"},{"first_name":"Jie","last_name":"Gao","full_name":"Gao, Jie","orcid":"0000-0001-5083-6082"},{"orcid":"0000-0002-6856-2902","full_name":"Kisfaludi-Bak, Sándor","first_name":"Sándor","last_name":"Kisfaludi-Bak"},{"orcid":"0000-0001-8223-9944","full_name":"Le, Hung","first_name":"Hung","last_name":"Le"},{"first_name":"Da Wei","last_name":"Zheng","full_name":"Zheng, Da Wei","id":"af77956b-e859-11ef-8dc9-d301b898e32f"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","OA_type":"gold","das_tickbox":"0","external_id":{"arxiv":["2605.10692"]},"file":[{"date_created":"2026-07-27T06:20:41Z","file_id":"22407","checksum":"1e66eba4cfe4e74ab28108b1ca0bb956","content_type":"application/pdf","relation":"main_file","access_level":"open_access","success":1,"creator":"dernst","file_size":1440497,"file_name":"2026_LIPIcSICALP_Chan.pdf","date_updated":"2026-07-27T06:20:41Z"}],"keyword":["String graphs","Fine-grained complexity","Theory of computation → Computational geometry"],"title":"Charting the landscape of diameter computation on geometric intersection graphs in the plane","has_accepted_license":"1","OA_place":"publisher","date_created":"2026-07-27T05:53:08Z","publication":"53rd International Colloquium on Automata, Languages, and Programming","researchdata_availability":"no","file_date_updated":"2026-07-27T06:20:41Z","supplementarymaterial":"no","fulldoi":"https://doi.org/10.4230/LIPICS.ICALP.2026.54","date_updated":"2026-08-12T09:03:26Z","month":"07"},{"acknowledgement":"M. Henzinger: This project has received funding from the European Research Council (ERC) under the European Union’s\r\nHorizon 2020 research and innovation programme (MoDynStruct, No. 101019564) and the Austrian Science Fund\r\n(FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the\r\nnetidee SCIENCE Stiftung, 2020–2024. Views and opinions expressed are those of the author(s) only and do not necessarily\r\nreflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor\r\nthe granting authority can be held responsible for them","doi":"10.1145/3816252","volume":22,"quality_controlled":"1","year":"2026","status":"public","date_published":"2026-07-06T00:00:00Z","PlanS_conform":"1","_id":"22716","intvolume":" 22","citation":{"apa":"Goranci, G., Henzinger, M., Räcke, H., & Sricharan, A. R. (2026). Incremental approximate maximum flow via residual graph sparsification. ACM Transactions on Algorithms. ACM. https://doi.org/10.1145/3816252","ama":"Goranci G, Henzinger M, Räcke H, Sricharan AR. Incremental approximate maximum flow via residual graph sparsification. ACM Transactions on Algorithms. 2026;22(3). doi:10.1145/3816252","chicago":"Goranci, Gramoz, Monika Henzinger, Harald Räcke, and A. R. Sricharan. “Incremental Approximate Maximum Flow via Residual Graph Sparsification.” ACM Transactions on Algorithms. ACM, 2026. https://doi.org/10.1145/3816252.","mla":"Goranci, Gramoz, et al. “Incremental Approximate Maximum Flow via Residual Graph Sparsification.” ACM Transactions on Algorithms, vol. 22, no. 3, 31, ACM, 2026, doi:10.1145/3816252.","ieee":"G. Goranci, M. Henzinger, H. Räcke, and A. R. Sricharan, “Incremental approximate maximum flow via residual graph sparsification,” ACM Transactions on Algorithms, vol. 22, no. 3. ACM, 2026.","ista":"Goranci G, Henzinger M, Räcke H, Sricharan AR. 2026. Incremental approximate maximum flow via residual graph sparsification. ACM Transactions on Algorithms. 22(3), 31.","short":"G. Goranci, M. Henzinger, H. Räcke, A.R. Sricharan, ACM Transactions on Algorithms 22 (2026)."},"publication_identifier":{"eissn":["1549-6333"],"issn":["1549-6325"]},"publisher":"ACM","ec_funded":1,"publication_status":"published","corr_author":"1","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."}],"oa_version":"Published Version","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"language":[{"iso":"eng"}],"scopus_import":"1","department":[{"_id":"MoHe"}],"oa":1,"article_number":"31","article_processing_charge":"Yes","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","grant_number":"101019564"},{"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"},{"name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"ddc":["000"],"issue":"3","month":"07","file_date_updated":"2026-08-20T06:19:51Z","researchdata_availability":"no","fulldoi":"https://doi.org/10.1145/3816252","date_updated":"2026-08-20T06:28:01Z","supplementarymaterial":"yes","OA_place":"publisher","publication":"ACM Transactions on Algorithms","date_created":"2026-08-16T22:01:43Z","has_accepted_license":"1","title":"Incremental approximate maximum flow via residual graph sparsification","article_type":"original","file":[{"success":1,"creator":"dernst","relation":"main_file","access_level":"open_access","file_name":"2026_TransactionsAlgorithms_Goranci.pdf","file_size":2272512,"date_updated":"2026-08-20T06:19:51Z","date_created":"2026-08-20T06:19:51Z","file_id":"22740","checksum":"97969d26dab25c3a35be3ae4dd0fd9ee","content_type":"application/pdf"}],"OA_type":"gold","das_tickbox":"0","external_id":{"arxiv":["2502.09105"]},"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"21280"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","arxiv":1,"author":[{"first_name":"Gramoz","last_name":"Goranci","full_name":"Goranci, Gramoz"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H"},{"full_name":"Räcke, Harald","last_name":"Räcke","first_name":"Harald"},{"first_name":"A. R.","last_name":"Sricharan","full_name":"Sricharan, A. R."}],"day":"06"},{"language":[{"iso":"eng"}],"scopus_import":"1","department":[{"_id":"MoHe"}],"article_number":"106663","article_processing_charge":"No","project":[{"call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"},{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","grant_number":"101019564"}],"intvolume":" 195","citation":{"ama":"Hahn N, Henzinger M, Stefankovic Z. Tight bounds on the performance of dynamic directed cutset data structures based on OMv. Information Processing Letters. 2026;195. doi:10.1016/j.ipl.2026.106663","apa":"Hahn, N., Henzinger, M., & Stefankovic, Z. (2026). Tight bounds on the performance of dynamic directed cutset data structures based on OMv. Information Processing Letters. Elsevier. https://doi.org/10.1016/j.ipl.2026.106663","mla":"Hahn, Niklas, et al. “Tight Bounds on the Performance of Dynamic Directed Cutset Data Structures Based on OMv.” Information Processing Letters, vol. 195, 106663, Elsevier, 2026, doi:10.1016/j.ipl.2026.106663.","ieee":"N. Hahn, M. Henzinger, and Z. Stefankovic, “Tight bounds on the performance of dynamic directed cutset data structures based on OMv,” Information Processing Letters, vol. 195. Elsevier, 2026.","chicago":"Hahn, Niklas, Monika Henzinger, and Zofia Stefankovic. “Tight Bounds on the Performance of Dynamic Directed Cutset Data Structures Based on OMv.” Information Processing Letters. Elsevier, 2026. https://doi.org/10.1016/j.ipl.2026.106663.","ista":"Hahn N, Henzinger M, Stefankovic Z. 2026. Tight bounds on the performance of dynamic directed cutset data structures based on OMv. Information Processing Letters. 195, 106663.","short":"N. Hahn, M. Henzinger, Z. Stefankovic, Information Processing Letters 195 (2026)."},"publication_identifier":{"issn":["0020-0190"]},"ec_funded":1,"publisher":"Elsevier","publication_status":"epub_ahead","abstract":[{"text":"Efficient data structures for computing the cutset of a set of nodes in a graph undergoing dynamic edge insertions/deletions are well-studied in undirected graphs. We study this problem in directed graphs and show a reduction from the Online Boolean Matrix-Vector Multiplication Conjecture (OMv) introduced by Henzinger et al. [STOC’15]. We prove conditional on OMv that a dynamic data structure computing the directed cutset of a set of nodes cannot have an amortized time of both O(n2−ε) for a query operation and O(n1−ε) for an update operation, for any constant ε > 0, even when an adversary’s operations are restricted to the incremental or decremental settings. We further give algorithms to match these lower bounds.","lang":"eng"}],"oa_version":"None","acknowledgement":"This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 101034413 and from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct, No. 101019564) Image 1 dummy alt text. Zofia Stefankovic was partially supported by the ISTernship program of the Institute of Science and Technology Austria and OEAD.","doi":"10.1016/j.ipl.2026.106663","volume":195,"quality_controlled":"1","year":"2026","status":"public","dataavailabilitystatement":"No data was used for the research described in the article.","date_published":"2026-08-30T00:00:00Z","_id":"22812","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"journal_article","author":[{"last_name":"Hahn","first_name":"Niklas","full_name":"Hahn, Niklas","id":"0a01c7b2-b823-11ed-9928-cc3f874f9ffd"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger"},{"last_name":"Stefankovic","first_name":"Zofia","full_name":"Stefankovic, Zofia"}],"day":"30","keyword":["Dynamic algorithms","Graph algorithms","Directed graphs","Lower bounds","Upper bounds"],"article_type":"original","OA_type":"closed access","das_tickbox":"1","date_created":"2026-09-06T22:01:55Z","publication":"Information Processing Letters","title":"Tight bounds on the performance of dynamic directed cutset data structures based on OMv","month":"08","researchdata_availability":"no","fulldoi":"https://doi.org/10.1016/j.ipl.2026.106663","date_updated":"2026-09-09T11:55:47Z","supplementarymaterial":"no"},{"ddc":["000"],"language":[{"iso":"eng"}],"article_processing_charge":"No","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":"d8f03aaa-b035-11f1-8588-d5147fa879e0","name":"Bilateral Artificial Intelligence (Lampert)","grant_number":"COE12"}],"oa":1,"article_number":"2:1-2:21","scopus_import":"1","department":[{"_id":"ChLa"},{"_id":"GradSch"},{"_id":"MoHe"}],"publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","ec_funded":1,"publication_identifier":{"isbn":["9783959774192"],"eissn":["1868-8969"]},"conference":{"name":"FORC: Symposium on Foundations of Responsible Computing","start_date":"2026-06-03","end_date":"2026-06-05","location":"Cambridge, MA; United States"},"citation":{"ama":"Kalinin N, Andersson JD. Learning rate scheduling with matrix factorization for private training. In: 7th Symposium on Foundations of Responsible Computing. Vol 368. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.FORC.2026.2","apa":"Kalinin, N., & Andersson, J. D. (2026). Learning rate scheduling with matrix factorization for private training. In 7th Symposium on Foundations of Responsible Computing (Vol. 368). Cambridge, MA; United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FORC.2026.2","chicago":"Kalinin, Nikita, and Joel D Andersson. “Learning Rate Scheduling with Matrix Factorization for Private Training.” In 7th Symposium on Foundations of Responsible Computing, Vol. 368. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.FORC.2026.2.","mla":"Kalinin, Nikita, and Joel D. Andersson. “Learning Rate Scheduling with Matrix Factorization for Private Training.” 7th Symposium on Foundations of Responsible Computing, vol. 368, 2:1-2:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.FORC.2026.2.","ieee":"N. Kalinin and J. D. Andersson, “Learning rate scheduling with matrix factorization for private training,” in 7th Symposium on Foundations of Responsible Computing, Cambridge, MA; United States, 2026, vol. 368.","short":"N. Kalinin, J.D. Andersson, in:, 7th Symposium on Foundations of Responsible Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","ista":"Kalinin N, Andersson JD. 2026. Learning rate scheduling with matrix factorization for private training. 7th Symposium on Foundations of Responsible Computing. FORC: Symposium on Foundations of Responsible Computing, LIPIcs, vol. 368, 2:1-2:21."},"intvolume":" 368","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa_version":"Published Version","abstract":[{"lang":"eng","text":"We study differentially private model training with stochastic gradient descent under learning rate scheduling and correlated noise. Although correlated noise, in particular via matrix factorizations, has been shown to improve accuracy, prior theoretical work focused primarily on the prefix-sum workload. That workload assumes a constant learning rate, whereas in practice learning rate schedules are widely used to accelerate training and improve convergence. We close this gap by deriving general upper and lower bounds for a broad class of learning rate schedules in both single- and multi-epoch settings. Building on these results, we propose a learning-rate-aware factorization that achieves improvements over prefix-sum factorizations under both MaxSE and MeanSE error metrics. Our theoretical analysis yields memory-efficient constructions suitable for practical deployment, and experiments on CIFAR-10 and IMDB datasets confirm that schedule-aware factorizations improve accuracy in private training."}],"corr_author":"1","volume":368,"quality_controlled":"1","doi":"10.4230/LIPIcs.FORC.2026.2","acknowledgement":"We thank Rasmus Pagh, Christoph Lampert and Jalaj Upadhyay for valuable\r\ncomments on an early draft. We thank Ryan Mckenna for a fruitful discussion on the experiment\r\ndesign. We thank Antti Honkela for sharing insights on learning rate scheduling and DP.\r\nNikita P. Kalinin: Funded in part by the Austrian Science Fund (FWF) [10.55776/COE12].\r\nJoel Daniel Andersson: Funded by the European Union. Views and opinions expressed are however\r\nthose of the author(s) only and do not necessarily reflect those of the European Union or the European\r\nResearch Council Executive Agency. Neither the European Union nor the granting authority can be\r\nheld responsible for them. This project has received funding from the European Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct,\r\nNo. 101019564). Additional funding by Providentia, a Data Science Distinguished Investigator grant\r\nfrom Novo Nordisk Fonden, with additional support from VILLUM Investigator grant 54451.\r\n","_id":"22146","alternative_title":["LIPIcs"],"date_published":"2026-06-01T00:00:00Z","status":"public","year":"2026","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Kalinin","first_name":"Nikita","id":"4b14526e-14d2-11ed-ba64-c14c9553d137","full_name":"Kalinin, Nikita"},{"id":"4a893819-d954-11f0-89b1-e360bad9ccc5","full_name":"Andersson, Joel D","first_name":"Joel D","last_name":"Andersson"}],"day":"01","arxiv":1,"file":[{"file_name":"2026_LIPIcsFORC_Kalinin.pdf","date_updated":"2026-06-29T06:55:23Z","file_size":1231914,"access_level":"open_access","relation":"main_file","creator":"dernst","success":1,"file_id":"22149","content_type":"application/pdf","checksum":"c661f016d3861a1c1b590b87a744d087","date_created":"2026-06-29T06:55:23Z"}],"keyword":["differential privacy","machine learning","matrix factorization"],"external_id":{"arxiv":["2511.17994"]},"das_tickbox":"0","OA_type":"gold","publication":"7th Symposium on Foundations of Responsible Computing","date_created":"2026-06-28T22:01:34Z","OA_place":"publisher","title":"Learning rate scheduling with matrix factorization for private training","has_accepted_license":"1","month":"06","date_updated":"2026-09-16T07:37:21Z","fulldoi":"https://doi.org/10.4230/LIPIcs.FORC.2026.2","supplementarymaterial":"no","researchdata_availability":"no","file_date_updated":"2026-06-29T06:55:23Z"},{"arxiv":1,"day":"25","author":[{"last_name":"De Berg","first_name":"Sarita","full_name":"De Berg, Sarita"},{"full_name":"Bække, Nynne Maria Foldager","first_name":"Nynne Maria Foldager","last_name":"Bække"},{"full_name":"Eriksen, Frida Astrup","first_name":"Frida Astrup","last_name":"Eriksen"},{"last_name":"Van Der Hoog","first_name":"Ivor","full_name":"Van Der Hoog, Ivor"},{"full_name":"Rotenberg, Eva","first_name":"Eva","last_name":"Rotenberg"},{"id":"7397d908-b582-11f0-bf73-88b902e86527","full_name":"Rutschmann, Daniel P","last_name":"Rutschmann","first_name":"Daniel P"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","OA_type":"gold","das_tickbox":"0","external_id":{"arxiv":["2605.07523"]},"keyword":["Pareto front","imprecise geometry","instance optimality","universal optimality","preprocessing model","partial information"],"file":[{"access_level":"open_access","relation":"main_file","success":1,"creator":"dernst","file_size":1102214,"date_updated":"2026-09-16T08:58:04Z","file_name":"2026_LIPIcsESA_deBerg.pdf","date_created":"2026-09-16T08:58:04Z","file_id":"22935","content_type":"application/pdf","checksum":"75cfae9e9773be4b06f9aab66041f0f3"}],"has_accepted_license":"1","title":"Instance optimal and universally optimal bounds for imprecise pareto fronts","OA_place":"publisher","date_created":"2026-09-13T22:01:52Z","publication":"34th Annual European Symposium on Algorithms","file_date_updated":"2026-09-16T08:58:04Z","researchdata_availability":"no","supplementarymaterial":"no","fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2026.106","date_updated":"2026-09-16T08:59:49Z","month":"08","ddc":["000"],"department":[{"_id":"MoHe"}],"scopus_import":"1","article_number":"106","oa":1,"article_processing_charge":"Yes","language":[{"iso":"eng"}],"abstract":[{"text":"In the imprecise geometry model, the input is a family of regions F = (R₁, R₂, …,R_n), each containing a point p_i ∈ R_i. The task is then to compute some function of the points p₁,p₂,… p_n, in our case an implicit representation of their Pareto front. To this end, one may query a region R_i to retrieve its contained point p_i ∈ R_i. In this model, efficiency is interpreted in two ways: minimizing (i) the number of retrievals, and (ii) the computation time both for preprocessing, and the execution of the query stage, i.e. for computing which points to query and constructing the output. \r\nWe present an algorithm to construct (an implicit representation of) the Pareto front for possibly overlapping rectangles, that is instance-optimal with respect to the number of retrievals. This means that for every fixed input (F, P), there is no algorithm that retrieves asymptotically fewer regions to compute the output. This is a strong algorithmic quality, as it means that our algorithm is competitive even to clairvoyant algorithms which only have to verify the correctness of a correct guess. In terms of algorithmic running time, instance-optimality is provably unobtainable. We instead present an algorithm which is within a log n-factor of instance optimality. This generalizes earlier results which assumed the regions to not overlap, at only a minor cost in running time. \r\nFor unit squares, we present an algorithm that is not only instance optimal in the number of retrievals, but also universally optimal in terms of running time. This means that for any fixed set of regions F, no algorithm has a better worst-case running time for all possible point sets P. Thus, this work presents the first universally optimal algorithm for overlapping planar input. Compared to previous work, our result improves the degree to which the input regions may overlap, the preprocessing time, the number of retrievals, and the running time.","lang":"eng"}],"corr_author":"1","oa_version":"Published Version","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"intvolume":" 388","citation":{"ista":"De Berg S, Bække NMF, Eriksen FA, Van Der Hoog I, Rotenberg E, Rutschmann DP. 2026. Instance optimal and universally optimal bounds for imprecise pareto fronts. 34th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 106.","short":"S. De Berg, N.M.F. Bække, F.A. Eriksen, I. Van Der Hoog, E. Rotenberg, D.P. Rutschmann, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","apa":"De Berg, S., Bække, N. M. F., Eriksen, F. A., Van Der Hoog, I., Rotenberg, E., & Rutschmann, D. P. (2026). Instance optimal and universally optimal bounds for imprecise pareto fronts. In 34th Annual European Symposium on Algorithms (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2026.106","ama":"De Berg S, Bække NMF, Eriksen FA, Van Der Hoog I, Rotenberg E, Rutschmann DP. Instance optimal and universally optimal bounds for imprecise pareto fronts. In: 34th Annual European Symposium on Algorithms. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.ESA.2026.106","mla":"De Berg, Sarita, et al. “Instance Optimal and Universally Optimal Bounds for Imprecise Pareto Fronts.” 34th Annual European Symposium on Algorithms, vol. 388, 106, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.ESA.2026.106.","ieee":"S. De Berg, N. M. F. Bække, F. A. Eriksen, I. Van Der Hoog, E. Rotenberg, and D. P. Rutschmann, “Instance optimal and universally optimal bounds for imprecise pareto fronts,” in 34th Annual European Symposium on Algorithms, L’Aquila, Italy, 2026, vol. 388.","chicago":"De Berg, Sarita, Nynne Maria Foldager Bække, Frida Astrup Eriksen, Ivor Van Der Hoog, Eva Rotenberg, and Daniel P Rutschmann. “Instance Optimal and Universally Optimal Bounds for Imprecise Pareto Fronts.” In 34th Annual European Symposium on Algorithms, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.ESA.2026.106."},"conference":{"end_date":"2026-09-04","location":"L’Aquila, Italy","name":"ESA: European Symposium on Algorithms","start_date":"2026-08-31"},"publication_identifier":{"isbn":["9783959774451"],"issn":["1868-8969"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","year":"2026","status":"public","date_published":"2026-08-25T00:00:00Z","_id":"22916","alternative_title":["LIPIcs"],"acknowledgement":"This work was supported by the the VILLUM Foundation grant (VIL37507) \"Efficient Recomputations for Changeful Problems\".","doi":"10.4230/LIPIcs.ESA.2026.106","quality_controlled":"1","volume":388},{"ddc":["000"],"language":[{"iso":"eng"}],"article_processing_charge":"Yes","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"}],"article_number":"101","oa":1,"department":[{"_id":"MoHe"}],"scopus_import":"1","publication_status":"published","ec_funded":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_identifier":{"isbn":["9783959774451"],"issn":["1868-8969"]},"citation":{"short":"I. Van Der Hoog, E. Rotenberg, D.P. Rutschmann, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","ista":"Van Der Hoog I, Rotenberg E, Rutschmann DP. 2026. Tight Better-Than-Worst-Case bounds for element distinctness and set intersection. 34th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 101.","apa":"Van Der Hoog, I., Rotenberg, E., & Rutschmann, D. P. (2026). Tight Better-Than-Worst-Case bounds for element distinctness and set intersection. In 34th Annual European Symposium on Algorithms (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2026.101","ama":"Van Der Hoog I, Rotenberg E, Rutschmann DP. Tight Better-Than-Worst-Case bounds for element distinctness and set intersection. In: 34th Annual European Symposium on Algorithms. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.ESA.2026.101","mla":"Van Der Hoog, Ivor, et al. “Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection.” 34th Annual European Symposium on Algorithms, vol. 388, 101, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.ESA.2026.101.","chicago":"Van Der Hoog, Ivor, Eva Rotenberg, and Daniel P Rutschmann. “Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection.” In 34th Annual European Symposium on Algorithms, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.ESA.2026.101.","ieee":"I. Van Der Hoog, E. Rotenberg, and D. P. Rutschmann, “Tight Better-Than-Worst-Case bounds for element distinctness and set intersection,” in 34th Annual European Symposium on Algorithms, L’Aquila, Italy, 2026, vol. 388."},"conference":{"start_date":"2026-08-31","name":"ESA: European Symposium on Algorithms","location":"L’Aquila, Italy","end_date":"2026-09-04"},"intvolume":" 388","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa_version":"Published Version","abstract":[{"lang":"eng","text":"The element distinctness problem takes as input a list I of n values from a totally ordered universe, where pairwise comparisons between values are allowed, and the goal is to decide whether I contains any duplicates. It is a well-studied problem with a classical worst-case Ω(n log n) comparison-based lower bound by Fredman [TCS'76]. At first glance, this lower bound appears to rule out any algorithm more efficient than the naive approach of sorting I and comparing adjacent elements. However, upon closer inspection, the Ω(n log n) bound is overly pessimistic. For instance, if I contains n/2 identical elements, a median-finding algorithm will, regardless of the input order, find a duplicate in linear time. This raises a natural question: Are there comparison-based lower bounds for element distinctness that are sensitive to the amount of duplicates in the input instance?\r\nTo address this question, we derive instance-specific lower bounds. For any input instance I, we represent the combinatorial structure of the duplicates in I by an undirected graph G(I) that connects identical elements. Each such graph G is a union of cliques, and we study algorithms by their worst-case running time over all inputs I' with G(I') ≅ G. We establish an adversarial lower bound showing that, for any deterministic algorithm 𝒜, there exists a graph G and an algorithm 𝒜' that, for all inputs I with G(I) ≅ G, is a factor O(log log n) faster than 𝒜. Consequently, no deterministic algorithm can be o(log log n)-competitive for all graphs G. We complement this with an O(log log n)-competitive deterministic algorithm, thereby obtaining tight bounds for element distinctness that go beyond classical worst-case analysis. Subsequently, we study the related problem of set intersection. We show that no deterministic set intersection algorithm can be o(log n)-competitive, and provide an O(log n)-competitive deterministic algorithm. We find it interesting and surprising to discover tight O(log log n)-competitive bounds for element distinctness. Moreover, we find the separation between element distinctness and the set intersection problem unexpected."}],"corr_author":"1","volume":388,"quality_controlled":"1","doi":"10.4230/LIPIcs.ESA.2026.101","acknowledgement":"Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann thank the VILLUM Foundation\r\ngrant (VIL37507) “Efficient Recomputations for Changeful Problems” for supporting this work.\r\nDaniel Rutschmann is supported by the European Research Council (ERC) under the European\r\nUnion’s Horizon 2020 research and innovation programme (No. 101019564) ","alternative_title":["LIPIcs"],"_id":"22915","date_published":"2026-08-25T00:00:00Z","status":"public","year":"2026","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Ivor","last_name":"Van Der Hoog","full_name":"Van Der Hoog, Ivor"},{"full_name":"Rotenberg, Eva","first_name":"Eva","last_name":"Rotenberg"},{"first_name":"Daniel P","last_name":"Rutschmann","full_name":"Rutschmann, Daniel P","id":"7397d908-b582-11f0-bf73-88b902e86527"}],"day":"25","arxiv":1,"file":[{"creator":"dernst","success":1,"access_level":"open_access","relation":"main_file","file_size":892322,"date_updated":"2026-09-16T09:20:49Z","file_name":"2026_LIPIcsESA_vanderHoog.pdf","date_created":"2026-09-16T09:20:49Z","file_id":"22937","content_type":"application/pdf","checksum":"c552853bfa37e4b9a0f060107e464ed0"}],"keyword":["Comparison-based analysis","set intersection","universal optimality"],"external_id":{"arxiv":["2511.02954"]},"OA_type":"gold","das_tickbox":"0","date_created":"2026-09-13T22:01:52Z","publication":"34th Annual European Symposium on Algorithms","OA_place":"publisher","title":"Tight Better-Than-Worst-Case bounds for element distinctness and set intersection","has_accepted_license":"1","month":"08","supplementarymaterial":"yes","fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2026.101","date_updated":"2026-09-16T09:21:35Z","researchdata_availability":"no","file_date_updated":"2026-09-16T09:20:49Z"},{"department":[{"_id":"MoHe"}],"scopus_import":"1","article_number":"61:1-61:12","oa":1,"project":[{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"article_processing_charge":"Yes","language":[{"iso":"eng"}],"ddc":["000"],"year":"2026","status":"public","date_published":"2026-08-25T00:00:00Z","alternative_title":["LIPIcs"],"_id":"22914","acknowledgement":"This project has received funding from the Austrian Science Fund (FWF)\r\ngrant DOI 10.55776/I5982. For open access purposes, the author has applied a CC BY public\r\ncopyright license to any author-accepted manuscript version arising from this submission. Thanks to Jie Gao for feedback on a preliminary version of the manuscript","doi":"10.4230/LIPIcs.ESA.2026.61","quality_controlled":"1","volume":388,"abstract":[{"lang":"eng","text":"We present the first truly subquadratic time algorithm to compute diameter and eccentricities in real-weighted directed graphs with constant distance VC-dimension and strongly sublinear-sized balanced separators. For real-weighted K_h-minor-free digraphs, this runs in O(n^{2-1/(2h-2)} polylog(n)) time.\r\nPrior to this work, truly subquadratic time computation of diameter was only known for real-weighted planar graphs, while extensions to broader classes like minor-free graphs were restricted to unweighted settings. In particular, existing algorithms that use VC-dimension [Ducoffe, Habib, Viennot; SICOMP 2022] [Le, Wulff-Nilsen; SODA 2024] [Chan, Chang, Gao, Le, Kisfaludi-Bak, Zheng; FOCS 2025] work with small integer weights, but do not naturally generalize to real weights. We overcome this barrier by introducing a randomized search-to-decision reduction, demonstrating that VC-dimension is a sufficiently powerful tool in the real-weighted regime."}],"corr_author":"1","oa_version":"Published Version","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"intvolume":" 388","citation":{"short":"D.W. Zheng, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","ista":"Zheng DW. 2026. Real-weighted diameter and eccentricities of minor-free and bounded VC-dimension graphs in truly subquadratic time. 34th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 61:1-61:12.","apa":"Zheng, D. W. (2026). Real-weighted diameter and eccentricities of minor-free and bounded VC-dimension graphs in truly subquadratic time. In 34th Annual European Symposium on Algorithms (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2026.61","ama":"Zheng DW. Real-weighted diameter and eccentricities of minor-free and bounded VC-dimension graphs in truly subquadratic time. In: 34th Annual European Symposium on Algorithms. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.ESA.2026.61","mla":"Zheng, Da Wei. “Real-Weighted Diameter and Eccentricities of Minor-Free and Bounded VC-Dimension Graphs in Truly Subquadratic Time.” 34th Annual European Symposium on Algorithms, vol. 388, 61:1-61:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.ESA.2026.61.","ieee":"D. W. Zheng, “Real-weighted diameter and eccentricities of minor-free and bounded VC-dimension graphs in truly subquadratic time,” in 34th Annual European Symposium on Algorithms, L’Aquila, Italy, 2026, vol. 388.","chicago":"Zheng, Da Wei. “Real-Weighted Diameter and Eccentricities of Minor-Free and Bounded VC-Dimension Graphs in Truly Subquadratic Time.” In 34th Annual European Symposium on Algorithms, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.ESA.2026.61."},"conference":{"end_date":"2026-09-04","location":"L’Aquila, Italy","name":"ESA: European Symposium on Algorithms","start_date":"2026-08-31"},"publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959774451"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","OA_type":"gold","das_tickbox":"0","external_id":{"arxiv":["2607.01926"]},"keyword":["Diameter","eccentricities","minor-free graphs","real weights","VC-dimension"],"file":[{"access_level":"open_access","relation":"main_file","creator":"dernst","success":1,"file_name":"2026_LIPIcsESA_Zheng.pdf","date_updated":"2026-09-17T09:28:04Z","file_size":760002,"date_created":"2026-09-17T09:28:04Z","file_id":"22942","content_type":"application/pdf","checksum":"574f50435b092a72041c7365cac3d280"}],"arxiv":1,"day":"25","author":[{"first_name":"Da Wei","last_name":"Zheng","id":"af77956b-e859-11ef-8dc9-d301b898e32f","full_name":"Zheng, Da Wei"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","file_date_updated":"2026-09-17T09:28:04Z","researchdata_availability":"no","date_updated":"2026-09-17T09:31:02Z","fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2026.61","supplementarymaterial":"no","month":"08","has_accepted_license":"1","title":"Real-weighted diameter and eccentricities of minor-free and bounded VC-dimension graphs in truly subquadratic time","OA_place":"publisher","date_created":"2026-09-13T22:01:52Z","publication":"34th Annual European Symposium on Algorithms"},{"ddc":["000"],"language":[{"iso":"eng"}],"oa":1,"article_number":"94:1-94:18","department":[{"_id":"MoHe"}],"scopus_import":"1","project":[{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982"}],"article_processing_charge":"Yes","conference":{"end_date":"2026-09-04","location":"L’Aquila, Italy","name":"ESA: European Symposium on Algorithms","start_date":"2026-08-31"},"citation":{"mla":"Bhore, Sujoy, et al. “DAG Covers for Structured Graphs: The Steiner Point Effect.” 34th Annual European Symposium on Algorithms, vol. 388, 94:1-94:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.ESA.2026.94.","ieee":"S. Bhore et al., “DAG covers for structured graphs: The Steiner point effect,” in 34th Annual European Symposium on Algorithms, L’Aquila, Italy, 2026, vol. 388.","chicago":"Bhore, Sujoy, Hsien Chih Chang, Jonathan Conroy, Arnold Filtser, Eunjin Oh, Nicole Wein, and Da Wei Zheng. “DAG Covers for Structured Graphs: The Steiner Point Effect.” In 34th Annual European Symposium on Algorithms, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.ESA.2026.94.","apa":"Bhore, S., Chang, H. C., Conroy, J., Filtser, A., Oh, E., Wein, N., & Zheng, D. W. (2026). DAG covers for structured graphs: The Steiner point effect. In 34th Annual European Symposium on Algorithms (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2026.94","ama":"Bhore S, Chang HC, Conroy J, et al. DAG covers for structured graphs: The Steiner point effect. In: 34th Annual European Symposium on Algorithms. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.ESA.2026.94","short":"S. Bhore, H.C. Chang, J. Conroy, A. Filtser, E. Oh, N. Wein, D.W. Zheng, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","ista":"Bhore S, Chang HC, Conroy J, Filtser A, Oh E, Wein N, Zheng DW. 2026. DAG covers for structured graphs: The Steiner point effect. 34th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 94:1-94:18."},"intvolume":" 388","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","publication_identifier":{"isbn":["9783959774451"],"issn":["1868-8969"]},"abstract":[{"text":"Given a weighted digraph G, a (t,g,μ)-DAG cover is a collection of g dominating DAGs D_1,… ,D_g such that all distances are approximately preserved: for every pair (u,v) of vertices, min_id_{D_i}(u,v) ≤ t⋅ d_G(u,v), and the total number of non-G edges is bounded by |(∪_i D_i)⧵ G| ≤ μ. Assadi, Hoppenworth, and Wein [STOC 25] and Filtser [SODA 26] studied DAG covers for general digraphs. This paper initiates the study of Steiner DAG cover, where the DAGs are allowed to contain Steiner points. \r\nWe obtain Steiner DAG covers on the important classes of planar digraphs and low-treewidth digraphs. Specifically, we show that any digraph with treewidth tw admits a (1,2,Õ(n⋅tw))-Steiner DAG cover. For planar digraphs we provide a (1+ε,2,Õ_ε(n))-Steiner DAG cover.\r\nWe also demonstrate a stark difference between Steiner and non-Steiner DAG covers. As a lower bound, we show that any non-Steiner DAG cover for graphs with treewidth 1 with stretch t < 2 and sub-quadratic number of extra edges requires Ω(log n) DAGs.","lang":"eng"}],"corr_author":"1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa_version":"Published Version","doi":"10.4230/LIPIcs.ESA.2026.94","acknowledgement":"This work was initiated at Dagstuhl Seminar 25212: Metric Sketching and\r\nDynamic Algorithms for Geometric and Topological Graphs. We thank the organizers and other\r\nparticipants for a productive environment.\r\nujoy Bhore: Work supported in part by ANRF ARG-MATRICS, Grant 002465.\r\nHsien-Chih Chang: Supported by the U.S. National Science Foundation Grant No. CCF-2443017.\r\nJonathan Conroy: Supported by the U.S. National Science Foundation Grant No. CCF-2443017.\r\nArnold Filtser: This research was supported by the ISRAEL SCIENCE FOUNDATION (grant No.\r\n1042/22).\r\nEunjin Oh: Supported by Institute of Information & Communications Technology Planning &\r\nEvaluation (IITP) grant funded by the Korea government (MSIT) (No. RS-2024-00440239, Sublinear\r\nScalable Algorithms for Large-Scale Data Analysis) and the National Research Foundation of Korea\r\n(NRF) grant funded by the Korea government (MSIT) (No. RS-2024-00358505).\r\nNicole Wein: Supported by NSF CAREER award 2541910.\r\nDa Wei Zheng: This project has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982. For open access purposes, the author has applied a CC BY public copyright\r\nlicense to any author-accepted manuscript version arising from this submission.","volume":388,"quality_controlled":"1","status":"public","year":"2026","alternative_title":["LIPIcs"],"_id":"22918","date_published":"2026-08-25T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","arxiv":1,"author":[{"first_name":"Sujoy","last_name":"Bhore","full_name":"Bhore, Sujoy"},{"last_name":"Chang","first_name":"Hsien Chih","full_name":"Chang, Hsien Chih"},{"full_name":"Conroy, Jonathan","last_name":"Conroy","first_name":"Jonathan"},{"first_name":"Arnold","last_name":"Filtser","full_name":"Filtser, Arnold"},{"full_name":"Oh, Eunjin","first_name":"Eunjin","last_name":"Oh"},{"full_name":"Wein, Nicole","first_name":"Nicole","last_name":"Wein"},{"first_name":"Da Wei","last_name":"Zheng","full_name":"Zheng, Da Wei","id":"af77956b-e859-11ef-8dc9-d301b898e32f"}],"day":"25","file":[{"success":1,"creator":"dernst","relation":"main_file","access_level":"open_access","date_updated":"2026-09-17T10:09:22Z","file_size":1123327,"file_name":"2026_LIPIcsESA_Bhore.pdf","date_created":"2026-09-17T10:09:22Z","content_type":"application/pdf","checksum":"2082683b3b72865c6a795305e5d61276","file_id":"22948"}],"keyword":["Directed graphs","DAG (directed acyclic graphs)","distortion","metric embeddings","planar graph","treewidth"],"OA_type":"gold","das_tickbox":"0","external_id":{"arxiv":["2604.04186"]},"OA_place":"publisher","publication":"34th Annual European Symposium on Algorithms","date_created":"2026-09-13T22:01:53Z","title":"DAG covers for structured graphs: The Steiner point effect","has_accepted_license":"1","month":"08","researchdata_availability":"no","file_date_updated":"2026-09-17T10:09:22Z","date_updated":"2026-09-17T10:27:46Z","fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2026.94","supplementarymaterial":"yes"},{"volume":388,"quality_controlled":"1","doi":"10.4230/LIPIcs.ESA.2026.45","acknowledgement":"Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann thank the VILLUM Foundation\r\ngrant (VIL37507) “Efficient Recomputations for Changeful Problems” for supporting this work.\r\nDaniel Rutschmann is supported by the European Research Council (ERC) under the European\r\nUnion’s Horizon 2020 research and innovation programme (No. 101019564) . John Iacono\r\nis supported by the Fonds de la Recherche Scientifique – FNRS.This work started at Dagstuhl 25191: Adaptive and Scalable Data Structures.\r\n\r\n","_id":"22917","alternative_title":["LIPIcs"],"date_published":"2026-08-25T00:00:00Z","status":"public","year":"2026","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","ec_funded":1,"publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959774451"]},"conference":{"name":"ESA: European Symposium on Algorithms","start_date":"2026-08-31","end_date":"2026-09-04","location":"L’Aquila, Italy"},"citation":{"short":"I. Van Der Hoog, J. Iacono, E. Rotenberg, D.P. Rutschmann, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","ista":"Van Der Hoog I, Iacono J, Rotenberg E, Rutschmann DP. 2026. Near-optimal working-set heaps and dijkstra on pointer machines. 34th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 45:1-45:13.","ama":"Van Der Hoog I, Iacono J, Rotenberg E, Rutschmann DP. Near-optimal working-set heaps and dijkstra on pointer machines. In: 34th Annual European Symposium on Algorithms. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.ESA.2026.45","apa":"Van Der Hoog, I., Iacono, J., Rotenberg, E., & Rutschmann, D. P. (2026). Near-optimal working-set heaps and dijkstra on pointer machines. In 34th Annual European Symposium on Algorithms (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2026.45","mla":"Van Der Hoog, Ivor, et al. “Near-Optimal Working-Set Heaps and Dijkstra on Pointer Machines.” 34th Annual European Symposium on Algorithms, vol. 388, 45:1-45:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.ESA.2026.45.","ieee":"I. Van Der Hoog, J. Iacono, E. Rotenberg, and D. P. Rutschmann, “Near-optimal working-set heaps and dijkstra on pointer machines,” in 34th Annual European Symposium on Algorithms, L’Aquila, Italy, 2026, vol. 388.","chicago":"Van Der Hoog, Ivor, John Iacono, Eva Rotenberg, and Daniel P Rutschmann. “Near-Optimal Working-Set Heaps and Dijkstra on Pointer Machines.” In 34th Annual European Symposium on Algorithms, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.ESA.2026.45."},"intvolume":" 388","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa_version":"Published Version","abstract":[{"lang":"eng","text":"A heap is a dynamic data structure that stores a set of labeled values under the following operations: pop returns the minimum value of the heap, Push(x_i) pushes a new value x_i onto the heap, and DecreaseKey(i, v) decreases the value x_i to v. A working-set heap is a heap that supports the x_i ← pop() operation in O(log Γ(x_i)) time where Γ(x_i) is the size of the working set: the number of elements that were pushed onto the heap while x_i was in the heap. The goal of working set heap design is to maintain the working set property while minimizing the overhead of the Push and DecreaseKey operations. On a word RAM, there exist working set heaps that support Push and DecreaseKey in amortized constant time. In this paper, we show via a simple construction that pointer machines, one of the most general and least-assuming computational models, support working set heaps that support Push in amortized constant time and DecreaseKey in inverse-Ackermann time. A by-product of this analysis is that Dijkstra’s shortest path algorithm can be near-universally optimal on a pointer machine - incurring only an additive O(m α(m)) overhead compared to the optimal running time for distance ordering, where m denotes the number of edges in the graph."}],"corr_author":"1","language":[{"iso":"eng"}],"project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020"}],"article_processing_charge":"Yes","article_number":"45:1-45:13","oa":1,"scopus_import":"1","department":[{"_id":"MoHe"}],"ddc":["000"],"month":"08","fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2026.45","supplementarymaterial":"no","date_updated":"2026-09-17T10:35:56Z","researchdata_availability":"no","file_date_updated":"2026-09-17T10:33:12Z","publication":"34th Annual European Symposium on Algorithms","date_created":"2026-09-13T22:01:53Z","OA_place":"publisher","title":"Near-optimal working-set heaps and dijkstra on pointer machines","has_accepted_license":"1","file":[{"content_type":"application/pdf","checksum":"52e7cb8881060e8f17b89cd46504f445","file_id":"22949","date_created":"2026-09-17T10:33:12Z","date_updated":"2026-09-17T10:33:12Z","file_size":792024,"file_name":"2026_LIPIcsESA_vanderHoog2.pdf","success":1,"creator":"dernst","relation":"main_file","access_level":"open_access"}],"keyword":["Data structures","graph algorithms","amortized analysis"],"external_id":{"arxiv":["2604.24134"]},"das_tickbox":"0","OA_type":"gold","type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"25","author":[{"full_name":"Van Der Hoog, Ivor","first_name":"Ivor","last_name":"Van Der Hoog"},{"first_name":"John","last_name":"Iacono","full_name":"Iacono, John"},{"full_name":"Rotenberg, Eva","last_name":"Rotenberg","first_name":"Eva"},{"full_name":"Rutschmann, Daniel P","id":"7397d908-b582-11f0-bf73-88b902e86527","first_name":"Daniel P","last_name":"Rutschmann"}],"arxiv":1}]