[{"quality_controlled":"1","project":[{"grant_number":"101020093","call_identifier":"H2020","name":"Vigilant Algorithmic Monitoring of Software","_id":"62781420-2b32-11ec-9570-8d9b63373d4d"}],"article_processing_charge":"No","date_created":"2026-08-02T22:01:52Z","supplementarymaterial":"no","license":"https://creativecommons.org/licenses/by/4.0/","month":"07","publication_status":"published","volume":380,"department":[{"_id":"ToHe"}],"language":[{"iso":"eng"}],"article_number":"23:1-23:26","type":"conference","doi":"10.4230/LIPIcs.LICS.2026.23","title":"Dicey games: Shared sources of randomness in distributed systems","oa":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959774345"]},"author":[{"first_name":"Leonard J","last_name":"Brice","id":"ce3b3409-db6c-11f0-aa64-ad678f7fd937","full_name":"Brice, Leonard J"},{"first_name":"Thomas A","orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","full_name":"Henzinger, Thomas A"},{"full_name":"Thejaswini, K. S.","last_name":"Thejaswini","first_name":"K. S."}],"publication":"41st Annual Symposium on Logic in Computer Science","scopus_import":"1","conference":{"start_date":"2026-07-20","end_date":"2026-07-23","name":"LICS: Logic in Computer Science","location":"Lisbon, Portugal"},"corr_author":"1","intvolume":"       380","file":[{"file_id":"22625","success":1,"date_created":"2026-08-03T07:02:30Z","file_size":919708,"file_name":"2026_LIPICSLICS_Brice.pdf","relation":"main_file","checksum":"5d0ff4d267565188a8b4c7502e1bd243","access_level":"open_access","creator":"dernst","date_updated":"2026-08-03T07:02:30Z","content_type":"application/pdf"}],"external_id":{"arxiv":["2601.18303"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2026","citation":{"chicago":"Brice, Leonard J, Thomas A Henzinger, and K. S. Thejaswini. “Dicey Games: Shared Sources of Randomness in Distributed Systems.” In <i>41st Annual Symposium on Logic in Computer Science</i>, Vol. 380. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.LICS.2026.23\">https://doi.org/10.4230/LIPIcs.LICS.2026.23</a>.","short":"L.J. Brice, T.A. Henzinger, K.S. Thejaswini, in:, 41st Annual Symposium on Logic in Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","mla":"Brice, Leonard J., et al. “Dicey Games: Shared Sources of Randomness in Distributed Systems.” <i>41st Annual Symposium on Logic in Computer Science</i>, vol. 380, 23:1-23:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.LICS.2026.23\">10.4230/LIPIcs.LICS.2026.23</a>.","ista":"Brice LJ, Henzinger TA, Thejaswini KS. 2026. Dicey games: Shared sources of randomness in distributed systems. 41st Annual Symposium on Logic in Computer Science. LICS: Logic in Computer Science, LIPIcs, vol. 380, 23:1-23:26.","ama":"Brice LJ, Henzinger TA, Thejaswini KS. Dicey games: Shared sources of randomness in distributed systems. In: <i>41st Annual Symposium on Logic in Computer Science</i>. Vol 380. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.LICS.2026.23\">10.4230/LIPIcs.LICS.2026.23</a>","apa":"Brice, L. J., Henzinger, T. A., &#38; Thejaswini, K. S. (2026). Dicey games: Shared sources of randomness in distributed systems. In <i>41st Annual Symposium on Logic in Computer Science</i> (Vol. 380). Lisbon, Portugal: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.LICS.2026.23\">https://doi.org/10.4230/LIPIcs.LICS.2026.23</a>","ieee":"L. J. Brice, T. A. Henzinger, and K. S. Thejaswini, “Dicey games: Shared sources of randomness in distributed systems,” in <i>41st Annual Symposium on Logic in Computer Science</i>, Lisbon, Portugal, 2026, vol. 380."},"acknowledgement":"This work was supported in part by the ERC-2020-AdG 101020093 (VAMOS).\r\nLéonard Brice: Part of this work was realised when this author was an FNRS aspirant at Université libre de Bruxelles.\r\nK. S. Thejaswini: Part of this work was realised when this author was a post-doctoral researcher at IST Austria.\r\nAcknowledgements We thank all our colleagues who took the time to hear our puzzle and wasted several hours of their research time in pursuit of the optimal bounds for the 3-player matching.\r\npennies problem.\r\n","das_tickbox":"0","day":"09","arxiv":1,"oa_version":"Published Version","_id":"22617","status":"public","researchdata_availability":"no","OA_place":"publisher","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"keyword":["Concurrent games","Shared randomness","Topology","Algebraic Geometry"],"fulldoi":"https://doi.org/10.4230/LIPIcs.LICS.2026.23","OA_type":"gold","date_published":"2026-07-09T00:00:00Z","has_accepted_license":"1","ddc":["000"],"ec_funded":1,"abstract":[{"lang":"eng","text":"Consider a 4-player version of Matching Pennies where a team of three players competes against the Devil. Each player simultaneously says \"Heads\" or \"Tails\". The team wins if all four choices match; otherwise the Devil wins. If all team players randomise independently, they win with probability 1/8; if all players share a common source of randomness, they win with probability 1/2. What happens when each pair of team players shares a source of randomness? Can the team do better than win with probability 1/4? The surprising (and nontrivial) answer is yes!\r\nWe introduce Dicey Games, a formal framework motivated by the study of distributed systems with shared sources of randomness (of which the above example is a specific instance). We characterise the existence, representation and computational complexity of optimal strategies in Dicey Games, and we study the problem of allocating limited sources of randomness optimally within a team."}],"file_date_updated":"2026-08-03T07:02:30Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-08-03T07:03:28Z","alternative_title":["LIPIcs"]},{"date_updated":"2026-09-16T08:59:49Z","alternative_title":["LIPIcs"],"abstract":[{"text":"In the imprecise geometry model, the input is a family of regions F = (R₁, R₂, …,R_n), each containing a point p_i ∈ R_i. The task is then to compute some function of the points p₁,p₂,… p_n, in our case an implicit representation of their Pareto front. To this end, one may query a region R_i to retrieve its contained point p_i ∈ R_i. In this model, efficiency is interpreted in two ways: minimizing (i) the number of retrievals, and (ii) the computation time both for preprocessing, and the execution of the query stage, i.e. for computing which points to query and constructing the output. \r\nWe present an algorithm to construct (an implicit representation of) the Pareto front for possibly overlapping rectangles, that is instance-optimal with respect to the number of retrievals. This means that for every fixed input (F, P), there is no algorithm that retrieves asymptotically fewer regions to compute the output. This is a strong algorithmic quality, as it means that our algorithm is competitive even to clairvoyant algorithms which only have to verify the correctness of a correct guess. In terms of algorithmic running time, instance-optimality is provably unobtainable. We instead present an algorithm which is within a log n-factor of instance optimality. This generalizes earlier results which assumed the regions to not overlap, at only a minor cost in running time. \r\nFor unit squares, we present an algorithm that is not only instance optimal in the number of retrievals, but also universally optimal in terms of running time. This means that for any fixed set of regions F, no algorithm has a better worst-case running time for all possible point sets P. Thus, this work presents the first universally optimal algorithm for overlapping planar input. Compared to previous work, our result improves the degree to which the input regions may overlap, the preprocessing time, the number of retrievals, and the running time.","lang":"eng"}],"file_date_updated":"2026-09-16T08:58:04Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2026.106","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"keyword":["Pareto front","imprecise geometry","instance optimality","universal optimality","preprocessing model","partial information"],"ddc":["000"],"date_published":"2026-08-25T00:00:00Z","OA_type":"gold","has_accepted_license":"1","OA_place":"publisher","oa_version":"Published Version","_id":"22916","researchdata_availability":"no","status":"public","year":"2026","acknowledgement":"This work was supported by the the VILLUM Foundation grant (VIL37507) \"Efficient Recomputations for Changeful Problems\".","citation":{"chicago":"De Berg, Sarita, Nynne Maria Foldager Bække, Frida Astrup Eriksen, Ivor Van Der Hoog, Eva Rotenberg, and Daniel P Rutschmann. “Instance Optimal and Universally Optimal Bounds for Imprecise Pareto Fronts.” In <i>34th Annual European Symposium on Algorithms</i>, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.106\">https://doi.org/10.4230/LIPIcs.ESA.2026.106</a>.","mla":"De Berg, Sarita, et al. “Instance Optimal and Universally Optimal Bounds for Imprecise Pareto Fronts.” <i>34th Annual European Symposium on Algorithms</i>, vol. 388, 106, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.106\">10.4230/LIPIcs.ESA.2026.106</a>.","short":"S. De Berg, N.M.F. Bække, F.A. Eriksen, I. Van Der Hoog, E. Rotenberg, D.P. Rutschmann, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","ama":"De Berg S, Bække NMF, Eriksen FA, Van Der Hoog I, Rotenberg E, Rutschmann DP. Instance optimal and universally optimal bounds for imprecise pareto fronts. In: <i>34th Annual European Symposium on Algorithms</i>. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.106\">10.4230/LIPIcs.ESA.2026.106</a>","ista":"De Berg S, Bække NMF, Eriksen FA, Van Der Hoog I, Rotenberg E, Rutschmann DP. 2026. Instance optimal and universally optimal bounds for imprecise pareto fronts. 34th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 106.","ieee":"S. De Berg, N. M. F. Bække, F. A. Eriksen, I. Van Der Hoog, E. Rotenberg, and D. P. Rutschmann, “Instance optimal and universally optimal bounds for imprecise pareto fronts,” in <i>34th Annual European Symposium on Algorithms</i>, L’Aquila, Italy, 2026, vol. 388.","apa":"De Berg, S., Bække, N. M. F., Eriksen, F. A., Van Der Hoog, I., Rotenberg, E., &#38; Rutschmann, D. P. (2026). Instance optimal and universally optimal bounds for imprecise pareto fronts. In <i>34th Annual European Symposium on Algorithms</i> (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.106\">https://doi.org/10.4230/LIPIcs.ESA.2026.106</a>"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"das_tickbox":"0","day":"25","file":[{"file_name":"2026_LIPIcsESA_deBerg.pdf","date_created":"2026-09-16T08:58:04Z","file_size":1102214,"file_id":"22935","success":1,"date_updated":"2026-09-16T08:58:04Z","content_type":"application/pdf","creator":"dernst","relation":"main_file","checksum":"75cfae9e9773be4b06f9aab66041f0f3","access_level":"open_access"}],"intvolume":"       388","external_id":{"arxiv":["2605.07523"]},"scopus_import":"1","corr_author":"1","conference":{"location":"L’Aquila, Italy","end_date":"2026-09-04","name":"ESA: European Symposium on Algorithms","start_date":"2026-08-31"},"author":[{"first_name":"Sarita","last_name":"De Berg","full_name":"De Berg, Sarita"},{"full_name":"Bække, Nynne Maria Foldager","last_name":"Bække","first_name":"Nynne Maria Foldager"},{"full_name":"Eriksen, Frida Astrup","last_name":"Eriksen","first_name":"Frida Astrup"},{"full_name":"Van Der Hoog, Ivor","last_name":"Van Der Hoog","first_name":"Ivor"},{"last_name":"Rotenberg","full_name":"Rotenberg, Eva","first_name":"Eva"},{"id":"7397d908-b582-11f0-bf73-88b902e86527","last_name":"Rutschmann","full_name":"Rutschmann, Daniel P","first_name":"Daniel P"}],"publication":"34th Annual European Symposium on Algorithms","doi":"10.4230/LIPIcs.ESA.2026.106","type":"conference","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959774451"]},"title":"Instance optimal and universally optimal bounds for imprecise pareto fronts","oa":1,"article_number":"106","volume":388,"language":[{"iso":"eng"}],"department":[{"_id":"MoHe"}],"publication_status":"published","month":"08","supplementarymaterial":"no","date_created":"2026-09-13T22:01:52Z","article_processing_charge":"Yes","quality_controlled":"1"},{"article_number":"101","title":"Tight Better-Than-Worst-Case bounds for element distinctness and set intersection","oa":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959774451"]},"type":"conference","doi":"10.4230/LIPIcs.ESA.2026.101","publication":"34th Annual European Symposium on Algorithms","author":[{"first_name":"Ivor","full_name":"Van Der Hoog, Ivor","last_name":"Van Der Hoog"},{"first_name":"Eva","full_name":"Rotenberg, Eva","last_name":"Rotenberg"},{"last_name":"Rutschmann","id":"7397d908-b582-11f0-bf73-88b902e86527","full_name":"Rutschmann, Daniel P","first_name":"Daniel P"}],"conference":{"location":"L’Aquila, Italy","end_date":"2026-09-04","name":"ESA: European Symposium on Algorithms","start_date":"2026-08-31"},"corr_author":"1","scopus_import":"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"}],"quality_controlled":"1","article_processing_charge":"Yes","date_created":"2026-09-13T22:01:52Z","supplementarymaterial":"yes","month":"08","publication_status":"published","language":[{"iso":"eng"}],"volume":388,"department":[{"_id":"MoHe"}],"OA_place":"publisher","OA_type":"gold","has_accepted_license":"1","date_published":"2026-08-25T00:00:00Z","ddc":["000"],"keyword":["Comparison-based analysis","set intersection","universal optimality"],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2026.101","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"file_date_updated":"2026-09-16T09:20:49Z","abstract":[{"text":"The element distinctness problem takes as input a list I of n values from a totally ordered universe, where pairwise comparisons between values are allowed, and the goal is to decide whether I contains any duplicates. It is a well-studied problem with a classical worst-case Ω(n log n) comparison-based lower bound by Fredman [TCS'76]. At first glance, this lower bound appears to rule out any algorithm more efficient than the naive approach of sorting I and comparing adjacent elements. However, upon closer inspection, the Ω(n log n) bound is overly pessimistic. For instance, if I contains n/2 identical elements, a median-finding algorithm will, regardless of the input order, find a duplicate in linear time. This raises a natural question: Are there comparison-based lower bounds for element distinctness that are sensitive to the amount of duplicates in the input instance?\r\nTo address this question, we derive instance-specific lower bounds. For any input instance I, we represent the combinatorial structure of the duplicates in I by an undirected graph G(I) that connects identical elements. Each such graph G is a union of cliques, and we study algorithms by their worst-case running time over all inputs I' with G(I') ≅ G. We establish an adversarial lower bound showing that, for any deterministic algorithm 𝒜, there exists a graph G and an algorithm 𝒜' that, for all inputs I with G(I) ≅ G, is a factor O(log log n) faster than 𝒜. Consequently, no deterministic algorithm can be o(log log n)-competitive for all graphs G. We complement this with an O(log log n)-competitive deterministic algorithm, thereby obtaining tight bounds for element distinctness that go beyond classical worst-case analysis. Subsequently, we study the related problem of set intersection. We show that no deterministic set intersection algorithm can be o(log n)-competitive, and provide an O(log n)-competitive deterministic algorithm. We find it interesting and surprising to discover tight O(log log n)-competitive bounds for element distinctness. Moreover, we find the separation between element distinctness and the set intersection problem unexpected.","lang":"eng"}],"date_updated":"2026-09-16T09:21:35Z","alternative_title":["LIPIcs"],"external_id":{"arxiv":["2511.02954"]},"intvolume":"       388","file":[{"creator":"dernst","content_type":"application/pdf","date_updated":"2026-09-16T09:20:49Z","checksum":"c552853bfa37e4b9a0f060107e464ed0","access_level":"open_access","relation":"main_file","file_size":892322,"date_created":"2026-09-16T09:20:49Z","file_name":"2026_LIPIcsESA_vanderHoog.pdf","success":1,"file_id":"22937"}],"das_tickbox":"0","arxiv":1,"day":"25","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","acknowledgement":"Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann thank the VILLUM Foundation\r\ngrant (VIL37507) “Efficient Recomputations for Changeful Problems” for supporting this work.\r\nDaniel Rutschmann is supported by the European Research Council (ERC) under the European\r\nUnion’s Horizon 2020 research and innovation programme (No. 101019564) ","citation":{"mla":"Van Der Hoog, Ivor, et al. “Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection.” <i>34th Annual European Symposium on Algorithms</i>, vol. 388, 101, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.101\">10.4230/LIPIcs.ESA.2026.101</a>.","short":"I. Van Der Hoog, E. Rotenberg, D.P. Rutschmann, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","chicago":"Van Der Hoog, Ivor, Eva Rotenberg, and Daniel P Rutschmann. “Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection.” In <i>34th Annual European Symposium on Algorithms</i>, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.101\">https://doi.org/10.4230/LIPIcs.ESA.2026.101</a>.","apa":"Van Der Hoog, I., Rotenberg, E., &#38; Rutschmann, D. P. (2026). Tight Better-Than-Worst-Case bounds for element distinctness and set intersection. In <i>34th Annual European Symposium on Algorithms</i> (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.101\">https://doi.org/10.4230/LIPIcs.ESA.2026.101</a>","ieee":"I. Van Der Hoog, E. Rotenberg, and D. P. Rutschmann, “Tight Better-Than-Worst-Case bounds for element distinctness and set intersection,” in <i>34th Annual European Symposium on Algorithms</i>, L’Aquila, Italy, 2026, vol. 388.","ama":"Van Der Hoog I, Rotenberg E, Rutschmann DP. Tight Better-Than-Worst-Case bounds for element distinctness and set intersection. In: <i>34th Annual European Symposium on Algorithms</i>. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.101\">10.4230/LIPIcs.ESA.2026.101</a>","ista":"Van Der Hoog I, Rotenberg E, Rutschmann DP. 2026. Tight Better-Than-Worst-Case bounds for element distinctness and set intersection. 34th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 101."},"year":"2026","_id":"22915","status":"public","researchdata_availability":"no","oa_version":"Published Version"},{"external_id":{"arxiv":["2604.04186"]},"intvolume":"       388","file":[{"relation":"main_file","checksum":"2082683b3b72865c6a795305e5d61276","access_level":"open_access","date_updated":"2026-09-17T10:09:22Z","content_type":"application/pdf","creator":"dernst","file_id":"22948","success":1,"file_name":"2026_LIPIcsESA_Bhore.pdf","file_size":1123327,"date_created":"2026-09-17T10:09:22Z"}],"day":"25","das_tickbox":"0","arxiv":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2026","citation":{"chicago":"Bhore, Sujoy, Hsien Chih Chang, Jonathan Conroy, Arnold Filtser, Eunjin Oh, Nicole Wein, and Da Wei Zheng. “DAG Covers for Structured Graphs: The Steiner Point Effect.” In <i>34th Annual European Symposium on Algorithms</i>, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.94\">https://doi.org/10.4230/LIPIcs.ESA.2026.94</a>.","mla":"Bhore, Sujoy, et al. “DAG Covers for Structured Graphs: The Steiner Point Effect.” <i>34th Annual European Symposium on Algorithms</i>, vol. 388, 94:1-94:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.94\">10.4230/LIPIcs.ESA.2026.94</a>.","short":"S. Bhore, H.C. Chang, J. Conroy, A. Filtser, E. Oh, N. Wein, D.W. Zheng, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","ista":"Bhore S, Chang HC, Conroy J, Filtser A, Oh E, Wein N, Zheng DW. 2026. DAG covers for structured graphs: The Steiner point effect. 34th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 94:1-94:18.","ama":"Bhore S, Chang HC, Conroy J, et al. DAG covers for structured graphs: The Steiner point effect. In: <i>34th Annual European Symposium on Algorithms</i>. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.94\">10.4230/LIPIcs.ESA.2026.94</a>","apa":"Bhore, S., Chang, H. C., Conroy, J., Filtser, A., Oh, E., Wein, N., &#38; Zheng, D. W. (2026). DAG covers for structured graphs: The Steiner point effect. In <i>34th Annual European Symposium on Algorithms</i> (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2026.94\">https://doi.org/10.4230/LIPIcs.ESA.2026.94</a>","ieee":"S. Bhore <i>et al.</i>, “DAG covers for structured graphs: The Steiner point effect,” in <i>34th Annual European Symposium on Algorithms</i>, L’Aquila, Italy, 2026, vol. 388."},"acknowledgement":"This work was initiated at Dagstuhl Seminar 25212: Metric Sketching and\r\nDynamic Algorithms for Geometric and Topological Graphs. We thank the organizers and other\r\nparticipants for a productive environment.\r\nujoy Bhore: Work supported in part by ANRF ARG-MATRICS, Grant 002465.\r\nHsien-Chih Chang: Supported by the U.S. National Science Foundation Grant No. CCF-2443017.\r\nJonathan Conroy: Supported by the U.S. National Science Foundation Grant No. CCF-2443017.\r\nArnold Filtser: This research was supported by the ISRAEL SCIENCE FOUNDATION (grant No.\r\n1042/22).\r\nEunjin Oh: Supported by Institute of Information & Communications Technology Planning &\r\nEvaluation (IITP) grant funded by the Korea government (MSIT) (No. RS-2024-00440239, Sublinear\r\nScalable Algorithms for Large-Scale Data Analysis) and the National Research Foundation of Korea\r\n(NRF) grant funded by the Korea government (MSIT) (No. RS-2024-00358505).\r\nNicole Wein: Supported by NSF CAREER award 2541910.\r\nDa Wei Zheng: This project has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982. For open access purposes, the author has applied a CC BY public copyright\r\nlicense to any author-accepted manuscript version arising from this submission.","_id":"22918","researchdata_availability":"no","status":"public","oa_version":"Published Version","OA_place":"publisher","has_accepted_license":"1","OA_type":"gold","date_published":"2026-08-25T00:00:00Z","ddc":["000"],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"keyword":["Directed graphs","DAG (directed acyclic graphs)","distortion","metric embeddings","planar graph","treewidth"],"fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2026.94","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2026-09-17T10:09:22Z","abstract":[{"text":"Given a weighted digraph G, a (t,g,μ)-DAG cover is a collection of g dominating DAGs D_1,… ,D_g such that all distances are approximately preserved: for every pair (u,v) of vertices, min_id_{D_i}(u,v) ≤ t⋅ d_G(u,v), and the total number of non-G edges is bounded by |(∪_i D_i)⧵ G| ≤ μ. Assadi, Hoppenworth, and Wein [STOC 25] and Filtser [SODA 26] studied DAG covers for general digraphs. This paper initiates the study of Steiner DAG cover, where the DAGs are allowed to contain Steiner points. \r\nWe obtain Steiner DAG covers on the important classes of planar digraphs and low-treewidth digraphs. Specifically, we show that any digraph with treewidth tw admits a (1,2,Õ(n⋅tw))-Steiner DAG cover. For planar digraphs we provide a (1+ε,2,Õ_ε(n))-Steiner DAG cover.\r\nWe also demonstrate a stark difference between Steiner and non-Steiner DAG covers. As a lower bound, we show that any non-Steiner DAG cover for graphs with treewidth 1 with stretch t < 2 and sub-quadratic number of extra edges requires Ω(log n) DAGs.","lang":"eng"}],"alternative_title":["LIPIcs"],"date_updated":"2026-09-17T10:27:46Z","project":[{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982"}],"quality_controlled":"1","article_processing_charge":"Yes","supplementarymaterial":"yes","date_created":"2026-09-13T22:01:53Z","month":"08","publication_status":"published","department":[{"_id":"MoHe"}],"language":[{"iso":"eng"}],"volume":388,"article_number":"94:1-94:18","title":"DAG covers for structured graphs: The Steiner point effect","oa":1,"publication_identifier":{"isbn":["9783959774451"],"issn":["1868-8969"]},"type":"conference","doi":"10.4230/LIPIcs.ESA.2026.94","publication":"34th Annual European Symposium on Algorithms","author":[{"full_name":"Bhore, Sujoy","last_name":"Bhore","first_name":"Sujoy"},{"first_name":"Hsien Chih","last_name":"Chang","full_name":"Chang, Hsien Chih"},{"full_name":"Conroy, Jonathan","last_name":"Conroy","first_name":"Jonathan"},{"first_name":"Arnold","full_name":"Filtser, Arnold","last_name":"Filtser"},{"last_name":"Oh","full_name":"Oh, Eunjin","first_name":"Eunjin"},{"last_name":"Wein","full_name":"Wein, Nicole","first_name":"Nicole"},{"full_name":"Zheng, Da Wei","last_name":"Zheng","id":"af77956b-e859-11ef-8dc9-d301b898e32f","first_name":"Da Wei"}],"conference":{"start_date":"2026-08-31","end_date":"2026-09-04","name":"ESA: European Symposium on Algorithms","location":"L’Aquila, Italy"},"corr_author":"1","scopus_import":"1"},{"OA_place":"publisher","has_accepted_license":"1","date_published":"2026-08-24T00:00:00Z","OA_type":"gold","ddc":["000"],"keyword":["Runtime Verification","Probabilistic Systems","Quantitative Verification","Approximate Monitoring"],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.4230/LIPIcs.CONCUR.2026.22","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2026-09-22T05:59:03Z","abstract":[{"text":"Runtime monitoring of quantitative signals faces a fundamental trade-off between volatility and over-aggregation: instantaneous observations are noisy, while long-run averages obscure local structure. Localisation measures such as discounted averages offer a principled middle ground, yet remain poorly understood in runtime verification. This paper studies discounted sums from a monitoring perspective, in both deterministic and stochastic settings. We formalize the discounted monitoring problem and show that exact, sound monitoring of discounted sums cannot be achieved with finite memory. To overcome this impossibility, we introduce ε-approximately sound monitoring, deriving explicit bounds on memory and observation requirements. We then extend the framework to stochastic processes via expected discounted sums, defining pointwise and uniform (ε,δ)-soundness notions, establishing statistical optimality, and proving impossibility beyond a precision threshold. We also formalize the resource complexity of deterministic discounted monitoring via affine register machines and prove a tight worst-case lower bound. Finally, we present a specification language for arithmetic expressions over multiple discounted sums with synchronous and asynchronous semantics, and evaluate our approach on practical scenarios including algorithmic fairness.","lang":"eng"}],"ec_funded":1,"alternative_title":["LIPIcs"],"date_updated":"2026-09-22T06:02:06Z","external_id":{"arxiv":["2606.25979"]},"intvolume":"       391","file":[{"access_level":"open_access","checksum":"f7b2e22428344fd7972c54f099df6aba","relation":"main_file","creator":"dernst","content_type":"application/pdf","date_updated":"2026-09-22T05:59:03Z","success":1,"file_id":"22978","date_created":"2026-09-22T05:59:03Z","file_size":997156,"file_name":"2026_LIPIcsCONCUR_Cano.pdf"}],"dataavailabilitystatement":"Software (Source Code): https://github.com/filipcano/monitoringdiscounted-sum-properties [10]\r\narchived at swh:1:dir:cb99396415f279c985cd05206b44320227f64245\r\n","arxiv":1,"das_tickbox":"1","day":"24","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2026","acknowledgement":"This work has been supported by the European Research Council under Grant No.: ERC2020-AdG 101020093 and ERC-2021-AdG 101055412.\r\nFilip Cano: ERC-2020-AdG 101020093\r\nThomas A. Henzinger: ERC-2020-AdG 101020093\r\nKonstantin Kueffner: ERC-2020-AdG 101020093\r\nN. Ege Saraç: ERC-2021-AdG 101055412","citation":{"mla":"Cano Cordoba, Filip, et al. “Monitoring Discounted Sum Properties.” <i>37th International Conference on Concurrency Theory</i>, vol. 391, 22:1-22:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2026.22\">10.4230/LIPIcs.CONCUR.2026.22</a>.","short":"F. Cano Cordoba, T.A. Henzinger, K. Kueffner, N.E. Sarac, in:, 37th International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","chicago":"Cano Cordoba, Filip, Thomas A Henzinger, Konstantin Kueffner, and Naci E Sarac. “Monitoring Discounted Sum Properties.” In <i>37th International Conference on Concurrency Theory</i>, Vol. 391. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2026.22\">https://doi.org/10.4230/LIPIcs.CONCUR.2026.22</a>.","ieee":"F. Cano Cordoba, T. A. Henzinger, K. Kueffner, and N. E. Sarac, “Monitoring discounted sum properties,” in <i>37th International Conference on Concurrency Theory</i>, Liverpool, United Kingdom, 2026, vol. 391.","apa":"Cano Cordoba, F., Henzinger, T. A., Kueffner, K., &#38; Sarac, N. E. (2026). Monitoring discounted sum properties. In <i>37th International Conference on Concurrency Theory</i> (Vol. 391). Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2026.22\">https://doi.org/10.4230/LIPIcs.CONCUR.2026.22</a>","ama":"Cano Cordoba F, Henzinger TA, Kueffner K, Sarac NE. Monitoring discounted sum properties. In: <i>37th International Conference on Concurrency Theory</i>. Vol 391. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2026.22\">10.4230/LIPIcs.CONCUR.2026.22</a>","ista":"Cano Cordoba F, Henzinger TA, Kueffner K, Sarac NE. 2026. Monitoring discounted sum properties. 37th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 391, 22:1-22:19."},"status":"public","_id":"22921","researchdata_availability":"no","oa_version":"Published Version","article_number":"22:1-22:19","title":"Monitoring discounted sum properties","oa":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959774475"]},"type":"conference","doi":"10.4230/LIPIcs.CONCUR.2026.22","publication":"37th International Conference on Concurrency Theory","author":[{"first_name":"Filip","orcid":"0000-0002-0783-904X","id":"708cad98-e86a-11ef-8098-bdae2d7c6af1","last_name":"Cano Cordoba","full_name":"Cano Cordoba, Filip"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","orcid":"0000-0002-2985-7724","first_name":"Thomas A"},{"first_name":"Konstantin","orcid":"0000-0001-8974-2542","id":"8121a2d0-dc85-11ea-9058-af578f3b4515","last_name":"Kueffner","full_name":"Kueffner, Konstantin"},{"last_name":"Sarac","id":"8C6B42F8-C8E6-11E9-A03A-F2DCE5697425","full_name":"Sarac, Naci E","first_name":"Naci E"}],"conference":{"start_date":"2026-09-01","end_date":"2026-09-04","name":"CONCUR: Conference on Concurrency Theory","location":"Liverpool, United Kingdom"},"corr_author":"1","scopus_import":"1","project":[{"call_identifier":"H2020","name":"Vigilant Algorithmic Monitoring of Software","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093"}],"quality_controlled":"1","article_processing_charge":"Yes","supplementarymaterial":"no","date_created":"2026-09-13T22:01:54Z","month":"08","publication_status":"published","volume":391,"language":[{"iso":"eng"}],"department":[{"_id":"ToHe"},{"_id":"GradSch"}]},{"article_number":"6:1-6:7","publication_identifier":{"isbn":["9783959774475"],"issn":["1868-8969"]},"title":"A look back at strategy logic","oa":1,"doi":"10.4230/LIPIcs.CONCUR.2026.6","type":"conference","publication":"37th International Conference on Concurrency Theory","author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"orcid":"0000-0002-2985-7724","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","full_name":"Henzinger, Thomas A"},{"full_name":"Piterman, Nir","last_name":"Piterman","first_name":"Nir"}],"corr_author":"1","conference":{"end_date":"2026-09-04","name":"CONCUR: Conference on Concurrency Theory","location":"Liverpool, United Kingdom","start_date":"2026-09-01"},"scopus_import":"1","project":[{"grant_number":"COE12","name":"Bilateral Artificial Intelligence (Chatterjee)","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee"},{"grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020"},{"grant_number":"101020093","call_identifier":"H2020","name":"Vigilant Algorithmic Monitoring of Software","_id":"62781420-2b32-11ec-9570-8d9b63373d4d"},{"name":"Interface Theory for Security and Privacy","_id":"34a1b658-11ca-11ed-8bc3-c75229f0241e","grant_number":"F8502"}],"quality_controlled":"1","date_created":"2026-09-13T22:01:54Z","supplementarymaterial":"no","article_processing_charge":"Yes","month":"08","language":[{"iso":"eng"}],"volume":391,"department":[{"_id":"KrCh"},{"_id":"ToHe"}],"publication_status":"published","OA_place":"publisher","ddc":["000"],"date_published":"2026-08-24T00:00:00Z","has_accepted_license":"1","OA_type":"gold","fulldoi":"https://doi.org/10.4230/LIPIcs.CONCUR.2026.6","keyword":["Strategy Logic","Games","Automata"],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2026-09-22T05:53:16Z","abstract":[{"text":"In this note, we recall the history and our motivation behind the development of Strategy Logic and we discuss some of the work that ensued from its introduction.","lang":"eng"}],"ec_funded":1,"alternative_title":["LIPIcs"],"date_updated":"2026-09-22T05:54:30Z","file":[{"file_name":"2026_LIPIcsCONCUR_Chatterjee.pdf","file_size":517651,"date_created":"2026-09-22T05:53:16Z","success":1,"file_id":"22977","date_updated":"2026-09-22T05:53:16Z","content_type":"application/pdf","creator":"dernst","access_level":"open_access","checksum":"f3995df175701f56a702bdb012e4f710","relation":"main_file"}],"intvolume":"       391","das_tickbox":"0","day":"24","citation":{"short":"K. Chatterjee, T.A. Henzinger, N. Piterman, in:, 37th International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.","mla":"Chatterjee, Krishnendu, et al. “A Look Back at Strategy Logic.” <i>37th International Conference on Concurrency Theory</i>, vol. 391, 6:1-6:7, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2026.6\">10.4230/LIPIcs.CONCUR.2026.6</a>.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Nir Piterman. “A Look Back at Strategy Logic.” In <i>37th International Conference on Concurrency Theory</i>, Vol. 391. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2026.6\">https://doi.org/10.4230/LIPIcs.CONCUR.2026.6</a>.","apa":"Chatterjee, K., Henzinger, T. A., &#38; Piterman, N. (2026). A look back at strategy logic. In <i>37th International Conference on Concurrency Theory</i> (Vol. 391). Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2026.6\">https://doi.org/10.4230/LIPIcs.CONCUR.2026.6</a>","ieee":"K. Chatterjee, T. A. Henzinger, and N. Piterman, “A look back at strategy logic,” in <i>37th International Conference on Concurrency Theory</i>, Liverpool, United Kingdom, 2026, vol. 391.","ista":"Chatterjee K, Henzinger TA, Piterman N. 2026. A look back at strategy logic. 37th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 391, 6:1-6:7.","ama":"Chatterjee K, Henzinger TA, Piterman N. A look back at strategy logic. In: <i>37th International Conference on Concurrency Theory</i>. Vol 391. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2026.6\">10.4230/LIPIcs.CONCUR.2026.6</a>"},"acknowledgement":" Krishnendu Chatterjee: Supported in part by the Austrian Science Fund (FWF) COE\r\ngrant 10.55776/COE12 and the ERC CoG 863818 (ForM-SMArt).\r\nThomas A. Henzinger: Supported in part by the ERC AdG 101020093 (VAMOS) and the FWF\r\nSFB grant F8502 (SPyCoDe).\r\nNir Piterman: Supported in part by the Swedish research council (VR) project no. 2025-05419 and\r\nthe Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and\r\nAlice Wallenberg Foundation.\r\nAcknowledgements We thank the jury that our paper introducing Strategy Logic at the Conference\r\non Concurrency Theory (CONCUR) 2007 [10] was chosen for a CONCUR Test-of-Time Award at\r\nCONCUR 2026.","year":"2026","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"22922","status":"public","researchdata_availability":"no","oa_version":"Published Version"},{"OA_place":"publisher","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.4230/LIPIcs.ITCS.2025.82","OA_type":"gold","has_accepted_license":"1","date_published":"2025-02-11T00:00:00Z","ddc":["510","000"],"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."}],"file_date_updated":"2025-03-04T09:35:57Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_updated":"2025-09-30T10:42:35Z","alternative_title":["LIPIcs"],"intvolume":"       325","file":[{"success":1,"file_id":"19286","file_name":"2025_LIPIcs_Resch.pdf","date_created":"2025-03-04T09:35:57Z","file_size":898601,"checksum":"df3921ddf1b360b07f43d427fea51242","access_level":"open_access","relation":"main_file","date_updated":"2025-03-04T09:35:57Z","content_type":"application/pdf","creator":"dernst"}],"external_id":{"arxiv":["2309.01800"],"isi":["001532717300082"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2025","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.","citation":{"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>.","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>.","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.","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>","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.","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>"},"isi":1,"day":"11","arxiv":1,"oa_version":"Published Version","_id":"19281","status":"public","article_number":"82","type":"conference","doi":"10.4230/LIPIcs.ITCS.2025.82","title":"Tight bounds on list-decodable and list-recoverable zero-rate codes","oa":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773614"]},"author":[{"first_name":"Nicolas","full_name":"Resch, Nicolas","last_name":"Resch"},{"last_name":"Yuan","full_name":"Yuan, Chen","first_name":"Chen"},{"first_name":"Yihan","orcid":"0000-0002-6465-6258","id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","last_name":"Zhang","full_name":"Zhang, Yihan"}],"publication":"16th Innovations in Theoretical Computer Science Conference","scopus_import":"1","conference":{"name":"ITCS: Innovations in Theoretical Computer Science","end_date":"2025-01-10","location":"New York, NY, United States","start_date":"2025-01-07"},"corr_author":"1","quality_controlled":"1","article_processing_charge":"Yes","date_created":"2025-03-02T23:01:53Z","month":"02","publication_status":"published","language":[{"iso":"eng"}],"volume":325,"department":[{"_id":"MaMo"}]},{"_id":"19858","status":"public","oa_version":"Published Version","arxiv":1,"day":"02","isi":1,"citation":{"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>","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.","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.","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>","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>.","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.","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>."},"year":"2025","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.","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","external_id":{"arxiv":["2310.01149"],"isi":["001532136900004"]},"file":[{"file_id":"19872","success":1,"file_name":"2025_LIPIcs_ElHayek.pdf","file_size":995666,"date_created":"2025-06-23T11:23:29Z","relation":"main_file","access_level":"open_access","checksum":"ad93a1e052adb29d7bfe8bd551bab193","date_updated":"2025-06-23T11:23:29Z","content_type":"application/pdf","creator":"dernst"}],"intvolume":"       330","date_updated":"2025-09-30T13:37:28Z","alternative_title":["LIPIcs"],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","abstract":[{"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.","lang":"eng"}],"file_date_updated":"2025-06-23T11:23:29Z","ec_funded":1,"ddc":["000"],"OA_type":"gold","date_published":"2025-06-02T00:00:00Z","has_accepted_license":"1","fulldoi":"https://doi.org/10.4230/LIPIcs.SAND.2025.4","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"OA_place":"publisher","department":[{"_id":"MoHe"}],"language":[{"iso":"eng"}],"volume":330,"publication_status":"published","month":"06","date_created":"2025-06-22T22:02:06Z","article_processing_charge":"No","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"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"}],"quality_controlled":"1","corr_author":"1","conference":{"location":"Liverpool, United Kingdom","name":"SAND: Symposium on Algorithmic Foundations of Dynamic Networks","end_date":"2025-06-11","start_date":"2025-06-09"},"scopus_import":"1","publication":"4th Symposium on Algorithmic Foundations of Dynamic Networks","author":[{"first_name":"Antoine","orcid":"0000-0003-4268-7368","full_name":"El-Hayek, Antoine","last_name":"El-Hayek","id":"888a098e-fcac-11ee-aff7-d347be57b725"},{"first_name":"Kathrin","full_name":"Hanauer, Kathrin","last_name":"Hanauer"},{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773683"]},"oa":1,"title":"On b-matching and fully-dynamic maximum k-edge coloring","doi":"10.4230/LIPIcs.SAND.2025.4","type":"conference","article_number":"4"},{"status":"public","_id":"20253","oa_version":"Published Version","isi":1,"arxiv":1,"day":"18","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"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.","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>","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.","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>","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>.","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>."},"year":"2025","acknowledgement":"This work was supported in part by the ERC-2020-AdG 101020093.","external_id":{"isi":["001570540800021"],"arxiv":["2506.0515"]},"intvolume":"       348","file":[{"relation":"main_file","access_level":"open_access","checksum":"9d4054058757a73477e6015b10ed6996","creator":"dernst","content_type":"application/pdf","date_updated":"2025-09-03T10:01:53Z","file_id":"20282","success":1,"date_created":"2025-09-03T10:01:53Z","file_size":1257397,"file_name":"2025_CONCUR_HenzingerT.pdf"}],"date_updated":"2025-12-01T12:36:52Z","alternative_title":["LIPIcs"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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"}],"date_published":"2025-08-18T00:00:00Z","OA_type":"gold","has_accepted_license":"1","ddc":["000"],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.4230/LIPIcs.CONCUR.2025.21","OA_place":"publisher","publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"ToHe"}],"volume":348,"month":"08","article_processing_charge":"No","date_created":"2025-08-31T22:01:32Z","project":[{"_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software","call_identifier":"H2020","grant_number":"101020093"}],"quality_controlled":"1","conference":{"location":"Aarhus, Denmark","end_date":"2025-08-29","name":"CONCUR: Conference on Concurrency Theory","start_date":"2025-08-26"},"corr_author":"1","scopus_import":"1","publication":"36th International Conference on Concurrency Theory","author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","full_name":"Henzinger, Thomas A","first_name":"Thomas A","orcid":"0000-0002-2985-7724"},{"first_name":"Pavol","last_name":"Kebis","id":"2e0132b3-4e98-11ef-b275-cf7281c2802a","full_name":"Kebis, Pavol"},{"last_name":"Mazzocchi","id":"b26baa86-3308-11ec-87b0-8990f34baa85","full_name":"Mazzocchi, Nicolas Adrien","first_name":"Nicolas Adrien"},{"first_name":"Naci E","full_name":"Sarac, Naci E","last_name":"Sarac","id":"8C6B42F8-C8E6-11E9-A03A-F2DCE5697425"}],"title":"Quantitative language automata","oa":1,"publication_identifier":{"isbn":["9783959773898"],"issn":["1868-8969"]},"type":"conference","doi":"10.4230/LIPIcs.CONCUR.2025.21","article_number":"21"},{"oa_version":"Published Version","_id":"20290","status":"public","year":"2025","citation":{"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>.","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>","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>","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."},"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. ","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"day":"20","file":[{"relation":"main_file","checksum":"9bc6b8e537662d371d2a27444cbc0b75","access_level":"open_access","date_updated":"2025-09-08T07:11:12Z","content_type":"application/pdf","creator":"dernst","file_id":"20306","success":1,"file_name":"2025_MFCS_Brice.pdf","date_created":"2025-09-08T07:11:12Z","file_size":1149694}],"intvolume":"       345","external_id":{"arxiv":["2502.0531"]},"alternative_title":["LIPIcs"],"date_updated":"2025-09-08T07:15:40Z","ec_funded":1,"abstract":[{"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.","lang":"eng"}],"file_date_updated":"2025-09-08T07:11:12Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.4230/LIPIcs.MFCS.2025.30","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"ddc":["000"],"OA_type":"gold","has_accepted_license":"1","date_published":"2025-08-20T00:00:00Z","OA_place":"publisher","department":[{"_id":"ToHe"}],"volume":345,"language":[{"iso":"eng"}],"publication_status":"published","month":"08","date_created":"2025-09-07T22:01:32Z","article_processing_charge":"Yes","quality_controlled":"1","project":[{"grant_number":"101020093","call_identifier":"H2020","name":"Vigilant Algorithmic Monitoring of Software","_id":"62781420-2b32-11ec-9570-8d9b63373d4d"}],"scopus_import":"1","corr_author":"1","conference":{"location":"Warsaw, Poland","end_date":"2025-08-29","name":"MFCS: Mathematical Foundations of Computer Science","start_date":"2025-08-25"},"author":[{"first_name":"Léonard","full_name":"Brice, Léonard","last_name":"Brice"},{"first_name":"Thomas A","orcid":"0000-0002-2985-7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","full_name":"Henzinger, Thomas A"},{"first_name":"K. S.","id":"3807fb92-fdc1-11ee-bb4a-b4d8a431c753","last_name":"Thejaswini","full_name":"Thejaswini, K. S."}],"publication":"50th International Symposium on Mathematical Foundations of Computer Science","doi":"10.4230/LIPIcs.MFCS.2025.30","type":"conference","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773881"]},"oa":1,"title":"Finding equilibria: Simpler for pessimists, simplest for optimists","article_number":"30"},{"_id":"20291","status":"public","oa_version":"Published Version","day":"20","arxiv":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","acknowledgement":"This work is a part of project VAMOS that has received funding from the European Research Council (ERC), grant agreement No 101020093.","year":"2025","citation":{"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.","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>","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.","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>","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>.","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."},"external_id":{"arxiv":["2502.12872"]},"intvolume":"       345","file":[{"success":1,"file_id":"20305","date_created":"2025-09-08T06:56:56Z","file_size":1009644,"file_name":"2025_MFCS_HenzingerT.pdf","checksum":"6068b772aba6cb0d01f3e5a90abed973","access_level":"open_access","relation":"main_file","creator":"dernst","date_updated":"2025-09-08T06:56:56Z","content_type":"application/pdf"}],"date_updated":"2025-09-08T07:06:11Z","alternative_title":["LIPIcs"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"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"}],"file_date_updated":"2025-09-08T06:56:56Z","date_published":"2025-08-20T00:00:00Z","OA_type":"gold","has_accepted_license":"1","ddc":["000"],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.4230/LIPIcs.MFCS.2025.57","OA_place":"publisher","publication_status":"published","volume":345,"language":[{"iso":"eng"}],"department":[{"_id":"ToHe"}],"month":"08","article_processing_charge":"No","date_created":"2025-09-07T22:01:32Z","project":[{"grant_number":"101020093","call_identifier":"H2020","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software"}],"quality_controlled":"1","conference":{"start_date":"2025-08-25","name":"MFCS: Mathematical Foundations of Computer Science","end_date":"2025-08-29","location":"Warsaw, Poland"},"corr_author":"1","scopus_import":"1","publication":"50th International Symposium on Mathematical Foundations of Computer Science","author":[{"orcid":"0000-0002-2985-7724","first_name":"Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","full_name":"Henzinger, Thomas A"},{"last_name":"Prakash","full_name":"Prakash, Aditya","first_name":"Aditya"},{"id":"3807fb92-fdc1-11ee-bb4a-b4d8a431c753","last_name":"Thejaswini","full_name":"Thejaswini, K. S.","first_name":"K. S."}],"oa":1,"title":"Resolving nondeterminism with randomness","publication_identifier":{"isbn":["9783959773881"],"issn":["1868-8969"]},"type":"conference","doi":"10.4230/LIPIcs.MFCS.2025.57","article_number":"57"},{"has_accepted_license":"1","date_published":"2025-10-01T00:00:00Z","OA_type":"gold","ddc":["000"],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2025.2","OA_place":"publisher","alternative_title":["LIPIcs"],"date_updated":"2025-10-27T08:00:13Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2025-10-27T07:57:00Z","abstract":[{"text":"We give an introduction into differential privacy in the dynamic setting, called the continual observation setting.","lang":"eng"}],"intvolume":"       351","file":[{"relation":"main_file","checksum":"094e0466d90664fbea397b469a60acbb","access_level":"open_access","date_updated":"2025-10-27T07:57:00Z","content_type":"application/pdf","creator":"dernst","file_id":"20541","success":1,"file_name":"2025_LIPIcs.ESA_Henzinger.pdf","file_size":770227,"date_created":"2025-10-27T07:57:00Z"}],"_id":"20533","status":"public","oa_version":"Published Version","day":"01","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"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.","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>.","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>","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>","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."},"year":"2025","title":"Securing dynamic data: A primer on differentially private data structures","oa":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773959"]},"type":"conference","doi":"10.4230/LIPIcs.ESA.2025.2","article_number":"2","conference":{"start_date":"2025-09-15","location":"Warsaw, Poland","end_date":"2025-09-17","name":"ESA: European Symposium on Algorithms"},"corr_author":"1","scopus_import":"1","publication":"33rd Annual European Symposium on Algorithms","author":[{"orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"first_name":"Roodabeh","last_name":"Safavi Hemami","id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","full_name":"Safavi Hemami, Roodabeh"}],"article_processing_charge":"No","date_created":"2025-10-26T23:01:34Z","quality_controlled":"1","publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"MoHe"}],"volume":351,"month":"10"},{"OA_place":"publisher","ddc":["000"],"date_published":"2025-10-01T00:00:00Z","OA_type":"gold","has_accepted_license":"1","fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2025.36","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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"}],"ec_funded":1,"file_date_updated":"2025-10-27T08:03:36Z","date_updated":"2025-10-27T08:05:46Z","external_id":{"arxiv":["2509.05157"]},"file":[{"checksum":"d2daf9a467e96fb5e7084a8a85321776","access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_updated":"2025-10-27T08:03:36Z","creator":"dernst","success":1,"file_id":"20542","file_name":"2025_LIPIcs.ESA_HenzingerM.pdf","date_created":"2025-10-27T08:03:36Z","file_size":934846}],"intvolume":"       351","day":"01","arxiv":1,"citation":{"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.","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>","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.","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>.","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."},"year":"2025","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.","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"20534","status":"public","oa_version":"Published Version","article_number":"36","publication_identifier":{"isbn":["9783959773959"],"issn":["1868-8969"]},"oa":1,"title":"Efficient contractions of dynamic graphs - with applications","doi":"10.4230/LIPIcs.ESA.2025.36","type":"conference","publication":"33rd Annual European Symposium on Algorithms","author":[{"first_name":"Monika H","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Evangelos","id":"4c7f9625-dbbc-11ee-9d86-bdcc2db5a949","last_name":"Kosinas","full_name":"Kosinas, Evangelos"},{"last_name":"Münk","full_name":"Münk, Robin","first_name":"Robin"},{"first_name":"Harald","full_name":"Räcke, Harald","last_name":"Räcke"}],"corr_author":"1","conference":{"start_date":"2025-09-15","end_date":"2025-09-17","name":"ESA: European Symposium on Algorithms","location":"Warsaw, Poland"},"scopus_import":"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"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms","grant_number":"Z00422"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982"}],"quality_controlled":"1","date_created":"2025-10-26T23:01:34Z","article_processing_charge":"No","month":"10","volume":351,"department":[{"_id":"MoHe"}],"language":[{"iso":"eng"}],"publication_status":"published"},{"alternative_title":["LIPIcs"],"date_updated":"2025-10-27T07:02:06Z","file_date_updated":"2025-10-27T06:58:43Z","abstract":[{"lang":"eng","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."}],"ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2025.91","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"ddc":["000"],"date_published":"2025-10-01T00:00:00Z","has_accepted_license":"1","OA_type":"gold","OA_place":"publisher","oa_version":"Published Version","status":"public","_id":"20535","year":"2025","citation":{"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>.","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>.","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>","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.","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>","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."},"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.","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"day":"01","file":[{"content_type":"application/pdf","date_updated":"2025-10-27T06:58:43Z","creator":"dernst","relation":"main_file","checksum":"19146e935b5b6ad5d33c8d08280ad8e7","access_level":"open_access","file_name":"2025_LIPIcs.ESA_Dhulipala.pdf","date_created":"2025-10-27T06:58:43Z","file_size":870317,"file_id":"20539","success":1}],"intvolume":"       351","external_id":{"arxiv":["2508.02182"]},"scopus_import":"1","corr_author":"1","conference":{"start_date":"2025-09-15","location":"Warsaw, Poland","name":"ESA: European Symposium on Algorithms","end_date":"2025-09-17"},"author":[{"first_name":"Laxman","last_name":"Dhulipala","full_name":"Dhulipala, Laxman"},{"full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530"},{"first_name":"George Z.","last_name":"Li","full_name":"Li, George Z."},{"full_name":"Liu, Quanquan C.","last_name":"Liu","first_name":"Quanquan C."},{"full_name":"Sricharan, A. R.","last_name":"Sricharan","first_name":"A. R."},{"first_name":"Leqi","full_name":"Zhu, Leqi","id":"a2117c59-cee4-11ed-b9d0-874ecf0f8ac5","last_name":"Zhu"}],"publication":"33rd Annual European Symposium on Algorithms","doi":"10.4230/LIPIcs.ESA.2025.91","type":"conference","publication_identifier":{"isbn":["9783959773959"],"issn":["1868-8969"]},"oa":1,"title":"Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism","article_number":"91","department":[{"_id":"MoHe"}],"volume":351,"language":[{"iso":"eng"}],"publication_status":"published","month":"10","date_created":"2025-10-26T23:01:35Z","article_processing_charge":"No","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"},{"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"}]},{"OA_place":"publisher","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.4230/LIPIcs.WADS.2025.47","OA_type":"gold","has_accepted_license":"1","date_published":"2025-08-29T00:00:00Z","ddc":["000"],"abstract":[{"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.","lang":"eng"}],"ec_funded":1,"file_date_updated":"2025-10-27T07:09:41Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LIPIcs"],"date_updated":"2025-10-27T07:10:49Z","intvolume":"       349","file":[{"content_type":"application/pdf","date_updated":"2025-10-27T07:09:41Z","creator":"dernst","access_level":"open_access","checksum":"196af33762831a78e87f4f95ecd8677b","relation":"main_file","file_name":"2025_LIPIcs.WADS_Safavi.pdf","file_size":1081870,"date_created":"2025-10-27T07:09:41Z","success":1,"file_id":"20540"}],"external_id":{"arxiv":["2303.04722"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2025","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.","citation":{"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>","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.","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.","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>","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>.","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."},"arxiv":1,"day":"29","oa_version":"Published Version","status":"public","_id":"20536","article_number":"47","type":"conference","doi":"10.4230/LIPIcs.WADS.2025.47","oa":1,"title":"B-Treaps revised: Write efficient randomized block search trees with high load","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773980"]},"author":[{"id":"72ed2640-8972-11ed-ae7b-f9c81ec75154","last_name":"Safavi Hemami","full_name":"Safavi Hemami, Roodabeh","first_name":"Roodabeh"},{"first_name":"Martin P.","full_name":"Seybold, Martin P.","last_name":"Seybold"}],"publication":"19th International Symposium on Algorithms and Data Structures","scopus_import":"1","conference":{"start_date":"2025-08-11","end_date":"2025-08-15","name":"WADS: Algorithms and Data Structures Symposium","location":"Toronto, Canada"},"corr_author":"1","quality_controlled":"1","project":[{"grant_number":"101019564","call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms","grant_number":"Z00422"},{"grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"article_processing_charge":"No","date_created":"2025-10-26T23:01:35Z","month":"08","publication_status":"published","department":[{"_id":"MoHe"}],"volume":349,"language":[{"iso":"eng"}]},{"date_updated":"2026-04-15T08:45:18Z","alternative_title":["LIPIcs"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","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."}],"file_date_updated":"2025-11-04T08:19:02Z","OA_type":"gold","has_accepted_license":"1","date_published":"2025-10-06T00:00:00Z","ddc":["000"],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.4230/LIPIcs.AFT.2025.16","OA_place":"publisher","_id":"20587","status":"public","oa_version":"Published Version","day":"06","arxiv":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","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.","year":"2025","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>","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.","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.","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>","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>.","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>."},"external_id":{"arxiv":["2508.01448"]},"intvolume":"       354","file":[{"creator":"dernst","date_updated":"2025-11-04T08:19:02Z","content_type":"application/pdf","access_level":"open_access","checksum":"b638adcd4fbffa77116c35393e165eb7","relation":"main_file","file_size":1061847,"date_created":"2025-11-04T08:19:02Z","file_name":"2025_LIPIcsAFT_Baig.pdf","success":1,"file_id":"20598"}],"conference":{"start_date":"2025-10-08","location":"Pittsburgh, PA, United States","name":"AFT: Conference on Advances in Financial Technologies","end_date":"2025-10-10"},"corr_author":"1","scopus_import":"1","publication":"7th Conference on Advances in Financial Technologies","author":[{"first_name":"Mirza Ahad","full_name":"Baig, Mirza Ahad","last_name":"Baig","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425"},{"first_name":"Christoph Ullrich","last_name":"Günther","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1","full_name":"Günther, Christoph Ullrich"},{"orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"title":"Nakamoto consensus from multiple resources","oa":1,"publication_identifier":{"isbn":["9783959774000"],"issn":["1868-8969"]},"type":"conference","doi":"10.4230/LIPIcs.AFT.2025.16","main_file_link":[{"url":"https://eprint.iacr.org/2025/1410","open_access":"1"}],"article_number":"16","publication_status":"published","volume":354,"department":[{"_id":"KrPi"}],"language":[{"iso":"eng"}],"month":"10","article_processing_charge":"Yes","date_created":"2025-11-02T23:01:34Z","project":[{"grant_number":"F8512","_id":"34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f","name":"Security and Privacy by Design for Complex Systems"},{"name":"Security and Privacy by Design for Complex Systems","_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1","grant_number":"F8509"}],"quality_controlled":"1","related_material":{"record":[{"relation":"dissertation_contains","id":"21651","status":"public"}]}},{"file":[{"relation":"main_file","checksum":"8e3d1594365df60163d9df22158a37b1","access_level":"open_access","creator":"dernst","date_updated":"2026-03-09T11:51:59Z","content_type":"application/pdf","file_id":"21418","success":1,"file_size":1130069,"date_created":"2026-03-09T11:51:59Z","file_name":"2025_DISC_Chatterjee.pdf"}],"intvolume":"       356","external_id":{"cryptoeprintid":["2025/1484"],"arxiv":["2508.14524"]},"oa_version":"Published Version","status":"public","_id":"21412","citation":{"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.","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>","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.","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>","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>.","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>."},"year":"2025","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).","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","day":"22","arxiv":1,"fulldoi":"https://doi.org/10.4230/LIPIcs.DISC.2025.23","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"ddc":["000"],"has_accepted_license":"1","OA_type":"gold","date_published":"2025-10-22T00:00:00Z","OA_place":"publisher","alternative_title":["LIPIcs"],"date_updated":"2026-09-16T07:27:09Z","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."}],"file_date_updated":"2026-03-09T11:51:59Z","ec_funded":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2026-03-08T23:01:46Z","article_processing_charge":"No","quality_controlled":"1","project":[{"grant_number":"863818","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"},{"_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","name":"Bilateral Artificial Intelligence (Chatterjee)","grant_number":"COE12"}],"language":[{"iso":"eng"}],"department":[{"_id":"KrCh"}],"volume":356,"publication_status":"published","month":"10","doi":"10.4230/LIPIcs.DISC.2025.23","type":"conference","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959774024"]},"title":"Boosting payment channel network liquidity with topology optimization and transaction selection","oa":1,"article_number":"23","scopus_import":"1","conference":{"start_date":"2025-10-27","location":"Berlin, Germany","end_date":"2025-10-31","name":"DISC: Symposium on Distributed Computing"},"author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Křišťan, Jan Matyáš","last_name":"Křišťan","first_name":"Jan Matyáš"},{"first_name":"Stefan","last_name":"Schmid","full_name":"Schmid, Stefan"},{"id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","last_name":"Svoboda","full_name":"Svoboda, Jakub","first_name":"Jakub","orcid":"0000-0002-1419-3267"},{"orcid":"0009-0001-3676-4809","first_name":"Michelle X","full_name":"Yeo, Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","last_name":"Yeo"}],"cryptoeprintid":1,"publication":"39th International Symposium on Distributed Computing"},{"quality_controlled":"1","project":[{"grant_number":"788183","name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"grant_number":"Z00342","name":"Mathematics, Computer Science","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"I02979-N35"},{"name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411"},{"_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","name":"Learning and triangulating manifolds via collapses","grant_number":"M03073"}],"date_created":"2024-06-16T22:01:06Z","supplementarymaterial":"no","article_processing_charge":"No","month":"06","department":[{"_id":"HeEd"}],"language":[{"iso":"eng"}],"volume":293,"publication_status":"published","article_number":"69","doi":"10.4230/LIPIcs.SoCG.2024.69","type":"conference","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773164"]},"oa":1,"title":"The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms","author":[{"full_name":"Kourimska, Hana","last_name":"Kourimska","id":"D9B8E14C-3C26-11EA-98F5-1F833DDC885E","orcid":"0000-0001-7841-0091","first_name":"Hana"},{"last_name":"Lieutier","full_name":"Lieutier, André","first_name":"André"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","last_name":"Wintraecken","full_name":"Wintraecken, Mathijs","first_name":"Mathijs","orcid":"0000-0002-7472-2220"}],"publication":"40th International Symposium on Computational Geometry","scopus_import":"1","conference":{"location":"Athens, Greece","name":"SoCG: Symposium on Computational Geometry","end_date":"2024-06-14"},"file":[{"relation":"main_file","access_level":"open_access","checksum":"b40ff456c19294adb5d9613fcfd751c6","creator":"dernst","date_updated":"2024-06-17T08:33:40Z","content_type":"application/pdf","file_id":"17150","success":1,"file_size":1612558,"date_created":"2024-06-17T08:33:40Z","file_name":"2024_LIPICS_Kourimska.pdf"}],"intvolume":"       293","external_id":{"arxiv":["2212.01118"]},"year":"2024","acknowledgement":"This research has been supported by the European Research Council (ERC), grant No. 788183, by the Wittgenstein Prize, Austrian Science Fund (FWF), grant No. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian Science Fund (FWF), grant No. I 02979-N35.\r\nSupported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411, the Austrian science fund (FWF) grant No. M-3073, and the welcome package from IDEX of the Université Cô d'Azur.\r\nWe are greatly indebted to Fred Chazal for sharing his insights. We further thank Erin Chambers, Christopher Fillmore, and Elizabeth Stephenson for early discussions and all members of the Edelsbrunner group (Institute of Science and Technology Austria) and the Datashape team (Inria) for the atmosphere in which this research was conducted.","citation":{"ista":"Kourimska H, Lieutier A, Wintraecken M. 2024. The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 293, 69.","ama":"Kourimska H, Lieutier A, Wintraecken M. The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms. In: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.69\">10.4230/LIPIcs.SoCG.2024.69</a>","ieee":"H. Kourimska, A. Lieutier, and M. Wintraecken, “The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms,” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293.","apa":"Kourimska, H., Lieutier, A., &#38; Wintraecken, M. (2024). The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms. In <i>40th International Symposium on Computational Geometry</i> (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.69\">https://doi.org/10.4230/LIPIcs.SoCG.2024.69</a>","chicago":"Kourimska, Hana, André Lieutier, and Mathijs Wintraecken. “The Medial Axis of Any Closed Bounded Set Is Lipschitz Stable with Respect to the Hausdorff Distance Under Ambient Diffeomorphisms.” In <i>40th International Symposium on Computational Geometry</i>, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.69\">https://doi.org/10.4230/LIPIcs.SoCG.2024.69</a>.","short":"H. Kourimska, A. Lieutier, M. Wintraecken, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","mla":"Kourimska, Hana, et al. “The Medial Axis of Any Closed Bounded Set Is Lipschitz Stable with Respect to the Hausdorff Distance Under Ambient Diffeomorphisms.” <i>40th International Symposium on Computational Geometry</i>, vol. 293, 69, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.69\">10.4230/LIPIcs.SoCG.2024.69</a>."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"day":"01","das_tickbox":"0","oa_version":"Published Version","researchdata_availability":"no","_id":"17144","status":"public","fulldoi":"https://doi.org/10.4230/LIPIcs.SoCG.2024.69","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"ddc":["510"],"date_published":"2024-06-01T00:00:00Z","has_accepted_license":"1","ec_funded":1,"file_date_updated":"2024-06-17T08:33:40Z","abstract":[{"lang":"eng","text":"We prove that the medial axis of closed sets is Hausdorff stable in the following sense: Let 𝒮 ⊆ ℝ^d be a fixed closed set that contains a bounding sphere. That is, the bounding sphere is part of the set 𝒮. Consider the space of C^{1,1} diffeomorphisms of ℝ^d to itself, which keep the bounding sphere invariant. The map from this space of diffeomorphisms (endowed with a Banach norm) to the space of closed subsets of ℝ^d (endowed with the Hausdorff distance), mapping a diffeomorphism F to the closure of the medial axis of F(𝒮), is Lipschitz. This extends a previous stability result of Chazal and Soufflet on the stability of the medial axis of C² manifolds under C² ambient diffeomorphisms."}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","alternative_title":["LIPIcs"],"date_updated":"2026-10-02T11:46:39Z"},{"external_id":{"arxiv":["2310.14801"]},"file":[{"success":1,"file_id":"17152","file_name":"2024_LIPICS_Edelsbrunner.pdf","date_created":"2024-06-17T08:46:33Z","file_size":766562,"access_level":"open_access","checksum":"5442d44fb89d77477a87668d6e61aac9","relation":"main_file","content_type":"application/pdf","date_updated":"2024-06-17T08:46:33Z","creator":"dernst"}],"intvolume":"       293","arxiv":1,"day":"01","das_tickbox":"0","year":"2024","acknowledgement":"The first author is supported by the European Research Council (ERC), grant no. 788183, and by the DFG Collaborative Research Center TRR 109, Austrian Science Fund (FWF), grant no. {I 02979-N35.} The second author is supported by the European Research Council (ERC), grant \"GeoScape\" and by the Hungarian Science Foundation (NKFIH), grant K-131529. Both authors are supported by the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.\r\nThe authors thank Matt Kahle for communicating the question about extremal Čech complexes, Ben Schweinhart for early discussions on the linked circles construction in three dimensions, and Gábor Tardos for helpful remarks and suggestions.","citation":{"chicago":"Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.” In <i>40th International Symposium on Computational Geometry</i>, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.53\">https://doi.org/10.4230/LIPIcs.SoCG.2024.53</a>.","short":"H. Edelsbrunner, J. Pach, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","mla":"Edelsbrunner, Herbert, and János Pach. “Maximum Betti Numbers of Čech Complexes.” <i>40th International Symposium on Computational Geometry</i>, vol. 293, 53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.53\">10.4230/LIPIcs.SoCG.2024.53</a>.","ama":"Edelsbrunner H, Pach J. Maximum Betti numbers of Čech complexes. In: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.53\">10.4230/LIPIcs.SoCG.2024.53</a>","ista":"Edelsbrunner H, Pach J. 2024. Maximum Betti numbers of Čech complexes. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 293, 53.","ieee":"H. Edelsbrunner and J. Pach, “Maximum Betti numbers of Čech complexes,” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293.","apa":"Edelsbrunner, H., &#38; Pach, J. (2024). Maximum Betti numbers of Čech complexes. In <i>40th International Symposium on Computational Geometry</i> (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.53\">https://doi.org/10.4230/LIPIcs.SoCG.2024.53</a>"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"17146","researchdata_availability":"no","status":"public","oa_version":"Published Version","ddc":["510"],"has_accepted_license":"1","date_published":"2024-06-01T00:00:00Z","fulldoi":"https://doi.org/10.4230/LIPIcs.SoCG.2024.53","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ec_funded":1,"file_date_updated":"2024-06-17T08:46:33Z","abstract":[{"text":"The Upper Bound Theorem for convex polytopes implies that the p-th Betti number of the Čech complex of any set of N points in ℝ^d and any radius satisfies β_p = O(N^m), with m = min{p+1, ⌈d/2⌉}. We construct sets in even and odd dimensions, which prove that this upper bound is asymptotically tight. For example, we describe a set of N = 2(n+1) points in ℝ³ and two radii such that the first Betti number of the Čech complex at one radius is (n+1)² - 1, and the second Betti number of the Čech complex at the other radius is n². In particular, there is an arrangement of n contruent balls in ℝ³ that enclose a quadratic number of voids, which answers a long-standing open question in computational geometry.","lang":"eng"}],"alternative_title":["LIPIcs"],"date_updated":"2026-10-02T11:48:01Z","project":[{"grant_number":"788183","call_identifier":"H2020","name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"grant_number":"I02979-N35","name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"Mathematics, Computer Science","grant_number":"Z00342"}],"related_material":{"record":[{"status":"public","id":"20657","relation":"later_version"}]},"quality_controlled":"1","date_created":"2024-06-16T22:01:06Z","supplementarymaterial":"no","article_processing_charge":"No","month":"06","language":[{"iso":"eng"}],"department":[{"_id":"HeEd"}],"volume":293,"publication_status":"published","article_number":"53","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773164"]},"oa":1,"title":"Maximum Betti numbers of Čech complexes","doi":"10.4230/LIPIcs.SoCG.2024.53","type":"conference","publication":"40th International Symposium on Computational Geometry","author":[{"last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","orcid":"0000-0002-9823-6833"},{"full_name":"Pach, János","id":"E62E3130-B088-11EA-B919-BF823C25FEA4","last_name":"Pach","first_name":"János"}],"conference":{"location":"Athens, Greece","end_date":"2024-06-14","name":"SoCG: Symposium on Computational Geometry","start_date":"2024-06-11"},"scopus_import":"1"},{"article_number":"76","type":"conference","doi":"10.4230/LIPIcs.SoCG.2024.76","title":"Grid peeling of parabolas","oa":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773164"]},"author":[{"first_name":"Günter","full_name":"Rote, Günter","last_name":"Rote"},{"full_name":"Rüber, Moritz","last_name":"Rüber","first_name":"Moritz"},{"id":"f86f7148-b140-11ec-9577-95435b8df824","last_name":"Saghafian","full_name":"Saghafian, Morteza","first_name":"Morteza"}],"publication":"40th International Symposium on Computational Geometry","scopus_import":"1","conference":{"end_date":"2024-06-14","name":"SoCG: Symposium on Computational Geometry","location":"Athens, Greece","start_date":"2024-06-11"},"quality_controlled":"1","article_processing_charge":"No","date_created":"2024-06-16T22:01:06Z","supplementarymaterial":"no","month":"06","publication_status":"published","language":[{"iso":"eng"}],"volume":293,"department":[{"_id":"HeEd"}],"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"fulldoi":"https://doi.org/10.4230/LIPIcs.SoCG.2024.76","date_published":"2024-06-01T00:00:00Z","has_accepted_license":"1","ddc":["510"],"abstract":[{"lang":"eng","text":"Grid peeling is the process of repeatedly removing the convex hull vertices of the grid points that lie inside a given convex curve. It has been conjectured that, for a more and more refined grid, grid peeling converges to a continuous process, the affine curve-shortening flow, which deforms the curve based on the curvature. We prove this conjecture for one class of curves, parabolas with a vertical axis, and we determine the value of the constant factor in the formula that relates the two processes."}],"file_date_updated":"2024-06-17T08:40:04Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_updated":"2026-10-02T11:47:18Z","alternative_title":["LIPIcs"],"intvolume":"       293","file":[{"creator":"dernst","date_updated":"2024-06-17T08:40:04Z","content_type":"application/pdf","relation":"main_file","checksum":"fbad1de06383a6b7e8a1cb3e8c7205ce","access_level":"open_access","file_size":1430896,"date_created":"2024-06-17T08:40:04Z","file_name":"2024_LIPICS_Rote.pdf","file_id":"17151","success":1}],"external_id":{"arxiv":["2402.15787"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","citation":{"mla":"Rote, Günter, et al. “Grid Peeling of Parabolas.” <i>40th International Symposium on Computational Geometry</i>, vol. 293, 76, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.76\">10.4230/LIPIcs.SoCG.2024.76</a>.","short":"G. Rote, M. Rüber, M. Saghafian, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"Rote, Günter, Moritz Rüber, and Morteza Saghafian. “Grid Peeling of Parabolas.” In <i>40th International Symposium on Computational Geometry</i>, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.76\">https://doi.org/10.4230/LIPIcs.SoCG.2024.76</a>.","ieee":"G. Rote, M. Rüber, and M. Saghafian, “Grid peeling of parabolas,” in <i>40th International Symposium on Computational Geometry</i>, Athens, Greece, 2024, vol. 293.","apa":"Rote, G., Rüber, M., &#38; Saghafian, M. (2024). Grid peeling of parabolas. In <i>40th International Symposium on Computational Geometry</i> (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.76\">https://doi.org/10.4230/LIPIcs.SoCG.2024.76</a>","ama":"Rote G, Rüber M, Saghafian M. Grid peeling of parabolas. In: <i>40th International Symposium on Computational Geometry</i>. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2024.76\">10.4230/LIPIcs.SoCG.2024.76</a>","ista":"Rote G, Rüber M, Saghafian M. 2024. Grid peeling of parabolas. 40th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 293, 76."},"acknowledgement":"Part of this work was done while G.R. enjoyed the hospitality of the Institute of Science and Technology Austria (ISTA) as a visiting professor during his sabbatical in the winter semester 2022/23.","year":"2024","das_tickbox":"0","arxiv":1,"day":"01","oa_version":"Published Version","_id":"17145","researchdata_availability":"no","status":"public"}]