[{"oa_version":"Published Version","citation":{"ista":"Lill J, Petrova KH, Weber S. 2024. Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. 19th International Symposium on Parameterized and Exact Computation. IPEC: Symposium on Parameterized and Exact Computation, LIPIcs, vol. 321, 2.","ama":"Lill J, Petrova KH, Weber S. Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. In: <i>19th International Symposium on Parameterized and Exact Computation</i>. Vol 321. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.IPEC.2024.2\">10.4230/LIPIcs.IPEC.2024.2</a>","ieee":"J. Lill, K. H. Petrova, and S. Weber, “Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound,” in <i>19th International Symposium on Parameterized and Exact Computation</i>, Egham, United Kingdom, 2024, vol. 321.","apa":"Lill, J., Petrova, K. H., &#38; Weber, S. (2024). Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. In <i>19th International Symposium on Parameterized and Exact Computation</i> (Vol. 321). Egham, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.IPEC.2024.2\">https://doi.org/10.4230/LIPIcs.IPEC.2024.2</a>","mla":"Lill, Jonas, et al. “Linear-Time MaxCut in Multigraphs Parameterized above the Poljak-Turzík Bound.” <i>19th International Symposium on Parameterized and Exact Computation</i>, vol. 321, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.IPEC.2024.2\">10.4230/LIPIcs.IPEC.2024.2</a>.","chicago":"Lill, Jonas, Kalina H Petrova, and Simon Weber. “Linear-Time MaxCut in Multigraphs Parameterized above the Poljak-Turzík Bound.” In <i>19th International Symposium on Parameterized and Exact Computation</i>, Vol. 321. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.IPEC.2024.2\">https://doi.org/10.4230/LIPIcs.IPEC.2024.2</a>.","short":"J. Lill, K.H. Petrova, S. Weber, in:, 19th International Symposium on Parameterized and Exact Computation, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024."},"article_number":"2","type":"conference","abstract":[{"text":"MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdős bound states that any connected graph on n vertices with m edges contains a cut of size at least m/2+(n-1)/4. Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple connected graphs admits an FPT algorithm, where the parameter k is the difference between the desired cut size c and the lower bound given by the Edwards-Erdős bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run in parameterized linear time, i.e., f(k)⋅ O(m). We improve upon this result in two ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively, graphs with positive integer weights). Secondly, we change the parameter; instead of the difference to the Edwards-Erdős bound, we use the difference to the Poljak-Turzík bound. The Poljak-Turzík bound states that any weighted graph G has a cut of size at least (w(G))/2+(w_MSF(G))/4, where w(G) denotes the total weight of G, and w_MSF(G) denotes the weight of its minimum spanning forest. In connected simple graphs the two bounds are equivalent, but for multigraphs the Poljak-Turzík bound can be larger and thus yield a smaller parameter k. Our algorithm also runs in parameterized linear time, i.e., f(k)⋅ O(m+n).","lang":"eng"}],"title":"Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound","corr_author":"1","article_processing_charge":"Yes","month":"12","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.4230/LIPIcs.IPEC.2024.2","arxiv":1,"has_accepted_license":"1","department":[{"_id":"MaKw"}],"publication":"19th International Symposium on Parameterized and Exact Computation","publication_status":"published","year":"2024","date_created":"2025-01-05T23:01:57Z","author":[{"first_name":"Jonas","last_name":"Lill","full_name":"Lill, Jonas"},{"full_name":"Petrova, Kalina H","id":"554ff4e4-f325-11ee-b0c4-a10dbd523381","last_name":"Petrova","first_name":"Kalina H"},{"full_name":"Weber, Simon","last_name":"Weber","first_name":"Simon"}],"date_updated":"2026-01-05T13:46:07Z","related_material":{"record":[{"relation":"later_version","status":"public","id":"19603"}]},"external_id":{"isi":["001534851900002"],"arxiv":["2407.01071"]},"date_published":"2024-12-05T00:00:00Z","status":"public","language":[{"iso":"eng"}],"_id":"18758","ddc":["500"],"oa":1,"day":"05","acknowledgement":"Kalina Petrova: Swiss National Science Foundation, grant no. CRSII5 173721. This project\r\nhas received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413.\r\nSimon Weber: Swiss National Science Foundation under project no. 204320","conference":{"location":"Egham, United Kingdom","start_date":"2024-09-04","name":"IPEC: Symposium on Parameterized and Exact Computation","end_date":"2024-09-06"},"scopus_import":"1","file_date_updated":"2025-01-08T09:14:59Z","OA_type":"gold","isi":1,"intvolume":"       321","publication_identifier":{"isbn":["9783959773539"],"issn":["1868-8969"]},"alternative_title":["LIPIcs"],"file":[{"access_level":"open_access","success":1,"content_type":"application/pdf","relation":"main_file","file_name":"2024_LIPIcs_Lill.pdf","date_updated":"2025-01-08T09:14:59Z","file_id":"18775","date_created":"2025-01-08T09:14:59Z","creator":"dernst","checksum":"a64b9a0e41f7b867d25cb155825ccd53","file_size":927326}],"ec_funded":1,"OA_place":"publisher","volume":321},{"volume":286,"ec_funded":1,"file":[{"success":1,"access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2024-02-26T09:04:58Z","creator":"dernst","date_updated":"2024-02-26T09:04:58Z","file_id":"15028","file_name":"2024_LIPICs_Hirvonen.pdf","file_size":867363,"checksum":"4fc7eea6e4ba140b904781fc7df868ec"}],"alternative_title":["LIPIcs"],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773089"]},"isi":1,"intvolume":"       286","scopus_import":"1","file_date_updated":"2024-02-26T09:04:58Z","acknowledgement":"This work was partially funded by the Academy of Finland, grant 314888, the European Research Council CoG 863818 (ForM-SMArt), and the Austrian Science Fund (FWF) project I 4800-N (ADVISE). LS was supported by the Stochastic Analysis and Application Research Center (SAARC) under National Research Foundation of Korea grant NRF-2019R1A5A1028324.","conference":{"start_date":"2023-12-06","location":"Tokyo, Japan","end_date":"2023-12-08","name":"OPODIS: Conference on Principles of Distributed Systems"},"day":"18","oa":1,"_id":"15006","ddc":["000"],"status":"public","language":[{"iso":"eng"}],"external_id":{"isi":["001585185800011"],"arxiv":["2102.13457"]},"date_published":"2024-01-18T00:00:00Z","date_created":"2024-02-18T23:01:01Z","author":[{"full_name":"Hirvonen, Juho","first_name":"Juho","last_name":"Hirvonen"},{"first_name":"Laura","last_name":"Schmid","orcid":"0000-0002-6978-7329","id":"38B437DE-F248-11E8-B48F-1D18A9856A87","full_name":"Schmid, Laura"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Schmid, Stefan","first_name":"Stefan","last_name":"Schmid"}],"date_updated":"2025-12-02T13:38:16Z","year":"2024","publication_status":"published","has_accepted_license":"1","department":[{"_id":"KrCh"}],"publication":"27th International Conference on Principles of Distributed Systems","arxiv":1,"doi":"10.4230/LIPIcs.OPODIS.2023.11","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"month":"01","article_processing_charge":"No","corr_author":"1","title":"On the convergence time in graphical games: A locality-sensitive approach","abstract":[{"lang":"eng","text":"Graphical games are a useful framework for modeling the interactions of (selfish) agents who are connected via an underlying topology and whose behaviors influence each other. They have wide applications ranging from computer science to economics and biology. Yet, even though an agent’s payoff only depends on the actions of their direct neighbors in graphical games, computing the Nash equilibria and making statements about the convergence time of \"natural\" local dynamics in particular can be highly challenging. In this work, we present a novel approach for classifying complexity of Nash equilibria in graphical games by establishing a connection to local graph algorithms, a subfield of distributed computing. In particular, we make the observation that the equilibria of graphical games are equivalent to locally verifiable labelings (LVL) in graphs; vertex labelings which are verifiable with constant-round local algorithms. This connection allows us to derive novel lower bounds on the convergence time to equilibrium of best-response dynamics in graphical games. Since we establish that distributed convergence can sometimes be provably slow, we also introduce and give bounds on an intuitive notion of \"time-constrained\" inefficiency of best responses. We exemplify how our results can be used in the implementation of mechanisms that ensure convergence of best responses to a Nash equilibrium. Our results thus also give insight into the convergence of strategy-proof algorithms for graphical games, which is still not well understood."}],"type":"conference","citation":{"short":"J. Hirvonen, L. Schmid, K. Chatterjee, S. Schmid, in:, 27th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"Hirvonen, Juho, Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid. “On the Convergence Time in Graphical Games: A Locality-Sensitive Approach.” In <i>27th International Conference on Principles of Distributed Systems</i>, Vol. 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.11</a>.","apa":"Hirvonen, J., Schmid, L., Chatterjee, K., &#38; Schmid, S. (2024). On the convergence time in graphical games: A locality-sensitive approach. In <i>27th International Conference on Principles of Distributed Systems</i> (Vol. 286). Tokyo, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.11</a>","mla":"Hirvonen, Juho, et al. “On the Convergence Time in Graphical Games: A Locality-Sensitive Approach.” <i>27th International Conference on Principles of Distributed Systems</i>, vol. 286, 11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11\">10.4230/LIPIcs.OPODIS.2023.11</a>.","ama":"Hirvonen J, Schmid L, Chatterjee K, Schmid S. On the convergence time in graphical games: A locality-sensitive approach. In: <i>27th International Conference on Principles of Distributed Systems</i>. Vol 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.11\">10.4230/LIPIcs.OPODIS.2023.11</a>","ieee":"J. Hirvonen, L. Schmid, K. Chatterjee, and S. Schmid, “On the convergence time in graphical games: A locality-sensitive approach,” in <i>27th International Conference on Principles of Distributed Systems</i>, Tokyo, Japan, 2024, vol. 286.","ista":"Hirvonen J, Schmid L, Chatterjee K, Schmid S. 2024. On the convergence time in graphical games: A locality-sensitive approach. 27th International Conference on Principles of Distributed Systems. OPODIS: Conference on Principles of Distributed Systems, LIPIcs, vol. 286, 11."},"article_number":"11","oa_version":"Published Version"},{"isi":1,"intvolume":"       286","file":[{"file_size":1505994,"checksum":"2993e810a45e8c8056106834b07aea92","file_name":"2024_LIPICs_Alpos.pdf","creator":"dernst","date_created":"2024-02-26T10:16:57Z","file_id":"15031","date_updated":"2024-02-26T10:16:57Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","success":1}],"alternative_title":["LIPIcs"],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773089"]},"volume":286,"date_created":"2024-02-18T23:01:02Z","author":[{"first_name":"Orestis","last_name":"Alpos","full_name":"Alpos, Orestis"},{"last_name":"Amores-Sesar","first_name":"Ignacio","full_name":"Amores-Sesar, Ignacio"},{"full_name":"Cachin, Christian","first_name":"Christian","last_name":"Cachin"},{"last_name":"Yeo","first_name":"Michelle X","orcid":"0009-0001-3676-4809","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","full_name":"Yeo, Michelle X"}],"date_updated":"2025-12-02T13:38:53Z","publication_status":"published","year":"2024","status":"public","language":[{"iso":"eng"}],"date_published":"2024-01-18T00:00:00Z","external_id":{"arxiv":["2307.02954"],"isi":["001585185800012"]},"day":"18","oa":1,"_id":"15007","ddc":["000"],"scopus_import":"1","file_date_updated":"2024-02-26T10:16:57Z","conference":{"name":"OPODIS: Conference on Principles of Distributed Systems","end_date":"2023-12-08","location":"Tokyo, Japan","start_date":"2023-12-06"},"acknowledgement":"We would like to thank Krzysztof Pietrzak and Jovana Mićić for useful discussions. This work has been funded by the Swiss National Science Foundation (SNSF) under grant agreement Nr. 200021_188443 (Advanced Consensus Protocols).\r\n","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","doi":"10.4230/LIPIcs.OPODIS.2023.12","arxiv":1,"publication":"27th International Conference on Principles of Distributed Systems","has_accepted_license":"1","department":[{"_id":"KrPi"}],"article_number":"12","citation":{"ista":"Alpos O, Amores-Sesar I, Cachin C, Yeo MX. 2024. Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. 27th International Conference on Principles of Distributed Systems. OPODIS: Conference on Principles of Distributed Systems, LIPIcs, vol. 286, 12.","mla":"Alpos, Orestis, et al. “Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks.” <i>27th International Conference on Principles of Distributed Systems</i>, vol. 286, 12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">10.4230/LIPIcs.OPODIS.2023.12</a>.","apa":"Alpos, O., Amores-Sesar, I., Cachin, C., &#38; Yeo, M. X. (2024). Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. In <i>27th International Conference on Principles of Distributed Systems</i> (Vol. 286). Tokyo, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.12</a>","ieee":"O. Alpos, I. Amores-Sesar, C. Cachin, and M. X. Yeo, “Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks,” in <i>27th International Conference on Principles of Distributed Systems</i>, Tokyo, Japan, 2024, vol. 286.","ama":"Alpos O, Amores-Sesar I, Cachin C, Yeo MX. Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. In: <i>27th International Conference on Principles of Distributed Systems</i>. Vol 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">10.4230/LIPIcs.OPODIS.2023.12</a>","short":"O. Alpos, I. Amores-Sesar, C. Cachin, M.X. Yeo, in:, 27th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"Alpos, Orestis, Ignacio Amores-Sesar, Christian Cachin, and Michelle X Yeo. “Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks.” In <i>27th International Conference on Principles of Distributed Systems</i>, Vol. 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.12</a>."},"oa_version":"Published Version","title":"Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks","type":"conference","abstract":[{"lang":"eng","text":"Traditional blockchains grant the miner of a block full control not only over which transactions but also their order. This constitutes a major flaw discovered with the introduction of decentralized finance and allows miners to perform MEV attacks. In this paper, we address the issue of sandwich attacks by providing a construction that takes as input a blockchain protocol and outputs a new blockchain protocol with the same security but in which sandwich attacks are not profitable. Furthermore, our protocol is fully decentralized with no trusted third parties or heavy cryptography primitives and carries a linear increase in latency and minimum computation overhead."}],"month":"01","article_processing_charge":"No","corr_author":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"}},{"isi":1,"intvolume":"       287","alternative_title":["LIPIcs"],"file":[{"file_id":"15030","date_updated":"2024-02-26T10:10:48Z","date_created":"2024-02-26T10:10:48Z","creator":"dernst","file_name":"2024_LIPICs_Goranci.pdf","checksum":"b89716aae6a5599f187897e39de1e53a","file_size":1054754,"success":1,"access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"publication_identifier":{"isbn":["9783959773096"],"issn":["1868-8969"]},"volume":287,"ec_funded":1,"author":[{"full_name":"Goranci, Gramoz","first_name":"Gramoz","last_name":"Goranci"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger"},{"full_name":"Räcke, Harald","last_name":"Räcke","first_name":"Harald"},{"first_name":"Sushant","last_name":"Sachdeva","full_name":"Sachdeva, Sushant"},{"full_name":"Sricharan, A. R.","last_name":"Sricharan","first_name":"A. R."}],"date_created":"2024-02-18T23:01:02Z","date_updated":"2025-09-04T12:06:25Z","publication_status":"published","year":"2024","status":"public","language":[{"iso":"eng"}],"external_id":{"arxiv":["2303.02491"],"isi":["001300389400055"]},"date_published":"2024-01-24T00:00:00Z","day":"24","ddc":["000"],"_id":"15008","oa":1,"scopus_import":"1","file_date_updated":"2024-02-26T10:10:48Z","conference":{"end_date":"2024-02-02","name":"ITCS: Innovations in Theoretical Computer Science","start_date":"2024-01-30","location":"Berkeley, CA, United States"},"acknowledgement":"Monika Henzinger and A. R. Sricharan: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation\r\nprogramme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) project Z\r\n422-N, project I 5982-N, and project P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nHarald Räcke: Research supported by German Research Foundation (DFG), grant 470029389\r\n(FlexNets), 2021-2024.\r\nSushant Sachdeva: SS’s work is supported by an Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant RGPIN-2018-06398 and a Sloan Research Fellowship.","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","quality_controlled":"1","doi":"10.4230/LIPIcs.ITCS.2024.55","arxiv":1,"publication":"15th Innovations in Theoretical Computer Science Conference","has_accepted_license":"1","department":[{"_id":"MoHe"}],"citation":{"short":"G. Goranci, M. Henzinger, H. Räcke, S. Sachdeva, A.R. Sricharan, in:, 15th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"Goranci, Gramoz, Monika Henzinger, Harald Räcke, Sushant Sachdeva, and A. R. Sricharan. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.” In <i>15th Innovations in Theoretical Computer Science Conference</i>, Vol. 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.55\">https://doi.org/10.4230/LIPIcs.ITCS.2024.55</a>.","mla":"Goranci, Gramoz, et al. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.” <i>15th Innovations in Theoretical Computer Science Conference</i>, vol. 287, 55, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.55\">10.4230/LIPIcs.ITCS.2024.55</a>.","apa":"Goranci, G., Henzinger, M., Räcke, H., Sachdeva, S., &#38; Sricharan, A. R. (2024). Electrical flows for polylogarithmic competitive oblivious routing. In <i>15th Innovations in Theoretical Computer Science Conference</i> (Vol. 287). Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.55\">https://doi.org/10.4230/LIPIcs.ITCS.2024.55</a>","ama":"Goranci G, Henzinger M, Räcke H, Sachdeva S, Sricharan AR. Electrical flows for polylogarithmic competitive oblivious routing. In: <i>15th Innovations in Theoretical Computer Science Conference</i>. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.55\">10.4230/LIPIcs.ITCS.2024.55</a>","ieee":"G. Goranci, M. Henzinger, H. Räcke, S. Sachdeva, and A. R. Sricharan, “Electrical flows for polylogarithmic competitive oblivious routing,” in <i>15th Innovations in Theoretical Computer Science Conference</i>, Berkeley, CA, United States, 2024, vol. 287.","ista":"Goranci G, Henzinger M, Räcke H, Sachdeva S, Sricharan AR. 2024. Electrical flows for polylogarithmic competitive oblivious routing. 15th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 287, 55."},"article_number":"55","oa_version":"Published Version","title":"Electrical flows for polylogarithmic competitive oblivious routing","abstract":[{"text":"Oblivious routing is a well-studied paradigm that uses static precomputed routing tables for selecting routing paths within a network. Existing oblivious routing schemes with polylogarithmic competitive ratio for general networks are tree-based, in the sense that routing is performed according to a convex combination of trees. However, this restriction to trees leads to a construction that has time quadratic in the size of the network and does not parallelize well. \r\nIn this paper we study oblivious routing schemes based on electrical routing. In particular, we show that general networks with n vertices and m edges admit a routing scheme that has competitive ratio O(log² n) and consists of a convex combination of only O(√m) electrical routings. This immediately leads to an improved construction algorithm with time Õ(m^{3/2}) that can also be implemented in parallel with Õ(√m) depth.","lang":"eng"}],"type":"conference","article_processing_charge":"No","month":"01","corr_author":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"project":[{"grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}]},{"project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","month":"12","article_processing_charge":"No","corr_author":"1","title":"Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms","type":"conference","abstract":[{"text":"We study two-player zero-sum concurrent stochastic games with finite state and action space played for an infinite number of steps. In every step, the two players simultaneously and independently choose an action. Given the current state and the chosen actions, the next state is obtained according to a stochastic transition function. An objective is a measurable function on plays (or infinite trajectories) of the game, and the value for an objective is the maximal expectation that the player can guarantee against the adversarial player. We consider: (a) stateful-discounted objectives, which are similar to the classical discounted-sum objectives, but states are associated with different discount factors rather than a single discount factor; and (b) parity objectives, which are a canonical representation for ω-regular objectives. For stateful-discounted objectives, given an ordering of the discount factors, the limit value is the limit of the value of the stateful-discounted objectives, as the discount factors approach zero according to the given order.\r\nThe computational problem we consider is the approximation of the value within an arbitrary\r\nadditive error. The above problem is known to be in EXPSPACE for the limit value of statefuldiscounted objectives and in PSPACE for parity objectives. The best-known algorithms for both the above problems are at least exponential time, with an exponential dependence on the number of states and actions. Our main results for the value approximation problem for the limit value of stateful-discounted objectives and parity objectives are as follows: (a) we establish TFNP[NP] complexity; and (b) we present algorithms that improve the dependency on the number of actions in the exponent from linear to logarithmic. In particular, if the number of states is constant, our algorithms run in polynomial time.","lang":"eng"}],"citation":{"ama":"Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. In: <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>. Vol 323. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">10.4230/LIPIcs.FSTTCS.2024.5</a>","ieee":"A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and J. Svoboda, “Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms,” in <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Gujarat, India, 2024, vol. 323.","apa":"Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., &#38; Svoboda, J. (2024). Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. In <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i> (Vol. 323). Gujarat, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5</a>","mla":"Asadi, Ali, et al. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives: Complexity and Algorithms.” <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, vol. 323, 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">10.4230/LIPIcs.FSTTCS.2024.5</a>.","ista":"Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. 2024. Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 323, 5.","chicago":"Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Jakub Svoboda. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives: Complexity and Algorithms.” In <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Vol. 323. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5</a>.","short":"A. Asadi, K. Chatterjee, R.J. Saona Urmeneta, J. Svoboda, in:, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024."},"article_number":"5","oa_version":"Published Version","department":[{"_id":"KrCh"}],"has_accepted_license":"1","publication":"44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","arxiv":1,"doi":"10.4230/LIPIcs.FSTTCS.2024.5","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","scopus_import":"1","file_date_updated":"2025-01-08T09:49:31Z","acknowledgement":"This research was partially supported by ERC CoG 863818 (ForM-SMArt), Austrian\r\nScience Fund (FWF) 10.55776/COE12, and French Agence Nationale de la Recherche (ANR)\r\nANR-21-CE40-0020 (CONVERGENCE project)","conference":{"start_date":"2024-12-16","location":"Gujarat, India","end_date":"2024-12-18","name":"FSTTCS: Foundations of Software Technology and Theoretical Computer Science"},"day":"05","_id":"17099","ddc":["000"],"oa":1,"language":[{"iso":"eng"}],"status":"public","date_published":"2024-12-05T00:00:00Z","external_id":{"isi":["001537516500005"],"arxiv":["2405.02486"]},"date_updated":"2025-12-02T13:40:52Z","author":[{"id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","full_name":"Asadi, Ali","first_name":"Ali","last_name":"Asadi"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee"},{"last_name":"Saona Urmeneta","first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J","orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425"},{"first_name":"Jakub","last_name":"Svoboda","full_name":"Svoboda, Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","orcid":"0000-0002-1419-3267"}],"date_created":"2024-06-03T07:44:27Z","year":"2024","publication_status":"published","volume":323,"OA_place":"publisher","ec_funded":1,"file":[{"date_updated":"2025-01-08T09:49:31Z","file_id":"18777","date_created":"2025-01-08T09:49:31Z","creator":"dernst","file_name":"2024_LIPIcs_Asadi.pdf","checksum":"5b544ab4692b93300b404435c036ddd4","file_size":847960,"success":1,"access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"alternative_title":["LIPIcs"],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773553"]},"isi":1,"intvolume":"       323","OA_type":"gold"},{"file":[{"checksum":"b40ff456c19294adb5d9613fcfd751c6","file_size":1612558,"file_name":"2024_LIPICS_Kourimska.pdf","file_id":"17150","date_updated":"2024-06-17T08:33:40Z","creator":"dernst","date_created":"2024-06-17T08:33:40Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","success":1}],"alternative_title":["LIPIcs"],"publication_identifier":{"isbn":["9783959773164"],"issn":["1868-8969"]},"volume":293,"ec_funded":1,"intvolume":"       293","day":"01","ddc":["510"],"_id":"17144","oa":1,"scopus_import":"1","file_date_updated":"2024-06-17T08:33:40Z","conference":{"location":"Athens, Greece","name":"SoCG: Symposium on Computational Geometry","end_date":"2024-06-14"},"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\nSupported 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ô d'Azur.\r\nWe are greatly indebted to Fred Chazal for sharing his insights. We further thank Erin Chambers, Christopher Fillmore, and Elizabeth Stephenson for early discussions and all members of the Edelsbrunner group (Institute of Science and Technology Austria) and the Datashape team (Inria) for the atmosphere in which this research was conducted.","date_updated":"2025-04-15T07:16:58Z","date_created":"2024-06-16T22:01:06Z","author":[{"first_name":"Hana","last_name":"Kourimska","full_name":"Kourimska, Hana","id":"D9B8E14C-3C26-11EA-98F5-1F833DDC885E","orcid":"0000-0001-7841-0091"},{"first_name":"André","last_name":"Lieutier","full_name":"Lieutier, André"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs","last_name":"Wintraecken","first_name":"Mathijs"}],"publication_status":"published","year":"2024","language":[{"iso":"eng"}],"status":"public","date_published":"2024-06-01T00:00:00Z","external_id":{"arxiv":["2212.01118"]},"arxiv":1,"department":[{"_id":"HeEd"}],"has_accepted_license":"1","publication":"40th International Symposium on Computational Geometry","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","doi":"10.4230/LIPIcs.SoCG.2024.69","month":"06","article_processing_charge":"No","project":[{"grant_number":"788183","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Alpha Shape Theory Extended"},{"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"},{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"},{"name":"Learning and triangulating manifolds via collapses","grant_number":"M03073","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"ista":"Kourimska H, Lieutier A, Wintraecken M. 2024. The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 293, 69.","apa":"Kourimska, H., Lieutier, A., &#38; Wintraecken, M. (2024). The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms. In <i>40th International Symposium on Computational Geometry</i> (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.69\">https://doi.org/10.4230/LIPIcs.SoCG.2024.69</a>","mla":"Kourimska, Hana, et al. “The Medial Axis of Any Closed Bounded Set Is Lipschitz Stable with Respect to the Hausdorff Distance Under Ambient Diffeomorphisms.” <i>40th International Symposium on Computational Geometry</i>, vol. 293, 69, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.69\">10.4230/LIPIcs.SoCG.2024.69</a>.","ieee":"H. Kourimska, A. Lieutier, and M. Wintraecken, “The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms,” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293.","ama":"Kourimska H, Lieutier A, Wintraecken M. The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms. In: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.69\">10.4230/LIPIcs.SoCG.2024.69</a>","short":"H. Kourimska, A. Lieutier, M. Wintraecken, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"Kourimska, Hana, André Lieutier, and Mathijs Wintraecken. “The Medial Axis of Any Closed Bounded Set Is Lipschitz Stable with Respect to the Hausdorff Distance Under Ambient Diffeomorphisms.” In <i>40th International Symposium on Computational Geometry</i>, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.69\">https://doi.org/10.4230/LIPIcs.SoCG.2024.69</a>."},"article_number":"69","oa_version":"Published Version","title":"The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms","type":"conference","abstract":[{"text":"We prove that the medial axis of closed sets is Hausdorff stable in the following sense: Let 𝒮 ⊆ ℝ^d be a fixed closed set that contains a bounding sphere. That is, the bounding sphere is part of the set 𝒮. Consider the space of C^{1,1} diffeomorphisms of ℝ^d to itself, which keep the bounding sphere invariant. The map from this space of diffeomorphisms (endowed with a Banach norm) to the space of closed subsets of ℝ^d (endowed with the Hausdorff distance), mapping a diffeomorphism F to the closure of the medial axis of F(𝒮), is Lipschitz. This extends a previous stability result of Chazal and Soufflet on the stability of the medial axis of C² manifolds under C² ambient diffeomorphisms.","lang":"eng"}]},{"volume":293,"alternative_title":["LIPIcs"],"file":[{"date_updated":"2024-06-17T08:40:04Z","file_id":"17151","date_created":"2024-06-17T08:40:04Z","creator":"dernst","file_name":"2024_LIPICS_Rote.pdf","checksum":"fbad1de06383a6b7e8a1cb3e8c7205ce","file_size":1430896,"success":1,"access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773164"]},"intvolume":"       293","file_date_updated":"2024-06-17T08:40:04Z","scopus_import":"1","conference":{"end_date":"2024-06-14","name":"SoCG: Symposium on Computational Geometry","start_date":"2024-06-11","location":"Athens, Greece"},"acknowledgement":"Part of this work was done while G.R. enjoyed the hospitality of the Institute of Science and Technology Austria (ISTA) as a visiting professor during his sabbatical in the winter semester 2022/23.","day":"01","_id":"17145","ddc":["510"],"oa":1,"language":[{"iso":"eng"}],"status":"public","date_published":"2024-06-01T00:00:00Z","external_id":{"arxiv":["2402.15787"]},"date_updated":"2024-06-17T08:41:56Z","author":[{"full_name":"Rote, Günter","first_name":"Günter","last_name":"Rote"},{"first_name":"Moritz","last_name":"Rüber","full_name":"Rüber, Moritz"},{"id":"f86f7148-b140-11ec-9577-95435b8df824","full_name":"Saghafian, Morteza","last_name":"Saghafian","first_name":"Morteza"}],"date_created":"2024-06-16T22:01:06Z","year":"2024","publication_status":"published","department":[{"_id":"HeEd"}],"has_accepted_license":"1","publication":"40th International Symposium on Computational Geometry","arxiv":1,"doi":"10.4230/LIPIcs.SoCG.2024.76","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_processing_charge":"No","month":"06","title":"Grid peeling of parabolas","abstract":[{"lang":"eng","text":"Grid peeling is the process of repeatedly removing the convex hull vertices of the grid points that lie inside a given convex curve. It has been conjectured that, for a more and more refined grid, grid peeling converges to a continuous process, the affine curve-shortening flow, which deforms the curve based on the curvature. We prove this conjecture for one class of curves, parabolas with a vertical axis, and we determine the value of the constant factor in the formula that relates the two processes."}],"type":"conference","article_number":"76","citation":{"short":"G. Rote, M. Rüber, M. Saghafian, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"Rote, Günter, Moritz Rüber, and Morteza Saghafian. “Grid Peeling of Parabolas.” In <i>40th International Symposium on Computational Geometry</i>, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.76\">https://doi.org/10.4230/LIPIcs.SoCG.2024.76</a>.","ista":"Rote G, Rüber M, Saghafian M. 2024. Grid peeling of parabolas. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 293, 76.","apa":"Rote, G., Rüber, M., &#38; Saghafian, M. (2024). Grid peeling of parabolas. In <i>40th International Symposium on Computational Geometry</i> (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.76\">https://doi.org/10.4230/LIPIcs.SoCG.2024.76</a>","mla":"Rote, Günter, et al. “Grid Peeling of Parabolas.” <i>40th International Symposium on Computational Geometry</i>, vol. 293, 76, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.76\">10.4230/LIPIcs.SoCG.2024.76</a>.","ieee":"G. Rote, M. Rüber, and M. Saghafian, “Grid peeling of parabolas,” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293.","ama":"Rote G, Rüber M, Saghafian M. Grid peeling of parabolas. In: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.76\">10.4230/LIPIcs.SoCG.2024.76</a>"},"oa_version":"Published Version"},{"volume":293,"ec_funded":1,"file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","success":1,"checksum":"5442d44fb89d77477a87668d6e61aac9","file_size":766562,"file_name":"2024_LIPICS_Edelsbrunner.pdf","file_id":"17152","date_updated":"2024-06-17T08:46:33Z","creator":"dernst","date_created":"2024-06-17T08:46:33Z"}],"alternative_title":["LIPIcs"],"publication_identifier":{"isbn":["9783959773164"],"issn":["1868-8969"]},"intvolume":"       293","file_date_updated":"2024-06-17T08:46:33Z","scopus_import":"1","conference":{"name":"SoCG: Symposium on Computational Geometry","end_date":"2024-06-14","location":"Athens, Greece","start_date":"2024-06-11"},"acknowledgement":"The first author is supported by the European Research Council (ERC), grant no. 788183, and by the DFG Collaborative Research Center TRR 109, Austrian Science Fund (FWF), grant no. {I 02979-N35.} The second author is supported by the European Research Council (ERC), grant \"GeoScape\" and by the Hungarian Science Foundation (NKFIH), grant K-131529. Both authors are supported by the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.\r\nThe authors thank Matt Kahle for communicating the question about extremal Čech complexes, Ben Schweinhart for early discussions on the linked circles construction in three dimensions, and Gábor Tardos for helpful remarks and suggestions.","day":"01","_id":"17146","ddc":["510"],"oa":1,"language":[{"iso":"eng"}],"status":"public","related_material":{"record":[{"id":"20657","status":"public","relation":"later_version"}]},"date_published":"2024-06-01T00:00:00Z","external_id":{"arxiv":["2310.14801"]},"date_updated":"2025-12-01T15:19:20Z","author":[{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"},{"last_name":"Pach","first_name":"János","full_name":"Pach, János","id":"E62E3130-B088-11EA-B919-BF823C25FEA4"}],"date_created":"2024-06-16T22:01:06Z","year":"2024","publication_status":"published","department":[{"_id":"HeEd"}],"has_accepted_license":"1","publication":"40th International Symposium on Computational Geometry","arxiv":1,"doi":"10.4230/LIPIcs.SoCG.2024.53","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","project":[{"_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183","name":"Alpha Shape Theory Extended","call_identifier":"H2020"},{"_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35","name":"Persistence and stability of geometric complexes","call_identifier":"FWF"},{"grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"Mathematics, Computer Science","call_identifier":"FWF"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_processing_charge":"No","month":"06","title":"Maximum Betti numbers of Čech complexes","abstract":[{"lang":"eng","text":"The Upper Bound Theorem for convex polytopes implies that the p-th Betti number of the Čech complex of any set of N points in ℝ^d and any radius satisfies β_p = O(N^m), with m = min{p+1, ⌈d/2⌉}. We construct sets in even and odd dimensions, which prove that this upper bound is asymptotically tight. For example, we describe a set of N = 2(n+1) points in ℝ³ and two radii such that the first Betti number of the Čech complex at one radius is (n+1)² - 1, and the second Betti number of the Čech complex at the other radius is n². In particular, there is an arrangement of n contruent balls in ℝ³ that enclose a quadratic number of voids, which answers a long-standing open question in computational geometry."}],"type":"conference","citation":{"apa":"Edelsbrunner, H., &#38; Pach, J. (2024). Maximum Betti numbers of Čech complexes. In <i>40th International Symposium on Computational Geometry</i> (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.53\">https://doi.org/10.4230/LIPIcs.SoCG.2024.53</a>","mla":"Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.” <i>40th International Symposium on Computational Geometry</i>, vol. 293, 53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.53\">10.4230/LIPIcs.SoCG.2024.53</a>.","ieee":"H. Edelsbrunner and J. Pach, “Maximum Betti numbers of Čech complexes,” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293.","ama":"Edelsbrunner H, Pach J. Maximum Betti numbers of Čech complexes. In: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.53\">10.4230/LIPIcs.SoCG.2024.53</a>","ista":"Edelsbrunner H, Pach J. 2024. Maximum Betti numbers of Čech complexes. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 293, 53.","short":"H. Edelsbrunner, J. Pach, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.” In <i>40th International Symposium on Computational Geometry</i>, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.53\">https://doi.org/10.4230/LIPIcs.SoCG.2024.53</a>."},"article_number":"53","oa_version":"Published Version"},{"file":[{"relation":"main_file","content_type":"application/pdf","success":1,"access_level":"open_access","file_size":1391381,"checksum":"cc6bb89be0eaa404a6ce019392cd293e","creator":"dernst","date_created":"2024-07-29T11:15:59Z","date_updated":"2024-07-29T11:15:59Z","file_id":"17341","file_name":"2024_LIPICs_Cano.pdf"}],"alternative_title":["LIPIcs"],"publication_identifier":{"isbn":["9783959773232"],"issn":["1868-8969"]},"volume":299,"ec_funded":1,"isi":1,"intvolume":"       299","day":"01","ddc":["000"],"_id":"17327","oa":1,"file_date_updated":"2024-07-29T11:15:59Z","scopus_import":"1","acknowledgement":"This work is partly supported by the European Research Council under Grant No.: ERC2020-AdG 101020093. It is also partially supported by the State Government of Styria, Austria –\r\nDepartment Zukunftsfonds Steiermark.","conference":{"location":"Tallinn, Estonia","start_date":"2024-07-10","name":"FSCD: Conference on Formal Structures for Computation and Deduction","end_date":"2024-07-13"},"author":[{"full_name":"Cano, Filip","last_name":"Cano","first_name":"Filip"},{"orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","last_name":"Henzinger","first_name":"Thomas A"},{"full_name":"Könighofer, Bettina","first_name":"Bettina","last_name":"Könighofer"},{"orcid":"0000-0001-8974-2542","id":"8121a2d0-dc85-11ea-9058-af578f3b4515","full_name":"Kueffner, Konstantin","first_name":"Konstantin","last_name":"Kueffner"},{"first_name":"Kaushik","last_name":"Mallik","full_name":"Mallik, Kaushik","id":"0834ff3c-6d72-11ec-94e0-b5b0a4fb8598","orcid":"0000-0001-9864-7475"}],"date_created":"2024-07-28T22:01:09Z","date_updated":"2025-12-02T13:43:50Z","year":"2024","publication_status":"published","status":"public","language":[{"iso":"eng"}],"date_published":"2024-07-01T00:00:00Z","external_id":{"isi":["001587746100002"]},"has_accepted_license":"1","publication":"9th International Conference on Formal Structures for Computation and Deduction","department":[{"_id":"ToHe"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","doi":"10.4230/LIPIcs.FSCD.2024.2","month":"07","article_processing_charge":"Yes","corr_author":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"project":[{"name":"Vigilant Algorithmic Monitoring of Software","call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093"}],"citation":{"chicago":"Cano, Filip, Thomas A Henzinger, Bettina Könighofer, Konstantin Kueffner, and Kaushik Mallik. “Abstraction-Based Decision Making for Statistical Properties.” In <i>9th International Conference on Formal Structures for Computation and Deduction</i>, Vol. 299. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.FSCD.2024.2\">https://doi.org/10.4230/LIPIcs.FSCD.2024.2</a>.","short":"F. Cano, T.A. Henzinger, B. Könighofer, K. Kueffner, K. Mallik, in:, 9th International Conference on Formal Structures for Computation and Deduction, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ista":"Cano F, Henzinger TA, Könighofer B, Kueffner K, Mallik K. 2024. Abstraction-based decision making for statistical properties. 9th International Conference on Formal Structures for Computation and Deduction. FSCD: Conference on Formal Structures for Computation and Deduction, LIPIcs, vol. 299, 2.","ieee":"F. Cano, T. A. Henzinger, B. Könighofer, K. Kueffner, and K. Mallik, “Abstraction-based decision making for statistical properties,” in <i>9th International Conference on Formal Structures for Computation and Deduction</i>, Tallinn, Estonia, 2024, vol. 299.","ama":"Cano F, Henzinger TA, Könighofer B, Kueffner K, Mallik K. Abstraction-based decision making for statistical properties. In: <i>9th International Conference on Formal Structures for Computation and Deduction</i>. Vol 299. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSCD.2024.2\">10.4230/LIPIcs.FSCD.2024.2</a>","mla":"Cano, Filip, et al. “Abstraction-Based Decision Making for Statistical Properties.” <i>9th International Conference on Formal Structures for Computation and Deduction</i>, vol. 299, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSCD.2024.2\">10.4230/LIPIcs.FSCD.2024.2</a>.","apa":"Cano, F., Henzinger, T. A., Könighofer, B., Kueffner, K., &#38; Mallik, K. (2024). Abstraction-based decision making for statistical properties. In <i>9th International Conference on Formal Structures for Computation and Deduction</i> (Vol. 299). Tallinn, Estonia: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FSCD.2024.2\">https://doi.org/10.4230/LIPIcs.FSCD.2024.2</a>"},"article_number":"2","oa_version":"Published Version","title":"Abstraction-based decision making for statistical properties","abstract":[{"text":"Sequential decision-making in probabilistic environments is a fundamental problem with many applications in AI and economics. In this paper, we present an algorithm for synthesizing sequential decision-making agents that optimize statistical properties such as maximum and average response times. In the general setting of sequential decision-making, the environment is modeled as a random process that generates inputs. The agent responds to each input, aiming to maximize rewards and minimize costs within a specified time horizon. The corresponding synthesis problem is known to be PSPACE-hard. We consider the special case where the input distribution, reward, and cost depend on input-output statistics specified by counter automata. For such problems, this paper presents the first PTIME synthesis algorithms. We introduce the notion of statistical abstraction, which clusters statistically indistinguishable input-output sequences into equivalence classes. This abstraction allows for a dynamic programming algorithm whose complexity grows polynomially with the considered horizon, making the statistical case exponentially more efficient than the general case. We evaluate our algorithm on three different application scenarios of a client-server protocol, where multiple clients compete via bidding to gain access to the service offered by the server. The synthesized policies optimize profit while guaranteeing that none of the server’s clients is disproportionately starved of the service.","lang":"eng"}],"type":"conference"},{"date_updated":"2025-09-08T08:31:53Z","author":[{"full_name":"Resch, Nicolas","last_name":"Resch","first_name":"Nicolas"},{"last_name":"Yuan","first_name":"Chen","full_name":"Yuan, Chen"},{"full_name":"Zhang, Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","orcid":"0000-0002-6465-6258","first_name":"Yihan","last_name":"Zhang"}],"date_created":"2023-08-20T22:01:13Z","year":"2023","publication_status":"published","language":[{"iso":"eng"}],"status":"public","external_id":{"arxiv":["2210.07754"]},"date_published":"2023-07-01T00:00:00Z","related_material":{"record":[{"id":"17330","status":"public","relation":"later_version"}]},"day":"01","_id":"14083","ddc":["000"],"oa":1,"scopus_import":"1","file_date_updated":"2023-08-21T07:23:18Z","acknowledgement":"Nicolas Resch: Research supported in part by ERC H2020 grant No.74079 (ALGSTRONGCRYPTO). Chen Yuan: Research supported in part by the National Key Research and Development Projects under Grant 2022YFA1004900 and Grant 2021YFE0109900, the National Natural Science Foundation of China under Grant 12101403 and Grant 12031011.\r\nAcknowledgements YZ is grateful to Shashank Vatedka, Diyuan Wu and Fengxing Zhu for inspiring discussions.","conference":{"start_date":"2023-07-10","location":"Paderborn, Germany","end_date":"2023-07-14","name":"ICALP: Automata, Languages and Programming"},"intvolume":"       261","alternative_title":["LIPIcs"],"file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","success":1,"checksum":"a449143fec3fbebb092cb8ef3b53c226","file_size":1141497,"file_name":"2023_LIPIcsICALP_Resch.pdf","date_updated":"2023-08-21T07:23:18Z","file_id":"14091","creator":"dernst","date_created":"2023-08-21T07:23:18Z"}],"publication_identifier":{"isbn":["9783959772785"],"issn":["1868-8969"]},"volume":261,"citation":{"ieee":"N. Resch, C. Yuan, and Y. Zhang, “Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery,” in <i>50th International Colloquium on Automata, Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261.","ama":"Resch N, Yuan C, Zhang Y. Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. In: <i>50th International Colloquium on Automata, Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.99\">10.4230/LIPIcs.ICALP.2023.99</a>","apa":"Resch, N., Yuan, C., &#38; Zhang, Y. (2023). Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. In <i>50th International Colloquium on Automata, Languages, and Programming</i> (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.99\">https://doi.org/10.4230/LIPIcs.ICALP.2023.99</a>","mla":"Resch, Nicolas, et al. “Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery.” <i>50th International Colloquium on Automata, Languages, and Programming</i>, vol. 261, 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.99\">10.4230/LIPIcs.ICALP.2023.99</a>.","ista":"Resch N, Yuan C, Zhang Y. 2023. Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 99.","chicago":"Resch, Nicolas, Chen Yuan, and Yihan Zhang. “Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery.” In <i>50th International Colloquium on Automata, Languages, and Programming</i>, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.99\">https://doi.org/10.4230/LIPIcs.ICALP.2023.99</a>.","short":"N. Resch, C. Yuan, Y. Zhang, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023."},"article_number":"99","oa_version":"Published Version","title":"Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery","abstract":[{"lang":"eng","text":"In this work we consider the list-decodability and list-recoverability of arbitrary q-ary codes, for all integer values of q ≥ 2. A code is called (p,L)_q-list-decodable if every radius pn Hamming ball contains less than L codewords; (p,𝓁,L)_q-list-recoverability is a generalization where we place radius pn Hamming balls on every point of a combinatorial rectangle with side length 𝓁 and again stipulate that there be less than L codewords.\r\nOur main contribution is to precisely calculate the maximum value of p for which there exist infinite families of positive rate (p,𝓁,L)_q-list-recoverable codes, the quantity we call the zero-rate threshold. Denoting this value by p_*, we in fact show that codes correcting a p_*+ε fraction of errors must have size O_ε(1), i.e., independent of n. Such a result is typically referred to as a \"Plotkin bound.\" To complement this, a standard random code with expurgation construction shows that there exist positive rate codes correcting a p_*-ε fraction of errors. We also follow a classical proof template (typically attributed to Elias and Bassalygo) to derive from the zero-rate threshold other tradeoffs between rate and decoding radius for list-decoding and list-recovery.\r\nTechnically, proving the Plotkin bound boils down to demonstrating the Schur convexity of a certain function defined on the q-simplex as well as the convexity of a univariate function derived from it. We remark that an earlier argument claimed similar results for q-ary list-decoding; however, we point out that this earlier proof is flawed."}],"type":"conference","month":"07","article_processing_charge":"Yes","corr_author":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","doi":"10.4230/LIPIcs.ICALP.2023.99","arxiv":1,"has_accepted_license":"1","department":[{"_id":"MaMo"}],"publication":"50th International Colloquium on Automata, Languages, and Programming"},{"volume":261,"file":[{"creator":"dernst","date_created":"2023-08-21T06:45:16Z","file_id":"14088","date_updated":"2023-08-21T06:45:16Z","file_name":"2023_LIPIcsICALP_Harris.pdf","file_size":917791,"checksum":"6dee0684245bb1c524b9c955db1e933d","success":1,"access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"alternative_title":["LIPIcs"],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772785"]},"intvolume":"       261","file_date_updated":"2023-08-21T06:45:16Z","scopus_import":"1","acknowledgement":"We thank Heng Guo for helpful explanations of algorithms for sampling connected subgraphs and matchings, Maksym Serbyn for bringing to our attention the Wang-Landau algorithm and its use in physics.","conference":{"end_date":"2023-07-14","name":"ICALP: Automata, Languages and Programming","start_date":"2023-07-10","location":"Paderborn, Germany"},"day":"01","ddc":["000","510"],"_id":"14084","oa":1,"status":"public","language":[{"iso":"eng"}],"external_id":{"arxiv":["2007.10824"]},"date_published":"2023-07-01T00:00:00Z","related_material":{"record":[{"relation":"later_version","status":"public","id":"18855"}]},"date_created":"2023-08-20T22:01:14Z","author":[{"last_name":"Harris","first_name":"David G.","full_name":"Harris, David G."},{"first_name":"Vladimir","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2025-07-10T11:50:45Z","year":"2023","publication_status":"published","publication":"50th International Colloquium on Automata, Languages, and Programming","has_accepted_license":"1","department":[{"_id":"VlKo"}],"arxiv":1,"doi":"10.4230/LIPIcs.ICALP.2023.72","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"month":"07","article_processing_charge":"Yes","corr_author":"1","title":"Parameter estimation for Gibbs distributions","type":"conference","abstract":[{"text":"A central problem in computational statistics is to convert a procedure for sampling combinatorial objects into a procedure for counting those objects, and vice versa. We will consider sampling problems which come from Gibbs distributions, which are families of probability distributions over a discrete space Ω with probability mass function of the form μ^Ω_β(ω) ∝ e^{β H(ω)} for β in an interval [β_min, β_max] and H(ω) ∈ {0} ∪ [1, n].\r\nThe partition function is the normalization factor Z(β) = ∑_{ω ∈ Ω} e^{β H(ω)}, and the log partition ratio is defined as q = (log Z(β_max))/Z(β_min)\r\nWe develop a number of algorithms to estimate the counts c_x using roughly Õ(q/ε²) samples for general Gibbs distributions and Õ(n²/ε²) samples for integer-valued distributions (ignoring some second-order terms and parameters), We show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs and perfect matchings in a graph.","lang":"eng"}],"article_number":"72","citation":{"ama":"Harris DG, Kolmogorov V. Parameter estimation for Gibbs distributions. In: <i>50th International Colloquium on Automata, Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.72\">10.4230/LIPIcs.ICALP.2023.72</a>","ieee":"D. G. Harris and V. Kolmogorov, “Parameter estimation for Gibbs distributions,” in <i>50th International Colloquium on Automata, Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261.","apa":"Harris, D. G., &#38; Kolmogorov, V. (2023). Parameter estimation for Gibbs distributions. In <i>50th International Colloquium on Automata, Languages, and Programming</i> (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.72\">https://doi.org/10.4230/LIPIcs.ICALP.2023.72</a>","mla":"Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs Distributions.” <i>50th International Colloquium on Automata, Languages, and Programming</i>, vol. 261, 72, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.72\">10.4230/LIPIcs.ICALP.2023.72</a>.","ista":"Harris DG, Kolmogorov V. 2023. Parameter estimation for Gibbs distributions. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 72.","chicago":"Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs Distributions.” In <i>50th International Colloquium on Automata, Languages, and Programming</i>, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.72\">https://doi.org/10.4230/LIPIcs.ICALP.2023.72</a>.","short":"D.G. Harris, V. Kolmogorov, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023."},"oa_version":"Published Version"},{"corr_author":"1","month":"07","article_processing_charge":"Yes","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa_version":"Published Version","article_number":"69","citation":{"chicago":"Goranci, Gramoz, and Monika Henzinger. “Efficient Data Structures for Incremental Exact and Approximate Maximum Flow.” In <i>50th International Colloquium on Automata, Languages, and Programming</i>, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.69\">https://doi.org/10.4230/LIPIcs.ICALP.2023.69</a>.","short":"G. Goranci, M. Henzinger, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","ista":"Goranci G, Henzinger M. 2023. Efficient data structures for incremental exact and approximate maximum flow. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 69.","ama":"Goranci G, Henzinger M. Efficient data structures for incremental exact and approximate maximum flow. In: <i>50th International Colloquium on Automata, Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.69\">10.4230/LIPIcs.ICALP.2023.69</a>","ieee":"G. Goranci and M. Henzinger, “Efficient data structures for incremental exact and approximate maximum flow,” in <i>50th International Colloquium on Automata, Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261.","apa":"Goranci, G., &#38; Henzinger, M. (2023). Efficient data structures for incremental exact and approximate maximum flow. In <i>50th International Colloquium on Automata, Languages, and Programming</i> (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.69\">https://doi.org/10.4230/LIPIcs.ICALP.2023.69</a>","mla":"Goranci, Gramoz, and Monika Henzinger. “Efficient Data Structures for Incremental Exact and Approximate Maximum Flow.” <i>50th International Colloquium on Automata, Languages, and Programming</i>, vol. 261, 69, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.69\">10.4230/LIPIcs.ICALP.2023.69</a>."},"abstract":[{"text":"We show an (1+ϵ)-approximation algorithm for maintaining maximum s-t flow under m edge insertions in m1/2+o(1)ϵ−1/2 amortized update time for directed, unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm in general sparse graphs with arbitrarily good approximation guarantee.","lang":"eng"}],"type":"conference","title":"Efficient data structures for incremental exact and approximate maximum flow","arxiv":1,"has_accepted_license":"1","department":[{"_id":"MoHe"}],"publication":"50th International Colloquium on Automata, Languages, and Programming","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.4230/LIPIcs.ICALP.2023.69","oa":1,"_id":"14085","ddc":["000"],"day":"01","conference":{"start_date":"2023-07-10","location":"Paderborn, Germany","end_date":"2023-07-14","name":"ICALP: Automata, Languages and Programming"},"acknowledgement":"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.\r\n101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the\r\nAustrian Science Fund (FWF) project “Static and Dynamic Hierarchical Graph Decompositions”,\r\nI 5982-N, and project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nThis work was done in part while Gramoz Goranci was at Institute for Theoretical Studies, ETH Zurich, Switzerland. There, he was supported by Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich Foundation. We also thank Richard Peng, Thatchaphol Saranurak, Sebastian Forster and Sushant Sachdeva for helpful discussions, and the anonymous reviewers for their insightful comments.","scopus_import":"1","file_date_updated":"2023-08-21T06:59:05Z","year":"2023","publication_status":"published","author":[{"first_name":"Gramoz","last_name":"Goranci","full_name":"Goranci, Gramoz"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger","first_name":"Monika H"}],"date_created":"2023-08-20T22:01:14Z","date_updated":"2025-06-04T07:19:37Z","external_id":{"arxiv":["2211.09606"]},"date_published":"2023-07-01T00:00:00Z","status":"public","language":[{"iso":"eng"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772785"]},"file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","success":1,"file_size":875910,"checksum":"074177e815a1656de5d4071c7a3dffa6","file_name":"2023_LIPIcsICALP_Goranci.pdf","date_created":"2023-08-21T06:59:05Z","creator":"dernst","date_updated":"2023-08-21T06:59:05Z","file_id":"14089"}],"alternative_title":["LIPIcs"],"ec_funded":1,"volume":261,"intvolume":"       261"},{"article_processing_charge":"Yes","month":"07","corr_author":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"project":[{"grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_number":"74","citation":{"ista":"Henzinger M, Liu P, Vondrák J, Zheng DW. 2023. Faster submodular maximization for several classes of matroids. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 74.","ama":"Henzinger M, Liu P, Vondrák J, Zheng DW. Faster submodular maximization for several classes of matroids. In: <i>50th International Colloquium on Automata, Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.74\">10.4230/LIPIcs.ICALP.2023.74</a>","ieee":"M. Henzinger, P. Liu, J. Vondrák, and D. W. Zheng, “Faster submodular maximization for several classes of matroids,” in <i>50th International Colloquium on Automata, Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261.","mla":"Henzinger, Monika, et al. “Faster Submodular Maximization for Several Classes of Matroids.” <i>50th International Colloquium on Automata, Languages, and Programming</i>, vol. 261, 74, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.74\">10.4230/LIPIcs.ICALP.2023.74</a>.","apa":"Henzinger, M., Liu, P., Vondrák, J., &#38; Zheng, D. W. (2023). Faster submodular maximization for several classes of matroids. In <i>50th International Colloquium on Automata, Languages, and Programming</i> (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.74\">https://doi.org/10.4230/LIPIcs.ICALP.2023.74</a>","chicago":"Henzinger, Monika, Paul Liu, Jan Vondrák, and Da Wei Zheng. “Faster Submodular Maximization for Several Classes of Matroids.” In <i>50th International Colloquium on Automata, Languages, and Programming</i>, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.74\">https://doi.org/10.4230/LIPIcs.ICALP.2023.74</a>.","short":"M. Henzinger, P. Liu, J. Vondrák, D.W. Zheng, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023."},"oa_version":"Published Version","title":"Faster submodular maximization for several classes of matroids","type":"conference","abstract":[{"lang":"eng","text":"The maximization of submodular functions have found widespread application in areas such as machine learning, combinatorial optimization, and economics, where practitioners often wish to enforce various constraints; the matroid constraint has been investigated extensively due to its algorithmic properties and expressive power. Though tight approximation algorithms for general matroid constraints exist in theory, the running times of such algorithms typically scale quadratically, and are not practical for truly large scale settings. Recent progress has focused on fast algorithms for important classes of matroids given in explicit form. Currently, nearly-linear time algorithms only exist for graphic and partition matroids [Alina Ene and Huy L. Nguyen, 2019]. In this work, we develop algorithms for monotone submodular maximization constrained by graphic, transversal matroids, or laminar matroids in time near-linear in the size of their representation. Our algorithms achieve an optimal approximation of 1-1/e-ε and both generalize and accelerate the results of Ene and Nguyen [Alina Ene and Huy L. Nguyen, 2019]. In fact, the running time of our algorithm cannot be improved within the fast continuous greedy framework of Badanidiyuru and Vondrák [Ashwinkumar Badanidiyuru and Jan Vondrák, 2014].\r\nTo achieve near-linear running time, we make use of dynamic data structures that maintain bases with approximate maximum cardinality and weight under certain element updates. These data structures need to support a weight decrease operation and a novel Freeze operation that allows the algorithm to freeze elements (i.e. force to be contained) in its basis regardless of future data structure operations. For the laminar matroid, we present a new dynamic data structure using the top tree interface of Alstrup, Holm, de Lichtenberg, and Thorup [Stephen Alstrup et al., 2005] that maintains the maximum weight basis under insertions and deletions of elements in O(log n) time. This data structure needs to support certain subtree query and path update operations that are performed every insertion and deletion that are non-trivial to handle in conjunction. For the transversal matroid the Freeze operation corresponds to requiring the data structure to keep a certain set S of vertices matched, a property that we call S-stability. While there is a large body of work on dynamic matching algorithms, none are S-stable and maintain an approximate maximum weight matching under vertex updates. We give the first such algorithm for bipartite graphs with total running time linear (up to log factors) in the number of edges."}],"arxiv":1,"publication":"50th International Colloquium on Automata, Languages, and Programming","has_accepted_license":"1","department":[{"_id":"MoHe"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","doi":"10.4230/LIPIcs.ICALP.2023.74","day":"01","ddc":["000"],"_id":"14086","oa":1,"file_date_updated":"2023-08-21T07:04:36Z","scopus_import":"1","acknowledgement":" Monika Henzinger: This project has received funding from the European Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant\r\nagreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project “Static and Dynamic Hierarchical Graph Decompositions”, I 5982-N, and project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024. Jan Vondrák: Supported by NSF Award 2127781.","conference":{"location":"Paderborn, Germany","start_date":"2023-07-10","name":"ICALP: Automata, Languages and Programming","end_date":"2023-07-14"},"date_updated":"2025-07-10T11:50:45Z","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger"},{"first_name":"Paul","last_name":"Liu","full_name":"Liu, Paul"},{"full_name":"Vondrák, Jan","last_name":"Vondrák","first_name":"Jan"},{"last_name":"Zheng","first_name":"Da Wei","full_name":"Zheng, Da Wei"}],"date_created":"2023-08-20T22:01:14Z","year":"2023","publication_status":"published","language":[{"iso":"eng"}],"status":"public","date_published":"2023-07-01T00:00:00Z","external_id":{"arxiv":["2305.00122"]},"file":[{"file_id":"14090","date_updated":"2023-08-21T07:04:36Z","creator":"dernst","date_created":"2023-08-21T07:04:36Z","file_name":"2023_LIPIcsICALP_HenzingerM.pdf","checksum":"a5eef225014e003efbfbe4830fdd23cb","file_size":930943,"success":1,"access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"alternative_title":["LIPIcs"],"publication_identifier":{"isbn":["9783959772785"],"issn":["1868-8969"]},"volume":261,"ec_funded":1,"intvolume":"       261"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","doi":"10.4230/LIPIcs.CONCUR.2023.21","arxiv":1,"department":[{"_id":"ToHe"}],"has_accepted_license":"1","publication":"34th International Conference on Concurrency Theory","citation":{"short":"E. Bartocci, T.A. Henzinger, D. Nickovic, A. Oliveira da Costa, in:, 34th International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","chicago":"Bartocci, Ezio, Thomas A Henzinger, Dejan Nickovic, and Ana Oliveira da Costa. “Hypernode 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.21\">https://doi.org/10.4230/LIPIcs.CONCUR.2023.21</a>.","ista":"Bartocci E, Henzinger TA, Nickovic D, Oliveira da Costa A. 2023. Hypernode automata. 34th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 279, 21.","mla":"Bartocci, Ezio, et al. “Hypernode Automata.” <i>34th International Conference on Concurrency Theory</i>, vol. 279, 21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.21\">10.4230/LIPIcs.CONCUR.2023.21</a>.","apa":"Bartocci, E., Henzinger, T. A., Nickovic, D., &#38; Oliveira da Costa, A. (2023). Hypernode 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.21\">https://doi.org/10.4230/LIPIcs.CONCUR.2023.21</a>","ieee":"E. Bartocci, T. A. Henzinger, D. Nickovic, and A. Oliveira da Costa, “Hypernode automata,” in <i>34th International Conference on Concurrency Theory</i>, Antwerp, Belgium, 2023, vol. 279.","ama":"Bartocci E, Henzinger TA, Nickovic D, Oliveira da Costa A. Hypernode 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.21\">10.4230/LIPIcs.CONCUR.2023.21</a>"},"article_number":"21","oa_version":"Published Version","title":"Hypernode automata","abstract":[{"text":"We introduce hypernode automata as a new specification formalism for hyperproperties of concurrent systems. They are finite automata with nodes labeled with hypernode logic formulas and transitions labeled with actions. A hypernode logic formula specifies relations between sequences of variable values in different system executions. Unlike HyperLTL, hypernode logic takes an asynchronous view on execution traces by constraining the values and the order of value changes of each variable without correlating the timing of the changes. Different execution traces are synchronized solely through the transitions of hypernode automata. Hypernode automata naturally combine asynchronicity at the node level with synchronicity at the transition level. We show that the model-checking problem for hypernode automata is decidable over action-labeled Kripke structures, whose actions induce transitions of the specification automata. For this reason, hypernode automaton is a suitable formalism for specifying and verifying asynchronous hyperproperties, such as declassifying observational determinism in multi-threaded programs.","lang":"eng"}],"type":"conference","article_processing_charge":"Yes","month":"09","corr_author":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093","name":"Vigilant Algorithmic Monitoring of Software","call_identifier":"H2020"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"intvolume":"       279","file":[{"checksum":"215765e40454d806174ac0a223e8d6fa","file_size":795790,"date_updated":"2023-10-09T07:42:45Z","file_id":"14413","creator":"dernst","date_created":"2023-10-09T07:42:45Z","file_name":"2023_LIPcs_Bartocci.pdf","relation":"main_file","content_type":"application/pdf","success":1,"access_level":"open_access"}],"alternative_title":["LIPIcs"],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772990"]},"volume":279,"ec_funded":1,"date_created":"2023-10-08T22:01:16Z","author":[{"first_name":"Ezio","last_name":"Bartocci","full_name":"Bartocci, Ezio"},{"first_name":"Thomas A","last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Dejan","last_name":"Nickovic","id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87","full_name":"Nickovic, Dejan"},{"full_name":"Oliveira da Costa, Ana","id":"f347ec37-6676-11ee-b395-a888cb7b4fb4","orcid":"0000-0002-8741-5799","last_name":"Oliveira da Costa","first_name":"Ana"}],"date_updated":"2026-01-05T12:27:40Z","publication_status":"published","year":"2023","status":"public","language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"20866"}]},"date_published":"2023-09-01T00:00:00Z","external_id":{"arxiv":["2305.02836"]},"day":"01","oa":1,"_id":"14405","ddc":["000"],"file_date_updated":"2023-10-09T07:42:45Z","scopus_import":"1","acknowledgement":"This work was supported in part by the Austrian Science Fund (FWF) SFB project\r\nSpyCoDe F8502, by the FWF projects ZK-35 and W1255-N23, and by the ERC Advanced Grant\r\nVAMOS 101020093.","conference":{"start_date":"2023-09-19","location":"Antwerp, Belgium","end_date":"2023-09-22","name":"CONCUR: Conference on Concurrency Theory"}},{"date_updated":"2024-10-09T21:07:14Z","date_created":"2023-11-05T23:00:53Z","author":[{"full_name":"Aksenov, Vitaly","last_name":"Aksenov","first_name":"Vitaly"},{"full_name":"Anoprenko, Michael","last_name":"Anoprenko","first_name":"Michael"},{"id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6","full_name":"Fedorov, Alexander","first_name":"Alexander","last_name":"Fedorov"},{"full_name":"Spear, Michael","first_name":"Michael","last_name":"Spear"}],"year":"2023","publication_status":"published","language":[{"iso":"eng"}],"status":"public","date_published":"2023-10-01T00:00:00Z","day":"01","ddc":["000"],"_id":"14485","oa":1,"scopus_import":"1","file_date_updated":"2023-11-06T11:45:21Z","conference":{"location":"L'Aquila, Italy","start_date":"2023-10-09","name":"DISC: Symposium on Distributed Computing","end_date":"2023-10-13"},"intvolume":"       281","file":[{"file_id":"14492","date_updated":"2023-11-06T11:45:21Z","creator":"dernst","date_created":"2023-11-06T11:45:21Z","file_name":"2023_LIPIcs_Aksenov.pdf","checksum":"d9f8d2915cccdf2df5905b7cd1b4a560","file_size":646665,"success":1,"access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"alternative_title":["LIPIcs"],"publication_identifier":{"isbn":["9783959773010"],"issn":["1868-8969"]},"volume":281,"citation":{"chicago":"Aksenov, Vitaly, Michael Anoprenko, Alexander Fedorov, and Michael Spear. “Brief Announcement: BatchBoost: Universal Batching for Concurrent Data Structures.” In <i>37th International Symposium on Distributed Computing</i>, Vol. 281. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2023.35\">https://doi.org/10.4230/LIPIcs.DISC.2023.35</a>.","short":"V. Aksenov, M. Anoprenko, A. Fedorov, M. Spear, in:, 37th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","ista":"Aksenov V, Anoprenko M, Fedorov A, Spear M. 2023. Brief announcement: BatchBoost: Universal batching for concurrent data structures. 37th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 281, 35.","ieee":"V. Aksenov, M. Anoprenko, A. Fedorov, and M. Spear, “Brief announcement: BatchBoost: Universal batching for concurrent data structures,” in <i>37th International Symposium on Distributed Computing</i>, L’Aquila, Italy, 2023, vol. 281.","ama":"Aksenov V, Anoprenko M, Fedorov A, Spear M. Brief announcement: BatchBoost: Universal batching for concurrent data structures. In: <i>37th International Symposium on Distributed Computing</i>. Vol 281. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2023.35\">10.4230/LIPIcs.DISC.2023.35</a>","apa":"Aksenov, V., Anoprenko, M., Fedorov, A., &#38; Spear, M. (2023). Brief announcement: BatchBoost: Universal batching for concurrent data structures. In <i>37th International Symposium on Distributed Computing</i> (Vol. 281). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2023.35\">https://doi.org/10.4230/LIPIcs.DISC.2023.35</a>","mla":"Aksenov, Vitaly, et al. “Brief Announcement: BatchBoost: Universal Batching for Concurrent Data Structures.” <i>37th International Symposium on Distributed Computing</i>, vol. 281, 35, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2023.35\">10.4230/LIPIcs.DISC.2023.35</a>."},"article_number":"35","oa_version":"Published Version","title":"Brief announcement: BatchBoost: Universal batching for concurrent data structures","type":"conference","abstract":[{"text":"Batching is a technique that stores multiple keys/values in each node of a data structure. In sequential search data structures, batching reduces latency by reducing the number of cache misses and shortening the chain of pointers to dereference. Applying batching to concurrent data structures is challenging, because it is difficult to maintain the search property and keep contention low in the presence of batching.\r\nIn this paper, we present a general methodology for leveraging batching in concurrent search data structures, called BatchBoost. BatchBoost builds a search data structure from distinct \"data\" and \"index\" layers. The data layer’s purpose is to store a batch of key/value pairs in each of its nodes. The index layer uses an unmodified concurrent search data structure to route operations to a position in the data layer that is \"close\" to where the corresponding key should exist. The requirements on the index and data layers are low: with minimal effort, we were able to compose three highly scalable concurrent search data structures based on three original data structures as the index layers with a batched version of the Lazy List as the data layer. The resulting BatchBoost data structures provide significant performance improvements over their original counterparts.","lang":"eng"}],"month":"10","article_processing_charge":"Yes","corr_author":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","doi":"10.4230/LIPIcs.DISC.2023.35","has_accepted_license":"1","publication":"37th International Symposium on Distributed Computing","department":[{"_id":"GradSch"}]},{"publication_identifier":{"isbn":["9783959773034"],"issn":["1868-8969"]},"file":[{"file_name":"2023_LIPIcs_Beaver.pdf","date_updated":"2023-11-13T08:44:34Z","file_id":"14521","creator":"dernst","date_created":"2023-11-13T08:44:34Z","checksum":"c1f98831cb5149d6c030c41999e6e960","file_size":793495,"access_level":"open_access","success":1,"content_type":"application/pdf","relation":"main_file"}],"alternative_title":["LIPIcs"],"volume":282,"intvolume":"       282","_id":"14516","ddc":["000"],"oa":1,"day":"01","acknowledgement":"Work done when all the authors were at Novi Research, Meta.","conference":{"location":"Princeton, NJ, United States","start_date":"2023-10-23","name":"AFT: Conference on Advances in Financial Technologies","end_date":"2023-10-25"},"file_date_updated":"2023-11-13T08:44:34Z","scopus_import":"1","publication_status":"published","year":"2023","author":[{"last_name":"Beaver","first_name":"Donald","full_name":"Beaver, Donald"},{"full_name":"Kelkar, Mahimna","first_name":"Mahimna","last_name":"Kelkar"},{"full_name":"Lewi, Kevin","first_name":"Kevin","last_name":"Lewi"},{"first_name":"Valeria","last_name":"Nikolaenko","full_name":"Nikolaenko, Valeria"},{"full_name":"Sonnino, Alberto","first_name":"Alberto","last_name":"Sonnino"},{"first_name":"Konstantinos","last_name":"Chalkias","full_name":"Chalkias, Konstantinos"},{"last_name":"Kokoris Kogias","first_name":"Eleftherios","full_name":"Kokoris Kogias, Eleftherios","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30"},{"last_name":"Naurois","first_name":"Ladi De","full_name":"Naurois, Ladi De"},{"last_name":"Roy","first_name":"Arnab","full_name":"Roy, Arnab"}],"date_created":"2023-11-12T23:00:55Z","date_updated":"2024-10-09T21:07:17Z","date_published":"2023-10-01T00:00:00Z","status":"public","language":[{"iso":"eng"}],"has_accepted_license":"1","department":[{"_id":"ElKo"}],"publication":"5th Conference on Advances in Financial Technologies","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.4230/LIPIcs.AFT.2023.7","corr_author":"1","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1643"}],"article_processing_charge":"Yes","month":"10","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa_version":"Published Version","citation":{"short":"D. Beaver, M. Kelkar, K. Lewi, V. Nikolaenko, A. Sonnino, K. Chalkias, E. Kokoris Kogias, L.D. Naurois, A. Roy, in:, 5th Conference on Advances in Financial Technologies, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","chicago":"Beaver, Donald, Mahimna Kelkar, Kevin Lewi, Valeria Nikolaenko, Alberto Sonnino, Konstantinos Chalkias, Eleftherios Kokoris Kogias, Ladi De Naurois, and Arnab Roy. “STROBE: Streaming Threshold Random Beacons.” In <i>5th Conference on Advances in Financial Technologies</i>, Vol. 282. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.AFT.2023.7\">https://doi.org/10.4230/LIPIcs.AFT.2023.7</a>.","ista":"Beaver D, Kelkar M, Lewi K, Nikolaenko V, Sonnino A, Chalkias K, Kokoris Kogias E, Naurois LD, Roy A. 2023. STROBE: Streaming Threshold Random Beacons. 5th Conference on Advances in Financial Technologies. AFT: Conference on Advances in Financial Technologies, LIPIcs, vol. 282, 7.","mla":"Beaver, Donald, et al. “STROBE: Streaming Threshold Random Beacons.” <i>5th Conference on Advances in Financial Technologies</i>, vol. 282, 7, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.AFT.2023.7\">10.4230/LIPIcs.AFT.2023.7</a>.","apa":"Beaver, D., Kelkar, M., Lewi, K., Nikolaenko, V., Sonnino, A., Chalkias, K., … Roy, A. (2023). STROBE: Streaming Threshold Random Beacons. In <i>5th Conference on Advances in Financial Technologies</i> (Vol. 282). Princeton, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.AFT.2023.7\">https://doi.org/10.4230/LIPIcs.AFT.2023.7</a>","ieee":"D. Beaver <i>et al.</i>, “STROBE: Streaming Threshold Random Beacons,” in <i>5th Conference on Advances in Financial Technologies</i>, Princeton, NJ, United States, 2023, vol. 282.","ama":"Beaver D, Kelkar M, Lewi K, et al. STROBE: Streaming Threshold Random Beacons. In: <i>5th Conference on Advances in Financial Technologies</i>. Vol 282. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.AFT.2023.7\">10.4230/LIPIcs.AFT.2023.7</a>"},"article_number":"7","abstract":[{"lang":"eng","text":"We revisit decentralized random beacons with a focus on practical distributed applications. Decentralized random beacons (Beaver and So, Eurocrypt'93) provide the functionality for n parties to generate an unpredictable sequence of bits in a way that cannot be biased, which is useful for any decentralized protocol requiring trusted randomness. Existing beacon constructions are highly inefficient in practical settings where protocol parties need to rejoin after crashes or disconnections, and more significantly where smart contracts may rely on arbitrary index points in high-volume streams. For this, we introduce a new notion of history-generating decentralized random beacons (HGDRBs). Roughly, the history-generation property of HGDRBs allows for previous beacon outputs to be efficiently generated knowing only the current value and the public key. At application layers, history-generation supports registering a sparser set of on-chain values if desired, so that apps like lotteries can utilize on-chain values without incurring high-frequency costs, enjoying all the benefits of DRBs implemented off-chain or with decoupled, special-purpose chains. Unlike rollups, HG is tailored specifically to recovering and verifying pseudorandom bit sequences and thus enjoys unique optimizations investigated in this work. We introduce STROBE: an efficient HGDRB construction which generalizes the original squaring-based RSA approach of Beaver and So. STROBE enjoys several useful properties that make it suited for practical applications that use beacons: 1) history-generating: it can regenerate and verify high-throughput beacon streams, supporting sparse (thus cost-effective) ledger entries; 2) concisely self-verifying: NIZK-free, with state and validation employing a single ring element; 3) eco-friendly: stake-based rather than work based; 4) unbounded: refresh-free, addressing limitations of Beaver and So; 5) delay-free: results are immediately available. 6) storage-efficient: the last beacon suffices to derive all past outputs, thus O(1) storage requirements for nodes serving the whole history."}],"type":"conference","title":"STROBE: Streaming Threshold Random Beacons"},{"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"corr_author":"1","month":"03","article_processing_charge":"No","abstract":[{"lang":"eng","text":"Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However,\r\nmany DP algorithms have to fill in large DP tables, represented by two-dimensional arrays, which causes at least quadratic running times and space usages. This has led to the development of improved algorithms for special cases when the DPs satisfy additional properties like, e.g., the Monge property or total monotonicity.\r\nIn this paper, we consider a new condition which assumes (among some other technical assumptions) that the rows of the DP table are monotone. Under this assumption, we introduce\r\na novel data structure for computing (1 + ϵ)-approximate DP solutions in near-linear time and\r\nspace in the static setting, and with polylogarithmic update times when the DP entries change\r\ndynamically. To the best of our knowledge, our new condition is incomparable to previous conditions and is the first which allows to derive dynamic algorithms based on existing DPs. Instead of using two-dimensional arrays to store the DP tables, we store the rows of the DP tables using monotone piecewise constant functions. This allows us to store length-n DP table rows with entries in [0, W] using only polylog(n, W) bits, and to perform operations, such as (min, +)-convolution or rounding, on these functions in polylogarithmic time.\r\nWe further present several applications of our data structure. For bicriteria versions of k-balanced graph partitioning and simultaneous source location, we obtain the first dynamic algorithms with subpolynomial update times, as well as the first static algorithms using only near-linear time and space. Additionally, we obtain the currently fastest algorithm for fully dynamic knapsack."}],"type":"conference","title":"Dynamic maintenance of monotone dynamic programs and applications","oa_version":"Published Version","article_number":"36","citation":{"short":"M. Henzinger, S. Neumann, H. Räcke, S. Schmid, in:, 40th International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","chicago":"Henzinger, Monika, Stefan Neumann, Harald Räcke, and Stefan Schmid. “Dynamic Maintenance of Monotone Dynamic Programs and Applications.” In <i>40th International Symposium on Theoretical Aspects of Computer Science</i>, Vol. 254. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2023.36\">https://doi.org/10.4230/LIPIcs.STACS.2023.36</a>.","apa":"Henzinger, M., Neumann, S., Räcke, H., &#38; Schmid, S. (2023). Dynamic maintenance of monotone dynamic programs and applications. In <i>40th International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 254). Hamburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2023.36\">https://doi.org/10.4230/LIPIcs.STACS.2023.36</a>","mla":"Henzinger, Monika, et al. “Dynamic Maintenance of Monotone Dynamic Programs and Applications.” <i>40th International Symposium on Theoretical Aspects of Computer Science</i>, vol. 254, 36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2023.36\">10.4230/LIPIcs.STACS.2023.36</a>.","ama":"Henzinger M, Neumann S, Räcke H, Schmid S. Dynamic maintenance of monotone dynamic programs and applications. In: <i>40th International Symposium on Theoretical Aspects of Computer Science</i>. Vol 254. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2023.36\">10.4230/LIPIcs.STACS.2023.36</a>","ieee":"M. Henzinger, S. Neumann, H. Räcke, and S. Schmid, “Dynamic maintenance of monotone dynamic programs and applications,” in <i>40th International Symposium on Theoretical Aspects of Computer Science</i>, Hamburg, Germany, 2023, vol. 254.","ista":"Henzinger M, Neumann S, Räcke H, Schmid S. 2023. Dynamic maintenance of monotone dynamic programs and applications. 40th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 254, 36."},"has_accepted_license":"1","department":[{"_id":"MoHe"}],"publication":"40th International Symposium on Theoretical Aspects of Computer Science","arxiv":1,"doi":"10.4230/LIPIcs.STACS.2023.36","quality_controlled":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","conference":{"start_date":"2023-03-07","location":"Hamburg, Germany","end_date":"2023-03-09","name":"STACS: Symposium on Theoretical Aspects of Computer Science"},"acknowledgement":"Monika Henzinger: This project has received funding from the European Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant\r\nagreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nStefan Neumann: This research is supported by the the ERC Advanced Grant REBOUND (834862) and the EC H2020 RIA project SoBigData++ (871042).\r\nStefan Schmid: Research supported by Austrian Science Fund (FWF) project I 5025-N (DELTA), 2020-2024.","file_date_updated":"2023-03-27T06:37:22Z","scopus_import":"1","oa":1,"_id":"12760","ddc":["000"],"day":"01","external_id":{"isi":["001532693100036"],"arxiv":["2301.01744"]},"date_published":"2023-03-01T00:00:00Z","status":"public","language":[{"iso":"eng"}],"publication_status":"published","year":"2023","author":[{"first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"first_name":"Stefan","last_name":"Neumann","full_name":"Neumann, Stefan"},{"first_name":"Harald","last_name":"Räcke","full_name":"Räcke, Harald"},{"full_name":"Schmid, Stefan","first_name":"Stefan","last_name":"Schmid"}],"date_created":"2023-03-26T22:01:07Z","date_updated":"2025-09-09T12:22:44Z","ec_funded":1,"volume":254,"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772662"]},"alternative_title":["LIPIcs"],"file":[{"relation":"main_file","content_type":"application/pdf","success":1,"access_level":"open_access","checksum":"22141ab8bc55188e2dfff665e5daecbd","file_size":872706,"date_updated":"2023-03-27T06:37:22Z","file_id":"12769","creator":"dernst","date_created":"2023-03-27T06:37:22Z","file_name":"2023_LIPICS_HenzingerM.pdf"}],"intvolume":"       254","isi":1},{"arxiv":1,"publication":"1st Symposium on Algorithmic Foundations of Dynamic Networks","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","doi":"10.4230/LIPIcs.SAND.2022.18","article_processing_charge":"No","month":"04","main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.SAND.2022.18","open_access":"1"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"ista":"Hanauer K, Henzinger M, Hua QC. 2022. Fully dynamic four-vertex subgraph counting. 1st Symposium on Algorithmic Foundations of Dynamic Networks. SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 221, 18.","ama":"Hanauer K, Henzinger M, Hua QC. Fully dynamic four-vertex subgraph counting. 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.18\">10.4230/LIPIcs.SAND.2022.18</a>","ieee":"K. Hanauer, M. Henzinger, and Q. C. Hua, “Fully dynamic four-vertex subgraph counting,” in <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>, Virtual, 2022, vol. 221.","mla":"Hanauer, Kathrin, et al. “Fully Dynamic Four-Vertex Subgraph Counting.” <i>1st Symposium on Algorithmic Foundations of Dynamic Networks</i>, vol. 221, 18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2022.18\">10.4230/LIPIcs.SAND.2022.18</a>.","apa":"Hanauer, K., Henzinger, M., &#38; Hua, Q. C. (2022). Fully dynamic four-vertex subgraph counting. 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.18\">https://doi.org/10.4230/LIPIcs.SAND.2022.18</a>","chicago":"Hanauer, Kathrin, Monika Henzinger, and Qi Cheng Hua. “Fully Dynamic Four-Vertex Subgraph Counting.” 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.18\">https://doi.org/10.4230/LIPIcs.SAND.2022.18</a>.","short":"K. Hanauer, M. Henzinger, Q.C. Hua, in:, 1st Symposium on Algorithmic Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022."},"article_number":"18","oa_version":"Published Version","title":"Fully dynamic four-vertex subgraph counting","abstract":[{"text":"This paper presents a comprehensive study of algorithms for maintaining the number of all connected four-vertex subgraphs in a dynamic graph. Specifically, our algorithms maintain the number of paths of length three in deterministic amortized O(m^{1/2}) update time, and any other connected four-vertex subgraph which is not a clique in deterministic amortized update time O(m^{2/3}). Queries can be answered in constant time. We also study the query times for subgraphs containing an arbitrary edge that is supplied only with the query as well as the case where only subgraphs containing a vertex s that is fixed beforehand are considered. For length-3 paths, paws, 4-cycles, and diamonds our bounds match or are not far from (conditional) lower bounds: Based on the OMv conjecture we show that any dynamic algorithm that detects the existence of paws, diamonds, or 4-cycles or that counts length-3 paths takes update time Ω(m^{1/2-δ}).\r\nAdditionally, for 4-cliques and all connected induced subgraphs, we show a lower bound of Ω(m^{1-δ}) for any small constant δ > 0 for the amortized update time, assuming the static combinatorial 4-clique conjecture holds. This shows that the O(m) algorithm by Eppstein et al. [David Eppstein et al., 2012] for these subgraphs cannot be improved by a polynomial factor.","lang":"eng"}],"type":"conference","alternative_title":["LIPIcs"],"publication_identifier":{"isbn":["9783959772242"],"issn":["1868-8969"]},"extern":"1","volume":221,"intvolume":"       221","day":"29","_id":"11812","oa":1,"scopus_import":"1","conference":{"location":"Virtual","start_date":"2022-04-28","name":"SAND: Symposium on Algorithmic Foundations of Dynamic Networks","end_date":"2022-04-30"},"date_created":"2022-08-12T06:57:55Z","author":[{"full_name":"Hanauer, Kathrin","last_name":"Hanauer","first_name":"Kathrin"},{"last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"full_name":"Hua, Qi Cheng","first_name":"Qi Cheng","last_name":"Hua"}],"date_updated":"2024-11-06T08:22:47Z","publication_status":"published","year":"2022","status":"public","language":[{"iso":"eng"}],"date_published":"2022-04-29T00:00:00Z","external_id":{"arxiv":["2106.15524"]}},{"file":[{"checksum":"6660c802489013f034c9e8bd57f4d46e","file_size":872534,"date_updated":"2023-01-20T10:39:44Z","file_id":"12324","creator":"dernst","date_created":"2023-01-20T10:39:44Z","file_name":"2022_LIPICs_Ahmadi.pdf","relation":"main_file","content_type":"application/pdf","success":1,"access_level":"open_access"}],"publication_identifier":{"isbn":["9783959772617"],"issn":["1868-8969"]},"volume":250,"ec_funded":1,"intvolume":"       250","day":"14","ddc":["000"],"_id":"12102","oa":1,"scopus_import":"1","file_date_updated":"2023-01-20T10:39:44Z","conference":{"location":"Madras, India","start_date":"2022-12-18","name":"FSTTCS: Foundations of Software Technology and Theoretical Computer Science","end_date":"2022-12-20"},"acknowledgement":"The research was partially supported by the Hong Kong Research Grants Council ECS\r\nProject No. 26208122, ERC CoG 863818 (FoRM-SMArt), the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385, HKUST– Kaisa Joint Research Institute Project Grant HKJRI3A-055 and HKUST Startup Grant R9272. Ali Ahmadi and Roodabeh Safavi were interns at HKUST.","date_updated":"2025-07-10T11:50:23Z","date_created":"2023-01-01T23:00:50Z","author":[{"first_name":"Ali","last_name":"Ahmadi","full_name":"Ahmadi, Ali"},{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"last_name":"Goharshady","first_name":"Amir Kafshdar","orcid":"0000-0003-1702-6584","id":"391365CE-F248-11E8-B48F-1D18A9856A87","full_name":"Goharshady, Amir Kafshdar"},{"full_name":"Meggendorfer, Tobias","orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","first_name":"Tobias","last_name":"Meggendorfer"},{"id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","full_name":"Safavi Hemami, Roodabeh","first_name":"Roodabeh","last_name":"Safavi Hemami"},{"last_name":"Zikelic","first_name":"Dorde","full_name":"Zikelic, Dorde","orcid":"0000-0002-4681-1699","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87"}],"year":"2022","publication_status":"published","language":[{"iso":"eng"}],"status":"public","date_published":"2022-12-14T00:00:00Z","has_accepted_license":"1","publication":"42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","department":[{"_id":"KrCh"},{"_id":"GradSch"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","doi":"10.4230/LIPIcs.FSTTCS.2022.29","month":"12","article_processing_charge":"No","corr_author":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"project":[{"grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020"},{"call_identifier":"H2020","name":"International IST Doctoral Program","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"chicago":"Ahmadi, Ali, Krishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer, Roodabeh Safavi Hemami, and Dorde Zikelic. “Algorithms and Hardness Results for Computing Cores of Markov Chains.” In <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Vol. 250. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29\">https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29</a>.","short":"A. Ahmadi, K. Chatterjee, A.K. Goharshady, T. Meggendorfer, R. Safavi Hemami, D. Zikelic, in:, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","ista":"Ahmadi A, Chatterjee K, Goharshady AK, Meggendorfer T, Safavi Hemami R, Zikelic D. 2022. Algorithms and hardness results for computing cores of Markov chains. 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTCS: Foundations of Software Technology and Theoretical Computer Science vol. 250, 29.","ama":"Ahmadi A, Chatterjee K, Goharshady AK, Meggendorfer T, Safavi Hemami R, Zikelic D. Algorithms and hardness results for computing cores of Markov chains. In: <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>. Vol 250. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29\">10.4230/LIPIcs.FSTTCS.2022.29</a>","ieee":"A. Ahmadi, K. Chatterjee, A. K. Goharshady, T. Meggendorfer, R. Safavi Hemami, and D. Zikelic, “Algorithms and hardness results for computing cores of Markov chains,” in <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Madras, India, 2022, vol. 250.","apa":"Ahmadi, A., Chatterjee, K., Goharshady, A. K., Meggendorfer, T., Safavi Hemami, R., &#38; Zikelic, D. (2022). Algorithms and hardness results for computing cores of Markov chains. In <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i> (Vol. 250). Madras, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29\">https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29</a>","mla":"Ahmadi, Ali, et al. “Algorithms and Hardness Results for Computing Cores of Markov Chains.” <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, vol. 250, 29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2022.29\">10.4230/LIPIcs.FSTTCS.2022.29</a>."},"article_number":"29","oa_version":"Published Version","title":"Algorithms and hardness results for computing cores of Markov chains","type":"conference","abstract":[{"text":"Given a Markov chain M = (V, v_0, δ), with state space V and a starting state v_0, and a probability threshold ε, an ε-core is a subset C of states that is left with probability at most ε. More formally, C ⊆ V is an ε-core, iff ℙ[reach (V\\C)] ≤ ε. Cores have been applied in a wide variety of verification problems over Markov chains, Markov decision processes, and probabilistic programs, as a means of discarding uninteresting and low-probability parts of a probabilistic system and instead being able to focus on the states that are likely to be encountered in a real-world run. In this work, we focus on the problem of computing a minimal ε-core in a Markov chain. Our contributions include both negative and positive results: (i) We show that the decision problem on the existence of an ε-core of a given size is NP-complete. This solves an open problem posed in [Jan Kretínský and Tobias Meggendorfer, 2020]. We additionally show that the problem remains NP-complete even when limited to acyclic Markov chains with bounded maximal vertex degree; (ii) We provide a polynomial time algorithm for computing a minimal ε-core on Markov chains over control-flow graphs of structured programs. A straightforward combination of our algorithm with standard branch prediction techniques allows one to apply the idea of cores to find a subset of program lines that are left with low probability and then focus any desired static analysis on this core subset.","lang":"eng"}]},{"intvolume":"       243","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772464"]},"file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","success":1,"checksum":"9e97e15628f66b2ad77f535bb0327dee","file_size":717940,"file_name":"2022_LIPICs_Henzinger2.pdf","file_id":"12520","date_updated":"2023-02-06T09:21:09Z","date_created":"2023-02-06T09:21:09Z","creator":"dernst"}],"alternative_title":["LIPIcs"],"ec_funded":1,"volume":243,"year":"2022","publication_status":"published","author":[{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2985-7724","first_name":"Thomas A","last_name":"Henzinger"},{"first_name":"Karoliina","last_name":"Lehtinen","full_name":"Lehtinen, Karoliina"},{"full_name":"Totzke, Patrick","last_name":"Totzke","first_name":"Patrick"}],"date_created":"2023-02-05T17:24:23Z","date_updated":"2025-09-08T14:35:16Z","date_published":"2022-09-06T00:00:00Z","related_material":{"record":[{"status":"public","relation":"later_version","id":"18530"}]},"status":"public","language":[{"iso":"eng"}],"oa":1,"_id":"12508","ddc":["000"],"day":"06","conference":{"start_date":"2022-09-13","location":"Warsaw, Poland","end_date":"2022-09-16","name":"CONCUR: Conference on Concurrency Theory"},"acknowledgement":"Thomas A. Henzinger: This work was supported in part by the ERC-2020-AdG 101020093.\r\nPatrick Totzke: acknowledges support from the EPSRC, project no. EP/V025848/1.\r\n","file_date_updated":"2023-02-06T09:21:09Z","scopus_import":"1","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.4230/LIPIcs.CONCUR.2022.14","publication":"33rd International Conference on Concurrency Theory","has_accepted_license":"1","department":[{"_id":"ToHe"}],"page":"14:1-14:21","oa_version":"Published Version","citation":{"short":"T.A. Henzinger, K. Lehtinen, P. Totzke, in:, 33rd International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, p. 14:1-14:21.","chicago":"Henzinger, Thomas A, Karoliina Lehtinen, and Patrick Totzke. “History-Deterministic Timed Automata.” In <i>33rd International Conference on Concurrency Theory</i>, 243:14:1-14:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2022.14\">https://doi.org/10.4230/LIPIcs.CONCUR.2022.14</a>.","mla":"Henzinger, Thomas A., et al. “History-Deterministic Timed Automata.” <i>33rd International Conference on Concurrency Theory</i>, vol. 243, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, p. 14:1-14:21, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2022.14\">10.4230/LIPIcs.CONCUR.2022.14</a>.","apa":"Henzinger, T. A., Lehtinen, K., &#38; Totzke, P. (2022). History-deterministic timed automata. In <i>33rd International Conference on Concurrency Theory</i> (Vol. 243, p. 14:1-14:21). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2022.14\">https://doi.org/10.4230/LIPIcs.CONCUR.2022.14</a>","ama":"Henzinger TA, Lehtinen K, Totzke P. History-deterministic timed automata. In: <i>33rd International Conference on Concurrency Theory</i>. Vol 243. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022:14:1-14:21. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2022.14\">10.4230/LIPIcs.CONCUR.2022.14</a>","ieee":"T. A. Henzinger, K. Lehtinen, and P. Totzke, “History-deterministic timed automata,” in <i>33rd International Conference on Concurrency Theory</i>, Warsaw, Poland, 2022, vol. 243, p. 14:1-14:21.","ista":"Henzinger TA, Lehtinen K, Totzke P. 2022. History-deterministic timed automata. 33rd International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 243, 14:1-14:21."},"abstract":[{"text":"We explore the notion of history-determinism in the context of timed automata (TA). History-deterministic automata are those in which nondeterminism can be resolved on the fly, based on the run constructed thus far. History-determinism is a robust property that admits different game-based characterisations, and history-deterministic specifications allow for game-based verification without an expensive determinization step.\r\nWe show yet another characterisation of history-determinism in terms of fair simulation, at the general level of labelled transition systems: a system is history-deterministic precisely if and only if it fairly simulates all language smaller systems.\r\nFor timed automata over infinite timed words it is known that universality is undecidable for Büchi TA. We show that for history-deterministic TA with arbitrary parity acceptance, timed universality, inclusion, and synthesis all remain decidable and are ExpTime-complete.\r\nFor the subclass of TA with safety or reachability acceptance, we show that checking whether such an automaton is history-deterministic is decidable (in ExpTime), and history-deterministic TA with safety acceptance are effectively determinizable without introducing new automata states.","lang":"eng"}],"type":"conference","title":"History-deterministic timed automata","corr_author":"1","article_processing_charge":"No","month":"09","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"name":"Vigilant Algorithmic Monitoring of Software","call_identifier":"H2020","grant_number":"101020093","_id":"62781420-2b32-11ec-9570-8d9b63373d4d"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"}}]