[{"article_processing_charge":"No","type":"conference","publication":"4th Symposium on Algorithmic Foundations of Dynamic Networks","date_updated":"2025-09-30T13:37:28Z","scopus_import":"1","ddc":["000"],"file_date_updated":"2025-06-23T11:23:29Z","ec_funded":1,"doi":"10.4230/LIPIcs.SAND.2025.4","publication_status":"published","oa":1,"day":"02","OA_type":"gold","conference":{"start_date":"2025-06-09","name":"SAND: Symposium on Algorithmic Foundations of Dynamic Networks","location":"Liverpool, United Kingdom","end_date":"2025-06-11"},"year":"2025","alternative_title":["LIPIcs"],"volume":330,"title":"On b-matching and fully-dynamic maximum k-edge coloring","language":[{"iso":"eng"}],"article_number":"4","abstract":[{"lang":"eng","text":"Given a graph G that undergoes a sequence of edge insertions and deletions, we study the Maximum k-Edge Coloring problem (MkEC): Having access to k different colors, color as many edges of G as possible such that no two adjacent edges share the same color. While this problem is different from simply maintaining a b-matching with b = k, the two problems are related. However, maximum b-matching can be solved efficiently in the static setting, whereas MkEC is NP-hard and even APX-hard for k ≥ 2. \r\nWe present new results on both problems: For b-matching, we show a new integrality gap result and we adapt Wajc’s matching sparsification scheme [David Wajc, 2020] for the case where b is a constant.\r\nUsing these as basis, we give three new algorithms for the dynamic MkEC problem: Our MatchO algorithm builds on the dynamic (2+ε)-approximation algorithm of Bhattacharya, Gupta, and Mohan [Sayan Bhattacharya et al., 2017] for b-matching and achieves a (2+ε)(k+1)/k-approximation in O(poly(log n, ε^-1)) update time against an oblivious adversary. Our MatchA algorithm builds on the dynamic (7+ε)-approximation algorithm by Bhattacharya, Henzinger, and Italiano [Sayan Bhattacharya et al., 2015] for fractional b-matching and achieves a (7+ε)(3k+3)/(3k-1)-approximation in O(poly(log n, ε^-1)) update time against an adaptive adversary. Moreover, our reductions use the dynamic b-matching algorithm as a black box, so any future improvement in the approximation ratio for dynamic b-matching will automatically translate into a better approximation ratio for our algorithms. Finally, we present a greedy algorithm with O(Δ+k) update time, which guarantees a 2.16 approximation factor."}],"corr_author":"1","department":[{"_id":"MoHe"}],"date_created":"2025-06-22T22:02:06Z","citation":{"chicago":"El-Hayek, Antoine, Kathrin Hanauer, and Monika Henzinger. “On B-Matching and Fully-Dynamic Maximum k-Edge Coloring.” In <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i>, Vol. 330. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2025.4\">https://doi.org/10.4230/LIPIcs.SAND.2025.4</a>.","ista":"El-Hayek A, Hanauer K, Henzinger M. 2025. On b-matching and fully-dynamic maximum k-edge coloring. 4th Symposium on Algorithmic Foundations of Dynamic Networks. SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 330, 4.","mla":"El-Hayek, Antoine, et al. “On B-Matching and Fully-Dynamic Maximum k-Edge Coloring.” <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i>, vol. 330, 4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2025.4\">10.4230/LIPIcs.SAND.2025.4</a>.","short":"A. El-Hayek, K. Hanauer, M. Henzinger, in:, 4th Symposium on Algorithmic Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","ieee":"A. El-Hayek, K. Hanauer, and M. Henzinger, “On b-matching and fully-dynamic maximum k-edge coloring,” in <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i>, Liverpool, United Kingdom, 2025, vol. 330.","ama":"El-Hayek A, Hanauer K, Henzinger M. On b-matching and fully-dynamic maximum k-edge coloring. In: <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i>. Vol 330. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2025.4\">10.4230/LIPIcs.SAND.2025.4</a>","apa":"El-Hayek, A., Hanauer, K., &#38; Henzinger, M. (2025). On b-matching and fully-dynamic maximum k-edge coloring. In <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i> (Vol. 330). Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2025.4\">https://doi.org/10.4230/LIPIcs.SAND.2025.4</a>"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","month":"06","status":"public","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"quality_controlled":"1","project":[{"name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020","grant_number":"101019564"},{"name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"date_published":"2025-06-02T00:00:00Z","_id":"19858","intvolume":"       330","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773683"]},"OA_place":"publisher","isi":1,"external_id":{"arxiv":["2310.01149"],"isi":["001532136900004"]},"arxiv":1,"author":[{"full_name":"El-Hayek, Antoine","orcid":"0000-0003-4268-7368","id":"888a098e-fcac-11ee-aff7-d347be57b725","first_name":"Antoine","last_name":"El-Hayek"},{"first_name":"Kathrin","last_name":"Hanauer","full_name":"Hanauer, Kathrin"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa_version":"Published Version","file":[{"file_size":995666,"checksum":"ad93a1e052adb29d7bfe8bd551bab193","success":1,"file_name":"2025_LIPIcs_ElHayek.pdf","date_created":"2025-06-23T11:23:29Z","relation":"main_file","access_level":"open_access","creator":"dernst","content_type":"application/pdf","file_id":"19872","date_updated":"2025-06-23T11:23:29Z"}],"has_accepted_license":"1","acknowledgement":"This project has received funding from the European Research Council (ERC) under the\r\nEuropean 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. This work was further supported by the Federal Ministry of Education and Research (BMBF) project, 6G-RIC: 6G Research and Innovation Cluster, grant 16KISK020K."},{"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"orcid":"0000-0002-2985-7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger"},{"full_name":"Kebis, Pavol","id":"2e0132b3-4e98-11ef-b275-cf7281c2802a","first_name":"Pavol","last_name":"Kebis"},{"first_name":"Nicolas Adrien","last_name":"Mazzocchi","full_name":"Mazzocchi, Nicolas Adrien","id":"b26baa86-3308-11ec-87b0-8990f34baa85"},{"first_name":"Naci E","last_name":"Sarac","full_name":"Sarac, Naci E","id":"8C6B42F8-C8E6-11E9-A03A-F2DCE5697425"}],"arxiv":1,"external_id":{"arxiv":["2506.0515"],"isi":["001570540800021"]},"isi":1,"OA_place":"publisher","has_accepted_license":"1","acknowledgement":"This work was supported in part by the ERC-2020-AdG 101020093.","file":[{"relation":"main_file","access_level":"open_access","date_created":"2025-09-03T10:01:53Z","success":1,"checksum":"9d4054058757a73477e6015b10ed6996","file_size":1257397,"file_name":"2025_CONCUR_HenzingerT.pdf","date_updated":"2025-09-03T10:01:53Z","file_id":"20282","content_type":"application/pdf","creator":"dernst"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"status":"public","month":"08","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"short":"T.A. Henzinger, P. Kebis, N.A. Mazzocchi, N.E. Sarac, in:, 36th International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","mla":"Henzinger, Thomas A., et al. “Quantitative Language Automata.” <i>36th International Conference on Concurrency Theory</i>, vol. 348, 21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2025.21\">10.4230/LIPIcs.CONCUR.2025.21</a>.","ista":"Henzinger TA, Kebis P, Mazzocchi NA, Sarac NE. 2025. Quantitative language automata. 36th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 348, 21.","chicago":"Henzinger, Thomas A, Pavol Kebis, Nicolas Adrien Mazzocchi, and Naci E Sarac. “Quantitative Language Automata.” In <i>36th International Conference on Concurrency Theory</i>, Vol. 348. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2025.21\">https://doi.org/10.4230/LIPIcs.CONCUR.2025.21</a>.","apa":"Henzinger, T. A., Kebis, P., Mazzocchi, N. A., &#38; Sarac, N. E. (2025). Quantitative language automata. In <i>36th International Conference on Concurrency Theory</i> (Vol. 348). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2025.21\">https://doi.org/10.4230/LIPIcs.CONCUR.2025.21</a>","ieee":"T. A. Henzinger, P. Kebis, N. A. Mazzocchi, and N. E. Sarac, “Quantitative language automata,” in <i>36th International Conference on Concurrency Theory</i>, Aarhus, Denmark, 2025, vol. 348.","ama":"Henzinger TA, Kebis P, Mazzocchi NA, Sarac NE. Quantitative language automata. In: <i>36th International Conference on Concurrency Theory</i>. Vol 348. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2025.21\">10.4230/LIPIcs.CONCUR.2025.21</a>"},"date_created":"2025-08-31T22:01:32Z","department":[{"_id":"ToHe"}],"intvolume":"       348","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773898"]},"_id":"20253","date_published":"2025-08-18T00:00:00Z","quality_controlled":"1","project":[{"grant_number":"101020093","call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software"}],"publication_status":"published","doi":"10.4230/LIPIcs.CONCUR.2025.21","ec_funded":1,"file_date_updated":"2025-09-03T10:01:53Z","abstract":[{"text":"A quantitative word automaton (QWA) defines a function from infinite words to values. For example, every infinite run of a limit-average QWA 𝒜 obtains a mean payoff, and every word w ∈ Σ^ω is assigned the maximal mean payoff obtained by nondeterministic runs of 𝒜 over w. We introduce quantitative language automata (QLAs) that define functions from language generators (i.e., implementations) to values, where a language generator can be nonprobabilistic, defining a set of infinite words, or probabilistic, defining a probability measure over infinite words. A QLA consists of a QWA and an aggregator function. For example, given a QWA 𝒜, the infimum aggregator maps each language L ⊆ Σ^ω to the greatest lower bound assigned by 𝒜 to any word in L. For boolean value sets, QWAs define boolean properties of traces, and QLAs define boolean properties of sets of traces, i.e., hyperproperties. For more general value sets, QLAs serve as a specification language for a generalization of hyperproperties, called quantitative hyperproperties. A nonprobabilistic (resp. probabilistic) quantitative hyperproperty assigns a value to each set (resp. distribution) G of traces, e.g., the minimal (resp. expected) average response time exhibited by the traces in G. We give several examples of quantitative hyperproperties and investigate three paradigmatic problems for QLAs: evaluation, nonemptiness, and universality. In the evaluation problem, given a QLA 𝔸 and an implementation G, we ask for the value that 𝔸 assigns to G. In the nonemptiness (resp. universality) problem, given a QLA 𝔸 and a value k, we ask whether 𝔸 assigns at least k to some (resp. every) language. We provide a comprehensive picture of decidability for these problems for QLAs with common aggregators as well as their restrictions to ω-regular languages and trace distributions generated by finite-state Markov chains.","lang":"eng"}],"corr_author":"1","article_number":"21","language":[{"iso":"eng"}],"title":"Quantitative language automata","volume":348,"year":"2025","alternative_title":["LIPIcs"],"day":"18","conference":{"name":"CONCUR: Conference on Concurrency Theory","location":"Aarhus, Denmark","end_date":"2025-08-29","start_date":"2025-08-26"},"OA_type":"gold","oa":1,"article_processing_charge":"No","ddc":["000"],"scopus_import":"1","date_updated":"2025-12-01T12:36:52Z","publication":"36th International Conference on Concurrency Theory","type":"conference"},{"oa":1,"day":"20","conference":{"start_date":"2025-08-25","name":"MFCS: Mathematical Foundations of Computer Science","location":"Warsaw, Poland","end_date":"2025-08-29"},"OA_type":"gold","year":"2025","alternative_title":["LIPIcs"],"volume":345,"title":"Finding equilibria: Simpler for pessimists, simplest for optimists","article_number":"30","language":[{"iso":"eng"}],"corr_author":"1","abstract":[{"lang":"eng","text":"We consider equilibria in multiplayer stochastic graph games with terminal-node rewards. In such games, Nash equilibria are defined assuming that each player seeks to maximise their expected payoff, ignoring their aversion or tolerance to risk. We therefore study risk-sensitive equilibria (RSEs), where the expected payoff is replaced by a risk measure. A classical risk measure in the literature is the entropic risk measure, where each player has a real valued parameter capturing their risk-averseness. We introduce the extreme risk measure, which corresponds to extreme cases of entropic risk measure, where players are either extreme optimists or extreme pessimists. Under extreme risk measure, every player is an extremist: an extreme optimist perceives their reward as the maximum payoff that can be achieved with positive probability, while an extreme pessimist expects the minimum payoff achievable with positive probability. We argue that the extreme risk measure, especially in multi-player graph based settings, is particularly relevant as they can model several real life instances such as interactions between secure systems and potential security threats, or distributed controls for safety critical systems. We prove that RSEs defined with the extreme risk measure are guaranteed to exist when all rewards are non-negative. Furthermore, we prove that the problem of deciding whether a given game contains an RSE that generates risk measures within specified intervals is decidable and NP-complete for our extreme risk measure, and even PTIME-complete when all players are extreme optimists, while that same problem is undecidable using the entropic risk measure or even the classical expected payoff. This establishes, to our knowledge, the first decidable fragment for equilibria in simple stochastic games without restrictions on strategy types or number of players."}],"file_date_updated":"2025-09-08T07:11:12Z","ec_funded":1,"doi":"10.4230/LIPIcs.MFCS.2025.30","publication_status":"published","type":"conference","publication":"50th International Symposium on Mathematical Foundations of Computer Science","date_updated":"2025-09-08T07:15:40Z","scopus_import":"1","ddc":["000"],"article_processing_charge":"Yes","file":[{"file_size":1149694,"success":1,"checksum":"9bc6b8e537662d371d2a27444cbc0b75","file_name":"2025_MFCS_Brice.pdf","date_created":"2025-09-08T07:11:12Z","relation":"main_file","access_level":"open_access","creator":"dernst","content_type":"application/pdf","date_updated":"2025-09-08T07:11:12Z","file_id":"20306"}],"acknowledgement":"This work is a part of project VAMOS that has received funding from the European\r\nResearch Council (ERC), grant agreement No 101020093. We thank anonymous reviewers for pointing us to the Hurwicz criterion and to the work of Gallego-Hernández and Mansutti [13]. We thank Marie van den Bogaard for her valuable feedback on the first author’s PhD dissertation, which helped improve the quality of this work. ","has_accepted_license":"1","OA_place":"publisher","external_id":{"arxiv":["2502.0531"]},"arxiv":1,"author":[{"last_name":"Brice","first_name":"Léonard","full_name":"Brice, Léonard"},{"last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"id":"3807fb92-fdc1-11ee-bb4a-b4d8a431c753","full_name":"Thejaswini, K. S.","last_name":"Thejaswini","first_name":"K. S."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","quality_controlled":"1","project":[{"grant_number":"101020093","call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software"}],"date_published":"2025-08-20T00:00:00Z","_id":"20290","intvolume":"       345","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773881"]},"date_created":"2025-09-07T22:01:32Z","department":[{"_id":"ToHe"}],"citation":{"ieee":"L. Brice, T. A. Henzinger, and K. S. Thejaswini, “Finding equilibria: Simpler for pessimists, simplest for optimists,” in <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, Warsaw, Poland, 2025, vol. 345.","ama":"Brice L, Henzinger TA, Thejaswini KS. Finding equilibria: Simpler for pessimists, simplest for optimists. In: <i>50th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.30\">10.4230/LIPIcs.MFCS.2025.30</a>","apa":"Brice, L., Henzinger, T. A., &#38; Thejaswini, K. S. (2025). Finding equilibria: Simpler for pessimists, simplest for optimists. In <i>50th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 345). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.30\">https://doi.org/10.4230/LIPIcs.MFCS.2025.30</a>","ista":"Brice L, Henzinger TA, Thejaswini KS. 2025. Finding equilibria: Simpler for pessimists, simplest for optimists. 50th International Symposium on Mathematical Foundations of Computer Science. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 345, 30.","short":"L. Brice, T.A. Henzinger, K.S. Thejaswini, in:, 50th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","mla":"Brice, Léonard, et al. “Finding Equilibria: Simpler for Pessimists, Simplest for Optimists.” <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 345, 30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.30\">10.4230/LIPIcs.MFCS.2025.30</a>.","chicago":"Brice, Léonard, Thomas A Henzinger, and K. S. Thejaswini. “Finding Equilibria: Simpler for Pessimists, Simplest for Optimists.” In <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.30\">https://doi.org/10.4230/LIPIcs.MFCS.2025.30</a>."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","month":"08","status":"public","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"}},{"article_processing_charge":"No","ddc":["000"],"scopus_import":"1","date_updated":"2025-09-08T07:06:11Z","type":"conference","publication":"50th International Symposium on Mathematical Foundations of Computer Science","doi":"10.4230/LIPIcs.MFCS.2025.57","publication_status":"published","file_date_updated":"2025-09-08T06:56:56Z","ec_funded":1,"article_number":"57","language":[{"iso":"eng"}],"abstract":[{"text":"We define and study classes of ω-regular automata for which the nondeterminism can be resolved by a policy that uses a combination of memory and randomness on any input word, based solely on the prefix read so far. We examine two settings for providing the input word to an automaton. In the first setting, called adversarial resolvability, the input word is constructed letter-by-letter by an adversary, dependent on the resolver’s previous decisions. In the second setting, called stochastic resolvability, the adversary pre-commits to an infinite word and reveals it letter-by-letter. In each setting, we require the existence of an almost-sure resolver, i.e., a policy that ensures that as long as the adversary provides a word in the language of the underlying nondeterministic automaton, the run constructed by the policy is accepting with probability 1.\r\nThe class of automata that are adversarially resolvable is the well-studied class of history-deterministic automata. The case of stochastically resolvable automata, on the other hand, defines a novel class. Restricting the class of resolvers in both settings to stochastic policies without memory introduces two additional new classes of automata. We show that the new automata classes offer interesting trade-offs between succinctness, expressivity, and computational complexity, providing a fine gradation between deterministic automata and nondeterministic automata.","lang":"eng"}],"corr_author":"1","OA_type":"gold","day":"20","conference":{"start_date":"2025-08-25","name":"MFCS: Mathematical Foundations of Computer Science","end_date":"2025-08-29","location":"Warsaw, Poland"},"oa":1,"title":"Resolving nondeterminism with randomness","volume":345,"year":"2025","alternative_title":["LIPIcs"],"status":"public","month":"08","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"department":[{"_id":"ToHe"}],"date_created":"2025-09-07T22:01:32Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"mla":"Henzinger, Thomas A., et al. “Resolving Nondeterminism with Randomness.” <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 345, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.57\">10.4230/LIPIcs.MFCS.2025.57</a>.","short":"T.A. Henzinger, A. Prakash, K.S. Thejaswini, in:, 50th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","ista":"Henzinger TA, Prakash A, Thejaswini KS. 2025. Resolving nondeterminism with randomness. 50th International Symposium on Mathematical Foundations of Computer Science. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 345, 57.","chicago":"Henzinger, Thomas A, Aditya Prakash, and K. S. Thejaswini. “Resolving Nondeterminism with Randomness.” In <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.57\">https://doi.org/10.4230/LIPIcs.MFCS.2025.57</a>.","apa":"Henzinger, T. A., Prakash, A., &#38; Thejaswini, K. S. (2025). Resolving nondeterminism with randomness. In <i>50th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 345). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.57\">https://doi.org/10.4230/LIPIcs.MFCS.2025.57</a>","ieee":"T. A. Henzinger, A. Prakash, and K. S. Thejaswini, “Resolving nondeterminism with randomness,” in <i>50th International Symposium on Mathematical Foundations of Computer Science</i>, Warsaw, Poland, 2025, vol. 345.","ama":"Henzinger TA, Prakash A, Thejaswini KS. Resolving nondeterminism with randomness. In: <i>50th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2025.57\">10.4230/LIPIcs.MFCS.2025.57</a>"},"publication_identifier":{"isbn":["9783959773881"],"issn":["1868-8969"]},"intvolume":"       345","_id":"20291","quality_controlled":"1","project":[{"call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software","grant_number":"101020093"}],"date_published":"2025-08-20T00:00:00Z","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_place":"publisher","author":[{"first_name":"Thomas A","last_name":"Henzinger","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2985-7724"},{"first_name":"Aditya","last_name":"Prakash","full_name":"Prakash, Aditya"},{"first_name":"K. S.","last_name":"Thejaswini","id":"3807fb92-fdc1-11ee-bb4a-b4d8a431c753","full_name":"Thejaswini, K. S."}],"arxiv":1,"external_id":{"arxiv":["2502.12872"]},"acknowledgement":"This work is a part of project VAMOS that has received funding from the European Research Council (ERC), grant agreement No 101020093.","has_accepted_license":"1","file":[{"file_id":"20305","date_updated":"2025-09-08T06:56:56Z","creator":"dernst","content_type":"application/pdf","date_created":"2025-09-08T06:56:56Z","access_level":"open_access","relation":"main_file","file_name":"2025_MFCS_HenzingerT.pdf","success":1,"checksum":"6068b772aba6cb0d01f3e5a90abed973","file_size":1009644}]},{"article_processing_charge":"No","ddc":["000"],"scopus_import":"1","date_updated":"2025-10-27T08:00:13Z","type":"conference","publication":"33rd Annual European Symposium on Algorithms","publication_status":"published","doi":"10.4230/LIPIcs.ESA.2025.2","file_date_updated":"2025-10-27T07:57:00Z","corr_author":"1","abstract":[{"text":"We give an introduction into differential privacy in the dynamic setting, called the continual observation setting.","lang":"eng"}],"language":[{"iso":"eng"}],"article_number":"2","volume":351,"title":"Securing dynamic data: A primer on differentially private data structures","year":"2025","alternative_title":["LIPIcs"],"OA_type":"gold","conference":{"start_date":"2025-09-15","location":"Warsaw, Poland","end_date":"2025-09-17","name":"ESA: European Symposium on Algorithms"},"day":"01","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"status":"public","month":"10","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"ama":"Henzinger M, Safavi Hemami R. Securing dynamic data: A primer on differentially private data structures. In: <i>33rd Annual European Symposium on Algorithms</i>. Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.2\">10.4230/LIPIcs.ESA.2025.2</a>","ieee":"M. Henzinger and R. Safavi Hemami, “Securing dynamic data: A primer on differentially private data structures,” in <i>33rd Annual European Symposium on Algorithms</i>, Warsaw, Poland, 2025, vol. 351.","apa":"Henzinger, M., &#38; Safavi Hemami, R. (2025). Securing dynamic data: A primer on differentially private data structures. In <i>33rd Annual European Symposium on Algorithms</i> (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.2\">https://doi.org/10.4230/LIPIcs.ESA.2025.2</a>","chicago":"Henzinger, Monika, and Roodabeh Safavi Hemami. “Securing Dynamic Data: A Primer on Differentially Private Data Structures.” In <i>33rd Annual European Symposium on Algorithms</i>, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.2\">https://doi.org/10.4230/LIPIcs.ESA.2025.2</a>.","ista":"Henzinger M, Safavi Hemami R. 2025. Securing dynamic data: A primer on differentially private data structures. 33rd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 351, 2.","mla":"Henzinger, Monika, and Roodabeh Safavi Hemami. “Securing Dynamic Data: A Primer on Differentially Private Data Structures.” <i>33rd Annual European Symposium on Algorithms</i>, vol. 351, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.2\">10.4230/LIPIcs.ESA.2025.2</a>.","short":"M. Henzinger, R. Safavi Hemami, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025."},"date_created":"2025-10-26T23:01:34Z","department":[{"_id":"MoHe"}],"intvolume":"       351","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773959"]},"_id":"20533","date_published":"2025-10-01T00:00:00Z","quality_controlled":"1","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger"},{"last_name":"Safavi Hemami","first_name":"Roodabeh","full_name":"Safavi Hemami, Roodabeh","id":"72ed2640-8972-11ed-ae7b-f9c81ec75154"}],"OA_place":"publisher","has_accepted_license":"1","file":[{"creator":"dernst","content_type":"application/pdf","file_id":"20541","date_updated":"2025-10-27T07:57:00Z","checksum":"094e0466d90664fbea397b469a60acbb","success":1,"file_size":770227,"file_name":"2025_LIPIcs.ESA_Henzinger.pdf","date_created":"2025-10-27T07:57:00Z","relation":"main_file","access_level":"open_access"}]},{"file":[{"creator":"dernst","content_type":"application/pdf","date_updated":"2025-10-27T08:03:36Z","file_id":"20542","file_size":934846,"success":1,"checksum":"d2daf9a467e96fb5e7084a8a85321776","file_name":"2025_LIPIcs.ESA_HenzingerM.pdf","date_created":"2025-10-27T08:03:36Z","relation":"main_file","access_level":"open_access"}],"acknowledgement":"Monika Henzinger and Evangelos Kosinas: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant https://www.doi.org/10.55776/Z422 and grant https://www.doi.org/10.55776/I5982. Harald Räcke and Robin Münk: This project has received funding from the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 498605858.","has_accepted_license":"1","external_id":{"arxiv":["2509.05157"]},"arxiv":1,"author":[{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Kosinas","first_name":"Evangelos","id":"4c7f9625-dbbc-11ee-9d86-bdcc2db5a949","full_name":"Kosinas, Evangelos"},{"full_name":"Münk, Robin","first_name":"Robin","last_name":"Münk"},{"first_name":"Harald","last_name":"Räcke","full_name":"Räcke, Harald"}],"OA_place":"publisher","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","date_published":"2025-10-01T00:00:00Z","project":[{"call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564"},{"grant_number":"Z00422","name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982"}],"quality_controlled":"1","_id":"20534","publication_identifier":{"isbn":["9783959773959"],"issn":["1868-8969"]},"intvolume":"       351","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"apa":"Henzinger, M., Kosinas, E., Münk, R., &#38; Räcke, H. (2025). Efficient contractions of dynamic graphs - with applications. In <i>33rd Annual European Symposium on Algorithms</i> (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.36\">https://doi.org/10.4230/LIPIcs.ESA.2025.36</a>","ieee":"M. Henzinger, E. Kosinas, R. Münk, and H. Räcke, “Efficient contractions of dynamic graphs - with applications,” in <i>33rd Annual European Symposium on Algorithms</i>, Warsaw, Poland, 2025, vol. 351.","ama":"Henzinger M, Kosinas E, Münk R, Räcke H. Efficient contractions of dynamic graphs - with applications. In: <i>33rd Annual European Symposium on Algorithms</i>. Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.36\">10.4230/LIPIcs.ESA.2025.36</a>","chicago":"Henzinger, Monika, Evangelos Kosinas, Robin Münk, and Harald Räcke. “Efficient Contractions of Dynamic Graphs - with Applications.” In <i>33rd Annual European Symposium on Algorithms</i>, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.36\">https://doi.org/10.4230/LIPIcs.ESA.2025.36</a>.","ista":"Henzinger M, Kosinas E, Münk R, Räcke H. 2025. Efficient contractions of dynamic graphs - with applications. 33rd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms vol. 351, 36.","mla":"Henzinger, Monika, et al. “Efficient Contractions of Dynamic Graphs - with Applications.” <i>33rd Annual European Symposium on Algorithms</i>, vol. 351, 36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.36\">10.4230/LIPIcs.ESA.2025.36</a>.","short":"M. Henzinger, E. Kosinas, R. Münk, H. Räcke, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025."},"department":[{"_id":"MoHe"}],"date_created":"2025-10-26T23:01:34Z","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"month":"10","status":"public","year":"2025","title":"Efficient contractions of dynamic graphs - with applications","volume":351,"oa":1,"day":"01","OA_type":"gold","conference":{"location":"Warsaw, Poland","name":"ESA: European Symposium on Algorithms","end_date":"2025-09-17","start_date":"2025-09-15"},"abstract":[{"text":"A non-trivial minimum cut (NMC) sparsifier is a multigraph Ĝ that preserves all non-trivial minimum cuts of a given undirected graph G. We introduce a flexible data structure for fully dynamic graphs that can efficiently provide an NMC sparsifier upon request at any point during the sequence of updates. We employ simple dynamic forest data structures to achieve a fast from-scratch construction of the sparsifier at query time. Based on the strength of the adversary and desired type of time bounds, the data structure comes with different guarantees. Specifically, let G be a fully dynamic simple graph with n vertices and minimum degree δ. Then our data structure supports an insertion/deletion of an edge to/from G in n^o(1) worst-case time. Furthermore, upon request, it can return w.h.p. an NMC sparsifier of G that has O(n/δ) vertices and O(n) edges, in Ô(n) time. The probabilistic guarantees hold against an adaptive adversary. Alternatively, the update and query times can be improved to Õ(1) and Õ(n) respectively, if amortized-time guarantees are sufficient, or if the adversary is oblivious. Throughout the paper, we use Õ to hide polylogarithmic factors and Ô to hide subpolynomial (i.e., n^o(1)) factors.\r\nWe discuss two applications of our new data structure. First, it can be used to efficiently report a cactus representation of all minimum cuts of a fully dynamic simple graph. Building this cactus for the NMC sparsifier instead of the original graph allows for a construction time that is sublinear in the number of edges. Against an adaptive adversary, we can with high probability output the cactus representation in worst-case Ô(n) time. Second, our data structure allows us to efficiently compute the maximal k-edge-connected subgraphs of undirected simple graphs, by repeatedly applying a minimum cut algorithm on the NMC sparsifier. Specifically, we can compute with high probability the maximal k-edge-connected subgraphs of a simple graph with n vertices and m edges in Õ(m+n²/k) time. This improves the best known time bounds for k = Ω(n^{1/8}) and naturally extends to the case of fully dynamic graphs.","lang":"eng"}],"corr_author":"1","language":[{"iso":"eng"}],"article_number":"36","ec_funded":1,"file_date_updated":"2025-10-27T08:03:36Z","publication_status":"published","doi":"10.4230/LIPIcs.ESA.2025.36","type":"conference","publication":"33rd Annual European Symposium on Algorithms","date_updated":"2025-10-27T08:05:46Z","scopus_import":"1","ddc":["000"],"article_processing_charge":"No"},{"OA_type":"gold","conference":{"location":"Warsaw, Poland","end_date":"2025-09-17","name":"ESA: European Symposium on Algorithms","start_date":"2025-09-15"},"day":"01","oa":1,"title":"Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism","volume":351,"alternative_title":["LIPIcs"],"year":"2025","language":[{"iso":"eng"}],"article_number":"91","abstract":[{"text":"Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the k-core decomposition problem, the classic peeling algorithm iteratively removes a vertex if its induced degree falls below a threshold. The sparse vector technique (SVT) is generally used to transform non-private threshold queries into private ones with only a small additive loss in accuracy. However, a naive application of SVT in the graph setting leads to an amplification of the error by a factor of n due to composition, as SVT is applied to every vertex. In this paper, we resolve this problem by formulating a novel generalized sparse vector technique which we call the Multidimensional AboveThreshold (MAT) Mechanism which generalizes SVT (applied to vectors with one dimension) to vectors with multiple dimensions. When applied to vectors with n dimensions, we solve a number of important graph problems with better bounds than previous work.\r\nSpecifically, we apply our MAT mechanism to obtain a set of improved bounds for a variety of problems including k-core decomposition, densest subgraph, low out-degree ordering, and vertex coloring. We give a tight local edge differentially private (LEDP) algorithm for k-core decomposition that results in an approximation with O(ε^{-1} log n) additive error and no multiplicative error in O(n) rounds. We also give a new (2+η)-factor multiplicative, O(ε^{-1} log n) additive error algorithm in O(log² n) rounds for any constant η > 0. Both of these results are asymptotically tight against our new lower bound of Ω(log n) for any constant-factor approximation algorithm for k-core decomposition. Our new algorithms for k-core decomposition also directly lead to new algorithms for the related problems of densest subgraph and low out-degree ordering. Finally, we give novel LEDP differentially private defective coloring algorithms that use number of colors given in terms of the arboricity of the graph.","lang":"eng"}],"corr_author":"1","file_date_updated":"2025-10-27T06:58:43Z","ec_funded":1,"doi":"10.4230/LIPIcs.ESA.2025.91","publication_status":"published","date_updated":"2025-10-27T07:02:06Z","type":"conference","publication":"33rd Annual European Symposium on Algorithms","ddc":["000"],"scopus_import":"1","article_processing_charge":"No","has_accepted_license":"1","acknowledgement":"Monika Henzinger and A. R. Sricharan: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation\r\nprogramme (MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant DOI\r\n10.55776/Z422 and grant DOI 10.55776/I5982. Laxman Dhulipala and George Z. Li: supported by NSF award number CNS-2317194. Quanquan C. Liu: supported by a Google Academic Research Award and by an NSF award number CCF-2453323.","file":[{"access_level":"open_access","relation":"main_file","date_created":"2025-10-27T06:58:43Z","file_name":"2025_LIPIcs.ESA_Dhulipala.pdf","success":1,"file_size":870317,"checksum":"19146e935b5b6ad5d33c8d08280ad8e7","file_id":"20539","date_updated":"2025-10-27T06:58:43Z","content_type":"application/pdf","creator":"dernst"}],"OA_place":"publisher","author":[{"full_name":"Dhulipala, Laxman","first_name":"Laxman","last_name":"Dhulipala"},{"last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"last_name":"Li","first_name":"George Z.","full_name":"Li, George Z."},{"first_name":"Quanquan C.","last_name":"Liu","full_name":"Liu, Quanquan C."},{"full_name":"Sricharan, A. R.","last_name":"Sricharan","first_name":"A. R."},{"first_name":"Leqi","last_name":"Zhu","id":"a2117c59-cee4-11ed-b9d0-874ecf0f8ac5","full_name":"Zhu, Leqi"}],"external_id":{"arxiv":["2508.02182"]},"arxiv":1,"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","project":[{"call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms","grant_number":"Z00422"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982"}],"date_published":"2025-10-01T00:00:00Z","intvolume":"       351","publication_identifier":{"isbn":["9783959773959"],"issn":["1868-8969"]},"_id":"20535","date_created":"2025-10-26T23:01:35Z","department":[{"_id":"MoHe"}],"citation":{"apa":"Dhulipala, L., Henzinger, M., Li, G. Z., Liu, Q. C., Sricharan, A. R., &#38; Zhu, L. (2025). Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism. In <i>33rd Annual European Symposium on Algorithms</i> (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.91\">https://doi.org/10.4230/LIPIcs.ESA.2025.91</a>","ama":"Dhulipala L, Henzinger M, Li GZ, Liu QC, Sricharan AR, Zhu L. Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism. In: <i>33rd Annual European Symposium on Algorithms</i>. Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.91\">10.4230/LIPIcs.ESA.2025.91</a>","ieee":"L. Dhulipala, M. Henzinger, G. Z. Li, Q. C. Liu, A. R. Sricharan, and L. Zhu, “Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism,” in <i>33rd Annual European Symposium on Algorithms</i>, Warsaw, Poland, 2025, vol. 351.","chicago":"Dhulipala, Laxman, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, and Leqi Zhu. “Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism.” In <i>33rd Annual European Symposium on Algorithms</i>, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.91\">https://doi.org/10.4230/LIPIcs.ESA.2025.91</a>.","short":"L. Dhulipala, M. Henzinger, G.Z. Li, Q.C. Liu, A.R. Sricharan, L. Zhu, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","mla":"Dhulipala, Laxman, et al. “Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism.” <i>33rd Annual European Symposium on Algorithms</i>, vol. 351, 91, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2025.91\">10.4230/LIPIcs.ESA.2025.91</a>.","ista":"Dhulipala L, Henzinger M, Li GZ, Liu QC, Sricharan AR, Zhu L. 2025. Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism. 33rd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 351, 91."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","status":"public","month":"10","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"}},{"OA_place":"publisher","author":[{"id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","full_name":"Safavi Hemami, Roodabeh","first_name":"Roodabeh","last_name":"Safavi Hemami"},{"full_name":"Seybold, Martin P.","last_name":"Seybold","first_name":"Martin P."}],"arxiv":1,"external_id":{"arxiv":["2303.04722"]},"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","has_accepted_license":"1","acknowledgement":"This work was supported under the Australian Research Council Discovery Projects\r\nfunding scheme (project number DP180102870). This project has received funding from the\r\nEuropean Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564) “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project Z 422-N and project “Fast Algorithms for a Reactive Network Layer (ReactNet)” P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.","file":[{"creator":"dernst","content_type":"application/pdf","date_updated":"2025-10-27T07:09:41Z","file_id":"20540","file_name":"2025_LIPIcs.WADS_Safavi.pdf","success":1,"checksum":"196af33762831a78e87f4f95ecd8677b","file_size":1081870,"date_created":"2025-10-27T07:09:41Z","access_level":"open_access","relation":"main_file"}],"department":[{"_id":"MoHe"}],"date_created":"2025-10-26T23:01:35Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"chicago":"Safavi Hemami, Roodabeh, and Martin P. Seybold. “B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load.” In <i>19th International Symposium on Algorithms and Data Structures</i>, Vol. 349. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.WADS.2025.47\">https://doi.org/10.4230/LIPIcs.WADS.2025.47</a>.","ista":"Safavi Hemami R, Seybold MP. 2025. B-Treaps revised: Write efficient randomized block search trees with high load. 19th International Symposium on Algorithms and Data Structures. WADS: Algorithms and Data Structures Symposium, LIPIcs, vol. 349, 47.","mla":"Safavi Hemami, Roodabeh, and Martin P. Seybold. “B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load.” <i>19th International Symposium on Algorithms and Data Structures</i>, vol. 349, 47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.WADS.2025.47\">10.4230/LIPIcs.WADS.2025.47</a>.","short":"R. Safavi Hemami, M.P. Seybold, in:, 19th International Symposium on Algorithms and Data Structures, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","apa":"Safavi Hemami, R., &#38; Seybold, M. P. (2025). B-Treaps revised: Write efficient randomized block search trees with high load. In <i>19th International Symposium on Algorithms and Data Structures</i> (Vol. 349). Toronto, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.WADS.2025.47\">https://doi.org/10.4230/LIPIcs.WADS.2025.47</a>","ama":"Safavi Hemami R, Seybold MP. B-Treaps revised: Write efficient randomized block search trees with high load. In: <i>19th International Symposium on Algorithms and Data Structures</i>. Vol 349. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.WADS.2025.47\">10.4230/LIPIcs.WADS.2025.47</a>","ieee":"R. Safavi Hemami and M. P. Seybold, “B-Treaps revised: Write efficient randomized block search trees with high load,” in <i>19th International Symposium on Algorithms and Data Structures</i>, Toronto, Canada, 2025, vol. 349."},"status":"public","month":"08","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"quality_controlled":"1","project":[{"call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564"},{"grant_number":"Z00422","name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775"}],"date_published":"2025-08-29T00:00:00Z","intvolume":"       349","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773980"]},"_id":"20536","file_date_updated":"2025-10-27T07:09:41Z","ec_funded":1,"doi":"10.4230/LIPIcs.WADS.2025.47","publication_status":"published","OA_type":"gold","conference":{"start_date":"2025-08-11","location":"Toronto, Canada","end_date":"2025-08-15","name":"WADS: Algorithms and Data Structures Symposium"},"day":"29","oa":1,"volume":349,"title":"B-Treaps revised: Write efficient randomized block search trees with high load","alternative_title":["LIPIcs"],"year":"2025","article_number":"47","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"Uniquely represented (UR) data structures represent each logical state with a unique storage state. We study the problem of maintaining a dynamic set of n keys from a totally ordered universe in this context. UR structures are also called \"strongly history independent\" structures in the literature.\r\nWe introduce a two-layer data structure called (α,ε)-Randomized Block Search Tree (RBST) that is uniquely represented and suitable for external memory (EM). Though RBSTs naturally generalize the well-known binary Treaps, several new ideas are needed to analyze the expected search, update, and storage efficiency in terms of block-reads, block-writes, and blocks stored. We prove that searches have O(ε^{-1} + log_α n) block-reads, that dynamic updates perform O(ε^{-1} + log_α(n)/α) block-writes and O(ε^{-2}+(1+(ε^{-1}+log n)/α)log_α n) block-reads, and that (α, ε)-RBSTs have an asymptotic load-factor of at least (1-ε) for every ε ∈ (0,1/2].\r\nThus (α, ε)-RBSTs improve on the known, uniquely represented B-Treap [Golovin; ICALP'09]. Compared with non-UR structures, the RBST is also, to the best of our knowledge, the first external memory structure that is storage-efficient and has a non-amortized, write-efficient update bound."}],"corr_author":"1","article_processing_charge":"No","date_updated":"2025-10-27T07:10:49Z","type":"conference","publication":"19th International Symposium on Algorithms and Data Structures","ddc":["000"],"scopus_import":"1"},{"year":"2025","alternative_title":["LIPIcs"],"title":"Tight bounds on list-decodable and list-recoverable zero-rate codes","volume":325,"oa":1,"OA_type":"gold","day":"11","conference":{"start_date":"2025-01-07","location":"New York, NY, United States","end_date":"2025-01-10","name":"ITCS: Innovations in Theoretical Computer Science"},"corr_author":"1","abstract":[{"lang":"eng","text":"In this work, we consider the list-decodability and list-recoverability of codes in the zero-rate regime. Briefly, a code 𝒞 ⊆ [q]ⁿ is (p,𝓁,L)-list-recoverable if for all tuples of input lists (Y₁,… ,Y_n) with each Y_i ⊆ [q] and |Y_i| = 𝓁, the number of codewords c ∈ 𝒞 such that c_i ∉ Y_i for at most pn choices of i ∈ [n] is less than L; list-decoding is the special case of 𝓁 = 1. In recent work by Resch, Yuan and Zhang (ICALP 2023) the zero-rate threshold for list-recovery was determined for all parameters: that is, the work explicitly computes p_*: = p_*(q,𝓁,L) with the property that for all ε > 0 (a) there exist positive-rate (p_*-ε,𝓁,L)-list-recoverable codes, and (b) any (p_*+ε,𝓁,L)-list-recoverable code has rate 0. In fact, in the latter case the code has constant size, independent on n. However, the constant size in their work is quite large in 1/ε, at least |𝒞| ≥ (1/(ε))^O(q^L).\r\nOur contribution in this work is to show that for all choices of q,𝓁 and L with q ≥ 3, any (p_*+ε,𝓁,L)-list-recoverable code must have size O_{q,𝓁,L}(1/ε), and furthermore this upper bound is complemented by a matching lower bound Ω_{q,𝓁,L}(1/ε). This greatly generalizes work by Alon, Bukh and Polyanskiy (IEEE Trans. Inf. Theory 2018) which focused only on the case of binary alphabet (and thus necessarily only list-decoding). We remark that we can in fact recover the same result for q = 2 and even L, as obtained by Alon, Bukh and Polyanskiy: we thus strictly generalize their work. \r\nOur main technical contribution is to (a) properly define a linear programming relaxation of the list-recovery condition over large alphabets; and (b) to demonstrate that a certain function defined on a q-ary probability simplex is maximized by the uniform distribution. This represents the core challenge in generalizing to larger q (as a binary simplex can be naturally identified with a one-dimensional interval). We can subsequently re-utilize certain Schur convexity and convexity properties established for a related function by Resch, Yuan and Zhang along with ideas of Alon, Bukh and Polyanskiy."}],"article_number":"82","language":[{"iso":"eng"}],"file_date_updated":"2025-03-04T09:35:57Z","publication_status":"published","doi":"10.4230/LIPIcs.ITCS.2025.82","type":"conference","publication":"16th Innovations in Theoretical Computer Science Conference","date_updated":"2025-09-30T10:42:35Z","scopus_import":"1","ddc":["510","000"],"article_processing_charge":"Yes","file":[{"creator":"dernst","content_type":"application/pdf","file_id":"19286","date_updated":"2025-03-04T09:35:57Z","checksum":"df3921ddf1b360b07f43d427fea51242","file_size":898601,"success":1,"file_name":"2025_LIPIcs_Resch.pdf","date_created":"2025-03-04T09:35:57Z","relation":"main_file","access_level":"open_access"}],"has_accepted_license":"1","acknowledgement":"The research of C. Yuan was support in part by the National Key R&D Program of China\r\nunder Grant 2023YFE0123900 and Natural Science Foundation of Shanghai under the 2024 Shanghai Action Plan for Science, Technology and Innovation Grant 24BC3200700. The research of N. Resch is supported in part by an NWO (Dutch Research Council) grant with number C.2324.0590, and this work was done in part while he was visiting the Simons Institute for the Theory of Computing, supported by DOE grant #DE-SC0024124.","external_id":{"arxiv":["2309.01800"],"isi":["001532717300082"]},"arxiv":1,"author":[{"full_name":"Resch, Nicolas","first_name":"Nicolas","last_name":"Resch"},{"full_name":"Yuan, Chen","first_name":"Chen","last_name":"Yuan"},{"first_name":"Yihan","last_name":"Zhang","full_name":"Zhang, Yihan","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","orcid":"0000-0002-6465-6258"}],"OA_place":"publisher","isi":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa_version":"Published Version","date_published":"2025-02-11T00:00:00Z","quality_controlled":"1","_id":"19281","publication_identifier":{"isbn":["9783959773614"],"issn":["1868-8969"]},"intvolume":"       325","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"ama":"Resch N, Yuan C, Zhang Y. Tight bounds on list-decodable and list-recoverable zero-rate codes. In: <i>16th Innovations in Theoretical Computer Science Conference</i>. Vol 325. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.82\">10.4230/LIPIcs.ITCS.2025.82</a>","apa":"Resch, N., Yuan, C., &#38; Zhang, Y. (2025). Tight bounds on list-decodable and list-recoverable zero-rate codes. In <i>16th Innovations in Theoretical Computer Science Conference</i> (Vol. 325). New York, NY, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.82\">https://doi.org/10.4230/LIPIcs.ITCS.2025.82</a>","ieee":"N. Resch, C. Yuan, and Y. Zhang, “Tight bounds on list-decodable and list-recoverable zero-rate codes,” in <i>16th Innovations in Theoretical Computer Science Conference</i>, New York, NY, United States, 2025, vol. 325.","chicago":"Resch, Nicolas, Chen Yuan, and Yihan Zhang. “Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes.” In <i>16th Innovations in Theoretical Computer Science Conference</i>, Vol. 325. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.82\">https://doi.org/10.4230/LIPIcs.ITCS.2025.82</a>.","short":"N. Resch, C. Yuan, Y. Zhang, in:, 16th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","mla":"Resch, Nicolas, et al. “Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes.” <i>16th Innovations in Theoretical Computer Science Conference</i>, vol. 325, 82, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2025.82\">10.4230/LIPIcs.ITCS.2025.82</a>.","ista":"Resch N, Yuan C, Zhang Y. 2025. Tight bounds on list-decodable and list-recoverable zero-rate codes. 16th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 325, 82."},"department":[{"_id":"MaMo"}],"date_created":"2025-03-02T23:01:53Z","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"month":"02","status":"public"},{"status":"public","month":"10","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"department":[{"_id":"KrCh"}],"date_created":"2026-03-08T23:01:46Z","citation":{"chicago":"Chatterjee, Krishnendu, Jan Matyáš Křišťan, Stefan Schmid, Jakub Svoboda, and Michelle X Yeo. “Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection.” In <i>39th International Symposium on Distributed Computing</i>, Vol. 356. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2025.23\">https://doi.org/10.4230/LIPIcs.DISC.2025.23</a>.","short":"K. Chatterjee, J.M. Křišťan, S. Schmid, J. Svoboda, M.X. Yeo, in:, 39th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","mla":"Chatterjee, Krishnendu, et al. “Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection.” <i>39th International Symposium on Distributed Computing</i>, vol. 356, 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2025.23\">10.4230/LIPIcs.DISC.2025.23</a>.","ista":"Chatterjee K, Křišťan JM, Schmid S, Svoboda J, Yeo MX. 2025. Boosting payment channel network liquidity with topology optimization and transaction selection. 39th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 356, 23.","ieee":"K. Chatterjee, J. M. Křišťan, S. Schmid, J. Svoboda, and M. X. Yeo, “Boosting payment channel network liquidity with topology optimization and transaction selection,” in <i>39th International Symposium on Distributed Computing</i>, Berlin, Germany, 2025, vol. 356.","ama":"Chatterjee K, Křišťan JM, Schmid S, Svoboda J, Yeo MX. Boosting payment channel network liquidity with topology optimization and transaction selection. In: <i>39th International Symposium on Distributed Computing</i>. Vol 356. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2025.23\">10.4230/LIPIcs.DISC.2025.23</a>","apa":"Chatterjee, K., Křišťan, J. M., Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2025). Boosting payment channel network liquidity with topology optimization and transaction selection. In <i>39th International Symposium on Distributed Computing</i> (Vol. 356). Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2025.23\">https://doi.org/10.4230/LIPIcs.DISC.2025.23</a>"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","intvolume":"       356","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959774024"]},"_id":"21412","project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"}],"quality_controlled":"1","date_published":"2025-10-22T00:00:00Z","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_place":"publisher","author":[{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"first_name":"Jan Matyáš","last_name":"Křišťan","full_name":"Křišťan, Jan Matyáš"},{"last_name":"Schmid","first_name":"Stefan","full_name":"Schmid, Stefan"},{"last_name":"Svoboda","first_name":"Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","orcid":"0000-0002-1419-3267","full_name":"Svoboda, Jakub"},{"last_name":"Yeo","first_name":"Michelle X","full_name":"Yeo, Michelle X","orcid":"0009-0001-3676-4809","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"external_id":{"arxiv":["2508.14524"]},"arxiv":1,"acknowledgement":"Chatterjee, Krishnendu: European Research Council CoG 863818 (ForM-SMArt) and Austrian Science Fund 10.55776/COE12.\r\nKřišťan, Jan Matyáš: Czech Science Foundation Grant no. 24-12046S.\r\nSchmid, Stefan: German Research Foundation (DFG) project ReNO (SPP 2378) from 2023-2027.\r\nSvoboda, Jakub: European Research Council CoG 863818 (ForM-SMArt) and Austrian Science Fund 10.55776/COE12.\r\nYeo, Michelle: MOE-T2EP20122-0014 (Data-Driven Distributed Algorithms).","has_accepted_license":"1","file":[{"creator":"dernst","content_type":"application/pdf","date_updated":"2026-03-09T11:51:59Z","file_id":"21418","file_name":"2025_DISC_Chatterjee.pdf","success":1,"file_size":1130069,"checksum":"8e3d1594365df60163d9df22158a37b1","date_created":"2026-03-09T11:51:59Z","access_level":"open_access","relation":"main_file"}],"article_processing_charge":"No","ddc":["000"],"scopus_import":"1","date_updated":"2026-03-09T11:52:58Z","type":"conference","publication":"39th International Symposium on Distributed Computing","doi":"10.4230/LIPIcs.DISC.2025.23","publication_status":"published","file_date_updated":"2026-03-09T11:51:59Z","ec_funded":1,"main_file_link":[{"url":"https://eprint.iacr.org/2025/1484.pdf","open_access":"1"}],"article_number":"23","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"Payment channel networks (PCNs) are a promising technology that alleviates blockchain scalability by shifting the transaction load from the blockchain to the PCN. Nevertheless, the network topology has to be carefully designed to maximise the transaction throughput in PCNs. Additionally, users in PCNs also have to make optimal decisions on which transactions to forward and which to reject to prolong the lifetime of their channels. In this work, we consider an input sequence of transactions over p parties. Each transaction consists of a transaction size, source, and target, and can be either accepted or rejected (entailing a cost). The goal is to design a PCN topology among the p cooperating parties, along with the channel capacities, and then output a decision for each transaction in the sequence to minimise the cost of creating and augmenting channels, as well as the cost of rejecting transactions. Our main contribution is an 𝒪(p) approximation algorithm for the problem with p parties. We further show that with some assumptions on the distribution of transactions, we can reduce the approximation ratio to 𝒪(√p). We complement our theoretical analysis with an empirical study of our assumptions and approach in the context of the Lightning Network."}],"OA_type":"gold","conference":{"end_date":"2025-10-31","name":"DISC: Symposium on Distributed Computing","location":"Berlin, Germany","start_date":"2025-10-27"},"day":"22","oa":1,"volume":356,"title":"Boosting payment channel network liquidity with topology optimization and transaction selection","year":"2025","alternative_title":["LIPIcs"]},{"article_processing_charge":"Yes","date_updated":"2026-04-15T08:45:18Z","publication":"7th Conference on Advances in Financial Technologies","type":"conference","ddc":["000"],"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2025/1410"}],"file_date_updated":"2025-11-04T08:19:02Z","publication_status":"published","doi":"10.4230/LIPIcs.AFT.2025.16","title":"Nakamoto consensus from multiple resources","volume":354,"year":"2025","alternative_title":["LIPIcs"],"OA_type":"gold","day":"06","conference":{"start_date":"2025-10-08","end_date":"2025-10-10","name":"AFT: Conference on Advances in Financial Technologies","location":"Pittsburgh, PA, United States"},"oa":1,"corr_author":"1","abstract":[{"text":"The blocks in the Bitcoin blockchain \"record\" the amount of work W that went into creating them through proofs of work. When honest parties control a majority of the work, consensus is achieved by picking the chain with the highest recorded weight. Resources other than work have been considered to secure such longest-chain blockchains. In Chia, blocks record the amount of disk-space S (via a proof of space) and sequential computational steps V (through a VDF).\r\nIn this paper, we ask what weight functions Γ(S,V,W) (that assign a weight to a block as a function of the recorded space, speed, and work) are secure in the sense that whenever the weight of the resources controlled by honest parties is larger than the weight of adversarial parties, the blockchain is secure against private double-spending attacks.\r\nWe completely classify such functions in an idealized \"continuous\" model: Γ(S,V,W) is secure against private double-spending attacks if and only if it is homogeneous of degree one in the \"timed\" resources V and W, i.e., αΓ(S,V,W) = Γ(S,α V, α W). This includes the Bitcoin rule Γ(S,V,W) = W and the Chia rule Γ(S,V,W) = S ⋅ V. In a more realistic model where blocks are created at discrete time-points, one additionally needs some mild assumptions on the dependency on S (basically, the weight should not grow too much if S is slightly increased, say linear as in Chia).\r\nOur classification is more general and allows various instantiations of the same resource. It provides a powerful tool for designing new longest-chain blockchains. E.g., consider combining different PoWs to counter centralization, say the Bitcoin PoW W₁ and a memory-hard PoW W₂. Previous work suggested to use W₁+W₂ as weight. Our results show that using e.g., √{W₁}⋅ √{W₂} or min{W₁,W₂} are also secure, and we argue that in practice these are much better choices.","lang":"eng"}],"article_number":"16","language":[{"iso":"eng"}],"citation":{"apa":"Baig, M. A., Günther, C. U., &#38; Pietrzak, K. Z. (2025). Nakamoto consensus from multiple resources. In <i>7th Conference on Advances in Financial Technologies</i> (Vol. 354). Pittsburgh, PA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.AFT.2025.16\">https://doi.org/10.4230/LIPIcs.AFT.2025.16</a>","ama":"Baig MA, Günther CU, Pietrzak KZ. Nakamoto consensus from multiple resources. In: <i>7th Conference on Advances in Financial Technologies</i>. Vol 354. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.AFT.2025.16\">10.4230/LIPIcs.AFT.2025.16</a>","ieee":"M. A. Baig, C. U. Günther, and K. Z. Pietrzak, “Nakamoto consensus from multiple resources,” in <i>7th Conference on Advances in Financial Technologies</i>, Pittsburgh, PA, United States, 2025, vol. 354.","chicago":"Baig, Mirza Ahad, Christoph Ullrich Günther, and Krzysztof Z Pietrzak. “Nakamoto Consensus from Multiple Resources.” In <i>7th Conference on Advances in Financial Technologies</i>, Vol. 354. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.AFT.2025.16\">https://doi.org/10.4230/LIPIcs.AFT.2025.16</a>.","short":"M.A. Baig, C.U. Günther, K.Z. Pietrzak, in:, 7th Conference on Advances in Financial Technologies, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","mla":"Baig, Mirza Ahad, et al. “Nakamoto Consensus from Multiple Resources.” <i>7th Conference on Advances in Financial Technologies</i>, vol. 354, 16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.AFT.2025.16\">10.4230/LIPIcs.AFT.2025.16</a>.","ista":"Baig MA, Günther CU, Pietrzak KZ. 2025. Nakamoto consensus from multiple resources. 7th Conference on Advances in Financial Technologies. AFT: Conference on Advances in Financial Technologies, LIPIcs, vol. 354, 16."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_created":"2025-11-02T23:01:34Z","department":[{"_id":"KrPi"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"status":"public","month":"10","date_published":"2025-10-06T00:00:00Z","quality_controlled":"1","project":[{"name":"Security and Privacy by Design for Complex Systems","_id":"34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f","grant_number":"F8512"},{"_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1","name":"Security and Privacy by Design for Complex Systems","grant_number":"F8509"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959774000"]},"intvolume":"       354","_id":"20587","author":[{"last_name":"Baig","first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","full_name":"Baig, Mirza Ahad"},{"last_name":"Günther","first_name":"Christoph Ullrich","full_name":"Günther, Christoph Ullrich","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1"},{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z"}],"arxiv":1,"external_id":{"arxiv":["2508.01448"]},"OA_place":"publisher","oa_version":"Published Version","related_material":{"record":[{"relation":"dissertation_contains","id":"21651","status":"public"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"This research was funded in whole or in part by the Austrian Science Fund (FWF)\r\n10.55776/F85. For open access purposes, the author has applied a CC BY public copyright license\r\nto any author-accepted manuscript version arising from this submission.","has_accepted_license":"1","file":[{"file_id":"20598","date_updated":"2025-11-04T08:19:02Z","creator":"dernst","content_type":"application/pdf","date_created":"2025-11-04T08:19:02Z","access_level":"open_access","relation":"main_file","file_name":"2025_LIPIcsAFT_Baig.pdf","file_size":1061847,"checksum":"b638adcd4fbffa77116c35393e165eb7","success":1}]},{"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"}],"corr_author":"1","article_number":"8","language":[{"iso":"eng"}],"alternative_title":["LIPIcs"],"year":"2024","title":"Bidding games with charging","volume":311,"oa":1,"day":"01","conference":{"end_date":"2024-09-13","location":"Calgary, Canada","name":"CONCUR: Conference on Concurrency Theory","start_date":"2024-09-09"},"publication_status":"published","doi":"10.4230/LIPIcs.CONCUR.2024.8","ec_funded":1,"file_date_updated":"2024-09-17T09:35:03Z","scopus_import":"1","ddc":["000"],"publication":"35th International Conference on Concurrency Theory","type":"conference","date_updated":"2025-12-02T13:46:11Z","article_processing_charge":"Yes","file":[{"creator":"dernst","content_type":"application/pdf","file_id":"18083","date_updated":"2024-09-17T09:35:03Z","file_name":"2024_LIPICS_Avni.pdf","success":1,"file_size":854430,"checksum":"cb6f2254b84922cd7bf224f550b73f4a","date_created":"2024-09-17T09:35:03Z","access_level":"open_access","relation":"main_file"}],"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.","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","arxiv":1,"external_id":{"isi":["001556847400008"],"arxiv":["2407.06288"]},"author":[{"id":"463C8BC2-F248-11E8-B48F-1D18A9856A87","full_name":"Avni, Guy","orcid":"0000-0001-5588-8287","first_name":"Guy","last_name":"Avni"},{"full_name":"Goharshady, Ehsan Kafshdar","last_name":"Goharshady","first_name":"Ehsan Kafshdar"},{"last_name":"Henzinger","first_name":"Thomas A","orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A"},{"last_name":"Mallik","first_name":"Kaushik","orcid":"0000-0001-9864-7475","id":"0834ff3c-6d72-11ec-94e0-b5b0a4fb8598","full_name":"Mallik, Kaushik"}],"isi":1,"_id":"18066","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773393"]},"intvolume":"       311","date_published":"2024-09-01T00:00:00Z","project":[{"call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software","grant_number":"101020093"},{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"}],"quality_controlled":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"month":"09","status":"public","citation":{"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>","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>","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.","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.","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>.","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>."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"ToHe"}],"date_created":"2024-09-15T22:01:39Z"},{"file":[{"content_type":"application/pdf","creator":"dernst","file_id":"18080","date_updated":"2024-09-17T07:31:18Z","file_size":766902,"success":1,"checksum":"66db11ef8e600a434079c278050c3f09","file_name":"2024_LIPICS_Boker.pdf","relation":"main_file","access_level":"open_access","date_created":"2024-09-17T07:31:18Z"}],"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)","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","isi":1,"arxiv":1,"external_id":{"isi":["001556847400012"],"arxiv":["2407.08620"]},"author":[{"first_name":"Udi","last_name":"Boker","id":"31E297B6-F248-11E8-B48F-1D18A9856A87","full_name":"Boker, Udi"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2985-7724","last_name":"Henzinger","first_name":"Thomas A"},{"full_name":"Lehtinen, Karoliina","first_name":"Karoliina","last_name":"Lehtinen"},{"full_name":"Prakash, Aditya","first_name":"Aditya","last_name":"Prakash"}],"_id":"18067","intvolume":"       311","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773393"]},"quality_controlled":"1","project":[{"call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software","grant_number":"101020093"}],"date_published":"2024-09-01T00:00:00Z","month":"09","status":"public","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"date_created":"2024-09-15T22:01:40Z","department":[{"_id":"ToHe"}],"citation":{"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>.","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.","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>.","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>","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.","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>"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","language":[{"iso":"eng"}],"article_number":"12","corr_author":"1","abstract":[{"lang":"eng","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."}],"oa":1,"day":"01","conference":{"start_date":"2024-09-09","name":"CONCUR: Conference on Concurrency Theory","end_date":"2024-09-13","location":"Calgary, Canada"},"year":"2024","alternative_title":["LIPIcs"],"title":"History-determinism vs fair simulation","volume":311,"doi":"10.4230/LIPIcs.CONCUR.2024.12","publication_status":"published","file_date_updated":"2024-09-17T07:31:18Z","ec_funded":1,"scopus_import":"1","ddc":["000"],"publication":"35th International Conference on Concurrency Theory","type":"conference","date_updated":"2025-12-02T13:44:54Z","article_processing_charge":"No"},{"publication":"35th International Conference on Concurrency Theory","type":"conference","date_updated":"2025-12-02T13:45:38Z","scopus_import":"1","ddc":["000"],"article_processing_charge":"Yes","year":"2024","alternative_title":["LIPIcs"],"title":"Strategic dominance: A new preorder for nondeterministic processes","volume":311,"oa":1,"day":"01","OA_type":"gold","conference":{"start_date":"2024-09-09","name":"CONCUR: Conference on Concurrency Theory","location":"Calgary, Canada","end_date":"2024-09-13"},"corr_author":"1","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"}],"article_number":"29","language":[{"iso":"eng"}],"ec_funded":1,"file_date_updated":"2024-09-17T07:48:56Z","publication_status":"published","doi":"10.4230/LIPIcs.CONCUR.2024.29","date_published":"2024-09-01T00:00:00Z","quality_controlled":"1","project":[{"grant_number":"101020093","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software","call_identifier":"H2020"}],"_id":"18068","publication_identifier":{"isbn":["9783959773393"],"issn":["1868-8969"]},"intvolume":"       311","citation":{"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>","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>","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.","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>.","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.","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."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_created":"2024-09-15T22:01:40Z","department":[{"_id":"ToHe"},{"_id":"GradSch"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"month":"09","status":"public","file":[{"date_updated":"2024-09-17T07:48:56Z","file_id":"18081","creator":"dernst","content_type":"application/pdf","date_created":"2024-09-17T07:48:56Z","relation":"main_file","access_level":"open_access","checksum":"555bd343e1fb38adeab8fc465ff4fad8","success":1,"file_size":964124,"file_name":"2024_LIPICS_Henzinger.pdf"}],"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.","has_accepted_license":"1","arxiv":1,"external_id":{"isi":["001556847400029"],"arxiv":["2407.10473"]},"author":[{"orcid":"0000-0002-2985-7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","last_name":"Henzinger"},{"first_name":"Nicolas Adrien","last_name":"Mazzocchi","id":"b26baa86-3308-11ec-87b0-8990f34baa85","full_name":"Mazzocchi, Nicolas Adrien"},{"last_name":"Sarac","first_name":"Naci E","full_name":"Sarac, Naci E","id":"8C6B42F8-C8E6-11E9-A03A-F2DCE5697425"}],"OA_place":"publisher","isi":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version"},{"type":"conference","publication":"International Conference on Approximation Algorithms for Combinatorial Optimization Problems ","date_updated":"2025-12-02T13:47:16Z","scopus_import":"1","ddc":["000"],"article_processing_charge":"No","oa":1,"conference":{"start_date":"2024-08-27","location":"London, United Kingdom","end_date":"2024-08-30","name":"APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems"},"day":"16","alternative_title":["LIPIcs"],"year":"2024","title":"Private counting of distinct elements in the turnstile model and extensions","volume":317,"language":[{"iso":"eng"}],"article_number":"40","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]."}],"corr_author":"1","file_date_updated":"2024-10-01T10:07:14Z","ec_funded":1,"doi":"10.4230/LIPIcs.APPROX/RANDOM.2024.40","publication_status":"published","quality_controlled":"1","project":[{"call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures","grant_number":"101019564"},{"grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"}],"date_published":"2024-09-16T00:00:00Z","_id":"18156","publication_identifier":{"isbn":["9783959773485"],"issn":["1868-8969"]},"intvolume":"       317","date_created":"2024-09-29T22:01:38Z","department":[{"_id":"MoHe"}],"citation":{"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>","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.","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>.","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.","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.","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>."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","month":"09","status":"public","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"file":[{"date_updated":"2024-10-01T10:07:14Z","file_id":"18166","creator":"dernst","content_type":"application/pdf","date_created":"2024-10-01T10:07:14Z","access_level":"open_access","relation":"main_file","file_name":"2024_LIPICs_HenzingerM.pdf","checksum":"c08b41c896e4d8c69570044808b40e0b","success":1,"file_size":973917}],"has_accepted_license":"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 (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.","isi":1,"arxiv":1,"external_id":{"arxiv":["2408.11637"],"isi":["001545634500040"]},"author":[{"orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger"},{"full_name":"Sricharan, A. R.","last_name":"Sricharan","first_name":"A. R."},{"full_name":"Steiner, Teresa Anna","last_name":"Steiner","first_name":"Teresa Anna"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version"},{"title":"The fault in our stars: Designing reproducible large-scale code analysis experiments","volume":313,"alternative_title":["LIPIcs"],"year":"2024","day":"01","conference":{"end_date":"2024-09-20","name":"ECOOP: European Conference on Object-Oriented Programming","location":"Vienna, Austria","start_date":"2024-09-16"},"oa":1,"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"}],"article_number":"27","language":[{"iso":"eng"}],"file_date_updated":"2024-10-07T11:10:55Z","publication_status":"published","doi":"10.4230/LIPIcs.ECOOP.2024.27","date_updated":"2025-12-02T13:48:19Z","type":"conference","publication":"38th European Conference on Object-Oriented Programming","ddc":["000"],"scopus_import":"1","article_processing_charge":"No","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.","has_accepted_license":"1","file":[{"creator":"dernst","content_type":"application/pdf","file_id":"18184","date_updated":"2024-10-07T11:10:55Z","checksum":"2e75d305a8c817d76a0c7f136ce34f86","success":1,"file_size":1764222,"file_name":"2024_LIPICs_Maj.pdf","date_created":"2024-10-07T11:10:55Z","relation":"main_file","access_level":"open_access"}],"author":[{"full_name":"Maj, Petr","last_name":"Maj","first_name":"Petr"},{"last_name":"Muroya Lei","first_name":"Stefanie","id":"a376de31-8972-11ed-ae7b-d0251c13c8ff","full_name":"Muroya Lei, Stefanie"},{"first_name":"Konrad","last_name":"Siek","full_name":"Siek, Konrad"},{"first_name":"Luca","last_name":"Di Grazia","full_name":"Di Grazia, Luca"},{"last_name":"Vitek","first_name":"Jan","full_name":"Vitek, Jan"}],"external_id":{"isi":["001533999700027"]},"isi":1,"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2024-09-01T00:00:00Z","quality_controlled":"1","intvolume":"       313","publication_identifier":{"isbn":["9783959773416"],"issn":["1868-8969"]},"_id":"18175","citation":{"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.","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>","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>.","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>.","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.","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","date_created":"2024-10-06T22:01:12Z","department":[{"_id":"ToHe"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"status":"public","month":"09"},{"isi":1,"OA_place":"publisher","author":[{"first_name":"Max Dupré","last_name":"La Tour","full_name":"La Tour, Max Dupré"},{"first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964","full_name":"Saulpic, David","last_name":"Saulpic","first_name":"David"}],"external_id":{"isi":["001545622400100"],"arxiv":["2406.19926"]},"arxiv":1,"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","has_accepted_license":"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 (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).","file":[{"date_created":"2024-10-21T09:41:48Z","relation":"main_file","access_level":"open_access","checksum":"8e8c0b13049f11bb0133dfac22e32718","file_size":873561,"success":1,"file_name":"2024_LIPICs_DuprelaTour.pdf","file_id":"18454","date_updated":"2024-10-21T09:41:48Z","creator":"dernst","content_type":"application/pdf"}],"date_created":"2024-10-13T22:01:50Z","department":[{"_id":"MoHe"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"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>.","short":"M.D. La Tour, M. Henzinger, D. Saulpic, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","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.","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>","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.","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>"},"status":"public","month":"09","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","grant_number":"101019564"},{"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"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"},{"call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413"}],"quality_controlled":"1","date_published":"2024-09-23T00:00:00Z","publication_identifier":{"isbn":["9783959773386"],"issn":["1868-8969"]},"intvolume":"       308","_id":"18308","file_date_updated":"2024-10-21T09:41:48Z","ec_funded":1,"doi":"10.4230/LIPIcs.ESA.2024.100","publication_status":"published","OA_type":"gold","conference":{"name":"ESA: European Symposium on Algorithms","location":"London, United Kingdom","end_date":"2024-09-04","start_date":"2024-09-02"},"day":"23","oa":1,"title":"Fully dynamic k-means coreset in near-optimal update time","volume":308,"alternative_title":["LIPIcs"],"year":"2024","language":[{"iso":"eng"}],"article_number":"100","abstract":[{"lang":"eng","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)."}],"corr_author":"1","article_processing_charge":"Yes","date_updated":"2025-12-02T13:49:11Z","publication":"32nd Annual European Symposium on Algorithms","type":"conference","ddc":["000"],"scopus_import":"1"},{"date_created":"2024-10-13T22:01:50Z","department":[{"_id":"MoHe"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"short":"B. Hu, E. Kosinas, A. Polak, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","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>.","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.","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>.","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>","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."},"month":"09","status":"public","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"quality_controlled":"1","date_published":"2024-09-01T00:00:00Z","_id":"18309","publication_identifier":{"isbn":["9783959773386"],"issn":["1868-8969"]},"intvolume":"       308","isi":1,"OA_place":"publisher","external_id":{"isi":["001545622400072"],"arxiv":["2312.08489"]},"arxiv":1,"author":[{"last_name":"Hu","first_name":"Bingbing","full_name":"Hu, Bingbing"},{"id":"4c7f9625-dbbc-11ee-9d86-bdcc2db5a949","full_name":"Kosinas, Evangelos","last_name":"Kosinas","first_name":"Evangelos"},{"first_name":"Adam","last_name":"Polak","full_name":"Polak, Adam"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","file":[{"date_created":"2024-10-21T10:03:48Z","access_level":"open_access","relation":"main_file","file_name":"2024_LIPICs_Hu.pdf","success":1,"file_size":853914,"checksum":"ab1f2f9161549a8763eda15db40e022c","file_id":"18455","date_updated":"2024-10-21T10:03:48Z","creator":"dernst","content_type":"application/pdf"}],"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","has_accepted_license":"1","article_processing_charge":"Yes","publication":"32nd Annual European Symposium on Algorithms","type":"conference","date_updated":"2025-12-02T13:49:52Z","scopus_import":"1","ddc":["000"],"file_date_updated":"2024-10-21T10:03:48Z","doi":"10.4230/LIPIcs.ESA.2024.72","publication_status":"published","oa":1,"OA_type":"gold","day":"01","conference":{"start_date":"2024-09-02","end_date":"2024-09-04","location":"London, United Kingdom","name":"ESA: European Symposium on Algorithms"},"alternative_title":["LIPIcs"],"year":"2024","title":"Connectivity oracles for predictable vertex failures","volume":308,"article_number":"72","language":[{"iso":"eng"}],"abstract":[{"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.","lang":"eng"}],"corr_author":"1"},{"month":"10","status":"public","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"},"date_created":"2024-11-17T23:01:47Z","department":[{"_id":"HeEd"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"short":"S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, M. Saghafian, in:, 32nd International Symposium on Graph Drawing and Network Visualization, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","mla":"Cultrera di Montesano, Sebastiano, et al. “The Euclidean MST-Ratio for Bi-Colored Lattices.” <i>32nd International Symposium on Graph Drawing and Network Visualization</i>, vol. 320, 3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.GD.2024.3\">10.4230/LIPIcs.GD.2024.3</a>.","ista":"Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. 2024. The Euclidean MST-ratio for bi-colored lattices. 32nd International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LIPIcs, vol. 320, 3.","chicago":"Cultrera di Montesano, Sebastiano, Ondrej Draganov, Herbert Edelsbrunner, and Morteza Saghafian. “The Euclidean MST-Ratio for Bi-Colored Lattices.” In <i>32nd International Symposium on Graph Drawing and Network Visualization</i>, Vol. 320. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.GD.2024.3\">https://doi.org/10.4230/LIPIcs.GD.2024.3</a>.","apa":"Cultrera di Montesano, S., Draganov, O., Edelsbrunner, H., &#38; Saghafian, M. (2024). The Euclidean MST-ratio for bi-colored lattices. In <i>32nd International Symposium on Graph Drawing and Network Visualization</i> (Vol. 320). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.GD.2024.3\">https://doi.org/10.4230/LIPIcs.GD.2024.3</a>","ieee":"S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, and M. Saghafian, “The Euclidean MST-ratio for bi-colored lattices,” in <i>32nd International Symposium on Graph Drawing and Network Visualization</i>, Vienna, Austria, 2024, vol. 320.","ama":"Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. The Euclidean MST-ratio for bi-colored lattices. In: <i>32nd International Symposium on Graph Drawing and Network Visualization</i>. Vol 320. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.GD.2024.3\">10.4230/LIPIcs.GD.2024.3</a>"},"_id":"18556","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773430"]},"intvolume":"       320","project":[{"_id":"266A2E9E-B435-11E9-9278-68D0E5697425","name":"Alpha Shape Theory Extended","call_identifier":"H2020","grant_number":"788183"},{"grant_number":"Z00342","name":"Mathematics, Computer Science","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"I02979-N35","call_identifier":"FWF","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","name":"Persistence and stability of geometric complexes"}],"quality_controlled":"1","date_published":"2024-10-28T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","isi":1,"OA_place":"publisher","arxiv":1,"external_id":{"isi":["001540278400001"],"arxiv":["2403.10204"]},"author":[{"id":"34D2A09C-F248-11E8-B48F-1D18A9856A87","full_name":"Cultrera di Montesano, Sebastiano","orcid":"0000-0001-6249-0832","last_name":"Cultrera di Montesano","first_name":"Sebastiano"},{"last_name":"Draganov","first_name":"Ondrej","orcid":"0000-0003-0464-3823","full_name":"Draganov, Ondrej","id":"2B23F01E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"},{"first_name":"Morteza","last_name":"Saghafian","id":"f86f7148-b140-11ec-9577-95435b8df824","full_name":"Saghafian, Morteza"}],"file":[{"creator":"dernst","content_type":"application/pdf","file_id":"18560","date_updated":"2024-11-18T07:49:25Z","success":1,"file_size":908541,"checksum":"5f9b35e115c3d375e99be78da9054cb4","file_name":"2024_LIPIcs_CultreradiMontesano.pdf","date_created":"2024-11-18T07:49:25Z","relation":"main_file","access_level":"open_access"}],"acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant no. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, \"Discretization in Geometry and Dynamics\", Austrian Science Fund (FWF), grant no. I 02979-N35.","has_accepted_license":"1","article_processing_charge":"Yes","scopus_import":"1","ddc":["510"],"type":"conference","publication":"32nd International Symposium on Graph Drawing and Network Visualization","date_updated":"2025-12-02T13:50:50Z","doi":"10.4230/LIPIcs.GD.2024.3","publication_status":"published","file_date_updated":"2024-11-18T07:49:25Z","ec_funded":1,"language":[{"iso":"eng"}],"article_number":"3","corr_author":"1","abstract":[{"lang":"eng","text":"Given a finite set, A ⊆ ℝ², and a subset, B ⊆ A, the MST-ratio is the combined length of the minimum spanning trees of B and A⧵B divided by the length of the minimum spanning tree of A. The question of the supremum, over all sets A, of the maximum, over all subsets B, is related to the Steiner ratio, and we prove this sup-max is between 2.154 and 2.427. Restricting ourselves to 2-dimensional lattices, we prove that the sup-max is 2, while the inf-max is 1.25. By some margin the most difficult of these results is the upper bound for the inf-max, which we prove by showing that the hexagonal lattice cannot have MST-ratio larger than 1.25."}],"oa":1,"day":"28","conference":{"start_date":"2024-09-18","end_date":"2024-09-20","location":"Vienna, Austria","name":"GD: Graph Drawing and Network Visualization"},"OA_type":"gold","alternative_title":["LIPIcs"],"year":"2024","title":"The Euclidean MST-ratio for bi-colored lattices","volume":320},{"day":"24","conference":{"end_date":"2024-11-01","name":"DISC: Symposium on Distributed Computing","location":"Madrid, Spain","start_date":"2024-10-28"},"OA_type":"gold","oa":1,"title":"Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges","volume":319,"year":"2024","alternative_title":["LIPIcs"],"language":[{"iso":"eng"}],"article_number":"21","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"}],"corr_author":"1","file_date_updated":"2024-11-18T08:02:45Z","ec_funded":1,"doi":"10.4230/LIPIcs.DISC.2024.21","publication_status":"published","date_updated":"2025-12-02T13:51:28Z","publication":"38th International Symposium on Distributed Computing","type":"conference","ddc":["000"],"scopus_import":"1","article_processing_charge":"Yes","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.","has_accepted_license":"1","file":[{"relation":"main_file","access_level":"open_access","date_created":"2024-11-18T08:02:45Z","checksum":"d6c8277331cafa188c33ba1717206cf4","success":1,"file_size":809666,"file_name":"2024_LIPIcs_ElHayek.pdf","file_id":"18561","date_updated":"2024-11-18T08:02:45Z","content_type":"application/pdf","creator":"dernst"}],"OA_place":"publisher","isi":1,"author":[{"orcid":"0000-0003-4268-7368","full_name":"El-Hayek, Antoine","id":"888a098e-fcac-11ee-aff7-d347be57b725","first_name":"Antoine","last_name":"El-Hayek"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger"},{"full_name":"Schmid, Stefan","last_name":"Schmid","first_name":"Stefan"}],"arxiv":1,"external_id":{"arxiv":["2302.11988"],"isi":["001542467600021"]},"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775"},{"grant_number":"101019564","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"quality_controlled":"1","date_published":"2024-10-24T00:00:00Z","intvolume":"       319","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773522"]},"_id":"18557","date_created":"2024-11-17T23:01:47Z","department":[{"_id":"MoHe"}],"citation":{"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>","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.","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>","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>.","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.","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>.","short":"A. El-Hayek, M. Henzinger, S. Schmid, in:, 38th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","status":"public","month":"10","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)"}}]