[{"publication":"Proceedings of the ACM Symposium on Principles of Distributed Computing","publication_status":"published","language":[{"iso":"eng"}],"ddc":["000"],"publisher":"Association for Computing Machinery","department":[{"_id":"MoHe"}],"conference":{"location":"Huatulco, Mexico","start_date":"2025-06-16","end_date":"2025-06-20","name":"PODC: Symposium on Principles of Distributed Computing"},"day":"13","isi":1,"project":[{"name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020","grant_number":"101019564"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"}],"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). ","author":[{"last_name":"Breitkopf","first_name":"Tom-Lukas","full_name":"Breitkopf, Tom-Lukas"},{"last_name":"Dallot","full_name":"Dallot, Julien","first_name":"Julien"},{"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":"Stefan","full_name":"Schmid, Stefan","last_name":"Schmid"}],"has_accepted_license":"1","corr_author":"1","date_created":"2025-07-21T08:17:04Z","page":"549-552","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","article_processing_charge":"No","month":"06","fulldoi":"https://doi.org/10.1145/3732772.3733512","quality_controlled":"1","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"doi":"10.1145/3732772.3733512","date_published":"2025-06-13T00:00:00Z","_id":"20052","date_updated":"2026-02-16T11:46:37Z","type":"conference","status":"public","external_id":{"isi":["001525534800069"]},"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"}],"OA_place":"publisher","OA_type":"hybrid","oa":1,"publication_identifier":{"isbn":["9798400718854"]},"file_date_updated":"2025-08-05T07:32:01Z","title":"Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols","year":"2025","citation":{"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.","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>","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.","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.","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>.","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>","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>."},"file":[{"file_size":549706,"content_type":"application/pdf","relation":"main_file","creator":"dernst","success":1,"date_updated":"2025-08-05T07:32:01Z","date_created":"2025-08-05T07:32:01Z","access_level":"open_access","checksum":"e99679ffb28877b7cea4d54860302790","file_name":"2025_PODC_Breitkopf.pdf","file_id":"20123"}],"ec_funded":1},{"date_updated":"2026-02-16T11:46:51Z","status":"public","type":"conference","date_published":"2025-06-13T00:00:00Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"doi":"10.1145/3732772.3733544","_id":"20053","external_id":{"isi":["001525534800030"]},"abstract":[{"text":"Liquid democracy is a transitive vote delegation mechanism over voting graphs. It enables each voter to delegate their vote(s) to another better-informed voter, with the goal of collectively making a better decision. The question of whether liquid democracy outperforms direct voting has been previously studied in the context of local delegation mechanisms (where voters can only delegate to someone in their neighbourhood) and binary decision problems. It has previously been shown that it is impossible for local delegation mechanisms to outperform direct voting in general graphs. This raises the question: for which classes of graphs do local delegation mechanisms yield good results?\r\nIn this work, we analyse (1) properties of specific graphs and (2) properties of local delegation mechanisms on these graphs, determining where local delegation actually outperforms direct voting. We show that a critical graph property enabling liquid democracy is that the voting outcome of local delegation mechanisms preserves a sufficient amount of variance, thereby avoiding situations where delegation falls behind direct voting1. These insights allow us to prove our main results, namely that there exist local delegation mechanisms that perform no worse and in fact quantitatively better than direct voting in natural graph topologies like complete, random d-regular, and bounded degree graphs, lending a more nuanced perspective to previous impossibility results.","lang":"eng"}],"oa":1,"file_date_updated":"2025-08-05T07:15:31Z","publication_identifier":{"isbn":["9798400718854"]},"title":"When is liquid democracy possible?: On the manipulation of variance","OA_place":"publisher","OA_type":"hybrid","year":"2025","main_file_link":[{"url":"https://eprint.iacr.org/2025/745","open_access":"1"}],"citation":{"apa":"Chatterjee, K., Gilbert, S., Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2025). When is liquid democracy possible?: On the manipulation of variance. In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i> (pp. 241–251). Huatulco, Mexico: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3732772.3733544\">https://doi.org/10.1145/3732772.3733544</a>","ista":"Chatterjee K, Gilbert S, Schmid S, Svoboda J, Yeo MX. 2025. When is liquid democracy possible?: On the manipulation of variance. Proceedings of the ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 241–251.","ieee":"K. Chatterjee, S. Gilbert, S. Schmid, J. Svoboda, and M. X. Yeo, “When is liquid democracy possible?: On the manipulation of variance,” in <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Huatulco, Mexico, 2025, pp. 241–251.","short":"K. Chatterjee, S. Gilbert, S. Schmid, J. Svoboda, M.X. Yeo, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2025, pp. 241–251.","chicago":"Chatterjee, Krishnendu, Seth Gilbert, Stefan Schmid, Jakub Svoboda, and Michelle X Yeo. “When Is Liquid Democracy Possible?: On the Manipulation of Variance.” In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, 241–51. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3732772.3733544\">https://doi.org/10.1145/3732772.3733544</a>.","mla":"Chatterjee, Krishnendu, et al. “When Is Liquid Democracy Possible?: On the Manipulation of Variance.” <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2025, pp. 241–51, doi:<a href=\"https://doi.org/10.1145/3732772.3733544\">10.1145/3732772.3733544</a>.","ama":"Chatterjee K, Gilbert S, Schmid S, Svoboda J, Yeo MX. When is liquid democracy possible?: On the manipulation of variance. In: <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2025:241-251. doi:<a href=\"https://doi.org/10.1145/3732772.3733544\">10.1145/3732772.3733544</a>"},"ec_funded":1,"file":[{"creator":"dernst","content_type":"application/pdf","relation":"main_file","file_size":783297,"checksum":"cd628fe54d96e9fc6cc789bb8145422b","file_id":"20122","file_name":"2025_PODC_Chatterjee.pdf","date_updated":"2025-08-05T07:15:31Z","access_level":"open_access","date_created":"2025-08-05T07:15:31Z","success":1}],"publication":"Proceedings of the ACM Symposium on Principles of Distributed Computing","publication_status":"published","language":[{"iso":"eng"}],"ddc":["000"],"day":"13","conference":{"name":"PODC: Symposium on Principles of Distributed Computing","end_date":"2025-06-20","start_date":"2025-06-16","location":"Huatulco, Mexico"},"department":[{"_id":"KrCh"},{"_id":"KrPi"}],"publisher":"Association for Computing Machinery","project":[{"grant_number":"863818","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"isi":1,"acknowledgement":"This work was partially supported by MOE-T2EP20122-0014 (DataDriven Distributed Algorithms), German Research Foundation (DFG) project ReNO (SPP 2378) from 2023-2027, ERC CoG 863818 (ForMSMArt) and Austrian Science Fund (FWF) 10.55776/COE12.","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Gilbert","first_name":"Seth","full_name":"Gilbert, Seth"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"},{"id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","orcid":"0000-0002-1419-3267","last_name":"Svoboda","full_name":"Svoboda, Jakub","first_name":"Jakub"},{"full_name":"Yeo, Michelle X","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0001-3676-4809","last_name":"Yeo"}],"has_accepted_license":"1","page":"241-251","date_created":"2025-07-21T08:18:26Z","corr_author":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"06","fulldoi":"https://doi.org/10.1145/3732772.3733544","quality_controlled":"1","oa_version":"Published Version","article_processing_charge":"No"}]