--- OA_place: publisher OA_type: gold _id: '22617' 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." 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" alternative_title: - LIPIcs article_number: 23:1-23:26 article_processing_charge: No arxiv: 1 author: - first_name: Leonard J full_name: Brice, Leonard J id: ce3b3409-db6c-11f0-aa64-ad678f7fd937 last_name: Brice - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000-0002-2985-7724 - first_name: K. S. full_name: Thejaswini, K. S. last_name: Thejaswini citation: ama: 'Brice LJ, Henzinger TA, Thejaswini KS. Dicey games: Shared sources of randomness in distributed systems. In: 41st Annual Symposium on Logic in Computer Science. Vol 380. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.LICS.2026.23' apa: 'Brice, L. J., Henzinger, T. A., & Thejaswini, K. S. (2026). Dicey games: Shared sources of randomness in distributed systems. In 41st Annual Symposium on Logic in Computer Science (Vol. 380). Lisbon, Portugal: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.LICS.2026.23' chicago: 'Brice, Leonard J, Thomas A Henzinger, and K. S. Thejaswini. “Dicey Games: Shared Sources of Randomness in Distributed Systems.” In 41st Annual Symposium on Logic in Computer Science, Vol. 380. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.LICS.2026.23.' ieee: 'L. J. Brice, T. A. Henzinger, and K. S. Thejaswini, “Dicey games: Shared sources of randomness in distributed systems,” in 41st Annual Symposium on Logic in Computer Science, Lisbon, Portugal, 2026, vol. 380.' 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.' mla: 'Brice, Leonard J., et al. “Dicey Games: Shared Sources of Randomness in Distributed Systems.” 41st Annual Symposium on Logic in Computer Science, vol. 380, 23:1-23:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.LICS.2026.23.' 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. conference: end_date: 2026-07-23 location: Lisbon, Portugal name: 'LICS: Logic in Computer Science' start_date: 2026-07-20 corr_author: '1' das_tickbox: '0' date_created: 2026-08-02T22:01:52Z date_published: 2026-07-09T00:00:00Z date_updated: 2026-08-03T07:03:28Z day: '09' ddc: - '000' department: - _id: ToHe doi: 10.4230/LIPIcs.LICS.2026.23 ec_funded: 1 external_id: arxiv: - '2601.18303' file: - access_level: open_access checksum: 5d0ff4d267565188a8b4c7502e1bd243 content_type: application/pdf creator: dernst date_created: 2026-08-03T07:02:30Z date_updated: 2026-08-03T07:02:30Z file_id: '22625' file_name: 2026_LIPICSLICS_Brice.pdf file_size: 919708 relation: main_file success: 1 file_date_updated: 2026-08-03T07:02:30Z has_accepted_license: '1' intvolume: ' 380' keyword: - Concurrent games - Shared randomness - Topology - Algebraic Geometry language: - iso: eng license: https://creativecommons.org/licenses/by/4.0/ month: '07' oa: 1 oa_version: Published Version project: - _id: 62781420-2b32-11ec-9570-8d9b63373d4d call_identifier: H2020 grant_number: '101020093' name: Vigilant Algorithmic Monitoring of Software publication: 41st Annual Symposium on Logic in Computer Science publication_identifier: isbn: - '9783959774345' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' researchdata_availability: no scopus_import: '1' status: public supplementarymaterial: no title: 'Dicey games: Shared sources of randomness in distributed systems' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 380 year: '2026' ... --- OA_place: publisher OA_type: gold _id: '21412' 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 \U0001D4AA(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 \U0001D4AA(√p). We complement our theoretical analysis with an empirical study of our assumptions and approach in the context of the Lightning Network." 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)." alternative_title: - LIPIcs article_number: '23' article_processing_charge: No arxiv: 1 author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Jan Matyáš full_name: Křišťan, Jan Matyáš last_name: Křišťan - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid - first_name: Jakub full_name: Svoboda, Jakub id: 130759D2-D7DD-11E9-87D2-DE0DE6697425 last_name: Svoboda orcid: 0000-0002-1419-3267 - first_name: Michelle X full_name: Yeo, Michelle X id: 2D82B818-F248-11E8-B48F-1D18A9856A87 last_name: Yeo orcid: 0009-0001-3676-4809 citation: 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: 39th International Symposium on Distributed Computing. Vol 356. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.DISC.2025.23' apa: 'Chatterjee, K., Křišťan, J. M., Schmid, S., Svoboda, J., & Yeo, M. X. (2025). Boosting payment channel network liquidity with topology optimization and transaction selection. In 39th International Symposium on Distributed Computing (Vol. 356). Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2025.23' 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 39th International Symposium on Distributed Computing, Vol. 356. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.DISC.2025.23. ieee: K. Chatterjee, J. M. Křišťan, S. Schmid, J. Svoboda, and M. X. Yeo, “Boosting payment channel network liquidity with topology optimization and transaction selection,” in 39th International Symposium on Distributed Computing, Berlin, Germany, 2025, vol. 356. 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.' mla: Chatterjee, Krishnendu, et al. “Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection.” 39th International Symposium on Distributed Computing, vol. 356, 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.DISC.2025.23. 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. conference: end_date: 2025-10-31 location: Berlin, Germany name: 'DISC: Symposium on Distributed Computing' start_date: 2025-10-27 date_created: 2026-03-08T23:01:46Z date_published: 2025-10-22T00:00:00Z date_updated: 2026-03-09T11:52:58Z day: '22' ddc: - '000' department: - _id: KrCh doi: 10.4230/LIPIcs.DISC.2025.23 ec_funded: 1 external_id: arxiv: - '2508.14524' file: - access_level: open_access checksum: 8e3d1594365df60163d9df22158a37b1 content_type: application/pdf creator: dernst date_created: 2026-03-09T11:51:59Z date_updated: 2026-03-09T11:51:59Z file_id: '21418' file_name: 2025_DISC_Chatterjee.pdf file_size: 1130069 relation: main_file success: 1 file_date_updated: 2026-03-09T11:51:59Z has_accepted_license: '1' intvolume: ' 356' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2025/1484.pdf month: '10' oa: 1 oa_version: Published Version project: - _id: 0599E47C-7A3F-11EA-A408-12923DDC885E call_identifier: H2020 grant_number: '863818' name: 'Formal Methods for Stochastic Models: Algorithms and Applications' publication: 39th International Symposium on Distributed Computing publication_identifier: isbn: - '9783959774024' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Boosting payment channel network liquidity with topology optimization and transaction selection tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 356 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '19281' 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 \U0001D49E ⊆ [q]ⁿ is (p,\U0001D4C1,L)-list-recoverable if for all tuples of input lists (Y₁,… ,Y_n) with each Y_i ⊆ [q] and |Y_i| = \U0001D4C1, the number of codewords c ∈ \U0001D49E 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 \U0001D4C1 = 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,\U0001D4C1,L) with the property that for all ε > 0 (a) there exist positive-rate (p_*-ε,\U0001D4C1,L)-list-recoverable codes, and (b) any (p_*+ε,\U0001D4C1,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 |\U0001D49E| ≥ (1/(ε))^O(q^L).\r\nOur contribution in this work is to show that for all choices of q,\U0001D4C1 and L with q ≥ 3, any (p_*+ε,\U0001D4C1,L)-list-recoverable code must have size O_{q,\U0001D4C1,L}(1/ε), and furthermore this upper bound is complemented by a matching lower bound Ω_{q,\U0001D4C1,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." 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." alternative_title: - LIPIcs article_number: '82' article_processing_charge: Yes arxiv: 1 author: - first_name: Nicolas full_name: Resch, Nicolas last_name: Resch - first_name: Chen full_name: Yuan, Chen last_name: Yuan - first_name: Yihan full_name: Zhang, Yihan id: 2ce5da42-b2ea-11eb-bba5-9f264e9d002c last_name: Zhang orcid: 0000-0002-6465-6258 citation: ama: 'Resch N, Yuan C, Zhang Y. Tight bounds on list-decodable and list-recoverable zero-rate codes. In: 16th Innovations in Theoretical Computer Science Conference. Vol 325. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.ITCS.2025.82' apa: 'Resch, N., Yuan, C., & Zhang, Y. (2025). Tight bounds on list-decodable and list-recoverable zero-rate codes. In 16th Innovations in Theoretical Computer Science Conference (Vol. 325). New York, NY, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITCS.2025.82' chicago: Resch, Nicolas, Chen Yuan, and Yihan Zhang. “Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes.” In 16th Innovations in Theoretical Computer Science Conference, Vol. 325. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.ITCS.2025.82. ieee: N. Resch, C. Yuan, and Y. Zhang, “Tight bounds on list-decodable and list-recoverable zero-rate codes,” in 16th Innovations in Theoretical Computer Science Conference, New York, NY, United States, 2025, vol. 325. 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.' mla: Resch, Nicolas, et al. “Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes.” 16th Innovations in Theoretical Computer Science Conference, vol. 325, 82, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.ITCS.2025.82. short: N. Resch, C. Yuan, Y. Zhang, in:, 16th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. conference: end_date: 2025-01-10 location: New York, NY, United States name: 'ITCS: Innovations in Theoretical Computer Science' start_date: 2025-01-07 corr_author: '1' date_created: 2025-03-02T23:01:53Z date_published: 2025-02-11T00:00:00Z date_updated: 2025-09-30T10:42:35Z day: '11' ddc: - '510' - '000' department: - _id: MaMo doi: 10.4230/LIPIcs.ITCS.2025.82 external_id: arxiv: - '2309.01800' isi: - '001532717300082' file: - access_level: open_access checksum: df3921ddf1b360b07f43d427fea51242 content_type: application/pdf creator: dernst date_created: 2025-03-04T09:35:57Z date_updated: 2025-03-04T09:35:57Z file_id: '19286' file_name: 2025_LIPIcs_Resch.pdf file_size: 898601 relation: main_file success: 1 file_date_updated: 2025-03-04T09:35:57Z has_accepted_license: '1' intvolume: ' 325' isi: 1 language: - iso: eng month: '02' oa: 1 oa_version: Published Version publication: 16th Innovations in Theoretical Computer Science Conference publication_identifier: isbn: - '9783959773614' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Tight bounds on list-decodable and list-recoverable zero-rate codes tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 volume: 325 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '19858' abstract: - lang: eng text: "Given a graph G that undergoes a sequence of edge insertions and deletions, we study the Maximum k-Edge Coloring problem (MkEC): Having access to k different colors, color as many edges of G as possible such that no two adjacent edges share the same color. While this problem is different from simply maintaining a b-matching with b = k, the two problems are related. However, maximum b-matching can be solved efficiently in the static setting, whereas MkEC is NP-hard and even APX-hard for k ≥ 2. \r\nWe present new results on both problems: For b-matching, we show a new integrality gap result and we adapt Wajc’s matching sparsification scheme [David Wajc, 2020] for the case where b is a constant.\r\nUsing these as basis, we give three new algorithms for the dynamic MkEC problem: Our MatchO algorithm builds on the dynamic (2+ε)-approximation algorithm of Bhattacharya, Gupta, and Mohan [Sayan Bhattacharya et al., 2017] for b-matching and achieves a (2+ε)(k+1)/k-approximation in O(poly(log n, ε^-1)) update time against an oblivious adversary. Our MatchA algorithm builds on the dynamic (7+ε)-approximation algorithm by Bhattacharya, Henzinger, and Italiano [Sayan Bhattacharya et al., 2015] for fractional b-matching and achieves a (7+ε)(3k+3)/(3k-1)-approximation in O(poly(log n, ε^-1)) update time against an adaptive adversary. Moreover, our reductions use the dynamic b-matching algorithm as a black box, so any future improvement in the approximation ratio for dynamic b-matching will automatically translate into a better approximation ratio for our algorithms. Finally, we present a greedy algorithm with O(Δ+k) update time, which guarantees a 2.16 approximation factor." 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." alternative_title: - LIPIcs article_number: '4' article_processing_charge: No arxiv: 1 author: - first_name: Antoine full_name: El-Hayek, Antoine id: 888a098e-fcac-11ee-aff7-d347be57b725 last_name: El-Hayek orcid: 0000-0003-4268-7368 - first_name: Kathrin full_name: Hanauer, Kathrin last_name: Hanauer - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 citation: ama: 'El-Hayek A, Hanauer K, Henzinger M. On b-matching and fully-dynamic maximum k-edge coloring. In: 4th Symposium on Algorithmic Foundations of Dynamic Networks. Vol 330. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.SAND.2025.4' apa: 'El-Hayek, A., Hanauer, K., & Henzinger, M. (2025). On b-matching and fully-dynamic maximum k-edge coloring. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (Vol. 330). Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SAND.2025.4' chicago: El-Hayek, Antoine, Kathrin Hanauer, and Monika Henzinger. “On B-Matching and Fully-Dynamic Maximum k-Edge Coloring.” In 4th Symposium on Algorithmic Foundations of Dynamic Networks, Vol. 330. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.SAND.2025.4. ieee: A. El-Hayek, K. Hanauer, and M. Henzinger, “On b-matching and fully-dynamic maximum k-edge coloring,” in 4th Symposium on Algorithmic Foundations of Dynamic Networks, Liverpool, United Kingdom, 2025, vol. 330. ista: 'El-Hayek A, Hanauer K, Henzinger M. 2025. On b-matching and fully-dynamic maximum k-edge coloring. 4th Symposium on Algorithmic Foundations of Dynamic Networks. SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 330, 4.' mla: El-Hayek, Antoine, et al. “On B-Matching and Fully-Dynamic Maximum k-Edge Coloring.” 4th Symposium on Algorithmic Foundations of Dynamic Networks, vol. 330, 4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.SAND.2025.4. 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. conference: end_date: 2025-06-11 location: Liverpool, United Kingdom name: 'SAND: Symposium on Algorithmic Foundations of Dynamic Networks' start_date: 2025-06-09 corr_author: '1' date_created: 2025-06-22T22:02:06Z date_published: 2025-06-02T00:00:00Z date_updated: 2025-09-30T13:37:28Z day: '02' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.SAND.2025.4 ec_funded: 1 external_id: arxiv: - '2310.01149' isi: - '001532136900004' file: - access_level: open_access checksum: ad93a1e052adb29d7bfe8bd551bab193 content_type: application/pdf creator: dernst date_created: 2025-06-23T11:23:29Z date_updated: 2025-06-23T11:23:29Z file_id: '19872' file_name: 2025_LIPIcs_ElHayek.pdf file_size: 995666 relation: main_file success: 1 file_date_updated: 2025-06-23T11:23:29Z has_accepted_license: '1' intvolume: ' 330' isi: 1 language: - iso: eng month: '06' oa: 1 oa_version: Published Version project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _id: 34def286-11ca-11ed-8bc3-da5948e1613c grant_number: Z00422 name: Efficient algorithms - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer publication: 4th Symposium on Algorithmic Foundations of Dynamic Networks publication_identifier: isbn: - '9783959773683' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: On b-matching and fully-dynamic maximum k-edge coloring tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 volume: 330 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '20253' abstract: - lang: eng text: "A quantitative word automaton (QWA) defines a function from infinite words to values. For example, every infinite run of a limit-average QWA \U0001D49C obtains a mean payoff, and every word w ∈ Σ^ω is assigned the maximal mean payoff obtained by nondeterministic runs of \U0001D49C 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 \U0001D49C, the infimum aggregator maps each language L ⊆ Σ^ω to the greatest lower bound assigned by \U0001D49C 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 \U0001D538 and an implementation G, we ask for the value that \U0001D538 assigns to G. In the nonemptiness (resp. universality) problem, given a QLA \U0001D538 and a value k, we ask whether \U0001D538 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." acknowledgement: This work was supported in part by the ERC-2020-AdG 101020093. alternative_title: - LIPIcs article_number: '21' article_processing_charge: No arxiv: 1 author: - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000-0002-2985-7724 - first_name: Pavol full_name: Kebis, Pavol id: 2e0132b3-4e98-11ef-b275-cf7281c2802a last_name: Kebis - first_name: Nicolas Adrien full_name: Mazzocchi, Nicolas Adrien id: b26baa86-3308-11ec-87b0-8990f34baa85 last_name: Mazzocchi - first_name: Naci E full_name: Sarac, Naci E id: 8C6B42F8-C8E6-11E9-A03A-F2DCE5697425 last_name: Sarac citation: ama: 'Henzinger TA, Kebis P, Mazzocchi NA, Sarac NE. Quantitative language automata. In: 36th International Conference on Concurrency Theory. Vol 348. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.CONCUR.2025.21' apa: 'Henzinger, T. A., Kebis, P., Mazzocchi, N. A., & Sarac, N. E. (2025). Quantitative language automata. In 36th International Conference on Concurrency Theory (Vol. 348). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2025.21' chicago: Henzinger, Thomas A, Pavol Kebis, Nicolas Adrien Mazzocchi, and Naci E Sarac. “Quantitative Language Automata.” In 36th International Conference on Concurrency Theory, Vol. 348. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.CONCUR.2025.21. ieee: T. A. Henzinger, P. Kebis, N. A. Mazzocchi, and N. E. Sarac, “Quantitative language automata,” in 36th International Conference on Concurrency Theory, Aarhus, Denmark, 2025, vol. 348. 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.' mla: Henzinger, Thomas A., et al. “Quantitative Language Automata.” 36th International Conference on Concurrency Theory, vol. 348, 21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.CONCUR.2025.21. 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. conference: end_date: 2025-08-29 location: Aarhus, Denmark name: 'CONCUR: Conference on Concurrency Theory' start_date: 2025-08-26 corr_author: '1' date_created: 2025-08-31T22:01:32Z date_published: 2025-08-18T00:00:00Z date_updated: 2025-12-01T12:36:52Z day: '18' ddc: - '000' department: - _id: ToHe doi: 10.4230/LIPIcs.CONCUR.2025.21 ec_funded: 1 external_id: arxiv: - '2506.0515' isi: - '001570540800021' file: - access_level: open_access checksum: 9d4054058757a73477e6015b10ed6996 content_type: application/pdf creator: dernst date_created: 2025-09-03T10:01:53Z date_updated: 2025-09-03T10:01:53Z file_id: '20282' file_name: 2025_CONCUR_HenzingerT.pdf file_size: 1257397 relation: main_file success: 1 file_date_updated: 2025-09-03T10:01:53Z has_accepted_license: '1' intvolume: ' 348' isi: 1 language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: 62781420-2b32-11ec-9570-8d9b63373d4d call_identifier: H2020 grant_number: '101020093' name: Vigilant Algorithmic Monitoring of Software publication: 36th International Conference on Concurrency Theory publication_identifier: isbn: - '9783959773898' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Quantitative language automata tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 348 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '20290' abstract: - lang: eng text: 'We consider equilibria in multiplayer stochastic graph games with terminal-node rewards. In such games, Nash equilibria are defined assuming that each player seeks to maximise their expected payoff, ignoring their aversion or tolerance to risk. We therefore study risk-sensitive equilibria (RSEs), where the expected payoff is replaced by a risk measure. A classical risk measure in the literature is the entropic risk measure, where each player has a real valued parameter capturing their risk-averseness. We introduce the extreme risk measure, which corresponds to extreme cases of entropic risk measure, where players are either extreme optimists or extreme pessimists. Under extreme risk measure, every player is an extremist: an extreme optimist perceives their reward as the maximum payoff that can be achieved with positive probability, while an extreme pessimist expects the minimum payoff achievable with positive probability. We argue that the extreme risk measure, especially in multi-player graph based settings, is particularly relevant as they can model several real life instances such as interactions between secure systems and potential security threats, or distributed controls for safety critical systems. We prove that RSEs defined with the extreme risk measure are guaranteed to exist when all rewards are non-negative. Furthermore, we prove that the problem of deciding whether a given game contains an RSE that generates risk measures within specified intervals is decidable and NP-complete for our extreme risk measure, and even PTIME-complete when all players are extreme optimists, while that same problem is undecidable using the entropic risk measure or even the classical expected payoff. This establishes, to our knowledge, the first decidable fragment for equilibria in simple stochastic games without restrictions on strategy types or number of players.' 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. " alternative_title: - LIPIcs article_number: '30' article_processing_charge: Yes arxiv: 1 author: - first_name: Léonard full_name: Brice, Léonard last_name: Brice - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000-0002-2985-7724 - first_name: K. S. full_name: Thejaswini, K. S. id: 3807fb92-fdc1-11ee-bb4a-b4d8a431c753 last_name: Thejaswini citation: ama: 'Brice L, Henzinger TA, Thejaswini KS. Finding equilibria: Simpler for pessimists, simplest for optimists. In: 50th International Symposium on Mathematical Foundations of Computer Science. Vol 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.MFCS.2025.30' apa: 'Brice, L., Henzinger, T. A., & Thejaswini, K. S. (2025). Finding equilibria: Simpler for pessimists, simplest for optimists. In 50th International Symposium on Mathematical Foundations of Computer Science (Vol. 345). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2025.30' chicago: 'Brice, Léonard, Thomas A Henzinger, and K. S. Thejaswini. “Finding Equilibria: Simpler for Pessimists, Simplest for Optimists.” In 50th International Symposium on Mathematical Foundations of Computer Science, Vol. 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.MFCS.2025.30.' ieee: 'L. Brice, T. A. Henzinger, and K. S. Thejaswini, “Finding equilibria: Simpler for pessimists, simplest for optimists,” in 50th International Symposium on Mathematical Foundations of Computer Science, Warsaw, Poland, 2025, vol. 345.' 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.' mla: 'Brice, Léonard, et al. “Finding Equilibria: Simpler for Pessimists, Simplest for Optimists.” 50th International Symposium on Mathematical Foundations of Computer Science, vol. 345, 30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.MFCS.2025.30.' short: L. Brice, T.A. Henzinger, K.S. Thejaswini, in:, 50th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. conference: end_date: 2025-08-29 location: Warsaw, Poland name: 'MFCS: Mathematical Foundations of Computer Science' start_date: 2025-08-25 corr_author: '1' date_created: 2025-09-07T22:01:32Z date_published: 2025-08-20T00:00:00Z date_updated: 2025-09-08T07:15:40Z day: '20' ddc: - '000' department: - _id: ToHe doi: 10.4230/LIPIcs.MFCS.2025.30 ec_funded: 1 external_id: arxiv: - '2502.0531' file: - access_level: open_access checksum: 9bc6b8e537662d371d2a27444cbc0b75 content_type: application/pdf creator: dernst date_created: 2025-09-08T07:11:12Z date_updated: 2025-09-08T07:11:12Z file_id: '20306' file_name: 2025_MFCS_Brice.pdf file_size: 1149694 relation: main_file success: 1 file_date_updated: 2025-09-08T07:11:12Z has_accepted_license: '1' intvolume: ' 345' language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: 62781420-2b32-11ec-9570-8d9b63373d4d call_identifier: H2020 grant_number: '101020093' name: Vigilant Algorithmic Monitoring of Software publication: 50th International Symposium on Mathematical Foundations of Computer Science publication_identifier: isbn: - '9783959773881' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: 'Finding equilibria: Simpler for pessimists, simplest for optimists' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 345 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '20291' abstract: - lang: eng 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." acknowledgement: This work is a part of project VAMOS that has received funding from the European Research Council (ERC), grant agreement No 101020093. alternative_title: - LIPIcs article_number: '57' article_processing_charge: No arxiv: 1 author: - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000-0002-2985-7724 - first_name: Aditya full_name: Prakash, Aditya last_name: Prakash - first_name: K. S. full_name: Thejaswini, K. S. id: 3807fb92-fdc1-11ee-bb4a-b4d8a431c753 last_name: Thejaswini citation: ama: 'Henzinger TA, Prakash A, Thejaswini KS. Resolving nondeterminism with randomness. In: 50th International Symposium on Mathematical Foundations of Computer Science. Vol 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.MFCS.2025.57' apa: 'Henzinger, T. A., Prakash, A., & Thejaswini, K. S. (2025). Resolving nondeterminism with randomness. In 50th International Symposium on Mathematical Foundations of Computer Science (Vol. 345). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2025.57' chicago: Henzinger, Thomas A, Aditya Prakash, and K. S. Thejaswini. “Resolving Nondeterminism with Randomness.” In 50th International Symposium on Mathematical Foundations of Computer Science, Vol. 345. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.MFCS.2025.57. ieee: T. A. Henzinger, A. Prakash, and K. S. Thejaswini, “Resolving nondeterminism with randomness,” in 50th International Symposium on Mathematical Foundations of Computer Science, Warsaw, Poland, 2025, vol. 345. 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.' mla: Henzinger, Thomas A., et al. “Resolving Nondeterminism with Randomness.” 50th International Symposium on Mathematical Foundations of Computer Science, vol. 345, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.MFCS.2025.57. 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. conference: end_date: 2025-08-29 location: Warsaw, Poland name: 'MFCS: Mathematical Foundations of Computer Science' start_date: 2025-08-25 corr_author: '1' date_created: 2025-09-07T22:01:32Z date_published: 2025-08-20T00:00:00Z date_updated: 2025-09-08T07:06:11Z day: '20' ddc: - '000' department: - _id: ToHe doi: 10.4230/LIPIcs.MFCS.2025.57 ec_funded: 1 external_id: arxiv: - '2502.12872' file: - access_level: open_access checksum: 6068b772aba6cb0d01f3e5a90abed973 content_type: application/pdf creator: dernst date_created: 2025-09-08T06:56:56Z date_updated: 2025-09-08T06:56:56Z file_id: '20305' file_name: 2025_MFCS_HenzingerT.pdf file_size: 1009644 relation: main_file success: 1 file_date_updated: 2025-09-08T06:56:56Z has_accepted_license: '1' intvolume: ' 345' language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: 62781420-2b32-11ec-9570-8d9b63373d4d call_identifier: H2020 grant_number: '101020093' name: Vigilant Algorithmic Monitoring of Software publication: 50th International Symposium on Mathematical Foundations of Computer Science publication_identifier: isbn: - '9783959773881' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Resolving nondeterminism with randomness tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 345 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '20533' abstract: - lang: eng text: We give an introduction into differential privacy in the dynamic setting, called the continual observation setting. alternative_title: - LIPIcs article_number: '2' article_processing_charge: No author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Roodabeh full_name: Safavi Hemami, Roodabeh id: 72ed2640-8972-11ed-ae7b-f9c81ec75154 last_name: Safavi Hemami citation: ama: 'Henzinger M, Safavi Hemami R. Securing dynamic data: A primer on differentially private data structures. In: 33rd Annual European Symposium on Algorithms. Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.ESA.2025.2' apa: 'Henzinger, M., & Safavi Hemami, R. (2025). Securing dynamic data: A primer on differentially private data structures. In 33rd Annual European Symposium on Algorithms (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2025.2' chicago: 'Henzinger, Monika, and Roodabeh Safavi Hemami. “Securing Dynamic Data: A Primer on Differentially Private Data Structures.” In 33rd Annual European Symposium on Algorithms, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.ESA.2025.2.' ieee: 'M. Henzinger and R. Safavi Hemami, “Securing dynamic data: A primer on differentially private data structures,” in 33rd Annual European Symposium on Algorithms, Warsaw, Poland, 2025, vol. 351.' ista: 'Henzinger M, Safavi Hemami R. 2025. Securing dynamic data: A primer on differentially private data structures. 33rd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 351, 2.' mla: 'Henzinger, Monika, and Roodabeh Safavi Hemami. “Securing Dynamic Data: A Primer on Differentially Private Data Structures.” 33rd Annual European Symposium on Algorithms, vol. 351, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.ESA.2025.2.' short: M. Henzinger, R. Safavi Hemami, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. conference: end_date: 2025-09-17 location: Warsaw, Poland name: 'ESA: European Symposium on Algorithms' start_date: 2025-09-15 corr_author: '1' date_created: 2025-10-26T23:01:34Z date_published: 2025-10-01T00:00:00Z date_updated: 2025-10-27T08:00:13Z day: '01' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.ESA.2025.2 file: - access_level: open_access checksum: 094e0466d90664fbea397b469a60acbb content_type: application/pdf creator: dernst date_created: 2025-10-27T07:57:00Z date_updated: 2025-10-27T07:57:00Z file_id: '20541' file_name: 2025_LIPIcs.ESA_Henzinger.pdf file_size: 770227 relation: main_file success: 1 file_date_updated: 2025-10-27T07:57:00Z has_accepted_license: '1' intvolume: ' 351' language: - iso: eng month: '10' oa: 1 oa_version: Published Version publication: 33rd Annual European Symposium on Algorithms publication_identifier: isbn: - '9783959773959' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: 'Securing dynamic data: A primer on differentially private data structures' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 351 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '20534' abstract: - lang: eng 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." 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.' article_number: '36' article_processing_charge: No arxiv: 1 author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Evangelos full_name: Kosinas, Evangelos id: 4c7f9625-dbbc-11ee-9d86-bdcc2db5a949 last_name: Kosinas - first_name: Robin full_name: Münk, Robin last_name: Münk - first_name: Harald full_name: Räcke, Harald last_name: Räcke citation: ama: 'Henzinger M, Kosinas E, Münk R, Räcke H. Efficient contractions of dynamic graphs - with applications. In: 33rd Annual European Symposium on Algorithms. Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.ESA.2025.36' apa: 'Henzinger, M., Kosinas, E., Münk, R., & Räcke, H. (2025). Efficient contractions of dynamic graphs - with applications. In 33rd Annual European Symposium on Algorithms (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2025.36' chicago: Henzinger, Monika, Evangelos Kosinas, Robin Münk, and Harald Räcke. “Efficient Contractions of Dynamic Graphs - with Applications.” In 33rd Annual European Symposium on Algorithms, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.ESA.2025.36. ieee: M. Henzinger, E. Kosinas, R. Münk, and H. Räcke, “Efficient contractions of dynamic graphs - with applications,” in 33rd Annual European Symposium on Algorithms, Warsaw, Poland, 2025, vol. 351. ista: 'Henzinger M, Kosinas E, Münk R, Räcke H. 2025. Efficient contractions of dynamic graphs - with applications. 33rd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms vol. 351, 36.' mla: Henzinger, Monika, et al. “Efficient Contractions of Dynamic Graphs - with Applications.” 33rd Annual European Symposium on Algorithms, vol. 351, 36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.ESA.2025.36. 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. conference: end_date: 2025-09-17 location: Warsaw, Poland name: 'ESA: European Symposium on Algorithms' start_date: 2025-09-15 corr_author: '1' date_created: 2025-10-26T23:01:34Z date_published: 2025-10-01T00:00:00Z date_updated: 2025-10-27T08:05:46Z day: '01' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.ESA.2025.36 ec_funded: 1 external_id: arxiv: - '2509.05157' file: - access_level: open_access checksum: d2daf9a467e96fb5e7084a8a85321776 content_type: application/pdf creator: dernst date_created: 2025-10-27T08:03:36Z date_updated: 2025-10-27T08:03:36Z file_id: '20542' file_name: 2025_LIPIcs.ESA_HenzingerM.pdf file_size: 934846 relation: main_file success: 1 file_date_updated: 2025-10-27T08:03:36Z has_accepted_license: '1' intvolume: ' 351' language: - iso: eng month: '10' oa: 1 oa_version: Published Version project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _id: 34def286-11ca-11ed-8bc3-da5948e1613c grant_number: Z00422 name: Efficient algorithms - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions publication: 33rd Annual European Symposium on Algorithms publication_identifier: isbn: - '9783959773959' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Efficient contractions of dynamic graphs - with applications tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 351 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '20535' 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." 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." alternative_title: - LIPIcs article_number: '91' article_processing_charge: No arxiv: 1 author: - first_name: Laxman full_name: Dhulipala, Laxman last_name: Dhulipala - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: George Z. full_name: Li, George Z. last_name: Li - first_name: Quanquan C. full_name: Liu, Quanquan C. last_name: Liu - first_name: A. R. full_name: Sricharan, A. R. last_name: Sricharan - first_name: Leqi full_name: Zhu, Leqi id: a2117c59-cee4-11ed-b9d0-874ecf0f8ac5 last_name: Zhu citation: 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: 33rd Annual European Symposium on Algorithms. Vol 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.ESA.2025.91' apa: 'Dhulipala, L., Henzinger, M., Li, G. Z., Liu, Q. C., Sricharan, A. R., & Zhu, L. (2025). Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism. In 33rd Annual European Symposium on Algorithms (Vol. 351). Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2025.91' 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 33rd Annual European Symposium on Algorithms, Vol. 351. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.ESA.2025.91. 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 33rd Annual European Symposium on Algorithms, Warsaw, Poland, 2025, vol. 351. 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.' mla: Dhulipala, Laxman, et al. “Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism.” 33rd Annual European Symposium on Algorithms, vol. 351, 91, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.ESA.2025.91. 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. conference: end_date: 2025-09-17 location: Warsaw, Poland name: 'ESA: European Symposium on Algorithms' start_date: 2025-09-15 corr_author: '1' date_created: 2025-10-26T23:01:35Z date_published: 2025-10-01T00:00:00Z date_updated: 2025-10-27T07:02:06Z day: '01' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.ESA.2025.91 ec_funded: 1 external_id: arxiv: - '2508.02182' file: - access_level: open_access checksum: 19146e935b5b6ad5d33c8d08280ad8e7 content_type: application/pdf creator: dernst date_created: 2025-10-27T06:58:43Z date_updated: 2025-10-27T06:58:43Z file_id: '20539' file_name: 2025_LIPIcs.ESA_Dhulipala.pdf file_size: 870317 relation: main_file success: 1 file_date_updated: 2025-10-27T06:58:43Z has_accepted_license: '1' intvolume: ' 351' language: - iso: eng month: '10' oa: 1 oa_version: Published Version project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _id: 34def286-11ca-11ed-8bc3-da5948e1613c grant_number: Z00422 name: Efficient algorithms - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions publication: 33rd Annual European Symposium on Algorithms publication_identifier: isbn: - '9783959773959' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 351 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '20536' abstract: - lang: eng text: "Uniquely represented (UR) data structures represent each logical state with a unique storage state. We study the problem of maintaining a dynamic set of n keys from a totally ordered universe in this context. UR structures are also called \"strongly history independent\" structures in the literature.\r\nWe introduce a two-layer data structure called (α,ε)-Randomized Block Search Tree (RBST) that is uniquely represented and suitable for external memory (EM). Though RBSTs naturally generalize the well-known binary Treaps, several new ideas are needed to analyze the expected search, update, and storage efficiency in terms of block-reads, block-writes, and blocks stored. We prove that searches have O(ε^{-1} + log_α n) block-reads, that dynamic updates perform O(ε^{-1} + log_α(n)/α) block-writes and O(ε^{-2}+(1+(ε^{-1}+log n)/α)log_α n) block-reads, and that (α, ε)-RBSTs have an asymptotic load-factor of at least (1-ε) for every ε ∈ (0,1/2].\r\nThus (α, ε)-RBSTs improve on the known, uniquely represented B-Treap [Golovin; ICALP'09]. Compared with non-UR structures, the RBST is also, to the best of our knowledge, the first external memory structure that is storage-efficient and has a non-amortized, write-efficient update bound." 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." alternative_title: - LIPIcs article_number: '47' article_processing_charge: No arxiv: 1 author: - first_name: Roodabeh full_name: Safavi Hemami, Roodabeh id: 72ed2640-8972-11ed-ae7b-f9c81ec75154 last_name: Safavi Hemami - first_name: Martin P. full_name: Seybold, Martin P. last_name: Seybold citation: ama: 'Safavi Hemami R, Seybold MP. B-Treaps revised: Write efficient randomized block search trees with high load. In: 19th International Symposium on Algorithms and Data Structures. Vol 349. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.WADS.2025.47' apa: 'Safavi Hemami, R., & Seybold, M. P. (2025). B-Treaps revised: Write efficient randomized block search trees with high load. In 19th International Symposium on Algorithms and Data Structures (Vol. 349). Toronto, Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.WADS.2025.47' chicago: 'Safavi Hemami, Roodabeh, and Martin P. Seybold. “B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load.” In 19th International Symposium on Algorithms and Data Structures, Vol. 349. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.WADS.2025.47.' ieee: 'R. Safavi Hemami and M. P. Seybold, “B-Treaps revised: Write efficient randomized block search trees with high load,” in 19th International Symposium on Algorithms and Data Structures, Toronto, Canada, 2025, vol. 349.' ista: 'Safavi Hemami R, Seybold MP. 2025. B-Treaps revised: Write efficient randomized block search trees with high load. 19th International Symposium on Algorithms and Data Structures. WADS: Algorithms and Data Structures Symposium, LIPIcs, vol. 349, 47.' mla: 'Safavi Hemami, Roodabeh, and Martin P. Seybold. “B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load.” 19th International Symposium on Algorithms and Data Structures, vol. 349, 47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.WADS.2025.47.' short: R. Safavi Hemami, M.P. Seybold, in:, 19th International Symposium on Algorithms and Data Structures, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. conference: end_date: 2025-08-15 location: Toronto, Canada name: 'WADS: Algorithms and Data Structures Symposium' start_date: 2025-08-11 corr_author: '1' date_created: 2025-10-26T23:01:35Z date_published: 2025-08-29T00:00:00Z date_updated: 2025-10-27T07:10:49Z day: '29' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.WADS.2025.47 ec_funded: 1 external_id: arxiv: - '2303.04722' file: - access_level: open_access checksum: 196af33762831a78e87f4f95ecd8677b content_type: application/pdf creator: dernst date_created: 2025-10-27T07:09:41Z date_updated: 2025-10-27T07:09:41Z file_id: '20540' file_name: 2025_LIPIcs.WADS_Safavi.pdf file_size: 1081870 relation: main_file success: 1 file_date_updated: 2025-10-27T07:09:41Z has_accepted_license: '1' intvolume: ' 349' language: - iso: eng month: '08' oa: 1 oa_version: Published Version project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _id: 34def286-11ca-11ed-8bc3-da5948e1613c grant_number: Z00422 name: Efficient algorithms - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer publication: 19th International Symposium on Algorithms and Data Structures publication_identifier: isbn: - '9783959773980' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: 'B-Treaps revised: Write efficient randomized block search trees with high load' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 349 year: '2025' ... --- OA_place: publisher OA_type: gold _id: '20587' 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." 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." alternative_title: - LIPIcs article_number: '16' article_processing_charge: Yes arxiv: 1 author: - first_name: Mirza Ahad full_name: Baig, Mirza Ahad id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425 last_name: Baig - first_name: Christoph Ullrich full_name: Günther, Christoph Ullrich id: ec98511c-eb8e-11eb-b029-edd25d7271a1 last_name: Günther - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 citation: ama: 'Baig MA, Günther CU, Pietrzak KZ. Nakamoto consensus from multiple resources. In: 7th Conference on Advances in Financial Technologies. Vol 354. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.AFT.2025.16' apa: 'Baig, M. A., Günther, C. U., & Pietrzak, K. Z. (2025). Nakamoto consensus from multiple resources. In 7th Conference on Advances in Financial Technologies (Vol. 354). Pittsburgh, PA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.AFT.2025.16' chicago: Baig, Mirza Ahad, Christoph Ullrich Günther, and Krzysztof Z Pietrzak. “Nakamoto Consensus from Multiple Resources.” In 7th Conference on Advances in Financial Technologies, Vol. 354. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.AFT.2025.16. ieee: M. A. Baig, C. U. Günther, and K. Z. Pietrzak, “Nakamoto consensus from multiple resources,” in 7th Conference on Advances in Financial Technologies, 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.' mla: Baig, Mirza Ahad, et al. “Nakamoto Consensus from Multiple Resources.” 7th Conference on Advances in Financial Technologies, vol. 354, 16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.AFT.2025.16. 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. conference: end_date: 2025-10-10 location: Pittsburgh, PA, United States name: 'AFT: Conference on Advances in Financial Technologies' start_date: 2025-10-08 corr_author: '1' date_created: 2025-11-02T23:01:34Z date_published: 2025-10-06T00:00:00Z date_updated: 2026-04-15T08:45:18Z day: '06' ddc: - '000' department: - _id: KrPi doi: 10.4230/LIPIcs.AFT.2025.16 external_id: arxiv: - '2508.01448' file: - access_level: open_access checksum: b638adcd4fbffa77116c35393e165eb7 content_type: application/pdf creator: dernst date_created: 2025-11-04T08:19:02Z date_updated: 2025-11-04T08:19:02Z file_id: '20598' file_name: 2025_LIPIcsAFT_Baig.pdf file_size: 1061847 relation: main_file success: 1 file_date_updated: 2025-11-04T08:19:02Z has_accepted_license: '1' intvolume: ' 354' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2025/1410 month: '10' oa: 1 oa_version: Published Version project: - _id: 34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f grant_number: F8512 name: Security and Privacy by Design for Complex Systems - _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1 grant_number: F8509 name: Security and Privacy by Design for Complex Systems publication: 7th Conference on Advances in Financial Technologies publication_identifier: isbn: - '9783959774000' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: record: - id: '21651' relation: dissertation_contains status: public scopus_import: '1' status: public title: Nakamoto consensus from multiple resources tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 354 year: '2025' ... --- _id: '15006' abstract: - lang: eng text: Graphical games are a useful framework for modeling the interactions of (selfish) agents who are connected via an underlying topology and whose behaviors influence each other. They have wide applications ranging from computer science to economics and biology. Yet, even though an agent’s payoff only depends on the actions of their direct neighbors in graphical games, computing the Nash equilibria and making statements about the convergence time of "natural" local dynamics in particular can be highly challenging. In this work, we present a novel approach for classifying complexity of Nash equilibria in graphical games by establishing a connection to local graph algorithms, a subfield of distributed computing. In particular, we make the observation that the equilibria of graphical games are equivalent to locally verifiable labelings (LVL) in graphs; vertex labelings which are verifiable with constant-round local algorithms. This connection allows us to derive novel lower bounds on the convergence time to equilibrium of best-response dynamics in graphical games. Since we establish that distributed convergence can sometimes be provably slow, we also introduce and give bounds on an intuitive notion of "time-constrained" inefficiency of best responses. We exemplify how our results can be used in the implementation of mechanisms that ensure convergence of best responses to a Nash equilibrium. Our results thus also give insight into the convergence of strategy-proof algorithms for graphical games, which is still not well understood. acknowledgement: This work was partially funded by the Academy of Finland, grant 314888, the European Research Council CoG 863818 (ForM-SMArt), and the Austrian Science Fund (FWF) project I 4800-N (ADVISE). LS was supported by the Stochastic Analysis and Application Research Center (SAARC) under National Research Foundation of Korea grant NRF-2019R1A5A1028324. alternative_title: - LIPIcs article_number: '11' article_processing_charge: No arxiv: 1 author: - first_name: Juho full_name: Hirvonen, Juho last_name: Hirvonen - first_name: Laura full_name: Schmid, Laura id: 38B437DE-F248-11E8-B48F-1D18A9856A87 last_name: Schmid orcid: 0000-0002-6978-7329 - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid citation: ama: 'Hirvonen J, Schmid L, Chatterjee K, Schmid S. On the convergence time in graphical games: A locality-sensitive approach. In: 27th International Conference on Principles of Distributed Systems. Vol 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.OPODIS.2023.11' apa: 'Hirvonen, J., Schmid, L., Chatterjee, K., & Schmid, S. (2024). On the convergence time in graphical games: A locality-sensitive approach. In 27th International Conference on Principles of Distributed Systems (Vol. 286). Tokyo, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2023.11' chicago: 'Hirvonen, Juho, Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid. “On the Convergence Time in Graphical Games: A Locality-Sensitive Approach.” In 27th International Conference on Principles of Distributed Systems, Vol. 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.OPODIS.2023.11.' ieee: 'J. Hirvonen, L. Schmid, K. Chatterjee, and S. Schmid, “On the convergence time in graphical games: A locality-sensitive approach,” in 27th International Conference on Principles of Distributed Systems, Tokyo, Japan, 2024, vol. 286.' ista: 'Hirvonen J, Schmid L, Chatterjee K, Schmid S. 2024. On the convergence time in graphical games: A locality-sensitive approach. 27th International Conference on Principles of Distributed Systems. OPODIS: Conference on Principles of Distributed Systems, LIPIcs, vol. 286, 11.' mla: 'Hirvonen, Juho, et al. “On the Convergence Time in Graphical Games: A Locality-Sensitive Approach.” 27th International Conference on Principles of Distributed Systems, vol. 286, 11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.OPODIS.2023.11.' short: J. Hirvonen, L. Schmid, K. Chatterjee, S. Schmid, in:, 27th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. conference: end_date: 2023-12-08 location: Tokyo, Japan name: 'OPODIS: Conference on Principles of Distributed Systems' start_date: 2023-12-06 corr_author: '1' date_created: 2024-02-18T23:01:01Z date_published: 2024-01-18T00:00:00Z date_updated: 2025-12-02T13:38:16Z day: '18' ddc: - '000' department: - _id: KrCh doi: 10.4230/LIPIcs.OPODIS.2023.11 ec_funded: 1 external_id: arxiv: - '2102.13457' isi: - '001585185800011' file: - access_level: open_access checksum: 4fc7eea6e4ba140b904781fc7df868ec content_type: application/pdf creator: dernst date_created: 2024-02-26T09:04:58Z date_updated: 2024-02-26T09:04:58Z file_id: '15028' file_name: 2024_LIPICs_Hirvonen.pdf file_size: 867363 relation: main_file success: 1 file_date_updated: 2024-02-26T09:04:58Z has_accepted_license: '1' intvolume: ' 286' isi: 1 language: - iso: eng month: '01' oa: 1 oa_version: Published Version project: - _id: 0599E47C-7A3F-11EA-A408-12923DDC885E call_identifier: H2020 grant_number: '863818' name: 'Formal Methods for Stochastic Models: Algorithms and Applications' publication: 27th International Conference on Principles of Distributed Systems publication_identifier: isbn: - '9783959773089' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: 'On the convergence time in graphical games: A locality-sensitive approach' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 286 year: '2024' ... --- _id: '15007' abstract: - lang: eng text: Traditional blockchains grant the miner of a block full control not only over which transactions but also their order. This constitutes a major flaw discovered with the introduction of decentralized finance and allows miners to perform MEV attacks. In this paper, we address the issue of sandwich attacks by providing a construction that takes as input a blockchain protocol and outputs a new blockchain protocol with the same security but in which sandwich attacks are not profitable. Furthermore, our protocol is fully decentralized with no trusted third parties or heavy cryptography primitives and carries a linear increase in latency and minimum computation overhead. acknowledgement: "We would like to thank Krzysztof Pietrzak and Jovana Mićić for useful discussions. This work has been funded by the Swiss National Science Foundation (SNSF) under grant agreement Nr. 200021_188443 (Advanced Consensus Protocols).\r\n" alternative_title: - LIPIcs article_number: '12' article_processing_charge: No arxiv: 1 author: - first_name: Orestis full_name: Alpos, Orestis last_name: Alpos - first_name: Ignacio full_name: Amores-Sesar, Ignacio last_name: Amores-Sesar - first_name: Christian full_name: Cachin, Christian last_name: Cachin - first_name: Michelle X full_name: Yeo, Michelle X id: 2D82B818-F248-11E8-B48F-1D18A9856A87 last_name: Yeo orcid: 0009-0001-3676-4809 citation: ama: 'Alpos O, Amores-Sesar I, Cachin C, Yeo MX. Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. In: 27th International Conference on Principles of Distributed Systems. Vol 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.OPODIS.2023.12' apa: 'Alpos, O., Amores-Sesar, I., Cachin, C., & Yeo, M. X. (2024). Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. In 27th International Conference on Principles of Distributed Systems (Vol. 286). Tokyo, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.OPODIS.2023.12' chicago: 'Alpos, Orestis, Ignacio Amores-Sesar, Christian Cachin, and Michelle X Yeo. “Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks.” In 27th International Conference on Principles of Distributed Systems, Vol. 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.OPODIS.2023.12.' ieee: 'O. Alpos, I. Amores-Sesar, C. Cachin, and M. X. Yeo, “Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks,” in 27th International Conference on Principles of Distributed Systems, Tokyo, Japan, 2024, vol. 286.' ista: 'Alpos O, Amores-Sesar I, Cachin C, Yeo MX. 2024. Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. 27th International Conference on Principles of Distributed Systems. OPODIS: Conference on Principles of Distributed Systems, LIPIcs, vol. 286, 12.' mla: 'Alpos, Orestis, et al. “Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks.” 27th International Conference on Principles of Distributed Systems, vol. 286, 12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.OPODIS.2023.12.' short: O. Alpos, I. Amores-Sesar, C. Cachin, M.X. Yeo, in:, 27th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. conference: end_date: 2023-12-08 location: Tokyo, Japan name: 'OPODIS: Conference on Principles of Distributed Systems' start_date: 2023-12-06 corr_author: '1' date_created: 2024-02-18T23:01:02Z date_published: 2024-01-18T00:00:00Z date_updated: 2025-12-02T13:38:53Z day: '18' ddc: - '000' department: - _id: KrPi doi: 10.4230/LIPIcs.OPODIS.2023.12 external_id: arxiv: - '2307.02954' isi: - '001585185800012' file: - access_level: open_access checksum: 2993e810a45e8c8056106834b07aea92 content_type: application/pdf creator: dernst date_created: 2024-02-26T10:16:57Z date_updated: 2024-02-26T10:16:57Z file_id: '15031' file_name: 2024_LIPICs_Alpos.pdf file_size: 1505994 relation: main_file success: 1 file_date_updated: 2024-02-26T10:16:57Z has_accepted_license: '1' intvolume: ' 286' isi: 1 language: - iso: eng month: '01' oa: 1 oa_version: Published Version publication: 27th International Conference on Principles of Distributed Systems publication_identifier: isbn: - '9783959773089' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: 'Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 286 year: '2024' ... --- _id: '15008' abstract: - lang: eng text: "Oblivious routing is a well-studied paradigm that uses static precomputed routing tables for selecting routing paths within a network. Existing oblivious routing schemes with polylogarithmic competitive ratio for general networks are tree-based, in the sense that routing is performed according to a convex combination of trees. However, this restriction to trees leads to a construction that has time quadratic in the size of the network and does not parallelize well. \r\nIn this paper we study oblivious routing schemes based on electrical routing. In particular, we show that general networks with n vertices and m edges admit a routing scheme that has competitive ratio O(log² n) and consists of a convex combination of only O(√m) electrical routings. This immediately leads to an improved construction algorithm with time Õ(m^{3/2}) that can also be implemented in parallel with Õ(√m) depth." acknowledgement: "Monika Henzinger and A. R. Sricharan: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation\r\nprogramme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) project Z\r\n422-N, project I 5982-N, and project P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nHarald Räcke: Research supported by German Research Foundation (DFG), grant 470029389\r\n(FlexNets), 2021-2024.\r\nSushant Sachdeva: SS’s work is supported by an Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant RGPIN-2018-06398 and a Sloan Research Fellowship." alternative_title: - LIPIcs article_number: '55' article_processing_charge: No arxiv: 1 author: - first_name: Gramoz full_name: Goranci, Gramoz last_name: Goranci - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Harald full_name: Räcke, Harald last_name: Räcke - first_name: Sushant full_name: Sachdeva, Sushant last_name: Sachdeva - first_name: A. R. full_name: Sricharan, A. R. last_name: Sricharan citation: ama: 'Goranci G, Henzinger M, Räcke H, Sachdeva S, Sricharan AR. Electrical flows for polylogarithmic competitive oblivious routing. In: 15th Innovations in Theoretical Computer Science Conference. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.ITCS.2024.55' apa: 'Goranci, G., Henzinger, M., Räcke, H., Sachdeva, S., & Sricharan, A. R. (2024). Electrical flows for polylogarithmic competitive oblivious routing. In 15th Innovations in Theoretical Computer Science Conference (Vol. 287). Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITCS.2024.55' chicago: Goranci, Gramoz, Monika Henzinger, Harald Räcke, Sushant Sachdeva, and A. R. Sricharan. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.” In 15th Innovations in Theoretical Computer Science Conference, Vol. 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ITCS.2024.55. ieee: G. Goranci, M. Henzinger, H. Räcke, S. Sachdeva, and A. R. Sricharan, “Electrical flows for polylogarithmic competitive oblivious routing,” in 15th Innovations in Theoretical Computer Science Conference, Berkeley, CA, United States, 2024, vol. 287. ista: 'Goranci G, Henzinger M, Räcke H, Sachdeva S, Sricharan AR. 2024. Electrical flows for polylogarithmic competitive oblivious routing. 15th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 287, 55.' mla: Goranci, Gramoz, et al. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.” 15th Innovations in Theoretical Computer Science Conference, vol. 287, 55, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ITCS.2024.55. short: G. Goranci, M. Henzinger, H. Räcke, S. Sachdeva, A.R. Sricharan, in:, 15th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. conference: end_date: 2024-02-02 location: Berkeley, CA, United States name: 'ITCS: Innovations in Theoretical Computer Science' start_date: 2024-01-30 corr_author: '1' date_created: 2024-02-18T23:01:02Z date_published: 2024-01-24T00:00:00Z date_updated: 2025-09-04T12:06:25Z day: '24' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.ITCS.2024.55 ec_funded: 1 external_id: arxiv: - '2303.02491' isi: - '001300389400055' file: - access_level: open_access checksum: b89716aae6a5599f187897e39de1e53a content_type: application/pdf creator: dernst date_created: 2024-02-26T10:10:48Z date_updated: 2024-02-26T10:10:48Z file_id: '15030' file_name: 2024_LIPICs_Goranci.pdf file_size: 1054754 relation: main_file success: 1 file_date_updated: 2024-02-26T10:10:48Z has_accepted_license: '1' intvolume: ' 287' isi: 1 language: - iso: eng month: '01' oa: 1 oa_version: Published Version project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _id: 34def286-11ca-11ed-8bc3-da5948e1613c grant_number: Z00422 name: Efficient algorithms - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer publication: 15th Innovations in Theoretical Computer Science Conference publication_identifier: isbn: - '9783959773096' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Electrical flows for polylogarithmic competitive oblivious routing tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345 volume: 287 year: '2024' ... --- OA_place: publisher OA_type: gold _id: '17099' abstract: - lang: eng text: "We study two-player zero-sum concurrent stochastic games with finite state and action space played for an infinite number of steps. In every step, the two players simultaneously and independently choose an action. Given the current state and the chosen actions, the next state is obtained according to a stochastic transition function. An objective is a measurable function on plays (or infinite trajectories) of the game, and the value for an objective is the maximal expectation that the player can guarantee against the adversarial player. We consider: (a) stateful-discounted objectives, which are similar to the classical discounted-sum objectives, but states are associated with different discount factors rather than a single discount factor; and (b) parity objectives, which are a canonical representation for ω-regular objectives. For stateful-discounted objectives, given an ordering of the discount factors, the limit value is the limit of the value of the stateful-discounted objectives, as the discount factors approach zero according to the given order.\r\nThe computational problem we consider is the approximation of the value within an arbitrary\r\nadditive error. The above problem is known to be in EXPSPACE for the limit value of statefuldiscounted objectives and in PSPACE for parity objectives. The best-known algorithms for both the above problems are at least exponential time, with an exponential dependence on the number of states and actions. Our main results for the value approximation problem for the limit value of stateful-discounted objectives and parity objectives are as follows: (a) we establish TFNP[NP] complexity; and (b) we present algorithms that improve the dependency on the number of actions in the exponent from linear to logarithmic. In particular, if the number of states is constant, our algorithms run in polynomial time." acknowledgement: "This research was partially supported by ERC CoG 863818 (ForM-SMArt), Austrian\r\nScience Fund (FWF) 10.55776/COE12, and French Agence Nationale de la Recherche (ANR)\r\nANR-21-CE40-0020 (CONVERGENCE project)" alternative_title: - LIPIcs article_number: '5' article_processing_charge: No arxiv: 1 author: - first_name: Ali full_name: Asadi, Ali id: 02d96aae-000e-11ec-b801-cadd0a5eefbb last_name: Asadi - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Raimundo J full_name: Saona Urmeneta, Raimundo J id: BD1DF4C4-D767-11E9-B658-BC13E6697425 last_name: Saona Urmeneta orcid: 0000-0001-5103-038X - first_name: Jakub full_name: Svoboda, Jakub id: 130759D2-D7DD-11E9-87D2-DE0DE6697425 last_name: Svoboda orcid: 0000-0002-1419-3267 citation: ama: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. In: 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Vol 323. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.FSTTCS.2024.5' apa: 'Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., & Svoboda, J. (2024). Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (Vol. 323). Gujarat, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5' chicago: 'Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Jakub Svoboda. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives: Complexity and Algorithms.” In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Vol. 323. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5.' ieee: 'A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and J. Svoboda, “Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms,” in 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Gujarat, India, 2024, vol. 323.' ista: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. 2024. Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 323, 5.' mla: 'Asadi, Ali, et al. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives: Complexity and Algorithms.” 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, vol. 323, 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.FSTTCS.2024.5.' short: A. Asadi, K. Chatterjee, R.J. Saona Urmeneta, J. Svoboda, in:, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. conference: end_date: 2024-12-18 location: Gujarat, India name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science' start_date: 2024-12-16 corr_author: '1' date_created: 2024-06-03T07:44:27Z date_published: 2024-12-05T00:00:00Z date_updated: 2025-12-02T13:40:52Z day: '05' ddc: - '000' department: - _id: KrCh doi: 10.4230/LIPIcs.FSTTCS.2024.5 ec_funded: 1 external_id: arxiv: - '2405.02486' isi: - '001537516500005' file: - access_level: open_access checksum: 5b544ab4692b93300b404435c036ddd4 content_type: application/pdf creator: dernst date_created: 2025-01-08T09:49:31Z date_updated: 2025-01-08T09:49:31Z file_id: '18777' file_name: 2024_LIPIcs_Asadi.pdf file_size: 847960 relation: main_file success: 1 file_date_updated: 2025-01-08T09:49:31Z has_accepted_license: '1' intvolume: ' 323' isi: 1 language: - iso: eng month: '12' oa: 1 oa_version: Published Version project: - _id: 0599E47C-7A3F-11EA-A408-12923DDC885E call_identifier: H2020 grant_number: '863818' name: 'Formal Methods for Stochastic Models: Algorithms and Applications' publication: 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science publication_identifier: isbn: - '9783959773553' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: 'Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms' tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 323 year: '2024' ... --- _id: '17144' abstract: - lang: eng text: "We prove that the medial axis of closed sets is Hausdorff stable in the following sense: Let \U0001D4AE ⊆ ℝ^d be a fixed closed set that contains a bounding sphere. That is, the bounding sphere is part of the set \U0001D4AE. 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(\U0001D4AE), 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." 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." alternative_title: - LIPIcs article_number: '69' article_processing_charge: No arxiv: 1 author: - first_name: Hana full_name: Kourimska, Hana id: D9B8E14C-3C26-11EA-98F5-1F833DDC885E last_name: Kourimska orcid: 0000-0001-7841-0091 - first_name: André full_name: Lieutier, André last_name: Lieutier - first_name: Mathijs full_name: Wintraecken, Mathijs id: 307CFBC8-F248-11E8-B48F-1D18A9856A87 last_name: Wintraecken orcid: 0000-0002-7472-2220 citation: 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: 40th International Symposium on Computational Geometry. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.SoCG.2024.69' apa: '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. In 40th International Symposium on Computational Geometry (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.69' 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 40th International Symposium on Computational Geometry, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.69. 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 40th International Symposium on Computational Geometry, Athens, Greece, 2024, vol. 293. 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.' 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.” 40th International Symposium on Computational Geometry, vol. 293, 69, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.SoCG.2024.69. short: H. Kourimska, A. Lieutier, M. Wintraecken, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. conference: end_date: 2024-06-14 location: Athens, Greece name: 'SoCG: Symposium on Computational Geometry' date_created: 2024-06-16T22:01:06Z date_published: 2024-06-01T00:00:00Z date_updated: 2025-04-15T07:16:58Z day: '01' ddc: - '510' department: - _id: HeEd doi: 10.4230/LIPIcs.SoCG.2024.69 ec_funded: 1 external_id: arxiv: - '2212.01118' file: - access_level: open_access checksum: b40ff456c19294adb5d9613fcfd751c6 content_type: application/pdf creator: dernst date_created: 2024-06-17T08:33:40Z date_updated: 2024-06-17T08:33:40Z file_id: '17150' file_name: 2024_LIPICS_Kourimska.pdf file_size: 1612558 relation: main_file success: 1 file_date_updated: 2024-06-17T08:33:40Z has_accepted_license: '1' intvolume: ' 293' language: - iso: eng month: '06' oa: 1 oa_version: Published Version project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships - _id: fc390959-9c52-11eb-aca3-afa58bd282b2 grant_number: M03073 name: Learning and triangulating manifolds via collapses publication: 40th International Symposium on Computational Geometry publication_identifier: isbn: - '9783959773164' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 293 year: '2024' ... --- _id: '17145' 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. 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. alternative_title: - LIPIcs article_number: '76' article_processing_charge: No arxiv: 1 author: - first_name: Günter full_name: Rote, Günter last_name: Rote - first_name: Moritz full_name: Rüber, Moritz last_name: Rüber - first_name: Morteza full_name: Saghafian, Morteza id: f86f7148-b140-11ec-9577-95435b8df824 last_name: Saghafian citation: ama: 'Rote G, Rüber M, Saghafian M. Grid peeling of parabolas. In: 40th International Symposium on Computational Geometry. Vol 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.SoCG.2024.76' apa: 'Rote, G., Rüber, M., & Saghafian, M. (2024). Grid peeling of parabolas. In 40th International Symposium on Computational Geometry (Vol. 293). Athens, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.76' chicago: Rote, Günter, Moritz Rüber, and Morteza Saghafian. “Grid Peeling of Parabolas.” In 40th International Symposium on Computational Geometry, Vol. 293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.SoCG.2024.76. ieee: G. Rote, M. Rüber, and M. Saghafian, “Grid peeling of parabolas,” in 40th International Symposium on Computational Geometry, Athens, Greece, 2024, vol. 293. 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.' mla: Rote, Günter, et al. “Grid Peeling of Parabolas.” 40th International Symposium on Computational Geometry, vol. 293, 76, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.SoCG.2024.76. short: G. Rote, M. Rüber, M. Saghafian, in:, 40th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. conference: end_date: 2024-06-14 location: Athens, Greece name: 'SoCG: Symposium on Computational Geometry' start_date: 2024-06-11 date_created: 2024-06-16T22:01:06Z date_published: 2024-06-01T00:00:00Z date_updated: 2024-06-17T08:41:56Z day: '01' ddc: - '510' department: - _id: HeEd doi: 10.4230/LIPIcs.SoCG.2024.76 external_id: arxiv: - '2402.15787' file: - access_level: open_access checksum: fbad1de06383a6b7e8a1cb3e8c7205ce content_type: application/pdf creator: dernst date_created: 2024-06-17T08:40:04Z date_updated: 2024-06-17T08:40:04Z file_id: '17151' file_name: 2024_LIPICS_Rote.pdf file_size: 1430896 relation: main_file success: 1 file_date_updated: 2024-06-17T08:40:04Z has_accepted_license: '1' intvolume: ' 293' language: - iso: eng month: '06' oa: 1 oa_version: Published Version publication: 40th International Symposium on Computational Geometry publication_identifier: isbn: - '9783959773164' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Grid peeling of parabolas tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 293 year: '2024' ... --- OA_place: publisher OA_type: gold _id: '18556' abstract: - lang: eng text: Given a finite set, A ⊆ ℝ², and a subset, B ⊆ A, the MST-ratio is the combined length of the minimum spanning trees of B and A⧵B divided by the length of the minimum spanning tree of A. The question of the supremum, over all sets A, of the maximum, over all subsets B, is related to the Steiner ratio, and we prove this sup-max is between 2.154 and 2.427. Restricting ourselves to 2-dimensional lattices, we prove that the sup-max is 2, while the inf-max is 1.25. By some margin the most difficult of these results is the upper bound for the inf-max, which we prove by showing that the hexagonal lattice cannot have MST-ratio larger than 1.25. acknowledgement: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant no. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, "Discretization in Geometry and Dynamics", Austrian Science Fund (FWF), grant no. I 02979-N35. alternative_title: - LIPIcs article_number: '3' article_processing_charge: Yes arxiv: 1 author: - first_name: Sebastiano full_name: Cultrera di Montesano, Sebastiano id: 34D2A09C-F248-11E8-B48F-1D18A9856A87 last_name: Cultrera di Montesano orcid: 0000-0001-6249-0832 - first_name: Ondrej full_name: Draganov, Ondrej id: 2B23F01E-F248-11E8-B48F-1D18A9856A87 last_name: Draganov orcid: 0000-0003-0464-3823 - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Morteza full_name: Saghafian, Morteza id: f86f7148-b140-11ec-9577-95435b8df824 last_name: Saghafian citation: ama: 'Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. The Euclidean MST-ratio for bi-colored lattices. In: 32nd International Symposium on Graph Drawing and Network Visualization. Vol 320. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.GD.2024.3' apa: 'Cultrera di Montesano, S., Draganov, O., Edelsbrunner, H., & Saghafian, M. (2024). The Euclidean MST-ratio for bi-colored lattices. In 32nd International Symposium on Graph Drawing and Network Visualization (Vol. 320). Vienna, Austria: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.GD.2024.3' chicago: Cultrera di Montesano, Sebastiano, Ondrej Draganov, Herbert Edelsbrunner, and Morteza Saghafian. “The Euclidean MST-Ratio for Bi-Colored Lattices.” In 32nd International Symposium on Graph Drawing and Network Visualization, Vol. 320. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.GD.2024.3. ieee: S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, and M. Saghafian, “The Euclidean MST-ratio for bi-colored lattices,” in 32nd International Symposium on Graph Drawing and Network Visualization, Vienna, Austria, 2024, vol. 320. ista: 'Cultrera di Montesano S, Draganov O, Edelsbrunner H, Saghafian M. 2024. The Euclidean MST-ratio for bi-colored lattices. 32nd International Symposium on Graph Drawing and Network Visualization. GD: Graph Drawing and Network Visualization, LIPIcs, vol. 320, 3.' mla: Cultrera di Montesano, Sebastiano, et al. “The Euclidean MST-Ratio for Bi-Colored Lattices.” 32nd International Symposium on Graph Drawing and Network Visualization, vol. 320, 3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.GD.2024.3. short: S. Cultrera di Montesano, O. Draganov, H. Edelsbrunner, M. Saghafian, in:, 32nd International Symposium on Graph Drawing and Network Visualization, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. conference: end_date: 2024-09-20 location: Vienna, Austria name: 'GD: Graph Drawing and Network Visualization' start_date: 2024-09-18 corr_author: '1' date_created: 2024-11-17T23:01:47Z date_published: 2024-10-28T00:00:00Z date_updated: 2025-12-02T13:50:50Z day: '28' ddc: - '510' department: - _id: HeEd doi: 10.4230/LIPIcs.GD.2024.3 ec_funded: 1 external_id: arxiv: - '2403.10204' isi: - '001540278400001' file: - access_level: open_access checksum: 5f9b35e115c3d375e99be78da9054cb4 content_type: application/pdf creator: dernst date_created: 2024-11-18T07:49:25Z date_updated: 2024-11-18T07:49:25Z file_id: '18560' file_name: 2024_LIPIcs_CultreradiMontesano.pdf file_size: 908541 relation: main_file success: 1 file_date_updated: 2024-11-18T07:49:25Z has_accepted_license: '1' intvolume: ' 320' isi: 1 language: - iso: eng month: '10' oa: 1 oa_version: Published Version project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: Mathematics, Computer Science - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication: 32nd International Symposium on Graph Drawing and Network Visualization publication_identifier: isbn: - '9783959773430' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: The Euclidean MST-ratio for bi-colored lattices tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 320 year: '2024' ... --- OA_place: publisher OA_type: gold _id: '18758' abstract: - lang: eng text: 'MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdős bound states that any connected graph on n vertices with m edges contains a cut of size at least m/2+(n-1)/4. Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple connected graphs admits an FPT algorithm, where the parameter k is the difference between the desired cut size c and the lower bound given by the Edwards-Erdős bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run in parameterized linear time, i.e., f(k)⋅ O(m). We improve upon this result in two ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively, graphs with positive integer weights). Secondly, we change the parameter; instead of the difference to the Edwards-Erdős bound, we use the difference to the Poljak-Turzík bound. The Poljak-Turzík bound states that any weighted graph G has a cut of size at least (w(G))/2+(w_MSF(G))/4, where w(G) denotes the total weight of G, and w_MSF(G) denotes the weight of its minimum spanning forest. In connected simple graphs the two bounds are equivalent, but for multigraphs the Poljak-Turzík bound can be larger and thus yield a smaller parameter k. Our algorithm also runs in parameterized linear time, i.e., f(k)⋅ O(m+n).' acknowledgement: "Kalina Petrova: Swiss National Science Foundation, grant no. CRSII5 173721. This project\r\nhas received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413.\r\nSimon Weber: Swiss National Science Foundation under project no. 204320" alternative_title: - LIPIcs article_number: '2' article_processing_charge: Yes arxiv: 1 author: - first_name: Jonas full_name: Lill, Jonas last_name: Lill - first_name: Kalina H full_name: Petrova, Kalina H id: 554ff4e4-f325-11ee-b0c4-a10dbd523381 last_name: Petrova - first_name: Simon full_name: Weber, Simon last_name: Weber citation: ama: 'Lill J, Petrova KH, Weber S. Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. In: 19th International Symposium on Parameterized and Exact Computation. Vol 321. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.IPEC.2024.2' apa: 'Lill, J., Petrova, K. H., & Weber, S. (2024). Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. In 19th International Symposium on Parameterized and Exact Computation (Vol. 321). Egham, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2024.2' chicago: Lill, Jonas, Kalina H Petrova, and Simon Weber. “Linear-Time MaxCut in Multigraphs Parameterized above the Poljak-Turzík Bound.” In 19th International Symposium on Parameterized and Exact Computation, Vol. 321. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.IPEC.2024.2. ieee: J. Lill, K. H. Petrova, and S. Weber, “Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound,” in 19th International Symposium on Parameterized and Exact Computation, Egham, United Kingdom, 2024, vol. 321. ista: 'Lill J, Petrova KH, Weber S. 2024. Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound. 19th International Symposium on Parameterized and Exact Computation. IPEC: Symposium on Parameterized and Exact Computation, LIPIcs, vol. 321, 2.' mla: Lill, Jonas, et al. “Linear-Time MaxCut in Multigraphs Parameterized above the Poljak-Turzík Bound.” 19th International Symposium on Parameterized and Exact Computation, vol. 321, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.IPEC.2024.2. short: J. Lill, K.H. Petrova, S. Weber, in:, 19th International Symposium on Parameterized and Exact Computation, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. conference: end_date: 2024-09-06 location: Egham, United Kingdom name: 'IPEC: Symposium on Parameterized and Exact Computation' start_date: 2024-09-04 corr_author: '1' date_created: 2025-01-05T23:01:57Z date_published: 2024-12-05T00:00:00Z date_updated: 2026-01-05T13:46:07Z day: '05' ddc: - '500' department: - _id: MaKw doi: 10.4230/LIPIcs.IPEC.2024.2 ec_funded: 1 external_id: arxiv: - '2407.01071' isi: - '001534851900002' file: - access_level: open_access checksum: a64b9a0e41f7b867d25cb155825ccd53 content_type: application/pdf creator: dernst date_created: 2025-01-08T09:14:59Z date_updated: 2025-01-08T09:14:59Z file_id: '18775' file_name: 2024_LIPIcs_Lill.pdf file_size: 927326 relation: main_file success: 1 file_date_updated: 2025-01-08T09:14:59Z has_accepted_license: '1' intvolume: ' 321' isi: 1 language: - iso: eng month: '12' oa: 1 oa_version: Published Version project: - _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c call_identifier: H2020 grant_number: '101034413' name: 'IST-BRIDGE: International postdoctoral program' publication: 19th International Symposium on Parameterized and Exact Computation publication_identifier: isbn: - '9783959773539' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: record: - id: '19603' relation: later_version status: public scopus_import: '1' status: public title: Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 321 year: '2024' ...