--- OA_place: publisher OA_type: gold _id: '22000' abstract: - lang: eng text: 'Simplicial approximation provides a framework for constructing simplicial complexes that are homotopy equivalent to a given manifold, provided a CW structure is explicitly known. However, its conventional implementation quickly becomes intractable on a computer: barycentric subdivision produces poorly shaped simplices, and the star condition introduces many vertices. To address these limitations, this article develops a subdivision scheme based on spherical Delaunay triangulations, which attains better refinement properties than barycentric subdivisions. Moreover, the star condition is reframed as two independent problems, one geometric and the other combinatorial, respectively tackled in the language of locally equiconnected spaces and the list homomorphism problem, allowing an exponential reduction in the number of vertices. Via a prototype implementation, we obtain simplicial complexes homotopy equivalent to Grassmannians and Stiefel manifolds up to dimension 5.' article_number: 93:1-93:22 article_processing_charge: Yes arxiv: 1 author: - first_name: Raphaël full_name: Tinarrage, Raphaël id: 40ebcc9d-905f-11ef-bf0a-dc475da8a04e last_name: Tinarrage orcid: 0000-0002-1404-1095 citation: ama: 'Tinarrage R. Simplicial approximation to CW complexes with spherical Delaunay triangulations. In: 42nd International Symposium on Computational Geometry. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.SoCG.2026.93' apa: 'Tinarrage, R. (2026). Simplicial approximation to CW complexes with spherical Delaunay triangulations. 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.93' chicago: Tinarrage, Raphaël. “Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations.” 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.93. ieee: R. Tinarrage, “Simplicial approximation to CW complexes with spherical Delaunay triangulations,” in 42nd International Symposium on Computational Geometry, New Brunswick, NJ, United States, 2026, vol. 367. ista: 'Tinarrage R. 2026. Simplicial approximation to CW complexes with spherical Delaunay triangulations. 42nd International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry vol. 367, 93:1-93:22.' mla: Tinarrage, Raphaël. “Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations.” 42nd International Symposium on Computational Geometry, vol. 367, 93:1-93:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.SoCG.2026.93. short: R. Tinarrage, in:, 42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. conference: end_date: 2026-06-05 location: New Brunswick, NJ, United States name: 'SoCG: Symposium on Computational Geometry' start_date: 2026-06-02 corr_author: '1' das_tickbox: '0' date_created: 2026-06-14T22:01:43Z date_published: 2026-05-27T00:00:00Z date_updated: 2026-06-22T11:28:26Z day: '27' ddc: - '500' department: - _id: UlWa doi: 10.4230/LIPIcs.SoCG.2026.93 external_id: arxiv: - '2112.07573' file: - access_level: open_access checksum: a468edad327962309688aa78678138da content_type: application/pdf creator: dernst date_created: 2026-06-22T07:53:13Z date_updated: 2026-06-22T07:53:13Z file_id: '22111' file_name: 2026_LIPIcSSoCG_Tinarrage.pdf file_size: 1436035 relation: main_file success: 1 file_date_updated: 2026-06-22T07:53:13Z has_accepted_license: '1' intvolume: ' 367' keyword: - Triangulation of manifolds - Simplicial approximation - CW complexes - Delaunay complexes - List homomorphism problem - Topological Data Analysis language: - iso: eng month: '05' oa: 1 oa_version: Published Version publication: 42nd International Symposium on Computational Geometry publication_identifier: eissn: - 1868-8969 isbn: - '9783959774185' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: link: - relation: software url: https://doi.org/10.5281/zenodo.19251455 researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: yes title: Simplicial approximation to CW complexes with spherical Delaunay triangulations tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 367 year: '2026' ... --- OA_place: publisher OA_type: gold _id: '22002' abstract: - lang: eng text: Topological simplification is the process of reducing complexity of a function while maintaining its essential features. Its goal is to find a new filter function, which reorders cells of the input complex in a way which eliminates some persistent homological features, without affecting the rest. We present a new approach to simplification based on the concept of forbidden regions and combinatorial dynamics. It allows us to reorder and cancel critical values, whose cancellation is not possible using existing methods because they are not consecutive in the total order. Each such cancellation takes O(c⋅n) time in the worst case, where c is the number of birth-death pairs and n is the size of the input complex. acknowledgement: "Jakub Leśkiewicz wants to thank his supervisor, Prof. Marian Mrozek, forscientific guidance, patience, and opportunity to delay the rest of his duties while writing this work.\r\nThe author also extends thanks to his entire family, to Zuzanna Świątek, and to Mikołaj Kardyś,\r\nBEng, MSc, for providing meals during the most intensive periods of work. Jakub Leśkiewicz: The research was partially funded by the Polish National Science Center under Opus Grant No. 2019/35/B/ST1/00874 and Opus Grant 2025/57/B/ST1/00550. Bartosz Furmanek: The research was partially funded by the Polish National Science Center under Opus Grant No. 2019/35/B/ST1/00874 and Opus Grant 2025/57/B/ST1/00550. Michał Lipiński: 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. \r\nDmitriy Morozov: This work was supported in part by the U.S. Department of Energy, Office\r\nof Science, Office of Advanced Scientific Computing Research, under Contract No. DE-AC02-\r\n05CH11231." alternative_title: - LIPIcs article_number: 72:1-72:17 article_processing_charge: No arxiv: 1 author: - first_name: Jakub full_name: Leśkiewicz, Jakub last_name: Leśkiewicz - first_name: Bartosz full_name: Furmanek, Bartosz last_name: Furmanek - first_name: Michał full_name: Lipiński, Michał id: dfffb474-4317-11ee-8f5c-fe3fc95a425e last_name: Lipiński orcid: 0000-0001-9789-9750 - first_name: Dmitriy full_name: Morozov, Dmitriy last_name: Morozov citation: ama: 'Leśkiewicz J, Furmanek B, Lipiński M, Morozov D. Topological simplification guided by forbidden regions. In: 42nd International Symposium on Computational Geometry. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.SoCG.2026.72' apa: 'Leśkiewicz, J., Furmanek, B., Lipiński, M., & Morozov, D. (2026). Topological simplification guided by forbidden regions. 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.72' chicago: Leśkiewicz, Jakub, Bartosz Furmanek, Michał Lipiński, and Dmitriy Morozov. “Topological Simplification Guided by Forbidden Regions.” 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.72. ieee: J. Leśkiewicz, B. Furmanek, M. Lipiński, and D. Morozov, “Topological simplification guided by forbidden regions,” in 42nd International Symposium on Computational Geometry, New Brunswick, NJ, United States, 2026, vol. 367. ista: 'Leśkiewicz J, Furmanek B, Lipiński M, Morozov D. 2026. Topological simplification guided by forbidden regions. 42nd International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 367, 72:1-72:17.' mla: Leśkiewicz, Jakub, et al. “Topological Simplification Guided by Forbidden Regions.” 42nd International Symposium on Computational Geometry, vol. 367, 72:1-72:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.SoCG.2026.72. short: J. Leśkiewicz, B. Furmanek, M. Lipiński, D. Morozov, in:, 42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. conference: end_date: 2026-06-05 location: New Brunswick, NJ, United States name: 'SoCG: Symposium on Computational Geometry' start_date: 2026-06-02 corr_author: '1' das_tickbox: '0' date_created: 2026-06-14T22:01:43Z date_published: 2026-05-27T00:00:00Z date_updated: 2026-06-22T07:45:36Z day: '27' ddc: - '500' department: - _id: HeEd doi: 10.4230/LIPIcs.SoCG.2026.72 ec_funded: 1 external_id: arxiv: - '2603.16416' file: - access_level: open_access checksum: 3be91c06fdf716c8735b6af64a09a921 content_type: application/pdf creator: dernst date_created: 2026-06-22T07:39:21Z date_updated: 2026-06-22T07:39:21Z file_id: '22110' file_name: 2026_LIPIcSSoCG_Leskiewicz.pdf file_size: 2052749 relation: main_file success: 1 file_date_updated: 2026-06-22T07:39:21Z has_accepted_license: '1' intvolume: ' 367' keyword: - persistent homology - topological simplification - depth posets language: - iso: eng month: '05' oa: 1 oa_version: Published Version project: - _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c call_identifier: H2020 grant_number: '101034413' name: 'IST-BRIDGE: International postdoctoral program' publication: 42nd International Symposium on Computational Geometry publication_identifier: eissn: - 1868-8969 isbn: - '9783959774185' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Topological simplification guided by forbidden regions tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 367 year: '2026' ... --- OA_place: publisher OA_type: gold _id: '22003' abstract: - lang: eng text: 'Let G be a finite, connected metric graph and let X be a subset of G. If X is sufficiently dense in G, we show that the Gromov-Hausdorff distance matches the Hausdorff distance, namely d_GH(G,X) = d_H(G,X). When the metric graph is the circle G = S¹ with circumference 2π, a recent study established the equality d_GH(S¹,X) = d_H(S¹,X) whenever d_GH(S¹,X) < π/6. Our results relax this hypothesis to d_GH(S¹,X) < π/3, and furthermore, we show that the constant π/3 is the best possible. We lower bound the Gromov-Hausdorff distance d_GH(G,X) by the Hausdorff distance d_H(G,X) via a simple topological obstruction: the existence of a possibly discontinuous function f: G → X with too small distortion contradicts the connectedness of G.' acknowledgement: "Funding Henry Adams: Simons Foundation Travel Support for Mathematicians.\r\nŽiga Virk: Slovene research agency grant P1-0292.\r\nNicolò Zava: FWF Grant, Project number I4245-N35.\r\n" alternative_title: - LIPIcs article_number: 3:1-3:16 article_processing_charge: Yes arxiv: 1 author: - first_name: Henry full_name: Adams, Henry last_name: Adams - first_name: Sushovan full_name: Majhi, Sushovan last_name: Majhi - first_name: Fedor full_name: Manin, Fedor last_name: Manin - first_name: Ziga full_name: Virk, Ziga id: 2E36B656-F248-11E8-B48F-1D18A9856A87 last_name: Virk - first_name: Nicolò full_name: Zava, Nicolò id: c8b3499c-7a77-11eb-b046-aa368cbbf2ad last_name: Zava orcid: 0000-0001-8686-1888 citation: ama: 'Adams H, Majhi S, Manin F, Virk Z, Zava N. Lower bounding the Gromov–Hausdorff distance in metric graphs. In: 42nd International Symposium on Computational Geometry. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.SoCG.2026.3' apa: 'Adams, H., Majhi, S., Manin, F., Virk, Z., & Zava, N. (2026). Lower bounding the Gromov–Hausdorff distance in metric graphs. 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.3' chicago: Adams, Henry, Sushovan Majhi, Fedor Manin, Ziga Virk, and Nicolò Zava. “Lower Bounding the Gromov–Hausdorff Distance in Metric Graphs.” 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.3. ieee: H. Adams, S. Majhi, F. Manin, Z. Virk, and N. Zava, “Lower bounding the Gromov–Hausdorff distance in metric graphs,” in 42nd International Symposium on Computational Geometry, New Brunswick, NJ, United States, 2026, vol. 367. ista: 'Adams H, Majhi S, Manin F, Virk Z, Zava N. 2026. Lower bounding the Gromov–Hausdorff distance in metric graphs. 42nd International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 367, 3:1-3:16.' mla: Adams, Henry, et al. “Lower Bounding the Gromov–Hausdorff Distance in Metric Graphs.” 42nd International Symposium on Computational Geometry, vol. 367, 3:1-3:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.SoCG.2026.3. short: H. Adams, S. Majhi, F. Manin, Z. Virk, N. Zava, in:, 42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. conference: end_date: 2026-06-05 location: New Brunswick, NJ, United States name: 'SoCG: Symposium on Computational Geometry' start_date: 2026-06-02 corr_author: '1' das_tickbox: '0' date_created: 2026-06-14T22:01:44Z date_published: 2026-05-27T00:00:00Z date_updated: 2026-06-22T08:49:17Z day: '27' ddc: - '500' department: - _id: HeEd doi: 10.4230/LIPIcs.SoCG.2026.3 external_id: arxiv: - '2411.09182' file: - access_level: open_access checksum: 25d27c016409563196b8aecfe5bfdf41 content_type: application/pdf creator: dernst date_created: 2026-06-22T08:43:47Z date_updated: 2026-06-22T08:43:47Z file_id: '22115' file_name: 2026_LIPIcSSoCG_Adams.pdf file_size: 1091310 relation: main_file success: 1 file_date_updated: 2026-06-22T08:43:47Z has_accepted_license: '1' intvolume: ' 367' keyword: - Gromov–Hausdorff distance - distortion - connectedness - Borsuk–Ulam theorem language: - iso: eng month: '05' oa: 1 oa_version: Published Version project: - _id: 26AD5D90-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I04245 name: Algebraic Footprints of Geometric Features in Homology publication: 42nd International Symposium on Computational Geometry publication_identifier: eissn: - 1868-8969 isbn: - '9783959774185' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Lower bounding the Gromov–Hausdorff distance in metric graphs tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 367 year: '2026' ... --- OA_place: publisher OA_type: gold _id: '22004' abstract: - lang: eng text: "Recent research on computing the diameter of geometric intersection graphs has made significant strides, primarily focusing on the 2D case [Duraj et al., 2024; Hsien-Chih Chang et al., 2024; Chan et al., 2025] where truly subquadratic-time algorithms were given for simple objects such as unit-disks and (axis-aligned) squares. However, in three or higher dimensions, there is no known truly subquadratic-time algorithm for any intersection graph of non-trivial objects, even basic ones such as unit balls or (axis-aligned) unit cubes. This was partially explained by the pioneering work of Bringmann et al. [Karl Bringmann et al., 2022] which gave several truly subquadratic lower bounds, notably for unit balls or unit cubes in 3D when the graph diameter Δ is at least Ω(log n), hinting at a pessimistic outlook for the complexity of the diameter problem in higher dimensions. In this paper, we substantially extend the landscape of diameter computation for objects in three and higher dimensions, giving a few positive results. Our highlighted findings include: \r\n1) A truly subquadratic-time algorithm for deciding if the diameter of unit cubes in 3D is at most 3 (Diameter-3 hereafter), the first algorithm of its kind for objects in 3D or higher dimensions. Our algorithm is based on a novel connection to pseudolines, which is of independent interest. \r\n2) A truly subquadratic time lower bound for Diameter-3 of unit balls in 3D under the Orthogonal Vector (OV) hypothesis, giving the first separation between unit balls and unit cubes in the small diameter regime. Previously, computing the diameter for both objects was known to be quadratic hard when the diameter is Ω(log n) [Karl Bringmann et al., 2022]. \r\n3) A near-linear-time algorithm for Diameter-2 of unit cubes in 3D, generalizing the previous result for unit squares in 2D [Karl Bringmann et al., 2022]. \r\n4) A truly subquadratic-time algorithm and lower bound for Diameter-2 and Diameter-3 of rectangular boxes (of arbitrary dimension and sizes), respectively." acknowledgement: "Timothy M. Chan: Supported by NSF grant CCF-2224271.\r\nHsien-Chih Chang: Supported by NSF CAREER award CCF-2443017.\r\nJie Gao: Supported by NSF DMS-2220271, DMS-2311064, IIS-2229876, CCF-2118953, CNS-2515159.\r\nSándor Kisfaludi-Bak: Supported by the Research Council of Finland, Grant 363444.\r\nHung Le: Supported by an NSF grant CCF-2517033 and an NSF CAREER Award CCF-2237288. Da Wei Zheng: This project has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982. For open access purposes, the author has applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission." alternative_title: - LIPIcs article_number: 29:1-29:15 article_processing_charge: Yes arxiv: 1 author: - first_name: Timothy M. full_name: Chan, Timothy M. last_name: Chan - first_name: Hsien Chih full_name: Chang, Hsien Chih last_name: Chang - first_name: Jie full_name: Gao, Jie last_name: Gao - first_name: Sándor full_name: Kisfaludi-Bak, Sándor last_name: Kisfaludi-Bak - first_name: Hung full_name: Le, Hung last_name: Le - first_name: Da Wei full_name: Zheng, Da Wei id: af77956b-e859-11ef-8dc9-d301b898e32f last_name: Zheng citation: ama: 'Chan TM, Chang HC, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. Charting the diameter computation landscape of intersection graphs in 3D and above. In: 42nd International Symposium on Computational Geometry. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.SoCG.2026.29' apa: 'Chan, T. M., Chang, H. C., Gao, J., Kisfaludi-Bak, S., Le, H., & Zheng, D. W. (2026). Charting the diameter computation landscape of intersection graphs in 3D and above. In 42nd International Symposium on Computational Geometry (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2026.29' chicago: Chan, Timothy M., Hsien Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng. “Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above.” In 42nd International Symposium on Computational Geometry, Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.SoCG.2026.29. ieee: T. M. Chan, H. C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, and D. W. Zheng, “Charting the diameter computation landscape of intersection graphs in 3D and above,” in 42nd International Symposium on Computational Geometry, New Brunswick, NJ, United States, 2026, vol. 367. ista: 'Chan TM, Chang HC, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. 2026. Charting the diameter computation landscape of intersection graphs in 3D and above. 42nd International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 367, 29:1-29:15.' mla: Chan, Timothy M., et al. “Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above.” 42nd International Symposium on Computational Geometry, vol. 367, 29:1-29:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.SoCG.2026.29. short: T.M. Chan, H.C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D.W. Zheng, in:, 42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. conference: end_date: 2026-06-05 location: New Brunswick, NJ, United States name: 'SoCG: Symposium on Computational Geometry' start_date: 2026-06-02 corr_author: '1' das_tickbox: '0' date_created: 2026-06-14T22:01:44Z date_published: 2026-05-27T00:00:00Z date_updated: 2026-06-22T08:37:44Z day: '27' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.SoCG.2026.29 external_id: arxiv: - '2603.21790' file: - access_level: open_access checksum: ffff03934cc182757d6db82d88f896e6 content_type: application/pdf creator: dernst date_created: 2026-06-22T08:34:11Z date_updated: 2026-06-22T08:34:11Z file_id: '22114' file_name: 2026_LIPIcSSoCG_Chan.pdf file_size: 918197 relation: main_file success: 1 file_date_updated: 2026-06-22T08:34:11Z has_accepted_license: '1' intvolume: ' 367' keyword: - Graph Diameter - Geometric Intersection Graphs - Unit Ball Graphs language: - iso: eng month: '05' oa: 1 oa_version: Published Version project: - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions publication: 42nd International Symposium on Computational Geometry publication_identifier: eissn: - 1868-8969 isbn: - '9783959774185' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Charting the diameter computation landscape of intersection graphs in 3D and above tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 367 year: '2026' ... --- OA_place: publisher OA_type: gold _id: '21411' abstract: - lang: eng text: "To achieve fast recovery from link failures, most modern communication networks feature fully\r\ndecentralized fast re-routing mechanisms. These re-routing mechanisms rely on pre-installed static re-routing rules at the nodes (the routers), which depend only on local failure information, namely on the failed links incident to the node. Ideally, a network is perfectly resilient: the re-routing rules ensure that packets are always successfully routed to their destinations as long as the source and the destination are still physically connected in the underlying network after the failures. Unfortunately, there are examples where achieving perfect resilience is not possible. Surprisingly, only very little is known about the algorithmic aspect of when and how perfect resilience can be achieved. We investigate the computational complexity of analyzing such local fast re-routing mechanisms. Our main result is a negative one: we show that even checking whether a given set of static re-routing rules ensures perfect resilience is coNP-complete. Additionally, we investigate other fundamental variations of the problem. In particular, we show that our coNP-completeness proof also applies to scenarios where the re-routing rules have specific patterns (known as skipping in the literature). On the positive side, for scenarios where nodes do not have information about the link from which a packet arrived (the so-called in-port), we present a linear-time algorithm to realize perfect resilience whenever possible (which we show can also be determined in linear time). " acknowledgement: "Matthias Bentert: ERC Horizon 2020 research and innovation programme (grant agreement\r\nNo. 819416) and ERC Consolidator grant AdjustNet (agreement No. 864228).\r\nEsra Ceylan: German Research Foundation (DFG) project ReNO, Schwerpunktprogramm:\r\nResilienz in Vernetzten Welten – Beherrschen von Fehlern, Überlast, Angriffen und dem\r\nUnbekannten (SPP 2378).\r\nStefan Schmid: German Research Foundation (DFG) project ReNO, Schwerpunktprogramm:\r\nResilienz in Vernetzten Welten – Beherrschen von Fehlern, Überlast, Angriffen und dem\r\nUnbekannten (SPP 2378)." alternative_title: - LIPIcs article_number: '31' article_processing_charge: No author: - first_name: Matthias full_name: Bentert, Matthias last_name: Bentert - first_name: Esra full_name: Ceylan, Esra last_name: Ceylan - first_name: Valentin full_name: Hübner, Valentin id: 2c8aa207-dc7d-11ea-9b2f-f22972ecd910 last_name: Hübner orcid: 0009-0001-5009-4987 - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid - first_name: Jiří full_name: Srba, Jiří last_name: Srba citation: ama: 'Bentert M, Ceylan E, Hübner V, Schmid S, Srba J. Fast re-routing in networks: On the complexity of perfect resilience. In: 29th International Conference on Principles of Distributed Systems. Vol 361. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.OPODIS.2025.31' apa: 'Bentert, M., Ceylan, E., Hübner, V., Schmid, S., & Srba, J. (2026). Fast re-routing in networks: On the complexity of perfect resilience. In 29th International Conference on Principles of Distributed Systems (Vol. 361). Iaşi, Romania: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2025.31' chicago: 'Bentert, Matthias, Esra Ceylan, Valentin Hübner, Stefan Schmid, and Jiří Srba. “Fast Re-Routing in Networks: On the Complexity of Perfect Resilience.” In 29th International Conference on Principles of Distributed Systems, Vol. 361. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.OPODIS.2025.31.' ieee: 'M. Bentert, E. Ceylan, V. Hübner, S. Schmid, and J. Srba, “Fast re-routing in networks: On the complexity of perfect resilience,” in 29th International Conference on Principles of Distributed Systems, Iaşi, Romania, 2026, vol. 361.' ista: 'Bentert M, Ceylan E, Hübner V, Schmid S, Srba J. 2026. Fast re-routing in networks: On the complexity of perfect resilience. 29th International Conference on Principles of Distributed Systems. OPODIS: Conference on Principles of Distributed Systems, LIPIcs, vol. 361, 31.' mla: 'Bentert, Matthias, et al. “Fast Re-Routing in Networks: On the Complexity of Perfect Resilience.” 29th International Conference on Principles of Distributed Systems, vol. 361, 31, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.OPODIS.2025.31.' short: M. Bentert, E. Ceylan, V. Hübner, S. Schmid, J. Srba, in:, 29th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. conference: end_date: 2025-12-05 location: Iaşi, Romania name: 'OPODIS: Conference on Principles of Distributed Systems' start_date: 2025-12-03 date_created: 2026-03-08T23:01:46Z date_published: 2026-01-07T00:00:00Z date_updated: 2026-03-09T12:36:11Z day: '07' ddc: - '000' department: - _id: KrCh doi: 10.4230/LIPIcs.OPODIS.2025.31 file: - access_level: open_access checksum: a7af114da7c38d2338b4edb922eb27f1 content_type: application/pdf creator: dernst date_created: 2026-03-09T12:33:58Z date_updated: 2026-03-09T12:33:58Z file_id: '21419' file_name: 2026_OPODIS_Bentert.pdf file_size: 1041334 relation: main_file success: 1 file_date_updated: 2026-03-09T12:33:58Z has_accepted_license: '1' intvolume: ' 361' language: - iso: eng month: '01' oa: 1 oa_version: Published Version publication: 29th International Conference on Principles of Distributed Systems publication_identifier: eissn: - 1868-8969 isbn: - '9783959774093' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: 'Fast re-routing in networks: On the complexity of perfect resilience' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 361 year: '2026' ... --- OA_place: publisher OA_type: gold _id: '22146' 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. 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" alternative_title: - LIPIcs article_number: 2:1-2:21 article_processing_charge: No arxiv: 1 author: - first_name: Nikita full_name: Kalinin, Nikita id: 4b14526e-14d2-11ed-ba64-c14c9553d137 last_name: Kalinin - first_name: Joel D full_name: Andersson, Joel D id: 4a893819-d954-11f0-89b1-e360bad9ccc5 last_name: Andersson 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. 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. 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.' 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. short: N. Kalinin, J.D. Andersson, in:, 7th Symposium on Foundations of Responsible Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. conference: end_date: 2026-06-05 location: Cambridge, MA; United States name: 'FORC: Symposium on Foundations of Responsible Computing' start_date: 2026-06-03 corr_author: '1' das_tickbox: '0' date_created: 2026-06-28T22:01:34Z date_published: 2026-06-01T00:00:00Z date_updated: 2026-06-29T06:56:34Z day: '01' ddc: - '000' department: - _id: ChLa - _id: GradSch - _id: MoHe doi: 10.4230/LIPIcs.FORC.2026.2 ec_funded: 1 external_id: arxiv: - '2511.17994' file: - access_level: open_access checksum: c661f016d3861a1c1b590b87a744d087 content_type: application/pdf creator: dernst date_created: 2026-06-29T06:55:23Z date_updated: 2026-06-29T06:55:23Z file_id: '22149' file_name: 2026_LIPIcsFORC_Kalinin.pdf file_size: 1231914 relation: main_file success: 1 file_date_updated: 2026-06-29T06:55:23Z has_accepted_license: '1' intvolume: ' 368' keyword: - differential privacy - machine learning - matrix factorization language: - iso: eng month: '06' oa: 1 oa_version: Published Version project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures publication: 7th Symposium on Foundations of Responsible Computing publication_identifier: eissn: - 1868-8969 isbn: - '9783959774192' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: Learning rate scheduling with matrix factorization for private training tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 368 year: '2026' ... --- OA_place: publisher OA_type: gold _id: '22299' abstract: - lang: eng text: The depth poset of a filtered Lefschetz complex reflects the dependencies between the cancellations of different shallow birth-death pairs. Using the fast algorithms for computing the depth poset in [Edelsbrunner et al., 2026] and for updating the persistence diagram under transpositions in [Cohen-Steiner et al., 2006], we give a complete case analysis of how transpositions of cells in the filter affect the depth poset. In addition, we present statistics on the depth poset for random point data and its sensitivity to the transpositions that occur in random straight-line homotopies. acknowledgement: "The authors thank Jakub Leśkiewicz and Bartosz Furmanek for discussions\r\nthat helped improve the paper. Herbert Edelsbrunner: DFG Collaborative Research Center TRR 109, Austrian Science\r\nFund (FWF), grant no. I 02979-N35\r\nMichał Lipiński: European Union’s Horizon 2020 research and innovation programme under the\r\nMarie Skłodowska-Curie Grant Agreement No. 101034413\r\nMarian Mrozek: Polish National Science Center under Opus Grant 2019/35/B/ST1/00874 and Opus\r\nGrant 2025/57/B/ST1/00550" alternative_title: - LIPIcs article_number: 41:1-41:18 article_processing_charge: Yes arxiv: 1 author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Michał full_name: Lipiński, Michał id: dfffb474-4317-11ee-8f5c-fe3fc95a425e last_name: Lipiński orcid: 0000-0001-9789-9750 - first_name: Marian full_name: Mrozek, Marian last_name: Mrozek orcid: 0000-0002-0619-6417 - first_name: Manuel full_name: Soriano Trigueros, Manuel id: 15ebd7cf-15bf-11ee-aebd-bb4bb5121ea8 last_name: Soriano Trigueros orcid: 0000-0003-2449-1433 - first_name: Fedor full_name: Zimin, Fedor id: afd27eda-91c1-11f0-aad8-c6edbec24c04 last_name: Zimin citation: ama: 'Edelsbrunner H, Lipiński M, Mrozek M, Soriano Trigueros M, Zimin F. The depth poset under transpositions in the filter. In: 42nd International Symposium on Computational Geometry. Vol 367. Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPICS.SOCG.2026.41' apa: 'Edelsbrunner, H., Lipiński, M., Mrozek, M., Soriano Trigueros, M., & Zimin, F. (2026). The depth poset under transpositions in the filter. 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.41' chicago: Edelsbrunner, Herbert, Michał Lipiński, Marian Mrozek, Manuel Soriano Trigueros, and Fedor Zimin. “The Depth Poset under Transpositions in the Filter.” 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.41. ieee: H. Edelsbrunner, M. Lipiński, M. Mrozek, M. Soriano Trigueros, and F. Zimin, “The depth poset under transpositions in the filter,” in 42nd International Symposium on Computational Geometry, New Brunswick, NJ, United States, 2026, vol. 367. ista: 'Edelsbrunner H, Lipiński M, Mrozek M, Soriano Trigueros M, Zimin F. 2026. The depth poset under transpositions in the filter. 42nd International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 367, 41:1-41:18.' mla: Edelsbrunner, Herbert, et al. “The Depth Poset under Transpositions in the Filter.” 42nd International Symposium on Computational Geometry, vol. 367, 41:1-41:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPICS.SOCG.2026.41. short: H. Edelsbrunner, M. Lipiński, M. Mrozek, M. Soriano Trigueros, F. Zimin, in:, 42nd International Symposium on Computational Geometry, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. conference: end_date: 2026-06-05 location: New Brunswick, NJ, United States name: 'SoCG: Symposium on Computational Geometry' start_date: 2026-06-02 corr_author: '1' das_tickbox: '0' date_created: 2026-07-13T09:56:38Z date_published: 2026-05-27T00:00:00Z date_updated: 2026-07-14T06:09:32Z day: '27' ddc: - '500' department: - _id: HeEd - _id: GradSch doi: 10.4230/LIPICS.SOCG.2026.41 ec_funded: 1 external_id: arxiv: - '2511.21961' file: - access_level: open_access checksum: 9dfb96ee66985c724b499b0e5888dc8e content_type: application/pdf creator: dernst date_created: 2026-07-14T06:08:05Z date_updated: 2026-07-14T06:08:05Z file_id: '22329' file_name: 2026_LIPIcSSoCG_Edelsbrunner.pdf file_size: 2902144 relation: main_file success: 1 file_date_updated: 2026-07-14T06:08:05Z has_accepted_license: '1' intvolume: ' 367' keyword: - Algebraic topology - Lefschetz complexes - persistent homology - vines and vineyards - birth-death pairs - shallow pairs - relations - partial orders - transpositions - Theory of computation → Computational geometry language: - iso: eng month: '05' oa: 1 oa_version: Published Version project: - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes - _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c call_identifier: H2020 grant_number: '101034413' name: 'IST-BRIDGE: International postdoctoral program' publication: 42nd International Symposium on Computational Geometry publication_identifier: eissn: - 1868-8969 isbn: - '9783959774185' publication_status: published publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: The depth poset under transpositions in the filter tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 367 year: '2026' ... --- OA_place: publisher OA_type: gold _id: '22405' abstract: - lang: eng text: "Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainly depends on the object types: for unit disks and squares in 2D, the problem is solvable in truly subquadratic time [Chan et al., 2025], while for other objects, including unit segments and equilateral triangles in 2D or unit balls and axis-parallel unit cubes in 3D, there is no truly subquadratic time algorithm under the Orthogonal Vector (OV) hypothesis [Bringmann et al., 2022]. \r\nWe undertake a comprehensive study of computing the diameter of geometric intersection graphs for various types of objects. We discover many new irregularities, showing that the landscape is extremely nuanced: the source of hardness is a combination of the object type, the true diameter value, and how the objects intersect with each other. Our highlighted results for the 2D case include: \r\n1) The diameter of non-degenerate, axis-aligned line segments can be computed in truly subquadratic time. Previous hardness result [Bringmann et al., 2022] for line segments applies only to degenerate instances. On the other hand, for the degenerate case, we show that a truly subquadratic time algorithm exists when the true diameter is constant. \r\n2) An almost-linear-time algorithm for unit-square graphs of constant diameter. Previous algorithms [Duraj et al., 2024; Chan et al., 2025] rely on succinct representation assuming bounded VC-dimension; for such a strategy Ω(n^{7/4}) time is an inherent barrier. \r\n3) An Õ(n^{4/3})-time algorithm to decide if the diameter of a unit-disk graph is at most 2. This improves upon the recent algorithm with running time Õ(n^{2-1/9}) [Chan et al., 2025]. \r\n4) Deciding if the diameter of intersection graphs of fat triangles or line segments is at most 2 is truly subquadratic-hard under fine-grained complexity assumptions. Previous lower bounds [Bringmann et al., 2022] only hold when deciding if diameter is at most 3. Our findings are presented in a pair of papers. This paper focuses solely on the 2D case, while the companion paper is devoted to higher-dimensional cases." acknowledgement: "Timothy M. Chan: Supported by NSF grant CCF-2224271.\r\nHsien-Chih Chang: Supported by NSF CAREER award CCF-2443017.\r\nJie Gao: Supported by NSF DMS-2220271, DMS-2311064, IIS-2229876, CCF-2118953, CNS-2515159.\r\nSándor Kisfaludi-Bak: Supported by the Research Council of Finland, Grant 363444.\r\nHung Le: Supported by an NSF grant CCF-2517033 and an NSF CAREER Award CCF-2237288.\r\nDa Wei Zheng: This project has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982. For open access purposes, the author has applied a CC BY public copyright\r\nlicense to any author-accepted manuscript version arising from this submission.\r\n" article_number: 54:1-54:22 article_processing_charge: No arxiv: 1 author: - first_name: Timothy M. full_name: Chan, Timothy M. last_name: Chan orcid: 0000-0002-8093-0675 - first_name: Hsien-Chih full_name: Chang, Hsien-Chih last_name: Chang orcid: 0000-0001-6714-7988 - first_name: Jie full_name: Gao, Jie last_name: Gao orcid: 0000-0001-5083-6082 - first_name: Sándor full_name: Kisfaludi-Bak, Sándor last_name: Kisfaludi-Bak orcid: 0000-0002-6856-2902 - first_name: Hung full_name: Le, Hung last_name: Le orcid: 0000-0001-8223-9944 - first_name: Da Wei full_name: Zheng, Da Wei id: af77956b-e859-11ef-8dc9-d301b898e32f last_name: Zheng citation: ama: 'Chan TM, Chang H-C, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. Charting the landscape of diameter computation on geometric intersection graphs in the plane. In: 53rd International Colloquium on Automata, Languages, and Programming. Vol 374. Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPICS.ICALP.2026.54' apa: 'Chan, T. M., Chang, H.-C., Gao, J., Kisfaludi-Bak, S., Le, H., & Zheng, D. W. (2026). Charting the landscape of diameter computation on geometric intersection graphs in the plane. In 53rd International Colloquium on Automata, Languages, and Programming (Vol. 374). Egham, United Kingdom: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2026.54' chicago: Chan, Timothy M., Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng. “Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane.” In 53rd International Colloquium on Automata, Languages, and Programming, Vol. 374. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPICS.ICALP.2026.54. ieee: T. M. Chan, H.-C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, and D. W. Zheng, “Charting the landscape of diameter computation on geometric intersection graphs in the plane,” in 53rd International Colloquium on Automata, Languages, and Programming, Egham, United Kingdom, 2026, vol. 374. ista: 'Chan TM, Chang H-C, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. 2026. Charting the landscape of diameter computation on geometric intersection graphs in the plane. 53rd International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming vol. 374, 54:1-54:22.' mla: Chan, Timothy M., et al. “Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane.” 53rd International Colloquium on Automata, Languages, and Programming, vol. 374, 54:1-54:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPICS.ICALP.2026.54. short: T.M. Chan, H.-C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D.W. Zheng, in:, 53rd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. conference: end_date: 2026-07-10 location: Egham, United Kingdom name: 'ICALP: Automata, Languages and Programming' start_date: 2026-07-07 corr_author: '1' das_tickbox: '0' date_created: 2026-07-27T05:53:08Z date_published: 2026-07-01T00:00:00Z date_updated: 2026-07-27T06:22:03Z day: '01' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPICS.ICALP.2026.54 external_id: arxiv: - '2605.10692' file: - access_level: open_access checksum: 1e66eba4cfe4e74ab28108b1ca0bb956 content_type: application/pdf creator: dernst date_created: 2026-07-27T06:20:41Z date_updated: 2026-07-27T06:20:41Z file_id: '22407' file_name: 2026_LIPIcSICALP_Chan.pdf file_size: 1440497 relation: main_file success: 1 file_date_updated: 2026-07-27T06:20:41Z has_accepted_license: '1' intvolume: ' 374' keyword: - String graphs - Fine-grained complexity - Theory of computation → Computational geometry language: - iso: eng month: '07' oa: 1 oa_version: Published Version project: - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions publication: 53rd International Colloquium on Automata, Languages, and Programming publication_identifier: eissn: - 1868-8969 - '9783959774284' publication_status: published publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: Charting the landscape of diameter computation on geometric intersection graphs in the plane tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 374 year: '2026' ... --- OA_place: publisher OA_type: gold _id: '22007' abstract: - lang: eng text: "Truncation of cryptographic outputs is a technique that was recently introduced in Baldimtsi et al. [Foteini Baldimtsi et al., 2022]. The general idea is to try out many inputs to some cryptographic algorithm until the output (e.g. a public-key or some hash value) falls into some sparse set and thus can be compressed: by trying out an expected 2^k different inputs one will find an output that starts with k zeros.\r\nUsing such truncation one can for example save substantial gas fees on Blockchains where storing values is very expensive. While [Foteini Baldimtsi et al., 2022] show that truncation preserves the security of the underlying primitive, they only consider a setting without preprocessing. In this work we show that lower bounds on the time-space tradeoff for inverting random functions and permutations also hold with truncation, except for parameters ranges where the bound fails to hold for \"trivial\" reasons.\r\nConcretely, it’s known that any algorithm that inverts a random function or permutation with range N making T queries and using S bits of auxiliary input must satisfy S⋅ T ≥ Nlog N. This lower bound no longer holds in the truncated setting where one must only invert a challenge from a range of size N/2^k, as now one can simply save the replies to all N/2^k challenges, which requires S = log N⋅ N /2^k bits and allows to invert with T = 1 query.\r\nWe show that with truncation, whenever S is somewhat smaller than the log N⋅ N /2^k bits required to store the entire truncated function table, the known S⋅ T ≥ Nlog N lower bound applies." alternative_title: - LIPIcs article_number: 4:1-4:10 article_processing_charge: Yes author: - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 - first_name: Pengxiang full_name: Wang, Pengxiang last_name: Wang citation: ama: 'Pietrzak KZ, Wang P. Time-space tradeoffs of truncation with preprocessing. In: 6th Conference on Information-Theoretic Cryptography. Vol 343. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.ITC.2025.4' apa: 'Pietrzak, K. Z., & Wang, P. (2025). Time-space tradeoffs of truncation with preprocessing. In 6th Conference on Information-Theoretic Cryptography (Vol. 343). Santa Barbara, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITC.2025.4' chicago: Pietrzak, Krzysztof Z, and Pengxiang Wang. “Time-Space Tradeoffs of Truncation with Preprocessing.” In 6th Conference on Information-Theoretic Cryptography, Vol. 343. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.ITC.2025.4. ieee: K. Z. Pietrzak and P. Wang, “Time-space tradeoffs of truncation with preprocessing,” in 6th Conference on Information-Theoretic Cryptography, Santa Barbara, CA, United States, 2025, vol. 343. ista: 'Pietrzak KZ, Wang P. 2025. Time-space tradeoffs of truncation with preprocessing. 6th Conference on Information-Theoretic Cryptography. ITC: Information Theoretic Cryptography, LIPIcs, vol. 343, 4:1-4:10.' mla: Pietrzak, Krzysztof Z., and Pengxiang Wang. “Time-Space Tradeoffs of Truncation with Preprocessing.” 6th Conference on Information-Theoretic Cryptography, vol. 343, 4:1-4:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.ITC.2025.4. short: K.Z. Pietrzak, P. Wang, in:, 6th Conference on Information-Theoretic Cryptography, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. conference: end_date: 2025-08-17 location: Santa Barbara, CA, United States name: 'ITC: Information Theoretic Cryptography' start_date: 2025-08-16 corr_author: '1' cryptoeprintid: 1 das_tickbox: '0' date_created: 2026-06-14T22:01:45Z date_published: 2025-09-08T00:00:00Z date_updated: 2026-06-22T08:57:41Z day: '08' ddc: - '000' department: - _id: KrPi doi: 10.4230/LIPIcs.ITC.2025.4 external_id: cryptoeprintid: - 2025/723 file: - access_level: open_access checksum: 3f791b03df26853342855a9d9581cb58 content_type: application/pdf creator: dernst date_created: 2026-06-22T08:54:32Z date_updated: 2026-06-22T08:54:32Z file_id: '22118' file_name: 2025_LIPIcs_Pietrzak.pdf file_size: 772046 relation: main_file success: 1 file_date_updated: 2026-06-22T08:54:32Z has_accepted_license: '1' intvolume: ' 343' keyword: - Time-Space Lower Bounds - Blockchains language: - iso: eng month: '09' oa: 1 oa_version: Published Version publication: 6th Conference on Information-Theoretic Cryptography publication_identifier: eissn: - 1868-8969 isbn: - '9783959773850' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Time-space tradeoffs of truncation with preprocessing tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 343 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '20005' abstract: - lang: eng text: "We generalize a classical result by Boris Delaunay that introduced Delaunay triangulations. In particular, we prove that for a locally finite and coarsely dense generic point set A in ℝ^d, every generic point of ℝ^d belongs to exactly binom(d+k,d) simplices whose vertices belong to A and whose circumspheres enclose exactly k points of A. We extend this result to the cases in which the points are weighted, and when A contains only finitely many points in ℝ^d or in \U0001D54A^d. Furthermore, we use the result to give a new geometric proof for the fact that volumes of hypersimplices are Eulerian numbers." acknowledgement: "Herbert Edelsbrunner: partially supported by the Wittgenstein Prize, Austrian Science\r\nFund (FWF), grant no. Z 342-N31, and by the DFG Collaborative Research Center TRR 109,\r\nAustrian Science Fund (FWF), grant no. I 02979-N35.\r\nAlexey Garber: partially supported by the Simons Foundation.\r\nMorteza Saghafian: partially supported by the Wittgenstein Prize, Austrian Science Fund (FWF),\r\ngrant no. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian Science\r\nFund (FWF), grant no. I 02979-N35" alternative_title: - LIPIcs article_number: '43' article_processing_charge: Yes arxiv: 1 author: - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Alexey full_name: Garber, Alexey last_name: Garber - first_name: Morteza full_name: Saghafian, Morteza id: f86f7148-b140-11ec-9577-95435b8df824 last_name: Saghafian citation: ama: 'Edelsbrunner H, Garber A, Saghafian M. On spheres with k points inside. In: 41st International Symposium on Computational Geometry. Vol 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.SoCG.2025.43' apa: 'Edelsbrunner, H., Garber, A., & Saghafian, M. (2025). On spheres with k points inside. In 41st International Symposium on Computational Geometry (Vol. 332). Kanazawa, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2025.43' chicago: Edelsbrunner, Herbert, Alexey Garber, and Morteza Saghafian. “On Spheres with k Points Inside.” In 41st International Symposium on Computational Geometry, Vol. 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.SoCG.2025.43. ieee: H. Edelsbrunner, A. Garber, and M. Saghafian, “On spheres with k points inside,” in 41st International Symposium on Computational Geometry, Kanazawa, Japan, 2025, vol. 332. ista: 'Edelsbrunner H, Garber A, Saghafian M. 2025. On spheres with k points inside. 41st International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 332, 43.' mla: Edelsbrunner, Herbert, et al. “On Spheres with k Points Inside.” 41st International Symposium on Computational Geometry, vol. 332, 43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.SoCG.2025.43. short: H. Edelsbrunner, A. Garber, M. Saghafian, in:, 41st International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. conference: end_date: 2025-06-27 location: Kanazawa, Japan name: 'SoCG: Symposium on Computational Geometry' start_date: 2025-06-23 corr_author: '1' date_created: 2025-07-13T22:01:22Z date_published: 2025-06-20T00:00:00Z date_updated: 2025-07-14T07:26:14Z day: '20' ddc: - '510' department: - _id: HeEd doi: 10.4230/LIPIcs.SoCG.2025.43 external_id: arxiv: - '2410.21204' file: - access_level: open_access checksum: b5313ed8575ea87913c71a6e3c7513c8 content_type: application/pdf creator: dernst date_created: 2025-07-14T07:24:22Z date_updated: 2025-07-14T07:24:22Z file_id: '20016' file_name: 2025_LIPIcs.SoCG_Edelsbrunner.pdf file_size: 661893 relation: main_file success: 1 file_date_updated: 2025-07-14T07:24:22Z has_accepted_license: '1' intvolume: ' 332' language: - iso: eng month: '06' oa: 1 oa_version: Published Version project: - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication: 41st International Symposium on Computational Geometry publication_identifier: eissn: - 1868-8969 isbn: - '9783959773706' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: On spheres with k points inside tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 332 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '20006' abstract: - lang: eng text: In numerous fields, dynamic time series data require continuous updates, necessitating efficient data processing techniques for accurate analysis. This paper examines the banana tree data structure, specifically designed to efficiently maintain the multi-scale topological descriptor commonly known as persistent homology for dynamically changing time series data. We implement this data structure and conduct an experimental study to assess its properties and runtime for update operations. Our findings indicate that banana trees are highly effective with unbiased random data, outperforming state-of-the-art static algorithms in these scenarios. Additionally, our results show that real-world time series share structural properties with unbiased random walks, suggesting potential practical utility for our implementation. acknowledgement: "Lara Ost: Supported by the Vienna Graduate School on Computational Optimization\r\n(VGSCO), FWF project no. W1260-N35.\r\nSebastiano Cultrera di Montesano: Supported by the Eric and Wendy Schmidt Center at the Broad Institute of MIT and Harvard.\r\nHerbert Edelsbrunner: Partially supported by the Wittgenstein Prize, FWF grant no. Z 342-N31,\r\nand by the DFG Collaborative Research Center TRR 109, FWF grant no. I 02979-N35." alternative_title: - LIPIcs article_number: '71' article_processing_charge: Yes arxiv: 1 author: - first_name: Lara full_name: Ost, Lara last_name: Ost - first_name: Sebastiano full_name: Cultrera di Montesano, Sebastiano id: 34D2A09C-F248-11E8-B48F-1D18A9856A87 last_name: Cultrera di Montesano orcid: 0000-0001-6249-0832 - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 citation: ama: 'Ost L, Cultrera di Montesano S, Edelsbrunner H. Banana trees for the persistence in time series experimentally. In: 41st International Symposium on Computational Geometry. Vol 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.SoCG.2025.71' apa: 'Ost, L., Cultrera di Montesano, S., & Edelsbrunner, H. (2025). Banana trees for the persistence in time series experimentally. In 41st International Symposium on Computational Geometry (Vol. 332). Kanazawa, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2025.71' chicago: Ost, Lara, Sebastiano Cultrera di Montesano, and Herbert Edelsbrunner. “Banana Trees for the Persistence in Time Series Experimentally.” In 41st International Symposium on Computational Geometry, Vol. 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.SoCG.2025.71. ieee: L. Ost, S. Cultrera di Montesano, and H. Edelsbrunner, “Banana trees for the persistence in time series experimentally,” in 41st International Symposium on Computational Geometry, Kanazawa, Japan, 2025, vol. 332. ista: 'Ost L, Cultrera di Montesano S, Edelsbrunner H. 2025. Banana trees for the persistence in time series experimentally. 41st International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 332, 71.' mla: Ost, Lara, et al. “Banana Trees for the Persistence in Time Series Experimentally.” 41st International Symposium on Computational Geometry, vol. 332, 71, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.SoCG.2025.71. short: L. Ost, S. Cultrera di Montesano, H. Edelsbrunner, in:, 41st International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. conference: end_date: 2025-06-27 location: Kanazawa, Japan name: 'SoCG: Symposium on Computational Geometry' start_date: 2025-06-23 corr_author: '1' date_created: 2025-07-13T22:01:22Z date_published: 2025-06-20T00:00:00Z date_updated: 2025-12-30T11:04:33Z day: '20' ddc: - '000' department: - _id: HeEd doi: 10.4230/LIPIcs.SoCG.2025.71 external_id: arxiv: - '2405.17920' file: - access_level: open_access checksum: 3a4a7a707a56e0cfdf51428782dee55a content_type: application/pdf creator: dernst date_created: 2025-07-14T08:23:38Z date_updated: 2025-07-14T08:23:38Z file_id: '20017' file_name: 2025_LIPIcs.SoCG_Ost.pdf file_size: 834623 relation: main_file success: 1 file_date_updated: 2025-07-14T08:23:38Z has_accepted_license: '1' intvolume: ' 332' language: - iso: eng month: '06' oa: 1 oa_version: Published Version project: - _id: 9B9290DE-BA93-11EA-9121-9846C619BF3A grant_number: W1260-N35 name: Vienna Graduate School on Computational Optimization - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science publication: 41st International Symposium on Computational Geometry publication_identifier: eissn: - 1868-8969 isbn: - '9783959773706' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: link: - relation: software url: https://github.com/laraost/BananaPersist scopus_import: '1' status: public title: Banana trees for the persistence in time series experimentally tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 332 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '20004' abstract: - lang: eng text: "A long-standing conjecture of Eckhoff, Linhart, and Welzl, which would generalize McMullen’s Upper Bound Theorem for polytopes and refine asymptotic bounds due to Clarkson, asserts that for k ⩽ ⌊(n-d-2)/2⌋, the complexity of the (⩽ k)-level in a simple arrangement of n hemispheres in S^d is maximized for arrangements that are polar duals of neighborly d-polytopes. We prove this conjecture in the case n = d+4. By Gale duality, this implies the following result about crossing numbers: In every spherical arc drawing of K_n in S² (given by a set V ⊂ S² of n unit vectors connected by spherical arcs), the number of crossings is at least 1/4 ⌊n/2⌋ ⌊(n-1)/2⌋ ⌊(n-2)/2⌋ ⌊(n-3)/2⌋. This lower bound is attained if every open linear halfspace contains at least ⌊(n-2)/2⌋ of the vectors in V.\r\nMoreover, we determine the space of all linear and affine relations that hold between the face numbers of levels in simple arrangements of n hemispheres in S^d. This completes a long line of research on such relations, answers a question posed by Andrzejak and Welzl in 2003, and generalizes the classical fact that the Dehn-Sommerville relations generate all linear relations between the face numbers of simple polytopes (which correspond to the 0-level).\r\nTo prove these results, we introduce the notion of the g-matrix, which encodes the face numbers of levels in an arrangement and generalizes the classical g-vector of a polytope." alternative_title: - LIPIcs article_number: '75' article_processing_charge: Yes arxiv: 1 author: - first_name: Elizaveta full_name: Streltsova, Elizaveta id: 57a170da-dc96-11ea-b7c8-ab3565071bf7 last_name: Streltsova - first_name: Uli full_name: Wagner, Uli id: 36690CA2-F248-11E8-B48F-1D18A9856A87 last_name: Wagner orcid: 0000-0002-1494-0568 citation: ama: 'Streltsova E, Wagner U. Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers. In: 41st International Symposium on Computational Geometry. Vol 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.SoCG.2025.75' apa: 'Streltsova, E., & Wagner, U. (2025). Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers. In 41st International Symposium on Computational Geometry (Vol. 332). Kanazawa, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2025.75' chicago: 'Streltsova, Elizaveta, and Uli Wagner. “Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers.” In 41st International Symposium on Computational Geometry, Vol. 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.SoCG.2025.75.' ieee: 'E. Streltsova and U. Wagner, “Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers,” in 41st International Symposium on Computational Geometry, Kanazawa, Japan, 2025, vol. 332.' ista: 'Streltsova E, Wagner U. 2025. Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers. 41st International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 332, 75.' mla: 'Streltsova, Elizaveta, and Uli Wagner. “Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers.” 41st International Symposium on Computational Geometry, vol. 332, 75, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.SoCG.2025.75.' short: E. Streltsova, U. Wagner, in:, 41st International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. conference: end_date: 2025-06-27 location: Kanazawa, Japan name: 'SoCG: Symposium on Computational Geometry' start_date: 2025-06-23 corr_author: '1' das_tickbox: '1' date_created: 2025-07-13T22:01:22Z date_published: 2025-06-20T00:00:00Z date_updated: 2026-07-07T13:03:16Z day: '20' ddc: - '510' department: - _id: UlWa doi: 10.4230/LIPIcs.SoCG.2025.75 external_id: arxiv: - '2504.07752' - '2504.07770' file: - access_level: open_access checksum: a8f7feb1aa3b896e31195841a989d622 content_type: application/pdf creator: dernst date_created: 2025-07-14T07:11:04Z date_updated: 2025-07-14T07:11:04Z file_id: '20015' file_name: 2025_LIPIcs.SoCG_Streltsova.pdf file_size: 952807 relation: main_file success: 1 file_date_updated: 2025-07-14T07:11:04Z has_accepted_license: '1' intvolume: ' 332' language: - iso: eng month: '06' oa: 1 oa_version: Published Version publication: 41st International Symposium on Computational Geometry publication_identifier: eissn: - 1868-8969 isbn: - '9783959773706' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: 'Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 332 year: '2025' ... --- _id: '17170' abstract: - lang: eng text: "In this article we extend and strengthen the seminal work by Niyogi, Smale, and Weinberger on the learning of the homotopy type from a sample of an underlying space. In their work, Niyogi, Smale, and Weinberger studied samples of C² manifolds with positive reach embedded in ℝ^d. We extend their results in the following ways: - As the ambient space we consider both ℝ^d and Riemannian manifolds with lower bounded sectional curvature. - In both types of ambient spaces, we study sets of positive reach - a significantly more general setting than C² manifolds - as well as general manifolds of positive reach. - The sample P of a set (or a manifold) \U0001D4AE of positive reach may be noisy. We work with two one-sided Hausdorff distances - ε and δ - between P and \U0001D4AE. We provide tight bounds in terms of ε and δ, that guarantee that there exists a parameter r such that the union of balls of radius r centred at the sample P deformation-retracts to \U0001D4AE. We exhibit their tightness by an explicit construction. We carefully distinguish the roles of δ and ε. This is not only essential to achieve tight bounds, but also sensible in practical situations, since it allows one to adapt the bound according to sample density and the amount of noise present in the sample separately." acknowledgement: "This research has been supported by the European Research Council (ERC), grant No. 788183, by the Wittgenstein Prize, Austrian Science Fund (FWF), grant No. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian Science Fund (FWF), grant No. I 02979-N35.\r\nWintraecken, Mathijs: Supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411, the Austrian science fund (FWF) grant No. M-3073, and the welcome package from IDEX of the Université Côte d'Azur." alternative_title: - LIPIcs article_processing_charge: No arxiv: 1 author: - first_name: Dominique full_name: Attali, Dominique last_name: Attali - first_name: Hana full_name: Kourimska, Hana id: D9B8E14C-3C26-11EA-98F5-1F833DDC885E last_name: Kourimska orcid: 0000-0001-7841-0091 - first_name: Christopher D full_name: Fillmore, Christopher D id: 35638A5C-AAC7-11E9-B0BF-5503E6697425 last_name: Fillmore - first_name: Ishika full_name: Ghosh, Ishika id: ee449b28-344d-11ef-a6d5-9ca430e9e9ff last_name: Ghosh - first_name: André full_name: Lieutier, André last_name: Lieutier - first_name: Elizabeth R full_name: Stephenson, Elizabeth R id: 2D04F932-F248-11E8-B48F-1D18A9856A87 last_name: Stephenson orcid: 0000-0002-6862-208X - first_name: Mathijs full_name: Wintraecken, Mathijs id: 307CFBC8-F248-11E8-B48F-1D18A9856A87 last_name: Wintraecken orcid: 0000-0002-7472-2220 citation: ama: 'Attali D, Kourimska H, Fillmore CD, et al. Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds. In: 40th International Symposium on Computational Geometry. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:11:1-11:19. doi:10.4230/LIPIcs.SoCG.2024.11' apa: 'Attali, D., Kourimska, H., Fillmore, C. D., Ghosh, I., Lieutier, A., Stephenson, E. R., & Wintraecken, M. (2024). Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds. In 40th International Symposium on Computational Geometry (Vol. 293, p. 11:1-11:19). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.11' chicago: Attali, Dominique, Hana Kourimska, Christopher D Fillmore, Ishika Ghosh, André Lieutier, Elizabeth R Stephenson, and Mathijs Wintraecken. “Tight Bounds for the Learning of Homotopy à La Niyogi, Smale, and Weinberger for Subsets of Euclidean Spaces and of Riemannian Manifolds.” In 40th International Symposium on Computational Geometry, 293:11:1-11:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.11. ieee: D. Attali et al., “Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds,” in 40th International Symposium on Computational Geometry, Athens, Greece, 2024, vol. 293, p. 11:1-11:19. ista: 'Attali D, Kourimska H, Fillmore CD, Ghosh I, Lieutier A, Stephenson ER, Wintraecken M. 2024. Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 293, 11:1-11:19.' mla: Attali, Dominique, et al. “Tight Bounds for the Learning of Homotopy à La Niyogi, Smale, and Weinberger for Subsets of Euclidean Spaces and of Riemannian Manifolds.” 40th International Symposium on Computational Geometry, vol. 293, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 11:1-11:19, doi:10.4230/LIPIcs.SoCG.2024.11. short: D. Attali, H. Kourimska, C.D. Fillmore, I. Ghosh, A. Lieutier, E.R. Stephenson, M. Wintraecken, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 11:1-11:19. conference: end_date: 2024-06-14 location: Athens, Greece name: 'SoCG: Symposium on Computational Geometry' start_date: 2024-06-11 date_created: 2024-06-25T11:45:58Z date_published: 2024-06-06T00:00:00Z date_updated: 2025-04-15T07:16:57Z day: '06' ddc: - '516' department: - _id: GradSch - _id: HeEd doi: 10.4230/LIPIcs.SoCG.2024.11 ec_funded: 1 external_id: arxiv: - '2206.10485' file: - access_level: open_access checksum: 6a2ddc8b51aa58f197a8b294750f1f8d content_type: application/pdf creator: cfillmor date_created: 2024-06-25T11:47:26Z date_updated: 2024-06-25T11:47:26Z file_id: '17171' file_name: LIPIcs.SoCG.2024.11.pdf file_size: 20886142 relation: main_file success: 1 file_date_updated: 2024-06-25T11:47:26Z has_accepted_license: '1' intvolume: ' 293' language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: 11:1-11:19 project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes - _id: fc390959-9c52-11eb-aca3-afa58bd282b2 grant_number: M03073 name: Learning and triangulating manifolds via collapses publication: 40th International Symposium on Computational Geometry publication_identifier: eissn: - 1868-8969 isbn: - '9783959773164' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 293 year: '2024' ... --- OA_place: publisher OA_type: gold _id: '18928' abstract: - lang: eng text: "Algorithms with predictions is a new research direction that leverages machine learned predictions for algorithm design. So far a plethora of recent works have incorporated predictions to improve on worst-case bounds for online problems. In this paper, we initiate the study of complexity of dynamic data structures with predictions, including dynamic graph algorithms. Unlike online algorithms, the goal in dynamic data structures is to maintain the solution efficiently with every update.\r\nWe investigate three natural models of prediction: (1) δ-accurate predictions where each predicted request matches the true request with probability δ, (2) list-accurate predictions where a true request comes from a list of possible requests, and (3) bounded delay predictions where the true requests are a permutation of the predicted requests. We give general reductions among the prediction models, showing that bounded delay is the strongest prediction model, followed by list-accurate, and δ-accurate.\r\nFurther, we identify two broad problem classes based on lower bounds due to the Online Matrix Vector (OMv) conjecture. Specifically, we show that locally correctable dynamic problems have strong conditional lower bounds for list-accurate predictions that are equivalent to the non-prediction setting, unless list-accurate predictions are perfect. Moreover, we show that locally reducible dynamic problems have time complexity that degrades gracefully with the quality of bounded delay predictions. We categorize problems with known OMv lower bounds accordingly and give several upper bounds in the delay model that show that our lower bounds are almost tight.\r\nWe note that concurrent work by v.d.Brand et al. [SODA '24] and Liu and Srinivas [arXiv:2307.08890] independently study dynamic graph algorithms with predictions, but their work is mostly focused on showing upper bounds." acknowledgement: "Henzinger, Monika: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) project Z 422-N, project I 5982-N, and project P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020-2024.\r\nSaha, Barna: This project is partially supported by NSF grants 1652303, 1909046, 2112533, and HDR TRIPODS Phase II grant 2217058.\r\nWe would like to thank Andrea Lincoln for many helpful discussions and insightful comments." alternative_title: - LIPIcs article_processing_charge: Yes arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Barna full_name: Saha, Barna last_name: Saha - first_name: Martin P. full_name: Seybold, Martin P. last_name: Seybold - first_name: Christopher full_name: Ye, Christopher last_name: Ye citation: ama: 'Henzinger M, Saha B, Seybold MP, Ye C. On the complexity of algorithms with predictions for dynamic graph problems. In: 15th Innovations in Theoretical Computer Science Conference. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:62:1-62:25. doi:10.4230/LIPIcs.ITCS.2024.62' apa: 'Henzinger, M., Saha, B., Seybold, M. P., & Ye, C. (2024). On the complexity of algorithms with predictions for dynamic graph problems. In 15th Innovations in Theoretical Computer Science Conference (Vol. 287, p. 62:1-62:25). Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITCS.2024.62' chicago: Henzinger, Monika, Barna Saha, Martin P. Seybold, and Christopher Ye. “On the Complexity of Algorithms with Predictions for Dynamic Graph Problems.” In 15th Innovations in Theoretical Computer Science Conference, 287:62:1-62:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ITCS.2024.62. ieee: M. Henzinger, B. Saha, M. P. Seybold, and C. Ye, “On the complexity of algorithms with predictions for dynamic graph problems,” in 15th Innovations in Theoretical Computer Science Conference, Berkeley, CA, United States, 2024, vol. 287, p. 62:1-62:25. ista: 'Henzinger M, Saha B, Seybold MP, Ye C. 2024. On the complexity of algorithms with predictions for dynamic graph problems. 15th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 287, 62:1-62:25.' mla: Henzinger, Monika, et al. “On the Complexity of Algorithms with Predictions for Dynamic Graph Problems.” 15th Innovations in Theoretical Computer Science Conference, vol. 287, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 62:1-62:25, doi:10.4230/LIPIcs.ITCS.2024.62. short: M. Henzinger, B. Saha, M.P. Seybold, C. Ye, in:, 15th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 62:1-62:25. conference: end_date: 2024-02-02 location: Berkeley, CA, United States name: 'ITCS: Innovations in Theoretical Computer Science' start_date: 2024-01-30 corr_author: '1' date_created: 2025-01-27T15:33:42Z date_published: 2024-01-24T00:00:00Z date_updated: 2025-09-09T12:11:33Z day: '24' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.ITCS.2024.62 ec_funded: 1 external_id: arxiv: - '2307.16771' isi: - '001300389400062' file: - access_level: open_access checksum: 15085a5b3697a408b92a4a7a27293927 content_type: application/pdf creator: dernst date_created: 2025-01-27T15:33:24Z date_updated: 2025-01-27T15:33:24Z file_id: '18929' file_name: 2024_LIPICs_HenzingerMo.pdf file_size: 1084372 relation: main_file success: 1 file_date_updated: 2025-01-27T15:33:24Z has_accepted_license: '1' intvolume: ' 287' isi: 1 language: - iso: eng month: '01' oa: 1 oa_version: Published Version page: 62:1-62:25 project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _id: 34def286-11ca-11ed-8bc3-da5948e1613c grant_number: Z00422 name: Efficient algorithms - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer publication: 15th Innovations in Theoretical Computer Science Conference publication_identifier: eissn: - 1868-8969 isbn: - '9783959773096' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: On the complexity of algorithms with predictions for dynamic graph problems tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 volume: 287 year: '2024' ... --- _id: '15168' abstract: - lang: eng text: 'A linearly ordered (LO) k-colouring of a hypergraph is a colouring of its vertices with colours 1, … , k such that each edge contains a unique maximal colour. Deciding whether an input hypergraph admits LO k-colouring with a fixed number of colours is NP-complete (and in the special case of graphs, LO colouring coincides with the usual graph colouring). Here, we investigate the complexity of approximating the "linearly ordered chromatic number" of a hypergraph. We prove that the following promise problem is NP-complete: Given a 3-uniform hypergraph, distinguish between the case that it is LO 3-colourable, and the case that it is not even LO 4-colourable. We prove this result by a combination of algebraic, topological, and combinatorial methods, building on and extending a topological approach for studying approximate graph colouring introduced by Krokhin, Opršal, Wrochna, and Živný (2023).' acknowledgement: "Marek Filakovský: This research was supported by Charles University (project PRIMUS/\r\n21/SCI/014), the Austrian Science Fund (FWF project P31312-N35), and MSCAfellow5_MUNI\r\n(CZ.02.01.01/00/22_010/0003229). Tamio-Vesa Nakajima: This research was funded by UKRI EP/X024431/1 and by a Clarendon Fund Scholarship. All data is provided in full in the results section of this paper. Jakub Opršal: 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. Uli Wagner: This research was supported by the Austrian Science Fund (FWF project P31312-N35)." alternative_title: - LIPIcs article_number: '34' article_processing_charge: No arxiv: 1 author: - first_name: Marek full_name: Filakovský, Marek id: 3E8AF77E-F248-11E8-B48F-1D18A9856A87 last_name: Filakovský - first_name: Tamio Vesa full_name: Nakajima, Tamio Vesa last_name: Nakajima - first_name: Jakub full_name: Opršal, Jakub id: ec596741-c539-11ec-b829-c79322a91242 last_name: Opršal orcid: 0000-0003-1245-3456 - first_name: Gianluca full_name: Tasinato, Gianluca id: 0433290C-AF8F-11E9-A4C7-F729E6697425 last_name: Tasinato - first_name: Uli full_name: Wagner, Uli id: 36690CA2-F248-11E8-B48F-1D18A9856A87 last_name: Wagner orcid: 0000-0002-1494-0568 citation: ama: 'Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In: 41st International Symposium on Theoretical Aspects of Computer Science. Vol 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.STACS.2024.34' apa: 'Filakovský, M., Nakajima, T. V., Opršal, J., Tasinato, G., & Wagner, U. (2024). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In 41st International Symposium on Theoretical Aspects of Computer Science (Vol. 289). Clermont-Ferrand, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2024.34' chicago: Filakovský, Marek, Tamio Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” In 41st International Symposium on Theoretical Aspects of Computer Science, Vol. 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.STACS.2024.34. ieee: M. Filakovský, T. V. Nakajima, J. Opršal, G. Tasinato, and U. Wagner, “Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs,” in 41st International Symposium on Theoretical Aspects of Computer Science, Clermont-Ferrand, France, 2024, vol. 289. ista: 'Filakovský M, Nakajima TV, Opršal J, Tasinato G, Wagner U. 2024. Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. 41st International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 289, 34.' mla: Filakovský, Marek, et al. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” 41st International Symposium on Theoretical Aspects of Computer Science, vol. 289, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.STACS.2024.34. short: M. Filakovský, T.V. Nakajima, J. Opršal, G. Tasinato, U. Wagner, in:, 41st International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. conference: end_date: 2024-03-14 location: Clermont-Ferrand, France name: 'STACS: Symposium on Theoretical Aspects of Computer Science' start_date: 2024-03-12 corr_author: '1' date_created: 2024-03-24T23:00:59Z date_published: 2024-03-01T00:00:00Z date_updated: 2026-07-29T13:13:17Z day: '01' ddc: - '510' department: - _id: UlWa doi: 10.4230/LIPIcs.STACS.2024.34 ec_funded: 1 external_id: arxiv: - '2312.12981' isi: - '001300393400034' file: - access_level: open_access checksum: 0524d4189fd1ed08989546511343edf3 content_type: application/pdf creator: dernst date_created: 2024-03-25T07:44:30Z date_updated: 2024-03-25T07:44:30Z file_id: '15175' file_name: 2024_LIPICs_Filakovsky.pdf file_size: 927290 relation: main_file success: 1 file_date_updated: 2024-03-25T07:44:30Z has_accepted_license: '1' intvolume: ' 289' isi: 1 language: - iso: eng month: '03' oa: 1 oa_version: Published Version project: - _id: 26611F5C-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P31312 name: Algorithms for Embeddings and Homotopy Theory - _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c call_identifier: H2020 grant_number: '101034413' name: 'IST-BRIDGE: International postdoctoral program' publication: 41st International Symposium on Theoretical Aspects of Computer Science publication_identifier: eissn: - 1868-8969 isbn: - '9783959773119' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: record: - id: '22247' relation: later_version status: public - id: '20339' relation: dissertation_contains status: public scopus_import: '1' status: public title: Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 volume: 289 year: '2024' ... --- _id: '13292' abstract: - lang: eng text: The operator precedence languages (OPLs) represent the largest known subclass of the context-free languages which enjoys all desirable closure and decidability properties. This includes the decidability of language inclusion, which is the ultimate verification problem. Operator precedence grammars, automata, and logics have been investigated and used, for example, to verify programs with arithmetic expressions and exceptions (both of which are deterministic pushdown but lie outside the scope of the visibly pushdown languages). In this paper, we complete the picture and give, for the first time, an algebraic characterization of the class of OPLs in the form of a syntactic congruence that has finitely many equivalence classes exactly for the operator precedence languages. This is a generalization of the celebrated Myhill-Nerode theorem for the regular languages to OPLs. As one of the consequences, we show that universality and language inclusion for nondeterministic operator precedence automata can be solved by an antichain algorithm. Antichain algorithms avoid determinization and complementation through an explicit subset construction, by leveraging a quasi-order on words, which allows the pruning of the search space for counterexample words without sacrificing completeness. Antichain algorithms can be implemented symbolically, and these implementations are today the best-performing algorithms in practice for the inclusion of finite automata. We give a generic construction of the quasi-order needed for antichain algorithms from a finite syntactic congruence. This yields the first antichain algorithm for OPLs, an algorithm that solves the ExpTime-hard language inclusion problem for OPLs in exponential time. acknowledgement: "This work was supported in part by the ERC-2020-AdG 101020093.\r\nWe thank Pierre Ganty for early discussions and the anonymous reviewers for their helpful comments.\r\n" alternative_title: - LIPIcs article_processing_charge: Yes arxiv: 1 author: - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000-0002-2985-7724 - first_name: Pavol full_name: Kebis, Pavol last_name: Kebis - first_name: Nicolas Adrien full_name: Mazzocchi, Nicolas Adrien id: b26baa86-3308-11ec-87b0-8990f34baa85 last_name: Mazzocchi - first_name: Naci E full_name: Sarac, Naci E id: 8C6B42F8-C8E6-11E9-A03A-F2DCE5697425 last_name: Sarac citation: ama: 'Henzinger TA, Kebis P, Mazzocchi NA, Sarac NE. Regular methods for operator precedence languages. In: 50th International Colloquium on Automata, Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023:129:1--129:20. doi:10.4230/LIPIcs.ICALP.2023.129' apa: 'Henzinger, T. A., Kebis, P., Mazzocchi, N. A., & Sarac, N. E. (2023). Regular methods for operator precedence languages. In 50th International Colloquium on Automata, Languages, and Programming (Vol. 261, p. 129:1--129:20). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.129' chicago: Henzinger, Thomas A, Pavol Kebis, Nicolas Adrien Mazzocchi, and Naci E Sarac. “Regular Methods for Operator Precedence Languages.” In 50th International Colloquium on Automata, Languages, and Programming, 261:129:1--129:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.129. ieee: T. A. Henzinger, P. Kebis, N. A. Mazzocchi, and N. E. Sarac, “Regular methods for operator precedence languages,” in 50th International Colloquium on Automata, Languages, and Programming, Paderborn, Germany, 2023, vol. 261, p. 129:1--129:20. ista: 'Henzinger TA, Kebis P, Mazzocchi NA, Sarac NE. 2023. Regular methods for operator precedence languages. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 129:1--129:20.' mla: Henzinger, Thomas A., et al. “Regular Methods for Operator Precedence Languages.” 50th International Colloquium on Automata, Languages, and Programming, vol. 261, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, p. 129:1--129:20, doi:10.4230/LIPIcs.ICALP.2023.129. short: T.A. Henzinger, P. Kebis, N.A. Mazzocchi, N.E. Sarac, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, p. 129:1--129:20. conference: end_date: 2023-07-14 location: Paderborn, Germany name: 'ICALP: Automata, Languages and Programming' start_date: 2023-07-10 corr_author: '1' date_created: 2023-07-24T15:11:41Z date_published: 2023-07-05T00:00:00Z date_updated: 2025-07-10T11:50:41Z day: '05' ddc: - '000' department: - _id: GradSch - _id: ToHe doi: 10.4230/LIPIcs.ICALP.2023.129 ec_funded: 1 external_id: arxiv: - '2305.03447' file: - access_level: open_access checksum: 5d4c8932ef3450615a53b9bb15d92eb2 content_type: application/pdf creator: esarac date_created: 2023-07-24T15:11:05Z date_updated: 2023-07-24T15:11:05Z file_id: '13293' file_name: icalp23.pdf file_size: 859379 relation: main_file success: 1 file_date_updated: 2023-07-24T15:11:05Z has_accepted_license: '1' intvolume: ' 261' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: 129:1--129:20 project: - _id: 62781420-2b32-11ec-9570-8d9b63373d4d call_identifier: H2020 grant_number: '101020093' name: Vigilant Algorithmic Monitoring of Software publication: 50th International Colloquium on Automata, Languages, and Programming publication_identifier: eissn: - 1868-8969 isbn: - '9783959772785' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Regular methods for operator precedence languages tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 261 year: '2023' ... --- _id: '14417' abstract: - lang: eng text: Entropic risk (ERisk) is an established risk measure in finance, quantifying risk by an exponential re-weighting of rewards. We study ERisk for the first time in the context of turn-based stochastic games with the total reward objective. This gives rise to an objective function that demands the control of systems in a risk-averse manner. We show that the resulting games are determined and, in particular, admit optimal memoryless deterministic strategies. This contrasts risk measures that previously have been considered in the special case of Markov decision processes and that require randomization and/or memory. We provide several results on the decidability and the computational complexity of the threshold problem, i.e. whether the optimal value of ERisk exceeds a given threshold. In the most general case, the problem is decidable subject to Shanuel’s conjecture. If all inputs are rational, the resulting threshold problem can be solved using algebraic numbers, leading to decidability via a polynomial-time reduction to the existential theory of the reals. Further restrictions on the encoding of the input allow the solution of the threshold problem in NP∩coNP. Finally, an approximation algorithm for the optimal value of ERisk is provided. acknowledgement: "This work was partly funded by the ERC CoG 863818 (ForM-SMArt), the DFG Grant\r\n389792660 as part of TRR 248 (Foundations of Perspicuous Software Systems), the Cluster of\r\nExcellence EXC 2050/1 (CeTI, project ID 390696704, as part of Germany’s Excellence Strategy), and the DFG projects BA-1679/11-1 and BA-1679/12-1." alternative_title: - LIPIcs article_number: '15' article_processing_charge: Yes arxiv: 1 author: - first_name: Christel full_name: Baier, Christel last_name: Baier - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Tobias full_name: Meggendorfer, Tobias id: b21b0c15-30a2-11eb-80dc-f13ca25802e1 last_name: Meggendorfer orcid: 0000-0002-1712-2165 - first_name: Jakob full_name: Piribauer, Jakob last_name: Piribauer citation: ama: 'Baier C, Chatterjee K, Meggendorfer T, Piribauer J. Entropic risk for turn-based stochastic games. In: 48th International Symposium on Mathematical Foundations of Computer Science. Vol 272. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.MFCS.2023.15' apa: 'Baier, C., Chatterjee, K., Meggendorfer, T., & Piribauer, J. (2023). Entropic risk for turn-based stochastic games. In 48th International Symposium on Mathematical Foundations of Computer Science (Vol. 272). Bordeaux, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2023.15' chicago: Baier, Christel, Krishnendu Chatterjee, Tobias Meggendorfer, and Jakob Piribauer. “Entropic Risk for Turn-Based Stochastic Games.” In 48th International Symposium on Mathematical Foundations of Computer Science, Vol. 272. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.MFCS.2023.15. ieee: C. Baier, K. Chatterjee, T. Meggendorfer, and J. Piribauer, “Entropic risk for turn-based stochastic games,” in 48th International Symposium on Mathematical Foundations of Computer Science, Bordeaux, France, 2023, vol. 272. ista: 'Baier C, Chatterjee K, Meggendorfer T, Piribauer J. 2023. Entropic risk for turn-based stochastic games. 48th International Symposium on Mathematical Foundations of Computer Science. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 272, 15.' mla: Baier, Christel, et al. “Entropic Risk for Turn-Based Stochastic Games.” 48th International Symposium on Mathematical Foundations of Computer Science, vol. 272, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.MFCS.2023.15. short: C. Baier, K. Chatterjee, T. Meggendorfer, J. Piribauer, in:, 48th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. conference: end_date: 2023-09-01 location: Bordeaux, France name: 'MFCS: Mathematical Foundations of Computer Science' start_date: 2023-08-28 corr_author: '1' date_created: 2023-10-09T09:21:05Z date_published: 2023-08-21T00:00:00Z date_updated: 2025-09-08T09:10:05Z day: '21' ddc: - '000' department: - _id: KrCh doi: 10.4230/LIPIcs.MFCS.2023.15 ec_funded: 1 external_id: arxiv: - '2307.06611' file: - access_level: open_access checksum: 402281b17ed669bbf149d0fdf68ac201 content_type: application/pdf creator: dernst date_created: 2023-10-09T09:19:11Z date_updated: 2023-10-09T09:19:11Z file_id: '14418' file_name: 2023_LIPIcsMFCS_Baier.pdf file_size: 826843 relation: main_file success: 1 file_date_updated: 2023-10-09T09:19:11Z has_accepted_license: '1' intvolume: ' 272' language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: 0599E47C-7A3F-11EA-A408-12923DDC885E call_identifier: H2020 grant_number: '863818' name: 'Formal Methods for Stochastic Models: Algorithms and Applications' publication: 48th International Symposium on Mathematical Foundations of Computer Science publication_identifier: eissn: - 1868-8969 isbn: - '9783959772921' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: record: - id: '17474' relation: later_version status: public scopus_import: '1' status: public title: Entropic risk for turn-based stochastic games tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 272 year: '2023' ... --- _id: '13221' abstract: - lang: eng text: The safety-liveness dichotomy is a fundamental concept in formal languages which plays a key role in verification. Recently, this dichotomy has been lifted to quantitative properties, which are arbitrary functions from infinite words to partially-ordered domains. We look into harnessing the dichotomy for the specific classes of quantitative properties expressed by quantitative automata. These automata contain finitely many states and rational-valued transition weights, and their common value functions Inf, Sup, LimInf, LimSup, LimInfAvg, LimSupAvg, and DSum map infinite words into the totallyordered domain of real numbers. In this automata-theoretic setting, we establish a connection between quantitative safety and topological continuity and provide an alternative characterization of quantitative safety and liveness in terms of their boolean counterparts. For all common value functions, we show how the safety closure of a quantitative automaton can be constructed in PTime, and we provide PSpace-complete checks of whether a given quantitative automaton is safe or live, with the exception of LimInfAvg and LimSupAvg automata, for which the safety check is in ExpSpace. Moreover, for deterministic Sup, LimInf, and LimSup automata, we give PTime decompositions into safe and live automata. These decompositions enable the separation of techniques for safety and liveness verification for quantitative specifications. acknowledgement: We thank Christof Löding for pointing us to some results on PSpace-hardess of universality problems and the anonymous reviewers for their helpful comments. This work was supported in part by the ERC-2020-AdG 101020093 and the Israel Science Foundation grant 2410/22. alternative_title: - LIPIcs article_number: '17' article_processing_charge: No arxiv: 1 author: - first_name: Udi full_name: Boker, Udi id: 31E297B6-F248-11E8-B48F-1D18A9856A87 last_name: Boker - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000-0002-2985-7724 - first_name: Nicolas Adrien full_name: Mazzocchi, Nicolas Adrien id: b26baa86-3308-11ec-87b0-8990f34baa85 last_name: Mazzocchi - first_name: Naci E full_name: Sarac, Naci E id: 8C6B42F8-C8E6-11E9-A03A-F2DCE5697425 last_name: Sarac citation: ama: 'Boker U, Henzinger TA, Mazzocchi NA, Sarac NE. Safety and liveness of quantitative automata. In: 34th International Conference on Concurrency Theory. Vol 279. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.CONCUR.2023.17' apa: 'Boker, U., Henzinger, T. A., Mazzocchi, N. A., & Sarac, N. E. (2023). Safety and liveness of quantitative automata. In 34th International Conference on Concurrency Theory (Vol. 279). Antwerp, Belgium: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2023.17' chicago: Boker, Udi, Thomas A Henzinger, Nicolas Adrien Mazzocchi, and Naci E Sarac. “Safety and Liveness of Quantitative Automata.” In 34th International Conference on Concurrency Theory, Vol. 279. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.CONCUR.2023.17. ieee: U. Boker, T. A. Henzinger, N. A. Mazzocchi, and N. E. Sarac, “Safety and liveness of quantitative automata,” in 34th International Conference on Concurrency Theory, Antwerp, Belgium, 2023, vol. 279. ista: 'Boker U, Henzinger TA, Mazzocchi NA, Sarac NE. 2023. Safety and liveness of quantitative automata. 34th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 279, 17.' mla: Boker, Udi, et al. “Safety and Liveness of Quantitative Automata.” 34th International Conference on Concurrency Theory, vol. 279, 17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.CONCUR.2023.17. short: U. Boker, T.A. Henzinger, N.A. Mazzocchi, N.E. Sarac, in:, 34th International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. conference: end_date: 2023-09-23 location: Antwerp, Belgium name: 'CONCUR: Conference on Concurrency Theory' start_date: 2023-09-18 corr_author: '1' date_created: 2023-07-14T10:00:15Z date_published: 2023-09-01T00:00:00Z date_updated: 2026-07-27T12:48:18Z day: '01' ddc: - '000' department: - _id: GradSch - _id: ToHe doi: 10.4230/LIPIcs.CONCUR.2023.17 ec_funded: 1 external_id: arxiv: - '2307.06016' isi: - '001570542500017' file: - access_level: open_access checksum: d40e57a04448ea5c77d7e1cfb9590a81 content_type: application/pdf creator: esarac date_created: 2023-07-14T12:03:48Z date_updated: 2023-07-14T12:03:48Z file_id: '13224' file_name: CONCUR23.pdf file_size: 755529 relation: main_file success: 1 file_date_updated: 2023-07-14T12:03:48Z has_accepted_license: '1' intvolume: ' 279' isi: 1 language: - iso: eng month: '09' oa: 1 oa_version: Published Version project: - _id: 62781420-2b32-11ec-9570-8d9b63373d4d call_identifier: H2020 grant_number: '101020093' name: Vigilant Algorithmic Monitoring of Software publication: 34th International Conference on Concurrency Theory publication_identifier: eissn: - 1868-8969 isbn: - '9783959772990' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: record: - id: '20342' relation: later_version status: public - id: '20147' relation: dissertation_contains status: public scopus_import: '1' status: public title: Safety and liveness of quantitative automata tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 279 year: '2023' ... --- _id: '13120' abstract: - lang: eng text: 'We formalized general (i.e., type-0) grammars using the Lean 3 proof assistant. We defined basic notions of rewrite rules and of words derived by a grammar, and used grammars to show closure of the class of type-0 languages under four operations: union, reversal, concatenation, and the Kleene star. The literature mostly focuses on Turing machine arguments, which are possibly more difficult to formalize. For the Kleene star, we could not follow the literature and came up with our own grammar-based construction.' acknowledgement: "Jasmin Blanchette: This research has received funding from the Netherlands Organization\r\nfor Scientific Research (NWO) under the Vidi program (project No. 016.Vidi.189.037, Lean Forward).\r\n__\r\nWe thank Vladimir Kolmogorov for making this collaboration possible. We\r\nthank Václav Končický for discussing ideas about the Kleene star construction. We thank Patrick Johnson, Floris van Doorn, and Damiano Testa for their small yet very valuable contributions to our code. We thank Eric Wieser for simplifying one of our proofs. We thank Mark Summerfield for suggesting textual improvements. We thank the anonymous reviewers for very helpful comments. Finally, we thank the Lean community for helping us with various technical issues and answering many questions. " alternative_title: - LIPIcs article_number: '15' article_processing_charge: No arxiv: 1 author: - first_name: Martin full_name: Dvorak, Martin id: 40ED02A8-C8B4-11E9-A9C0-453BE6697425 last_name: Dvorak orcid: 0000-0001-5293-214X - first_name: Jasmin full_name: Blanchette, Jasmin last_name: Blanchette citation: ama: 'Dvorak M, Blanchette J. Closure properties of general grammars - formally verified. In: 14th International Conference on Interactive Theorem Proving. Vol 268. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.ITP.2023.15' apa: 'Dvorak, M., & Blanchette, J. (2023). Closure properties of general grammars - formally verified. In 14th International Conference on Interactive Theorem Proving (Vol. 268). Bialystok, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITP.2023.15' chicago: Dvorak, Martin, and Jasmin Blanchette. “Closure Properties of General Grammars - Formally Verified.” In 14th International Conference on Interactive Theorem Proving, Vol. 268. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ITP.2023.15. ieee: M. Dvorak and J. Blanchette, “Closure properties of general grammars - formally verified,” in 14th International Conference on Interactive Theorem Proving, Bialystok, Poland, 2023, vol. 268. ista: 'Dvorak M, Blanchette J. 2023. Closure properties of general grammars - formally verified. 14th International Conference on Interactive Theorem Proving. ITP: Interactive Theorem Proving, LIPIcs, vol. 268, 15.' mla: Dvorak, Martin, and Jasmin Blanchette. “Closure Properties of General Grammars - Formally Verified.” 14th International Conference on Interactive Theorem Proving, vol. 268, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.ITP.2023.15. short: M. Dvorak, J. Blanchette, in:, 14th International Conference on Interactive Theorem Proving, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. conference: end_date: 2023-08-04 location: Bialystok, Poland name: 'ITP: Interactive Theorem Proving' start_date: 2023-07-31 corr_author: '1' date_created: 2023-06-05T07:29:05Z date_published: 2023-07-27T00:00:00Z date_updated: 2026-07-29T12:56:51Z day: '27' ddc: - '000' department: - _id: GradSch - _id: VlKo doi: 10.4230/LIPIcs.ITP.2023.15 external_id: arxiv: - '2302.06420' isi: - '001515590500015' file: - access_level: open_access checksum: 773a0197f05b67feaa6cb1e17ec3642d content_type: application/pdf creator: dernst date_created: 2023-08-07T11:55:43Z date_updated: 2023-08-07T11:55:43Z file_id: '13982' file_name: 2023_LIPIcS_Dvorak.pdf file_size: 715976 relation: main_file success: 1 file_date_updated: 2023-08-07T11:55:43Z has_accepted_license: '1' intvolume: ' 268' isi: 1 language: - iso: eng month: '07' oa: 1 oa_version: Published Version publication: 14th International Conference on Interactive Theorem Proving publication_identifier: eissn: - 1868-8969 isbn: - '9783959772846' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: link: - relation: software url: https://github.com/madvorak/grammars/tree/publish record: - id: '21393' relation: dissertation_contains status: public scopus_import: '1' status: public title: Closure properties of general grammars - formally verified tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 volume: 268 year: '2023' ... --- _id: '11808' abstract: - lang: eng text: In recent years, significant advances have been made in the design and analysis of fully dynamic algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. Here, we present a quick reference guide to recent engineering and theory results in the area of fully dynamic graph algorithms. alternative_title: - LIPIcs article_number: '1' article_processing_charge: No arxiv: 1 author: - first_name: Kathrin full_name: Hanauer, Kathrin last_name: Hanauer - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Christian full_name: Schulz, Christian last_name: Schulz citation: ama: 'Hanauer K, Henzinger M, Schulz C. Recent advances in fully dynamic graph algorithms. In: 1st Symposium on Algorithmic Foundations of Dynamic Networks. Vol 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.SAND.2022.1' apa: 'Hanauer, K., Henzinger, M., & Schulz, C. (2022). Recent advances in fully dynamic graph algorithms. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (Vol. 221). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SAND.2022.1' chicago: Hanauer, Kathrin, Monika Henzinger, and Christian Schulz. “Recent Advances in Fully Dynamic Graph Algorithms.” In 1st Symposium on Algorithmic Foundations of Dynamic Networks, Vol. 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.SAND.2022.1. ieee: K. Hanauer, M. Henzinger, and C. Schulz, “Recent advances in fully dynamic graph algorithms,” in 1st Symposium on Algorithmic Foundations of Dynamic Networks, Virtual, 2022, vol. 221. ista: 'Hanauer K, Henzinger M, Schulz C. 2022. Recent advances in fully dynamic graph algorithms. 1st Symposium on Algorithmic Foundations of Dynamic Networks. SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 221, 1.' mla: Hanauer, Kathrin, et al. “Recent Advances in Fully Dynamic Graph Algorithms.” 1st Symposium on Algorithmic Foundations of Dynamic Networks, vol. 221, 1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:10.4230/LIPIcs.SAND.2022.1. short: K. Hanauer, M. Henzinger, C. Schulz, in:, 1st Symposium on Algorithmic Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. conference: end_date: 2022-03-30 location: Virtual name: 'SAND: Symposium on Algorithmic Foundations of Dynamic Networks' start_date: 2022-03-28 date_created: 2022-08-11T14:35:52Z date_published: 2022-04-29T00:00:00Z date_updated: 2024-11-06T08:23:49Z day: '29' doi: 10.4230/LIPIcs.SAND.2022.1 extern: '1' external_id: arxiv: - '2102.11169' intvolume: ' 221' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPIcs.SAND.2022.1 month: '04' oa: 1 oa_version: Published Version publication: 1st Symposium on Algorithmic Foundations of Dynamic Networks publication_identifier: eissn: - 1868-8969 isbn: - '9783959772242' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Recent advances in fully dynamic graph algorithms type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 221 year: '2022' ...