[{"title":"Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks","oa":1,"date_updated":"2024-02-26T10:18:18Z","article_processing_charge":"No","has_accepted_license":"1","scopus_import":"1","intvolume":"       286","language":[{"iso":"eng"}],"publication":"27th International Conference on Principles of Distributed Systems","author":[{"last_name":"Alpos","first_name":"Orestis","full_name":"Alpos, Orestis"},{"first_name":"Ignacio","full_name":"Amores-Sesar, Ignacio","last_name":"Amores-Sesar"},{"first_name":"Christian","full_name":"Cachin, Christian","last_name":"Cachin"},{"last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","first_name":"Michelle X","full_name":"Yeo, Michelle X"}],"arxiv":1,"oa_version":"Published Version","day":"18","file":[{"creator":"dernst","access_level":"open_access","file_size":1505994,"relation":"main_file","content_type":"application/pdf","file_name":"2024_LIPICs_Alpos.pdf","file_id":"15031","checksum":"2993e810a45e8c8056106834b07aea92","success":1,"date_updated":"2024-02-26T10:16:57Z","date_created":"2024-02-26T10:16:57Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"end_date":"2023-12-08","location":"Tokyo, Japan","start_date":"2023-12-06","name":"OPODIS: Conference on Principles of Distributed Systems"},"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773089"]},"month":"01","alternative_title":["LIPIcs"],"status":"public","type":"conference","citation":{"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>.","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.","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>.","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.","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>","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>"},"date_created":"2024-02-18T23:01:02Z","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","year":"2024","article_number":"12","file_date_updated":"2024-02-26T10:16:57Z","_id":"15007","doi":"10.4230/LIPIcs.OPODIS.2023.12","publication_status":"published","external_id":{"arxiv":["2307.02954"]},"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."}],"ddc":["000"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"department":[{"_id":"KrPi"}],"quality_controlled":"1","volume":286,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2024-01-18T00:00:00Z","license":"https://creativecommons.org/licenses/by/4.0/"},{"project":[{"grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures"},{"name":"Wittgenstein Award - Monika Henzinger","grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982"},{"name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775 ","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"quality_controlled":"1","volume":287,"department":[{"_id":"MoHe"}],"date_published":"2024-01-24T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","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"}],"external_id":{"arxiv":["2303.02491"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["000"],"_id":"15008","file_date_updated":"2024-02-26T10:10:48Z","doi":"10.4230/LIPIcs.ITCS.2024.55","date_created":"2024-02-18T23:01:02Z","citation":{"ama":"Goranci G, Henzinger MH, 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. H. 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.","short":"G. Goranci, M.H. 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 H 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>.","ista":"Goranci G, Henzinger MH, 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 Conference, LIPIcs, vol. 287, 55.","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. H., 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>"},"year":"2024","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.","article_number":"55","ec_funded":1,"status":"public","type":"conference","alternative_title":["LIPIcs"],"arxiv":1,"author":[{"full_name":"Goranci, Gramoz","first_name":"Gramoz","last_name":"Goranci"},{"full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Räcke","first_name":"Harald","full_name":"Räcke, Harald"},{"full_name":"Sachdeva, Sushant","first_name":"Sushant","last_name":"Sachdeva"},{"last_name":"Sricharan","full_name":"Sricharan, A. R.","first_name":"A. R."}],"file":[{"creator":"dernst","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_size":1054754,"checksum":"b89716aae6a5599f187897e39de1e53a","file_name":"2024_LIPICs_Goranci.pdf","file_id":"15030","success":1,"date_updated":"2024-02-26T10:10:48Z","date_created":"2024-02-26T10:10:48Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","day":"24","month":"01","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773096"]},"conference":{"name":"ITCS: Innovations in Theoretical Computer Science Conference","start_date":"2024-01-30","location":"Berkeley, CA, United States","end_date":"2024-02-02"},"language":[{"iso":"eng"}],"publication":"15th Innovations in Theoretical Computer Science Conference","title":"Electrical flows for polylogarithmic competitive oblivious routing","article_processing_charge":"No","oa":1,"date_updated":"2025-07-15T12:51:53Z","has_accepted_license":"1","intvolume":"       287","scopus_import":"1"},{"publication":"40th International Symposium on Theoretical Aspects of Computer Science","language":[{"iso":"eng"}],"has_accepted_license":"1","scopus_import":"1","intvolume":"       254","title":"Dynamic maintenance of monotone dynamic programs and applications","article_processing_charge":"No","date_updated":"2023-03-27T06:46:27Z","oa":1,"status":"public","type":"conference","alternative_title":["LIPIcs"],"file":[{"date_updated":"2023-03-27T06:37:22Z","date_created":"2023-03-27T06:37:22Z","file_id":"12769","checksum":"22141ab8bc55188e2dfff665e5daecbd","file_name":"2023_LIPICS_HenzingerM.pdf","success":1,"file_size":872706,"relation":"main_file","content_type":"application/pdf","access_level":"open_access","creator":"dernst"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","day":"01","month":"03","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772662"]},"conference":{"name":"STACS: Symposium on Theoretical Aspects of Computer Science","start_date":"2023-03-07","location":"Hamburg, Germany","end_date":"2023-03-09"},"arxiv":1,"author":[{"first_name":"Monika H","full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"first_name":"Stefan","full_name":"Neumann, Stefan","last_name":"Neumann"},{"last_name":"Räcke","first_name":"Harald","full_name":"Räcke, Harald"},{"full_name":"Schmid, Stefan","first_name":"Stefan","last_name":"Schmid"}],"doi":"10.4230/LIPIcs.STACS.2023.36","_id":"12760","file_date_updated":"2023-03-27T06:37:22Z","article_number":"36","citation":{"ista":"Henzinger MH, 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.","mla":"Henzinger, Monika H., 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>.","chicago":"Henzinger, Monika H, 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>.","short":"M.H. 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.","ieee":"M. H. 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.","ama":"Henzinger MH, 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>","apa":"Henzinger, M. H., 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>"},"date_created":"2023-03-26T22:01:07Z","year":"2023","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.","quality_controlled":"1","volume":254,"department":[{"_id":"MoHe"}],"date_published":"2023-03-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","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."}],"external_id":{"arxiv":["2301.01744"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["000"],"publication_status":"published"},{"alternative_title":["LIPIcs"],"status":"public","type":"conference","author":[{"first_name":"Nicolas","full_name":"Resch, Nicolas","last_name":"Resch"},{"last_name":"Yuan","first_name":"Chen","full_name":"Yuan, Chen"},{"full_name":"Zhang, Yihan","first_name":"Yihan","orcid":"0000-0002-6465-6258","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","last_name":"Zhang"}],"arxiv":1,"conference":{"start_date":"2023-07-10","name":"ICALP: International Colloquium on Automata, Languages, and Programming","end_date":"2023-07-14","location":"Paderborn, Germany"},"publication_identifier":{"isbn":["9783959772785"],"issn":["1868-8969"]},"month":"07","day":"01","oa_version":"Published Version","file":[{"creator":"dernst","access_level":"open_access","content_type":"application/pdf","relation":"main_file","file_size":1141497,"success":1,"file_name":"2023_LIPIcsICALP_Resch.pdf","checksum":"a449143fec3fbebb092cb8ef3b53c226","file_id":"14091","date_created":"2023-08-21T07:23:18Z","date_updated":"2023-08-21T07:23:18Z"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"publication":"50th International Colloquium on Automata, Languages, and Programming","date_updated":"2023-08-21T07:26:01Z","oa":1,"article_processing_charge":"Yes","title":"Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery","has_accepted_license":"1","scopus_import":"1","intvolume":"       261","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2023-07-01T00:00:00Z","department":[{"_id":"MaMo"}],"volume":261,"quality_controlled":"1","publication_status":"published","ddc":["000"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"external_id":{"arxiv":["2210.07754"]},"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."}],"file_date_updated":"2023-08-21T07:23:18Z","_id":"14083","doi":"10.4230/LIPIcs.ICALP.2023.99","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.","year":"2023","citation":{"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>","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>","short":"N. Resch, C. Yuan, Y. Zhang, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","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: International Colloquium on 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>."},"date_created":"2023-08-20T22:01:13Z","article_number":"99"},{"department":[{"_id":"VlKo"}],"volume":261,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2023-07-01T00:00:00Z","external_id":{"arxiv":["2007.10824"]},"abstract":[{"lang":"eng","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."}],"ddc":["000","510"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publication_status":"published","doi":"10.4230/LIPIcs.ICALP.2023.72","file_date_updated":"2023-08-21T06:45:16Z","_id":"14084","article_number":"72","date_created":"2023-08-20T22:01:14Z","citation":{"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>","ista":"Harris DG, Kolmogorov V. 2023. Parameter estimation for Gibbs distributions. 50th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on 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>.","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>.","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.","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>","short":"D.G. Harris, V. Kolmogorov, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023."},"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.","year":"2023","alternative_title":["LIPIcs"],"status":"public","type":"conference","day":"01","oa_version":"Published Version","file":[{"date_updated":"2023-08-21T06:45:16Z","date_created":"2023-08-21T06:45:16Z","file_name":"2023_LIPIcsICALP_Harris.pdf","checksum":"6dee0684245bb1c524b9c955db1e933d","file_id":"14088","success":1,"content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_size":917791,"creator":"dernst"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Paderborn, Germany","end_date":"2023-07-14","name":"ICALP: International Colloquium on Automata, Languages, and Programming","start_date":"2023-07-10"},"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772785"]},"month":"07","author":[{"first_name":"David G.","full_name":"Harris, David G.","last_name":"Harris"},{"first_name":"Vladimir","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov"}],"arxiv":1,"publication":"50th International Colloquium on Automata, Languages, and Programming","language":[{"iso":"eng"}],"has_accepted_license":"1","scopus_import":"1","intvolume":"       261","title":"Parameter estimation for Gibbs distributions","oa":1,"date_updated":"2023-08-21T06:49:11Z","article_processing_charge":"Yes"},{"author":[{"full_name":"Goranci, Gramoz","first_name":"Gramoz","last_name":"Goranci"},{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H"}],"conference":{"end_date":"2023-07-14","location":"Paderborn, Germany","start_date":"2023-07-10","name":"ICALP: International Colloquium on Automata, Languages, and Programming"},"month":"07","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772785"]},"oa_version":"Published Version","day":"01","file":[{"success":1,"checksum":"074177e815a1656de5d4071c7a3dffa6","file_name":"2023_LIPIcsICALP_Goranci.pdf","file_id":"14089","date_created":"2023-08-21T06:59:05Z","date_updated":"2023-08-21T06:59:05Z","creator":"dernst","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_size":875910}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LIPIcs"],"type":"conference","status":"public","oa":1,"date_updated":"2023-08-21T07:00:49Z","article_processing_charge":"Yes","title":"Efficient data structures for incremental exact and approximate maximum flow","has_accepted_license":"1","intvolume":"       261","scopus_import":"1","language":[{"iso":"eng"}],"publication":"50th International Colloquium on Automata, Languages, and Programming","publication_status":"published","ddc":["000"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"external_id":{"unknown":["2211.09606"]},"abstract":[{"lang":"eng","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."}],"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 "}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2023-07-01T00:00:00Z","department":[{"_id":"MoHe"}],"quality_controlled":"1","volume":261,"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.","year":"2023","citation":{"apa":"Goranci, G., &#38; Henzinger, M. H. (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>","short":"G. Goranci, M.H. Henzinger, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","ama":"Goranci G, Henzinger MH. 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. H. 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.","chicago":"Goranci, Gramoz, and Monika H 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>.","mla":"Goranci, Gramoz, and Monika H. 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>.","ista":"Goranci G, Henzinger MH. 2023. Efficient data structures for incremental exact and approximate maximum flow. 50th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 261, 69."},"date_created":"2023-08-20T22:01:14Z","ec_funded":1,"article_number":"69","file_date_updated":"2023-08-21T06:59:05Z","_id":"14085","doi":"10.4230/LIPIcs.ICALP.2023.69"},{"article_number":"35","year":"2023","date_created":"2023-11-05T23:00:53Z","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>.","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.","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>.","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>","short":"V. Aksenov, M. Anoprenko, A. Fedorov, M. Spear, in:, 37th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","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>"},"doi":"10.4230/LIPIcs.DISC.2023.35","file_date_updated":"2023-11-06T11:45:21Z","_id":"14485","ddc":["000"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"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"}],"publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2023-10-01T00:00:00Z","department":[{"_id":"GradSch"}],"quality_controlled":"1","volume":281,"has_accepted_license":"1","intvolume":"       281","scopus_import":"1","oa":1,"date_updated":"2023-11-07T07:48:01Z","article_processing_charge":"Yes","title":"Brief announcement: BatchBoost: Universal batching for concurrent data structures","publication":"37th International Symposium on Distributed Computing","language":[{"iso":"eng"}],"conference":{"start_date":"2023-10-09","name":"DISC: Symposium on Distributed Computing","end_date":"2023-10-13","location":"L'Aquila, Italy"},"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773010"]},"month":"10","day":"01","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"creator":"dernst","file_size":646665,"access_level":"open_access","content_type":"application/pdf","relation":"main_file","success":1,"file_id":"14492","file_name":"2023_LIPIcs_Aksenov.pdf","checksum":"d9f8d2915cccdf2df5905b7cd1b4a560","date_created":"2023-11-06T11:45:21Z","date_updated":"2023-11-06T11:45:21Z"}],"author":[{"full_name":"Aksenov, Vitaly","first_name":"Vitaly","last_name":"Aksenov"},{"full_name":"Anoprenko, Michael","first_name":"Michael","last_name":"Anoprenko"},{"id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6","last_name":"Fedorov","full_name":"Fedorov, Alexander","first_name":"Alexander"},{"full_name":"Spear, Michael","first_name":"Michael","last_name":"Spear"}],"alternative_title":["LIPIcs"],"type":"conference","status":"public"},{"doi":"10.4230/LIPIcs.AFT.2023.7","_id":"14516","file_date_updated":"2023-11-13T08:44:34Z","article_number":"7","year":"2023","acknowledgement":"Work done when all the authors were at Novi Research, Meta.","citation":{"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>.","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>.","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>","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.","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.","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>"},"date_created":"2023-11-12T23:00:55Z","date_published":"2023-10-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","volume":282,"department":[{"_id":"ElKo"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["000"],"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."}],"publication_status":"published","publication":"5th Conference on Advances in Financial Technologies","language":[{"iso":"eng"}],"scopus_import":"1","has_accepted_license":"1","intvolume":"       282","article_processing_charge":"Yes","date_updated":"2023-11-13T08:52:01Z","oa":1,"title":"STROBE: Streaming Threshold Random Beacons","status":"public","type":"conference","alternative_title":["LIPIcs"],"month":"10","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773034"]},"conference":{"name":"AFT: Conference on Advances in Financial Technologies","start_date":"2023-10-23","location":"Princeton, NJ, United States","end_date":"2023-10-25"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"creator":"dernst","access_level":"open_access","relation":"main_file","file_size":793495,"content_type":"application/pdf","success":1,"file_id":"14521","checksum":"c1f98831cb5149d6c030c41999e6e960","file_name":"2023_LIPIcs_Beaver.pdf","date_created":"2023-11-13T08:44:34Z","date_updated":"2023-11-13T08:44:34Z"}],"day":"01","oa_version":"Published Version","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1643"}],"author":[{"first_name":"Donald","full_name":"Beaver, Donald","last_name":"Beaver"},{"full_name":"Kelkar, Mahimna","first_name":"Mahimna","last_name":"Kelkar"},{"last_name":"Lewi","full_name":"Lewi, Kevin","first_name":"Kevin"},{"last_name":"Nikolaenko","first_name":"Valeria","full_name":"Nikolaenko, Valeria"},{"last_name":"Sonnino","first_name":"Alberto","full_name":"Sonnino, Alberto"},{"full_name":"Chalkias, Konstantinos","first_name":"Konstantinos","last_name":"Chalkias"},{"first_name":"Eleftherios","full_name":"Kokoris Kogias, Eleftherios","last_name":"Kokoris Kogias","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30"},{"full_name":"Naurois, Ladi De","first_name":"Ladi De","last_name":"Naurois"},{"last_name":"Roy","full_name":"Roy, Arnab","first_name":"Arnab"}]},{"ec_funded":1,"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","year":"2022","date_created":"2023-02-05T17:24:23Z","citation":{"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.","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>.","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>.","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.","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.","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>","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>"},"doi":"10.4230/LIPIcs.CONCUR.2022.14","file_date_updated":"2023-02-06T09:21:09Z","_id":"12508","ddc":["000"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"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"}],"publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2022-09-06T00:00:00Z","department":[{"_id":"ToHe"}],"page":"14:1-14:21","volume":243,"quality_controlled":"1","project":[{"name":"Vigilant Algorithmic Monitoring of Software","call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093"}],"has_accepted_license":"1","intvolume":"       243","scopus_import":"1","oa":1,"date_updated":"2023-02-06T09:23:31Z","article_processing_charge":"No","title":"History-deterministic timed automata","publication":"33rd International Conference on Concurrency Theory","language":[{"iso":"eng"}],"conference":{"end_date":"2022-09-16","location":"Warsaw, Poland","start_date":"2022-09-13","name":"CONCUR: Conference on Concurrency Theory"},"publication_identifier":{"isbn":["9783959772464"],"issn":["1868-8969"]},"month":"09","oa_version":"Published Version","day":"06","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"creator":"dernst","access_level":"open_access","file_size":717940,"relation":"main_file","content_type":"application/pdf","success":1,"file_id":"12520","checksum":"9e97e15628f66b2ad77f535bb0327dee","file_name":"2022_LIPICs_Henzinger2.pdf","date_created":"2023-02-06T09:21:09Z","date_updated":"2023-02-06T09:21:09Z"}],"author":[{"first_name":"Thomas A","full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2985-7724"},{"full_name":"Lehtinen, Karoliina","first_name":"Karoliina","last_name":"Lehtinen"},{"first_name":"Patrick","full_name":"Totzke, Patrick","last_name":"Totzke"}],"alternative_title":["LIPIcs"],"status":"public","type":"conference"},{"ec_funded":1,"acknowledgement":"Guy Avni: Work partially supported by the Israel Science Foundation, ISF grant agreement\r\nno 1679/21.\r\nThomas A. Henzinger: This work was supported in part by the ERC-2020-AdG 101020093.\r\nWe would like to thank all our collaborators Milad Aghajohari, Ventsislav Chonev, Rasmus Ibsen-Jensen, Ismäel Jecker, Petr Novotný, Josef Tkadlec, and Ðorđe Žikelić; we hope the collaboration was as fun and meaningful for you as it was for us.","year":"2022","citation":{"mla":"Avni, Guy, and Thomas A. Henzinger. “An Updated Survey of Bidding Games on Graphs.” <i>47th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 241, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, p. 3:1-3:6, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2022.3\">10.4230/LIPIcs.MFCS.2022.3</a>.","ista":"Avni G, Henzinger TA. 2022. An updated survey of bidding games on graphs. 47th International Symposium on Mathematical Foundations of Computer Science. MFCS: Symposium on Mathematical Foundations of Computer ScienceLeibniz International Proceedings in Informatics (LIPIcs) vol. 241, 3:1-3:6.","chicago":"Avni, Guy, and Thomas A Henzinger. “An Updated Survey of Bidding Games on Graphs.” In <i>47th International Symposium on Mathematical Foundations of Computer Science</i>, 241:3:1-3:6. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2022.3\">https://doi.org/10.4230/LIPIcs.MFCS.2022.3</a>.","short":"G. Avni, T.A. Henzinger, in:, 47th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2022, p. 3:1-3:6.","ieee":"G. Avni and T. A. Henzinger, “An updated survey of bidding games on graphs,” in <i>47th International Symposium on Mathematical Foundations of Computer Science</i>, Vienna, Austria, 2022, vol. 241, p. 3:1-3:6.","ama":"Avni G, Henzinger TA. An updated survey of bidding games on graphs. In: <i>47th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 241. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022:3:1-3:6. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2022.3\">10.4230/LIPIcs.MFCS.2022.3</a>","apa":"Avni, G., &#38; Henzinger, T. A. (2022). An updated survey of bidding games on graphs. In <i>47th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 241, p. 3:1-3:6). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2022.3\">https://doi.org/10.4230/LIPIcs.MFCS.2022.3</a>"},"date_created":"2023-02-05T17:26:01Z","doi":"10.4230/LIPIcs.MFCS.2022.3","file_date_updated":"2023-02-06T09:13:04Z","_id":"12509","ddc":["000"],"series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"abstract":[{"lang":"eng","text":"A graph game is a two-player zero-sum game in which the players move a token throughout a graph to produce an infinite path, which determines the winner or payoff of the game. In bidding games, both players have budgets, and in each turn, we hold an \"auction\" (bidding) to determine which player moves the token. In this survey, we consider several bidding mechanisms and their effect on the properties of the game. Specifically, bidding games, and in particular bidding games of infinite duration, have an intriguing equivalence with random-turn games in which in each turn, the player who moves is chosen randomly. We summarize how minor changes in the bidding mechanism lead to unexpected differences in the equivalence with random-turn games."}],"place":"Dagstuhl, Germany","publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2022-08-22T00:00:00Z","department":[{"_id":"ToHe"}],"page":"3:1-3:6","volume":241,"quality_controlled":"1","project":[{"_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093","call_identifier":"H2020","name":"Vigilant Algorithmic Monitoring of Software"}],"scopus_import":"1","has_accepted_license":"1","intvolume":"       241","date_updated":"2023-02-06T09:16:54Z","oa":1,"article_processing_charge":"No","title":"An updated survey of bidding games on graphs","publication":"47th International Symposium on Mathematical Foundations of Computer Science","language":[{"iso":"eng"}],"conference":{"start_date":"2022-08-22","name":"MFCS: Symposium on Mathematical Foundations of Computer Science","end_date":"2022-08-26","location":"Vienna, Austria"},"month":"08","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772563"]},"day":"22","oa_version":"Published Version","file":[{"access_level":"open_access","file_size":624586,"content_type":"application/pdf","relation":"main_file","creator":"dernst","date_created":"2023-02-06T09:13:04Z","date_updated":"2023-02-06T09:13:04Z","success":1,"checksum":"1888ec9421622f9526fbec2de035f132","file_name":"2022_LIPICs_Avni.pdf","file_id":"12519"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","last_name":"Avni","orcid":"0000-0001-5588-8287","full_name":"Avni, Guy","first_name":"Guy"},{"first_name":"Thomas A","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000-0002-2985-7724"}],"status":"public","type":"conference"},{"title":"Anytime guarantees for reachability in uncountable Markov decision processes","article_processing_charge":"No","oa":1,"date_updated":"2023-09-26T10:43:30Z","scopus_import":"1","intvolume":"       243","has_accepted_license":"1","language":[{"iso":"eng"}],"publication":"33rd International Conference on Concurrency Theory ","arxiv":1,"author":[{"last_name":"Grover","full_name":"Grover, Kush","first_name":"Kush"},{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","last_name":"Kretinsky","orcid":"0000-0002-8122-2881","first_name":"Jan","full_name":"Kretinsky, Jan"},{"id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","last_name":"Meggendorfer","orcid":"0000-0002-1712-2165","full_name":"Meggendorfer, Tobias","first_name":"Tobias"},{"first_name":"Maimilian","full_name":"Weininger, Maimilian","last_name":"Weininger"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"date_updated":"2023-09-26T10:43:15Z","date_created":"2023-09-26T10:43:15Z","file_id":"14372","file_name":"2022_LIPIcS_Grover.pdf","checksum":"e282e43d3ae0ba6e067b72f4583e13c0","success":1,"relation":"main_file","content_type":"application/pdf","file_size":960036,"access_level":"open_access","creator":"dernst"}],"oa_version":"Published Version","day":"15","publication_identifier":{"issn":["1868-8969"]},"month":"09","conference":{"location":"Warsaw, Poland","end_date":"2022-09-16","name":"CONCUR: Conference on Concurrency Theory","start_date":"2022-09-13"},"status":"public","type":"conference","alternative_title":["LIPIcs"],"citation":{"apa":"Grover, K., Kretinsky, J., Meggendorfer, T., &#38; Weininger, M. (2022). Anytime guarantees for reachability in uncountable Markov decision processes. In <i>33rd International Conference on Concurrency Theory </i> (Vol. 243). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2022.11\">https://doi.org/10.4230/LIPIcs.CONCUR.2022.11</a>","short":"K. Grover, J. Kretinsky, T. Meggendorfer, M. Weininger, in:, 33rd International Conference on Concurrency Theory , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","ieee":"K. Grover, J. Kretinsky, T. Meggendorfer, and M. Weininger, “Anytime guarantees for reachability in uncountable Markov decision processes,” in <i>33rd International Conference on Concurrency Theory </i>, Warsaw, Poland, 2022, vol. 243.","ama":"Grover K, Kretinsky J, Meggendorfer T, Weininger M. Anytime guarantees for reachability in uncountable Markov decision processes. In: <i>33rd International Conference on Concurrency Theory </i>. Vol 243. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2022.11\">10.4230/LIPIcs.CONCUR.2022.11</a>","mla":"Grover, Kush, et al. “Anytime Guarantees for Reachability in Uncountable Markov Decision Processes.” <i>33rd International Conference on Concurrency Theory </i>, vol. 243, 11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2022.11\">10.4230/LIPIcs.CONCUR.2022.11</a>.","chicago":"Grover, Kush, Jan Kretinsky, Tobias Meggendorfer, and Maimilian Weininger. “Anytime Guarantees for Reachability in Uncountable Markov Decision Processes.” In <i>33rd International Conference on Concurrency Theory </i>, Vol. 243. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2022.11\">https://doi.org/10.4230/LIPIcs.CONCUR.2022.11</a>.","ista":"Grover K, Kretinsky J, Meggendorfer T, Weininger M. 2022. Anytime guarantees for reachability in uncountable Markov decision processes. 33rd International Conference on Concurrency Theory . CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 243, 11."},"date_created":"2023-03-28T08:09:32Z","year":"2022","acknowledgement":"Kush Grover: The author has been supported by the DFG research training group GRK\r\n2428 ConVeY.\r\nMaximilian Weininger: The author has been partially supported by DFG projects 383882557\r\nStatistical Unbounded Verification (SUV) and 427755713 Group-By Objectives in Probabilistic\r\nVerification (GOPro)","article_number":"11","_id":"12775","file_date_updated":"2023-09-26T10:43:15Z","doi":"10.4230/LIPIcs.CONCUR.2022.11","publication_status":"published","abstract":[{"text":"We consider the problem of approximating the reachability probabilities in Markov decision processes (MDP) with uncountable (continuous) state and action spaces. While there are algorithms that, for special classes of such MDP, provide a sequence of approximations converging to the true value in the limit, our aim is to obtain an algorithm with guarantees on the precision of the approximation.\r\nAs this problem is undecidable in general, assumptions on the MDP are necessary. Our main contribution is to identify sufficient assumptions that are as weak as possible, thus approaching the \"boundary\" of which systems can be correctly and reliably analyzed. To this end, we also argue why each of our assumptions is necessary for algorithms based on processing finitely many observations.\r\nWe present two solution variants. The first one provides converging lower bounds under weaker assumptions than typical ones from previous works concerned with guarantees. The second one then utilizes stronger assumptions to additionally provide converging upper bounds. Altogether, we obtain an anytime algorithm, i.e. yielding a sequence of approximants with known and iteratively improving precision, converging to the true value in the limit. Besides, due to the generality of our assumptions, our algorithms are very general templates, readily allowing for various heuristics from literature in contrast to, e.g., a specific discretization algorithm. Our theoretical contribution thus paves the way for future practical improvements without sacrificing correctness guarantees.","lang":"eng"}],"external_id":{"arxiv":["2008.04824"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["000"],"quality_controlled":"1","volume":243,"department":[{"_id":"KrCh"}],"date_published":"2022-09-15T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik"},{"has_accepted_license":"1","intvolume":"       217","scopus_import":"1","editor":[{"full_name":"Bramas, Quentin","first_name":"Quentin","last_name":"Bramas"},{"last_name":"Gramoli","first_name":"Vincent","full_name":"Gramoli, Vincent"},{"full_name":"Milani, Alessia","first_name":"Alessia","last_name":"Milani"}],"title":"Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters","article_processing_charge":"No","date_updated":"2022-05-02T07:56:35Z","oa":1,"publication":"25th International Conference on Principles of Distributed Systems","language":[{"iso":"eng"}],"file":[{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_size":790396,"creator":"dernst","date_created":"2022-05-02T07:53:00Z","date_updated":"2022-05-02T07:53:00Z","success":1,"checksum":"626551c14de5d4091573200ed0535752","file_id":"11345","file_name":"2022_LIPICs_Nikabadi.pdf"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","day":"01","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772198"]},"month":"02","conference":{"location":"Strasbourg, France","end_date":"2021-12-15","name":"OPODIS","start_date":"2021-12-13"},"author":[{"last_name":"Nikabadi","first_name":"Amir","full_name":"Nikabadi, Amir"},{"full_name":"Korhonen, Janne","first_name":"Janne","last_name":"Korhonen","id":"C5402D42-15BC-11E9-A202-CA2BE6697425"}],"type":"conference","status":"public","alternative_title":["LIPIcs"],"article_number":"15","ec_funded":1,"citation":{"ieee":"A. Nikabadi and J. Korhonen, “Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters,” in <i>25th International Conference on Principles of Distributed Systems</i>, Strasbourg, France, 2022, vol. 217.","ama":"Nikabadi A, Korhonen J. Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters. In: Bramas Q, Gramoli V, Milani A, eds. <i>25th International Conference on Principles of Distributed Systems</i>. Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2021.15\">10.4230/LIPIcs.OPODIS.2021.15</a>","short":"A. Nikabadi, J. Korhonen, in:, Q. Bramas, V. Gramoli, A. Milani (Eds.), 25th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","ista":"Nikabadi A, Korhonen J. 2022. Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters. 25th International Conference on Principles of Distributed Systems. OPODIS, LIPIcs, vol. 217, 15.","chicago":"Nikabadi, Amir, and Janne Korhonen. “Beyond Distributed Subgraph Detection: Induced Subgraphs, Multicolored Problems and Graph Parameters.” In <i>25th International Conference on Principles of Distributed Systems</i>, edited by Quentin Bramas, Vincent Gramoli, and Alessia Milani, Vol. 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2021.15\">https://doi.org/10.4230/LIPIcs.OPODIS.2021.15</a>.","mla":"Nikabadi, Amir, and Janne Korhonen. “Beyond Distributed Subgraph Detection: Induced Subgraphs, Multicolored Problems and Graph Parameters.” <i>25th International Conference on Principles of Distributed Systems</i>, edited by Quentin Bramas et al., vol. 217, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2021.15\">10.4230/LIPIcs.OPODIS.2021.15</a>.","apa":"Nikabadi, A., &#38; Korhonen, J. (2022). Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters. In Q. Bramas, V. Gramoli, &#38; A. Milani (Eds.), <i>25th International Conference on Principles of Distributed Systems</i> (Vol. 217). Strasbourg, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2021.15\">https://doi.org/10.4230/LIPIcs.OPODIS.2021.15</a>"},"date_created":"2022-04-17T22:01:47Z","year":"2022","acknowledgement":"Amir Nikabadi: Supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR). Janne H. Korhonen: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).\r\nWe thank François Le Gall and Masayuki Miyamoto for sharing their work on lower bounds for induced subgraph detection [36].","doi":"10.4230/LIPIcs.OPODIS.2021.15","_id":"11183","file_date_updated":"2022-05-02T07:53:00Z","abstract":[{"lang":"eng","text":"Subgraph detection has recently been one of the most studied problems in the CONGEST model of distributed computing. In this work, we study the distributed complexity of problems closely related to subgraph detection, mainly focusing on induced subgraph detection. The main line of this work presents lower bounds and parameterized algorithms w.r.t structural parameters of the input graph:\r\n- On general graphs, we give unconditional lower bounds for induced detection of cycles and patterns of treewidth 2 in CONGEST. Moreover, by adapting reductions from centralized parameterized complexity, we prove lower bounds in CONGEST for detecting patterns with a 4-clique, and for induced path detection conditional on the hardness of triangle detection in the congested clique.\r\n- On graphs of bounded degeneracy, we show that induced paths can be detected fast in CONGEST using techniques from parameterized algorithms, while detecting cycles and patterns of treewidth 2 is hard.\r\n- On graphs of bounded vertex cover number, we show that induced subgraph detection is easy in CONGEST for any pattern graph. More specifically, we adapt a centralized parameterized algorithm for a more general maximum common induced subgraph detection problem to the distributed setting. In addition to these induced subgraph detection results, we study various related problems in the CONGEST and congested clique models, including for multicolored versions of subgraph-detection-like problems."}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["510"],"publication_status":"published","volume":217,"quality_controlled":"1","department":[{"_id":"DaAl"}],"date_published":"2022-02-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223"}]},{"language":[{"iso":"eng"}],"publication":"25th International Conference on Principles of Distributed Systems","title":"Fast graphical population protocols","oa":1,"date_updated":"2022-05-02T08:09:39Z","article_processing_charge":"No","has_accepted_license":"1","intvolume":"       217","scopus_import":"1","editor":[{"full_name":"Bramas, Quentin","first_name":"Quentin","last_name":"Bramas"},{"last_name":"Gramoli","full_name":"Gramoli, Vincent","first_name":"Vincent"},{"last_name":"Milani","first_name":"Alessia","full_name":"Milani, Alessia"}],"alternative_title":["LIPIcs"],"status":"public","type":"conference","author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian"},{"last_name":"Gelashvili","full_name":"Gelashvili, Rati","first_name":"Rati"},{"full_name":"Rybicki, Joel","first_name":"Joel","orcid":"0000-0002-6432-6646","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","last_name":"Rybicki"}],"arxiv":1,"oa_version":"Published Version","day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"creator":"dernst","content_type":"application/pdf","access_level":"open_access","file_size":959406,"relation":"main_file","success":1,"checksum":"2c7c982174c6f98c4ca6e92539d15086","file_id":"11346","file_name":"2022_LIPICs_Alistarh.pdf","date_created":"2022-05-02T08:06:33Z","date_updated":"2022-05-02T08:06:33Z"}],"conference":{"start_date":"2021-12-13","name":"OPODIS","end_date":"2021-12-15","location":"Strasbourg, France"},"month":"02","publication_identifier":{"isbn":["9783959772198"],"issn":["1868-8969"]},"file_date_updated":"2022-05-02T08:06:33Z","_id":"11184","doi":"10.4230/LIPIcs.OPODIS.2021.14","citation":{"ama":"Alistarh D-A, Gelashvili R, Rybicki J. Fast graphical population protocols. In: Bramas Q, Gramoli V, Milani A, eds. <i>25th International Conference on Principles of Distributed Systems</i>. Vol 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2021.14\">10.4230/LIPIcs.OPODIS.2021.14</a>","ieee":"D.-A. Alistarh, R. Gelashvili, and J. Rybicki, “Fast graphical population protocols,” in <i>25th International Conference on Principles of Distributed Systems</i>, Strasbourg, France, 2022, vol. 217.","short":"D.-A. Alistarh, R. Gelashvili, J. Rybicki, in:, Q. Bramas, V. Gramoli, A. Milani (Eds.), 25th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","mla":"Alistarh, Dan-Adrian, et al. “Fast Graphical Population Protocols.” <i>25th International Conference on Principles of Distributed Systems</i>, edited by Quentin Bramas et al., vol. 217, 14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2021.14\">10.4230/LIPIcs.OPODIS.2021.14</a>.","chicago":"Alistarh, Dan-Adrian, Rati Gelashvili, and Joel Rybicki. “Fast Graphical Population Protocols.” In <i>25th International Conference on Principles of Distributed Systems</i>, edited by Quentin Bramas, Vincent Gramoli, and Alessia Milani, Vol. 217. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2021.14\">https://doi.org/10.4230/LIPIcs.OPODIS.2021.14</a>.","ista":"Alistarh D-A, Gelashvili R, Rybicki J. 2022. Fast graphical population protocols. 25th International Conference on Principles of Distributed Systems. OPODIS, LIPIcs, vol. 217, 14.","apa":"Alistarh, D.-A., Gelashvili, R., &#38; Rybicki, J. (2022). Fast graphical population protocols. In Q. Bramas, V. Gramoli, &#38; A. Milani (Eds.), <i>25th International Conference on Principles of Distributed Systems</i> (Vol. 217). Strasbourg, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2021.14\">https://doi.org/10.4230/LIPIcs.OPODIS.2021.14</a>"},"date_created":"2022-04-17T22:01:47Z","acknowledgement":"Dan Alistarh: This project has received funding from the European Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation programme (grant agreement No.805223 ScaleML).\r\nJoel Rybicki: This project has received from the European Union’s Horizon 2020 research and\r\ninnovation programme under the Marie Skłodowska-Curie grant agreement No. 840605.\r\nAcknowledgements We grateful to Giorgi Nadiradze for pointing out a generalisation of the phase clock construction to non-regular graphs. We also thank anonymous reviewers for their useful comments on earlier versions of this manuscript.","year":"2022","ec_funded":1,"article_number":"14","project":[{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning"},{"grant_number":"840605","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","name":"Coordination in constrained and natural distributed systems","call_identifier":"H2020"}],"department":[{"_id":"DaAl"}],"volume":217,"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2022-02-01T00:00:00Z","publication_status":"published","external_id":{"arxiv":["2102.08808"]},"abstract":[{"lang":"eng","text":"Let G be a graph on n nodes. In the stochastic population protocol model, a collection of n indistinguishable, resource-limited nodes collectively solve tasks via pairwise interactions. In each interaction, two randomly chosen neighbors first read each other’s states, and then update their local states. A rich line of research has established tight upper and lower bounds on the complexity of fundamental tasks, such as majority and leader election, in this model, when G is a clique. Specifically, in the clique, these tasks can be solved fast, i.e., in n polylog n pairwise interactions, with high probability, using at most polylog n states per node.\r\nIn this work, we consider the more general setting where G is an arbitrary regular graph, and present a technique for simulating protocols designed for fully-connected networks in any connected regular graph. Our main result is a simulation that is efficient on many interesting graph families: roughly, the simulation overhead is polylogarithmic in the number of nodes, and quadratic in the conductance of the graph. As a sample application, we show that, in any regular graph with conductance φ, both leader election and exact majority can be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability, using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast and space-efficient population protocols for leader election and exact majority on graphs with good expansion properties. We believe our results will prove generally useful, as they allow efficient technology transfer between the well-mixed (clique) case, and the under-explored spatial setting."}],"ddc":["510"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"}},{"month":"06","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-227-3"]},"conference":{"start_date":"2022-06-07","name":"SoCG: Symposium on Computational Geometry","end_date":"2022-06-10","location":"Berlin, Germany"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file":[{"success":1,"file_name":"2022_LIPICs_Chambers.pdf","checksum":"b25ce40fade4ebc0bcaae176db4f5f1f","file_id":"11437","date_created":"2022-06-07T07:58:30Z","date_updated":"2022-06-07T07:58:30Z","creator":"dernst","file_size":17580705,"content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"day":"01","oa_version":"Published Version","author":[{"first_name":"Erin","full_name":"Chambers, Erin","last_name":"Chambers"},{"id":"35638A5C-AAC7-11E9-B0BF-5503E6697425","last_name":"Fillmore","first_name":"Christopher D","full_name":"Fillmore, Christopher D"},{"orcid":"0000-0002-6862-208X","id":"2D04F932-F248-11E8-B48F-1D18A9856A87","last_name":"Stephenson","first_name":"Elizabeth R","full_name":"Stephenson, Elizabeth R"},{"orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","last_name":"Wintraecken","full_name":"Wintraecken, Mathijs","first_name":"Mathijs"}],"status":"public","type":"conference","editor":[{"last_name":"Goaoc","full_name":"Goaoc, Xavier","first_name":"Xavier"},{"last_name":"Kerber","first_name":"Michael","full_name":"Kerber, Michael"}],"scopus_import":"1","has_accepted_license":"1","intvolume":"       224","article_processing_charge":"No","date_updated":"2023-02-21T09:50:52Z","oa":1,"title":"A cautionary tale: Burning the medial axis is unstable","publication":"38th International Symposium on Computational Geometry","language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["510"],"series_title":"LIPIcs","abstract":[{"text":"The medial axis of a set consists of the points in the ambient space without a unique closest point on the original set. Since its introduction, the medial axis has been used extensively in many applications as a method of computing a topologically equivalent skeleton. Unfortunately, one limiting factor in the use of the medial axis of a smooth manifold is that it is not necessarily topologically stable under small perturbations of the manifold. To counter these instabilities various prunings of the medial axis have been proposed. Here, we examine one type of pruning, called burning. Because of the good experimental results, it was hoped that the burning method of simplifying the medial axis would be stable. In this work we show a simple example that dashes such hopes based on Bing’s house with two rooms, demonstrating an isotopy of a shape where the medial axis goes from collapsible to non-collapsible.","lang":"eng"}],"publication_status":"published","date_published":"2022-06-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","volume":224,"department":[{"_id":"HeEd"}],"page":"66:1-66:9","project":[{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073","name":"Learning and triangulating manifolds via collapses"},{"call_identifier":"H2020","name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183"},{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}],"ec_funded":1,"year":"2022","acknowledgement":"Partially supported by the DFG Collaborative Research Center TRR 109, “Discretization in Geometry and Dynamics” and the European Research Council (ERC), grant no. 788183, “Alpha Shape Theory Extended”. Erin Chambers: Supported in part by the National Science Foundation through grants DBI-1759807, CCF-1907612, and CCF-2106672. Mathijs Wintraecken: Supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411. The Austrian science fund (FWF) M-3073 Acknowledgements We thank André Lieutier, David Letscher, Ellen Gasparovic, Kathryn Leonard, and Tao Ju for early discussions on this work. We also thank Lu Liu, Yajie Yan and Tao Ju for sharing code to generate the examples.","date_created":"2022-06-01T14:18:04Z","citation":{"apa":"Chambers, E., Fillmore, C. D., Stephenson, E. R., &#38; Wintraecken, M. (2022). A cautionary tale: Burning the medial axis is unstable. In X. Goaoc &#38; M. Kerber (Eds.), <i>38th International Symposium on Computational Geometry</i> (Vol. 224, p. 66:1-66:9). Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2022.66\">https://doi.org/10.4230/LIPIcs.SoCG.2022.66</a>","short":"E. Chambers, C.D. Fillmore, E.R. Stephenson, M. Wintraecken, in:, X. Goaoc, M. Kerber (Eds.), 38th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, p. 66:1-66:9.","ama":"Chambers E, Fillmore CD, Stephenson ER, Wintraecken M. A cautionary tale: Burning the medial axis is unstable. In: Goaoc X, Kerber M, eds. <i>38th International Symposium on Computational Geometry</i>. Vol 224. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022:66:1-66:9. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2022.66\">10.4230/LIPIcs.SoCG.2022.66</a>","ieee":"E. Chambers, C. D. Fillmore, E. R. Stephenson, and M. Wintraecken, “A cautionary tale: Burning the medial axis is unstable,” in <i>38th International Symposium on Computational Geometry</i>, Berlin, Germany, 2022, vol. 224, p. 66:1-66:9.","ista":"Chambers E, Fillmore CD, Stephenson ER, Wintraecken M. 2022. A cautionary tale: Burning the medial axis is unstable. 38th International Symposium on Computational Geometry. SoCG: Symposium on Computational GeometryLIPIcs vol. 224, 66:1-66:9.","mla":"Chambers, Erin, et al. “A Cautionary Tale: Burning the Medial Axis Is Unstable.” <i>38th International Symposium on Computational Geometry</i>, edited by Xavier Goaoc and Michael Kerber, vol. 224, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, p. 66:1-66:9, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2022.66\">10.4230/LIPIcs.SoCG.2022.66</a>.","chicago":"Chambers, Erin, Christopher D Fillmore, Elizabeth R Stephenson, and Mathijs Wintraecken. “A Cautionary Tale: Burning the Medial Axis Is Unstable.” In <i>38th International Symposium on Computational Geometry</i>, edited by Xavier Goaoc and Michael Kerber, 224:66:1-66:9. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2022.66\">https://doi.org/10.4230/LIPIcs.SoCG.2022.66</a>."},"doi":"10.4230/LIPIcs.SoCG.2022.66","_id":"11428","file_date_updated":"2022-06-07T07:58:30Z"},{"quality_controlled":"1","volume":221,"extern":"1","date_published":"2022-04-29T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","abstract":[{"lang":"eng","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."}],"external_id":{"arxiv":["2106.15524"]},"_id":"11812","doi":"10.4230/LIPIcs.SAND.2022.18","date_created":"2022-08-12T06:57:55Z","citation":{"short":"K. Hanauer, M.H. Henzinger, Q.C. Hua, in:, 1st Symposium on Algorithmic Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","ama":"Hanauer K, Henzinger MH, 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. H. 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.","chicago":"Hanauer, Kathrin, Monika H 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>.","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>.","ista":"Hanauer K, Henzinger MH, 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.","apa":"Hanauer, K., Henzinger, M. H., &#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>"},"year":"2022","article_number":"18","type":"conference","status":"public","alternative_title":["LIPIcs"],"arxiv":1,"author":[{"last_name":"Hanauer","full_name":"Hanauer, Kathrin","first_name":"Kathrin"},{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"full_name":"Hua, Qi Cheng","first_name":"Qi Cheng","last_name":"Hua"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.SAND.2022.18","open_access":"1"}],"day":"29","oa_version":"Published Version","month":"04","publication_identifier":{"isbn":["9783959772242"],"issn":["1868-8969"]},"conference":{"name":"SAND: Symposium on Algorithmic Foundations of Dynamic Networks","start_date":"2022-04-28","location":"Virtual","end_date":"2022-04-30"},"language":[{"iso":"eng"}],"publication":"1st Symposium on Algorithmic Foundations of Dynamic Networks","title":"Fully dynamic four-vertex subgraph counting","article_processing_charge":"No","oa":1,"date_updated":"2023-02-14T08:25:42Z","scopus_import":"1","intvolume":"       221"},{"has_accepted_license":"1","intvolume":"       250","scopus_import":"1","oa":1,"date_updated":"2025-07-14T09:09:55Z","article_processing_charge":"No","title":"Complexity of spatial games","publication":"42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","language":[{"iso":"eng"}],"conference":{"name":"FSTTC: Foundations of Software Technology and Theoretical Computer Science","start_date":"2022-12-18","location":"Madras, India","end_date":"2022-12-20"},"month":"12","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772617"]},"oa_version":"Published Version","day":"14","file":[{"relation":"main_file","content_type":"application/pdf","access_level":"open_access","file_size":657396,"creator":"dernst","date_created":"2023-01-20T10:19:19Z","date_updated":"2023-01-20T10:19:19Z","success":1,"file_id":"12323","file_name":"2022_LIPICs_Chatterjee.pdf","checksum":"a21e3ba2421e2c4a06aa2cb6d530ede1"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus"},{"id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","last_name":"Jecker","full_name":"Jecker, Ismael R","first_name":"Ismael R"},{"first_name":"Jakub","full_name":"Svoboda, Jakub","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","orcid":"0000-0002-1419-3267"}],"type":"conference","status":"public","ec_funded":1,"article_number":"11:1-11:14","acknowledgement":"Krishnendu Chatterjee: The research was partially supported by the ERC CoG 863818\r\n(ForM-SMArt).\r\nIsmaël Jecker: The research was partially supported by the ERC grant 950398 (INFSYS).\r\nJakub Svoboda: The research was partially supported by the ERC CoG 863818 (ForM-SMArt)","year":"2022","citation":{"ieee":"K. Chatterjee, R. Ibsen-Jensen, I. R. Jecker, and J. Svoboda, “Complexity of spatial games,” in <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Madras, India, 2022, vol. 250.","ama":"Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. Complexity of spatial games. 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.11\">10.4230/LIPIcs.FSTTCS.2022.11</a>","short":"K. Chatterjee, R. Ibsen-Jensen, I.R. Jecker, J. Svoboda, in:, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, Ismael R Jecker, and Jakub Svoboda. “Complexity of Spatial Games.” 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.11\">https://doi.org/10.4230/LIPIcs.FSTTCS.2022.11</a>.","mla":"Chatterjee, Krishnendu, et al. “Complexity of Spatial Games.” <i>42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, vol. 250, 11:1-11:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2022.11\">10.4230/LIPIcs.FSTTCS.2022.11</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Jecker IR, Svoboda J. 2022. Complexity of spatial games. 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTC: Foundations of Software Technology and Theoretical Computer Science vol. 250, 11:1-11:14.","apa":"Chatterjee, K., Ibsen-Jensen, R., Jecker, I. R., &#38; Svoboda, J. (2022). Complexity of spatial games. 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.11\">https://doi.org/10.4230/LIPIcs.FSTTCS.2022.11</a>"},"date_created":"2023-01-01T23:00:50Z","doi":"10.4230/LIPIcs.FSTTCS.2022.11","file_date_updated":"2023-01-20T10:19:19Z","_id":"12101","ddc":["000"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"abstract":[{"lang":"eng","text":"Spatial games form a widely-studied class of games from biology and physics modeling the evolution of social behavior. Formally, such a game is defined by a square (d by d) payoff matrix M and an undirected graph G. Each vertex of G represents an individual, that initially follows some strategy i ∈ {1,2,…,d}. In each round of the game, every individual plays the matrix game with each of its neighbors: An individual following strategy i meeting a neighbor following strategy j receives a payoff equal to the entry (i,j) of M. Then, each individual updates its strategy to its neighbors' strategy with the highest sum of payoffs, and the next round starts. The basic computational problems consist of reachability between configurations and the average frequency of a strategy. For general spatial games and graphs, these problems are in PSPACE. In this paper, we examine restricted setting: the game is a prisoner’s dilemma; and G is a subgraph of grid. We prove that basic computational problems for spatial games with prisoner’s dilemma on a subgraph of a grid are PSPACE-hard."}],"publication_status":"published","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2022-12-14T00:00:00Z","department":[{"_id":"KrCh"}],"quality_controlled":"1","volume":250,"project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}]},{"type":"conference","status":"public","author":[{"full_name":"Ahmadi, Ali","first_name":"Ali","last_name":"Ahmadi"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"first_name":"Amir Kafshdar","full_name":"Goharshady, Amir Kafshdar","orcid":"0000-0003-1702-6584","last_name":"Goharshady","id":"391365CE-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","last_name":"Meggendorfer","first_name":"Tobias","full_name":"Meggendorfer, Tobias"},{"last_name":"Safavi Hemami","id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","full_name":"Safavi Hemami, Roodabeh","first_name":"Roodabeh"},{"id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","last_name":"Zikelic","orcid":"0000-0002-4681-1699","full_name":"Zikelic, Dorde","first_name":"Dorde"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772617"]},"month":"12","conference":{"start_date":"2022-12-18","name":"FSTTC: Foundations of Software Technology and Theoretical Computer Science","end_date":"2022-12-20","location":"Madras, India"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"access_level":"open_access","file_size":872534,"relation":"main_file","content_type":"application/pdf","creator":"dernst","date_created":"2023-01-20T10:39:44Z","date_updated":"2023-01-20T10:39:44Z","success":1,"file_name":"2022_LIPICs_Ahmadi.pdf","file_id":"12324","checksum":"6660c802489013f034c9e8bd57f4d46e"}],"oa_version":"Published Version","day":"14","language":[{"iso":"eng"}],"publication":"42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","article_processing_charge":"No","oa":1,"date_updated":"2025-07-14T09:09:55Z","title":"Algorithms and hardness results for computing cores of Markov chains","scopus_import":"1","intvolume":"       250","has_accepted_license":"1","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"},{"name":"International IST Doctoral Program","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385"}],"date_published":"2022-12-14T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":250,"quality_controlled":"1","department":[{"_id":"KrCh"},{"_id":"GradSch"}],"publication_status":"published","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["000"],"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"}],"_id":"12102","file_date_updated":"2023-01-20T10:39:44Z","doi":"10.4230/LIPIcs.FSTTCS.2022.29","year":"2022","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_created":"2023-01-01T23:00:50Z","citation":{"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>","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.","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>","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. FSTTC: Foundations of Software Technology and Theoretical Computer Science vol. 250, 29.","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>.","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","ec_funded":1},{"publication_status":"published","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["004","516"],"abstract":[{"text":"Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functionsthat facilitates the efficient search for new materials and material properties. We prove invarianceunder isometries, continuity, and completeness in the generic case, which are necessary featuresfor the reliable comparison of crystals. The proof of continuity integrates methods from discretegeometry and lattice theory, while the proof of generic completeness combines techniques fromgeometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and relatedinclusion-exclusion formulae. We have implemented the algorithm and describe its application tocrystal structure prediction.","lang":"eng"}],"project":[{"call_identifier":"H2020","name":"Alpha Shape Theory Extended","grant_number":"788183","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"name":"Discretization in Geometry and Dynamics","_id":"0aa4bc98-070f-11eb-9043-e6fff9c6a316","grant_number":"I4887"},{"name":"The Wittgenstein Prize","call_identifier":"FWF","grant_number":"Z00312","_id":"25C5A090-B435-11E9-9278-68D0E5697425"},{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"}],"date_published":"2021-06-02T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","volume":189,"department":[{"_id":"HeEd"}],"page":"32:1-32:16","year":"2021","acknowledgement":"The authors thank Janos Pach for insightful discussions on the topic of thispaper, Morteza Saghafian for finding the one-dimensional counterexample mentioned in Section 5,and Larry Andrews for generously sharing his crystallographic perspective.","date_created":"2021-04-22T08:09:58Z","citation":{"apa":"Edelsbrunner, H., Heiss, T.,  Kurlin , V., Smith, P., &#38; Wintraecken, M. (2021). The density fingerprint of a periodic point set. In <i>37th International Symposium on Computational Geometry (SoCG 2021)</i> (Vol. 189, p. 32:1-32:16). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.32\">https://doi.org/10.4230/LIPIcs.SoCG.2021.32</a>","short":"H. Edelsbrunner, T. Heiss, V.  Kurlin , P. Smith, M. Wintraecken, in:, 37th International Symposium on Computational Geometry (SoCG 2021), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 32:1-32:16.","ama":"Edelsbrunner H, Heiss T,  Kurlin  V, Smith P, Wintraecken M. The density fingerprint of a periodic point set. In: <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>. Vol 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021:32:1-32:16. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.32\">10.4230/LIPIcs.SoCG.2021.32</a>","ieee":"H. Edelsbrunner, T. Heiss, V.  Kurlin , P. Smith, and M. Wintraecken, “The density fingerprint of a periodic point set,” in <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>, Virtual, 2021, vol. 189, p. 32:1-32:16.","mla":"Edelsbrunner, Herbert, et al. “The Density Fingerprint of a Periodic Point Set.” <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>, vol. 189, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 32:1-32:16, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.32\">10.4230/LIPIcs.SoCG.2021.32</a>.","chicago":"Edelsbrunner, Herbert, Teresa Heiss, Vitaliy  Kurlin , Philip Smith, and Mathijs Wintraecken. “The Density Fingerprint of a Periodic Point Set.” In <i>37th International Symposium on Computational Geometry (SoCG 2021)</i>, 189:32:1-32:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.32\">https://doi.org/10.4230/LIPIcs.SoCG.2021.32</a>.","ista":"Edelsbrunner H, Heiss T,  Kurlin  V, Smith P, Wintraecken M. 2021. The density fingerprint of a periodic point set. 37th International Symposium on Computational Geometry (SoCG 2021). SoCG: Symposium on Computational Geometry, LIPIcs, vol. 189, 32:1-32:16."},"ec_funded":1,"_id":"9345","file_date_updated":"2021-04-22T08:08:14Z","doi":"10.4230/LIPIcs.SoCG.2021.32","author":[{"last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"orcid":"0000-0002-1780-2689","last_name":"Heiss","id":"4879BB4E-F248-11E8-B48F-1D18A9856A87","full_name":"Heiss, Teresa","first_name":"Teresa"},{"last_name":" Kurlin ","full_name":" Kurlin , Vitaliy","first_name":"Vitaliy"},{"last_name":"Smith","full_name":"Smith, Philip","first_name":"Philip"},{"last_name":"Wintraecken","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","first_name":"Mathijs","full_name":"Wintraecken, Mathijs"}],"month":"06","publication_identifier":{"issn":["1868-8969"]},"conference":{"end_date":"2021-06-11","location":"Virtual","start_date":"2021-06-07","name":"SoCG: Symposium on Computational Geometry"},"file":[{"success":1,"file_name":"df_socg_final_version.pdf","checksum":"1787baef1523d6d93753b90d0c109a6d","file_id":"9346","date_created":"2021-04-22T08:08:14Z","date_updated":"2021-04-22T08:08:14Z","creator":"mwintrae","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_size":3117435}],"user_id":"D865714E-FA4E-11E9-B85B-F5C5E5697425","day":"02","oa_version":"Published Version","status":"public","type":"conference","alternative_title":["LIPIcs"],"article_processing_charge":"No","date_updated":"2023-02-23T13:55:40Z","oa":1,"title":"The density fingerprint of a periodic point set","has_accepted_license":"1","intvolume":"       189","language":[{"iso":"eng"}],"publication":"37th International Symposium on Computational Geometry (SoCG 2021)"},{"file":[{"success":1,"file_name":"2021_CONCUR_Jecker.pdf","checksum":"4722c81be82265cf45e78adf9db91250","file_id":"10064","date_created":"2021-10-01T11:10:53Z","date_updated":"2021-10-01T11:10:53Z","creator":"cchlebak","file_size":1003552,"relation":"main_file","access_level":"open_access","content_type":"application/pdf"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"13","oa_version":"Published Version","month":"08","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-9597-7203-7"]},"conference":{"end_date":"2021-08-27","location":"Paris, France","start_date":"2021-08-23","name":"CONCUR: Conference on Concurrency Theory"},"arxiv":1,"author":[{"first_name":"Ismael R","full_name":"Jecker, Ismael R","id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","last_name":"Jecker"},{"first_name":"Nicolas","full_name":"Mazzocchi, Nicolas","last_name":"Mazzocchi"},{"first_name":"Petra","full_name":"Wolf, Petra","last_name":"Wolf"}],"type":"conference","status":"public","alternative_title":["LIPIcs"],"has_accepted_license":"1","scopus_import":"1","intvolume":"       203","title":"Decomposing permutation automata","article_processing_charge":"No","oa":1,"date_updated":"2022-05-13T08:12:52Z","publication":"32nd International Conference on Concurrency Theory","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"A deterministic finite automaton (DFA) 𝒜 is composite if its language L(𝒜) can be decomposed into an intersection ⋂_{i = 1}^k L(𝒜_i) of languages of smaller DFAs. Otherwise, 𝒜 is prime. This notion of primality was introduced by Kupferman and Mosheiff in 2013, and while they proved that we can decide whether a DFA is composite, the precise complexity of this problem is still open, with a doubly-exponential gap between the upper and lower bounds. In this work, we focus on permutation DFAs, i.e., those for which the transition monoid is a group. We provide an NP algorithm to decide whether a permutation DFA is composite, and show that the difficulty of this problem comes from the number of non-accepting states of the instance: we give a fixed-parameter tractable algorithm with the number of rejecting states as the parameter. Moreover, we investigate the class of commutative permutation DFAs. Their structural properties allow us to decide compositionality in NL, and even in LOGSPACE if the alphabet size is fixed. Despite this low complexity, we show that complex behaviors still arise in this class: we provide a family of composite DFAs each requiring polynomially many factors with respect to its size. We also consider the variant of the problem that asks whether a DFA is k-factor composite, that is, decomposable into k smaller DFAs, for some given integer k ∈ ℕ. We show that, for commutative permutation DFAs, restricting the number of factors makes the decision computationally harder, and yields a problem with tight bounds: it is NP-complete. Finally, we show that in general, this problem is in PSPACE, and it is in LOGSPACE for DFAs with a singleton alphabet."}],"external_id":{"arxiv":["2107.04683"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"ddc":["000"],"publication_status":"published","quality_controlled":"1","volume":203,"department":[{"_id":"KrCh"}],"date_published":"2021-08-13T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"article_number":"18","ec_funded":1,"date_created":"2021-09-27T14:33:14Z","citation":{"apa":"Jecker, I. R., Mazzocchi, N., &#38; Wolf, P. (2021). Decomposing permutation automata. In <i>32nd International Conference on Concurrency Theory</i> (Vol. 203). Paris, France: Schloss Dagstuhl - Leibniz Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2021.18\">https://doi.org/10.4230/LIPIcs.CONCUR.2021.18</a>","chicago":"Jecker, Ismael R, Nicolas Mazzocchi, and Petra Wolf. “Decomposing Permutation Automata.” In <i>32nd International Conference on Concurrency Theory</i>, Vol. 203. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2021.18\">https://doi.org/10.4230/LIPIcs.CONCUR.2021.18</a>.","ista":"Jecker IR, Mazzocchi N, Wolf P. 2021. Decomposing permutation automata. 32nd International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 203, 18.","mla":"Jecker, Ismael R., et al. “Decomposing Permutation Automata.” <i>32nd International Conference on Concurrency Theory</i>, vol. 203, 18, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2021.18\">10.4230/LIPIcs.CONCUR.2021.18</a>.","short":"I.R. Jecker, N. Mazzocchi, P. Wolf, in:, 32nd International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.","ieee":"I. R. Jecker, N. Mazzocchi, and P. Wolf, “Decomposing permutation automata,” in <i>32nd International Conference on Concurrency Theory</i>, Paris, France, 2021, vol. 203.","ama":"Jecker IR, Mazzocchi N, Wolf P. Decomposing permutation automata. In: <i>32nd International Conference on Concurrency Theory</i>. Vol 203. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2021.18\">10.4230/LIPIcs.CONCUR.2021.18</a>"},"year":"2021","acknowledgement":"Ismaël Jecker: Marie Skłodowska-Curie Grant Agreement No. 754411. Nicolas Mazzocchi: BOSCO project PGC2018-102210-B-I00 (MCIU/AEI/FEDER, UE), BLOQUESCM project S2018/TCS-4339, and MINECO grant RYC-2016-20281.\r\nPetra Wolf : DFG project FE 560/9-1.\r\n","doi":"10.4230/LIPIcs.CONCUR.2021.18","_id":"10052","file_date_updated":"2021-10-01T11:10:53Z"},{"day":"02","oa_version":"Published Version","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","file":[{"success":1,"checksum":"5a3fed8dbba8c088cbeac1e24cc10bc5","file_name":"2021_LIPIcs_Chatterjee.pdf","file_id":"10062","date_created":"2021-10-01T08:49:26Z","date_updated":"2021-10-01T08:49:26Z","creator":"cchlebak","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_size":854576}],"conference":{"start_date":"2021-07-12","name":"ICALP: International Colloquium on Automata, Languages, and Programming","end_date":"2021-07-16","location":"Glasgow, Scotland"},"month":"07","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-195-5"]},"author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H"},{"first_name":"Sagar Sudhir","full_name":"Kale, Sagar Sudhir","last_name":"Kale"},{"last_name":"Svozil","full_name":"Svozil, Alexander","first_name":"Alexander"}],"alternative_title":["LIPIcs"],"status":"public","type":"conference","scopus_import":"1","intvolume":"       198","has_accepted_license":"1","title":"Faster algorithms for bounded liveness in graphs and game graphs","oa":1,"date_updated":"2025-07-14T09:10:08Z","article_processing_charge":"No","publication":"48th International Colloquium on Automata, Languages, and Programming","language":[{"iso":"eng"}],"abstract":[{"text":"Graphs and games on graphs are fundamental models for the analysis of reactive systems, in particular, for model-checking and the synthesis of reactive systems. The class of ω-regular languages provides a robust specification formalism for the desired properties of reactive systems. In the classical infinitary formulation of the liveness part of an ω-regular specification, a \"good\" event must happen eventually without any bound between the good events. A stronger notion of liveness is bounded liveness, which requires that good events happen within d transitions. Given a graph or a game graph with n vertices, m edges, and a bounded liveness objective, the previous best-known algorithmic bounds are as follows: (i) O(dm) for graphs, which in the worst-case is O(n³); and (ii) O(n² d²) for games on graphs. Our main contributions improve these long-standing algorithmic bounds. For graphs we present: (i) a randomized algorithm with one-sided error with running time O(n^{2.5} log n) for the bounded liveness objectives; and (ii) a deterministic linear-time algorithm for the complement of bounded liveness objectives. For games on graphs, we present an O(n² d) time algorithm for the bounded liveness objectives.","lang":"eng"}],"ddc":["000"],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"publication_status":"published","department":[{"_id":"KrCh"}],"quality_controlled":"1","volume":198,"publisher":"Schloss Dagstuhl - Leibniz Zentrum für Informatik","date_published":"2021-07-02T00:00:00Z","project":[{"grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"ec_funded":1,"article_number":"124","citation":{"apa":"Chatterjee, K., Henzinger, M. H., Kale, S. S., &#38; Svozil, A. (2021). Faster algorithms for bounded liveness in graphs and game graphs. In <i>48th International Colloquium on Automata, Languages, and Programming</i> (Vol. 198). Glasgow, Scotland: Schloss Dagstuhl - Leibniz Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2021.124\">https://doi.org/10.4230/LIPIcs.ICALP.2021.124</a>","ama":"Chatterjee K, Henzinger MH, Kale SS, Svozil A. Faster algorithms for bounded liveness in graphs and game graphs. In: <i>48th International Colloquium on Automata, Languages, and Programming</i>. Vol 198. Schloss Dagstuhl - Leibniz Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2021.124\">10.4230/LIPIcs.ICALP.2021.124</a>","ieee":"K. Chatterjee, M. H. Henzinger, S. S. Kale, and A. Svozil, “Faster algorithms for bounded liveness in graphs and game graphs,” in <i>48th International Colloquium on Automata, Languages, and Programming</i>, Glasgow, Scotland, 2021, vol. 198.","short":"K. Chatterjee, M.H. Henzinger, S.S. Kale, A. Svozil, in:, 48th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021.","ista":"Chatterjee K, Henzinger MH, Kale SS, Svozil A. 2021. Faster algorithms for bounded liveness in graphs and game graphs. 48th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 198, 124.","chicago":"Chatterjee, Krishnendu, Monika H Henzinger, Sagar Sudhir Kale, and Alexander Svozil. “Faster Algorithms for Bounded Liveness in Graphs and Game Graphs.” In <i>48th International Colloquium on Automata, Languages, and Programming</i>, Vol. 198. Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2021.124\">https://doi.org/10.4230/LIPIcs.ICALP.2021.124</a>.","mla":"Chatterjee, Krishnendu, et al. “Faster Algorithms for Bounded Liveness in Graphs and Game Graphs.” <i>48th International Colloquium on Automata, Languages, and Programming</i>, vol. 198, 124, Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2021.124\">10.4230/LIPIcs.ICALP.2021.124</a>."},"date_created":"2021-09-27T14:33:15Z","acknowledgement":"Krishnendu Chatterjee: Supported by the ERC CoG 863818 (ForM-SMArt). Monika Henzinger: Supported by the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N. Sagar Sudhir Kale: Partially supported by the Vienna Science and Technology Fund (WWTF) through project ICT15-003. Alexander Svozil: Fully supported by the Vienna Science and Technology Fund (WWTF) through project ICT15-003.","year":"2021","doi":"10.4230/LIPIcs.ICALP.2021.124","file_date_updated":"2021-10-01T08:49:26Z","_id":"10054"}]