[{"file":[{"checksum":"cc6bb89be0eaa404a6ce019392cd293e","relation":"main_file","creator":"dernst","access_level":"open_access","file_size":1391381,"date_updated":"2024-07-29T11:15:59Z","file_id":"17341","content_type":"application/pdf","file_name":"2024_LIPICs_Cano.pdf","success":1,"date_created":"2024-07-29T11:15:59Z"}],"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2024","day":"01","publication_status":"published","type":"conference","department":[{"_id":"ToHe"}],"isi":1,"month":"07","date_updated":"2025-12-02T13:43:50Z","language":[{"iso":"eng"}],"oa":1,"license":"https://creativecommons.org/licenses/by/4.0/","acknowledgement":"This work is partly supported by the European Research Council under Grant No.: ERC2020-AdG 101020093. It is also partially supported by the State Government of Styria, Austria –\r\nDepartment Zukunftsfonds Steiermark.","alternative_title":["LIPIcs"],"ddc":["000"],"date_created":"2024-07-28T22:01:09Z","publication":"9th International Conference on Formal Structures for Computation and Deduction","status":"public","article_number":"2","oa_version":"Published Version","intvolume":"       299","file_date_updated":"2024-07-29T11:15:59Z","project":[{"call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093","name":"Vigilant Algorithmic Monitoring of Software"}],"_id":"17327","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773232"]},"date_published":"2024-07-01T00:00:00Z","citation":{"ista":"Cano F, Henzinger TA, Könighofer B, Kueffner K, Mallik K. 2024. Abstraction-based decision making for statistical properties. 9th International Conference on Formal Structures for Computation and Deduction. FSCD: Conference on Formal Structures for Computation and Deduction, LIPIcs, vol. 299, 2.","apa":"Cano, F., Henzinger, T. A., Könighofer, B., Kueffner, K., &#38; Mallik, K. (2024). Abstraction-based decision making for statistical properties. In <i>9th International Conference on Formal Structures for Computation and Deduction</i> (Vol. 299). Tallinn, Estonia: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FSCD.2024.2\">https://doi.org/10.4230/LIPIcs.FSCD.2024.2</a>","ama":"Cano F, Henzinger TA, Könighofer B, Kueffner K, Mallik K. Abstraction-based decision making for statistical properties. In: <i>9th International Conference on Formal Structures for Computation and Deduction</i>. Vol 299. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSCD.2024.2\">10.4230/LIPIcs.FSCD.2024.2</a>","ieee":"F. Cano, T. A. Henzinger, B. Könighofer, K. Kueffner, and K. Mallik, “Abstraction-based decision making for statistical properties,” in <i>9th International Conference on Formal Structures for Computation and Deduction</i>, Tallinn, Estonia, 2024, vol. 299.","chicago":"Cano, Filip, Thomas A Henzinger, Bettina Könighofer, Konstantin Kueffner, and Kaushik Mallik. “Abstraction-Based Decision Making for Statistical Properties.” In <i>9th International Conference on Formal Structures for Computation and Deduction</i>, Vol. 299. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.FSCD.2024.2\">https://doi.org/10.4230/LIPIcs.FSCD.2024.2</a>.","short":"F. Cano, T.A. Henzinger, B. Könighofer, K. Kueffner, K. Mallik, in:, 9th International Conference on Formal Structures for Computation and Deduction, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","mla":"Cano, Filip, et al. “Abstraction-Based Decision Making for Statistical Properties.” <i>9th International Conference on Formal Structures for Computation and Deduction</i>, vol. 299, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSCD.2024.2\">10.4230/LIPIcs.FSCD.2024.2</a>."},"article_processing_charge":"Yes","volume":299,"external_id":{"isi":["001587746100002"]},"quality_controlled":"1","corr_author":"1","scopus_import":"1","conference":{"location":"Tallinn, Estonia","name":"FSCD: Conference on Formal Structures for Computation and Deduction","start_date":"2024-07-10","end_date":"2024-07-13"},"title":"Abstraction-based decision making for statistical properties","abstract":[{"lang":"eng","text":"Sequential decision-making in probabilistic environments is a fundamental problem with many applications in AI and economics. In this paper, we present an algorithm for synthesizing sequential decision-making agents that optimize statistical properties such as maximum and average response times. In the general setting of sequential decision-making, the environment is modeled as a random process that generates inputs. The agent responds to each input, aiming to maximize rewards and minimize costs within a specified time horizon. The corresponding synthesis problem is known to be PSPACE-hard. We consider the special case where the input distribution, reward, and cost depend on input-output statistics specified by counter automata. For such problems, this paper presents the first PTIME synthesis algorithms. We introduce the notion of statistical abstraction, which clusters statistically indistinguishable input-output sequences into equivalence classes. This abstraction allows for a dynamic programming algorithm whose complexity grows polynomially with the considered horizon, making the statistical case exponentially more efficient than the general case. We evaluate our algorithm on three different application scenarios of a client-server protocol, where multiple clients compete via bidding to gain access to the service offered by the server. The synthesized policies optimize profit while guaranteeing that none of the server’s clients is disproportionately starved of the service."}],"ec_funded":1,"doi":"10.4230/LIPIcs.FSCD.2024.2","author":[{"first_name":"Filip","full_name":"Cano, Filip","last_name":"Cano"},{"last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724","first_name":"Thomas A"},{"last_name":"Könighofer","full_name":"Könighofer, Bettina","first_name":"Bettina"},{"first_name":"Konstantin","orcid":"0000-0001-8974-2542","last_name":"Kueffner","id":"8121a2d0-dc85-11ea-9058-af578f3b4515","full_name":"Kueffner, Konstantin"},{"full_name":"Mallik, Kaushik","id":"0834ff3c-6d72-11ec-94e0-b5b0a4fb8598","last_name":"Mallik","first_name":"Kaushik","orcid":"0000-0001-9864-7475"}],"has_accepted_license":"1"},{"article_number":"8","date_created":"2024-09-15T22:01:39Z","publication":"35th International Conference on Concurrency Theory","status":"public","alternative_title":["LIPIcs"],"ddc":["000"],"arxiv":1,"oa":1,"language":[{"iso":"eng"}],"date_updated":"2025-12-02T13:46:11Z","month":"09","acknowledgement":"This work was supported in part by the ERC projects ERC-2020-AdG 101020093 and CoG 863818 (ForM-SMArt) and by ISF grant no. 1679/21.","department":[{"_id":"ToHe"}],"isi":1,"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"year":"2024","day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","type":"conference","file":[{"date_created":"2024-09-17T09:35:03Z","content_type":"application/pdf","file_id":"18083","success":1,"file_name":"2024_LIPICS_Avni.pdf","file_size":854430,"date_updated":"2024-09-17T09:35:03Z","access_level":"open_access","checksum":"cb6f2254b84922cd7bf224f550b73f4a","creator":"dernst","relation":"main_file"}],"doi":"10.4230/LIPIcs.CONCUR.2024.8","has_accepted_license":"1","author":[{"last_name":"Avni","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","full_name":"Avni, Guy","orcid":"0000-0001-5588-8287","first_name":"Guy"},{"last_name":"Goharshady","full_name":"Goharshady, Ehsan Kafshdar","first_name":"Ehsan Kafshdar"},{"full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2985-7724","first_name":"Thomas A"},{"full_name":"Mallik, Kaushik","id":"0834ff3c-6d72-11ec-94e0-b5b0a4fb8598","last_name":"Mallik","orcid":"0000-0001-9864-7475","first_name":"Kaushik"}],"conference":{"start_date":"2024-09-09","name":"CONCUR: Conference on Concurrency Theory","location":"Calgary, Canada","end_date":"2024-09-13"},"abstract":[{"text":"Graph games lie at the algorithmic core of many automated design problems in computer science. These are games usually played between two players on a given graph, where the players keep moving a token along the edges according to pre-determined rules (turn-based, concurrent, etc.), and the winner is decided based on the infinite path (aka play) traversed by the token from a given initial position. In bidding games, the players initially get some monetary budgets which they need to use to bid for the privilege of moving the token at each step. Each round of bidding affects the players' available budgets, which is the only form of update that the budgets experience. We introduce bidding games with charging where the players can additionally improve their budgets during the game by collecting vertex-dependent monetary rewards, aka the \"charges.\" Unlike traditional bidding games (where all charges are zero), bidding games with charging allow non-trivial recurrent behaviors. For example, a reachability objective may require multiple detours to vertices with high charges to earn additional budget. We show that, nonetheless, the central property of traditional bidding games generalizes to bidding games with charging: For each vertex there exists a threshold ratio, which is the necessary and sufficient fraction of the total budget for winning the game from that vertex. While the thresholds of traditional bidding games correspond to unique fixed points of linear systems of equations, in games with charging, these fixed points are no longer unique. This significantly complicates the proof of existence and the algorithmic computation of thresholds for infinite-duration objectives. We also provide the lower complexity bounds for computing thresholds for Rabin and Streett objectives, which are the first known lower bounds in any form of bidding games (with or without charging), and we solve the following repair problem for safety and reachability games that have unsatisfiable objectives: Can we distribute a given amount of charge to the players in a way such that the objective can be satisfied?","lang":"eng"}],"title":"Bidding games with charging","ec_funded":1,"scopus_import":"1","quality_controlled":"1","corr_author":"1","external_id":{"arxiv":["2407.06288"],"isi":["001556847400008"]},"article_processing_charge":"Yes","volume":311,"_id":"18066","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2024-09-01T00:00:00Z","citation":{"mla":"Avni, Guy, et al. “Bidding Games with Charging.” <i>35th International Conference on Concurrency Theory</i>, vol. 311, 8, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2024.8\">10.4230/LIPIcs.CONCUR.2024.8</a>.","short":"G. Avni, E.K. Goharshady, T.A. Henzinger, K. Mallik, in:, 35th International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"Avni, Guy, Ehsan Kafshdar Goharshady, Thomas A Henzinger, and Kaushik Mallik. “Bidding Games with Charging.” In <i>35th International Conference on Concurrency Theory</i>, Vol. 311. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2024.8\">https://doi.org/10.4230/LIPIcs.CONCUR.2024.8</a>.","ieee":"G. Avni, E. K. Goharshady, T. A. Henzinger, and K. Mallik, “Bidding games with charging,” in <i>35th International Conference on Concurrency Theory</i>, Calgary, Canada, 2024, vol. 311.","ista":"Avni G, Goharshady EK, Henzinger TA, Mallik K. 2024. Bidding games with charging. 35th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 311, 8.","ama":"Avni G, Goharshady EK, Henzinger TA, Mallik K. Bidding games with charging. In: <i>35th International Conference on Concurrency Theory</i>. Vol 311. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2024.8\">10.4230/LIPIcs.CONCUR.2024.8</a>","apa":"Avni, G., Goharshady, E. K., Henzinger, T. A., &#38; Mallik, K. (2024). Bidding games with charging. In <i>35th International Conference on Concurrency Theory</i> (Vol. 311). Calgary, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2024.8\">https://doi.org/10.4230/LIPIcs.CONCUR.2024.8</a>"},"publication_identifier":{"isbn":["9783959773393"],"issn":["1868-8969"]},"project":[{"_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software","grant_number":"101020093","call_identifier":"H2020"},{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"oa_version":"Published Version","intvolume":"       311","file_date_updated":"2024-09-17T09:35:03Z"},{"isi":1,"department":[{"_id":"ToHe"}],"acknowledgement":"Udi Boker: Israel Science Foundation grant 2410/22\r\nThomas A. Henzinger: ERC-2020-AdG 101020093 (VAMOS)\r\nKaroliina Lehtinen: ANR QUASY 23-CE48-0008-01\r\nAditya Prakash: Chancellors’ International Scholarship from the University of Warwick and Centre for Discrete Mathematics and Its Applications (DIMAP)","month":"09","date_updated":"2025-12-02T13:44:54Z","language":[{"iso":"eng"}],"oa":1,"file":[{"file_size":766902,"date_updated":"2024-09-17T07:31:18Z","access_level":"open_access","relation":"main_file","creator":"dernst","checksum":"66db11ef8e600a434079c278050c3f09","date_created":"2024-09-17T07:31:18Z","file_name":"2024_LIPICS_Boker.pdf","success":1,"file_id":"18080","content_type":"application/pdf"}],"publication_status":"published","type":"conference","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"day":"01","year":"2024","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_number":"12","ddc":["000"],"arxiv":1,"alternative_title":["LIPIcs"],"publication":"35th International Conference on Concurrency Theory","status":"public","date_created":"2024-09-15T22:01:40Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773393"]},"citation":{"ieee":"U. Boker, T. A. Henzinger, K. Lehtinen, and A. Prakash, “History-determinism vs fair simulation,” in <i>35th International Conference on Concurrency Theory</i>, Calgary, Canada, 2024, vol. 311.","chicago":"Boker, Udi, Thomas A Henzinger, Karoliina Lehtinen, and Aditya Prakash. “History-Determinism vs Fair Simulation.” In <i>35th International Conference on Concurrency Theory</i>, Vol. 311. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2024.12\">https://doi.org/10.4230/LIPIcs.CONCUR.2024.12</a>.","short":"U. Boker, T.A. Henzinger, K. Lehtinen, A. Prakash, in:, 35th International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","mla":"Boker, Udi, et al. “History-Determinism vs Fair Simulation.” <i>35th International Conference on Concurrency Theory</i>, vol. 311, 12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2024.12\">10.4230/LIPIcs.CONCUR.2024.12</a>.","ista":"Boker U, Henzinger TA, Lehtinen K, Prakash A. 2024. History-determinism vs fair simulation. 35th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 311, 12.","apa":"Boker, U., Henzinger, T. A., Lehtinen, K., &#38; Prakash, A. (2024). History-determinism vs fair simulation. In <i>35th International Conference on Concurrency Theory</i> (Vol. 311). Calgary, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2024.12\">https://doi.org/10.4230/LIPIcs.CONCUR.2024.12</a>","ama":"Boker U, Henzinger TA, Lehtinen K, Prakash A. History-determinism vs fair simulation. In: <i>35th International Conference on Concurrency Theory</i>. Vol 311. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2024.12\">10.4230/LIPIcs.CONCUR.2024.12</a>"},"date_published":"2024-09-01T00:00:00Z","_id":"18067","volume":311,"article_processing_charge":"No","intvolume":"       311","oa_version":"Published Version","file_date_updated":"2024-09-17T07:31:18Z","project":[{"call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093","name":"Vigilant Algorithmic Monitoring of Software"}],"title":"History-determinism vs fair simulation","abstract":[{"text":"An automaton 𝒜 is history-deterministic if its nondeterminism can be resolved on the fly, only using the prefix of the word read so far. This mild form of nondeterminism has attracted particular attention for its applications in synthesis problems. An automaton 𝒜 is guidable with respect to a class C of automata if it can fairly simulate every automaton in C, whose language is contained in that of 𝒜. In other words, guidable automata are those for which inclusion and simulation coincide, making them particularly interesting for model-checking. We study the connection between these two notions, and specifically the question of when they coincide. For classes of automata on which they do, deciding guidability, an otherwise challenging decision problem, reduces to deciding history-determinism, a problem that is starting to be well-understood for many classes. We provide a selection of sufficient criteria for a class of automata to guarantee the coincidence of the notions, and use them to show that the notions coincide for the most common automata classes, among which are ω-regular automata and many infinite-state automata with safety and reachability acceptance conditions, including vector addition systems with states, one-counter nets, pushdown-, Parikh-, and timed-automata. We also demonstrate that history-determinism and guidability do not always coincide, for example, for the classes of timed automata with a fixed number of clocks.","lang":"eng"}],"ec_funded":1,"conference":{"start_date":"2024-09-09","name":"CONCUR: Conference on Concurrency Theory","location":"Calgary, Canada","end_date":"2024-09-13"},"author":[{"first_name":"Udi","full_name":"Boker, Udi","last_name":"Boker","id":"31E297B6-F248-11E8-B48F-1D18A9856A87"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724","first_name":"Thomas A"},{"last_name":"Lehtinen","full_name":"Lehtinen, Karoliina","first_name":"Karoliina"},{"full_name":"Prakash, Aditya","last_name":"Prakash","first_name":"Aditya"}],"has_accepted_license":"1","doi":"10.4230/LIPIcs.CONCUR.2024.12","external_id":{"isi":["001556847400012"],"arxiv":["2407.08620"]},"quality_controlled":"1","corr_author":"1","scopus_import":"1"},{"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","year":"2024","publication_status":"published","type":"conference","file":[{"file_name":"2024_LIPICS_Henzinger.pdf","success":1,"file_id":"18081","content_type":"application/pdf","date_created":"2024-09-17T07:48:56Z","relation":"main_file","creator":"dernst","checksum":"555bd343e1fb38adeab8fc465ff4fad8","file_size":964124,"date_updated":"2024-09-17T07:48:56Z","access_level":"open_access"}],"OA_place":"publisher","language":[{"iso":"eng"}],"date_updated":"2025-12-02T13:45:38Z","oa":1,"month":"09","acknowledgement":"This work was supported in part by the ERC-2020-AdG 101020093. N. Mazzocchi was affiliated with ISTA when this work was submitted for publication.","department":[{"_id":"ToHe"},{"_id":"GradSch"}],"isi":1,"OA_type":"gold","date_created":"2024-09-15T22:01:40Z","publication":"35th International Conference on Concurrency Theory","status":"public","alternative_title":["LIPIcs"],"ddc":["000"],"arxiv":1,"article_number":"29","project":[{"call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software","grant_number":"101020093"}],"intvolume":"       311","oa_version":"Published Version","file_date_updated":"2024-09-17T07:48:56Z","article_processing_charge":"Yes","volume":311,"_id":"18068","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"mla":"Henzinger, Thomas A., et al. “Strategic Dominance: A New Preorder for Nondeterministic Processes.” <i>35th International Conference on Concurrency Theory</i>, vol. 311, 29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2024.29\">10.4230/LIPIcs.CONCUR.2024.29</a>.","short":"T.A. Henzinger, N.A. Mazzocchi, N.E. Sarac, in:, 35th International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"Henzinger, Thomas A, Nicolas Adrien Mazzocchi, and Naci E Sarac. “Strategic Dominance: A New Preorder for Nondeterministic Processes.” In <i>35th International Conference on Concurrency Theory</i>, Vol. 311. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2024.29\">https://doi.org/10.4230/LIPIcs.CONCUR.2024.29</a>.","ieee":"T. A. Henzinger, N. A. Mazzocchi, and N. E. Sarac, “Strategic dominance: A new preorder for nondeterministic processes,” in <i>35th International Conference on Concurrency Theory</i>, Calgary, Canada, 2024, vol. 311.","ista":"Henzinger TA, Mazzocchi NA, Sarac NE. 2024. Strategic dominance: A new preorder for nondeterministic processes. 35th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 311, 29.","ama":"Henzinger TA, Mazzocchi NA, Sarac NE. Strategic dominance: A new preorder for nondeterministic processes. In: <i>35th International Conference on Concurrency Theory</i>. Vol 311. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2024.29\">10.4230/LIPIcs.CONCUR.2024.29</a>","apa":"Henzinger, T. A., Mazzocchi, N. A., &#38; Sarac, N. E. (2024). Strategic dominance: A new preorder for nondeterministic processes. In <i>35th International Conference on Concurrency Theory</i> (Vol. 311). Calgary, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2024.29\">https://doi.org/10.4230/LIPIcs.CONCUR.2024.29</a>"},"date_published":"2024-09-01T00:00:00Z","publication_identifier":{"isbn":["9783959773393"],"issn":["1868-8969"]},"scopus_import":"1","quality_controlled":"1","corr_author":"1","external_id":{"arxiv":["2407.10473"],"isi":["001556847400029"]},"doi":"10.4230/LIPIcs.CONCUR.2024.29","has_accepted_license":"1","author":[{"orcid":"0000-0002-2985-7724","first_name":"Thomas A","full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Nicolas Adrien","last_name":"Mazzocchi","id":"b26baa86-3308-11ec-87b0-8990f34baa85","full_name":"Mazzocchi, Nicolas Adrien"},{"first_name":"Naci E","full_name":"Sarac, Naci E","id":"8C6B42F8-C8E6-11E9-A03A-F2DCE5697425","last_name":"Sarac"}],"conference":{"start_date":"2024-09-09","name":"CONCUR: Conference on Concurrency Theory","location":"Calgary, Canada","end_date":"2024-09-13"},"abstract":[{"text":"We study the following refinement relation between nondeterministic state-transition models: model ℬ strategically dominates model 𝒜 iff every deterministic refinement of 𝒜 is language contained in some deterministic refinement of ℬ. While language containment is trace inclusion, and the (fair) simulation preorder coincides with tree inclusion, strategic dominance falls strictly between the two and can be characterized as \"strategy inclusion\" between 𝒜 and ℬ: every strategy that resolves the nondeterminism of 𝒜 is dominated by a strategy that resolves the nondeterminism of ℬ. Strategic dominance can be checked in 2-ExpTime by a decidable first-order Presburger logic with quantification over words and strategies, called resolver logic. We give several other applications of resolver logic, including checking the co-safety, co-liveness, and history-determinism of boolean and quantitative automata, and checking the inclusion between hyperproperties that are specified by nondeterministic boolean and quantitative automata.","lang":"eng"}],"title":"Strategic dominance: A new preorder for nondeterministic processes","ec_funded":1},{"article_number":"40","date_created":"2024-09-29T22:01:38Z","publication":"International Conference on Approximation Algorithms for Combinatorial Optimization Problems ","status":"public","alternative_title":["LIPIcs"],"ddc":["000"],"arxiv":1,"oa":1,"language":[{"iso":"eng"}],"date_updated":"2025-12-02T13:47:16Z","month":"09","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 (MoDynStruct,No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nTeresa Anna Steiner: Supported by a research grant (VIL51463) from VILLUM FONDEN.","department":[{"_id":"MoHe"}],"isi":1,"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"year":"2024","day":"16","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","type":"conference","file":[{"checksum":"c08b41c896e4d8c69570044808b40e0b","relation":"main_file","creator":"dernst","date_updated":"2024-10-01T10:07:14Z","file_size":973917,"access_level":"open_access","file_id":"18166","content_type":"application/pdf","file_name":"2024_LIPICs_HenzingerM.pdf","success":1,"date_created":"2024-10-01T10:07:14Z"}],"doi":"10.4230/LIPIcs.APPROX/RANDOM.2024.40","has_accepted_license":"1","author":[{"orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"A. R.","last_name":"Sricharan","full_name":"Sricharan, A. R."},{"full_name":"Steiner, Teresa Anna","last_name":"Steiner","first_name":"Teresa Anna"}],"conference":{"end_date":"2024-08-30","name":"APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems","start_date":"2024-08-27","location":"London, United Kingdom"},"title":"Private counting of distinct elements in the turnstile model and extensions","abstract":[{"lang":"eng","text":"Privately counting distinct elements in a stream is a fundamental data analysis problem with many applications in machine learning. In the turnstile model, Jain et al. [NeurIPS2023] initiated the study of this problem parameterized by the maximum flippancy of any element, i.e., the number of times that the count of an element changes from 0 to above 0 or vice versa. They give an item-level (ε,δ)-differentially private algorithm whose additive error is tight with respect to that parameterization. In this work, we show that a very simple algorithm based on the sparse vector technique achieves a tight additive error for item-level (ε,δ)-differential privacy and item-level ε-differential privacy with regards to a different parameterization, namely the sum of all flippancies. Our second result is a bound which shows that for a large class of algorithms, including all existing differentially private algorithms for this problem, the lower bound from item-level differential privacy extends to event-level differential privacy. This partially answers an open question by Jain et al. [NeurIPS2023]."}],"ec_funded":1,"scopus_import":"1","quality_controlled":"1","corr_author":"1","external_id":{"isi":["001545634500040"],"arxiv":["2408.11637"]},"article_processing_charge":"No","volume":317,"_id":"18156","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_identifier":{"isbn":["9783959773485"],"issn":["1868-8969"]},"date_published":"2024-09-16T00:00:00Z","citation":{"ista":"Henzinger M, Sricharan AR, Steiner TA. 2024. Private counting of distinct elements in the turnstile model and extensions. International Conference on Approximation Algorithms for Combinatorial Optimization Problems . APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems, LIPIcs, vol. 317, 40.","ama":"Henzinger M, Sricharan AR, Steiner TA. Private counting of distinct elements in the turnstile model and extensions. In: <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i>. Vol 317. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40\">10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>","apa":"Henzinger, M., Sricharan, A. R., &#38; Steiner, T. A. (2024). Private counting of distinct elements in the turnstile model and extensions. In <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i> (Vol. 317). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40\">https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>","mla":"Henzinger, Monika, et al. “Private Counting of Distinct Elements in the Turnstile Model and Extensions.” <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i>, vol. 317, 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40\">10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>.","ieee":"M. Henzinger, A. R. Sricharan, and T. A. Steiner, “Private counting of distinct elements in the turnstile model and extensions,” in <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i>, London, United Kingdom, 2024, vol. 317.","chicago":"Henzinger, Monika, A. R. Sricharan, and Teresa Anna Steiner. “Private Counting of Distinct Elements in the Turnstile Model and Extensions.” In <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i>, Vol. 317. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40\">https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>.","short":"M. Henzinger, A.R. Sricharan, T.A. Steiner, in:, International Conference on Approximation Algorithms for Combinatorial Optimization Problems , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024."},"project":[{"grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms","grant_number":"Z00422"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer"}],"intvolume":"       317","oa_version":"Published Version","file_date_updated":"2024-10-01T10:07:14Z"},{"alternative_title":["LIPIcs"],"ddc":["000"],"status":"public","publication":"38th European Conference on Object-Oriented Programming","date_created":"2024-10-06T22:01:12Z","article_number":"27","file":[{"file_name":"2024_LIPICs_Maj.pdf","success":1,"file_id":"18184","content_type":"application/pdf","date_created":"2024-10-07T11:10:55Z","relation":"main_file","creator":"dernst","checksum":"2e75d305a8c817d76a0c7f136ce34f86","date_updated":"2024-10-07T11:10:55Z","access_level":"open_access","file_size":1764222}],"type":"conference","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","year":"2024","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"isi":1,"department":[{"_id":"ToHe"}],"acknowledgement":"This work was supported by the Czech Ministry of Education, Youth and Sports under\r\nprogram ERC-CZ, grant agreement LL2325, BigCode (reg. no. CZ.02.1.01/0.0/0.0/15_003/0000421). NSF grants CCF-1910850, CNS-1925644, and CCF-2139612, as well as the GACR EXPRO grant 23-07580X. We would like to thank Digital Ocean for their involuntary contribution of computational resources during the early data gathering phase of our research. We acknoweldge the reviewers of ICSE’22, and thank the reviewers of ECOOP’23 for their encouragments and for sticking around until 2024.","oa":1,"month":"09","date_updated":"2025-12-02T13:48:19Z","language":[{"iso":"eng"}],"external_id":{"isi":["001533999700027"]},"scopus_import":"1","quality_controlled":"1","title":"The fault in our stars: Designing reproducible large-scale code analysis experiments","abstract":[{"text":"Large-scale software repositories are a source of insights for software engineering. They offer an unmatched window into the software development process at scale. Their sheer number and size holds the promise of broadly applicable results. At the same time, that very size presents practical challenges for scaling tools and algorithms to millions of projects. A reasonable approach is to limit studies to representative samples of the population of interest. Broadly applicable conclusions can then be obtained by generalizing to the entire population. The contribution of this paper is a standardized experimental design methodology for choosing the inputs of studies working with large-scale repositories. We advocate for a methodology that clearly lays out what the population of interest is, how to sample it, and that fosters reproducibility. Along the way, we discourage researchers from using extrinsic attributes of projects such as stars, that measure some unclear notion of popularity.","lang":"eng"}],"conference":{"end_date":"2024-09-20","location":"Vienna, Austria","name":"ECOOP: European Conference on Object-Oriented Programming","start_date":"2024-09-16"},"has_accepted_license":"1","author":[{"first_name":"Petr","full_name":"Maj, Petr","last_name":"Maj"},{"full_name":"Muroya Lei, Stefanie","id":"a376de31-8972-11ed-ae7b-d0251c13c8ff","last_name":"Muroya Lei","first_name":"Stefanie"},{"first_name":"Konrad","full_name":"Siek, Konrad","last_name":"Siek"},{"first_name":"Luca","full_name":"Di Grazia, Luca","last_name":"Di Grazia"},{"first_name":"Jan","full_name":"Vitek, Jan","last_name":"Vitek"}],"doi":"10.4230/LIPIcs.ECOOP.2024.27","file_date_updated":"2024-10-07T11:10:55Z","intvolume":"       313","oa_version":"Published Version","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773416"]},"date_published":"2024-09-01T00:00:00Z","citation":{"mla":"Maj, Petr, et al. “The Fault in Our Stars: Designing Reproducible Large-Scale Code Analysis Experiments.” <i>38th European Conference on Object-Oriented Programming</i>, vol. 313, 27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ECOOP.2024.27\">10.4230/LIPIcs.ECOOP.2024.27</a>.","ieee":"P. Maj, S. Muroya Lei, K. Siek, L. Di Grazia, and J. Vitek, “The fault in our stars: Designing reproducible large-scale code analysis experiments,” in <i>38th European Conference on Object-Oriented Programming</i>, Vienna, Austria, 2024, vol. 313.","short":"P. Maj, S. Muroya Lei, K. Siek, L. Di Grazia, J. Vitek, in:, 38th European Conference on Object-Oriented Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"Maj, Petr, Stefanie Muroya Lei, Konrad Siek, Luca Di Grazia, and Jan Vitek. “The Fault in Our Stars: Designing Reproducible Large-Scale Code Analysis Experiments.” In <i>38th European Conference on Object-Oriented Programming</i>, Vol. 313. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.ECOOP.2024.27\">https://doi.org/10.4230/LIPIcs.ECOOP.2024.27</a>.","ama":"Maj P, Muroya Lei S, Siek K, Di Grazia L, Vitek J. The fault in our stars: Designing reproducible large-scale code analysis experiments. In: <i>38th European Conference on Object-Oriented Programming</i>. Vol 313. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ECOOP.2024.27\">10.4230/LIPIcs.ECOOP.2024.27</a>","apa":"Maj, P., Muroya Lei, S., Siek, K., Di Grazia, L., &#38; Vitek, J. (2024). The fault in our stars: Designing reproducible large-scale code analysis experiments. In <i>38th European Conference on Object-Oriented Programming</i> (Vol. 313). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ECOOP.2024.27\">https://doi.org/10.4230/LIPIcs.ECOOP.2024.27</a>","ista":"Maj P, Muroya Lei S, Siek K, Di Grazia L, Vitek J. 2024. The fault in our stars: Designing reproducible large-scale code analysis experiments. 38th European Conference on Object-Oriented Programming. ECOOP: European Conference on Object-Oriented Programming, LIPIcs, vol. 313, 27."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"18175","volume":313,"article_processing_charge":"No"},{"volume":308,"article_processing_charge":"Yes","date_published":"2024-09-23T00:00:00Z","citation":{"apa":"La Tour, M. D., Henzinger, M., &#38; Saulpic, D. (2024). Fully dynamic k-means coreset in near-optimal update time. In <i>32nd Annual European Symposium on Algorithms</i> (Vol. 308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.100\">https://doi.org/10.4230/LIPIcs.ESA.2024.100</a>","ama":"La Tour MD, Henzinger M, Saulpic D. Fully dynamic k-means coreset in near-optimal update time. In: <i>32nd Annual European Symposium on Algorithms</i>. Vol 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.100\">10.4230/LIPIcs.ESA.2024.100</a>","ista":"La Tour MD, Henzinger M, Saulpic D. 2024. Fully dynamic k-means coreset in near-optimal update time. 32nd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 308, 100.","ieee":"M. D. La Tour, M. Henzinger, and D. Saulpic, “Fully dynamic k-means coreset in near-optimal update time,” in <i>32nd Annual European Symposium on Algorithms</i>, London, United Kingdom, 2024, vol. 308.","short":"M.D. La Tour, M. Henzinger, D. Saulpic, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"La Tour, Max Dupré, Monika Henzinger, and David Saulpic. “Fully Dynamic K-Means Coreset in near-Optimal Update Time.” In <i>32nd Annual European Symposium on Algorithms</i>, Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.100\">https://doi.org/10.4230/LIPIcs.ESA.2024.100</a>.","mla":"La Tour, Max Dupré, et al. “Fully Dynamic K-Means Coreset in near-Optimal Update Time.” <i>32nd Annual European Symposium on Algorithms</i>, vol. 308, 100, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.100\">10.4230/LIPIcs.ESA.2024.100</a>."},"publication_identifier":{"isbn":["9783959773386"],"issn":["1868-8969"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"18308","project":[{"call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures"},{"grant_number":"Z00422","name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer"},{"call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program"}],"file_date_updated":"2024-10-21T09:41:48Z","intvolume":"       308","oa_version":"Published Version","has_accepted_license":"1","author":[{"last_name":"La Tour","full_name":"La Tour, Max Dupré","first_name":"Max Dupré"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"first_name":"David","last_name":"Saulpic","id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964","full_name":"Saulpic, David"}],"doi":"10.4230/LIPIcs.ESA.2024.100","ec_funded":1,"title":"Fully dynamic k-means coreset in near-optimal update time","abstract":[{"text":"We study in this paper the problem of maintaining a solution to k-median and k-means clustering in a fully dynamic setting. To do so, we present an algorithm to efficiently maintain a coreset, a compressed version of the dataset, that allows easy computation of a clustering solution at query time. Our coreset algorithm has near-optimal update time of Õ(k) in general metric spaces, which reduces to Õ(d) in the Euclidean space ℝ^d. The query time is O(k²) in general metrics, and O(kd) in ℝ^d. To maintain a constant-factor approximation for k-median and k-means clustering in Euclidean space, this directly leads to an algorithm with update time Õ(d), and query time Õ(kd + k²). To maintain a O(polylog k)-approximation, the query time is reduced to Õ(kd).","lang":"eng"}],"conference":{"end_date":"2024-09-04","name":"ESA: European Symposium on Algorithms","start_date":"2024-09-02","location":"London, United Kingdom"},"corr_author":"1","quality_controlled":"1","scopus_import":"1","external_id":{"isi":["001545622400100"],"arxiv":["2406.19926"]},"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 (MoDynStruct Grant agreement No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nDavid Saulpic: Work partially done while at ISTA. Received funding from the European Union’s\r\nHorizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 101034413. This work was partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR).","month":"09","language":[{"iso":"eng"}],"date_updated":"2025-12-02T13:49:11Z","oa":1,"isi":1,"department":[{"_id":"MoHe"}],"type":"conference","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2024","day":"23","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"OA_place":"publisher","file":[{"access_level":"open_access","file_size":873561,"date_updated":"2024-10-21T09:41:48Z","relation":"main_file","creator":"dernst","checksum":"8e8c0b13049f11bb0133dfac22e32718","date_created":"2024-10-21T09:41:48Z","file_name":"2024_LIPICs_DuprelaTour.pdf","success":1,"file_id":"18454","content_type":"application/pdf"}],"article_number":"100","status":"public","publication":"32nd Annual European Symposium on Algorithms","date_created":"2024-10-13T22:01:50Z","OA_type":"gold","arxiv":1,"ddc":["000"],"alternative_title":["LIPIcs"]},{"doi":"10.4230/LIPIcs.ESA.2024.72","has_accepted_license":"1","author":[{"last_name":"Hu","full_name":"Hu, Bingbing","first_name":"Bingbing"},{"full_name":"Kosinas, Evangelos","last_name":"Kosinas","id":"4c7f9625-dbbc-11ee-9d86-bdcc2db5a949","first_name":"Evangelos"},{"full_name":"Polak, Adam","last_name":"Polak","first_name":"Adam"}],"conference":{"end_date":"2024-09-04","name":"ESA: European Symposium on Algorithms","start_date":"2024-09-02","location":"London, United Kingdom"},"abstract":[{"lang":"eng","text":"The problem of designing connectivity oracles supporting vertex failures is one of the basic data structures problems for undirected graphs. It is already well understood: previous works [Duan-Pettie STOC'10; Long-Saranurak FOCS'22] achieve query time linear in the number of failed vertices, and it is conditionally optimal as long as we require preprocessing time polynomial in the size of the graph and update time polynomial in the number of failed vertices. We revisit this problem in the paradigm of algorithms with predictions: we ask if the query time can be improved if the set of failed vertices can be predicted beforehand up to a small number of errors. More specifically, we design a data structure that, given a graph G = (V,E) and a set of vertices predicted to fail D̂ ⊆ V of size d = |D̂|, preprocesses it in time Õ(d|E|) and then can receive an update given as the symmetric difference between the predicted and the actual set of failed vertices D̂△D = (D̂ ⧵ D) ∪ (D ⧵ D̂) of size η = |D̂△D|, process it in time Õ(η⁴), and after that answer connectivity queries in G ⧵ D in time O(η). Viewed from another perspective, our data structure provides an improvement over the state of the art for the fully dynamic subgraph connectivity problem in the sensitivity setting [Henzinger-Neumann ESA'16]. We argue that the preprocessing time and query time of our data structure are conditionally optimal under standard fine-grained complexity assumptions."}],"title":"Connectivity oracles for predictable vertex failures","quality_controlled":"1","corr_author":"1","scopus_import":"1","external_id":{"arxiv":["2312.08489"],"isi":["001545622400072"]},"article_processing_charge":"Yes","volume":308,"_id":"18309","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773386"]},"date_published":"2024-09-01T00:00:00Z","citation":{"ama":"Hu B, Kosinas E, Polak A. Connectivity oracles for predictable vertex failures. In: <i>32nd Annual European Symposium on Algorithms</i>. Vol 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.72\">10.4230/LIPIcs.ESA.2024.72</a>","apa":"Hu, B., Kosinas, E., &#38; Polak, A. (2024). Connectivity oracles for predictable vertex failures. In <i>32nd Annual European Symposium on Algorithms</i> (Vol. 308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.72\">https://doi.org/10.4230/LIPIcs.ESA.2024.72</a>","ista":"Hu B, Kosinas E, Polak A. 2024. Connectivity oracles for predictable vertex failures. 32nd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 308, 72.","mla":"Hu, Bingbing, et al. “Connectivity Oracles for Predictable Vertex Failures.” <i>32nd Annual European Symposium on Algorithms</i>, vol. 308, 72, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.72\">10.4230/LIPIcs.ESA.2024.72</a>.","chicago":"Hu, Bingbing, Evangelos Kosinas, and Adam Polak. “Connectivity Oracles for Predictable Vertex Failures.” In <i>32nd Annual European Symposium on Algorithms</i>, Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.72\">https://doi.org/10.4230/LIPIcs.ESA.2024.72</a>.","ieee":"B. Hu, E. Kosinas, and A. Polak, “Connectivity oracles for predictable vertex failures,” in <i>32nd Annual European Symposium on Algorithms</i>, London, United Kingdom, 2024, vol. 308.","short":"B. Hu, E. Kosinas, A. Polak, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2024-10-21T10:03:48Z","oa_version":"Published Version","intvolume":"       308","article_number":"72","OA_type":"gold","date_created":"2024-10-13T22:01:50Z","status":"public","publication":"32nd Annual European Symposium on Algorithms","ddc":["000"],"alternative_title":["LIPIcs"],"arxiv":1,"language":[{"iso":"eng"}],"date_updated":"2025-12-02T13:49:52Z","oa":1,"month":"09","acknowledgement":"Part of this work was done when Evangelos Kosinas was at University of Ioannina and Adam Polak was at Max Planck Institute of Informatics.\r\n","department":[{"_id":"MoHe"}],"isi":1,"day":"01","year":"2024","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"type":"conference","publication_status":"published","file":[{"checksum":"ab1f2f9161549a8763eda15db40e022c","relation":"main_file","creator":"dernst","access_level":"open_access","file_size":853914,"date_updated":"2024-10-21T10:03:48Z","content_type":"application/pdf","file_id":"18455","file_name":"2024_LIPICs_Hu.pdf","success":1,"date_created":"2024-10-21T10:03:48Z"}],"OA_place":"publisher"},{"arxiv":1,"ddc":["000"],"related_material":{"record":[{"id":"22281","status":"public","relation":"dissertation_contains"}]},"alternative_title":["LIPIcs"],"OA_type":"gold","date_created":"2024-11-17T23:01:47Z","status":"public","publication":"38th International Symposium on Distributed Computing","article_number":"21","file":[{"date_updated":"2024-11-18T08:02:45Z","file_size":809666,"access_level":"open_access","checksum":"d6c8277331cafa188c33ba1717206cf4","relation":"main_file","creator":"dernst","date_created":"2024-11-18T08:02:45Z","content_type":"application/pdf","file_id":"18561","file_name":"2024_LIPIcs_ElHayek.pdf","success":1}],"OA_place":"publisher","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2024","day":"24","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"type":"conference","publication_status":"published","department":[{"_id":"MoHe"}],"isi":1,"language":[{"iso":"eng"}],"oa":1,"month":"10","date_updated":"2026-07-24T12:48:28Z","acknowledgement":"Antoine El-Hayek: This project has received funding from the Austrian Science Fund\r\n(FWF) grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung,\r\n2020–2024.\r\nMonika Henzinger: This project has received funding from the European Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation programme (MoDynStruct,\r\nNo. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI\r\n10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE\r\nStiftung, 2020–2024.\r\nStefan Schmid: This project has received funding from the German Research Foundation (DFG),\r\nSPP 2378 (project ReNO), 2023-2027.","external_id":{"arxiv":["2302.11988"],"isi":["001542467600021"]},"quality_controlled":"1","scopus_import":"1","corr_author":"1","conference":{"location":"Madrid, Spain","start_date":"2024-10-28","name":"DISC: Symposium on Distributed Computing","end_date":"2024-11-01"},"ec_funded":1,"abstract":[{"text":"Broadcast and Consensus are most fundamental tasks in distributed computing. These tasks are particularly challenging in dynamic networks where communication across the network links may be unreliable, e.g., due to mobility or failures. Over the last years, researchers have derived several impossibility results and high time complexity lower bounds for these tasks. Specifically for the setting where in each round of communication the adversary is allowed to choose one rooted tree along which the information is disseminated, there is a lower as well as an upper bound that is linear in the number n of nodes for Broadcast and for n ≥ 3 the adversary can guarantee that Consensus never happens. This setting is called the oblivious message adversary for rooted trees. Also note that if the adversary is allowed to choose a graph that does not contain a rooted tree, then it can guarantee that Broadcast and Consensus will never happen. However, such deterministic adversarial models may be overly pessimistic, as many processes in real-world settings are stochastic in nature rather than worst-case. This paper studies Broadcast on stochastic dynamic networks and shows that the situation is very different to the deterministic case. In particular, we show that if information dissemination occurs along random rooted trees and directed Erdős–Rényi graphs, Broadcast completes in O(log n) rounds of communication with high probability. The fundamental insight in our analysis is that key variables are mutually independent. We then study two adversarial models, (a) one with Byzantine nodes and (b) one where an adversary controls the edges. (a) Our techniques without Byzantine nodes are general enough so that they can be extended to Byzantine nodes. (b) In the spirit of smoothed analysis, we introduce the notion of randomized oblivious message adversary, where in each round, an adversary picks k ≤ 2n/3 edges to appear in the communication network, and then a graph (e.g. rooted tree or directed Erdős–Rényi graph) is chosen uniformly at random among the set of all such graphs that include these edges. We show that Broadcast completes in a finite number of rounds, which is, e.g., O(k+log n) rounds in rooted trees. We then extend these results to All-to-All Broadcast, and Consensus, and give lower bounds that show that most of our upper bounds are tight.","lang":"eng"}],"title":"Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges","doi":"10.4230/LIPIcs.DISC.2024.21","author":[{"first_name":"Antoine","orcid":"0000-0003-4268-7368","id":"888a098e-fcac-11ee-aff7-d347be57b725","last_name":"El-Hayek","full_name":"El-Hayek, Antoine"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"first_name":"Stefan","last_name":"Schmid","full_name":"Schmid, Stefan"}],"has_accepted_license":"1","file_date_updated":"2024-11-18T08:02:45Z","intvolume":"       319","oa_version":"Published Version","project":[{"grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"},{"call_identifier":"H2020","grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422","name":"Efficient algorithms"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"_id":"18557","date_published":"2024-10-24T00:00:00Z","citation":{"mla":"El-Hayek, Antoine, et al. “Broadcast and Consensus in Stochastic Dynamic Networks with Byzantine Nodes and Adversarial Edges.” <i>38th International Symposium on Distributed Computing</i>, vol. 319, 21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2024.21\">10.4230/LIPIcs.DISC.2024.21</a>.","ieee":"A. El-Hayek, M. Henzinger, and S. Schmid, “Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges,” in <i>38th International Symposium on Distributed Computing</i>, Madrid, Spain, 2024, vol. 319.","short":"A. El-Hayek, M. Henzinger, S. Schmid, in:, 38th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Broadcast and Consensus in Stochastic Dynamic Networks with Byzantine Nodes and Adversarial Edges.” In <i>38th International Symposium on Distributed Computing</i>, Vol. 319. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2024.21\">https://doi.org/10.4230/LIPIcs.DISC.2024.21</a>.","ama":"El-Hayek A, Henzinger M, Schmid S. Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. In: <i>38th International Symposium on Distributed Computing</i>. Vol 319. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2024.21\">10.4230/LIPIcs.DISC.2024.21</a>","apa":"El-Hayek, A., Henzinger, M., &#38; Schmid, S. (2024). Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. In <i>38th International Symposium on Distributed Computing</i> (Vol. 319). Madrid, Spain: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2024.21\">https://doi.org/10.4230/LIPIcs.DISC.2024.21</a>","ista":"El-Hayek A, Henzinger M, Schmid S. 2024. Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. 38th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 319, 21."},"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773522"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_processing_charge":"Yes","volume":319},{"project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020"},{"grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"intvolume":"       254","oa_version":"Published Version","file_date_updated":"2023-03-27T06:37:22Z","article_processing_charge":"No","volume":254,"_id":"12760","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772662"]},"date_published":"2023-03-01T00:00:00Z","citation":{"ista":"Henzinger M, Neumann S, Räcke H, Schmid S. 2023. Dynamic maintenance of monotone dynamic programs and applications. 40th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 254, 36.","ama":"Henzinger M, Neumann S, Räcke H, Schmid S. Dynamic maintenance of monotone dynamic programs and applications. In: <i>40th International Symposium on Theoretical Aspects of Computer Science</i>. Vol 254. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2023.36\">10.4230/LIPIcs.STACS.2023.36</a>","apa":"Henzinger, M., Neumann, S., Räcke, H., &#38; Schmid, S. (2023). Dynamic maintenance of monotone dynamic programs and applications. In <i>40th International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 254). Hamburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2023.36\">https://doi.org/10.4230/LIPIcs.STACS.2023.36</a>","mla":"Henzinger, Monika, et al. “Dynamic Maintenance of Monotone Dynamic Programs and Applications.” <i>40th International Symposium on Theoretical Aspects of Computer Science</i>, vol. 254, 36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2023.36\">10.4230/LIPIcs.STACS.2023.36</a>.","chicago":"Henzinger, Monika, Stefan Neumann, Harald Räcke, and Stefan Schmid. “Dynamic Maintenance of Monotone Dynamic Programs and Applications.” In <i>40th International Symposium on Theoretical Aspects of Computer Science</i>, Vol. 254. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2023.36\">https://doi.org/10.4230/LIPIcs.STACS.2023.36</a>.","short":"M. Henzinger, S. Neumann, H. Räcke, S. Schmid, in:, 40th International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","ieee":"M. Henzinger, S. Neumann, H. Räcke, and S. Schmid, “Dynamic maintenance of monotone dynamic programs and applications,” in <i>40th International Symposium on Theoretical Aspects of Computer Science</i>, Hamburg, Germany, 2023, vol. 254."},"corr_author":"1","quality_controlled":"1","scopus_import":"1","external_id":{"arxiv":["2301.01744"],"isi":["001532693100036"]},"doi":"10.4230/LIPIcs.STACS.2023.36","has_accepted_license":"1","author":[{"first_name":"Monika H","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"last_name":"Neumann","full_name":"Neumann, Stefan","first_name":"Stefan"},{"last_name":"Räcke","full_name":"Räcke, Harald","first_name":"Harald"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"}],"conference":{"start_date":"2023-03-07","name":"STACS: Symposium on Theoretical Aspects of Computer Science","location":"Hamburg, Germany","end_date":"2023-03-09"},"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."}],"title":"Dynamic maintenance of monotone dynamic programs and applications","ec_funded":1,"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"day":"01","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","year":"2023","publication_status":"published","type":"conference","file":[{"file_id":"12769","content_type":"application/pdf","success":1,"file_name":"2023_LIPICS_HenzingerM.pdf","date_created":"2023-03-27T06:37:22Z","checksum":"22141ab8bc55188e2dfff665e5daecbd","creator":"dernst","relation":"main_file","access_level":"open_access","file_size":872706,"date_updated":"2023-03-27T06:37:22Z"}],"language":[{"iso":"eng"}],"date_updated":"2025-09-09T12:22:44Z","month":"03","oa":1,"acknowledgement":"Monika Henzinger: This project has received funding from the European Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant\r\nagreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project “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.","department":[{"_id":"MoHe"}],"isi":1,"date_created":"2023-03-26T22:01:07Z","publication":"40th International Symposium on Theoretical Aspects of Computer Science","status":"public","ddc":["000"],"alternative_title":["LIPIcs"],"arxiv":1,"article_number":"36"},{"department":[{"_id":"MaMo"}],"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.","oa":1,"language":[{"iso":"eng"}],"date_updated":"2025-09-08T08:31:53Z","month":"07","file":[{"date_created":"2023-08-21T07:23:18Z","content_type":"application/pdf","file_id":"14091","success":1,"file_name":"2023_LIPIcsICALP_Resch.pdf","access_level":"open_access","date_updated":"2023-08-21T07:23:18Z","file_size":1141497,"checksum":"a449143fec3fbebb092cb8ef3b53c226","creator":"dernst","relation":"main_file"}],"type":"conference","publication_status":"published","year":"2023","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"article_number":"99","related_material":{"record":[{"relation":"later_version","status":"public","id":"17330"}]},"alternative_title":["LIPIcs"],"ddc":["000"],"arxiv":1,"status":"public","publication":"50th International Colloquium on Automata, Languages, and Programming","date_created":"2023-08-20T22:01:13Z","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>","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>","ista":"Resch N, Yuan C, Zhang Y. 2023. Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 99.","short":"N. Resch, C. Yuan, Y. Zhang, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","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>.","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.","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>."},"date_published":"2023-07-01T00:00:00Z","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772785"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"14083","volume":261,"article_processing_charge":"Yes","file_date_updated":"2023-08-21T07:23:18Z","intvolume":"       261","oa_version":"Published Version","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."}],"title":"Zero-rate thresholds and new capacity bounds for list-decoding and list-recovery","conference":{"end_date":"2023-07-14","start_date":"2023-07-10","name":"ICALP: Automata, Languages and Programming","location":"Paderborn, Germany"},"has_accepted_license":"1","author":[{"first_name":"Nicolas","last_name":"Resch","full_name":"Resch, Nicolas"},{"full_name":"Yuan, Chen","last_name":"Yuan","first_name":"Chen"},{"orcid":"0000-0002-6465-6258","first_name":"Yihan","full_name":"Zhang, Yihan","last_name":"Zhang","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c"}],"doi":"10.4230/LIPIcs.ICALP.2023.99","external_id":{"arxiv":["2210.07754"]},"scopus_import":"1","quality_controlled":"1","corr_author":"1"},{"has_accepted_license":"1","author":[{"first_name":"David G.","last_name":"Harris","full_name":"Harris, David G."},{"first_name":"Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir"}],"doi":"10.4230/LIPIcs.ICALP.2023.72","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."}],"title":"Parameter estimation for Gibbs distributions","conference":{"location":"Paderborn, Germany","name":"ICALP: Automata, Languages and Programming","start_date":"2023-07-10","end_date":"2023-07-14"},"scopus_import":"1","corr_author":"1","quality_controlled":"1","external_id":{"arxiv":["2007.10824"]},"volume":261,"article_processing_charge":"Yes","date_published":"2023-07-01T00:00:00Z","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772785"]},"citation":{"chicago":"Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs Distributions.” In <i>50th International Colloquium on Automata, Languages, and Programming</i>, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.72\">https://doi.org/10.4230/LIPIcs.ICALP.2023.72</a>.","short":"D.G. Harris, V. Kolmogorov, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","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.","mla":"Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs Distributions.” <i>50th International Colloquium on Automata, Languages, and Programming</i>, vol. 261, 72, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.72\">10.4230/LIPIcs.ICALP.2023.72</a>.","ista":"Harris DG, Kolmogorov V. 2023. Parameter estimation for Gibbs distributions. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 72.","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>","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>"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"14084","file_date_updated":"2023-08-21T06:45:16Z","oa_version":"Published Version","intvolume":"       261","article_number":"72","status":"public","publication":"50th International Colloquium on Automata, Languages, and Programming","date_created":"2023-08-20T22:01:14Z","related_material":{"record":[{"relation":"later_version","id":"18855","status":"public"}]},"alternative_title":["LIPIcs"],"ddc":["000","510"],"arxiv":1,"acknowledgement":"We thank Heng Guo for helpful explanations of algorithms for sampling connected subgraphs and matchings, Maksym Serbyn for bringing to our attention the Wang-Landau algorithm and its use in physics.","oa":1,"date_updated":"2025-07-10T11:50:45Z","month":"07","language":[{"iso":"eng"}],"department":[{"_id":"VlKo"}],"type":"conference","publication_status":"published","day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2023","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"file":[{"creator":"dernst","relation":"main_file","checksum":"6dee0684245bb1c524b9c955db1e933d","date_updated":"2023-08-21T06:45:16Z","access_level":"open_access","file_size":917791,"success":1,"file_name":"2023_LIPIcsICALP_Harris.pdf","file_id":"14088","content_type":"application/pdf","date_created":"2023-08-21T06:45:16Z"}]},{"conference":{"end_date":"2023-07-14","name":"ICALP: Automata, Languages and Programming","start_date":"2023-07-10","location":"Paderborn, Germany"},"ec_funded":1,"title":"Efficient data structures for incremental exact and approximate maximum flow","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."}],"doi":"10.4230/LIPIcs.ICALP.2023.69","has_accepted_license":"1","author":[{"last_name":"Goranci","full_name":"Goranci, Gramoz","first_name":"Gramoz"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530"}],"external_id":{"arxiv":["2211.09606"]},"scopus_import":"1","corr_author":"1","quality_controlled":"1","_id":"14085","citation":{"mla":"Goranci, Gramoz, and Monika Henzinger. “Efficient Data Structures for Incremental Exact and Approximate Maximum Flow.” <i>50th International Colloquium on Automata, Languages, and Programming</i>, vol. 261, 69, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.69\">10.4230/LIPIcs.ICALP.2023.69</a>.","ieee":"G. Goranci and M. Henzinger, “Efficient data structures for incremental exact and approximate maximum flow,” in <i>50th International Colloquium on Automata, Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261.","chicago":"Goranci, Gramoz, and Monika Henzinger. “Efficient Data Structures for Incremental Exact and Approximate Maximum Flow.” In <i>50th International Colloquium on Automata, Languages, and Programming</i>, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.69\">https://doi.org/10.4230/LIPIcs.ICALP.2023.69</a>.","short":"G. Goranci, M. Henzinger, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","ama":"Goranci G, Henzinger M. Efficient data structures for incremental exact and approximate maximum flow. In: <i>50th International Colloquium on Automata, Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.69\">10.4230/LIPIcs.ICALP.2023.69</a>","apa":"Goranci, G., &#38; Henzinger, M. (2023). Efficient data structures for incremental exact and approximate maximum flow. In <i>50th International Colloquium on Automata, Languages, and Programming</i> (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.69\">https://doi.org/10.4230/LIPIcs.ICALP.2023.69</a>","ista":"Goranci G, Henzinger M. 2023. Efficient data structures for incremental exact and approximate maximum flow. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 69."},"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772785"]},"date_published":"2023-07-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_processing_charge":"Yes","volume":261,"file_date_updated":"2023-08-21T06:59:05Z","intvolume":"       261","oa_version":"Published Version","project":[{"call_identifier":"H2020","grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"article_number":"69","arxiv":1,"alternative_title":["LIPIcs"],"ddc":["000"],"date_created":"2023-08-20T22:01:14Z","status":"public","publication":"50th International Colloquium on Automata, Languages, and Programming","department":[{"_id":"MoHe"}],"language":[{"iso":"eng"}],"month":"07","oa":1,"date_updated":"2025-06-04T07:19:37Z","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.","file":[{"date_created":"2023-08-21T06:59:05Z","content_type":"application/pdf","file_id":"14089","file_name":"2023_LIPIcsICALP_Goranci.pdf","success":1,"access_level":"open_access","file_size":875910,"date_updated":"2023-08-21T06:59:05Z","checksum":"074177e815a1656de5d4071c7a3dffa6","relation":"main_file","creator":"dernst"}],"day":"01","year":"2023","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"type":"conference","publication_status":"published"},{"quality_controlled":"1","scopus_import":"1","corr_author":"1","external_id":{"arxiv":["2305.00122"]},"author":[{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","first_name":"Monika H"},{"first_name":"Paul","full_name":"Liu, Paul","last_name":"Liu"},{"first_name":"Jan","last_name":"Vondrák","full_name":"Vondrák, Jan"},{"first_name":"Da Wei","full_name":"Zheng, Da Wei","last_name":"Zheng"}],"has_accepted_license":"1","doi":"10.4230/LIPIcs.ICALP.2023.74","title":"Faster submodular maximization for several classes of matroids","abstract":[{"text":"The maximization of submodular functions have found widespread application in areas such as machine learning, combinatorial optimization, and economics, where practitioners often wish to enforce various constraints; the matroid constraint has been investigated extensively due to its algorithmic properties and expressive power. Though tight approximation algorithms for general matroid constraints exist in theory, the running times of such algorithms typically scale quadratically, and are not practical for truly large scale settings. Recent progress has focused on fast algorithms for important classes of matroids given in explicit form. Currently, nearly-linear time algorithms only exist for graphic and partition matroids [Alina Ene and Huy L. Nguyen, 2019]. In this work, we develop algorithms for monotone submodular maximization constrained by graphic, transversal matroids, or laminar matroids in time near-linear in the size of their representation. Our algorithms achieve an optimal approximation of 1-1/e-ε and both generalize and accelerate the results of Ene and Nguyen [Alina Ene and Huy L. Nguyen, 2019]. In fact, the running time of our algorithm cannot be improved within the fast continuous greedy framework of Badanidiyuru and Vondrák [Ashwinkumar Badanidiyuru and Jan Vondrák, 2014].\r\nTo achieve near-linear running time, we make use of dynamic data structures that maintain bases with approximate maximum cardinality and weight under certain element updates. These data structures need to support a weight decrease operation and a novel Freeze operation that allows the algorithm to freeze elements (i.e. force to be contained) in its basis regardless of future data structure operations. For the laminar matroid, we present a new dynamic data structure using the top tree interface of Alstrup, Holm, de Lichtenberg, and Thorup [Stephen Alstrup et al., 2005] that maintains the maximum weight basis under insertions and deletions of elements in O(log n) time. This data structure needs to support certain subtree query and path update operations that are performed every insertion and deletion that are non-trivial to handle in conjunction. For the transversal matroid the Freeze operation corresponds to requiring the data structure to keep a certain set S of vertices matched, a property that we call S-stability. While there is a large body of work on dynamic matching algorithms, none are S-stable and maintain an approximate maximum weight matching under vertex updates. We give the first such algorithm for bipartite graphs with total running time linear (up to log factors) in the number of edges.","lang":"eng"}],"ec_funded":1,"conference":{"end_date":"2023-07-14","start_date":"2023-07-10","name":"ICALP: Automata, Languages and Programming","location":"Paderborn, Germany"},"project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","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","grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"intvolume":"       261","oa_version":"Published Version","file_date_updated":"2023-08-21T07:04:36Z","volume":261,"article_processing_charge":"Yes","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"ista":"Henzinger M, Liu P, Vondrák J, Zheng DW. 2023. Faster submodular maximization for several classes of matroids. 50th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261, 74.","ama":"Henzinger M, Liu P, Vondrák J, Zheng DW. Faster submodular maximization for several classes of matroids. In: <i>50th International Colloquium on Automata, Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.74\">10.4230/LIPIcs.ICALP.2023.74</a>","apa":"Henzinger, M., Liu, P., Vondrák, J., &#38; Zheng, D. W. (2023). Faster submodular maximization for several classes of matroids. In <i>50th International Colloquium on Automata, Languages, and Programming</i> (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.74\">https://doi.org/10.4230/LIPIcs.ICALP.2023.74</a>","mla":"Henzinger, Monika, et al. “Faster Submodular Maximization for Several Classes of Matroids.” <i>50th International Colloquium on Automata, Languages, and Programming</i>, vol. 261, 74, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.74\">10.4230/LIPIcs.ICALP.2023.74</a>.","chicago":"Henzinger, Monika, Paul Liu, Jan Vondrák, and Da Wei Zheng. “Faster Submodular Maximization for Several Classes of Matroids.” In <i>50th International Colloquium on Automata, Languages, and Programming</i>, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2023.74\">https://doi.org/10.4230/LIPIcs.ICALP.2023.74</a>.","short":"M. Henzinger, P. Liu, J. Vondrák, D.W. Zheng, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","ieee":"M. Henzinger, P. Liu, J. Vondrák, and D. W. Zheng, “Faster submodular maximization for several classes of matroids,” in <i>50th International Colloquium on Automata, Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261."},"publication_identifier":{"isbn":["9783959772785"],"issn":["1868-8969"]},"date_published":"2023-07-01T00:00:00Z","_id":"14086","publication":"50th International Colloquium on Automata, Languages, and Programming","status":"public","date_created":"2023-08-20T22:01:14Z","arxiv":1,"alternative_title":["LIPIcs"],"ddc":["000"],"article_number":"74","publication_status":"published","type":"conference","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"year":"2023","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","file":[{"relation":"main_file","creator":"dernst","checksum":"a5eef225014e003efbfbe4830fdd23cb","access_level":"open_access","file_size":930943,"date_updated":"2023-08-21T07:04:36Z","file_name":"2023_LIPIcsICALP_HenzingerM.pdf","success":1,"content_type":"application/pdf","file_id":"14090","date_created":"2023-08-21T07:04:36Z"}],"acknowledgement":" Monika Henzinger: This project has received funding from the European Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant\r\nagreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project “Static and Dynamic Hierarchical Graph Decompositions”, I 5982-N, and project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024. Jan Vondrák: Supported by NSF Award 2127781.","language":[{"iso":"eng"}],"date_updated":"2025-07-10T11:50:45Z","oa":1,"month":"07","department":[{"_id":"MoHe"}]},{"conference":{"end_date":"2023-09-22","name":"CONCUR: Conference on Concurrency Theory","start_date":"2023-09-19","location":"Antwerp, Belgium"},"ec_funded":1,"title":"Hypernode automata","abstract":[{"lang":"eng","text":"We introduce hypernode automata as a new specification formalism for hyperproperties of concurrent systems. They are finite automata with nodes labeled with hypernode logic formulas and transitions labeled with actions. A hypernode logic formula specifies relations between sequences of variable values in different system executions. Unlike HyperLTL, hypernode logic takes an asynchronous view on execution traces by constraining the values and the order of value changes of each variable without correlating the timing of the changes. Different execution traces are synchronized solely through the transitions of hypernode automata. Hypernode automata naturally combine asynchronicity at the node level with synchronicity at the transition level. We show that the model-checking problem for hypernode automata is decidable over action-labeled Kripke structures, whose actions induce transitions of the specification automata. For this reason, hypernode automaton is a suitable formalism for specifying and verifying asynchronous hyperproperties, such as declassifying observational determinism in multi-threaded programs."}],"doi":"10.4230/LIPIcs.CONCUR.2023.21","has_accepted_license":"1","author":[{"first_name":"Ezio","full_name":"Bartocci, Ezio","last_name":"Bartocci"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000-0002-2985-7724","first_name":"Thomas A"},{"last_name":"Nickovic","id":"41BCEE5C-F248-11E8-B48F-1D18A9856A87","full_name":"Nickovic, Dejan","first_name":"Dejan"},{"orcid":"0000-0002-8741-5799","first_name":"Ana","full_name":"Oliveira da Costa, Ana","id":"f347ec37-6676-11ee-b395-a888cb7b4fb4","last_name":"Oliveira da Costa"}],"external_id":{"arxiv":["2305.02836"]},"corr_author":"1","scopus_import":"1","quality_controlled":"1","_id":"14405","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772990"]},"citation":{"ista":"Bartocci E, Henzinger TA, Nickovic D, Oliveira da Costa A. 2023. Hypernode automata. 34th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 279, 21.","ama":"Bartocci E, Henzinger TA, Nickovic D, Oliveira da Costa A. Hypernode automata. In: <i>34th International Conference on Concurrency Theory</i>. Vol 279. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.21\">10.4230/LIPIcs.CONCUR.2023.21</a>","apa":"Bartocci, E., Henzinger, T. A., Nickovic, D., &#38; Oliveira da Costa, A. (2023). Hypernode automata. In <i>34th International Conference on Concurrency Theory</i> (Vol. 279). Antwerp, Belgium: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.21\">https://doi.org/10.4230/LIPIcs.CONCUR.2023.21</a>","mla":"Bartocci, Ezio, et al. “Hypernode Automata.” <i>34th International Conference on Concurrency Theory</i>, vol. 279, 21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.21\">10.4230/LIPIcs.CONCUR.2023.21</a>.","short":"E. Bartocci, T.A. Henzinger, D. Nickovic, A. Oliveira da Costa, in:, 34th International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","ieee":"E. Bartocci, T. A. Henzinger, D. Nickovic, and A. Oliveira da Costa, “Hypernode automata,” in <i>34th International Conference on Concurrency Theory</i>, Antwerp, Belgium, 2023, vol. 279.","chicago":"Bartocci, Ezio, Thomas A Henzinger, Dejan Nickovic, and Ana Oliveira da Costa. “Hypernode Automata.” In <i>34th International Conference on Concurrency Theory</i>, Vol. 279. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2023.21\">https://doi.org/10.4230/LIPIcs.CONCUR.2023.21</a>."},"date_published":"2023-09-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","article_processing_charge":"Yes","volume":279,"file_date_updated":"2023-10-09T07:42:45Z","oa_version":"Published Version","intvolume":"       279","project":[{"call_identifier":"H2020","name":"Vigilant Algorithmic Monitoring of Software","grant_number":"101020093","_id":"62781420-2b32-11ec-9570-8d9b63373d4d"}],"article_number":"21","alternative_title":["LIPIcs"],"ddc":["000"],"related_material":{"record":[{"status":"public","id":"20866","relation":"later_version"}]},"arxiv":1,"date_created":"2023-10-08T22:01:16Z","status":"public","publication":"34th International Conference on Concurrency Theory","department":[{"_id":"ToHe"}],"month":"09","oa":1,"date_updated":"2026-01-05T12:27:40Z","language":[{"iso":"eng"}],"acknowledgement":"This work was supported in part by the Austrian Science Fund (FWF) SFB project\r\nSpyCoDe F8502, by the FWF projects ZK-35 and W1255-N23, and by the ERC Advanced Grant\r\nVAMOS 101020093.","file":[{"date_created":"2023-10-09T07:42:45Z","file_name":"2023_LIPcs_Bartocci.pdf","success":1,"file_id":"14413","content_type":"application/pdf","access_level":"open_access","file_size":795790,"date_updated":"2023-10-09T07:42:45Z","relation":"main_file","creator":"dernst","checksum":"215765e40454d806174ac0a223e8d6fa"}],"year":"2023","day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"type":"conference","publication_status":"published"},{"doi":"10.4230/LIPIcs.DISC.2023.35","author":[{"first_name":"Vitaly","last_name":"Aksenov","full_name":"Aksenov, Vitaly"},{"last_name":"Anoprenko","full_name":"Anoprenko, Michael","first_name":"Michael"},{"id":"2e711909-896a-11ed-bdf8-eb0f5a2984c6","last_name":"Fedorov","full_name":"Fedorov, Alexander","first_name":"Alexander"},{"last_name":"Spear","full_name":"Spear, Michael","first_name":"Michael"}],"has_accepted_license":"1","conference":{"location":"L'Aquila, Italy","start_date":"2023-10-09","name":"DISC: Symposium on Distributed Computing","end_date":"2023-10-13"},"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"}],"title":"Brief announcement: BatchBoost: Universal batching for concurrent data structures","quality_controlled":"1","scopus_import":"1","corr_author":"1","article_processing_charge":"Yes","volume":281,"_id":"14485","citation":{"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>","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>","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.","short":"V. Aksenov, M. Anoprenko, A. Fedorov, M. Spear, in:, 37th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","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>.","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.","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>."},"publication_identifier":{"isbn":["9783959773010"],"issn":["1868-8969"]},"date_published":"2023-10-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2023-11-06T11:45:21Z","intvolume":"       281","oa_version":"Published Version","article_number":"35","date_created":"2023-11-05T23:00:53Z","status":"public","publication":"37th International Symposium on Distributed Computing","ddc":["000"],"alternative_title":["LIPIcs"],"language":[{"iso":"eng"}],"date_updated":"2024-10-09T21:07:14Z","oa":1,"month":"10","department":[{"_id":"GradSch"}],"year":"2023","day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"type":"conference","publication_status":"published","file":[{"access_level":"open_access","date_updated":"2023-11-06T11:45:21Z","file_size":646665,"checksum":"d9f8d2915cccdf2df5905b7cd1b4a560","creator":"dernst","relation":"main_file","date_created":"2023-11-06T11:45:21Z","content_type":"application/pdf","file_id":"14492","success":1,"file_name":"2023_LIPIcs_Aksenov.pdf"}]},{"corr_author":"1","quality_controlled":"1","scopus_import":"1","title":"STROBE: Streaming Threshold Random Beacons","abstract":[{"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.","lang":"eng"}],"conference":{"location":"Princeton, NJ, United States","name":"AFT: Conference on Advances in Financial Technologies","start_date":"2023-10-23","end_date":"2023-10-25"},"has_accepted_license":"1","author":[{"first_name":"Donald","full_name":"Beaver, Donald","last_name":"Beaver"},{"full_name":"Kelkar, Mahimna","last_name":"Kelkar","first_name":"Mahimna"},{"first_name":"Kevin","last_name":"Lewi","full_name":"Lewi, Kevin"},{"full_name":"Nikolaenko, Valeria","last_name":"Nikolaenko","first_name":"Valeria"},{"full_name":"Sonnino, Alberto","last_name":"Sonnino","first_name":"Alberto"},{"first_name":"Konstantinos","full_name":"Chalkias, Konstantinos","last_name":"Chalkias"},{"last_name":"Kokoris Kogias","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","full_name":"Kokoris Kogias, Eleftherios","first_name":"Eleftherios"},{"first_name":"Ladi De","full_name":"Naurois, Ladi De","last_name":"Naurois"},{"last_name":"Roy","full_name":"Roy, Arnab","first_name":"Arnab"}],"main_file_link":[{"url":"https://eprint.iacr.org/2021/1643","open_access":"1"}],"doi":"10.4230/LIPIcs.AFT.2023.7","file_date_updated":"2023-11-13T08:44:34Z","oa_version":"Published Version","intvolume":"       282","publication_identifier":{"isbn":["9783959773034"],"issn":["1868-8969"]},"date_published":"2023-10-01T00:00:00Z","citation":{"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>.","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.","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>.","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.","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>","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>","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."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"14516","volume":282,"article_processing_charge":"Yes","alternative_title":["LIPIcs"],"ddc":["000"],"status":"public","publication":"5th Conference on Advances in Financial Technologies","date_created":"2023-11-12T23:00:55Z","article_number":"7","file":[{"access_level":"open_access","file_size":793495,"date_updated":"2023-11-13T08:44:34Z","relation":"main_file","creator":"dernst","checksum":"c1f98831cb5149d6c030c41999e6e960","date_created":"2023-11-13T08:44:34Z","file_name":"2023_LIPIcs_Beaver.pdf","success":1,"file_id":"14521","content_type":"application/pdf"}],"type":"conference","publication_status":"published","year":"2023","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"department":[{"_id":"ElKo"}],"acknowledgement":"Work done when all the authors were at Novi Research, Meta.","language":[{"iso":"eng"}],"month":"10","date_updated":"2024-10-09T21:07:17Z","oa":1},{"extern":"1","external_id":{"arxiv":["2211.10151"]},"scopus_import":"1","quality_controlled":"1","abstract":[{"text":"Data dissemination is a fundamental task in distributed computing. This paper studies broadcast problems in various innovative models where the communication network connecting n processes is dynamic (e.g., due to mobility or failures) and controlled by an adversary. \r\nIn the first model, the processes transitively communicate their ids in synchronous rounds along a rooted tree given in each round by the adversary whose goal is to maximize the number of rounds until at least one id is known by all processes. Previous research has shown a ⌈(3n-1)/2⌉-2 lower bound and an O(nlog log n) upper bound. We show the first linear upper bound for this problem, namely ⌈(1+√2) n-1⌉ ≈ 2.4n.\r\nWe extend these results to the setting where the adversary gives in each round k-disjoint forests and their goal is to maximize the number of rounds until there is a set of k ids such that each process knows of at least one of them. We give a ⌈3(n-k)/2⌉-1 lower bound and a (π²+6)/6 n+1 ≈ 2.6n upper bound for this problem.\r\nFinally, we study the setting where the adversary gives in each round a directed graph with k roots and their goal is to maximize the number of rounds until there exist k ids that are known by all processes. We give a ⌈3(n-3k)/2⌉+2 lower bound and a ⌈(1+√2)n⌉+k-1 ≈ 2.4n+k upper bound for this problem.\r\nFor the two latter problems no upper or lower bounds were previously known.","lang":"eng"}],"title":"Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks","keyword":["broadcast","cover","k-broadcast","dynamic radius","dynamic graphs","oblivious message adversary","time complexity","Theory of computation → Distributed algorithms","Networks → Network algorithms"],"conference":{"location":"Cambridge, Massachusetts, USA","start_date":"2023-01-10","name":"ITCS: Innovations in Theoretical Computer Science","end_date":"2023-01-13"},"author":[{"orcid":"0000-0003-4268-7368","first_name":"Antoine","last_name":"El-Hayek","id":"888a098e-fcac-11ee-aff7-d347be57b725","full_name":"El-Hayek, Antoine"},{"first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan","orcid":"0000-0002-7798-1711"}],"has_accepted_license":"1","doi":"10.4230/LIPICS.ITCS.2023.47","file_date_updated":"2026-07-22T08:04:03Z","intvolume":"       251","oa_version":"Published Version","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772631"]},"citation":{"apa":"El-Hayek, A., Henzinger, M., &#38; Schmid, S. (2023). Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks. In Y. Tauman Kalai (Ed.), <i>14th Innovations in Theoretical Computer Science Conference</i> (Vol. 251). Cambridge, Massachusetts, USA: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ITCS.2023.47\">https://doi.org/10.4230/LIPICS.ITCS.2023.47</a>","ama":"El-Hayek A, Henzinger M, Schmid S. Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks. In: Tauman Kalai Y, ed. <i>14th Innovations in Theoretical Computer Science Conference</i>. Vol 251. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPICS.ITCS.2023.47\">10.4230/LIPICS.ITCS.2023.47</a>","ista":"El-Hayek A, Henzinger M, Schmid S. 2023. Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks. 14th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 251, 47.","short":"A. El-Hayek, M. Henzinger, S. Schmid, in:, Y. Tauman Kalai (Ed.), 14th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","ieee":"A. El-Hayek, M. Henzinger, and S. Schmid, “Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks,” in <i>14th Innovations in Theoretical Computer Science Conference</i>, Cambridge, Massachusetts, USA, 2023, vol. 251.","chicago":"El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks.” In <i>14th Innovations in Theoretical Computer Science Conference</i>, edited by Yael Tauman Kalai, Vol. 251. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPICS.ITCS.2023.47\">https://doi.org/10.4230/LIPICS.ITCS.2023.47</a>.","mla":"El-Hayek, Antoine, et al. “Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks.” <i>14th Innovations in Theoretical Computer Science Conference</i>, edited by Yael Tauman Kalai, vol. 251, 47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPICS.ITCS.2023.47\">10.4230/LIPICS.ITCS.2023.47</a>."},"date_published":"2023-02-01T00:00:00Z","editor":[{"last_name":"Tauman Kalai","full_name":"Tauman Kalai, Yael","first_name":"Yael"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"22373","volume":251,"article_processing_charge":"No","related_material":{"record":[{"status":"public","id":"22281","relation":"dissertation_contains"}]},"alternative_title":["LIPIcs"],"arxiv":1,"ddc":["000"],"status":"public","publication":"14th Innovations in Theoretical Computer Science Conference","date_created":"2026-07-20T11:45:04Z","article_number":"47","file":[{"file_size":1077427,"date_updated":"2026-07-22T08:04:03Z","access_level":"open_access","checksum":"d7f45fdcbc5fccd61db69f56d775c636","relation":"main_file","creator":"cchlebak","date_created":"2026-07-22T08:04:03Z","file_id":"22383","content_type":"application/pdf","file_name":"2023_LIPIcs_El-Hayek.pdf","success":1}],"type":"conference","publication_status":"published","day":"01","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","year":"2023","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"acknowledgement":" This project has received funding from the European Research Council (ERC) under\r\nthe European Union’s Horizon 2020 research and innovation programme (grant agreement No.\r\n101019564). This work was further supported by the Austrian Science Fund (FWF) and netIDEE\r\nSCIENCE project P 33775-N, as well as the FWF project I 4800-N (ADVISE)","language":[{"iso":"eng"}],"oa":1,"month":"02","date_updated":"2026-07-24T12:48:29Z"},{"quality_controlled":"1","scopus_import":"1","corr_author":"1","title":"Beyond distributed subgraph detection: Induced subgraphs, multicolored problems and graph parameters","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."}],"ec_funded":1,"conference":{"end_date":"2021-12-15","location":"Strasbourg, France","start_date":"2021-12-13","name":"OPODIS"},"has_accepted_license":"1","author":[{"first_name":"Amir","last_name":"Nikabadi","full_name":"Nikabadi, Amir"},{"first_name":"Janne","last_name":"Korhonen","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","full_name":"Korhonen, Janne"}],"doi":"10.4230/LIPIcs.OPODIS.2021.15","oa_version":"Published Version","intvolume":"       217","file_date_updated":"2022-05-02T07:53:00Z","project":[{"call_identifier":"H2020","grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","editor":[{"first_name":"Quentin","full_name":"Bramas, Quentin","last_name":"Bramas"},{"first_name":"Vincent","full_name":"Gramoli, Vincent","last_name":"Gramoli"},{"first_name":"Alessia","full_name":"Milani, Alessia","last_name":"Milani"}],"citation":{"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>","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>","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.","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>.","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>.","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.","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."},"publication_identifier":{"isbn":["9783959772198"],"issn":["1868-8969"]},"date_published":"2022-02-01T00:00:00Z","_id":"11183","volume":217,"article_processing_charge":"No","alternative_title":["LIPIcs"],"ddc":["510"],"publication":"25th International Conference on Principles of Distributed Systems","status":"public","date_created":"2022-04-17T22:01:47Z","article_number":"15","file":[{"access_level":"open_access","file_size":790396,"date_updated":"2022-05-02T07:53:00Z","checksum":"626551c14de5d4091573200ed0535752","relation":"main_file","creator":"dernst","date_created":"2022-05-02T07:53:00Z","file_id":"11345","content_type":"application/pdf","file_name":"2022_LIPICs_Nikabadi.pdf","success":1}],"publication_status":"published","type":"conference","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"year":"2022","day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"DaAl"}],"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].","month":"02","date_updated":"2025-04-14T07:49:13Z","oa":1,"language":[{"iso":"eng"}]},{"corr_author":"1","scopus_import":"1","quality_controlled":"1","external_id":{"arxiv":["2102.08808"]},"has_accepted_license":"1","author":[{"last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian"},{"full_name":"Gelashvili, Rati","last_name":"Gelashvili","first_name":"Rati"},{"first_name":"Joel","orcid":"0000-0002-6432-6646","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","last_name":"Rybicki","full_name":"Rybicki, Joel"}],"doi":"10.4230/LIPIcs.OPODIS.2021.14","title":"Fast graphical population protocols","abstract":[{"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.","lang":"eng"}],"ec_funded":1,"conference":{"end_date":"2021-12-15","start_date":"2021-12-13","name":"OPODIS","location":"Strasbourg, France"},"project":[{"call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning"},{"name":"Coordination in constrained and natural distributed systems","grant_number":"840605","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"intvolume":"       217","oa_version":"Published Version","file_date_updated":"2022-05-02T08:06:33Z","volume":217,"article_processing_charge":"No","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","editor":[{"first_name":"Quentin","last_name":"Bramas","full_name":"Bramas, Quentin"},{"first_name":"Vincent","last_name":"Gramoli","full_name":"Gramoli, Vincent"},{"first_name":"Alessia","last_name":"Milani","full_name":"Milani, Alessia"}],"date_published":"2022-02-01T00:00:00Z","citation":{"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.","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.","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>.","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>.","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>","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>"},"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772198"]},"_id":"11184","publication":"25th International Conference on Principles of Distributed Systems","status":"public","date_created":"2022-04-17T22:01:47Z","arxiv":1,"alternative_title":["LIPIcs"],"ddc":["510"],"article_number":"14","publication_status":"published","type":"conference","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"year":"2022","day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"date_updated":"2022-05-02T08:06:33Z","access_level":"open_access","file_size":959406,"checksum":"2c7c982174c6f98c4ca6e92539d15086","creator":"dernst","relation":"main_file","date_created":"2022-05-02T08:06:33Z","content_type":"application/pdf","file_id":"11346","success":1,"file_name":"2022_LIPICs_Alistarh.pdf"}],"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.","date_updated":"2025-04-14T07:49:13Z","language":[{"iso":"eng"}],"oa":1,"month":"02","department":[{"_id":"DaAl"}]}]