[{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564"},{"grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions"}],"OA_place":"repository","publication":"Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms","arxiv":1,"year":"2026","publication_identifier":{"eisbn":["9781611978971"],"eissn":["1557-9468"],"issn":["1071-9040"]},"acknowledgement":"Funded by the European union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. 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 DOI 10.55776/I5982. For open access purposes, the author has applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission.","ec_funded":1,"oa":1,"day":"07","doi":"10.1137/1.9781611978971.25","date_published":"2026-01-07T00:00:00Z","intvolume":"      2026","language":[{"iso":"eng"}],"status":"public","article_processing_charge":"No","author":[{"orcid":"0000-0003-4268-7368","id":"888a098e-fcac-11ee-aff7-d347be57b725","last_name":"El-Hayek","full_name":"El-Hayek, Antoine","first_name":"Antoine"},{"last_name":"Henzinger","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H"},{"last_name":"Li","full_name":"Li, Jason","first_name":"Jason"}],"title":"Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time","date_updated":"2026-05-04T11:36:47Z","page":"613-663","oa_version":"Preprint","publisher":"Society for Industrial and Applied Mathematics","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2512.13105","open_access":"1"}],"volume":2026,"OA_type":"green","department":[{"_id":"MoHe"},{"_id":"GradSch"}],"citation":{"short":"A. El-Hayek, M. Henzinger, J. Li, in:, Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2026, pp. 613–663.","ieee":"A. El-Hayek, M. Henzinger, and J. Li, “Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time,” in <i>Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms</i>, Vancouver, Canada, 2026, vol. 2026, pp. 613–663.","apa":"El-Hayek, A., Henzinger, M., &#38; Li, J. (2026). Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time. In <i>Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms</i> (Vol. 2026, pp. 613–663). Vancouver, Canada: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611978971.25\">https://doi.org/10.1137/1.9781611978971.25</a>","ama":"El-Hayek A, Henzinger M, Li J. Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time. In: <i>Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms</i>. Vol 2026. Society for Industrial and Applied Mathematics; 2026:613-663. doi:<a href=\"https://doi.org/10.1137/1.9781611978971.25\">10.1137/1.9781611978971.25</a>","mla":"El-Hayek, Antoine, et al. “Deterministic and Exact Fully-Dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time.” <i>Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms</i>, vol. 2026, Society for Industrial and Applied Mathematics, 2026, pp. 613–63, doi:<a href=\"https://doi.org/10.1137/1.9781611978971.25\">10.1137/1.9781611978971.25</a>.","ista":"El-Hayek A, Henzinger M, Li J. 2026. Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time. Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2026, 613–663.","chicago":"El-Hayek, Antoine, Monika Henzinger, and Jason Li. “Deterministic and Exact Fully-Dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time.” In <i>Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms</i>, 2026:613–63. Society for Industrial and Applied Mathematics, 2026. <a href=\"https://doi.org/10.1137/1.9781611978971.25\">https://doi.org/10.1137/1.9781611978971.25</a>."},"type":"conference","abstract":[{"text":"We present an exact fully-dynamic minimum cut algorithm that runs in 𝑛𝑜⁡(1) deterministic update time when the minimum cut size is at most 2Θ⁡(log3/4−𝑐⁡𝑛) for any 𝑐 >0, improving on the previous algorithm of Jin, Sun, and Thorup (SODA 2024) whose minimum cut size limit is (log⁡𝑛)𝑜⁡(1). Combined with graph sparsification, we obtain the first (1 +𝜖)-approximate fully-dynamic minimum cut algorithm on weighted graphs, for any 𝜖 ≥2−Θ⁡(log3/4−𝑐⁡𝑛), in 𝑛𝑜⁡(1) randomized update time.\r\nOur main technical contribution is a deterministic local minimum cut algorithm, which replaces the randomized LocalKCut procedure from El-Hayek, Henzinger, and Li (SODA 2025).","lang":"eng"}],"quality_controlled":"1","month":"01","scopus_import":"1","_id":"21720","conference":{"name":"SODA: Symposium on Discrete Algorithms","location":"Vancouver, Canada","start_date":"2026-01-11","end_date":"2026-01-14"},"external_id":{"arxiv":["2512.13105"]},"publication_status":"published","date_created":"2026-04-12T22:01:51Z"},{"corr_author":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":330,"department":[{"_id":"MoHe"}],"OA_type":"gold","type":"conference","abstract":[{"text":"Given a graph G that undergoes a sequence of edge insertions and deletions, we study the Maximum k-Edge Coloring problem (MkEC): Having access to k different colors, color as many edges of G as possible such that no two adjacent edges share the same color. While this problem is different from simply maintaining a b-matching with b = k, the two problems are related. However, maximum b-matching can be solved efficiently in the static setting, whereas MkEC is NP-hard and even APX-hard for k ≥ 2. \r\nWe present new results on both problems: For b-matching, we show a new integrality gap result and we adapt Wajc’s matching sparsification scheme [David Wajc, 2020] for the case where b is a constant.\r\nUsing these as basis, we give three new algorithms for the dynamic MkEC problem: Our MatchO algorithm builds on the dynamic (2+ε)-approximation algorithm of Bhattacharya, Gupta, and Mohan [Sayan Bhattacharya et al., 2017] for b-matching and achieves a (2+ε)(k+1)/k-approximation in O(poly(log n, ε^-1)) update time against an oblivious adversary. Our MatchA algorithm builds on the dynamic (7+ε)-approximation algorithm by Bhattacharya, Henzinger, and Italiano [Sayan Bhattacharya et al., 2015] for fractional b-matching and achieves a (7+ε)(3k+3)/(3k-1)-approximation in O(poly(log n, ε^-1)) update time against an adaptive adversary. Moreover, our reductions use the dynamic b-matching algorithm as a black box, so any future improvement in the approximation ratio for dynamic b-matching will automatically translate into a better approximation ratio for our algorithms. Finally, we present a greedy algorithm with O(Δ+k) update time, which guarantees a 2.16 approximation factor.","lang":"eng"}],"citation":{"short":"A. El-Hayek, K. Hanauer, M. Henzinger, in:, 4th Symposium on Algorithmic Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","ieee":"A. El-Hayek, K. Hanauer, and M. Henzinger, “On b-matching and fully-dynamic maximum k-edge coloring,” in <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i>, Liverpool, United Kingdom, 2025, vol. 330.","ama":"El-Hayek A, Hanauer K, Henzinger M. On b-matching and fully-dynamic maximum k-edge coloring. In: <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i>. Vol 330. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2025.4\">10.4230/LIPIcs.SAND.2025.4</a>","apa":"El-Hayek, A., Hanauer, K., &#38; Henzinger, M. (2025). On b-matching and fully-dynamic maximum k-edge coloring. In <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i> (Vol. 330). Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2025.4\">https://doi.org/10.4230/LIPIcs.SAND.2025.4</a>","mla":"El-Hayek, Antoine, et al. “On B-Matching and Fully-Dynamic Maximum k-Edge Coloring.” <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i>, vol. 330, 4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2025.4\">10.4230/LIPIcs.SAND.2025.4</a>.","chicago":"El-Hayek, Antoine, Kathrin Hanauer, and Monika Henzinger. “On B-Matching and Fully-Dynamic Maximum k-Edge Coloring.” In <i>4th Symposium on Algorithmic Foundations of Dynamic Networks</i>, Vol. 330. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2025.4\">https://doi.org/10.4230/LIPIcs.SAND.2025.4</a>.","ista":"El-Hayek A, Hanauer K, Henzinger M. 2025. On b-matching and fully-dynamic maximum k-edge coloring. 4th Symposium on Algorithmic Foundations of Dynamic Networks. SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 330, 4."},"quality_controlled":"1","month":"06","scopus_import":"1","_id":"19858","conference":{"end_date":"2025-06-11","location":"Liverpool, United Kingdom","name":"SAND: Symposium on Algorithmic Foundations of Dynamic Networks","start_date":"2025-06-09"},"external_id":{"isi":["001532136900004"],"arxiv":["2310.01149"]},"alternative_title":["LIPIcs"],"publication_status":"published","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"date_created":"2025-06-22T22:02:06Z","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures","grant_number":"101019564","call_identifier":"H2020"},{"name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","OA_place":"publisher","ddc":["000"],"arxiv":1,"publication":"4th Symposium on Algorithmic Foundations of Dynamic Networks","isi":1,"article_number":"4","ec_funded":1,"publication_identifier":{"isbn":["9783959773683"],"issn":["1868-8969"]},"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.","year":"2025","day":"02","doi":"10.4230/LIPIcs.SAND.2025.4","file":[{"creator":"dernst","file_size":995666,"success":1,"date_created":"2025-06-23T11:23:29Z","file_name":"2025_LIPIcs_ElHayek.pdf","access_level":"open_access","date_updated":"2025-06-23T11:23:29Z","file_id":"19872","content_type":"application/pdf","checksum":"ad93a1e052adb29d7bfe8bd551bab193","relation":"main_file"}],"oa":1,"intvolume":"       330","date_published":"2025-06-02T00:00:00Z","language":[{"iso":"eng"}],"status":"public","file_date_updated":"2025-06-23T11:23:29Z","has_accepted_license":"1","article_processing_charge":"No","title":"On b-matching and fully-dynamic maximum k-edge coloring","author":[{"orcid":"0000-0003-4268-7368","last_name":"El-Hayek","full_name":"El-Hayek, Antoine","id":"888a098e-fcac-11ee-aff7-d347be57b725","first_name":"Antoine"},{"last_name":"Hanauer","full_name":"Hanauer, Kathrin","first_name":"Kathrin"},{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"}],"date_updated":"2025-09-30T13:37:28Z","oa_version":"Published Version"},{"date_published":"2025-01-07T00:00:00Z","doi":"10.1137/1.9781611978322.22","day":"07","oa":1,"ec_funded":1,"acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union’sHorizon 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.","publication_identifier":{"eisbn":["9781611978322"]},"year":"2025","publication":"Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms","arxiv":1,"OA_place":"repository","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures","grant_number":"101019564","call_identifier":"H2020"},{"grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms"},{"grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"}],"oa_version":"Preprint","page":"750-784","date_updated":"2025-12-29T12:30:04Z","title":"Fully dynamic approximate minimum cut in subpolynomial time per operation","author":[{"first_name":"Antoine","id":"888a098e-fcac-11ee-aff7-d347be57b725","full_name":"El-Hayek, Antoine","last_name":"El-Hayek","orcid":"0000-0003-4268-7368"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"},{"full_name":"Li, Jason","last_name":"Li","first_name":"Jason"}],"article_processing_charge":"No","language":[{"iso":"eng"}],"status":"public","quality_controlled":"1","abstract":[{"text":"Dynamically maintaining the minimum cut in a graph G under edge insertions and deletion is a fundamental problem in dynamic graph algorithms for which no conditional lower bound on the time per operation exists. In an n-node graph the best known (1 + o (1))-approximate algorithm takes  update time [14]. If the minimum cut is guaranteed to be (log n )o (1), a deterministic exact algorithm with n o (1) update time exists [8].\r\nWe present the first fully dynamic algorithm for (1 + o (1))-approximate minimum cut with n o(1) update time. Our main technical contribution is to show that it suffices to consider small-volume cuts in suitably contracted graphs.","lang":"eng"}],"type":"conference","citation":{"ieee":"A. El-Hayek, M. Henzinger, and J. Li, “Fully dynamic approximate minimum cut in subpolynomial time per operation,” in <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, New Orleans, LA, United States, 2025, pp. 750–784.","ama":"El-Hayek A, Henzinger M, Li J. Fully dynamic approximate minimum cut in subpolynomial time per operation. In: <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2025:750-784. doi:<a href=\"https://doi.org/10.1137/1.9781611978322.22\">10.1137/1.9781611978322.22</a>","apa":"El-Hayek, A., Henzinger, M., &#38; Li, J. (2025). Fully dynamic approximate minimum cut in subpolynomial time per operation. In <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 750–784). New Orleans, LA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611978322.22\">https://doi.org/10.1137/1.9781611978322.22</a>","mla":"El-Hayek, Antoine, et al. “Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation.” <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2025, pp. 750–84, doi:<a href=\"https://doi.org/10.1137/1.9781611978322.22\">10.1137/1.9781611978322.22</a>.","chicago":"El-Hayek, Antoine, Monika Henzinger, and Jason Li. “Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation.” In <i>Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 750–84. Society for Industrial and Applied Mathematics, 2025. <a href=\"https://doi.org/10.1137/1.9781611978322.22\">https://doi.org/10.1137/1.9781611978322.22</a>.","ista":"El-Hayek A, Henzinger M, Li J. 2025. Fully dynamic approximate minimum cut in subpolynomial time per operation. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 750–784.","short":"A. El-Hayek, M. Henzinger, J. Li, in:, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2025, pp. 750–784."},"department":[{"_id":"MoHe"}],"OA_type":"green","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2412.15069"}],"corr_author":"1","publisher":"Society for Industrial and Applied Mathematics","date_created":"2025-07-10T13:08:57Z","publication_status":"published","external_id":{"arxiv":["2412.15069"]},"conference":{"end_date":"2025-01-15","start_date":"2025-01-12","name":"SODA: Symposium on Discrete Algorithms","location":"New Orleans, LA, United States"},"_id":"19982","month":"01"},{"month":"06","_id":"20051","conference":{"end_date":"2025-06-20","start_date":"2025-06-16","location":"Huatulco, Mexico","name":"PODC: Symposium on Principles of Distributed Computing"},"external_id":{"isi":["001525534800066"],"arxiv":["2505.02765"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"publication_status":"published","date_created":"2025-07-21T08:16:15Z","corr_author":"1","publisher":"Association for Computing Machinery","OA_type":"hybrid","department":[{"_id":"MoHe"}],"citation":{"short":"A. El-Hayek, R. Elsässer, S. Schmid, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2025.","ama":"El-Hayek A, Elsässer R, Schmid S. An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model. In: <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2025. doi:<a href=\"https://doi.org/10.1145/3732772.3733505\">10.1145/3732772.3733505</a>","ieee":"A. El-Hayek, R. Elsässer, and S. Schmid, “An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model,” in <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Huatulco, Mexico, 2025.","apa":"El-Hayek, A., Elsässer, R., &#38; Schmid, S. (2025). An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model. In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>. Huatulco, Mexico: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3732772.3733505\">https://doi.org/10.1145/3732772.3733505</a>","chicago":"El-Hayek, Antoine, Robert Elsässer, and Stefan Schmid. “An Almost Tight Lower Bound for Plurality Consensus with Undecided State Dynamics in the Population Protocol Model.” In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3732772.3733505\">https://doi.org/10.1145/3732772.3733505</a>.","ista":"El-Hayek A, Elsässer R, Schmid S. 2025. An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model. Proceedings of the ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing.","mla":"El-Hayek, Antoine, et al. “An Almost Tight Lower Bound for Plurality Consensus with Undecided State Dynamics in the Population Protocol Model.” <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2025, doi:<a href=\"https://doi.org/10.1145/3732772.3733505\">10.1145/3732772.3733505</a>."},"abstract":[{"lang":"eng","text":"We revisit the majority problem in the population protocol communication model, as first studied by Angluin et al. (Distributed Computing 2008). We consider a more general version of this problem known as plurality consensus, which has already been studied intensively in the literature. In this problem, each node in a system of n nodes, has initially one of k different opinions, and they need to agree on the (relative) majority opinion. In particular, we consider the important and intensively studied model of Undecided State Dynamics.\r\nOur main contribution is an almost tight lower bound on the stabilization time: we prove that there exists an initial configuration, even with bias \\Delta = \\omega(\\sqrt{n\\log n}), where stabilization requires \\Omega(kn\\log \\frac {\\sqrt n} {k \\log n}) interactions, or equivalently, \\Omega(k\\log \\frac {\\sqrt n} {k \\log n}) parallel time for any k = o\\left(\\frac {\\sqrt n}{\\log n}\\right). This bound is tight for any k \\le n^{\\frac 1 2 - \\epsilon}, where \\epsilon >0 can be any small constant, as Amir et al.~(PODC'23) gave a O(k\\log n) parallel time upper bound for k = O\\left(\\frac {\\sqrt n} {\\log ^2 n}\\right)."}],"type":"conference","quality_controlled":"1","status":"public","language":[{"iso":"eng"}],"has_accepted_license":"1","article_processing_charge":"Yes (via OA deal)","file_date_updated":"2025-08-04T09:10:55Z","author":[{"first_name":"Antoine","last_name":"El-Hayek","full_name":"El-Hayek, Antoine","id":"888a098e-fcac-11ee-aff7-d347be57b725","orcid":"0000-0003-4268-7368"},{"full_name":"Elsässer, Robert","last_name":"Elsässer","first_name":"Robert"},{"first_name":"Stefan","last_name":"Schmid","full_name":"Schmid, Stefan"}],"title":"An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model","date_updated":"2025-10-16T13:08:45Z","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures","grant_number":"101019564","call_identifier":"H2020"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982"},{"grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"OA_place":"publisher","ddc":["000"],"isi":1,"arxiv":1,"publication":"Proceedings of the ACM Symposium on Principles of Distributed Computing","year":"2025","publication_identifier":{"isbn":[" 9798400718854"]},"acknowledgement":"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 DOI 10.55776/I5862,grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with\r\nadditional funding from the netidee SCIENCE Stiftung, 2020–2024\r\nand the German Research Foundation (DFG), grant 470029389\r\n(FlexNets).","ec_funded":1,"oa":1,"file":[{"checksum":"52976d226f3f691aa519d71c1c718fa5","content_type":"application/pdf","relation":"main_file","date_updated":"2025-08-04T09:10:55Z","file_id":"20115","access_level":"open_access","creator":"dernst","file_size":2200347,"success":1,"file_name":"2025_PODC_ElHayek.pdf","date_created":"2025-08-04T09:10:55Z"}],"doi":"10.1145/3732772.3733505","day":"13","date_published":"2025-06-13T00:00:00Z"},{"status":"public","language":[{"iso":"eng"}],"file_date_updated":"2025-08-05T07:32:01Z","has_accepted_license":"1","article_processing_charge":"No","title":"Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols","author":[{"last_name":"Breitkopf","full_name":"Breitkopf, Tom-Lukas","first_name":"Tom-Lukas"},{"first_name":"Julien","full_name":"Dallot, Julien","last_name":"Dallot"},{"orcid":"0000-0003-4268-7368","id":"888a098e-fcac-11ee-aff7-d347be57b725","last_name":"El-Hayek","full_name":"El-Hayek, Antoine","first_name":"Antoine"},{"full_name":"Schmid, Stefan","last_name":"Schmid","first_name":"Stefan"}],"page":"549-552","date_updated":"2026-02-16T11:46:37Z","oa_version":"Published Version","project":[{"call_identifier":"H2020","grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_place":"publisher","ddc":["000"],"publication":"Proceedings of the ACM Symposium on Principles of Distributed Computing","isi":1,"ec_funded":1,"acknowledgement":"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 DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024 and the German Research Foundation (DFG), grant 470029389 (FlexNets). ","year":"2025","publication_identifier":{"isbn":["9798400718854"]},"day":"13","doi":"10.1145/3732772.3733512","file":[{"relation":"main_file","content_type":"application/pdf","checksum":"e99679ffb28877b7cea4d54860302790","file_id":"20123","date_updated":"2025-08-05T07:32:01Z","access_level":"open_access","success":1,"date_created":"2025-08-05T07:32:01Z","file_name":"2025_PODC_Breitkopf.pdf","file_size":549706,"creator":"dernst"}],"oa":1,"date_published":"2025-06-13T00:00:00Z","month":"06","_id":"20052","conference":{"name":"PODC: Symposium on Principles of Distributed Computing","location":"Huatulco, Mexico","start_date":"2025-06-16","end_date":"2025-06-20"},"external_id":{"isi":["001525534800069"]},"publication_status":"published","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"date_created":"2025-07-21T08:17:04Z","corr_author":"1","publisher":"Association for Computing Machinery","OA_type":"hybrid","department":[{"_id":"MoHe"}],"abstract":[{"text":"This paper revisits a fundamental distributed computing problem in the population protocol model. Provided n agents each starting with an input color in [k], the relative majority problem asks to find the predominant color. In the population protocol model, at each time step, a scheduler selects two agents that first learn each other's states and then update their states based on what they learned.\r\nWe present the Circles protocol that solves the relative majority problem with k3 states. It is always-correct under weakly fair scheduling. Not only does it improve upon the best known upper bound of O(k7), but it also shows a strikingly simpler design inspired by energy minimization in chemical settings.","lang":"eng"}],"type":"conference","citation":{"chicago":"Breitkopf, Tom-Lukas, Julien Dallot, Antoine El-Hayek, and Stefan Schmid. “Brief Announcement: Minimizing Energy Solves Relative Majority with a Cubic Number of States in Population Protocols.” In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, 549–52. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3732772.3733512\">https://doi.org/10.1145/3732772.3733512</a>.","ista":"Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. 2025. Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols. Proceedings of the ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 549–552.","mla":"Breitkopf, Tom-Lukas, et al. “Brief Announcement: Minimizing Energy Solves Relative Majority with a Cubic Number of States in Population Protocols.” <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2025, pp. 549–52, doi:<a href=\"https://doi.org/10.1145/3732772.3733512\">10.1145/3732772.3733512</a>.","apa":"Breitkopf, T.-L., Dallot, J., El-Hayek, A., &#38; Schmid, S. (2025). Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols. In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i> (pp. 549–552). Huatulco, Mexico: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3732772.3733512\">https://doi.org/10.1145/3732772.3733512</a>","ama":"Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols. In: <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2025:549-552. doi:<a href=\"https://doi.org/10.1145/3732772.3733512\">10.1145/3732772.3733512</a>","ieee":"T.-L. Breitkopf, J. Dallot, A. El-Hayek, and S. Schmid, “Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols,” in <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Huatulco, Mexico, 2025, pp. 549–552.","short":"T.-L. Breitkopf, J. Dallot, A. El-Hayek, S. Schmid, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2025, pp. 549–552."},"quality_controlled":"1"},{"date_created":"2024-11-17T23:01:47Z","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"publication_status":"published","alternative_title":["LIPIcs"],"external_id":{"isi":["001542467600021"],"arxiv":["2302.11988"]},"conference":{"end_date":"2024-11-01","start_date":"2024-10-28","name":"DISC: Symposium on Distributed Computing","location":"Madrid, Spain"},"_id":"18557","scopus_import":"1","month":"10","quality_controlled":"1","citation":{"apa":"El-Hayek, A., Henzinger, M., &#38; Schmid, S. (2024). Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. In <i>38th International Symposium on Distributed Computing</i> (Vol. 319). Madrid, Spain: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2024.21\">https://doi.org/10.4230/LIPIcs.DISC.2024.21</a>","ieee":"A. El-Hayek, M. Henzinger, and S. Schmid, “Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges,” in <i>38th International Symposium on Distributed Computing</i>, Madrid, Spain, 2024, vol. 319.","ama":"El-Hayek A, Henzinger M, Schmid S. Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. In: <i>38th International Symposium on Distributed Computing</i>. Vol 319. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2024.21\">10.4230/LIPIcs.DISC.2024.21</a>","mla":"El-Hayek, Antoine, et al. “Broadcast and Consensus in Stochastic Dynamic Networks with Byzantine Nodes and Adversarial Edges.” <i>38th International Symposium on Distributed Computing</i>, vol. 319, 21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2024.21\">10.4230/LIPIcs.DISC.2024.21</a>.","chicago":"El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Broadcast and Consensus in Stochastic Dynamic Networks with Byzantine Nodes and Adversarial Edges.” In <i>38th International Symposium on Distributed Computing</i>, Vol. 319. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2024.21\">https://doi.org/10.4230/LIPIcs.DISC.2024.21</a>.","ista":"El-Hayek A, Henzinger M, Schmid S. 2024. Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. 38th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 319, 21.","short":"A. El-Hayek, M. Henzinger, S. Schmid, in:, 38th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024."},"abstract":[{"lang":"eng","text":"Broadcast and Consensus are most fundamental tasks in distributed computing. These tasks are particularly challenging in dynamic networks where communication across the network links may be unreliable, e.g., due to mobility or failures. Over the last years, researchers have derived several impossibility results and high time complexity lower bounds for these tasks. Specifically for the setting where in each round of communication the adversary is allowed to choose one rooted tree along which the information is disseminated, there is a lower as well as an upper bound that is linear in the number n of nodes for Broadcast and for n ≥ 3 the adversary can guarantee that Consensus never happens. This setting is called the oblivious message adversary for rooted trees. Also note that if the adversary is allowed to choose a graph that does not contain a rooted tree, then it can guarantee that Broadcast and Consensus will never happen. However, such deterministic adversarial models may be overly pessimistic, as many processes in real-world settings are stochastic in nature rather than worst-case. This paper studies Broadcast on stochastic dynamic networks and shows that the situation is very different to the deterministic case. In particular, we show that if information dissemination occurs along random rooted trees and directed Erdős–Rényi graphs, Broadcast completes in O(log n) rounds of communication with high probability. The fundamental insight in our analysis is that key variables are mutually independent. We then study two adversarial models, (a) one with Byzantine nodes and (b) one where an adversary controls the edges. (a) Our techniques without Byzantine nodes are general enough so that they can be extended to Byzantine nodes. (b) In the spirit of smoothed analysis, we introduce the notion of randomized oblivious message adversary, where in each round, an adversary picks k ≤ 2n/3 edges to appear in the communication network, and then a graph (e.g. rooted tree or directed Erdős–Rényi graph) is chosen uniformly at random among the set of all such graphs that include these edges. We show that Broadcast completes in a finite number of rounds, which is, e.g., O(k+log n) rounds in rooted trees. We then extend these results to All-to-All Broadcast, and Consensus, and give lower bounds that show that most of our upper bounds are tight."}],"type":"conference","OA_type":"gold","department":[{"_id":"MoHe"}],"volume":319,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","corr_author":"1","oa_version":"Published Version","date_updated":"2025-12-02T13:51:28Z","title":"Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges","author":[{"first_name":"Antoine","orcid":"0000-0003-4268-7368","id":"888a098e-fcac-11ee-aff7-d347be57b725","full_name":"El-Hayek, Antoine","last_name":"El-Hayek"},{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"}],"has_accepted_license":"1","article_processing_charge":"Yes","file_date_updated":"2024-11-18T08:02:45Z","language":[{"iso":"eng"}],"status":"public","date_published":"2024-10-24T00:00:00Z","intvolume":"       319","file":[{"file_id":"18561","date_updated":"2024-11-18T08:02:45Z","relation":"main_file","checksum":"d6c8277331cafa188c33ba1717206cf4","content_type":"application/pdf","file_size":809666,"creator":"dernst","success":1,"file_name":"2024_LIPIcs_ElHayek.pdf","date_created":"2024-11-18T08:02:45Z","access_level":"open_access"}],"oa":1,"doi":"10.4230/LIPIcs.DISC.2024.21","day":"24","year":"2024","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773522"]},"acknowledgement":"Antoine El-Hayek: This project has received funding from the Austrian Science Fund\r\n(FWF) grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung,\r\n2020–2024.\r\nMonika Henzinger: This project has received funding from the European Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation programme (MoDynStruct,\r\nNo. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI\r\n10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE\r\nStiftung, 2020–2024.\r\nStefan Schmid: This project has received funding from the German Research Foundation (DFG),\r\nSPP 2378 (project ReNO), 2023-2027.","ec_funded":1,"article_number":"21","isi":1,"publication":"38th International Symposium on Distributed Computing","arxiv":1,"ddc":["000"],"OA_place":"publisher","project":[{"grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"},{"call_identifier":"H2020","grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures"},{"grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms"},{"grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"}]