[{"month":"06","_id":"20053","external_id":{"isi":["001525534800030"]},"conference":{"start_date":"2025-06-16","name":"PODC: Symposium on Principles of Distributed Computing","location":"Huatulco, Mexico","end_date":"2025-06-20"},"date_created":"2025-07-21T08:18:26Z","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","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2025/745"}],"publisher":"Association for Computing Machinery","corr_author":"1","department":[{"_id":"KrCh"},{"_id":"KrPi"}],"OA_type":"hybrid","quality_controlled":"1","citation":{"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>.","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.","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>.","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.","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>","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>"},"type":"conference","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"}],"article_processing_charge":"No","has_accepted_license":"1","file_date_updated":"2025-08-05T07:15:31Z","language":[{"iso":"eng"}],"status":"public","date_updated":"2026-02-16T11:46:51Z","page":"241-251","author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Seth","last_name":"Gilbert","full_name":"Gilbert, Seth"},{"first_name":"Stefan","full_name":"Schmid, Stefan","last_name":"Schmid"},{"first_name":"Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","full_name":"Svoboda, Jakub","last_name":"Svoboda","orcid":"0000-0002-1419-3267"},{"first_name":"Michelle X","full_name":"Yeo, Michelle X","last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0001-3676-4809"}],"title":"When is liquid democracy possible?: On the manipulation of variance","oa_version":"Published Version","OA_place":"publisher","ddc":["000"],"project":[{"call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","isi":1,"publication":"Proceedings of the ACM Symposium on Principles of Distributed Computing","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.","year":"2025","publication_identifier":{"isbn":["9798400718854"]},"ec_funded":1,"date_published":"2025-06-13T00:00:00Z","file":[{"date_created":"2025-08-05T07:15:31Z","file_name":"2025_PODC_Chatterjee.pdf","success":1,"creator":"dernst","file_size":783297,"access_level":"open_access","date_updated":"2025-08-05T07:15:31Z","file_id":"20122","checksum":"cd628fe54d96e9fc6cc789bb8145422b","content_type":"application/pdf","relation":"main_file"}],"oa":1,"day":"13","doi":"10.1145/3732772.3733544"},{"file_date_updated":"2025-09-03T06:20:08Z","article_processing_charge":"Yes","has_accepted_license":"1","language":[{"iso":"eng"}],"status":"public","date_updated":"2026-02-16T12:23:19Z","author":[{"last_name":"Brewster","full_name":"Brewster, David A.","first_name":"David A."},{"orcid":"0000-0002-1419-3267","full_name":"Svoboda, Jakub","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub"},{"first_name":"Dylan","last_name":"Roscow","full_name":"Roscow, Dylan"},{"first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"full_name":"Tkadlec, Josef","last_name":"Tkadlec","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1097-9684","first_name":"Josef"},{"full_name":"Nowak, Martin A.","last_name":"Nowak","first_name":"Martin A."}],"title":"Maintaining diversity in structured populations","DOAJ_listed":"1","oa_version":"Published Version","OA_place":"publisher","ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"}],"arxiv":1,"publication":"PNAS Nexus","ec_funded":1,"acknowledgement":"J.S. and K.C. were supported by the European Research Council CoG 863818 (ForM-SMArt) and Austrian Science Fund 10.55776/COE12. J.T. was supported by GAČR grant 25-17377S and by Charles Univ. projects UNCE 24/SCI/008 and PRIMUS 24/SCI/012.","year":"2025","publication_identifier":{"eissn":["2752-6542"]},"article_type":"original","article_number":"pgaf252","intvolume":"         4","date_published":"2025-08-01T00:00:00Z","doi":"10.1093/pnasnexus/pgaf252","day":"01","file":[{"access_level":"open_access","creator":"dernst","file_size":1086419,"date_created":"2025-09-03T06:20:08Z","file_name":"2025_PNASNexus_Brewster.pdf","success":1,"checksum":"8a5e82c6f842e3220ec96028c9374b69","content_type":"application/pdf","relation":"main_file","date_updated":"2025-09-03T06:20:08Z","file_id":"20280"}],"oa":1,"scopus_import":"1","issue":"8","month":"08","_id":"20254","external_id":{"arxiv":["2503.09841"]},"date_created":"2025-08-31T22:01:32Z","publication_status":"published","PlanS_conform":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"publisher":"Oxford University Press","OA_type":"gold","department":[{"_id":"KrCh"}],"volume":4,"quality_controlled":"1","type":"journal_article","abstract":[{"text":"We examine population structures for their ability to maintain diversity in neutral evolution. We use the general framework of evolutionary graph theory and consider birth–death (bd) and death–birth (db) updating. The population is of size N. Initially all individuals represent different types. The basic question is: what is the time TN until one type takes over the population? This time is known as consensus time in computer science and as total coalescent time in evolutionary biology. For the complete graph, it is known that TN is quadratic in N for db and bd. For the cycle, we prove that TN is cubic in N for db and bd. For the star, we prove that TN is cubic for bd and quasilinear (N log N) for db. For the double star, we show that TN is quartic for bd. We derive upper and lower bounds for all undirected graphs for bd and db. We also show the Pareto front of graphs (of size N = 8) that maintain diversity the longest for bd and db. Further, we show that some graphs that quickly homogenize can maintain high levels of diversity longer than graphs that slowly homogenize. For directed graphs, we give simple contracting star-like structures that have superexponential time scales for maintaining diversity.","lang":"eng"}],"citation":{"ieee":"D. A. Brewster, J. Svoboda, D. Roscow, K. Chatterjee, J. Tkadlec, and M. A. Nowak, “Maintaining diversity in structured populations,” <i>PNAS Nexus</i>, vol. 4, no. 8. Oxford University Press, 2025.","apa":"Brewster, D. A., Svoboda, J., Roscow, D., Chatterjee, K., Tkadlec, J., &#38; Nowak, M. A. (2025). Maintaining diversity in structured populations. <i>PNAS Nexus</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/pnasnexus/pgaf252\">https://doi.org/10.1093/pnasnexus/pgaf252</a>","ama":"Brewster DA, Svoboda J, Roscow D, Chatterjee K, Tkadlec J, Nowak MA. Maintaining diversity in structured populations. <i>PNAS Nexus</i>. 2025;4(8). doi:<a href=\"https://doi.org/10.1093/pnasnexus/pgaf252\">10.1093/pnasnexus/pgaf252</a>","chicago":"Brewster, David A., Jakub Svoboda, Dylan Roscow, Krishnendu Chatterjee, Josef Tkadlec, and Martin A. Nowak. “Maintaining Diversity in Structured Populations.” <i>PNAS Nexus</i>. Oxford University Press, 2025. <a href=\"https://doi.org/10.1093/pnasnexus/pgaf252\">https://doi.org/10.1093/pnasnexus/pgaf252</a>.","ista":"Brewster DA, Svoboda J, Roscow D, Chatterjee K, Tkadlec J, Nowak MA. 2025. Maintaining diversity in structured populations. PNAS Nexus. 4(8), pgaf252.","mla":"Brewster, David A., et al. “Maintaining Diversity in Structured Populations.” <i>PNAS Nexus</i>, vol. 4, no. 8, pgaf252, Oxford University Press, 2025, doi:<a href=\"https://doi.org/10.1093/pnasnexus/pgaf252\">10.1093/pnasnexus/pgaf252</a>.","short":"D.A. Brewster, J. Svoboda, D. Roscow, K. Chatterjee, J. Tkadlec, M.A. Nowak, PNAS Nexus 4 (2025)."}},{"scopus_import":"1","month":"02","_id":"19445","alternative_title":["LNCS"],"external_id":{"arxiv":["2411.12582"],"isi":["001537885900016"]},"conference":{"end_date":"2025-03-02","name":"WALCOM: International Conference and Workshops on Algorithms and Computation","location":"Chengdu, China","start_date":"2025-02-28"},"date_created":"2025-03-23T23:01:27Z","publication_status":"published","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2411.12582"}],"publisher":"Springer Nature","department":[{"_id":"KrCh"}],"OA_type":"green","volume":15411,"quality_controlled":"1","type":"conference","abstract":[{"lang":"eng","text":"In reconfiguration, we are given two solutions to a graph problem, such as Vertex Cover or Dominating Set, with each solution represented by a placement of tokens on vertices of the graph. Our task is to reconfigure one into the other using small steps while ensuring the intermediate configurations of tokens are also valid solutions. The two commonly studied settings are Token Jumping and Token Sliding, which allows moving a single token to an arbitrary or an adjacent vertex, respectively.\r\n\r\nWe introduce new rules that generalize Token Jumping, parameterized by the number of tokens allowed to move at once and by the maximum distance of each move. Our main contribution is identifying minimal rules that allow reconfiguring any possible given solution into any other for Independent Set, Vertex Cover, and Dominating Set. For each minimal rule, we also provide an efficient algorithm that finds a corresponding reconfiguration sequence.\r\n\r\nWe further focus on the rule that allows each token to move to an adjacent vertex in a single step. This natural variant turns out to be the minimal rule that guarantees reconfigurability for Vertex Cover. We determine the computational complexity of deciding whether a (shortest) reconfiguration sequence exists under this rule for the three studied problems. While reachability for Vertex Cover is shown to be in P, finding a shortest sequence is shown to be NP-complete. For Independent Set and Dominating Set, even reachability is shown to be PSPACE-complete."}],"citation":{"short":"J.M. Křišťan, J. Svoboda, in:, 19th International Conference and Workshops on Algorithms and Computation, Springer Nature, 2025, pp. 244–265.","apa":"Křišťan, J. M., &#38; Svoboda, J. (2025). Reconfiguration using generalized token jumping. In <i>19th International Conference and Workshops on Algorithms and Computation</i> (Vol. 15411, pp. 244–265). Chengdu, China: Springer Nature. <a href=\"https://doi.org/10.1007/978-981-96-2845-2_16\">https://doi.org/10.1007/978-981-96-2845-2_16</a>","ieee":"J. M. Křišťan and J. Svoboda, “Reconfiguration using generalized token jumping,” in <i>19th International Conference and Workshops on Algorithms and Computation</i>, Chengdu, China, 2025, vol. 15411, pp. 244–265.","ama":"Křišťan JM, Svoboda J. Reconfiguration using generalized token jumping. In: <i>19th International Conference and Workshops on Algorithms and Computation</i>. Vol 15411. Springer Nature; 2025:244-265. doi:<a href=\"https://doi.org/10.1007/978-981-96-2845-2_16\">10.1007/978-981-96-2845-2_16</a>","chicago":"Křišťan, Jan Matyáš, and Jakub Svoboda. “Reconfiguration Using Generalized Token Jumping.” In <i>19th International Conference and Workshops on Algorithms and Computation</i>, 15411:244–65. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-981-96-2845-2_16\">https://doi.org/10.1007/978-981-96-2845-2_16</a>.","ista":"Křišťan JM, Svoboda J. 2025. Reconfiguration using generalized token jumping. 19th International Conference and Workshops on Algorithms and Computation. WALCOM: International Conference and Workshops on Algorithms and Computation, LNCS, vol. 15411, 244–265.","mla":"Křišťan, Jan Matyáš, and Jakub Svoboda. “Reconfiguration Using Generalized Token Jumping.” <i>19th International Conference and Workshops on Algorithms and Computation</i>, vol. 15411, Springer Nature, 2025, pp. 244–65, doi:<a href=\"https://doi.org/10.1007/978-981-96-2845-2_16\">10.1007/978-981-96-2845-2_16</a>."},"article_processing_charge":"No","language":[{"iso":"eng"}],"status":"public","date_updated":"2025-09-30T11:14:33Z","page":"244-265","title":"Reconfiguration using generalized token jumping","author":[{"first_name":"Jan Matyáš","full_name":"Křišťan, Jan Matyáš","last_name":"Křišťan"},{"orcid":"0000-0002-1419-3267","last_name":"Svoboda","full_name":"Svoboda, Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub"}],"oa_version":"Preprint","OA_place":"repository","project":[{"call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication":"19th International Conference and Workshops on Algorithms and Computation","arxiv":1,"isi":1,"ec_funded":1,"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9789819628445"]},"year":"2025","acknowledgement":"J. M. Křišťan acknowledges the support of the Czech Science Foundation Grant No. 24-12046S. This work was supported by the Grant Agency of the Czech Technical University in Prague, grant No. SGS23/205/OHK3/3T/18. J. Svoboda acknowledges the support of the ERC CoG 863818 (ForM-SMArt) grant.","intvolume":"     15411","date_published":"2025-02-20T00:00:00Z","day":"20","doi":"10.1007/978-981-96-2845-2_16","oa":1},{"OA_type":"green","department":[{"_id":"KrPi"},{"_id":"KrCh"}],"volume":15263,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1539"}],"publisher":"Springer Nature","quality_controlled":"1","type":"conference","abstract":[{"text":"In this work, we explore route discovery in private payment channel networks. We first determine what “ideal\" privacy for a routing protocol means in this setting. We observe that protocols achieving this strong privacy definition exist by leveraging Multi-Party Computation but they are inherently inefficient as they must involve the entire network. We then present protocols with weaker privacy guarantees but much better efficiency (involving only a small fraction of the nodes). The core idea is that both sender and receiver gossip a message which propagates through the network, and the moment any node in the network receives both messages, a path is found. In our first protocol the message is always sent to all neighbouring nodes with a delay proportional to the fees of that edge. In our second protocol the message is only sent to one neighbour chosen randomly with a probability proportional to its degree. We additionally propose a more realistic notion of privacy in order to measure the privacy leakage of our protocols in practice. Our realistic notion of privacy challenges an adversary that join the network with a fixed budget to create channels to guess the sender and receiver of a transaction upon receiving messages from our protocols. Simulations of our protocols on the Lightning network topology (for random transactions and uniform fees) show that 1) forming edges with high degree nodes is a more effective attack strategy for the adversary, 2) there is a tradeoff between the number of nodes involved in our protocols (privacy) and the optimality of the discovered path, and 3) our protocols involve a very small fraction of the network on average.","lang":"eng"}],"citation":{"mla":"Avarikioti, Zeta, et al. “Route Discovery in Private Payment Channel Networks.” <i>Computer Security. ESORICS 2024 International Workshops</i>, vol. 15263, Springer Nature, 2025, pp. 207–23, doi:<a href=\"https://doi.org/10.1007/978-3-031-82349-7_15\">10.1007/978-3-031-82349-7_15</a>.","ista":"Avarikioti Z, Bastankhah M, Maddah-Ali MA, Pietrzak KZ, Svoboda J, Yeo MX. 2025. Route discovery in private payment channel networks. Computer Security. ESORICS 2024 International Workshops. ESORICS: European Symposium on Research in Computer Security, LNCS, vol. 15263, 207–223.","chicago":"Avarikioti, Zeta, Mahsa Bastankhah, Mohammad Ali Maddah-Ali, Krzysztof Z Pietrzak, Jakub Svoboda, and Michelle X Yeo. “Route Discovery in Private Payment Channel Networks.” In <i>Computer Security. ESORICS 2024 International Workshops</i>, 15263:207–23. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-031-82349-7_15\">https://doi.org/10.1007/978-3-031-82349-7_15</a>.","ieee":"Z. Avarikioti, M. Bastankhah, M. A. Maddah-Ali, K. Z. Pietrzak, J. Svoboda, and M. X. Yeo, “Route discovery in private payment channel networks,” in <i>Computer Security. ESORICS 2024 International Workshops</i>, Bydgoszcz, Poland, 2025, vol. 15263, pp. 207–223.","apa":"Avarikioti, Z., Bastankhah, M., Maddah-Ali, M. A., Pietrzak, K. Z., Svoboda, J., &#38; Yeo, M. X. (2025). Route discovery in private payment channel networks. In <i>Computer Security. ESORICS 2024 International Workshops</i> (Vol. 15263, pp. 207–223). Bydgoszcz, Poland: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-82349-7_15\">https://doi.org/10.1007/978-3-031-82349-7_15</a>","ama":"Avarikioti Z, Bastankhah M, Maddah-Ali MA, Pietrzak KZ, Svoboda J, Yeo MX. Route discovery in private payment channel networks. In: <i>Computer Security. ESORICS 2024 International Workshops</i>. Vol 15263. Springer Nature; 2025:207-223. doi:<a href=\"https://doi.org/10.1007/978-3-031-82349-7_15\">10.1007/978-3-031-82349-7_15</a>","short":"Z. Avarikioti, M. Bastankhah, M.A. Maddah-Ali, K.Z. Pietrzak, J. Svoboda, M.X. Yeo, in:, Computer Security. ESORICS 2024 International Workshops, Springer Nature, 2025, pp. 207–223."},"_id":"19600","scopus_import":"1","month":"04","date_created":"2025-04-20T22:01:28Z","publication_status":"published","alternative_title":["LNCS"],"conference":{"end_date":"2024-09-20","location":"Bydgoszcz, Poland","name":"ESORICS: European Symposium on Research in Computer Security","start_date":"2024-09-16"},"publication":"Computer Security. ESORICS 2024 International Workshops","OA_place":"repository","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"intvolume":"     15263","date_published":"2025-04-01T00:00:00Z","day":"01","doi":"10.1007/978-3-031-82349-7_15","oa":1,"ec_funded":1,"publication_identifier":{"eissn":["1611-3349"],"isbn":["9783031823480"],"issn":["0302-9743"]},"year":"2025","acknowledgement":"This work was supported in part by the ERC CoG 863818 (ForM-SMArt), Austrian Science Fund (FWF) 10.55776/COE12, and MOE-T2EP20122-0014 (Data-Driven Distributed Algorithms) grants.","date_updated":"2025-11-05T07:52:35Z","page":"207-223","title":"Route discovery in private payment channel networks","author":[{"first_name":"Zeta","full_name":"Avarikioti, Zeta","last_name":"Avarikioti"},{"first_name":"Mahsa","full_name":"Bastankhah, Mahsa","last_name":"Bastankhah"},{"last_name":"Maddah-Ali","full_name":"Maddah-Ali, Mohammad Ali","first_name":"Mohammad Ali"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z"},{"first_name":"Jakub","orcid":"0000-0002-1419-3267","full_name":"Svoboda, Jakub","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","full_name":"Yeo, Michelle X","last_name":"Yeo","orcid":"0009-0001-3676-4809","first_name":"Michelle X"}],"article_processing_charge":"No","status":"public","language":[{"iso":"eng"}],"oa_version":"Submitted Version"},{"volume":39,"department":[{"_id":"KrCh"}],"OA_type":"green","publisher":"Association for the Advancement of Artificial Intelligence","corr_author":"1","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2412.12228","open_access":"1"}],"citation":{"short":"K. Chatterjee, R. Luo, R.J. Saona Urmeneta, J. Svoboda, in:, Proceedings of the 39th AAAI Conference on Artificial Intelligence, Association for the Advancement of Artificial Intelligence, 2025, pp. 11150–11157.","ieee":"K. Chatterjee, R. Luo, R. J. Saona Urmeneta, and J. Svoboda, “Linear equations with min and max operators: Computational complexity,” in <i>Proceedings of the 39th AAAI Conference on Artificial Intelligence</i>, Philadelphia, PA, United States, 2025, vol. 39, no. 11, pp. 11150–11157.","apa":"Chatterjee, K., Luo, R., Saona Urmeneta, R. J., &#38; Svoboda, J. (2025). Linear equations with min and max operators: Computational complexity. In <i>Proceedings of the 39th AAAI Conference on Artificial Intelligence</i> (Vol. 39, pp. 11150–11157). Philadelphia, PA, United States: Association for the Advancement of Artificial Intelligence. <a href=\"https://doi.org/10.1609/aaai.v39i11.33212\">https://doi.org/10.1609/aaai.v39i11.33212</a>","ama":"Chatterjee K, Luo R, Saona Urmeneta RJ, Svoboda J. Linear equations with min and max operators: Computational complexity. In: <i>Proceedings of the 39th AAAI Conference on Artificial Intelligence</i>. Vol 39. Association for the Advancement of Artificial Intelligence; 2025:11150-11157. doi:<a href=\"https://doi.org/10.1609/aaai.v39i11.33212\">10.1609/aaai.v39i11.33212</a>","ista":"Chatterjee K, Luo R, Saona Urmeneta RJ, Svoboda J. 2025. Linear equations with min and max operators: Computational complexity. Proceedings of the 39th AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence vol. 39, 11150–11157.","chicago":"Chatterjee, Krishnendu, Ruichen Luo, Raimundo J Saona Urmeneta, and Jakub Svoboda. “Linear Equations with Min and Max Operators: Computational Complexity.” In <i>Proceedings of the 39th AAAI Conference on Artificial Intelligence</i>, 39:11150–57. Association for the Advancement of Artificial Intelligence, 2025. <a href=\"https://doi.org/10.1609/aaai.v39i11.33212\">https://doi.org/10.1609/aaai.v39i11.33212</a>.","mla":"Chatterjee, Krishnendu, et al. “Linear Equations with Min and Max Operators: Computational Complexity.” <i>Proceedings of the 39th AAAI Conference on Artificial Intelligence</i>, vol. 39, no. 11, Association for the Advancement of Artificial Intelligence, 2025, pp. 11150–57, doi:<a href=\"https://doi.org/10.1609/aaai.v39i11.33212\">10.1609/aaai.v39i11.33212</a>."},"abstract":[{"text":"We consider a class of optimization problems defined by a system of linear equations with min and max operators. This class of optimization problems has been studied under restrictive conditions, such as, (C1) the halting or stability condition; (C2) the non-negative coefficients condition; (C3) the sum upto 1 condition; and (C4) the only min or only max operator condition. Several seminal results in the literature focus on special cases. For example, turn-based stochastic games correspond to conditions C2 and C3; and Markov decision process to conditions C2, C3, and C4. However, the systematic computational complexity study of all the cases has not been explored, which we address in this work. Some highlights of our results are: with conditions C2 and C4, and with conditions C3 and C4, the problem is NP-complete, whereas with condition C1 only, the problem is in UP intersects coUP. Finally, we establish the computational complexity of the decision problem of checking the respective conditions.","lang":"eng"}],"type":"conference","quality_controlled":"1","_id":"19669","month":"04","issue":"11","scopus_import":"1","publication_status":"published","date_created":"2025-05-11T22:02:40Z","conference":{"start_date":"2025-02-25","name":"AAAI: Conference on Artificial Intelligence","location":"Philadelphia, PA, United States","end_date":"2025-03-04"},"external_id":{"arxiv":["2412.12228"]},"arxiv":1,"publication":"Proceedings of the 39th AAAI Conference on Artificial Intelligence","project":[{"call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_place":"repository","oa":1,"day":"11","doi":"10.1609/aaai.v39i11.33212","date_published":"2025-04-11T00:00:00Z","intvolume":"        39","year":"2025","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant and the Austrian Science Fund (FWF) 10.55776/COE12 grant.","publication_identifier":{"eissn":["2374-3468"],"issn":["2159-5399"]},"ec_funded":1,"author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"},{"first_name":"Ruichen","full_name":"Luo, Ruichen","last_name":"Luo","id":"b391db08-1ffe-11ee-8b67-d18ddcfb5a14"},{"orcid":"0000-0001-5103-038X","full_name":"Saona Urmeneta, Raimundo J","last_name":"Saona Urmeneta","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J"},{"id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","last_name":"Svoboda","full_name":"Svoboda, Jakub","orcid":"0000-0002-1419-3267","first_name":"Jakub"}],"title":"Linear equations with min and max operators: Computational complexity","date_updated":"2025-05-12T09:42:09Z","page":"11150-11157","language":[{"iso":"eng"}],"status":"public","article_processing_charge":"No","oa_version":"Preprint"},{"author":[{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"last_name":"Jafariraviz","full_name":"Jafariraviz, Mahdi","first_name":"Mahdi"},{"id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","last_name":"Saona Urmeneta","full_name":"Saona Urmeneta, Raimundo J","orcid":"0000-0001-5103-038X","first_name":"Raimundo J"},{"full_name":"Svoboda, Jakub","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","orcid":"0000-0002-1419-3267","first_name":"Jakub"}],"title":"Value iteration with guessing for Markov chains and Markov decision processes","page":"217-236","date_updated":"2025-06-02T07:35:06Z","language":[{"iso":"eng"}],"status":"public","has_accepted_license":"1","article_processing_charge":"No","file_date_updated":"2025-06-02T07:31:12Z","oa_version":"Published Version","publication":"31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems","arxiv":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"}],"OA_place":"publisher","ddc":["000"],"oa":1,"file":[{"checksum":"45da6efbcbed20aada16c48c8e55e2d6","content_type":"application/pdf","relation":"main_file","date_updated":"2025-06-02T07:31:12Z","file_id":"19767","access_level":"open_access","creator":"dernst","file_size":557481,"success":1,"file_name":"2025_TACAS_Chatterjee.pdf","date_created":"2025-06-02T07:31:12Z"}],"doi":"10.1007/978-3-031-90653-4_11","day":"01","date_published":"2025-05-01T00:00:00Z","intvolume":"     15697","year":"2025","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant and Austrian Science Fund (FWF) 10.55776/COE12 grant.","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783031906527"],"issn":["0302-9743"]},"ec_funded":1,"_id":"19740","month":"05","scopus_import":"1","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"publication_status":"published","date_created":"2025-05-25T22:17:06Z","conference":{"end_date":"2025-05-08","name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","location":"Hamilton, ON, Canada","start_date":"2025-05-03"},"external_id":{"arxiv":["2505.06769"]},"alternative_title":["LNCS"],"volume":15697,"department":[{"_id":"KrCh"}],"OA_type":"hybrid","corr_author":"1","publisher":"Springer Nature","citation":{"mla":"Chatterjee, Krishnendu, et al. “Value Iteration with Guessing for Markov Chains and Markov Decision Processes.” <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, vol. 15697, Springer Nature, 2025, pp. 217–36, doi:<a href=\"https://doi.org/10.1007/978-3-031-90653-4_11\">10.1007/978-3-031-90653-4_11</a>.","ista":"Chatterjee K, Jafariraviz M, Saona Urmeneta RJ, Svoboda J. 2025. Value iteration with guessing for Markov chains and Markov decision processes. 31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems. TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS, vol. 15697, 217–236.","chicago":"Chatterjee, Krishnendu, Mahdi Jafariraviz, Raimundo J Saona Urmeneta, and Jakub Svoboda. “Value Iteration with Guessing for Markov Chains and Markov Decision Processes.” In <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, 15697:217–36. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-031-90653-4_11\">https://doi.org/10.1007/978-3-031-90653-4_11</a>.","ama":"Chatterjee K, Jafariraviz M, Saona Urmeneta RJ, Svoboda J. Value iteration with guessing for Markov chains and Markov decision processes. In: <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>. Vol 15697. Springer Nature; 2025:217-236. doi:<a href=\"https://doi.org/10.1007/978-3-031-90653-4_11\">10.1007/978-3-031-90653-4_11</a>","ieee":"K. Chatterjee, M. Jafariraviz, R. J. Saona Urmeneta, and J. Svoboda, “Value iteration with guessing for Markov chains and Markov decision processes,” in <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, Hamilton, ON, Canada, 2025, vol. 15697, pp. 217–236.","apa":"Chatterjee, K., Jafariraviz, M., Saona Urmeneta, R. J., &#38; Svoboda, J. (2025). Value iteration with guessing for Markov chains and Markov decision processes. In <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i> (Vol. 15697, pp. 217–236). Hamilton, ON, Canada: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-90653-4_11\">https://doi.org/10.1007/978-3-031-90653-4_11</a>","short":"K. Chatterjee, M. Jafariraviz, R.J. Saona Urmeneta, J. Svoboda, in:, 31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Springer Nature, 2025, pp. 217–236."},"type":"conference","abstract":[{"text":"Two standard models for probabilistic systems are Markov chains (MCs) and Markov decision processes (MDPs). Classic objectives for such probabilistic models for control and planning problems are reachability and stochastic shortest path. The widely studied algorithmic approach for these problems is the Value Iteration (VI) algorithm which iteratively applies local updates called Bellman updates. There are many practical approaches for VI in the literature but they all require exponentially many Bellman updates for MCs in the worst case. A preprocessing step is an algorithm that is discrete, graph-theoretical, and requires linear space. An important open question is whether, after a polynomial-time preprocessing, VI can be achieved with sub-exponentially many Bellman updates. In this work, we present a new approach for VI based on guessing values. Our theoretical contributions are twofold. First, for MCs, we present an almost-linear-time preprocessing algorithm after which, along with guessing values, VI requires only subexponentially many Bellman updates. Second, we present an improved analysis of the speed of convergence of VI for MDPs. Finally, we present a practical algorithm for MDPs based on our new approach. Experimental results show that our approach provides a considerable improvement over existing VI-based approaches on several benchmark examples from the literature.","lang":"eng"}],"quality_controlled":"1"},{"corr_author":"1","publisher":"National Academy of Sciences","volume":122,"OA_type":"hybrid","department":[{"_id":"KrCh"}],"abstract":[{"text":"Evolutionary games provide a flexible mathematical framework for many problems in biology and social evolution. Prisoners’ dilemma, and in particular, the important special case of donation games, represents social dilemmas where cooperation is mutually beneficial, yet defection is preferred by selfish agents. In evolutionary games on networks, the agents interact over a population structure. The existence of population structures that promote cooperative behavior is a fascinating and active research topic. Previous research establishes structures promoting cooperation in the limit of weak selection where the benefit-to-cost ratio β exceeds 1.5. The existence of such structures for medium and strong selection for 1 < ß < 2 and for weak selection for 1 < ß < 1.5 has been a long-standing open question. First, we answer the open questions in the affirmative: For every selection strength and every ß > 1, we construct networks promoting cooperation. Second, we present a robustness result with respect to β and selection strength: Our structures promote cooperation for a range of these parameter values rather than specific parameter values. Finally, we supplement our theoretical results with simulation results on small population structures that show the effectiveness of our construction over well-studied population structures.","lang":"eng"}],"pmid":1,"type":"journal_article","citation":{"short":"J. Svoboda, K. Chatterjee, Proceedings of the National Academy of Sciences 122 (2025) e2524109122.","mla":"Svoboda, Jakub, and Krishnendu Chatterjee. “Promoters of Cooperation in Evolutionary Games.” <i>Proceedings of the National Academy of Sciences</i>, vol. 122, no. 51, National Academy of Sciences, 2025, p. e2524109122, doi:<a href=\"https://doi.org/10.1073/pnas.2524109122\">10.1073/pnas.2524109122</a>.","ista":"Svoboda J, Chatterjee K. 2025. Promoters of cooperation in evolutionary games. Proceedings of the National Academy of Sciences. 122(51), e2524109122.","chicago":"Svoboda, Jakub, and Krishnendu Chatterjee. “Promoters of Cooperation in Evolutionary Games.” <i>Proceedings of the National Academy of Sciences</i>. National Academy of Sciences, 2025. <a href=\"https://doi.org/10.1073/pnas.2524109122\">https://doi.org/10.1073/pnas.2524109122</a>.","ieee":"J. Svoboda and K. Chatterjee, “Promoters of cooperation in evolutionary games,” <i>Proceedings of the National Academy of Sciences</i>, vol. 122, no. 51. National Academy of Sciences, p. e2524109122, 2025.","ama":"Svoboda J, Chatterjee K. Promoters of cooperation in evolutionary games. <i>Proceedings of the National Academy of Sciences</i>. 2025;122(51):e2524109122. doi:<a href=\"https://doi.org/10.1073/pnas.2524109122\">10.1073/pnas.2524109122</a>","apa":"Svoboda, J., &#38; Chatterjee, K. (2025). Promoters of cooperation in evolutionary games. <i>Proceedings of the National Academy of Sciences</i>. National Academy of Sciences. <a href=\"https://doi.org/10.1073/pnas.2524109122\">https://doi.org/10.1073/pnas.2524109122</a>"},"quality_controlled":"1","month":"12","scopus_import":"1","issue":"51","_id":"20857","external_id":{"pmid":["41397136"]},"publication_status":"published","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png"},"date_created":"2025-12-28T23:01:26Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"}],"OA_place":"publisher","ddc":["000"],"publication":"Proceedings of the National Academy of Sciences","ec_funded":1,"year":"2025","publication_identifier":{"eissn":["1091-6490"]},"acknowledgement":"J.S. and K.C. were supported by the European Research Council CoG 863818 (ForM-SMArt) and Austrian Science Fund (FWF) 10.55776/COE12.","article_type":"original","doi":"10.1073/pnas.2524109122","day":"15","oa":1,"file":[{"file_size":2308124,"creator":"dernst","success":1,"date_created":"2025-12-29T09:36:50Z","file_name":"2025_PNAS_Svoboda.pdf","access_level":"open_access","file_id":"20860","date_updated":"2025-12-29T09:36:50Z","relation":"main_file","content_type":"application/pdf","checksum":"dd50b62a1efc28c0133fe9c11dbee53c"}],"intvolume":"       122","date_published":"2025-12-15T00:00:00Z","language":[{"iso":"eng"}],"status":"public","file_date_updated":"2025-12-29T09:36:50Z","has_accepted_license":"1","article_processing_charge":"Yes (in subscription journal)","author":[{"last_name":"Svoboda","full_name":"Svoboda, Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","orcid":"0000-0002-1419-3267","first_name":"Jakub"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"}],"title":"Promoters of cooperation in evolutionary games","page":"e2524109122","date_updated":"2026-02-16T12:34:04Z","oa_version":"Published Version"},{"date_updated":"2026-03-09T11:52:58Z","title":"Boosting payment channel network liquidity with topology optimization and transaction selection","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"last_name":"Křišťan","full_name":"Křišťan, Jan Matyáš","first_name":"Jan Matyáš"},{"first_name":"Stefan","full_name":"Schmid, Stefan","last_name":"Schmid"},{"full_name":"Svoboda, Jakub","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","orcid":"0000-0002-1419-3267","first_name":"Jakub"},{"first_name":"Michelle X","orcid":"0009-0001-3676-4809","full_name":"Yeo, Michelle X","last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"file_date_updated":"2026-03-09T11:51:59Z","has_accepted_license":"1","article_processing_charge":"No","status":"public","language":[{"iso":"eng"}],"oa_version":"Published Version","arxiv":1,"publication":"39th International Symposium on Distributed Computing","OA_place":"publisher","ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"intvolume":"       356","date_published":"2025-10-22T00:00:00Z","doi":"10.4230/LIPIcs.DISC.2025.23","day":"22","oa":1,"file":[{"file_id":"21418","date_updated":"2026-03-09T11:51:59Z","relation":"main_file","checksum":"8e3d1594365df60163d9df22158a37b1","content_type":"application/pdf","file_size":1130069,"creator":"dernst","date_created":"2026-03-09T11:51:59Z","success":1,"file_name":"2025_DISC_Chatterjee.pdf","access_level":"open_access"}],"ec_funded":1,"publication_identifier":{"isbn":["9783959774024"],"issn":["1868-8969"]},"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).","year":"2025","article_number":"23","_id":"21412","scopus_import":"1","month":"10","date_created":"2026-03-08T23:01:46Z","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"},"external_id":{"arxiv":["2508.14524"]},"alternative_title":["LIPIcs"],"conference":{"end_date":"2025-10-31","name":"DISC: Symposium on Distributed Computing","location":"Berlin, Germany","start_date":"2025-10-27"},"OA_type":"gold","department":[{"_id":"KrCh"}],"volume":356,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2025/1484.pdf"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","abstract":[{"lang":"eng","text":"Payment channel networks (PCNs) are a promising technology that alleviates blockchain scalability by shifting the transaction load from the blockchain to the PCN. Nevertheless, the network topology has to be carefully designed to maximise the transaction throughput in PCNs. Additionally, users in PCNs also have to make optimal decisions on which transactions to forward and which to reject to prolong the lifetime of their channels. In this work, we consider an input sequence of transactions over p parties. Each transaction consists of a transaction size, source, and target, and can be either accepted or rejected (entailing a cost). The goal is to design a PCN topology among the p cooperating parties, along with the channel capacities, and then output a decision for each transaction in the sequence to minimise the cost of creating and augmenting channels, as well as the cost of rejecting transactions. Our main contribution is an 𝒪(p) approximation algorithm for the problem with p parties. We further show that with some assumptions on the distribution of transactions, we can reduce the approximation ratio to 𝒪(√p). We complement our theoretical analysis with an empirical study of our assumptions and approach in the context of the Lightning Network."}],"type":"conference","citation":{"short":"K. Chatterjee, J.M. Křišťan, S. Schmid, J. Svoboda, M.X. Yeo, in:, 39th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","mla":"Chatterjee, Krishnendu, et al. “Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection.” <i>39th International Symposium on Distributed Computing</i>, vol. 356, 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2025.23\">10.4230/LIPIcs.DISC.2025.23</a>.","chicago":"Chatterjee, Krishnendu, Jan Matyáš Křišťan, Stefan Schmid, Jakub Svoboda, and Michelle X Yeo. “Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection.” In <i>39th International Symposium on Distributed Computing</i>, Vol. 356. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2025.23\">https://doi.org/10.4230/LIPIcs.DISC.2025.23</a>.","ista":"Chatterjee K, Křišťan JM, Schmid S, Svoboda J, Yeo MX. 2025. Boosting payment channel network liquidity with topology optimization and transaction selection. 39th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 356, 23.","ieee":"K. Chatterjee, J. M. Křišťan, S. Schmid, J. Svoboda, and M. X. Yeo, “Boosting payment channel network liquidity with topology optimization and transaction selection,” in <i>39th International Symposium on Distributed Computing</i>, Berlin, Germany, 2025, vol. 356.","apa":"Chatterjee, K., Křišťan, J. M., Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2025). Boosting payment channel network liquidity with topology optimization and transaction selection. In <i>39th International Symposium on Distributed Computing</i> (Vol. 356). Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2025.23\">https://doi.org/10.4230/LIPIcs.DISC.2025.23</a>","ama":"Chatterjee K, Křišťan JM, Schmid S, Svoboda J, Yeo MX. Boosting payment channel network liquidity with topology optimization and transaction selection. In: <i>39th International Symposium on Distributed Computing</i>. Vol 356. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2025.23\">10.4230/LIPIcs.DISC.2025.23</a>"}},{"ddc":["000","519"],"OA_place":"publisher","project":[{"grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"}],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","supervisor":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"}],"year":"2025","acknowledgement":"This work was supported by the European Research Council CoG 863818 (ForMSMArt) and Austrian Science Fund 10.55776/COE12.\r\n","publication_identifier":{"issn":["2663-337X"]},"degree_awarded":"PhD","ec_funded":1,"date_published":"2025-08-05T00:00:00Z","file":[{"date_created":"2025-08-14T09:54:43Z","success":1,"file_name":"2025_Svoboda_Jakub_Thesis.pdf","file_size":5927291,"creator":"jsvoboda","access_level":"open_access","file_id":"20177","date_updated":"2025-08-14T09:54:43Z","relation":"main_file","checksum":"c6c4df9777f4537940de7ab392ad57e2","content_type":"application/pdf"},{"date_updated":"2025-08-21T11:48:39Z","file_id":"20178","checksum":"485e9f9822821bc03666d245d80aaa08","content_type":"application/zip","relation":"source_file","date_created":"2025-08-14T09:55:20Z","file_name":"2025_Svoboda_Jakub_Thesis.zip","creator":"jsvoboda","file_size":6731815,"access_level":"closed"}],"oa":1,"day":"05","doi":"10.15479/AT-ISTA-20138","has_accepted_license":"1","article_processing_charge":"No","file_date_updated":"2025-08-21T11:48:39Z","status":"public","language":[{"iso":"eng"}],"date_updated":"2026-04-07T11:49:12Z","related_material":{"record":[{"relation":"part_of_dissertation","id":"12787","status":"public"},{"id":"12101","relation":"part_of_dissertation","status":"public"},{"relation":"part_of_dissertation","id":"12257","status":"public"},{"id":"15297","relation":"part_of_dissertation","status":"public"},{"id":"18703","relation":"part_of_dissertation","status":"public"}]},"page":"167","title":"Structural properties of games on graphs","author":[{"id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","full_name":"Svoboda, Jakub","last_name":"Svoboda","orcid":"0000-0002-1419-3267","first_name":"Jakub"}],"oa_version":"Published Version","corr_author":"1","publisher":"Institute of Science and Technology Austria","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"citation":{"short":"J. Svoboda, Structural Properties of Games on Graphs, Institute of Science and Technology Austria, 2025.","apa":"Svoboda, J. (2025). <i>Structural properties of games on graphs</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-20138\">https://doi.org/10.15479/AT-ISTA-20138</a>","ieee":"J. Svoboda, “Structural properties of games on graphs,” Institute of Science and Technology Austria, 2025.","ama":"Svoboda J. Structural properties of games on graphs. 2025. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20138\">10.15479/AT-ISTA-20138</a>","mla":"Svoboda, Jakub. <i>Structural Properties of Games on Graphs</i>. Institute of Science and Technology Austria, 2025, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20138\">10.15479/AT-ISTA-20138</a>.","chicago":"Svoboda, Jakub. “Structural Properties of Games on Graphs.” Institute of Science and Technology Austria, 2025. <a href=\"https://doi.org/10.15479/AT-ISTA-20138\">https://doi.org/10.15479/AT-ISTA-20138</a>.","ista":"Svoboda J. 2025. Structural properties of games on graphs. Institute of Science and Technology Austria."},"type":"dissertation","abstract":[{"text":"The evolution shapes the world around us.\r\nNot only in biology, where the fittest individuals spread their genes but also in physics and social dynamics, the evolutionary forces determine the development of a state of matter or public opinions.\r\nMany models describe these dynamics.\r\nThis thesis examines the role of the structure in the models of selection.\r\nThe population structure is represented as a graph or a network, and each vertex is occupied by one individual.\r\nEvery individual has a type and fitness that represents the reproductive potential and depends on the type, occupied vertex, and the arrangement of the neighbors.\r\nThe evolution is modeled in discrete steps; in one step, one individual is replaced by a neighbor selected randomly with the influence of fitness.\r\n\r\n\r\n\r\nThe role of the networks is widely examined in the literature.\r\nThe structures that promote the spread of the desired type compared to the structureless case are called amplifiers.\r\nThe existence of amplifiers in various settings is an intensively studied topic, and in some settings, the amplifiers have been identified.\r\nMoreover, there are other important questions about the number of steps until one type spreads over the whole network (fixation time), the computational complexity, and the questions about the robustness of these processes.\r\n\r\n\r\nThis thesis explores the role of structure in evolution from many perspectives.\r\nFirst, it introduces different models and various choices that can be made in the models of evolution.\r\nIt highlights the role of the structure in the real world and how this is reflected in these models.\r\nThen, it describes the previous results and open problems.\r\nSecond, the thesis describes an amplifier for two variants of the Moran process: one with a constant birth rate and the other with a constant death rate.\r\nThis is an important contribution to the robustness of the amplification.\r\nThird, the thesis determines the complexity of spatial games.\r\nThese are processes where the fitness comes from a game, and the strength of selection is high.\r\nIt shows that determining the fate of cooperation in these games is a PSPACE-complete problem.\r\nFourth, the thesis describes the amplifier of cooperation for spatial games.\r\nThis is the first amplifier in this setting.\r\nFifth, the thesis examines the coexistence in the Moran process with environmental heterogeneity.\r\nIn this setting, the fitness depends not only on the type of the individual but also on the occupied vertex.\r\nThe chapter determines the relationship between the interactions of vertices of different types and the coexistence time.\r\nSixth, the thesis examines the social balance on networks and proposes a stochastic dynamic partially aware of the state of the graph, which reaches a balanced position quickly.\r\nFinally, the thesis presents conclusions and outlines the directions for future work.\r\n\r\n\r\n","lang":"eng"}],"month":"08","_id":"20138","alternative_title":["ISTA Thesis"],"date_created":"2025-08-05T14:33:59Z","tmp":{"image":"/images/cc_by_nc_sa.png","short":"CC BY-NC-SA (4.0)","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode"},"publication_status":"published"},{"publication":"NOMS 2024-2024 IEEE Network Operations and Management Symposium","isi":1,"OA_place":"other","project":[{"call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"},{"grant_number":"894907","name":"Graphical Games","_id":"bd622a5c-d553-11ed-ba76-bae280ba8aff"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2024-05-01T00:00:00Z","day":"01","doi":"10.1109/noms59830.2024.10575579","oa":1,"ec_funded":1,"publication_identifier":{"isbn":["9798350327946"],"eissn":["2374-9709"]},"acknowledgement":"Research was supported by the Austrian Science Fund (FWF), project I 5025-N (DELTA), 2020-2024. Esra Ceylan’s research was supported by FFG, FEMtech Praktika für Studentinnen. Jakub Svoboda and Krishnendu Chatterjee were supported by the European Research Council (ERC) CoG 863818 (ForM-SMArt).","year":"2024","date_updated":"2025-11-05T07:34:27Z","title":"Congestion-free rerouting of network flows: Hardness and an FPT algorithm","author":[{"first_name":"Esra","id":"cb1ca1d8-dcc0-11ef-baa5-9f1b3ef75933","full_name":"Ceylan, Esra","last_name":"Ceylan"},{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"},{"orcid":"0000-0002-1419-3267","full_name":"Svoboda, Jakub","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub"}],"article_processing_charge":"No","status":"public","language":[{"iso":"eng"}],"oa_version":"Submitted Version","OA_type":"green","department":[{"_id":"KrCh"}],"main_file_link":[{"url":"https://schmiste.github.io/noms24.pdf","open_access":"1"}],"corr_author":"1","publisher":"IEEE","quality_controlled":"1","abstract":[{"lang":"eng","text":"Given the increasingly stringent requirements on the performance and efficiency of communication networks, over the last years, great efforts have been made to render networks more flexible and programmable. In particular, modern networks support a flexible rerouting of flows, e.g., depending on the dynamically changing traffic or network conditions. However, the underlying algorithmic problems are still not well-understood today.In this paper, we revisit the k-Network Flow Update problem that asks for a schedule to reroute k unsplittable flows from their current paths to the given new paths, in a congestion-free manner in a capacitated network. We show that the problem is already NP-hard for three acyclic flows on simple directed graphs. Our main contribution is an efficient algorithm for sparse networks; specifically the algorithm is fixed parameter tractable in the number of flows and the treewidth of a graph that is the union of all flows. Our results also settle the open complexity question in the literature."}],"type":"conference","citation":{"short":"E. Ceylan, K. Chatterjee, S. Schmid, J. Svoboda, in:, NOMS 2024-2024 IEEE Network Operations and Management Symposium, IEEE, 2024.","apa":"Ceylan, E., Chatterjee, K., Schmid, S., &#38; Svoboda, J. (2024). Congestion-free rerouting of network flows: Hardness and an FPT algorithm. In <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>. Seoul, Republic of Korea: IEEE. <a href=\"https://doi.org/10.1109/noms59830.2024.10575579\">https://doi.org/10.1109/noms59830.2024.10575579</a>","ieee":"E. Ceylan, K. Chatterjee, S. Schmid, and J. Svoboda, “Congestion-free rerouting of network flows: Hardness and an FPT algorithm,” in <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>, Seoul, Republic of Korea, 2024.","ama":"Ceylan E, Chatterjee K, Schmid S, Svoboda J. Congestion-free rerouting of network flows: Hardness and an FPT algorithm. In: <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>. IEEE; 2024. doi:<a href=\"https://doi.org/10.1109/noms59830.2024.10575579\">10.1109/noms59830.2024.10575579</a>","ista":"Ceylan E, Chatterjee K, Schmid S, Svoboda J. 2024. Congestion-free rerouting of network flows: Hardness and an FPT algorithm. NOMS 2024-2024 IEEE Network Operations and Management Symposium. NOMS: Network Operations and Management Symposiu .","chicago":"Ceylan, Esra, Krishnendu Chatterjee, Stefan Schmid, and Jakub Svoboda. “Congestion-Free Rerouting of Network Flows: Hardness and an FPT Algorithm.” In <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>. IEEE, 2024. <a href=\"https://doi.org/10.1109/noms59830.2024.10575579\">https://doi.org/10.1109/noms59830.2024.10575579</a>.","mla":"Ceylan, Esra, et al. “Congestion-Free Rerouting of Network Flows: Hardness and an FPT Algorithm.” <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>, IEEE, 2024, doi:<a href=\"https://doi.org/10.1109/noms59830.2024.10575579\">10.1109/noms59830.2024.10575579</a>."},"_id":"18925","scopus_import":"1","month":"05","date_created":"2025-01-27T15:06:45Z","publication_status":"published","external_id":{"isi":["001270140300143"]},"conference":{"location":"Seoul, Republic of Korea","name":"NOMS: Network Operations and Management Symposiu ","start_date":"2024-05-06","end_date":"2024-05-10"}},{"type":"conference","abstract":[{"lang":"eng","text":"Reinforcement Learning (RL) from temporal logical specifications is a fundamental problem in sequential decision making. One of the basic and core such specification is the reachability specification that requires a target set to be eventually visited. Despite strong empirical results for RL from such specifications, the theoretical guarantees are bleak, including the impossibility of Probably Approximately Correct (PAC) guarantee for reachability specifications. Given the impossibility result, in this work we consider the problem of RL from reachability specifications along with the information of expected conditional distance (ECD). We present (a) lower bound results which establish the necessity of ECD information for PAC guarantees and (b) an algorithm that establishes PAC-guarantees given the ECD information. To the best of our knowledge, this is the first RL from reachability specifications that does not make any assumptions on the underlying environment to learn policies."}],"citation":{"mla":"Svoboda, Jakub, et al. “Reinforcement Learning from Reachability Specifications: PAC Guarantees with Expected Conditional Distance.” <i>41st International Conference on Machine Learning</i>, vol. 235, ML Research Press, 2024, pp. 47331–44.","ista":"Svoboda J, Bansal S, Chatterjee K. 2024. Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance. 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 47331–47344.","chicago":"Svoboda, Jakub, Suguman Bansal, and Krishnendu Chatterjee. “Reinforcement Learning from Reachability Specifications: PAC Guarantees with Expected Conditional Distance.” In <i>41st International Conference on Machine Learning</i>, 235:47331–44. ML Research Press, 2024.","ieee":"J. Svoboda, S. Bansal, and K. Chatterjee, “Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance,” in <i>41st International Conference on Machine Learning</i>, Vienna, Austria, 2024, vol. 235, pp. 47331–47344.","apa":"Svoboda, J., Bansal, S., &#38; Chatterjee, K. (2024). Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance. In <i>41st International Conference on Machine Learning</i> (Vol. 235, pp. 47331–47344). Vienna, Austria: ML Research Press.","ama":"Svoboda J, Bansal S, Chatterjee K. Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance. In: <i>41st International Conference on Machine Learning</i>. Vol 235. ML Research Press; 2024:47331-47344.","short":"J. Svoboda, S. Bansal, K. Chatterjee, in:, 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 47331–47344."},"quality_controlled":"1","volume":235,"department":[{"_id":"KrCh"}],"OA_type":"green","publisher":"ML Research Press","corr_author":"1","main_file_link":[{"open_access":"1","url":"https://openreview.net/forum?id=mXUDDL4r1Q"}],"publication_status":"published","date_created":"2025-01-30T07:45:22Z","conference":{"name":"ICML: International Conference on Machine Learning","location":"Vienna, Austria","start_date":"2024-07-21","end_date":"2024-07-27"},"alternative_title":["PMLR"],"_id":"18974","month":"07","scopus_import":"1","day":"29","oa":1,"intvolume":"       235","date_published":"2024-07-29T00:00:00Z","year":"2024","publication":"41st International Conference on Machine Learning","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_place":"publisher","oa_version":"Preprint","author":[{"first_name":"Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","last_name":"Svoboda","full_name":"Svoboda, Jakub","orcid":"0000-0002-1419-3267"},{"first_name":"Suguman","full_name":"Bansal, Suguman","last_name":"Bansal"},{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"}],"title":"Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance","date_updated":"2025-01-30T07:46:16Z","page":"47331-47344","status":"public","language":[{"iso":"eng"}],"article_processing_charge":"No"},{"doi":"10.1016/j.tcs.2023.114353","day":"21","oa":1,"file":[{"file_id":"17263","date_updated":"2024-07-16T12:02:25Z","relation":"main_file","content_type":"application/pdf","checksum":"efd5b7e738bf845312ba53889a3e13e4","file_size":603570,"creator":"dernst","date_created":"2024-07-16T12:02:25Z","file_name":"2024_TheorComputerScience_Schmid.pdf","success":1,"access_level":"open_access"}],"intvolume":"       989","date_published":"2024-03-21T00:00:00Z","article_number":"114353","ec_funded":1,"publication_identifier":{"issn":["0304-3975"]},"year":"2024","acknowledgement":"We thank Mahsa Bastankhah and Mohammad Ali Maddah-Ali for fruitful discussions about different variants of the problem. This work is supported by the European Research Council (ERC) Consolidator Project 864228 (AdjustNet), 2020-2025, the ERC CoG 863818 (ForM-SMArt), and the German Research Foundation (DFG) grant 470029389 (FlexNets), 2021-2024.","article_type":"original","publication":"Theoretical Computer Science","isi":1,"project":[{"call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ddc":["000"],"oa_version":"Published Version","keyword":["General Computer Science","Theoretical Computer Science"],"title":"Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation","author":[{"full_name":"Schmid, Stefan","last_name":"Schmid","first_name":"Stefan"},{"first_name":"Jakub","orcid":"0000-0002-1419-3267","last_name":"Svoboda","full_name":"Svoboda, Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425"},{"full_name":"Yeo, Michelle X","last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0001-3676-4809","first_name":"Michelle X"}],"date_updated":"2025-12-02T14:02:37Z","related_material":{"record":[{"id":"19985","relation":"earlier_version","status":"public"}]},"status":"public","language":[{"iso":"eng"}],"file_date_updated":"2024-07-16T12:02:25Z","has_accepted_license":"1","article_processing_charge":"Yes (via OA deal)","abstract":[{"lang":"eng","text":"We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link (u, v) is determined by how many nodes u and v allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given (u, v) and a packet of weight x going from u to v, node u can either accept or reject the packet. If u accepts the packet, the capacity on link (u, v) decreases by x. Correspondingly, v's capacity on \r\n increases by x. If a node rejects the packet, this will entail a cost affinely linear in the weight of the packet. A link is “rechargeable” in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on the nodes' decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of (1+E) . (1+3)  for some arbitrary E>0."}],"type":"journal_article","citation":{"mla":"Schmid, Stefan, et al. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” <i>Theoretical Computer Science</i>, vol. 989, 114353, Elsevier, 2024, doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">10.1016/j.tcs.2023.114353</a>.","chicago":"Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” <i>Theoretical Computer Science</i>. Elsevier, 2024. <a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">https://doi.org/10.1016/j.tcs.2023.114353</a>.","ista":"Schmid S, Svoboda J, Yeo MX. 2024. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. Theoretical Computer Science. 989, 114353.","ama":"Schmid S, Svoboda J, Yeo MX. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. <i>Theoretical Computer Science</i>. 2024;989. doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">10.1016/j.tcs.2023.114353</a>","apa":"Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2024). Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">https://doi.org/10.1016/j.tcs.2023.114353</a>","ieee":"S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation,” <i>Theoretical Computer Science</i>, vol. 989. Elsevier, 2024.","short":"S. Schmid, J. Svoboda, M.X. Yeo, Theoretical Computer Science 989 (2024)."},"quality_controlled":"1","volume":989,"department":[{"_id":"KrCh"},{"_id":"KrPi"}],"publisher":"Elsevier","corr_author":"1","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":"2024-01-16T13:40:41Z","external_id":{"isi":["001168211400001"]},"_id":"14820","month":"03","scopus_import":"1"},{"isi":1,"publication":"39th Annual ACM/IEEE Symposium on Logic in Computer Science","arxiv":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","project":[{"call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"}],"oa":1,"day":"08","doi":"10.1145/3661814.3662080","date_published":"2024-07-08T00:00:00Z","article_number":"6","publication_identifier":{"isbn":["9798400706608"],"eissn":["1043-6871"]},"year":"2024","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant.\r\n","ec_funded":1,"author":[{"first_name":"Ali","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","last_name":"Asadi","full_name":"Asadi, Ali"},{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"first_name":"Jakub","orcid":"0000-0002-1419-3267","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","full_name":"Svoboda, Jakub","last_name":"Svoboda"},{"first_name":"Raimundo J","orcid":"0000-0001-5103-038X","last_name":"Saona Urmeneta","full_name":"Saona Urmeneta, Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425"}],"title":"Deterministic sub-exponential algorithm for discounted-sum games with unary weights","date_updated":"2025-09-08T07:44:29Z","status":"public","language":[{"iso":"eng"}],"article_processing_charge":"No","oa_version":"Preprint","department":[{"_id":"KrCh"}],"corr_author":"1","publisher":"Association for Computing Machinery","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2405.02479"}],"citation":{"short":"A. Asadi, K. Chatterjee, J. Svoboda, R.J. Saona Urmeneta, in:, 39th Annual ACM/IEEE Symposium on Logic in Computer Science, Association for Computing Machinery, 2024.","mla":"Asadi, Ali, et al. “Deterministic Sub-Exponential Algorithm for Discounted-Sum Games with Unary Weights.” <i>39th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 6, Association for Computing Machinery, 2024, doi:<a href=\"https://doi.org/10.1145/3661814.3662080\">10.1145/3661814.3662080</a>.","ista":"Asadi A, Chatterjee K, Svoboda J, Saona Urmeneta RJ. 2024. Deterministic sub-exponential algorithm for discounted-sum games with unary weights. 39th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 6.","chicago":"Asadi, Ali, Krishnendu Chatterjee, Jakub Svoboda, and Raimundo J Saona Urmeneta. “Deterministic Sub-Exponential Algorithm for Discounted-Sum Games with Unary Weights.” In <i>39th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Association for Computing Machinery, 2024. <a href=\"https://doi.org/10.1145/3661814.3662080\">https://doi.org/10.1145/3661814.3662080</a>.","ama":"Asadi A, Chatterjee K, Svoboda J, Saona Urmeneta RJ. Deterministic sub-exponential algorithm for discounted-sum games with unary weights. In: <i>39th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Association for Computing Machinery; 2024. doi:<a href=\"https://doi.org/10.1145/3661814.3662080\">10.1145/3661814.3662080</a>","ieee":"A. Asadi, K. Chatterjee, J. Svoboda, and R. J. Saona Urmeneta, “Deterministic sub-exponential algorithm for discounted-sum games with unary weights,” in <i>39th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Tallinn, Estonia, 2024.","apa":"Asadi, A., Chatterjee, K., Svoboda, J., &#38; Saona Urmeneta, R. J. (2024). Deterministic sub-exponential algorithm for discounted-sum games with unary weights. In <i>39th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. Tallinn, Estonia: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3661814.3662080\">https://doi.org/10.1145/3661814.3662080</a>"},"type":"conference","abstract":[{"text":"Turn-based discounted-sum games are two-player zero-sum games played on finite directed graphs. The vertices of the graph are partitioned between player 1 and player 2. Plays are infinite walks on the graph where the next vertex is decided by a player that owns the current vertex. Each edge is assigned an integer weight and the payoff of a play is the discounted-sum of the weights of the play. The goal of player 1 is to maximize the discounted-sum payoff against the adversarial player 2. These games lie in NP ∩ coNP and are among the rare combinatorial problems that belong to this complexity class and the existence of a polynomial-time algorithm is a major open question. Since breaking the general exponential barrier has been a challenging problem, faster parameterized algorithms have been considered. If the discount factor is expressed in unary, then discounted-sum games can be solved in polynomial time. However, if the discount factor is arbitrary (or expressed in binary), but the weights are in unary, none of the existing approaches yield a sub-exponential bound. Our main result is a new analysis technique for a classical algorithm (namely, the strategy iteration algorithm) that present a new runtime bound which is [EQUATION] for game graphs with n vertices and absolute weights of at most W. In particular, our result yields a deterministic sub-exponential bound for games with weights that are constant or represented in unary.","lang":"eng"}],"quality_controlled":"1","_id":"17098","month":"07","scopus_import":"1","publication_status":"published","date_created":"2024-06-03T07:43:15Z","conference":{"end_date":"2024-07-11","location":"Tallinn, Estonia","name":"LICS: Logic in Computer Science","start_date":"2024-07-08"},"external_id":{"isi":["001275042100006"],"arxiv":["2405.02479"]}},{"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."}],"type":"conference","citation":{"mla":"Asadi, Ali, et al. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives: Complexity and Algorithms.” <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, vol. 323, 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">10.4230/LIPIcs.FSTTCS.2024.5</a>.","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.","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 <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Vol. 323. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5</a>.","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 <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Gujarat, India, 2024, vol. 323.","apa":"Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., &#38; Svoboda, J. (2024). Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. In <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i> (Vol. 323). Gujarat, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5</a>","ama":"Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. In: <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>. Vol 323. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">10.4230/LIPIcs.FSTTCS.2024.5</a>","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."},"quality_controlled":"1","corr_author":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","volume":323,"department":[{"_id":"KrCh"}],"OA_type":"gold","conference":{"name":"FSTTCS: Foundations of Software Technology and Theoretical Computer Science","location":"Gujarat, India","start_date":"2024-12-16","end_date":"2024-12-18"},"external_id":{"isi":["001537516500005"],"arxiv":["2405.02486"]},"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":"2024-06-03T07:44:27Z","month":"12","scopus_import":"1","_id":"17099","article_number":"5","ec_funded":1,"year":"2024","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)","publication_identifier":{"isbn":["9783959773553"],"issn":["1868-8969"]},"doi":"10.4230/LIPIcs.FSTTCS.2024.5","day":"05","oa":1,"file":[{"creator":"dernst","file_size":847960,"success":1,"file_name":"2024_LIPIcs_Asadi.pdf","date_created":"2025-01-08T09:49:31Z","access_level":"open_access","date_updated":"2025-01-08T09:49:31Z","file_id":"18777","content_type":"application/pdf","checksum":"5b544ab4692b93300b404435c036ddd4","relation":"main_file"}],"intvolume":"       323","date_published":"2024-12-05T00:00:00Z","project":[{"call_identifier":"H2020","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","OA_place":"publisher","ddc":["000"],"publication":"44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","arxiv":1,"isi":1,"oa_version":"Published Version","language":[{"iso":"eng"}],"status":"public","file_date_updated":"2025-01-08T09:49:31Z","article_processing_charge":"No","has_accepted_license":"1","author":[{"first_name":"Ali","last_name":"Asadi","full_name":"Asadi, Ali","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb"},{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"first_name":"Raimundo J","orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","full_name":"Saona Urmeneta, Raimundo J","last_name":"Saona Urmeneta"},{"first_name":"Jakub","orcid":"0000-0002-1419-3267","full_name":"Svoboda, Jakub","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425"}],"title":"Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms","date_updated":"2025-12-02T13:40:52Z"},{"external_id":{"isi":["001194482400002"],"arxiv":["2401.14914"]},"date_created":"2024-04-07T22:00:55Z","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","issue":"3","scopus_import":"1","month":"03","_id":"15297","quality_controlled":"1","citation":{"ama":"Svoboda J, Joshi SS, Tkadlec J, Chatterjee K. Amplifiers of selection for the Moran process with both Birth-death and death-Birth updating. <i>PLoS Computational Biology</i>. 2024;20(3). doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1012008\">10.1371/journal.pcbi.1012008</a>","apa":"Svoboda, J., Joshi, S. S., Tkadlec, J., &#38; Chatterjee, K. (2024). Amplifiers of selection for the Moran process with both Birth-death and death-Birth updating. <i>PLoS Computational Biology</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pcbi.1012008\">https://doi.org/10.1371/journal.pcbi.1012008</a>","ieee":"J. Svoboda, S. S. Joshi, J. Tkadlec, and K. Chatterjee, “Amplifiers of selection for the Moran process with both Birth-death and death-Birth updating,” <i>PLoS Computational Biology</i>, vol. 20, no. 3. Public Library of Science, 2024.","mla":"Svoboda, Jakub, et al. “Amplifiers of Selection for the Moran Process with Both Birth-Death and Death-Birth Updating.” <i>PLoS Computational Biology</i>, vol. 20, no. 3, e1012008, Public Library of Science, 2024, doi:<a href=\"https://doi.org/10.1371/journal.pcbi.1012008\">10.1371/journal.pcbi.1012008</a>.","chicago":"Svoboda, Jakub, Soham Shrikant Joshi, Josef Tkadlec, and Krishnendu Chatterjee. “Amplifiers of Selection for the Moran Process with Both Birth-Death and Death-Birth Updating.” <i>PLoS Computational Biology</i>. Public Library of Science, 2024. <a href=\"https://doi.org/10.1371/journal.pcbi.1012008\">https://doi.org/10.1371/journal.pcbi.1012008</a>.","ista":"Svoboda J, Joshi SS, Tkadlec J, Chatterjee K. 2024. Amplifiers of selection for the Moran process with both Birth-death and death-Birth updating. PLoS Computational Biology. 20(3), e1012008.","short":"J. Svoboda, S.S. Joshi, J. Tkadlec, K. Chatterjee, PLoS Computational Biology 20 (2024)."},"type":"journal_article","abstract":[{"text":"Populations evolve by accumulating advantageous mutations. Every population has some spatial structure that can be modeled by an underlying network. The network then influences the probability that new advantageous mutations fixate. Amplifiers of selection are networks that increase the fixation probability of advantageous mutants, as compared to the unstructured fully-connected network. Whether or not a network is an amplifier depends on the choice of the random process that governs the evolutionary dynamics. Two popular choices are Moran process with Birth-death updating and Moran process with death-Birth updating. Interestingly, while some networks are amplifiers under Birth-death updating and other networks are amplifiers under death-Birth updating, so far no spatial structures have been found that function as an amplifier under both types of updating simultaneously. In this work, we identify networks that act as amplifiers of selection under both versions of the Moran process. The amplifiers are robust, modular, and increase fixation probability for any mutant fitness advantage in a range r ∈ (1, 1.2). To complement this positive result, we also prove that for certain quantities closely related to fixation probability, it is impossible to improve them simultaneously for both versions of the Moran process. Together, our results highlight how the two versions of the Moran process differ and what they have in common.","lang":"eng"}],"publisher":"Public Library of Science","corr_author":"1","OA_type":"gold","department":[{"_id":"KrCh"}],"volume":20,"APC_amount":"3149,96 EUR","DOAJ_listed":"1","oa_version":"Published Version","article_processing_charge":"Yes","has_accepted_license":"1","file_date_updated":"2024-08-20T10:52:28Z","language":[{"iso":"eng"}],"status":"public","date_updated":"2026-04-07T11:49:11Z","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"20138"}]},"author":[{"first_name":"Jakub","orcid":"0000-0002-1419-3267","full_name":"Svoboda, Jakub","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425"},{"first_name":"Soham Shrikant","full_name":"Joshi, Soham Shrikant","last_name":"Joshi","id":"f97aac0e-f57c-11ee-93d0-a5a82d8df168"},{"first_name":"Josef","orcid":"0000-0002-1097-9684","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","last_name":"Tkadlec","full_name":"Tkadlec, Josef"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"}],"title":"Amplifiers of selection for the Moran process with both Birth-death and death-Birth updating","article_type":"original","publication_identifier":{"issn":["1553-734X"],"eissn":["1553-7358"]},"year":"2024","acknowledgement":"We thank Gavin Rees for helpful discussions. J.S., S.J., and K.C were supported by\r\nEuropean Research Council (ERC) CoG 863818 (ForM-SMArt). J.T was supported by Center for Foundations of Modern Computer Science (Charles University project UNCE/SCI/004) and by the project PRIMUS/24/SCI/012 from Charles University. ","ec_funded":1,"article_number":"e1012008","date_published":"2024-03-29T00:00:00Z","intvolume":"        20","oa":1,"file":[{"file_id":"17450","date_updated":"2024-08-20T10:52:28Z","relation":"main_file","checksum":"a511cf369d9172beb123fe73f291b5cc","content_type":"application/pdf","file_size":1425292,"creator":"dernst","file_name":"2024_PloSComBio_Svoboda.pdf","date_created":"2024-08-20T10:52:28Z","success":1,"access_level":"open_access"}],"day":"29","doi":"10.1371/journal.pcbi.1012008","OA_place":"publisher","ddc":["000"],"project":[{"call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"publication":"PLoS Computational Biology","arxiv":1},{"intvolume":"       121","date_published":"2024-12-10T00:00:00Z","doi":"10.1073/pnas.2405605121","day":"10","file":[{"access_level":"open_access","file_size":2491151,"creator":"dernst","success":1,"date_created":"2025-01-02T12:14:15Z","file_name":"2024_PNAS_Svoboda.pdf","relation":"main_file","checksum":"0115e9090b478e0644308c6dab58605b","content_type":"application/pdf","file_id":"18721","date_updated":"2025-01-02T12:14:15Z"}],"oa":1,"ec_funded":1,"publication_identifier":{"issn":["0027-8424"],"eissn":["1091-6490"]},"year":"2024","acknowledgement":"J.S. and K.C. were supported by the European Research Council CoG 863818 (ForM-SMArt) and Austrian Science Fund 10.55776/COE12.","article_type":"original","article_number":"e2405605121","publication":"Proceedings of the National Academy of Sciences of the United States of America","isi":1,"ddc":["000"],"OA_place":"publisher","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","call_identifier":"H2020"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa_version":"Published Version","APC_amount":"3143,76 EUR","related_material":{"record":[{"status":"public","id":"20138","relation":"dissertation_contains"}]},"date_updated":"2026-04-07T11:49:11Z","title":"Density amplifiers of cooperation for spatial games","author":[{"orcid":"0000-0002-1419-3267","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","full_name":"Svoboda, Jakub","last_name":"Svoboda","first_name":"Jakub"},{"first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"}],"file_date_updated":"2025-01-02T12:14:15Z","article_processing_charge":"Yes","has_accepted_license":"1","language":[{"iso":"eng"}],"status":"public","quality_controlled":"1","abstract":[{"lang":"eng","text":"Spatial games provide a simple and elegant mathematical model to study the evolution of cooperation in networks. In spatial games, individuals reside in vertices, adopt simple strategies, and interact with neighbors to receive a payoff. Depending on their own and neighbors’ payoffs, individuals can change their strategy. The payoff is determined by the Prisoners’ Dilemma, a classical matrix game, where players cooperate or defect. While cooperation is the desired behavior, defection provides a higher payoff for a selfish individual. There are many theoretical and empirical studies related to the role of the network in the evolution of cooperation. However, the fundamental question of whether there exist networks that for low initial cooperation rate ensure a high chance of fixation, i.e., cooperation spreads across the whole population, has remained elusive for spatial games with strong selection. In this work, we answer this fundamental question in the affirmative by presenting network structures that ensure high fixation probability for cooperators in the strong selection regime. Besides, our structures have many desirable properties: (a) they ensure the spread of cooperation even for a low initial density of cooperation and high temptation of defection, (b) they have constant degrees, and (c) the number of steps, until cooperation spreads, is at most quadratic in the size of the network."}],"pmid":1,"type":"journal_article","citation":{"apa":"Svoboda, J., &#38; Chatterjee, K. (2024). Density amplifiers of cooperation for spatial games. <i>Proceedings of the National Academy of Sciences of the United States of America</i>. National Academy of Sciences. <a href=\"https://doi.org/10.1073/pnas.2405605121\">https://doi.org/10.1073/pnas.2405605121</a>","ama":"Svoboda J, Chatterjee K. Density amplifiers of cooperation for spatial games. <i>Proceedings of the National Academy of Sciences of the United States of America</i>. 2024;121(50). doi:<a href=\"https://doi.org/10.1073/pnas.2405605121\">10.1073/pnas.2405605121</a>","ieee":"J. Svoboda and K. Chatterjee, “Density amplifiers of cooperation for spatial games,” <i>Proceedings of the National Academy of Sciences of the United States of America</i>, vol. 121, no. 50. National Academy of Sciences, 2024.","chicago":"Svoboda, Jakub, and Krishnendu Chatterjee. “Density Amplifiers of Cooperation for Spatial Games.” <i>Proceedings of the National Academy of Sciences of the United States of America</i>. National Academy of Sciences, 2024. <a href=\"https://doi.org/10.1073/pnas.2405605121\">https://doi.org/10.1073/pnas.2405605121</a>.","ista":"Svoboda J, Chatterjee K. 2024. Density amplifiers of cooperation for spatial games. Proceedings of the National Academy of Sciences of the United States of America. 121(50), e2405605121.","mla":"Svoboda, Jakub, and Krishnendu Chatterjee. “Density Amplifiers of Cooperation for Spatial Games.” <i>Proceedings of the National Academy of Sciences of the United States of America</i>, vol. 121, no. 50, e2405605121, National Academy of Sciences, 2024, doi:<a href=\"https://doi.org/10.1073/pnas.2405605121\">10.1073/pnas.2405605121</a>.","short":"J. Svoboda, K. Chatterjee, Proceedings of the National Academy of Sciences of the United States of America 121 (2024)."},"department":[{"_id":"KrCh"}],"OA_type":"hybrid","volume":121,"corr_author":"1","publisher":"National Academy of Sciences","date_created":"2024-12-22T23:01:47Z","publication_status":"published","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png"},"external_id":{"pmid":["39642209"],"isi":["001379596100014"]},"_id":"18703","scopus_import":"1","issue":"50","month":"12"},{"publication_status":"published","date_created":"2023-10-29T23:01:16Z","conference":{"end_date":"2023-09-21","start_date":"2023-09-18","location":"Trier, Germany","name":"FCT: Fundamentals of Computation Theory"},"external_id":{"isi":["001162288800024"],"arxiv":["2307.10847"]},"alternative_title":["LNCS"],"_id":"14456","month":"09","scopus_import":"1","type":"conference","abstract":[{"lang":"eng","text":"In this paper, we present novel algorithms that efficiently compute a shortest reconfiguration sequence between two given dominating sets in trees and interval graphs under the TOKEN SLIDING model. In this problem, a graph is provided along with its two dominating sets, which can be imagined as tokens placed on vertices. The objective is to find a shortest sequence of dominating sets that transforms one set into the other, with each set in the sequence resulting from sliding a single token in the previous set. While identifying any sequence has been well studied, our work presents the first polynomial algorithms for this optimization variant in the context of dominating sets."}],"citation":{"short":"J.M. Křišťan, J. Svoboda, in:, 24th International Symposium on Fundamentals of Computation Theory, Springer Nature, 2023, pp. 333–347.","ama":"Křišťan JM, Svoboda J. Shortest dominating set reconfiguration under token sliding. In: <i>24th International Symposium on Fundamentals of Computation Theory</i>. Vol 14292. Springer Nature; 2023:333-347. doi:<a href=\"https://doi.org/10.1007/978-3-031-43587-4_24\">10.1007/978-3-031-43587-4_24</a>","apa":"Křišťan, J. M., &#38; Svoboda, J. (2023). Shortest dominating set reconfiguration under token sliding. In <i>24th International Symposium on Fundamentals of Computation Theory</i> (Vol. 14292, pp. 333–347). Trier, Germany: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-43587-4_24\">https://doi.org/10.1007/978-3-031-43587-4_24</a>","ieee":"J. M. Křišťan and J. Svoboda, “Shortest dominating set reconfiguration under token sliding,” in <i>24th International Symposium on Fundamentals of Computation Theory</i>, Trier, Germany, 2023, vol. 14292, pp. 333–347.","ista":"Křišťan JM, Svoboda J. 2023. Shortest dominating set reconfiguration under token sliding. 24th International Symposium on Fundamentals of Computation Theory. FCT: Fundamentals of Computation Theory, LNCS, vol. 14292, 333–347.","chicago":"Křišťan, Jan Matyáš, and Jakub Svoboda. “Shortest Dominating Set Reconfiguration under Token Sliding.” In <i>24th International Symposium on Fundamentals of Computation Theory</i>, 14292:333–47. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/978-3-031-43587-4_24\">https://doi.org/10.1007/978-3-031-43587-4_24</a>.","mla":"Křišťan, Jan Matyáš, and Jakub Svoboda. “Shortest Dominating Set Reconfiguration under Token Sliding.” <i>24th International Symposium on Fundamentals of Computation Theory</i>, vol. 14292, Springer Nature, 2023, pp. 333–47, doi:<a href=\"https://doi.org/10.1007/978-3-031-43587-4_24\">10.1007/978-3-031-43587-4_24</a>."},"quality_controlled":"1","volume":14292,"department":[{"_id":"KrCh"}],"publisher":"Springer Nature","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2307.10847","open_access":"1"}],"oa_version":"Preprint","title":"Shortest dominating set reconfiguration under token sliding","author":[{"last_name":"Křišťan","full_name":"Křišťan, Jan Matyáš","first_name":"Jan Matyáš"},{"id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","full_name":"Svoboda, Jakub","last_name":"Svoboda","orcid":"0000-0002-1419-3267","first_name":"Jakub"}],"page":"333-347","related_material":{"link":[{"relation":"erratum","url":"https://doi.org/10.1007/978-3-031-43587-4_31"}]},"date_updated":"2025-09-09T13:07:40Z","language":[{"iso":"eng"}],"status":"public","article_processing_charge":"No","doi":"10.1007/978-3-031-43587-4_24","day":"21","oa":1,"intvolume":"     14292","date_published":"2023-09-21T00:00:00Z","year":"2023","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031435867"],"eissn":["1611-3349"]},"arxiv":1,"publication":"24th International Symposium on Fundamentals of Computation Theory","isi":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345"},{"citation":{"mla":"Bastankhah, Mahsa, et al. “R2: Boosting Liquidity in Payment Channel Networks with Online Admission Control.” <i>27th International Conference on Financial Cryptography and Data Security</i>, vol. 13950, Springer Nature, 2023, pp. 309–25, doi:<a href=\"https://doi.org/10.1007/978-3-031-47754-6_18\">10.1007/978-3-031-47754-6_18</a>.","ista":"Bastankhah M, Chatterjee K, Maddah-Ali MA, Schmid S, Svoboda J, Yeo MX. 2023. R2: Boosting liquidity in payment channel networks with online admission control. 27th International Conference on Financial Cryptography and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 13950, 309–325.","chicago":"Bastankhah, Mahsa, Krishnendu Chatterjee, Mohammad Ali Maddah-Ali, Stefan Schmid, Jakub Svoboda, and Michelle X Yeo. “R2: Boosting Liquidity in Payment Channel Networks with Online Admission Control.” In <i>27th International Conference on Financial Cryptography and Data Security</i>, 13950:309–25. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/978-3-031-47754-6_18\">https://doi.org/10.1007/978-3-031-47754-6_18</a>.","ieee":"M. Bastankhah, K. Chatterjee, M. A. Maddah-Ali, S. Schmid, J. Svoboda, and M. X. Yeo, “R2: Boosting liquidity in payment channel networks with online admission control,” in <i>27th International Conference on Financial Cryptography and Data Security</i>, Bol, Brac, Croatia, 2023, vol. 13950, pp. 309–325.","apa":"Bastankhah, M., Chatterjee, K., Maddah-Ali, M. A., Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2023). R2: Boosting liquidity in payment channel networks with online admission control. In <i>27th International Conference on Financial Cryptography and Data Security</i> (Vol. 13950, pp. 309–325). Bol, Brac, Croatia: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-47754-6_18\">https://doi.org/10.1007/978-3-031-47754-6_18</a>","ama":"Bastankhah M, Chatterjee K, Maddah-Ali MA, Schmid S, Svoboda J, Yeo MX. R2: Boosting liquidity in payment channel networks with online admission control. In: <i>27th International Conference on Financial Cryptography and Data Security</i>. Vol 13950. Springer Nature; 2023:309-325. doi:<a href=\"https://doi.org/10.1007/978-3-031-47754-6_18\">10.1007/978-3-031-47754-6_18</a>","short":"M. Bastankhah, K. Chatterjee, M.A. Maddah-Ali, S. Schmid, J. Svoboda, M.X. Yeo, in:, 27th International Conference on Financial Cryptography and Data Security, Springer Nature, 2023, pp. 309–325."},"type":"conference","abstract":[{"lang":"eng","text":"Payment channel networks (PCNs) are a promising technology to improve the scalability of cryptocurrencies. PCNs, however, face the challenge that the frequent usage of certain routes may deplete channels in one direction, and hence prevent further transactions. In order to reap the full potential of PCNs, recharging and rebalancing mechanisms are required to provision channels, as well as an admission control logic to decide which transactions to reject in case capacity is insufficient. This paper presents a formal model of this optimisation problem. In particular, we consider an online algorithms perspective, where transactions arrive over time in an unpredictable manner. Our main contributions are competitive online algorithms which come with provable guarantees over time. We empirically evaluate our algorithms on randomly generated transactions to compare the average performance of our algorithms to our theoretical bounds. We also show how this model and approach differs from related problems in classic communication networks."}],"quality_controlled":"1","volume":13950,"department":[{"_id":"KrCh"},{"_id":"KrPi"}],"OA_type":"green","publisher":"Springer Nature","main_file_link":[{"url":"https://openreview.net/forum?id=Dg0qdd9uha","open_access":"1"}],"publication_status":"published","date_created":"2024-01-08T09:30:22Z","conference":{"start_date":"2023-05-01","name":"FC: Financial Cryptography and Data Security","location":"Bol, Brac, Croatia","end_date":"2023-05-05"},"external_id":{"isi":["001150222600018"]},"alternative_title":["LNCS"],"_id":"14736","month":"12","scopus_import":"1","oa":1,"day":"01","doi":"10.1007/978-3-031-47754-6_18","date_published":"2023-12-01T00:00:00Z","intvolume":"     13950","acknowledgement":"Supported by the German Federal Ministry of Education and Research (BMBF), grant 16KISK020K (6G-RIC), 2021–2025, and ERC CoG 863818 (ForM-SMArt).","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031477539"],"eisbn":["9783031477546"],"eissn":["1611-3349"]},"year":"2023","ec_funded":1,"isi":1,"publication":"27th International Conference on Financial Cryptography and Data Security","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020"}],"OA_place":"repository","oa_version":"Submitted Version","author":[{"last_name":"Bastankhah","full_name":"Bastankhah, Mahsa","first_name":"Mahsa"},{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"},{"first_name":"Mohammad Ali","full_name":"Maddah-Ali, Mohammad Ali","last_name":"Maddah-Ali"},{"full_name":"Schmid, Stefan","last_name":"Schmid","first_name":"Stefan"},{"last_name":"Svoboda","full_name":"Svoboda, Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","orcid":"0000-0002-1419-3267","first_name":"Jakub"},{"orcid":"0009-0001-3676-4809","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","full_name":"Yeo, Michelle X","last_name":"Yeo","first_name":"Michelle X"}],"title":"R2: Boosting liquidity in payment channel networks with online admission control","page":"309-325","date_updated":"2025-11-05T07:37:31Z","language":[{"iso":"eng"}],"status":"public","article_processing_charge":"No"},{"quality_controlled":"1","citation":{"short":"K. Chatterjee, T. Meggendorfer, R.J. Saona Urmeneta, J. Svoboda, in:, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2023, pp. 4590–4605.","apa":"Chatterjee, K., Meggendorfer, T., Saona Urmeneta, R. J., &#38; Svoboda, J. (2023). Faster algorithm for turn-based stochastic games with bounded treewidth. In <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 4590–4605). Florence, Italy: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977554.ch173\">https://doi.org/10.1137/1.9781611977554.ch173</a>","ama":"Chatterjee K, Meggendorfer T, Saona Urmeneta RJ, Svoboda J. Faster algorithm for turn-based stochastic games with bounded treewidth. In: <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2023:4590-4605. doi:<a href=\"https://doi.org/10.1137/1.9781611977554.ch173\">10.1137/1.9781611977554.ch173</a>","ieee":"K. Chatterjee, T. Meggendorfer, R. J. Saona Urmeneta, and J. Svoboda, “Faster algorithm for turn-based stochastic games with bounded treewidth,” in <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Florence, Italy, 2023, pp. 4590–4605.","chicago":"Chatterjee, Krishnendu, Tobias Meggendorfer, Raimundo J Saona Urmeneta, and Jakub Svoboda. “Faster Algorithm for Turn-Based Stochastic Games with Bounded Treewidth.” In <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 4590–4605. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/1.9781611977554.ch173\">https://doi.org/10.1137/1.9781611977554.ch173</a>.","ista":"Chatterjee K, Meggendorfer T, Saona Urmeneta RJ, Svoboda J. 2023. Faster algorithm for turn-based stochastic games with bounded treewidth. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 4590–4605.","mla":"Chatterjee, Krishnendu, et al. “Faster Algorithm for Turn-Based Stochastic Games with Bounded Treewidth.” <i>Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2023, pp. 4590–605, doi:<a href=\"https://doi.org/10.1137/1.9781611977554.ch173\">10.1137/1.9781611977554.ch173</a>."},"type":"conference","abstract":[{"lang":"eng","text":"Turn-based stochastic games (aka simple stochastic games) are two-player zero-sum games played on directed graphs with probabilistic transitions. The goal of player-max is to maximize the probability to reach a target state against the adversarial player-min. These games lie in NP ∩ coNP and are among the rare combinatorial problems that belong to this complexity class for which the existence of polynomial-time algorithm is a major open question. While randomized sub-exponential time algorithm exists, all known deterministic algorithms require exponential time in the worst-case. An important open question has been whether faster algorithms can be obtained parametrized by the treewidth of the game graph. Even deterministic sub-exponential time algorithm for constant treewidth turn-based stochastic games has remain elusive. In this work our main result is a deterministic algorithm to solve turn-based stochastic games that, given a game with n states, treewidth at most t, and the bit-complexity of the probabilistic transition function log D, has running time O ((tn2 log D)t log n). In particular, our algorithm is quasi-polynomial time for games with constant or poly-logarithmic treewidth."}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1137/1.9781611977554.ch173"}],"corr_author":"1","publisher":"Society for Industrial and Applied Mathematics","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"conference":{"start_date":"2023-01-22","location":"Florence, Italy","name":"SODA: Symposium on Discrete Algorithms","end_date":"2023-01-25"},"date_created":"2023-02-24T12:20:47Z","publication_status":"published","month":"02","_id":"12676","year":"2023","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant.","publication_identifier":{"isbn":["9781611977554"]},"ec_funded":1,"date_published":"2023-02-01T00:00:00Z","oa":1,"doi":"10.1137/1.9781611977554.ch173","day":"01","project":[{"grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms","oa_version":"Published Version","article_processing_charge":"No","status":"public","language":[{"iso":"eng"}],"date_updated":"2025-04-14T07:52:47Z","page":"4590-4605","title":"Faster algorithm for turn-based stochastic games with bounded treewidth","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","full_name":"Meggendorfer, Tobias","last_name":"Meggendorfer","orcid":"0000-0002-1712-2165","first_name":"Tobias"},{"first_name":"Raimundo J","orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","last_name":"Saona Urmeneta","full_name":"Saona Urmeneta, Raimundo J"},{"first_name":"Jakub","orcid":"0000-0002-1419-3267","last_name":"Svoboda","full_name":"Svoboda, Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425"}]},{"publication_status":"published","date_created":"2025-07-10T13:15:43Z","conference":{"end_date":"2023-06-09","start_date":"2023-06-06","name":"SIROCCO: International Colloquium on Structural Information and Communication Complexity","location":"Alcalá de Henares, Spain"},"external_id":{"isi":["001292782600026"]},"alternative_title":["LNCS"],"_id":"19985","month":"05","scopus_import":"1","citation":{"short":"S. Schmid, J. Svoboda, M.X. Yeo, in:, 30th International Colloquium on Structural Information and Communication Complexity, Springer Nature, 2023, pp. 576–594.","apa":"Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2023). Weighted acket selection for rechargeable links in cryptocurrency networks: Complexity and approximation. In <i>30th International Colloquium on Structural Information and Communication Complexity</i> (Vol. 13892, pp. 576–594). Alcalá de Henares, Spain: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-32733-9_26\">https://doi.org/10.1007/978-3-031-32733-9_26</a>","ama":"Schmid S, Svoboda J, Yeo MX. Weighted acket selection for rechargeable links in cryptocurrency networks: Complexity and approximation. In: <i>30th International Colloquium on Structural Information and Communication Complexity</i>. Vol 13892. Springer Nature; 2023:576-594. doi:<a href=\"https://doi.org/10.1007/978-3-031-32733-9_26\">10.1007/978-3-031-32733-9_26</a>","ieee":"S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted acket selection for rechargeable links in cryptocurrency networks: Complexity and approximation,” in <i>30th International Colloquium on Structural Information and Communication Complexity</i>, Alcalá de Henares, Spain, 2023, vol. 13892, pp. 576–594.","chicago":"Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Acket Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” In <i>30th International Colloquium on Structural Information and Communication Complexity</i>, 13892:576–94. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/978-3-031-32733-9_26\">https://doi.org/10.1007/978-3-031-32733-9_26</a>.","ista":"Schmid S, Svoboda J, Yeo MX. 2023. Weighted acket selection for rechargeable links in cryptocurrency networks: Complexity and approximation. 30th International Colloquium on Structural Information and Communication Complexity. SIROCCO: International Colloquium on Structural Information and Communication Complexity, LNCS, vol. 13892, 576–594.","mla":"Schmid, Stefan, et al. “Weighted Acket Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” <i>30th International Colloquium on Structural Information and Communication Complexity</i>, vol. 13892, Springer Nature, 2023, pp. 576–94, doi:<a href=\"https://doi.org/10.1007/978-3-031-32733-9_26\">10.1007/978-3-031-32733-9_26</a>."},"type":"conference","abstract":[{"text":"We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link (u, v) is determined by how much nodes u and v allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given (u, v) and a packet of weight x going from u to v, node u can either accept or reject the packet. If u accepts the packet, the capacity on link (u, v) decreases by x. Correspondingly, v’s capacity on (u, v) increases by x. If a node rejects the packet, this will entail a cost affinely linear in the weight of the packet. A link is “rechargeable” in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on the nodes’ decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of (1 + E) . (1 + square3) for some arbitrary E>0.","lang":"eng"}],"quality_controlled":"1","volume":13892,"department":[{"_id":"KrCh"},{"_id":"KrPi"}],"OA_type":"closed access","corr_author":"1","publisher":"Springer Nature","oa_version":"None","author":[{"first_name":"Stefan","last_name":"Schmid","full_name":"Schmid, Stefan"},{"first_name":"Jakub","orcid":"0000-0002-1419-3267","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","full_name":"Svoboda, Jakub","last_name":"Svoboda"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","last_name":"Yeo","full_name":"Yeo, Michelle X","orcid":"0009-0001-3676-4809","first_name":"Michelle X"}],"title":"Weighted acket selection for rechargeable links in cryptocurrency networks: Complexity and approximation","page":"576-594","date_updated":"2025-12-02T14:02:38Z","related_material":{"record":[{"id":"14820","relation":"later_version","status":"public"}]},"status":"public","language":[{"iso":"eng"}],"article_processing_charge":"No","doi":"10.1007/978-3-031-32733-9_26","day":"25","date_published":"2023-05-25T00:00:00Z","intvolume":"     13892","year":"2023","acknowledgement":"We thank Mahsa Bastankhah and Mohammad Ali Maddah-Ali for fruitful discussions about different variants of the problem. This work is supported by the European Research Council (ERC) Consolidator Project 864228 (AdjustNet), 2020-2025, the ERC CoG 863818 (ForM-SMArt), and the German Research Foundation (DFG) grant 470029389 (FlexNets), 2021–2024.","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031327322"],"eissn":["1611-3349"],"eisbn":["9783031327339"]},"ec_funded":1,"isi":1,"publication":"30th International Colloquium on Structural Information and Communication Complexity","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"}]