[{"researchdata_availability":"no","day":"27","OA_place":"publisher","corr_author":"1","publication":"42nd International Symposium on Computational Geometry","department":[{"_id":"UlWa"}],"conference":{"start_date":"2026-06-02","end_date":"2026-06-05","name":"SoCG: Symposium on Computational Geometry","location":"New Brunswick, NJ, United States"},"_id":"22000","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"file_date_updated":"2026-06-22T07:53:13Z","author":[{"first_name":"Raphaël","last_name":"Tinarrage","orcid":"0000-0002-1404-1095","id":"40ebcc9d-905f-11ef-bf0a-dc475da8a04e","full_name":"Tinarrage, Raphaël"}],"ddc":["500"],"language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.SoCG.2026.93","file":[{"content_type":"application/pdf","date_updated":"2026-06-22T07:53:13Z","relation":"main_file","file_size":1436035,"file_name":"2026_LIPIcSSoCG_Tinarrage.pdf","access_level":"open_access","checksum":"a468edad327962309688aa78678138da","creator":"dernst","success":1,"file_id":"22111","date_created":"2026-06-22T07:53:13Z"}],"oa":1,"publication_status":"published","intvolume":"       367","year":"2026","date_created":"2026-06-14T22:01:43Z","OA_type":"gold","related_material":{"link":[{"relation":"software","url":"https://doi.org/10.5281/zenodo.19251455"}]},"supplementarymaterial":"yes","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959774185"]},"type":"conference","status":"public","oa_version":"Published Version","abstract":[{"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.","lang":"eng"}],"article_number":"93:1-93:22","keyword":["Triangulation of manifolds","Simplicial approximation","CW complexes","Delaunay complexes","List homomorphism problem","Topological Data Analysis"],"scopus_import":"1","citation":{"ieee":"R. Tinarrage, “Simplicial approximation to CW complexes with spherical Delaunay triangulations,” in <i>42nd International Symposium on Computational Geometry</i>, New Brunswick, NJ, United States, 2026, vol. 367.","ama":"Tinarrage R. Simplicial approximation to CW complexes with spherical Delaunay triangulations. In: <i>42nd International Symposium on Computational Geometry</i>. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.93\">10.4230/LIPIcs.SoCG.2026.93</a>","apa":"Tinarrage, R. (2026). Simplicial approximation to CW complexes with spherical Delaunay triangulations. In <i>42nd International Symposium on Computational Geometry</i> (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.93\">https://doi.org/10.4230/LIPIcs.SoCG.2026.93</a>","chicago":"Tinarrage, Raphaël. “Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations.” In <i>42nd International Symposium on Computational Geometry</i>, Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.93\">https://doi.org/10.4230/LIPIcs.SoCG.2026.93</a>.","mla":"Tinarrage, Raphaël. “Simplicial Approximation to CW Complexes with Spherical Delaunay Triangulations.” <i>42nd International Symposium on Computational Geometry</i>, vol. 367, 93:1-93:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.93\">10.4230/LIPIcs.SoCG.2026.93</a>.","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.","short":"R. Tinarrage, in:, 42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","das_tickbox":"0","external_id":{"arxiv":["2112.07573"]},"quality_controlled":"1","date_updated":"2026-06-22T11:28:26Z","month":"05","volume":367,"title":"Simplicial approximation to CW complexes with spherical Delaunay triangulations","article_processing_charge":"Yes","arxiv":1,"date_published":"2026-05-27T00:00:00Z"},{"has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ec_funded":1,"conference":{"end_date":"2026-06-05","name":"SoCG: Symposium on Computational Geometry","start_date":"2026-06-02","location":"New Brunswick, NJ, United States"},"department":[{"_id":"HeEd"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"22002","corr_author":"1","OA_place":"publisher","publication":"42nd International Symposium on Computational Geometry","day":"27","date_created":"2026-06-14T22:01:43Z","alternative_title":["LIPIcs"],"year":"2026","project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program"}],"file":[{"content_type":"application/pdf","date_updated":"2026-06-22T07:39:21Z","relation":"main_file","file_size":2052749,"file_id":"22110","success":1,"date_created":"2026-06-22T07:39:21Z","access_level":"open_access","file_name":"2026_LIPIcSSoCG_Leskiewicz.pdf","checksum":"3be91c06fdf716c8735b6af64a09a921","creator":"dernst"}],"doi":"10.4230/LIPIcs.SoCG.2026.72","publication_status":"published","oa":1,"intvolume":"       367","file_date_updated":"2026-06-22T07:39:21Z","author":[{"last_name":"Leśkiewicz","first_name":"Jakub","full_name":"Leśkiewicz, Jakub"},{"full_name":"Furmanek, Bartosz","last_name":"Furmanek","first_name":"Bartosz"},{"orcid":"0000-0001-9789-9750","first_name":"Michał","last_name":"Lipiński","full_name":"Lipiński, Michał","id":"dfffb474-4317-11ee-8f5c-fe3fc95a425e"},{"last_name":"Morozov","first_name":"Dmitriy","full_name":"Morozov, Dmitriy"}],"ddc":["500"],"language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","das_tickbox":"0","oa_version":"Published Version","abstract":[{"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.","lang":"eng"}],"article_number":"72:1-72:17","scopus_import":"1","citation":{"chicago":"Leśkiewicz, Jakub, Bartosz Furmanek, Michał Lipiński, and Dmitriy Morozov. “Topological Simplification Guided by Forbidden Regions.” In <i>42nd International Symposium on Computational Geometry</i>, Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.72\">https://doi.org/10.4230/LIPIcs.SoCG.2026.72</a>.","apa":"Leśkiewicz, J., Furmanek, B., Lipiński, M., &#38; Morozov, D. (2026). Topological simplification guided by forbidden regions. In <i>42nd International Symposium on Computational Geometry</i> (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.72\">https://doi.org/10.4230/LIPIcs.SoCG.2026.72</a>","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.","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.” <i>42nd International Symposium on Computational Geometry</i>, vol. 367, 72:1-72:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.72\">10.4230/LIPIcs.SoCG.2026.72</a>.","ieee":"J. Leśkiewicz, B. Furmanek, M. Lipiński, and D. Morozov, “Topological simplification guided by forbidden regions,” in <i>42nd International Symposium on Computational Geometry</i>, New Brunswick, NJ, United States, 2026, vol. 367.","ama":"Leśkiewicz J, Furmanek B, Lipiński M, Morozov D. Topological simplification guided by forbidden regions. In: <i>42nd International Symposium on Computational Geometry</i>. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.72\">10.4230/LIPIcs.SoCG.2026.72</a>"},"keyword":["persistent homology","topological simplification","depth posets"],"publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959774185"]},"type":"conference","status":"public","OA_type":"gold","title":"Topological simplification guided by forbidden regions","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.","arxiv":1,"date_published":"2026-05-27T00:00:00Z","article_processing_charge":"No","volume":367,"month":"05","external_id":{"arxiv":["2603.16416"]},"quality_controlled":"1","date_updated":"2026-06-22T07:45:36Z"},{"publication":"42nd International Symposium on Computational Geometry","OA_place":"publisher","corr_author":"1","day":"27","has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"conference":{"location":"New Brunswick, NJ, United States","start_date":"2026-06-02","name":"SoCG: Symposium on Computational Geometry","end_date":"2026-06-05"},"department":[{"_id":"HeEd"}],"_id":"22003","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":"       367","file":[{"date_created":"2026-06-22T08:43:47Z","success":1,"file_id":"22115","checksum":"25d27c016409563196b8aecfe5bfdf41","creator":"dernst","file_name":"2026_LIPIcSSoCG_Adams.pdf","access_level":"open_access","file_size":1091310,"date_updated":"2026-06-22T08:43:47Z","relation":"main_file","content_type":"application/pdf"}],"project":[{"_id":"26AD5D90-B435-11E9-9278-68D0E5697425","grant_number":"I04245","name":"Algebraic Footprints of Geometric Features in Homology","call_identifier":"FWF"}],"doi":"10.4230/LIPIcs.SoCG.2026.3","oa":1,"publication_status":"published","author":[{"full_name":"Adams, Henry","first_name":"Henry","last_name":"Adams"},{"last_name":"Majhi","first_name":"Sushovan","full_name":"Majhi, Sushovan"},{"first_name":"Fedor","last_name":"Manin","full_name":"Manin, Fedor"},{"id":"2E36B656-F248-11E8-B48F-1D18A9856A87","full_name":"Virk, Ziga","first_name":"Ziga","last_name":"Virk"},{"orcid":"0000-0001-8686-1888","first_name":"Nicolò","last_name":"Zava","full_name":"Zava, Nicolò","id":"c8b3499c-7a77-11eb-b046-aa368cbbf2ad"}],"language":[{"iso":"eng"}],"ddc":["500"],"file_date_updated":"2026-06-22T08:43:47Z","alternative_title":["LIPIcs"],"date_created":"2026-06-14T22:01:44Z","year":"2026","status":"public","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959774185"]},"type":"conference","OA_type":"gold","das_tickbox":"0","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa_version":"Published Version","article_number":"3:1-3:16","keyword":["Gromov–Hausdorff distance","distortion","connectedness","Borsuk–Ulam theorem"],"abstract":[{"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.","lang":"eng"}],"scopus_import":"1","citation":{"ama":"Adams H, Majhi S, Manin F, Virk Z, Zava N. Lower bounding the Gromov–Hausdorff distance in metric graphs. In: <i>42nd International Symposium on Computational Geometry</i>. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.3\">10.4230/LIPIcs.SoCG.2026.3</a>","ieee":"H. Adams, S. Majhi, F. Manin, Z. Virk, and N. Zava, “Lower bounding the Gromov–Hausdorff distance in metric graphs,” in <i>42nd International Symposium on Computational Geometry</i>, New Brunswick, NJ, United States, 2026, vol. 367.","mla":"Adams, Henry, et al. “Lower Bounding the Gromov–Hausdorff Distance in Metric Graphs.” <i>42nd International Symposium on Computational Geometry</i>, vol. 367, 3:1-3:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.3\">10.4230/LIPIcs.SoCG.2026.3</a>.","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.","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.","apa":"Adams, H., Majhi, S., Manin, F., Virk, Z., &#38; Zava, N. (2026). Lower bounding the Gromov–Hausdorff distance in metric graphs. In <i>42nd International Symposium on Computational Geometry</i> (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.3\">https://doi.org/10.4230/LIPIcs.SoCG.2026.3</a>","chicago":"Adams, Henry, Sushovan Majhi, Fedor Manin, Ziga Virk, and Nicolò Zava. “Lower Bounding the Gromov–Hausdorff Distance in Metric Graphs.” In <i>42nd International Symposium on Computational Geometry</i>, Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.3\">https://doi.org/10.4230/LIPIcs.SoCG.2026.3</a>."},"month":"05","date_updated":"2026-06-22T08:49:17Z","quality_controlled":"1","external_id":{"arxiv":["2411.09182"]},"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","article_processing_charge":"Yes","date_published":"2026-05-27T00:00:00Z","arxiv":1,"title":"Lower bounding the Gromov–Hausdorff distance in metric graphs","volume":367},{"month":"05","external_id":{"arxiv":["2603.21790"]},"date_updated":"2026-06-22T08:37:44Z","quality_controlled":"1","title":"Charting the diameter computation landscape of intersection graphs in 3D and above","date_published":"2026-05-27T00:00:00Z","arxiv":1,"article_processing_charge":"Yes","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.","volume":367,"type":"conference","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959774185"]},"status":"public","OA_type":"gold","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","das_tickbox":"0","article_number":"29:1-29:15","keyword":["Graph Diameter","Geometric Intersection Graphs","Unit Ball Graphs"],"scopus_import":"1","citation":{"ieee":"T. M. Chan, H. C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, and D. W. Zheng, “Charting the diameter computation landscape of intersection graphs in 3D and above,” in <i>42nd International Symposium on Computational Geometry</i>, New Brunswick, NJ, United States, 2026, vol. 367.","ama":"Chan TM, Chang HC, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. Charting the diameter computation landscape of intersection graphs in 3D and above. In: <i>42nd International Symposium on Computational Geometry</i>. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.29\">10.4230/LIPIcs.SoCG.2026.29</a>","chicago":"Chan, Timothy M., Hsien Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng. “Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above.” In <i>42nd International Symposium on Computational Geometry</i>, Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.29\">https://doi.org/10.4230/LIPIcs.SoCG.2026.29</a>.","apa":"Chan, T. M., Chang, H. C., Gao, J., Kisfaludi-Bak, S., Le, H., &#38; Zheng, D. W. (2026). Charting the diameter computation landscape of intersection graphs in 3D and above. In <i>42nd International Symposium on Computational Geometry</i> (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.29\">https://doi.org/10.4230/LIPIcs.SoCG.2026.29</a>","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.","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.","mla":"Chan, Timothy M., et al. “Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above.” <i>42nd International Symposium on Computational Geometry</i>, vol. 367, 29:1-29:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2026.29\">10.4230/LIPIcs.SoCG.2026.29</a>."},"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."}],"oa_version":"Published Version","publication_status":"published","oa":1,"doi":"10.4230/LIPIcs.SoCG.2026.29","file":[{"relation":"main_file","date_updated":"2026-06-22T08:34:11Z","content_type":"application/pdf","file_size":918197,"success":1,"file_id":"22114","date_created":"2026-06-22T08:34:11Z","file_name":"2026_LIPIcSSoCG_Chan.pdf","access_level":"open_access","creator":"dernst","checksum":"ffff03934cc182757d6db82d88f896e6"}],"project":[{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"intvolume":"       367","file_date_updated":"2026-06-22T08:34:11Z","ddc":["000"],"language":[{"iso":"eng"}],"author":[{"last_name":"Chan","first_name":"Timothy M.","full_name":"Chan, Timothy M."},{"first_name":"Hsien Chih","last_name":"Chang","full_name":"Chang, Hsien Chih"},{"first_name":"Jie","last_name":"Gao","full_name":"Gao, Jie"},{"full_name":"Kisfaludi-Bak, Sándor","last_name":"Kisfaludi-Bak","first_name":"Sándor"},{"first_name":"Hung","last_name":"Le","full_name":"Le, Hung"},{"id":"af77956b-e859-11ef-8dc9-d301b898e32f","full_name":"Zheng, Da Wei","last_name":"Zheng","first_name":"Da Wei"}],"date_created":"2026-06-14T22:01:44Z","alternative_title":["LIPIcs"],"year":"2026","corr_author":"1","OA_place":"publisher","publication":"42nd International Symposium on Computational Geometry","day":"27","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","_id":"22004","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2026-06-02","end_date":"2026-06-05","name":"SoCG: Symposium on Computational Geometry","location":"New Brunswick, NJ, United States"},"department":[{"_id":"MoHe"}]},{"volume":361,"title":"Fast re-routing in networks: On the complexity of perfect resilience","article_processing_charge":"No","date_published":"2026-01-07T00:00:00Z","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).","date_updated":"2026-03-09T12:36:11Z","quality_controlled":"1","month":"01","scopus_import":"1","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). "}],"article_number":"31","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: <i>29th International Conference on Principles of Distributed Systems</i>. Vol 361. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2025.31\">10.4230/LIPIcs.OPODIS.2025.31</a>","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 <i>29th International Conference on Principles of Distributed Systems</i>, Iaşi, Romania, 2026, vol. 361.","mla":"Bentert, Matthias, et al. “Fast Re-Routing in Networks: On the Complexity of Perfect Resilience.” <i>29th International Conference on Principles of Distributed Systems</i>, vol. 361, 31, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2025.31\">10.4230/LIPIcs.OPODIS.2025.31</a>.","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.","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.","apa":"Bentert, M., Ceylan, E., Hübner, V., Schmid, S., &#38; Srba, J. (2026). Fast re-routing in networks: On the complexity of perfect resilience. In <i>29th International Conference on Principles of Distributed Systems</i> (Vol. 361). Iaşi, Romania: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2025.31\">https://doi.org/10.4230/LIPIcs.OPODIS.2025.31</a>","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 <i>29th International Conference on Principles of Distributed Systems</i>, Vol. 361. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2025.31\">https://doi.org/10.4230/LIPIcs.OPODIS.2025.31</a>."},"oa_version":"Published Version","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","OA_type":"gold","type":"conference","publication_identifier":{"isbn":["9783959774093"],"eissn":["1868-8969"]},"status":"public","year":"2026","date_created":"2026-03-08T23:01:46Z","alternative_title":["LIPIcs"],"file_date_updated":"2026-03-09T12:33:58Z","ddc":["000"],"language":[{"iso":"eng"}],"author":[{"last_name":"Bentert","first_name":"Matthias","full_name":"Bentert, Matthias"},{"full_name":"Ceylan, Esra","last_name":"Ceylan","first_name":"Esra"},{"first_name":"Valentin","last_name":"Hübner","orcid":"0009-0001-5009-4987","id":"2c8aa207-dc7d-11ea-9b2f-f22972ecd910","full_name":"Hübner, Valentin"},{"last_name":"Schmid","first_name":"Stefan","full_name":"Schmid, Stefan"},{"full_name":"Srba, Jiří","first_name":"Jiří","last_name":"Srba"}],"publication_status":"published","oa":1,"file":[{"file_id":"21419","success":1,"date_created":"2026-03-09T12:33:58Z","access_level":"open_access","file_name":"2026_OPODIS_Bentert.pdf","checksum":"a7af114da7c38d2338b4edb922eb27f1","creator":"dernst","date_updated":"2026-03-09T12:33:58Z","content_type":"application/pdf","relation":"main_file","file_size":1041334}],"doi":"10.4230/LIPIcs.OPODIS.2025.31","intvolume":"       361","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"21411","department":[{"_id":"KrCh"}],"conference":{"start_date":"2025-12-03","end_date":"2025-12-05","name":"OPODIS: Conference on Principles of Distributed Systems","location":"Iaşi, Romania"},"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","day":"07","OA_place":"publisher","publication":"29th International Conference on Principles of Distributed Systems"},{"month":"06","date_updated":"2026-06-29T06:56:34Z","quality_controlled":"1","external_id":{"arxiv":["2511.17994"]},"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","date_published":"2026-06-01T00:00:00Z","article_processing_charge":"No","arxiv":1,"title":"Learning rate scheduling with matrix factorization for private training","volume":368,"status":"public","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959774192"]},"type":"conference","supplementarymaterial":"no","OA_type":"gold","das_tickbox":"0","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa_version":"Published Version","article_number":"2:1-2:21","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."}],"scopus_import":"1","keyword":["differential privacy","machine learning","matrix factorization"],"citation":{"mla":"Kalinin, Nikita, and Joel D. Andersson. “Learning Rate Scheduling with Matrix Factorization for Private Training.” <i>7th Symposium on Foundations of Responsible Computing</i>, vol. 368, 2:1-2:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FORC.2026.2\">10.4230/LIPIcs.FORC.2026.2</a>.","short":"N. Kalinin, J.D. Andersson, in:, 7th Symposium on Foundations of Responsible Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","ista":"Kalinin N, Andersson JD. 2026. Learning rate scheduling with matrix factorization for private training. 7th Symposium on Foundations of Responsible Computing. FORC: Symposium on Foundations of Responsible Computing, LIPIcs, vol. 368, 2:1-2:21.","apa":"Kalinin, N., &#38; Andersson, J. D. (2026). Learning rate scheduling with matrix factorization for private training. In <i>7th Symposium on Foundations of Responsible Computing</i> (Vol. 368). Cambridge, MA; United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FORC.2026.2\">https://doi.org/10.4230/LIPIcs.FORC.2026.2</a>","chicago":"Kalinin, Nikita, and Joel D Andersson. “Learning Rate Scheduling with Matrix Factorization for Private Training.” In <i>7th Symposium on Foundations of Responsible Computing</i>, Vol. 368. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.FORC.2026.2\">https://doi.org/10.4230/LIPIcs.FORC.2026.2</a>.","ama":"Kalinin N, Andersson JD. Learning rate scheduling with matrix factorization for private training. In: <i>7th Symposium on Foundations of Responsible Computing</i>. Vol 368. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FORC.2026.2\">10.4230/LIPIcs.FORC.2026.2</a>","ieee":"N. Kalinin and J. D. Andersson, “Learning rate scheduling with matrix factorization for private training,” in <i>7th Symposium on Foundations of Responsible Computing</i>, Cambridge, MA; United States, 2026, vol. 368."},"intvolume":"       368","project":[{"grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020"}],"doi":"10.4230/LIPIcs.FORC.2026.2","file":[{"file_size":1231914,"date_updated":"2026-06-29T06:55:23Z","content_type":"application/pdf","relation":"main_file","creator":"dernst","checksum":"c661f016d3861a1c1b590b87a744d087","file_name":"2026_LIPIcsFORC_Kalinin.pdf","access_level":"open_access","date_created":"2026-06-29T06:55:23Z","success":1,"file_id":"22149"}],"publication_status":"published","oa":1,"author":[{"full_name":"Kalinin, Nikita","id":"4b14526e-14d2-11ed-ba64-c14c9553d137","first_name":"Nikita","last_name":"Kalinin"},{"first_name":"Joel D","last_name":"Andersson","full_name":"Andersson, Joel D","id":"4a893819-d954-11f0-89b1-e360bad9ccc5"}],"language":[{"iso":"eng"}],"ddc":["000"],"file_date_updated":"2026-06-29T06:55:23Z","alternative_title":["LIPIcs"],"date_created":"2026-06-28T22:01:34Z","year":"2026","publication":"7th Symposium on Foundations of Responsible Computing","corr_author":"1","OA_place":"publisher","researchdata_availability":"no","day":"01","has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"department":[{"_id":"ChLa"},{"_id":"GradSch"},{"_id":"MoHe"}],"conference":{"start_date":"2026-06-03","name":"FORC: Symposium on Foundations of Responsible Computing","end_date":"2026-06-05","location":"Cambridge, MA; United States"},"ec_funded":1,"_id":"22146","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"month":"05","external_id":{"arxiv":["2511.21961"]},"date_updated":"2026-07-14T06:09:32Z","quality_controlled":"1","title":"The depth poset under transpositions in the filter","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","arxiv":1,"article_processing_charge":"Yes","date_published":"2026-05-27T00:00:00Z","volume":367,"publication_identifier":{"isbn":["9783959774185"],"eissn":["1868-8969"]},"type":"conference","status":"public","OA_type":"gold","supplementarymaterial":"no","publisher":"Schloss Dagstuhl – Leibniz-Zentrum für Informatik","das_tickbox":"0","oa_version":"Published Version","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."}],"article_number":"41:1-41:18","scopus_import":"1","keyword":["Algebraic topology","Lefschetz complexes","persistent homology","vines and vineyards","birth-death pairs","shallow pairs","relations","partial orders","transpositions","Theory of computation → Computational geometry"],"citation":{"apa":"Edelsbrunner, H., Lipiński, M., Mrozek, M., Soriano Trigueros, M., &#38; Zimin, F. (2026). The depth poset under transpositions in the filter. In <i>42nd International Symposium on Computational Geometry</i> (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2026.41\">https://doi.org/10.4230/LIPICS.SOCG.2026.41</a>","chicago":"Edelsbrunner, Herbert, Michał Lipiński, Marian Mrozek, Manuel Soriano Trigueros, and Fedor Zimin. “The Depth Poset under Transpositions in the Filter.” In <i>42nd International Symposium on Computational Geometry</i>, Vol. 367. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPICS.SOCG.2026.41\">https://doi.org/10.4230/LIPICS.SOCG.2026.41</a>.","mla":"Edelsbrunner, Herbert, et al. “The Depth Poset under Transpositions in the Filter.” <i>42nd International Symposium on Computational Geometry</i>, vol. 367, 41:1-41:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2026.41\">10.4230/LIPICS.SOCG.2026.41</a>.","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.","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.","ieee":"H. Edelsbrunner, M. Lipiński, M. Mrozek, M. Soriano Trigueros, and F. Zimin, “The depth poset under transpositions in the filter,” in <i>42nd International Symposium on Computational Geometry</i>, New Brunswick, NJ, United States, 2026, vol. 367.","ama":"Edelsbrunner H, Lipiński M, Mrozek M, Soriano Trigueros M, Zimin F. The depth poset under transpositions in the filter. In: <i>42nd International Symposium on Computational Geometry</i>. Vol 367. Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPICS.SOCG.2026.41\">10.4230/LIPICS.SOCG.2026.41</a>"},"file":[{"date_created":"2026-07-14T06:08:05Z","success":1,"file_id":"22329","checksum":"9dfb96ee66985c724b499b0e5888dc8e","creator":"dernst","file_name":"2026_LIPIcSSoCG_Edelsbrunner.pdf","access_level":"open_access","file_size":2902144,"content_type":"application/pdf","date_updated":"2026-07-14T06:08:05Z","relation":"main_file"}],"doi":"10.4230/LIPICS.SOCG.2026.41","project":[{"grant_number":"I02979-N35","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","name":"Persistence and stability of geometric complexes","call_identifier":"FWF"},{"grant_number":"101034413","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program"}],"publication_status":"published","oa":1,"intvolume":"       367","file_date_updated":"2026-07-14T06:08:05Z","author":[{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"},{"orcid":"0000-0001-9789-9750","last_name":"Lipiński","first_name":"Michał","full_name":"Lipiński, Michał","id":"dfffb474-4317-11ee-8f5c-fe3fc95a425e"},{"orcid":"0000-0002-0619-6417","first_name":"Marian","last_name":"Mrozek","full_name":"Mrozek, Marian"},{"orcid":"0000-0003-2449-1433","first_name":"Manuel","last_name":"Soriano Trigueros","full_name":"Soriano Trigueros, Manuel","id":"15ebd7cf-15bf-11ee-aebd-bb4bb5121ea8"},{"last_name":"Zimin","first_name":"Fedor","full_name":"Zimin, Fedor","id":"afd27eda-91c1-11f0-aad8-c6edbec24c04"}],"ddc":["500"],"language":[{"iso":"eng"}],"date_created":"2026-07-13T09:56:38Z","alternative_title":["LIPIcs"],"year":"2026","OA_place":"publisher","corr_author":"1","publication":"42nd International Symposium on Computational Geometry","researchdata_availability":"no","day":"27","has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"department":[{"_id":"HeEd"},{"_id":"GradSch"}],"ec_funded":1,"conference":{"location":"New Brunswick, NJ, United States","start_date":"2026-06-02","end_date":"2026-06-05","name":"SoCG: Symposium on Computational Geometry"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"22299"},{"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","_id":"22405","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"MoHe"}],"conference":{"location":"Egham, United Kingdom","start_date":"2026-07-07","name":"ICALP: Automata, Languages and Programming","end_date":"2026-07-10"},"publication":"53rd International Colloquium on Automata, Languages, and Programming","OA_place":"publisher","corr_author":"1","day":"01","researchdata_availability":"no","date_created":"2026-07-27T05:53:08Z","year":"2026","intvolume":"       374","publication_status":"published","oa":1,"file":[{"relation":"main_file","content_type":"application/pdf","date_updated":"2026-07-27T06:20:41Z","file_size":1440497,"file_id":"22407","success":1,"date_created":"2026-07-27T06:20:41Z","access_level":"open_access","file_name":"2026_LIPIcSICALP_Chan.pdf","creator":"dernst","checksum":"1e66eba4cfe4e74ab28108b1ca0bb956"}],"doi":"10.4230/LIPICS.ICALP.2026.54","project":[{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions"}],"ddc":["000"],"language":[{"iso":"eng"}],"author":[{"first_name":"Timothy M.","last_name":"Chan","orcid":"0000-0002-8093-0675","full_name":"Chan, Timothy M."},{"orcid":"0000-0001-6714-7988","last_name":"Chang","first_name":"Hsien-Chih","full_name":"Chang, Hsien-Chih"},{"full_name":"Gao, Jie","orcid":"0000-0001-5083-6082","first_name":"Jie","last_name":"Gao"},{"full_name":"Kisfaludi-Bak, Sándor","orcid":"0000-0002-6856-2902","first_name":"Sándor","last_name":"Kisfaludi-Bak"},{"full_name":"Le, Hung","orcid":"0000-0001-8223-9944","last_name":"Le","first_name":"Hung"},{"last_name":"Zheng","first_name":"Da Wei","id":"af77956b-e859-11ef-8dc9-d301b898e32f","full_name":"Zheng, Da Wei"}],"file_date_updated":"2026-07-27T06:20:41Z","das_tickbox":"0","publisher":"Schloss Dagstuhl – Leibniz-Zentrum für Informatik","article_number":"54:1-54:22","citation":{"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 <i>53rd International Colloquium on Automata, Languages, and Programming</i>, Egham, United Kingdom, 2026, vol. 374.","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: <i>53rd International Colloquium on Automata, Languages, and Programming</i>. Vol 374. Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPICS.ICALP.2026.54\">10.4230/LIPICS.ICALP.2026.54</a>","apa":"Chan, T. M., Chang, H.-C., Gao, J., Kisfaludi-Bak, S., Le, H., &#38; Zheng, D. W. (2026). Charting the landscape of diameter computation on geometric intersection graphs in the plane. In <i>53rd International Colloquium on Automata, Languages, and Programming</i> (Vol. 374). Egham, United Kingdom: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ICALP.2026.54\">https://doi.org/10.4230/LIPICS.ICALP.2026.54</a>","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 <i>53rd International Colloquium on Automata, Languages, and Programming</i>, Vol. 374. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPICS.ICALP.2026.54\">https://doi.org/10.4230/LIPICS.ICALP.2026.54</a>.","mla":"Chan, Timothy M., et al. “Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane.” <i>53rd International Colloquium on Automata, Languages, and Programming</i>, vol. 374, 54:1-54:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPICS.ICALP.2026.54\">10.4230/LIPICS.ICALP.2026.54</a>.","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.","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."},"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."}],"scopus_import":"1","keyword":["String graphs","Fine-grained complexity","Theory of computation → Computational geometry"],"oa_version":"Published Version","status":"public","type":"conference","publication_identifier":{"eissn":["1868-8969","9783959774284"]},"supplementarymaterial":"no","OA_type":"gold","date_published":"2026-07-01T00:00:00Z","arxiv":1,"article_processing_charge":"No","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","title":"Charting the landscape of diameter computation on geometric intersection graphs in the plane","volume":374,"month":"07","quality_controlled":"1","date_updated":"2026-07-27T06:22:03Z","external_id":{"arxiv":["2605.10692"]}},{"volume":343,"title":"Time-space tradeoffs of truncation with preprocessing","date_published":"2025-09-08T00:00:00Z","article_processing_charge":"Yes","external_id":{"cryptoeprintid":["2025/723"]},"quality_controlled":"1","date_updated":"2026-06-22T08:57:41Z","month":"09","abstract":[{"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.","lang":"eng"}],"citation":{"apa":"Pietrzak, K. Z., &#38; Wang, P. (2025). Time-space tradeoffs of truncation with preprocessing. In <i>6th Conference on Information-Theoretic Cryptography</i> (Vol. 343). Santa Barbara, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITC.2025.4\">https://doi.org/10.4230/LIPIcs.ITC.2025.4</a>","chicago":"Pietrzak, Krzysztof Z, and Pengxiang Wang. “Time-Space Tradeoffs of Truncation with Preprocessing.” In <i>6th Conference on Information-Theoretic Cryptography</i>, Vol. 343. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ITC.2025.4\">https://doi.org/10.4230/LIPIcs.ITC.2025.4</a>.","mla":"Pietrzak, Krzysztof Z., and Pengxiang Wang. “Time-Space Tradeoffs of Truncation with Preprocessing.” <i>6th Conference on Information-Theoretic Cryptography</i>, vol. 343, 4:1-4:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITC.2025.4\">10.4230/LIPIcs.ITC.2025.4</a>.","short":"K.Z. Pietrzak, P. Wang, in:, 6th Conference on Information-Theoretic Cryptography, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","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.","ieee":"K. Z. Pietrzak and P. Wang, “Time-space tradeoffs of truncation with preprocessing,” in <i>6th Conference on Information-Theoretic Cryptography</i>, Santa Barbara, CA, United States, 2025, vol. 343.","ama":"Pietrzak KZ, Wang P. Time-space tradeoffs of truncation with preprocessing. In: <i>6th Conference on Information-Theoretic Cryptography</i>. Vol 343. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITC.2025.4\">10.4230/LIPIcs.ITC.2025.4</a>"},"scopus_import":"1","keyword":["Time-Space Lower Bounds","Blockchains"],"article_number":"4:1-4:10","oa_version":"Published Version","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","das_tickbox":"0","cryptoeprintid":1,"OA_type":"gold","type":"conference","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773850"]},"status":"public","year":"2025","date_created":"2026-06-14T22:01:45Z","alternative_title":["LIPIcs"],"file_date_updated":"2026-06-22T08:54:32Z","ddc":["000"],"language":[{"iso":"eng"}],"author":[{"orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Wang, Pengxiang","first_name":"Pengxiang","last_name":"Wang"}],"oa":1,"publication_status":"published","doi":"10.4230/LIPIcs.ITC.2025.4","file":[{"date_updated":"2026-06-22T08:54:32Z","relation":"main_file","content_type":"application/pdf","file_size":772046,"file_name":"2025_LIPIcs_Pietrzak.pdf","access_level":"open_access","creator":"dernst","checksum":"3f791b03df26853342855a9d9581cb58","success":1,"file_id":"22118","date_created":"2026-06-22T08:54:32Z"}],"intvolume":"       343","_id":"22007","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"KrPi"}],"conference":{"start_date":"2025-08-16","name":"ITC: Information Theoretic Cryptography","end_date":"2025-08-17","location":"Santa Barbara, CA, United States"},"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","day":"08","OA_place":"publisher","corr_author":"1","publication":"6th Conference on Information-Theoretic Cryptography"},{"oa_version":"Published Version","article_number":"43","abstract":[{"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 𝕊^d. Furthermore, we use the result to give a new geometric proof for the fact that volumes of hypersimplices are Eulerian numbers.","lang":"eng"}],"scopus_import":"1","citation":{"ieee":"H. Edelsbrunner, A. Garber, and M. Saghafian, “On spheres with k points inside,” in <i>41st International Symposium on Computational Geometry</i>, Kanazawa, Japan, 2025, vol. 332.","ama":"Edelsbrunner H, Garber A, Saghafian M. On spheres with k points inside. In: <i>41st International Symposium on Computational Geometry</i>. Vol 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.43\">10.4230/LIPIcs.SoCG.2025.43</a>","chicago":"Edelsbrunner, Herbert, Alexey Garber, and Morteza Saghafian. “On Spheres with k Points Inside.” In <i>41st International Symposium on Computational Geometry</i>, Vol. 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.43\">https://doi.org/10.4230/LIPIcs.SoCG.2025.43</a>.","apa":"Edelsbrunner, H., Garber, A., &#38; Saghafian, M. (2025). On spheres with k points inside. In <i>41st International Symposium on Computational Geometry</i> (Vol. 332). Kanazawa, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.43\">https://doi.org/10.4230/LIPIcs.SoCG.2025.43</a>","short":"H. Edelsbrunner, A. Garber, M. Saghafian, in:, 41st International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","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.” <i>41st International Symposium on Computational Geometry</i>, vol. 332, 43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.43\">10.4230/LIPIcs.SoCG.2025.43</a>."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","OA_type":"gold","status":"public","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773706"]},"type":"conference","volume":332,"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","date_published":"2025-06-20T00:00:00Z","arxiv":1,"article_processing_charge":"Yes","title":"On spheres with k points inside","date_updated":"2025-07-14T07:26:14Z","quality_controlled":"1","external_id":{"arxiv":["2410.21204"]},"month":"06","department":[{"_id":"HeEd"}],"conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2025-06-27","start_date":"2025-06-23","location":"Kanazawa, Japan"},"_id":"20005","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"day":"20","publication":"41st International Symposium on Computational Geometry","corr_author":"1","OA_place":"publisher","year":"2025","alternative_title":["LIPIcs"],"date_created":"2025-07-13T22:01:22Z","author":[{"first_name":"Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"first_name":"Alexey","last_name":"Garber","full_name":"Garber, Alexey"},{"id":"f86f7148-b140-11ec-9577-95435b8df824","full_name":"Saghafian, Morteza","last_name":"Saghafian","first_name":"Morteza"}],"language":[{"iso":"eng"}],"ddc":["510"],"file_date_updated":"2025-07-14T07:24:22Z","intvolume":"       332","doi":"10.4230/LIPIcs.SoCG.2025.43","project":[{"call_identifier":"FWF","name":"Mathematics, Computer Science","grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425"},{"grant_number":"I02979-N35","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","name":"Persistence and stability of geometric complexes","call_identifier":"FWF"}],"file":[{"date_created":"2025-07-14T07:24:22Z","file_id":"20016","success":1,"creator":"dernst","checksum":"b5313ed8575ea87913c71a6e3c7513c8","access_level":"open_access","file_name":"2025_LIPIcs.SoCG_Edelsbrunner.pdf","file_size":661893,"date_updated":"2025-07-14T07:24:22Z","content_type":"application/pdf","relation":"main_file"}],"publication_status":"published","oa":1},{"has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"department":[{"_id":"HeEd"}],"conference":{"location":"Kanazawa, Japan","start_date":"2025-06-23","name":"SoCG: Symposium on Computational Geometry","end_date":"2025-06-27"},"_id":"20006","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"41st International Symposium on Computational Geometry","corr_author":"1","OA_place":"publisher","day":"20","alternative_title":["LIPIcs"],"date_created":"2025-07-13T22:01:22Z","year":"2025","intvolume":"       332","doi":"10.4230/LIPIcs.SoCG.2025.71","file":[{"file_id":"20017","success":1,"date_created":"2025-07-14T08:23:38Z","access_level":"open_access","file_name":"2025_LIPIcs.SoCG_Ost.pdf","checksum":"3a4a7a707a56e0cfdf51428782dee55a","creator":"dernst","content_type":"application/pdf","relation":"main_file","date_updated":"2025-07-14T08:23:38Z","file_size":834623}],"project":[{"grant_number":"W1260-N35","_id":"9B9290DE-BA93-11EA-9121-9846C619BF3A","name":"Vienna Graduate School on Computational Optimization"},{"grant_number":"I02979-N35","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Persistence and stability of geometric complexes"},{"name":"Mathematics, Computer Science","call_identifier":"FWF","grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425"}],"oa":1,"publication_status":"published","author":[{"full_name":"Ost, Lara","last_name":"Ost","first_name":"Lara"},{"full_name":"Cultrera di Montesano, Sebastiano","id":"34D2A09C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6249-0832","last_name":"Cultrera di Montesano","first_name":"Sebastiano"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833"}],"ddc":["000"],"language":[{"iso":"eng"}],"file_date_updated":"2025-07-14T08:23:38Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa_version":"Published Version","scopus_import":"1","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."}],"article_number":"71","citation":{"apa":"Ost, L., Cultrera di Montesano, S., &#38; Edelsbrunner, H. (2025). Banana trees for the persistence in time series experimentally. In <i>41st International Symposium on Computational Geometry</i> (Vol. 332). Kanazawa, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.71\">https://doi.org/10.4230/LIPIcs.SoCG.2025.71</a>","chicago":"Ost, Lara, Sebastiano Cultrera di Montesano, and Herbert Edelsbrunner. “Banana Trees for the Persistence in Time Series Experimentally.” In <i>41st International Symposium on Computational Geometry</i>, Vol. 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.71\">https://doi.org/10.4230/LIPIcs.SoCG.2025.71</a>.","mla":"Ost, Lara, et al. “Banana Trees for the Persistence in Time Series Experimentally.” <i>41st International Symposium on Computational Geometry</i>, vol. 332, 71, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.71\">10.4230/LIPIcs.SoCG.2025.71</a>.","short":"L. Ost, S. Cultrera di Montesano, H. Edelsbrunner, in:, 41st International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","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.","ieee":"L. Ost, S. Cultrera di Montesano, and H. Edelsbrunner, “Banana trees for the persistence in time series experimentally,” in <i>41st International Symposium on Computational Geometry</i>, Kanazawa, Japan, 2025, vol. 332.","ama":"Ost L, Cultrera di Montesano S, Edelsbrunner H. Banana trees for the persistence in time series experimentally. In: <i>41st International Symposium on Computational Geometry</i>. Vol 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.71\">10.4230/LIPIcs.SoCG.2025.71</a>"},"status":"public","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773706"]},"type":"conference","related_material":{"link":[{"relation":"software","url":"https://github.com/laraost/BananaPersist"}]},"OA_type":"gold","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.","date_published":"2025-06-20T00:00:00Z","article_processing_charge":"Yes","arxiv":1,"title":"Banana trees for the persistence in time series experimentally","volume":332,"month":"06","date_updated":"2025-12-30T11:04:33Z","quality_controlled":"1","external_id":{"arxiv":["2405.17920"]}},{"year":"2025","alternative_title":["LIPIcs"],"date_created":"2025-07-13T22:01:22Z","language":[{"iso":"eng"}],"ddc":["510"],"author":[{"last_name":"Streltsova","first_name":"Elizaveta","id":"57a170da-dc96-11ea-b7c8-ab3565071bf7","full_name":"Streltsova, Elizaveta"},{"first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"file_date_updated":"2025-07-14T07:11:04Z","intvolume":"       332","publication_status":"published","oa":1,"file":[{"date_updated":"2025-07-14T07:11:04Z","relation":"main_file","content_type":"application/pdf","file_size":952807,"file_name":"2025_LIPIcs.SoCG_Streltsova.pdf","access_level":"open_access","creator":"dernst","checksum":"a8f7feb1aa3b896e31195841a989d622","success":1,"file_id":"20015","date_created":"2025-07-14T07:11:04Z"}],"doi":"10.4230/LIPIcs.SoCG.2025.75","_id":"20004","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2025-06-23","name":"SoCG: Symposium on Computational Geometry","end_date":"2025-06-27","location":"Kanazawa, Japan"},"department":[{"_id":"UlWa"}],"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","day":"20","publication":"41st International Symposium on Computational Geometry","OA_place":"publisher","corr_author":"1","volume":332,"arxiv":1,"article_processing_charge":"Yes","date_published":"2025-06-20T00:00:00Z","title":"Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers","quality_controlled":"1","date_updated":"2026-07-07T13:03:16Z","external_id":{"arxiv":["2504.07752","2504.07770"]},"month":"06","scopus_import":"1","article_number":"75","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."}],"citation":{"chicago":"Streltsova, Elizaveta, and Uli Wagner. “Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers.” In <i>41st International Symposium on Computational Geometry</i>, Vol. 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.75\">https://doi.org/10.4230/LIPIcs.SoCG.2025.75</a>.","apa":"Streltsova, E., &#38; Wagner, U. (2025). Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers. In <i>41st International Symposium on Computational Geometry</i> (Vol. 332). Kanazawa, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.75\">https://doi.org/10.4230/LIPIcs.SoCG.2025.75</a>","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.","short":"E. Streltsova, U. Wagner, in:, 41st International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","mla":"Streltsova, Elizaveta, and Uli Wagner. “Levels in Arrangements: Linear Relations, the g-Matrix, and Applications to Crossing Numbers.” <i>41st International Symposium on Computational Geometry</i>, vol. 332, 75, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.75\">10.4230/LIPIcs.SoCG.2025.75</a>.","ieee":"E. Streltsova and U. Wagner, “Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers,” in <i>41st International Symposium on Computational Geometry</i>, Kanazawa, Japan, 2025, vol. 332.","ama":"Streltsova E, Wagner U. Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers. In: <i>41st International Symposium on Computational Geometry</i>. Vol 332. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2025.75\">10.4230/LIPIcs.SoCG.2025.75</a>"},"oa_version":"Published Version","das_tickbox":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","OA_type":"gold","status":"public","type":"conference","publication_identifier":{"isbn":["9783959773706"],"eissn":["1868-8969"]}},{"title":"Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds","article_processing_charge":"No","date_published":"2024-06-06T00:00:00Z","arxiv":1,"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.","volume":293,"month":"06","external_id":{"arxiv":["2206.10485"]},"date_updated":"2025-04-15T07:16:57Z","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","abstract":[{"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) 𝒮 of positive reach may be noisy. We work with two one-sided Hausdorff distances - ε and δ - between P and 𝒮. 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 𝒮. 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.","lang":"eng"}],"citation":{"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 <i>40th International Symposium on Computational Geometry</i>, 293:11:1-11:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.11\">https://doi.org/10.4230/LIPIcs.SoCG.2024.11</a>.","apa":"Attali, D., Kourimska, H., Fillmore, C. D., Ghosh, I., Lieutier, A., Stephenson, E. R., &#38; 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 <i>40th International Symposium on Computational Geometry</i> (Vol. 293, p. 11:1-11:19). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.11\">https://doi.org/10.4230/LIPIcs.SoCG.2024.11</a>","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.","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.","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.” <i>40th International Symposium on Computational Geometry</i>, vol. 293, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 11:1-11:19, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.11\">10.4230/LIPIcs.SoCG.2024.11</a>.","ieee":"D. Attali <i>et al.</i>, “Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds,” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293, p. 11:1-11:19.","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: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:11:1-11:19. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.11\">10.4230/LIPIcs.SoCG.2024.11</a>"},"scopus_import":"1","oa_version":"Published Version","type":"conference","publication_identifier":{"isbn":["9783959773164"],"eissn":["1868-8969"]},"status":"public","date_created":"2024-06-25T11:45:58Z","alternative_title":["LIPIcs"],"year":"2024","publication_status":"published","oa":1,"project":[{"call_identifier":"H2020","name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183"},{"grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"Mathematics, Computer Science","call_identifier":"FWF"},{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"grant_number":"I02979-N35","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","name":"Persistence and stability of geometric complexes","call_identifier":"FWF"},{"name":"Learning and triangulating manifolds via collapses","grant_number":"M03073","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2"}],"file":[{"file_size":20886142,"date_updated":"2024-06-25T11:47:26Z","content_type":"application/pdf","relation":"main_file","date_created":"2024-06-25T11:47:26Z","file_id":"17171","success":1,"checksum":"6a2ddc8b51aa58f197a8b294750f1f8d","creator":"cfillmor","access_level":"open_access","file_name":"LIPIcs.SoCG.2024.11.pdf"}],"doi":"10.4230/LIPIcs.SoCG.2024.11","intvolume":"       293","file_date_updated":"2024-06-25T11:47:26Z","language":[{"iso":"eng"}],"ddc":["516"],"author":[{"last_name":"Attali","first_name":"Dominique","full_name":"Attali, Dominique"},{"first_name":"Hana","last_name":"Kourimska","orcid":"0000-0001-7841-0091","id":"D9B8E14C-3C26-11EA-98F5-1F833DDC885E","full_name":"Kourimska, Hana"},{"id":"35638A5C-AAC7-11E9-B0BF-5503E6697425","full_name":"Fillmore, Christopher D","first_name":"Christopher D","last_name":"Fillmore"},{"first_name":"Ishika","last_name":"Ghosh","id":"ee449b28-344d-11ef-a6d5-9ca430e9e9ff","full_name":"Ghosh, Ishika"},{"full_name":"Lieutier, André","last_name":"Lieutier","first_name":"André"},{"full_name":"Stephenson, Elizabeth R","id":"2D04F932-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6862-208X","first_name":"Elizabeth R","last_name":"Stephenson"},{"last_name":"Wintraecken","first_name":"Mathijs","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","full_name":"Wintraecken, Mathijs"}],"page":"11:1-11:19","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","_id":"17170","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Athens, Greece","start_date":"2024-06-11","end_date":"2024-06-14","name":"SoCG: Symposium on Computational Geometry"},"department":[{"_id":"GradSch"},{"_id":"HeEd"}],"ec_funded":1,"publication":"40th International Symposium on Computational Geometry","day":"06"},{"isi":1,"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.","arxiv":1,"date_published":"2024-01-24T00:00:00Z","article_processing_charge":"Yes","title":"On the complexity of algorithms with predictions for dynamic graph problems","volume":287,"month":"01","date_updated":"2025-09-09T12:11:33Z","quality_controlled":"1","external_id":{"isi":["001300389400062"],"arxiv":["2307.16771"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa_version":"Published Version","citation":{"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.","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.","mla":"Henzinger, Monika, et al. “On the Complexity of Algorithms with Predictions for Dynamic Graph Problems.” <i>15th Innovations in Theoretical Computer Science Conference</i>, vol. 287, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 62:1-62:25, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.62\">10.4230/LIPIcs.ITCS.2024.62</a>.","chicago":"Henzinger, Monika, Barna Saha, Martin P. Seybold, and Christopher Ye. “On the Complexity of Algorithms with Predictions for Dynamic Graph Problems.” In <i>15th Innovations in Theoretical Computer Science Conference</i>, 287:62:1-62:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.62\">https://doi.org/10.4230/LIPIcs.ITCS.2024.62</a>.","apa":"Henzinger, M., Saha, B., Seybold, M. P., &#38; Ye, C. (2024). On the complexity of algorithms with predictions for dynamic graph problems. In <i>15th Innovations in Theoretical Computer Science Conference</i> (Vol. 287, p. 62:1-62:25). Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.62\">https://doi.org/10.4230/LIPIcs.ITCS.2024.62</a>","ama":"Henzinger M, Saha B, Seybold MP, Ye C. On the complexity of algorithms with predictions for dynamic graph problems. In: <i>15th Innovations in Theoretical Computer Science Conference</i>. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:62:1-62:25. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.62\">10.4230/LIPIcs.ITCS.2024.62</a>","ieee":"M. Henzinger, B. Saha, M. P. Seybold, and C. Ye, “On the complexity of algorithms with predictions for dynamic graph problems,” in <i>15th Innovations in Theoretical Computer Science Conference</i>, Berkeley, CA, United States, 2024, vol. 287, p. 62:1-62:25."},"scopus_import":"1","abstract":[{"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.","lang":"eng"}],"status":"public","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773096"]},"type":"conference","OA_type":"gold","alternative_title":["LIPIcs"],"date_created":"2025-01-27T15:33:42Z","year":"2024","intvolume":"       287","file":[{"date_created":"2025-01-27T15:33:24Z","success":1,"file_id":"18929","checksum":"15085a5b3697a408b92a4a7a27293927","creator":"dernst","file_name":"2024_LIPICs_HenzingerMo.pdf","access_level":"open_access","file_size":1084372,"relation":"main_file","date_updated":"2025-01-27T15:33:24Z","content_type":"application/pdf"}],"project":[{"name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"name":"Efficient algorithms","grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"doi":"10.4230/LIPIcs.ITCS.2024.62","publication_status":"published","oa":1,"author":[{"orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Barna","last_name":"Saha","full_name":"Saha, Barna"},{"first_name":"Martin P.","last_name":"Seybold","full_name":"Seybold, Martin P."},{"full_name":"Ye, Christopher","last_name":"Ye","first_name":"Christopher"}],"language":[{"iso":"eng"}],"ddc":["000"],"file_date_updated":"2025-01-27T15:33:24Z","has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"page":"62:1-62:25","ec_funded":1,"conference":{"end_date":"2024-02-02","name":"ITCS: Innovations in Theoretical Computer Science","start_date":"2024-01-30","location":"Berkeley, CA, United States"},"department":[{"_id":"MoHe"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","_id":"18928","publication":"15th Innovations in Theoretical Computer Science Conference","corr_author":"1","OA_place":"publisher","day":"24"},{"alternative_title":["LIPIcs"],"date_created":"2024-03-24T23:00:59Z","year":"2024","intvolume":"       289","doi":"10.4230/LIPIcs.STACS.2024.34","project":[{"grant_number":"P31312","_id":"26611F5C-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Algorithms for Embeddings and Homotopy Theory"},{"name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413"}],"file":[{"date_created":"2024-03-25T07:44:30Z","file_id":"15175","success":1,"creator":"dernst","checksum":"0524d4189fd1ed08989546511343edf3","access_level":"open_access","file_name":"2024_LIPICs_Filakovsky.pdf","file_size":927290,"date_updated":"2024-03-25T07:44:30Z","content_type":"application/pdf","relation":"main_file"}],"oa":1,"publication_status":"published","author":[{"full_name":"Filakovský, Marek","id":"3E8AF77E-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","last_name":"Filakovský"},{"last_name":"Nakajima","first_name":"Tamio Vesa","full_name":"Nakajima, Tamio Vesa"},{"orcid":"0000-0003-1245-3456","first_name":"Jakub","last_name":"Opršal","full_name":"Opršal, Jakub","id":"ec596741-c539-11ec-b829-c79322a91242"},{"full_name":"Tasinato, Gianluca","id":"0433290C-AF8F-11E9-A4C7-F729E6697425","first_name":"Gianluca","last_name":"Tasinato"},{"first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli"}],"language":[{"iso":"eng"}],"ddc":["510"],"file_date_updated":"2024-03-25T07:44:30Z","has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"conference":{"end_date":"2024-03-14","name":"STACS: Symposium on Theoretical Aspects of Computer Science","start_date":"2024-03-12","location":"Clermont-Ferrand, France"},"ec_funded":1,"department":[{"_id":"UlWa"}],"_id":"15168","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication":"41st International Symposium on Theoretical Aspects of Computer Science","corr_author":"1","day":"01","isi":1,"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).","arxiv":1,"article_processing_charge":"No","date_published":"2024-03-01T00:00:00Z","title":"Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs","volume":289,"month":"03","quality_controlled":"1","date_updated":"2026-07-29T13:13:17Z","external_id":{"isi":["001300393400034"],"arxiv":["2312.12981"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa_version":"Published Version","abstract":[{"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).","lang":"eng"}],"article_number":"34","scopus_import":"1","citation":{"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 <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, Clermont-Ferrand, France, 2024, vol. 289.","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: <i>41st International Symposium on Theoretical Aspects of Computer Science</i>. Vol 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">10.4230/LIPIcs.STACS.2024.34</a>","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 <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, Vol. 289. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">https://doi.org/10.4230/LIPIcs.STACS.2024.34</a>.","apa":"Filakovský, M., Nakajima, T. V., Opršal, J., Tasinato, G., &#38; Wagner, U. (2024). Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs. In <i>41st International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 289). Clermont-Ferrand, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">https://doi.org/10.4230/LIPIcs.STACS.2024.34</a>","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.","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.","mla":"Filakovský, Marek, et al. “Hardness of Linearly Ordered 4-Colouring of 3-Colourable 3-Uniform Hypergraphs.” <i>41st International Symposium on Theoretical Aspects of Computer Science</i>, vol. 289, 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2024.34\">10.4230/LIPIcs.STACS.2024.34</a>."},"status":"public","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773119"]},"type":"conference","related_material":{"record":[{"relation":"later_version","id":"22247","status":"public"},{"id":"20339","relation":"dissertation_contains","status":"public"}]}},{"alternative_title":["LIPIcs"],"date_created":"2023-07-24T15:11:41Z","year":"2023","intvolume":"       261","oa":1,"publication_status":"published","project":[{"call_identifier":"H2020","name":"Vigilant Algorithmic Monitoring of Software","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093"}],"file":[{"date_updated":"2023-07-24T15:11:05Z","relation":"main_file","content_type":"application/pdf","file_size":859379,"file_id":"13293","success":1,"date_created":"2023-07-24T15:11:05Z","access_level":"open_access","file_name":"icalp23.pdf","checksum":"5d4c8932ef3450615a53b9bb15d92eb2","creator":"esarac"}],"doi":"10.4230/LIPIcs.ICALP.2023.129","language":[{"iso":"eng"}],"ddc":["000"],"author":[{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2985-7724","first_name":"Thomas A","last_name":"Henzinger"},{"full_name":"Kebis, Pavol","first_name":"Pavol","last_name":"Kebis"},{"full_name":"Mazzocchi, Nicolas Adrien","id":"b26baa86-3308-11ec-87b0-8990f34baa85","first_name":"Nicolas Adrien","last_name":"Mazzocchi"},{"last_name":"Sarac","first_name":"Naci E","full_name":"Sarac, Naci E","id":"8C6B42F8-C8E6-11E9-A03A-F2DCE5697425"}],"file_date_updated":"2023-07-24T15:11:05Z","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","page":"129:1--129:20","_id":"13292","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"GradSch"},{"_id":"ToHe"}],"conference":{"end_date":"2023-07-14","name":"ICALP: Automata, Languages and Programming","start_date":"2023-07-10","location":"Paderborn, Germany"},"ec_funded":1,"publication":"50th International Colloquium on Automata, Languages, and Programming","corr_author":"1","day":"05","arxiv":1,"article_processing_charge":"Yes","date_published":"2023-07-05T00:00:00Z","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","title":"Regular methods for operator precedence languages","volume":261,"month":"07","date_updated":"2025-07-10T11:50:41Z","quality_controlled":"1","external_id":{"arxiv":["2305.03447"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","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."}],"citation":{"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.","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.” <i>50th International Colloquium on Automata, Languages, and Programming</i>, vol. 261, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, p. 129:1--129:20, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.129\">10.4230/LIPIcs.ICALP.2023.129</a>.","chicago":"Henzinger, Thomas A, Pavol Kebis, Nicolas Adrien Mazzocchi, and Naci E Sarac. “Regular Methods for Operator Precedence Languages.” In <i>50th International Colloquium on Automata, Languages, and Programming</i>, 261:129:1--129:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.129\">https://doi.org/10.4230/LIPIcs.ICALP.2023.129</a>.","apa":"Henzinger, T. A., Kebis, P., Mazzocchi, N. A., &#38; Sarac, N. E. (2023). Regular methods for operator precedence languages. In <i>50th International Colloquium on Automata, Languages, and Programming</i> (Vol. 261, p. 129:1--129:20). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.129\">https://doi.org/10.4230/LIPIcs.ICALP.2023.129</a>","ama":"Henzinger TA, Kebis P, Mazzocchi NA, Sarac NE. Regular methods for operator precedence languages. In: <i>50th International Colloquium on Automata, Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023:129:1--129:20. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.129\">10.4230/LIPIcs.ICALP.2023.129</a>","ieee":"T. A. Henzinger, P. Kebis, N. A. Mazzocchi, and N. E. Sarac, “Regular methods for operator precedence languages,” in <i>50th International Colloquium on Automata, Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261, p. 129:1--129:20."},"scopus_import":"1","oa_version":"Published Version","status":"public","type":"conference","publication_identifier":{"isbn":["9783959772785"],"eissn":["1868-8969"]}},{"intvolume":"       272","publication_status":"published","oa":1,"project":[{"grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"doi":"10.4230/LIPIcs.MFCS.2023.15","file":[{"file_size":826843,"date_updated":"2023-10-09T09:19:11Z","content_type":"application/pdf","relation":"main_file","creator":"dernst","checksum":"402281b17ed669bbf149d0fdf68ac201","file_name":"2023_LIPIcsMFCS_Baier.pdf","access_level":"open_access","date_created":"2023-10-09T09:19:11Z","success":1,"file_id":"14418"}],"language":[{"iso":"eng"}],"ddc":["000"],"author":[{"last_name":"Baier","first_name":"Christel","full_name":"Baier, Christel"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"first_name":"Tobias","last_name":"Meggendorfer","orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","full_name":"Meggendorfer, Tobias"},{"last_name":"Piribauer","first_name":"Jakob","full_name":"Piribauer, Jakob"}],"file_date_updated":"2023-10-09T09:19:11Z","alternative_title":["LIPIcs"],"date_created":"2023-10-09T09:21:05Z","year":"2023","publication":"48th International Symposium on Mathematical Foundations of Computer Science","corr_author":"1","day":"21","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","_id":"14417","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"department":[{"_id":"KrCh"}],"conference":{"location":"Bordeaux, France","start_date":"2023-08-28","end_date":"2023-09-01","name":"MFCS: Mathematical Foundations of Computer Science"},"month":"08","date_updated":"2025-09-08T09:10:05Z","quality_controlled":"1","external_id":{"arxiv":["2307.06611"]},"arxiv":1,"article_processing_charge":"Yes","date_published":"2023-08-21T00:00:00Z","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.","title":"Entropic risk for turn-based stochastic games","volume":272,"status":"public","type":"conference","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959772921"]},"related_material":{"record":[{"id":"17474","relation":"later_version","status":"public"}]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","abstract":[{"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.","lang":"eng"}],"citation":{"ama":"Baier C, Chatterjee K, Meggendorfer T, Piribauer J. Entropic risk for turn-based stochastic games. In: <i>48th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 272. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2023.15\">10.4230/LIPIcs.MFCS.2023.15</a>","ieee":"C. Baier, K. Chatterjee, T. Meggendorfer, and J. Piribauer, “Entropic risk for turn-based stochastic games,” in <i>48th International Symposium on Mathematical Foundations of Computer Science</i>, Bordeaux, France, 2023, vol. 272.","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.","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.” <i>48th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 272, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2023.15\">10.4230/LIPIcs.MFCS.2023.15</a>.","chicago":"Baier, Christel, Krishnendu Chatterjee, Tobias Meggendorfer, and Jakob Piribauer. “Entropic Risk for Turn-Based Stochastic Games.” In <i>48th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 272. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2023.15\">https://doi.org/10.4230/LIPIcs.MFCS.2023.15</a>.","apa":"Baier, C., Chatterjee, K., Meggendorfer, T., &#38; Piribauer, J. (2023). Entropic risk for turn-based stochastic games. In <i>48th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 272). Bordeaux, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2023.15\">https://doi.org/10.4230/LIPIcs.MFCS.2023.15</a>"},"scopus_import":"1","article_number":"15","oa_version":"Published Version"},{"year":"2023","alternative_title":["LIPIcs"],"date_created":"2023-07-14T10:00:15Z","language":[{"iso":"eng"}],"ddc":["000"],"author":[{"full_name":"Boker, Udi","id":"31E297B6-F248-11E8-B48F-1D18A9856A87","last_name":"Boker","first_name":"Udi"},{"orcid":"0000-0002-2985-7724","last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Mazzocchi, Nicolas Adrien","id":"b26baa86-3308-11ec-87b0-8990f34baa85","first_name":"Nicolas Adrien","last_name":"Mazzocchi"},{"full_name":"Sarac, Naci E","id":"8C6B42F8-C8E6-11E9-A03A-F2DCE5697425","last_name":"Sarac","first_name":"Naci E"}],"file_date_updated":"2023-07-14T12:03:48Z","intvolume":"       279","oa":1,"publication_status":"published","doi":"10.4230/LIPIcs.CONCUR.2023.17","file":[{"date_created":"2023-07-14T12:03:48Z","file_id":"13224","success":1,"checksum":"d40e57a04448ea5c77d7e1cfb9590a81","creator":"esarac","access_level":"open_access","file_name":"CONCUR23.pdf","file_size":755529,"date_updated":"2023-07-14T12:03:48Z","content_type":"application/pdf","relation":"main_file"}],"project":[{"grant_number":"101020093","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software","call_identifier":"H2020"}],"_id":"13221","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"conference":{"location":"Antwerp, Belgium","end_date":"2023-09-23","name":"CONCUR: Conference on Concurrency Theory","start_date":"2023-09-18"},"department":[{"_id":"GradSch"},{"_id":"ToHe"}],"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"has_accepted_license":"1","day":"01","publication":"34th International Conference on Concurrency Theory","corr_author":"1","volume":279,"article_processing_charge":"No","arxiv":1,"date_published":"2023-09-01T00:00:00Z","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.","isi":1,"title":"Safety and liveness of quantitative automata","date_updated":"2026-07-27T12:48:18Z","quality_controlled":"1","external_id":{"isi":["001570542500017"],"arxiv":["2307.06016"]},"month":"09","scopus_import":"1","citation":{"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.","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.” <i>34th International Conference on Concurrency Theory</i>, vol. 279, 17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.17\">10.4230/LIPIcs.CONCUR.2023.17</a>.","chicago":"Boker, Udi, Thomas A Henzinger, Nicolas Adrien Mazzocchi, and Naci E Sarac. “Safety and Liveness of Quantitative Automata.” In <i>34th International Conference on Concurrency Theory</i>, Vol. 279. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.17\">https://doi.org/10.4230/LIPIcs.CONCUR.2023.17</a>.","apa":"Boker, U., Henzinger, T. A., Mazzocchi, N. A., &#38; Sarac, N. E. (2023). Safety and liveness of quantitative automata. In <i>34th International Conference on Concurrency Theory</i> (Vol. 279). Antwerp, Belgium: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.17\">https://doi.org/10.4230/LIPIcs.CONCUR.2023.17</a>","ama":"Boker U, Henzinger TA, Mazzocchi NA, Sarac NE. Safety and liveness of quantitative automata. In: <i>34th International Conference on Concurrency Theory</i>. Vol 279. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.17\">10.4230/LIPIcs.CONCUR.2023.17</a>","ieee":"U. Boker, T. A. Henzinger, N. A. Mazzocchi, and N. E. Sarac, “Safety and liveness of quantitative automata,” in <i>34th International Conference on Concurrency Theory</i>, Antwerp, Belgium, 2023, vol. 279."},"article_number":"17","abstract":[{"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.","lang":"eng"}],"oa_version":"Published Version","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","related_material":{"record":[{"status":"public","relation":"later_version","id":"20342"},{"status":"public","id":"20147","relation":"dissertation_contains"}]},"status":"public","type":"conference","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959772990"]}},{"external_id":{"isi":["001515590500015"],"arxiv":["2302.06420"]},"date_updated":"2026-07-29T12:56:51Z","quality_controlled":"1","month":"07","volume":268,"title":"Closure properties of general grammars - formally verified","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. ","isi":1,"article_processing_charge":"No","arxiv":1,"date_published":"2023-07-27T00:00:00Z","related_material":{"link":[{"url":"https://github.com/madvorak/grammars/tree/publish","relation":"software"}],"record":[{"id":"21393","relation":"dissertation_contains","status":"public"}]},"publication_identifier":{"isbn":["9783959772846"],"eissn":["1868-8969"]},"type":"conference","status":"public","oa_version":"Published Version","article_number":"15","citation":{"ieee":"M. Dvorak and J. Blanchette, “Closure properties of general grammars - formally verified,” in <i>14th International Conference on Interactive Theorem Proving</i>, Bialystok, Poland, 2023, vol. 268.","ama":"Dvorak M, Blanchette J. Closure properties of general grammars - formally verified. In: <i>14th International Conference on Interactive Theorem Proving</i>. Vol 268. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITP.2023.15\">10.4230/LIPIcs.ITP.2023.15</a>","apa":"Dvorak, M., &#38; Blanchette, J. (2023). Closure properties of general grammars - formally verified. In <i>14th International Conference on Interactive Theorem Proving</i> (Vol. 268). Bialystok, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITP.2023.15\">https://doi.org/10.4230/LIPIcs.ITP.2023.15</a>","chicago":"Dvorak, Martin, and Jasmin Blanchette. “Closure Properties of General Grammars - Formally Verified.” In <i>14th International Conference on Interactive Theorem Proving</i>, Vol. 268. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ITP.2023.15\">https://doi.org/10.4230/LIPIcs.ITP.2023.15</a>.","mla":"Dvorak, Martin, and Jasmin Blanchette. “Closure Properties of General Grammars - Formally Verified.” <i>14th International Conference on Interactive Theorem Proving</i>, vol. 268, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITP.2023.15\">10.4230/LIPIcs.ITP.2023.15</a>.","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.","short":"M. Dvorak, J. Blanchette, in:, 14th International Conference on Interactive Theorem Proving, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023."},"scopus_import":"1","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."}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2023-08-07T11:55:43Z","author":[{"id":"40ED02A8-C8B4-11E9-A9C0-453BE6697425","full_name":"Dvorak, Martin","first_name":"Martin","last_name":"Dvorak","orcid":"0000-0001-5293-214X"},{"full_name":"Blanchette, Jasmin","first_name":"Jasmin","last_name":"Blanchette"}],"language":[{"iso":"eng"}],"ddc":["000"],"doi":"10.4230/LIPIcs.ITP.2023.15","file":[{"content_type":"application/pdf","date_updated":"2023-08-07T11:55:43Z","relation":"main_file","file_size":715976,"access_level":"open_access","file_name":"2023_LIPIcS_Dvorak.pdf","checksum":"773a0197f05b67feaa6cb1e17ec3642d","creator":"dernst","file_id":"13982","success":1,"date_created":"2023-08-07T11:55:43Z"}],"oa":1,"publication_status":"published","intvolume":"       268","year":"2023","date_created":"2023-06-05T07:29:05Z","alternative_title":["LIPIcs"],"day":"27","corr_author":"1","publication":"14th International Conference on Interactive Theorem Proving","conference":{"location":"Bialystok, Poland","name":"ITP: Interactive Theorem Proving","end_date":"2023-08-04","start_date":"2023-07-31"},"department":[{"_id":"GradSch"},{"_id":"VlKo"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","_id":"13120","has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"}},{"date_created":"2022-08-11T14:35:52Z","alternative_title":["LIPIcs"],"year":"2022","oa":1,"extern":"1","publication_status":"published","doi":"10.4230/LIPIcs.SAND.2022.1","intvolume":"       221","language":[{"iso":"eng"}],"author":[{"full_name":"Hanauer, Kathrin","last_name":"Hanauer","first_name":"Kathrin"},{"last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"last_name":"Schulz","first_name":"Christian","full_name":"Schulz, Christian"}],"_id":"11808","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2022-03-28","end_date":"2022-03-30","name":"SAND: Symposium on Algorithmic Foundations of Dynamic Networks","location":"Virtual"},"publication":"1st Symposium on Algorithmic Foundations of Dynamic Networks","day":"29","title":"Recent advances in fully dynamic graph algorithms","date_published":"2022-04-29T00:00:00Z","article_processing_charge":"No","arxiv":1,"volume":221,"month":"04","external_id":{"arxiv":["2102.11169"]},"date_updated":"2024-11-06T08:23:49Z","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.SAND.2022.1"}],"article_number":"1","citation":{"apa":"Hanauer, K., Henzinger, M., &#38; Schulz, C. (2022). Recent advances in fully dynamic graph algorithms. In <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i> (Vol. 221). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.1\">https://doi.org/10.4230/LIPIcs.SAND.2022.1</a>","chicago":"Hanauer, Kathrin, Monika Henzinger, and Christian Schulz. “Recent Advances in Fully Dynamic Graph Algorithms.” In <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>, Vol. 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.1\">https://doi.org/10.4230/LIPIcs.SAND.2022.1</a>.","mla":"Hanauer, Kathrin, et al. “Recent Advances in Fully Dynamic Graph Algorithms.” <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>, vol. 221, 1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.1\">10.4230/LIPIcs.SAND.2022.1</a>.","short":"K. Hanauer, M. Henzinger, C. Schulz, in:, 1st Symposium on Algorithmic Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","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.","ieee":"K. Hanauer, M. Henzinger, and C. Schulz, “Recent advances in fully dynamic graph algorithms,” in <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>, Virtual, 2022, vol. 221.","ama":"Hanauer K, Henzinger M, Schulz C. Recent advances in fully dynamic graph algorithms. In: <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>. Vol 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.1\">10.4230/LIPIcs.SAND.2022.1</a>"},"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."}],"scopus_import":"1","oa_version":"Published Version","type":"conference","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959772242"]},"status":"public"}]