[{"status":"public","corr_author":"1","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"full_name":"Jafariraviz, Mahdi","last_name":"Jafariraviz","first_name":"Mahdi"},{"orcid":"0000-0001-5103-038X","first_name":"Raimundo J","last_name":"Saona Urmeneta","full_name":"Saona Urmeneta, Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425"},{"last_name":"Svoboda","full_name":"Svoboda, Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub","orcid":"0000-0002-1419-3267"}],"year":"2025","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":15697,"date_updated":"2026-09-16T06:56:56Z","language":[{"iso":"eng"}],"license":"https://creativecommons.org/licenses/by/4.0/","page":"217-236","external_id":{"arxiv":["2505.06769"]},"ec_funded":1,"file_date_updated":"2025-06-02T07:31:12Z","arxiv":1,"ddc":["000"],"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa_version":"Published Version","title":"Value iteration with guessing for Markov chains and Markov decision processes","article_processing_charge":"No","publisher":"Springer Nature","date_created":"2025-05-25T22:17:06Z","OA_place":"publisher","date_published":"2025-05-01T00:00:00Z","department":[{"_id":"KrCh"}],"has_accepted_license":"1","file":[{"access_level":"open_access","creator":"dernst","date_created":"2025-06-02T07:31:12Z","file_size":557481,"content_type":"application/pdf","date_updated":"2025-06-02T07:31:12Z","relation":"main_file","file_id":"19767","success":1,"checksum":"45da6efbcbed20aada16c48c8e55e2d6","file_name":"2025_TACAS_Chatterjee.pdf"}],"scopus_import":"1","doi":"10.1007/978-3-031-90653-4_11","alternative_title":["LNCS"],"citation":{"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>","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>","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>.","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>.","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.","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."},"publication_identifier":{"issn":["0302-9743"],"isbn":["9783031906527"],"eissn":["1611-3349"]},"day":"01","intvolume":"     15697","fulldoi":"https://doi.org/10.1007/978-3-031-90653-4_11","publication_status":"published","type":"conference","project":[{"grant_number":"863818","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"},{"grant_number":"COE12","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","name":"Bilateral Artificial Intelligence (Chatterjee)"}],"OA_type":"hybrid","conference":{"end_date":"2025-05-08","name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","start_date":"2025-05-03","location":"Hamilton, ON, Canada"},"_id":"19740","oa":1,"month":"05","quality_controlled":"1","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant and Austrian Science Fund (FWF) 10.55776/COE12 grant.","abstract":[{"lang":"eng","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."}],"publication":"31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems"},{"page":"279-300","date_updated":"2026-09-16T06:57:43Z","language":[{"iso":"eng"}],"volume":15697,"status":"public","corr_author":"1","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"},{"orcid":"0000-0002-8595-0587","first_name":"Ehsan","id":"103b4fa0-896a-11ed-bdf8-87b697bef40d","full_name":"Kafshdar Goharshadi, Ehsan","last_name":"Kafshdar Goharshadi"},{"first_name":"Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","full_name":"Novotný, Petr","last_name":"Novotný"},{"first_name":"Dorde","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","last_name":"Zikelic","full_name":"Zikelic, Dorde","orcid":"0000-0002-4681-1699"}],"year":"2025","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Springer Nature","date_created":"2025-05-25T22:17:10Z","OA_place":"publisher","title":"Refuting equivalence in probabilistic programs with conditioning","article_processing_charge":"No","ec_funded":1,"arxiv":1,"file_date_updated":"2025-06-02T11:13:49Z","oa_version":"Published Version","tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"ddc":["000"],"external_id":{"arxiv":["2501.06579"]},"project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","grant_number":"863818"},{"_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","name":"Bilateral Artificial Intelligence (Chatterjee)","grant_number":"COE12"}],"day":"01","intvolume":"     15697","fulldoi":"https://doi.org/10.1007/978-3-031-90653-4_14","publication_status":"published","type":"conference","file":[{"checksum":"7dcd85e7e753bfa994c10b3cf9ebc185","file_name":"2025_TACAS_Chatterjee_Goharshadi.pdf","file_id":"19773","success":1,"file_size":532181,"content_type":"application/pdf","date_updated":"2025-06-02T11:13:49Z","relation":"main_file","creator":"dernst","access_level":"open_access","date_created":"2025-06-02T11:13:49Z"}],"has_accepted_license":"1","scopus_import":"1","alternative_title":["LNCS"],"publication_identifier":{"isbn":["9783031906527"],"eissn":["1611-3349"],"issn":["0302-9743"]},"citation":{"ista":"Chatterjee K, Goharshady E, Novotný P, Zikelic D. 2025. Refuting equivalence in probabilistic programs with conditioning. 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, 279–300.","short":"K. Chatterjee, E. Goharshady, P. Novotný, D. Zikelic, in:, 31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Springer Nature, 2025, pp. 279–300.","mla":"Chatterjee, Krishnendu, et al. “Refuting Equivalence in Probabilistic Programs with Conditioning.” <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, vol. 15697, Springer Nature, 2025, pp. 279–300, doi:<a href=\"https://doi.org/10.1007/978-3-031-90653-4_14\">10.1007/978-3-031-90653-4_14</a>.","chicago":"Chatterjee, Krishnendu, Ehsan Goharshady, Petr Novotný, and Dorde Zikelic. “Refuting Equivalence in Probabilistic Programs with Conditioning.” In <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, 15697:279–300. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-031-90653-4_14\">https://doi.org/10.1007/978-3-031-90653-4_14</a>.","ama":"Chatterjee K, Goharshady E, Novotný P, Zikelic D. Refuting equivalence in probabilistic programs with conditioning. In: <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>. Vol 15697. Springer Nature; 2025:279-300. doi:<a href=\"https://doi.org/10.1007/978-3-031-90653-4_14\">10.1007/978-3-031-90653-4_14</a>","apa":"Chatterjee, K., Goharshady, E., Novotný, P., &#38; Zikelic, D. (2025). Refuting equivalence in probabilistic programs with conditioning. In <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i> (Vol. 15697, pp. 279–300). Hamilton, ON, Canada: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-90653-4_14\">https://doi.org/10.1007/978-3-031-90653-4_14</a>","ieee":"K. Chatterjee, E. Goharshady, P. Novotný, and D. Zikelic, “Refuting equivalence in probabilistic programs with conditioning,” in <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, Hamilton, ON, Canada, 2025, vol. 15697, pp. 279–300."},"doi":"10.1007/978-3-031-90653-4_14","date_published":"2025-05-01T00:00:00Z","department":[{"_id":"KrCh"}],"abstract":[{"lang":"eng","text":"We consider the problem of refuting equivalence of probabilistic programs, i.e., the problem of proving that two probabilistic programs induce different output distributions. We study this problem in the context of programs with conditioning (i.e., with observe and score statements), where the output distribution is conditioned by the event that all the observe statements along a run evaluate to true, and where the probability densities of different runs may be updated via the score statements. Building on a recent work on programs without conditioning, we present a new equivalence refutation method for programs with conditioning. Our method is based on weighted restarting, a novel transformation of probabilistic programs with conditioning to the output equivalent probabilistic programs without conditioning that we introduce in this work. Our method is the first to be both a) fully automated, and b) providing provably correct answers. We demonstrate the applicability of our method on a set of programs from the probabilistic inference literature."}],"publication":"31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems","quality_controlled":"1","acknowledgement":"This work was partially supported by ERC CoG 863818 (ForM-SMArt) and Austrian Science Fund (FWF) 10.55776/COE12. Petr Novotný is supported by the Czech Science Foundation grant no. GA23-06963S.","_id":"19744","oa":1,"month":"05","OA_type":"hybrid","conference":{"name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","end_date":"2025-05-08","location":"Hamilton, ON, Canada","start_date":"2025-05-03"}},{"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2412.16226"}],"language":[{"iso":"eng"}],"date_updated":"2026-09-16T06:55:21Z","page":"11158-11166","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2025","corr_author":"1","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"Ehsan","id":"103b4fa0-896a-11ed-bdf8-87b697bef40d","last_name":"Kafshdar Goharshadi","full_name":"Kafshdar Goharshadi, Ehsan","orcid":"0000-0002-8595-0587"},{"orcid":"0009-0007-5253-9170","last_name":"Karrabi","full_name":"Karrabi, Mehrdad","id":"67638922-f394-11eb-9cf6-f20423e08757","first_name":"Mehrdad"},{"last_name":"Motwani","full_name":"Motwani, Harshit J.","first_name":"Harshit J."},{"first_name":"Maximilian","last_name":"Seeliger","full_name":"Seeliger, Maximilian"},{"orcid":"0000-0002-4681-1699","full_name":"Zikelic, Dorde","last_name":"Zikelic","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","first_name":"Dorde"}],"status":"public","volume":39,"article_processing_charge":"No","title":"Quantified linear and polynomial arithmetic satisfiability via template-based skolemization","OA_place":"repository","date_created":"2025-05-11T22:02:39Z","publisher":"Association for the Advancement of Artificial Intelligence","external_id":{"arxiv":["2412.16226"]},"issue":"11","oa_version":"Preprint","arxiv":1,"ec_funded":1,"type":"conference","publication_status":"published","fulldoi":"https://doi.org/10.1609/aaai.v39i11.33213","intvolume":"        39","day":"11","project":[{"call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"},{"grant_number":"COE12","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","name":"Bilateral Artificial Intelligence (Chatterjee)"}],"department":[{"_id":"KrCh"}],"date_published":"2025-04-11T00:00:00Z","citation":{"apa":"Chatterjee, K., Goharshady, E., Karrabi, M., Motwani, H. J., Seeliger, M., &#38; Zikelic, D. (2025). Quantified linear and polynomial arithmetic satisfiability via template-based skolemization. In <i>Proceedings of the 39th AAAI Conference on Artificial Intelligence</i> (Vol. 39, pp. 11158–11166). Philadelphia, PA, United States: Association for the Advancement of Artificial Intelligence. <a href=\"https://doi.org/10.1609/aaai.v39i11.33213\">https://doi.org/10.1609/aaai.v39i11.33213</a>","ieee":"K. Chatterjee, E. Goharshady, M. Karrabi, H. J. Motwani, M. Seeliger, and D. Zikelic, “Quantified linear and polynomial arithmetic satisfiability via template-based skolemization,” in <i>Proceedings of the 39th AAAI Conference on Artificial Intelligence</i>, Philadelphia, PA, United States, 2025, vol. 39, no. 11, pp. 11158–11166.","ama":"Chatterjee K, Goharshady E, Karrabi M, Motwani HJ, Seeliger M, Zikelic D. Quantified linear and polynomial arithmetic satisfiability via template-based skolemization. In: <i>Proceedings of the 39th AAAI Conference on Artificial Intelligence</i>. Vol 39. Association for the Advancement of Artificial Intelligence; 2025:11158-11166. doi:<a href=\"https://doi.org/10.1609/aaai.v39i11.33213\">10.1609/aaai.v39i11.33213</a>","mla":"Chatterjee, Krishnendu, et al. “Quantified Linear and Polynomial Arithmetic Satisfiability via Template-Based Skolemization.” <i>Proceedings of the 39th AAAI Conference on Artificial Intelligence</i>, vol. 39, no. 11, Association for the Advancement of Artificial Intelligence, 2025, pp. 11158–66, doi:<a href=\"https://doi.org/10.1609/aaai.v39i11.33213\">10.1609/aaai.v39i11.33213</a>.","chicago":"Chatterjee, Krishnendu, Ehsan Goharshady, Mehrdad Karrabi, Harshit J. Motwani, Maximilian Seeliger, and Dorde Zikelic. “Quantified Linear and Polynomial Arithmetic Satisfiability via Template-Based Skolemization.” In <i>Proceedings of the 39th AAAI Conference on Artificial Intelligence</i>, 39:11158–66. Association for the Advancement of Artificial Intelligence, 2025. <a href=\"https://doi.org/10.1609/aaai.v39i11.33213\">https://doi.org/10.1609/aaai.v39i11.33213</a>.","short":"K. Chatterjee, E. Goharshady, M. Karrabi, H.J. Motwani, M. Seeliger, D. Zikelic, in:, Proceedings of the 39th AAAI Conference on Artificial Intelligence, Association for the Advancement of Artificial Intelligence, 2025, pp. 11158–11166.","ista":"Chatterjee K, Goharshady E, Karrabi M, Motwani HJ, Seeliger M, Zikelic D. 2025. Quantified linear and polynomial arithmetic satisfiability via template-based skolemization. Proceedings of the 39th AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence vol. 39, 11158–11166."},"doi":"10.1609/aaai.v39i11.33213","publication_identifier":{"eissn":["2374-3468"],"issn":["2159-5399"]},"scopus_import":"1","acknowledgement":"This work was partially funded by ERC CoG 863818 (ForM-SMArt) and Austrian Science Fund (FWF) 10.55776/COE12.","quality_controlled":"1","publication":"Proceedings of the 39th AAAI Conference on Artificial Intelligence","abstract":[{"text":"The problem of checking satisfiability of linear real arithmetic (LRA) and non-linear real arithmetic (NRA) formulas has broad applications, in particular, they are at the heart of logic-related applications such as logic for artificial intelligence, program analysis, etc. While there has been much work on checking satisfiability of unquantified LRA and NRA formulas, the problem of checking satisfiability of quantified LRA and NRA formulas remains a significant challenge. The main bottleneck in the existing methods is a computationally expensive quantifier elimination step. In this work, we propose a novel method for efficient quantifier elimination in quantified LRA and NRA formulas. We propose a template-based Skolemization approach, where we automatically synthesize linear/polynomial Skolem functions in order to eliminate quantifiers in the formula. The key technical ingredient in our approach are Positivstellensätze theorems from algebraic geometry, which allow for an efficient manipulation of polynomial inequalities. Our method offers a range of appealing theoretical properties combined with a strong practical performance. On the theory side, our method is sound, semi-complete, and runs in subexponential time and polynomial space, as opposed to existing sound and complete quantifier elimination methods that run in doubly-exponential time and at least exponential space. On the practical side, our experiments show superior performance compared to state of the art SMT solvers in terms of the number of solved instances and runtime, both on LRA and on NRA benchmarks.","lang":"eng"}],"conference":{"start_date":"2025-02-25","location":"Philadelphia, PA, United States","end_date":"2025-03-04","name":"AAAI: Conference on Artificial Intelligence"},"OA_type":"green","month":"04","oa":1,"_id":"19667"},{"OA_place":"repository","date_created":"2025-05-11T22:02:40Z","publisher":"Association for the Advancement of Artificial Intelligence","article_processing_charge":"No","title":"Linear equations with min and max operators: Computational complexity","issue":"11","oa_version":"Preprint","arxiv":1,"ec_funded":1,"external_id":{"arxiv":["2412.12228"]},"page":"11150-11157","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2412.12228"}],"language":[{"iso":"eng"}],"date_updated":"2026-09-16T06:55:47Z","volume":39,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2025","corr_author":"1","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"last_name":"Luo","full_name":"Luo, Ruichen","id":"b391db08-1ffe-11ee-8b67-d18ddcfb5a14","first_name":"Ruichen"},{"orcid":"0000-0001-5103-038X","first_name":"Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","last_name":"Saona Urmeneta","full_name":"Saona Urmeneta, Raimundo J"},{"orcid":"0000-0002-1419-3267","full_name":"Svoboda, Jakub","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub"}],"status":"public","publication":"Proceedings of the 39th AAAI Conference on Artificial Intelligence","abstract":[{"lang":"eng","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."}],"acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant and the Austrian Science Fund (FWF) 10.55776/COE12 grant.","quality_controlled":"1","month":"04","oa":1,"_id":"19669","conference":{"start_date":"2025-02-25","location":"Philadelphia, PA, United States","end_date":"2025-03-04","name":"AAAI: Conference on Artificial Intelligence"},"OA_type":"green","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020"},{"_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","name":"Bilateral Artificial Intelligence (Chatterjee)","grant_number":"COE12"}],"type":"conference","fulldoi":"https://doi.org/10.1609/aaai.v39i11.33212","publication_status":"published","intvolume":"        39","day":"11","doi":"10.1609/aaai.v39i11.33212","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.","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>.","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>","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>"},"publication_identifier":{"issn":["2159-5399"],"eissn":["2374-3468"]},"scopus_import":"1","department":[{"_id":"KrCh"}],"date_published":"2025-04-11T00:00:00Z"},{"title":"Artifact: Fixed point certificates for reachability and expected rewards in MDPs","article_processing_charge":"No","abstract":[{"lang":"eng","text":"This artifact allows to review and reproduce the Isabelle proofs and practical experiments from the paper *Fixed Point Certificates for Reachability and Expected Rewards in MDPs*.\r\nThe contents are two-fold:\r\nFirst, the artifact contains a formally verified certificate checker for the certificates presented in the paper.\r\nThe formal Isabelle/HOL proofs of the background theory can be inspected, checked by Isabelle and the code extraction can be retraced.\r\n\r\nSecond, the artifact contains a modified version of the model checking tool `Storm` with support for certificate generation. Together with the provided scripts and benchmark files, this allows to reproduce the experiments from the paper.\r\nAn appropriate subset of the experiments is given to allow a review in a timely manner. In addition, original logfiles from our experiments are provided, allowing a detailed inspection.\r\n\r\nThe package includes convenient installation scripts for [the TACAS 2023 VM](https://doi.org/10.5281/zenodo.7113223) (based on Ubuntu 22.04).\r\nA native installation on Linux or macOS systems (including the newer ARM-based machines) is also possible."}],"publisher":"Zenodo","OA_place":"repository","related_material":{"record":[{"status":"public","relation":"used_in_publication","id":"19743"}]},"date_created":"2025-06-02T10:13:24Z","OA_type":"green","_id":"19771","month":"01","tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1,"oa_version":"Published Version","ddc":["000"],"date_updated":"2026-09-16T06:57:17Z","day":"09","type":"research_data_reference","main_file_link":[{"url":"https://doi.org/10.5281/ZENODO.14626585","open_access":"1"}],"fulldoi":"https://doi.org/10.5281/ZENODO.14626585","author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"},{"first_name":"Tim","full_name":"Quatmann, Tim","last_name":"Quatmann"},{"full_name":"Schäffeler, Maximilian","last_name":"Schäffeler","first_name":"Maximilian"},{"orcid":"0000-0002-0163-2152","full_name":"Weininger, Maximilian","last_name":"Weininger","id":"02ab0197-cc70-11ed-ab61-918e71f56881","first_name":"Maximilian"},{"last_name":"Winkler","full_name":"Winkler, Tobias","first_name":"Tobias"},{"first_name":"Daniel","full_name":"Zilken, Daniel","last_name":"Zilken","id":"d8ebc24a-3f98-11f0-9044-8296d4f39ab3"}],"date_published":"2025-01-09T00:00:00Z","status":"public","department":[{"_id":"KrCh"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2025","doi":"10.5281/ZENODO.14626585","citation":{"ama":"Chatterjee K, Quatmann T, Schäffeler M, Weininger M, Winkler T, Zilken D. Artifact: Fixed point certificates for reachability and expected rewards in MDPs. 2025. doi:<a href=\"https://doi.org/10.5281/ZENODO.14626585\">10.5281/ZENODO.14626585</a>","ieee":"K. Chatterjee, T. Quatmann, M. Schäffeler, M. Weininger, T. Winkler, and D. Zilken, “Artifact: Fixed point certificates for reachability and expected rewards in MDPs.” Zenodo, 2025.","apa":"Chatterjee, K., Quatmann, T., Schäffeler, M., Weininger, M., Winkler, T., &#38; Zilken, D. (2025). Artifact: Fixed point certificates for reachability and expected rewards in MDPs. Zenodo. <a href=\"https://doi.org/10.5281/ZENODO.14626585\">https://doi.org/10.5281/ZENODO.14626585</a>","ista":"Chatterjee K, Quatmann T, Schäffeler M, Weininger M, Winkler T, Zilken D. 2025. Artifact: Fixed point certificates for reachability and expected rewards in MDPs, Zenodo, <a href=\"https://doi.org/10.5281/ZENODO.14626585\">10.5281/ZENODO.14626585</a>.","short":"K. Chatterjee, T. Quatmann, M. Schäffeler, M. Weininger, T. Winkler, D. Zilken, (2025).","mla":"Chatterjee, Krishnendu, et al. <i>Artifact: Fixed Point Certificates for Reachability and Expected Rewards in MDPs</i>. Zenodo, 2025, doi:<a href=\"https://doi.org/10.5281/ZENODO.14626585\">10.5281/ZENODO.14626585</a>.","chicago":"Chatterjee, Krishnendu, Tim Quatmann, Maximilian Schäffeler, Maximilian Weininger, Tobias Winkler, and Daniel Zilken. “Artifact: Fixed Point Certificates for Reachability and Expected Rewards in MDPs.” Zenodo, 2025. <a href=\"https://doi.org/10.5281/ZENODO.14626585\">https://doi.org/10.5281/ZENODO.14626585</a>."}},{"date_updated":"2026-09-16T06:58:24Z","license":"https://creativecommons.org/licenses/by-nc/4.0/","language":[{"iso":"eng"}],"degree_awarded":"PhD","page":"157","supervisor":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"}],"corr_author":"1","author":[{"first_name":"Valentin","id":"2c8aa207-dc7d-11ea-9b2f-f22972ecd910","last_name":"Hübner","full_name":"Hübner, Valentin","orcid":"0009-0001-5009-4987"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2025","title":"Reciprocity and inequality in social dilemmas","article_processing_charge":"No","publisher":"Institute of Science and Technology Austria","related_material":{"record":[{"id":"19843","relation":"part_of_dissertation","status":"public"},{"id":"15083","status":"public","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","status":"public","id":"19074"}]},"OA_place":"publisher","date_created":"2025-06-25T13:50:10Z","file_date_updated":"2025-07-09T13:37:00Z","ec_funded":1,"tmp":{"image":"/images/cc_by_nc.png","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","short":"CC BY-NC (4.0)"},"ddc":["519"],"oa_version":"Published Version","doi_confirm":"1","day":"25","type":"dissertation","fulldoi":"https://doi.org/10.15479/AT-ISTA-19903","publication_status":"published","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","grant_number":"863818"},{"_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411"},{"grant_number":"COE12","name":"Bilateral Artificial Intelligence (Chatterjee)","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee"}],"date_published":"2025-06-25T00:00:00Z","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"has_accepted_license":"1","file":[{"checksum":"794c02f8c82ca59ba6dda3bd7eed871a","file_name":"Thesis Valentin Hübner source.tar.xz","file_id":"19905","file_size":6192760,"content_type":"application/x-xz","relation":"source_file","date_updated":"2025-06-25T13:38:07Z","date_created":"2025-06-25T13:38:07Z","access_level":"closed","creator":"vhuebner"},{"creator":"vhuebner","access_level":"open_access","date_created":"2025-07-09T13:37:00Z","content_type":"application/pdf","file_size":4837864,"date_updated":"2025-07-09T13:37:00Z","relation":"main_file","file_id":"19976","checksum":"ac56063d81c81e40322b6ff5a8c4912e","file_name":"Thesis Valentin Hübner.pdf"}],"citation":{"ista":"Hübner V. 2025. Reciprocity and inequality in social dilemmas. Institute of Science and Technology Austria.","short":"V. Hübner, Reciprocity and Inequality in Social Dilemmas, Institute of Science and Technology Austria, 2025.","mla":"Hübner, Valentin. <i>Reciprocity and Inequality in Social Dilemmas</i>. Institute of Science and Technology Austria, 2025, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-19903\">10.15479/AT-ISTA-19903</a>.","chicago":"Hübner, Valentin. “Reciprocity and Inequality in Social Dilemmas.” Institute of Science and Technology Austria, 2025. <a href=\"https://doi.org/10.15479/AT-ISTA-19903\">https://doi.org/10.15479/AT-ISTA-19903</a>.","ama":"Hübner V. Reciprocity and inequality in social dilemmas. 2025. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-19903\">10.15479/AT-ISTA-19903</a>","ieee":"V. Hübner, “Reciprocity and inequality in social dilemmas,” Institute of Science and Technology Austria, 2025.","apa":"Hübner, V. (2025). <i>Reciprocity and inequality in social dilemmas</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-19903\">https://doi.org/10.15479/AT-ISTA-19903</a>"},"doi":"10.15479/AT-ISTA-19903","publication_identifier":{"issn":["2663-337X"]},"alternative_title":["ISTA Thesis"],"acknowledgement":"The research for this thesis was supported by the European Research Council\r\n(grant agreements No. 863818 and No. 850529), the European Union’s Horizon 2020 research and innovation programme (Marie Skłodowska-Curie grant agreement No. 754411),\r\nthe Austrian Science Fund (grant DOI 10.55776/COE12), the French Agence Nationale\r\nde la Recherche under the Programme d’investissements d’avenir (project reference 17-\r\nEURE-0010) and the Australian Government through the Australian Research Council\r\n(grant No. SR200100005, “Securing Antarctica’s Environmental Future”).","abstract":[{"lang":"eng","text":"Cooperation, that is, one person paying a cost for another's benefit, is a fundamental principle without which no form of society could exist. The extent to which humans cooperate with each other is also an essential feature that differentiates them from other animals. Cooperation occurs even in the absence of altruistic motivations, when it is selfishly incentivised by the expectation of a future reward. For example, many economic interactions are well described that way. This kind of cooperation requires that people exhibit reciprocal behaviour that acts as a mechanism that rewards cooperation.\r\nWith game-theoretic models, it is possible to formally study potential such mechanisms and under what conditions they can exist. This thesis contributes to this effort by analysing recently introduced models of cooperation that advance on previous work by taking into account the potential for pre-existing inequality among cooperating individuals as well as the different forms that reciprocity can take.\r\nIndividuals may differ both intrinsically, in their abilities, as well as extrinsically, in the amount of resources they have available. Allowing for such differences in a model of cooperation helps to understand how inequality affects the potential for, and outcomes of, cooperation among unequals. In this thesis, it is shown that in the presence of intrinsic inequality, a similar unequal distribution of resources can increase the potential for cooperation. This effect is stronger the smaller the group is in which cooperation takes place. It is also shown that under particular assumptions, if the unequal members of a group vary the size of their contributions to a cooperative effort over time, they can thereby increase their efficiency and improve the collective outcome.\r\nCooperative behaviour in a two-person interaction can be rewarded either by direct reciprocation whenever the same two people interact again, or indirectly by a third party who observed the interaction. In the latter case of indirect reciprocity, individuals are proximally rewarded by a good reputation, which ultimately translates to being rewarded with cooperative behaviour by others. This mechanism can enable selfishly motivated cooperation even in circumstances where individuals are unlikely to meet again, akin to how money facilitates trade. While these two forms of reciprocity have mostly been studied in isolation, this thesis analyses both direct and indirect reciprocity in a general model in order to compare their relative effectiveness under different circumstances. The contribution of this thesis is an extension of previous work regarding a specific kind of interaction, whose parameters allow for convenient mathematical analysis, to the most general set of possible interactions."}],"_id":"19903","month":"06","oa":1},{"volume":44,"DOAJ_listed":"1","isi":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2025","author":[{"orcid":"0000-0002-8698-3823","id":"63836096-4690-11EA-BD4E-32803DDC885E","last_name":"Watson","full_name":"Watson, Jake","first_name":"Jake"},{"id":"2F55A9DE-F248-11E8-B48F-1D18A9856A87","full_name":"Vargas Barroso, Victor M","last_name":"Vargas Barroso","first_name":"Victor M"},{"orcid":"0000-0001-5001-4804","first_name":"Peter M","full_name":"Jonas, Peter M","last_name":"Jonas","id":"353C1B58-F248-11E8-B48F-1D18A9856A87"}],"corr_author":"1","status":"public","article_number":"116080","PlanS_conform":"1","language":[{"iso":"eng"}],"acknowledged_ssus":[{"_id":"Bio"},{"_id":"PreCl"},{"_id":"LifeSc"},{"_id":"M-Shop"}],"date_updated":"2026-09-16T06:58:59Z","issue":"8","tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa_version":"Published Version","ddc":["570"],"file_date_updated":"2025-08-04T06:53:07Z","ec_funded":1,"external_id":{"isi":["001544472300002"]},"OA_place":"publisher","date_created":"2025-08-03T22:01:30Z","publisher":"Elsevier","article_processing_charge":"Yes","title":"Cell-specific wiring routes information flow through hippocampal CA3","doi":"10.1016/j.celrep.2025.116080","publication_identifier":{"eissn":["2211-1247"],"issn":["2639-1856"]},"citation":{"ieee":"J. Watson, V. M. Vargas Barroso, and P. M. Jonas, “Cell-specific wiring routes information flow through hippocampal CA3,” <i>Cell Reports</i>, vol. 44, no. 8. Elsevier, 2025.","apa":"Watson, J., Vargas Barroso, V. M., &#38; Jonas, P. M. (2025). Cell-specific wiring routes information flow through hippocampal CA3. <i>Cell Reports</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.celrep.2025.116080\">https://doi.org/10.1016/j.celrep.2025.116080</a>","ama":"Watson J, Vargas Barroso VM, Jonas PM. Cell-specific wiring routes information flow through hippocampal CA3. <i>Cell Reports</i>. 2025;44(8). doi:<a href=\"https://doi.org/10.1016/j.celrep.2025.116080\">10.1016/j.celrep.2025.116080</a>","mla":"Watson, Jake, et al. “Cell-Specific Wiring Routes Information Flow through Hippocampal CA3.” <i>Cell Reports</i>, vol. 44, no. 8, 116080, Elsevier, 2025, doi:<a href=\"https://doi.org/10.1016/j.celrep.2025.116080\">10.1016/j.celrep.2025.116080</a>.","chicago":"Watson, Jake, Victor M Vargas Barroso, and Peter M Jonas. “Cell-Specific Wiring Routes Information Flow through Hippocampal CA3.” <i>Cell Reports</i>. Elsevier, 2025. <a href=\"https://doi.org/10.1016/j.celrep.2025.116080\">https://doi.org/10.1016/j.celrep.2025.116080</a>.","ista":"Watson J, Vargas Barroso VM, Jonas PM. 2025. Cell-specific wiring routes information flow through hippocampal CA3. Cell Reports. 44(8), 116080.","short":"J. Watson, V.M. Vargas Barroso, P.M. Jonas, Cell Reports 44 (2025)."},"scopus_import":"1","has_accepted_license":"1","file":[{"success":1,"file_id":"20106","file_name":"2025_CellReports_Watson.pdf","checksum":"556ff9760661ecd23949d75031043b1f","date_created":"2025-08-04T06:53:07Z","creator":"dernst","access_level":"open_access","relation":"main_file","date_updated":"2025-08-04T06:53:07Z","file_size":27695214,"content_type":"application/pdf"}],"department":[{"_id":"PeJo"}],"article_type":"original","date_published":"2025-08-01T00:00:00Z","project":[{"_id":"25B7EB9E-B435-11E9-9278-68D0E5697425","name":"Biophysics and circuit function of a giant cortical glutamatergic synapse","call_identifier":"H2020","grant_number":"692692"},{"call_identifier":"H2020","grant_number":"101026635","_id":"fc2be41b-9c52-11eb-aca3-faa90aa144e9","name":"Synaptic computations of the hippocampal CA3 circuitry"},{"name":"Mechanisms of GABA release in hippocampal circuits","_id":"bd88be38-d553-11ed-ba76-81d5a70a6ef5","grant_number":"P36232"},{"call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"},{"name":"Neuronal circuits in health and disease (Jonas)","_id":"0a6c8641-b036-11f1-bacf-e4eec62b5bb4","grant_number":"COE16"}],"type":"journal_article","publication_status":"published","fulldoi":"https://doi.org/10.1016/j.celrep.2025.116080","intvolume":"        44","day":"01","month":"08","oa":1,"_id":"20099","OA_type":"gold","publication":"Cell Reports","abstract":[{"lang":"eng","text":"The hippocampus, critical for learning and memory, is dogmatically described as a trisynaptic circuit where dentate gyrus granule cells (GCs), CA3 pyramidal neurons (PNs), and CA1 PNs are serially connected. However, CA3 also forms an autoassociative network, and its PNs have diverse morphologies, intrinsic properties, and GC input levels. How PN subtypes compose this recurrent network is unknown. To determine the synaptic arrangement of identified CA3 PNs, we combine multicellular patch-clamp recording and post hoc morphological analysis in mouse hippocampal slices. PNs can be divided into distinct “superficial” and “deep” subclasses, the latter including previously reported “athorny” cells. Subclasses have distinct input-output transformations and asymmetric connectivity, which is more abundant from superficial to deep PNs, splitting CA3 locally into two parallel recurrent networks. Coincident spontaneous inhibition occurs frequently within but not between subclasses, implying subclass-specific inhibitory innervation. Our results suggest two separately controlled sublayers for parallel information processing in hippocampal CA3."}],"acknowledgement":"We thank Andrea Navas-Olive and Rebecca J. Morse-Mora for critically reading an earlier version of the manuscript. We also thank Florian Marr and Christina Altmutter for excellent technical assistance, Alois Schlögl for programming and data-handling assistance, Todor Asenov for technical support, and Eleftheria Kralli-Beller for manuscript editing. This research was supported by the Scientific Services Units (SSUs) of ISTA. We are particularly grateful for assistance from the Imaging and Optics Facility, Preclinical Facility, Lab Support Facility, and Miba Machine Shop. The project received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement no. 692692 to P.J., Marie Skłodowska-Curie Actions Individual Fellowship no. 101026635 to J.F.W., and an ISTplus Fellowship through Marie Skłodowska-Curie grant agreement no. 754411 to V.V.-B.), the Austrian Science Fund (P 36232-B, PAT 4178023, and Cluster of Excellence 10.55776/COE16 to P.J.), and a CONACyT fellowship (289638 to V.V.-B.) and was supported by a non-stipendiary EMBO fellowship (ALTF 756–2020 to J.F.W.).","quality_controlled":"1"},{"intvolume":"         4","day":"01","type":"journal_article","fulldoi":"https://doi.org/10.1093/pnasnexus/pgaf154","publication_status":"published","project":[{"call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"article_type":"original","date_published":"2025-05-01T00:00:00Z","department":[{"_id":"KrCh"}],"scopus_import":"1","file":[{"creator":"dernst","access_level":"open_access","date_created":"2025-06-23T08:09:50Z","content_type":"application/pdf","file_size":2551195,"date_updated":"2025-06-23T08:09:50Z","relation":"main_file","file_id":"19867","success":1,"checksum":"efd6648db3fc3ea0cdd7155d667e5f11","file_name":"2025_PNASNexus_Huebner.pdf"}],"has_accepted_license":"1","citation":{"ama":"Hübner V, Schmid L, Hilbe C, Chatterjee K. Stable strategies of direct and indirect reciprocity across all social dilemmas. <i>PNAS Nexus</i>. 2025;4(5). doi:<a href=\"https://doi.org/10.1093/pnasnexus/pgaf154\">10.1093/pnasnexus/pgaf154</a>","ieee":"V. Hübner, L. Schmid, C. Hilbe, and K. Chatterjee, “Stable strategies of direct and indirect reciprocity across all social dilemmas,” <i>PNAS Nexus</i>, vol. 4, no. 5. Oxford University Press, 2025.","apa":"Hübner, V., Schmid, L., Hilbe, C., &#38; Chatterjee, K. (2025). Stable strategies of direct and indirect reciprocity across all social dilemmas. <i>PNAS Nexus</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/pnasnexus/pgaf154\">https://doi.org/10.1093/pnasnexus/pgaf154</a>","ista":"Hübner V, Schmid L, Hilbe C, Chatterjee K. 2025. Stable strategies of direct and indirect reciprocity across all social dilemmas. PNAS Nexus. 4(5), pgaf154.","short":"V. Hübner, L. Schmid, C. Hilbe, K. Chatterjee, PNAS Nexus 4 (2025).","mla":"Hübner, Valentin, et al. “Stable Strategies of Direct and Indirect Reciprocity across All Social Dilemmas.” <i>PNAS Nexus</i>, vol. 4, no. 5, pgaf154, Oxford University Press, 2025, doi:<a href=\"https://doi.org/10.1093/pnasnexus/pgaf154\">10.1093/pnasnexus/pgaf154</a>.","chicago":"Hübner, Valentin, Laura Schmid, Christian Hilbe, and Krishnendu Chatterjee. “Stable Strategies of Direct and Indirect Reciprocity across All Social Dilemmas.” <i>PNAS Nexus</i>. Oxford University Press, 2025. <a href=\"https://doi.org/10.1093/pnasnexus/pgaf154\">https://doi.org/10.1093/pnasnexus/pgaf154</a>."},"doi":"10.1093/pnasnexus/pgaf154","publication_identifier":{"eissn":["2752-6542"]},"quality_controlled":"1","acknowledgement":"This work was supported by the European Research Council CoG 863818 (ForM-SMArt) (to K.C.) and the European Research Council Starting Grant 850529: E-DIRECT (to C.H.).","abstract":[{"text":"Social dilemmas are collective-action problems where individual interests are at odds with group interests. Such dilemmas occur frequently at all scales of human interactions. When dealing with collective-action problems, people often act reciprocally. They adjust their behavior to match the previous behavior of the recipient. The literature distinguishes two kinds of reciprocity. According to direct reciprocity, individuals react to their immediate experiences with the recipient. They are more likely to cooperate if the recipient previously cooperated with them. According to indirect reciprocity, individuals react to the recipient’s general behavior, irrespectively of whether or not they benefited directly. In practice, the two kinds of reciprocity are often intertwined; people typically base their decisions on both direct experiences and indirect observations. Yet only recently have researchers begun to explore how the two kinds of reciprocity interact. So far, this research only addresses a single type of social dilemma, the donation game, where the effects of individual behaviors are independent. Instead, here we allow for all pairwise social dilemmas. By applying novel techniques to generalize the theory of zero-determinant strategies, we establish an important proof of principle: In all social dilemmas, socially optimal outcomes can be sustained as an equilibrium, using either direct or indirect reciprocity, or arbitrary mixtures thereof. These results neither require games to be repeated infinitely often, nor that individual opinions are synchronized. In this way, we considerably generalize the scope of models of reciprocity, and we build further bridges between the literatures on direct and indirect reciprocity.","lang":"eng"}],"publication":"PNAS Nexus","OA_type":"gold","_id":"19843","month":"05","oa":1,"date_updated":"2026-09-16T06:58:23Z","language":[{"iso":"eng"}],"article_number":"pgaf154","corr_author":"1","author":[{"first_name":"Valentin","full_name":"Hübner, Valentin","last_name":"Hübner","id":"2c8aa207-dc7d-11ea-9b2f-f22972ecd910","orcid":"0009-0001-5009-4987"},{"orcid":"0000-0002-6978-7329","full_name":"Schmid, Laura","last_name":"Schmid","id":"38B437DE-F248-11E8-B48F-1D18A9856A87","first_name":"Laura"},{"full_name":"Hilbe, Christian","last_name":"Hilbe","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","first_name":"Christian","orcid":"0000-0001-5116-955X"},{"first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2025","DOAJ_listed":"1","volume":4,"title":"Stable strategies of direct and indirect reciprocity across all social dilemmas","article_processing_charge":"Yes","publisher":"Oxford University Press","OA_place":"publisher","related_material":{"record":[{"id":"19903","relation":"dissertation_contains","status":"public"}]},"pmid":1,"date_created":"2025-06-15T22:01:30Z","external_id":{"pmid":["40417077"]},"file_date_updated":"2025-06-23T08:09:50Z","ec_funded":1,"issue":"5","tmp":{"image":"/images/cc_by_nc.png","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","short":"CC BY-NC (4.0)"},"ddc":["000"],"oa_version":"Published Version"},{"department":[{"_id":"KrCh"}],"article_type":"original","date_published":"2025-11-01T00:00:00Z","citation":{"ista":"Hübner V, Hilbe C, Staab M, Kleshnina M, Chatterjee K. 2025. Time-dependent strategies in repeated asymmetric public goods games. Dynamic Games and Applications. 15, 1617–1645.","short":"V. Hübner, C. Hilbe, M. Staab, M. Kleshnina, K. Chatterjee, Dynamic Games and Applications 15 (2025) 1617–1645.","chicago":"Hübner, Valentin, Christian Hilbe, Manuel Staab, Maria Kleshnina, and Krishnendu Chatterjee. “Time-Dependent Strategies in Repeated Asymmetric Public Goods Games.” <i>Dynamic Games and Applications</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s13235-025-00627-5\">https://doi.org/10.1007/s13235-025-00627-5</a>.","mla":"Hübner, Valentin, et al. “Time-Dependent Strategies in Repeated Asymmetric Public Goods Games.” <i>Dynamic Games and Applications</i>, vol. 15, Springer Nature, 2025, pp. 1617–45, doi:<a href=\"https://doi.org/10.1007/s13235-025-00627-5\">10.1007/s13235-025-00627-5</a>.","ama":"Hübner V, Hilbe C, Staab M, Kleshnina M, Chatterjee K. Time-dependent strategies in repeated asymmetric public goods games. <i>Dynamic Games and Applications</i>. 2025;15:1617-1645. doi:<a href=\"https://doi.org/10.1007/s13235-025-00627-5\">10.1007/s13235-025-00627-5</a>","apa":"Hübner, V., Hilbe, C., Staab, M., Kleshnina, M., &#38; Chatterjee, K. (2025). Time-dependent strategies in repeated asymmetric public goods games. <i>Dynamic Games and Applications</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s13235-025-00627-5\">https://doi.org/10.1007/s13235-025-00627-5</a>","ieee":"V. Hübner, C. Hilbe, M. Staab, M. Kleshnina, and K. Chatterjee, “Time-dependent strategies in repeated asymmetric public goods games,” <i>Dynamic Games and Applications</i>, vol. 15. Springer Nature, pp. 1617–1645, 2025."},"publication_identifier":{"eissn":["2153-0793"],"issn":["2153-0785"]},"doi":"10.1007/s13235-025-00627-5","scopus_import":"1","has_accepted_license":"1","file":[{"file_name":"2025_DynGamesAppl_Huebner.pdf","checksum":"de0a412cbb7d98bf5e6a551c26acbefa","success":1,"file_id":"20888","date_updated":"2025-12-30T08:01:35Z","relation":"main_file","content_type":"application/pdf","file_size":1126178,"access_level":"open_access","creator":"dernst","date_created":"2025-12-30T08:01:35Z"}],"type":"journal_article","fulldoi":"https://doi.org/10.1007/s13235-025-00627-5","publication_status":"published","intvolume":"        15","day":"01","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020"},{"_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411"}],"OA_type":"hybrid","month":"11","oa":1,"_id":"19074","acknowledgement":"This work was supported by the European Research Council CoG 863818 (ForM-SMArt) (to K.C.) and the European Research Council Starting Grant 850529: E-DIRECT (to C.H.), the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement #754411 and the French Agence Nationale de la Recherche (under the Investissement d’Avenir programme, ANR-17-EURE-0010), and ARC SRIEAS Grant SR200100005 Securing Antarctica’s Environmental Future (to M.K.). Open access funding provided by Institute of Science and Technology (IST Austria).","quality_controlled":"1","publication":"Dynamic Games and Applications","abstract":[{"text":"The public goods game is among the most studied metaphors of cooperation in groups. In this game, individuals can use their endowments to make contributions towards a good that benefits everyone. Each individual, however, is tempted to free-ride on the contributions of others. Herein, we study repeated public goods games among asymmetric players. Previous work has explored to which extent asymmetry allows for full cooperation, such that players contribute their full endowment each round. However, by design that work focusses on equilibria where individuals make the same contribution each round. Instead, here we consider players whose contributions along the equilibrium path can change from one round to the next. We do so for three different models – one without any budget constraints, one with endowment constraints, and one in which individuals can save their current endowment to be used in subsequent rounds. In each case, we explore two key quantities: the welfare and the resource efficiency that can be achieved in equilibrium. Welfare corresponds to the sum of all players’ payoffs. Resource efficiency relates this welfare to the total contributions made by the players. Compared to constant contribution sequences, we find that time-dependent contributions can improve resource efficiency across all three models. Moreover, they can improve the players’ welfare in the model with savings.","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2025","corr_author":"1","author":[{"orcid":"0009-0001-5009-4987","first_name":"Valentin","id":"2c8aa207-dc7d-11ea-9b2f-f22972ecd910","last_name":"Hübner","full_name":"Hübner, Valentin"},{"orcid":"0000-0001-5116-955X","first_name":"Christian","full_name":"Hilbe, Christian","last_name":"Hilbe","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Staab, Manuel","last_name":"Staab","first_name":"Manuel"},{"last_name":"Kleshnina","full_name":"Kleshnina, Maria","id":"4E21749C-F248-11E8-B48F-1D18A9856A87","first_name":"Maria","orcid":"0000-0002-5518-8317"},{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"}],"status":"public","volume":15,"isi":1,"PlanS_conform":"1","language":[{"iso":"eng"}],"date_updated":"2026-09-16T06:58:23Z","page":"1617-1645","external_id":{"isi":["001415587800001"]},"ddc":["000"],"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa_version":"Published Version","file_date_updated":"2025-12-30T08:01:35Z","ec_funded":1,"article_processing_charge":"Yes (via OA deal)","title":"Time-dependent strategies in repeated asymmetric public goods games","OA_place":"publisher","related_material":{"record":[{"id":"19903","relation":"dissertation_contains","status":"public"}]},"date_created":"2025-02-23T23:01:57Z","publisher":"Springer Nature"},{"has_accepted_license":"1","file":[{"success":1,"file_id":"20177","file_name":"2025_Svoboda_Jakub_Thesis.pdf","checksum":"c6c4df9777f4537940de7ab392ad57e2","date_created":"2025-08-14T09:54:43Z","creator":"jsvoboda","access_level":"open_access","relation":"main_file","date_updated":"2025-08-14T09:54:43Z","content_type":"application/pdf","file_size":5927291},{"date_updated":"2025-08-21T11:48:39Z","relation":"source_file","file_size":6731815,"content_type":"application/zip","creator":"jsvoboda","access_level":"closed","date_created":"2025-08-14T09:55:20Z","file_name":"2025_Svoboda_Jakub_Thesis.zip","checksum":"485e9f9822821bc03666d245d80aaa08","file_id":"20178"}],"doi":"10.15479/AT-ISTA-20138","alternative_title":["ISTA Thesis"],"publication_identifier":{"issn":["2663-337X"]},"citation":{"ieee":"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>","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>","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>.","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>.","short":"J. Svoboda, Structural Properties of Games on Graphs, Institute of Science and Technology Austria, 2025.","ista":"Svoboda J. 2025. Structural properties of games on graphs. Institute of Science and Technology Austria."},"date_published":"2025-08-05T00:00:00Z","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020"},{"grant_number":"COE12","name":"Bilateral Artificial Intelligence (Chatterjee)","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee"}],"day":"05","publication_status":"published","fulldoi":"https://doi.org/10.15479/AT-ISTA-20138","type":"dissertation","publisher_comment":"Chapter 4 is copyrighted by CC BY-NC-ND\r\n4.0, which prohibits derivatives. Chapter 6 is copyrighted: Copyright (2025) by the American\r\nPhysical Society. For a copy, redistribution, or modification needs to be permitted by the\r\nAmerican Physical Society.\r\n","_id":"20138","oa":1,"month":"08","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"}],"acknowledgement":"This work was supported by the European Research Council CoG 863818 (ForMSMArt) and Austrian Science Fund 10.55776/COE12.\r\n","status":"public","author":[{"orcid":"0000-0002-1419-3267","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","full_name":"Svoboda, Jakub","last_name":"Svoboda","first_name":"Jakub"}],"corr_author":"1","year":"2025","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"167","degree_awarded":"PhD","supervisor":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"}],"date_updated":"2026-09-16T06:59:33Z","language":[{"iso":"eng"}],"das_tickbox":"1","license":"https://creativecommons.org/licenses/by-nc-sa/4.0/","ec_funded":1,"file_date_updated":"2025-08-21T11:48:39Z","ddc":["000","519"],"tmp":{"image":"/images/cc_by_nc_sa.png","short":"CC BY-NC-SA (4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)"},"doi_confirm":"1","oa_version":"Published Version","publisher":"Institute of Science and Technology Austria","date_created":"2025-08-05T14:33:59Z","OA_place":"publisher","related_material":{"record":[{"id":"12787","relation":"part_of_dissertation","status":"public"},{"id":"12101","status":"public","relation":"part_of_dissertation"},{"id":"12257","status":"public","relation":"part_of_dissertation"},{"id":"15297","status":"public","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","status":"public","id":"18703"}]},"title":"Structural properties of games on graphs","article_processing_charge":"No"},{"publication":"The 41st Conference on Uncertainty in Artificial Intelligence","abstract":[{"lang":"eng","text":"Deterministic Markov Decision Processes (DMDPs) are a mathematical framework for decision-making where the outcomes and future possible actions are deterministically determined by the current action taken. DMDPs can be viewed as a finite directed weighted graph, where in each step, the controller chooses an outgoing edge. An objective is a measurable function on runs (or infinite trajectories) of the DMDP, and the value for an objective is the maximal cumulative reward (or weight) that the controller can guarantee. We consider the classical mean-payoff (aka limit-average) objective, which is a basic and fundamental objective.\r\n\r\nHoward's policy iteration algorithm is a popular method for solving DMDPs with mean-payoff objectives. Although Howard's algorithm performs well in practice, as experimental studies suggested, the best known upper bound is exponential and the current known lower bound is as follows: For the input size I, the algorithm requires (math formular) iterations, where (math formular) hides the poly-logarithmic factors, i.e., the current lower bound on iterations is sub-linear with respect to the input size. Our main result is an improved lower bound for this fundamental algorithm where we show that for the input size I, the algorithm requires (math formular) iterations."}],"acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant and Austrian Science Fund (FWF) 10.55776/COE12.\r\n","quality_controlled":"1","month":"01","oa":1,"_id":"20299","OA_type":"diamond","conference":{"name":"UAI: Conference on Uncertainty in Artificial Intelligence","end_date":"2025-07-25","location":"Rio de Janeiro, Brazil","start_date":"2025-07-21"},"project":[{"call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"},{"grant_number":"COE12","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","name":"Bilateral Artificial Intelligence (Chatterjee)"}],"type":"conference","publication_status":"published","intvolume":"       286","day":"01","alternative_title":["PMLR"],"citation":{"ama":"Asadi A, Chatterjee K, De Raaij J. Lower bound on Howard policy iteration for deterministic Markov Decision Processes. In: <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>. Vol 286. ML Research Press; 2025:223-232.","apa":"Asadi, A., Chatterjee, K., &#38; De Raaij, J. (2025). Lower bound on Howard policy iteration for deterministic Markov Decision Processes. In <i>The 41st Conference on Uncertainty in Artificial Intelligence</i> (Vol. 286, pp. 223–232). Rio de Janeiro, Brazil: ML Research Press.","ieee":"A. Asadi, K. Chatterjee, and J. De Raaij, “Lower bound on Howard policy iteration for deterministic Markov Decision Processes,” in <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>, Rio de Janeiro, Brazil, 2025, vol. 286, pp. 223–232.","short":"A. Asadi, K. Chatterjee, J. De Raaij, in:, The 41st Conference on Uncertainty in Artificial Intelligence, ML Research Press, 2025, pp. 223–232.","ista":"Asadi A, Chatterjee K, De Raaij J. 2025. Lower bound on Howard policy iteration for deterministic Markov Decision Processes. The 41st Conference on Uncertainty in Artificial Intelligence. UAI: Conference on Uncertainty in Artificial Intelligence, PMLR, vol. 286, 223–232.","chicago":"Asadi, Ali, Krishnendu Chatterjee, and Jakob De Raaij. “Lower Bound on Howard Policy Iteration for Deterministic Markov Decision Processes.” In <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>, 286:223–32. ML Research Press, 2025.","mla":"Asadi, Ali, et al. “Lower Bound on Howard Policy Iteration for Deterministic Markov Decision Processes.” <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>, vol. 286, ML Research Press, 2025, pp. 223–32."},"publication_identifier":{"eissn":["2640-3498"]},"scopus_import":"1","has_accepted_license":"1","file":[{"content_type":"application/pdf","file_size":317097,"relation":"main_file","date_updated":"2025-09-09T06:27:59Z","date_created":"2025-09-09T06:27:59Z","creator":"dernst","access_level":"open_access","checksum":"4180c81bb6ed3b4f5c7a8e48d06520c6","file_name":"2025_UAI_Asadi.pdf","file_id":"20313","success":1}],"department":[{"_id":"KrCh"},{"_id":"GradSch"}],"date_published":"2025-01-01T00:00:00Z","OA_place":"publisher","date_created":"2025-09-07T22:01:34Z","publisher":"ML Research Press","article_processing_charge":"No","title":"Lower bound on Howard policy iteration for deterministic Markov Decision Processes","tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa_version":"Published Version","ddc":["000"],"file_date_updated":"2025-09-09T06:27:59Z","arxiv":1,"ec_funded":1,"external_id":{"arxiv":["2506.12254"]},"page":"223-232","language":[{"iso":"eng"}],"date_updated":"2026-09-16T07:01:05Z","volume":286,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2025","corr_author":"1","author":[{"first_name":"Ali","last_name":"Asadi","full_name":"Asadi, Ali","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb"},{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"last_name":"De Raaij","full_name":"De Raaij, Jakob","first_name":"Jakob"}],"status":"public"},{"page":"238-247","date_updated":"2026-09-16T07:03:02Z","language":[{"iso":"eng"}],"volume":286,"author":[{"first_name":"Ali","full_name":"Asadi, Ali","last_name":"Asadi","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb"},{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu"},{"last_name":"Saona Urmeneta","full_name":"Saona Urmeneta, Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J","orcid":"0000-0001-5103-038X"},{"id":"2783031a-7378-11f0-b2d0-f17f1db2ebad","last_name":"Shafiee","full_name":"Shafiee, Ali","first_name":"Ali"}],"corr_author":"1","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2025","publisher":"ML Research Press","OA_place":"publisher","date_created":"2025-09-07T22:01:34Z","title":"Limit-sure reachability for small memory policies in POMDPs is NP-complete","article_processing_charge":"No","file_date_updated":"2025-09-09T08:19:41Z","arxiv":1,"ec_funded":1,"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa_version":"Published Version","ddc":["000"],"external_id":{"arxiv":["2412.00941"]},"project":[{"grant_number":"863818","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"},{"name":"Bilateral Artificial Intelligence (Chatterjee)","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","grant_number":"COE12"}],"intvolume":"       286","day":"01","type":"conference","publication_status":"published","scopus_import":"1","has_accepted_license":"1","file":[{"content_type":"application/pdf","file_size":307458,"relation":"main_file","date_updated":"2025-09-09T08:19:41Z","date_created":"2025-09-09T08:19:41Z","access_level":"open_access","creator":"dernst","checksum":"1a37ebe7ba73ab6985765bf0d17a0acc","file_name":"2025_UAI_AsadiAli.pdf","file_id":"20315","success":1}],"publication_identifier":{"eissn":["2640-3498"]},"alternative_title":["PMLR"],"citation":{"ama":"Asadi A, Chatterjee K, Saona Urmeneta RJ, Shafiee A. Limit-sure reachability for small memory policies in POMDPs is NP-complete. In: <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>. Vol 286. ML Research Press; 2025:238-247.","apa":"Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., &#38; Shafiee, A. (2025). Limit-sure reachability for small memory policies in POMDPs is NP-complete. In <i>The 41st Conference on Uncertainty in Artificial Intelligence</i> (Vol. 286, pp. 238–247). Rio de Janeiro, Brazil: ML Research Press.","ieee":"A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and A. Shafiee, “Limit-sure reachability for small memory policies in POMDPs is NP-complete,” in <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>, Rio de Janeiro, Brazil, 2025, vol. 286, pp. 238–247.","short":"A. Asadi, K. Chatterjee, R.J. Saona Urmeneta, A. Shafiee, in:, The 41st Conference on Uncertainty in Artificial Intelligence, ML Research Press, 2025, pp. 238–247.","ista":"Asadi A, Chatterjee K, Saona Urmeneta RJ, Shafiee A. 2025. Limit-sure reachability for small memory policies in POMDPs is NP-complete. The 41st Conference on Uncertainty in Artificial Intelligence. UAI: Conference on Uncertainty in Artificial Intelligence, PMLR, vol. 286, 238–247.","mla":"Asadi, Ali, et al. “Limit-Sure Reachability for Small Memory Policies in POMDPs Is NP-Complete.” <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>, vol. 286, ML Research Press, 2025, pp. 238–47.","chicago":"Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Ali Shafiee. “Limit-Sure Reachability for Small Memory Policies in POMDPs Is NP-Complete.” In <i>The 41st Conference on Uncertainty in Artificial Intelligence</i>, 286:238–47. ML Research Press, 2025."},"date_published":"2025-07-01T00:00:00Z","department":[{"_id":"KrCh"},{"_id":"GradSch"}],"abstract":[{"text":"A standard model that arises in several applications in sequential decision-making is partially observable Markov decision processes (POMDPs) where a decision-making agent interacts with an uncertain environment. A basic objective in POMDPs is the reachability objective, where given a target set of states, the goal is to eventually arrive at one of them.\r\n\r\nThe limit-sure problem asks whether reachability can be ensured with probability arbitrarily close to 1. In general, the limit-sure reachability problem for POMDPs is undecidable. However, in many practical cases, the most relevant question is the existence of policies with a small amount of memory. In this work, we study the limit-sure reachability problem for POMDPs with a fixed amount of memory. We establish that the computational complexity of the problem is NP-complete.","lang":"eng"}],"publication":"The 41st Conference on Uncertainty in Artificial Intelligence","quality_controlled":"1","acknowledgement":"This research was partially supported by Austrian Science Fund (FWF) 10.55776/COE12, the support of the French Agence Nationale de la Recherche (ANR) under reference ANR-21-CE40-0020 (CONVERGENCE project), and the ERC CoG 863818 (ForM-SMArt) grant.","_id":"20297","month":"07","oa":1,"OA_type":"diamond","conference":{"name":"UAI: Conference on Uncertainty in Artificial Intelligence","end_date":"2025-07-25","location":"Rio de Janeiro, Brazil","start_date":"2025-07-21"}},{"ec_funded":1,"file_date_updated":"2025-09-09T08:10:13Z","arxiv":1,"ddc":["000"],"oa_version":"Published Version","external_id":{"arxiv":["2505.19932"]},"publisher":"ML Research Press","date_created":"2025-09-07T22:01:34Z","OA_place":"publisher","title":"Logic gate neural networks are good for verification","article_processing_charge":"No","volume":288,"status":"public","corr_author":"1","author":[{"id":"faff3c84-23f6-11ef-9085-e5187b51c604","full_name":"Kresse, Fabian","last_name":"Kresse","first_name":"Fabian"},{"orcid":"0000-0002-4993-773X","first_name":"Zhengqi","last_name":"Yu","full_name":"Yu, Zhengqi","id":"20aa2ae8-f2f1-11ed-bbfa-8205053f1342"},{"orcid":"0000-0001-8622-7887","first_name":"Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","full_name":"Lampert, Christoph","last_name":"Lampert"},{"full_name":"Henzinger, Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","orcid":"0000-0002-2985-7724"}],"year":"2025","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_number":"26","date_updated":"2026-09-16T07:02:18Z","acknowledged_ssus":[{"_id":"ScienComp"}],"language":[{"iso":"eng"}],"_id":"20296","oa":1,"month":"06","OA_type":"diamond","conference":{"start_date":"2025-05-28","location":"Philadephia, PA, United States","end_date":"2025-05-30","name":"NeuS: International Conferenceon Neuro-Symbolic Systems"},"abstract":[{"lang":"eng","text":"Learning-based systems are increasingly deployed across various domains, yet the complexity of traditional neural networks poses significant challenges for formal verification. Unlike conventional neural networks, learned Logic Gate Networks (LGNs) replace multiplications with Boolean logic gates, yielding a sparse, netlist-like architecture that is inherently more amenable to symbolic verification, while still delivering promising performance. In this paper, we introduce a SAT encoding for verifying global robustness and fairness in LGNs. We evaluate our method on five benchmark datasets, including a newly constructed 5-class variant, and find that LGNs are both verification-friendly and maintain strong predictive performance."}],"publication":"2nd International Conferenceon Neuro-Symbolic Systems","quality_controlled":"1","acknowledgement":"This work is supported in part by the ERC grant under Grant No. ERC-2020-AdG 101020093 and\r\nthe Austrian Science Fund (FWF) [10.55776/COE12]. This research was supported by the Scientific\r\nService Units (SSU) of ISTA through resources provided by Scientific Computing (SciComp).","has_accepted_license":"1","file":[{"date_created":"2025-09-09T08:10:13Z","access_level":"open_access","creator":"dernst","relation":"main_file","date_updated":"2025-09-09T08:10:13Z","file_size":295466,"content_type":"application/pdf","success":1,"file_id":"20314","file_name":"2025_NeuS_Kresse.pdf","checksum":"90a32defed34787e771a5c1623b6b0d2"}],"scopus_import":"1","publication_identifier":{"eissn":["2640-3498"]},"citation":{"ama":"Kresse F, Yu E, Lampert C, Henzinger TA. Logic gate neural networks are good for verification. In: <i>2nd International Conferenceon Neuro-Symbolic Systems</i>. Vol 288. ML Research Press; 2025.","apa":"Kresse, F., Yu, E., Lampert, C., &#38; Henzinger, T. A. (2025). Logic gate neural networks are good for verification. In <i>2nd International Conferenceon Neuro-Symbolic Systems</i> (Vol. 288). Philadephia, PA, United States: ML Research Press.","ieee":"F. Kresse, E. Yu, C. Lampert, and T. A. Henzinger, “Logic gate neural networks are good for verification,” in <i>2nd International Conferenceon Neuro-Symbolic Systems</i>, Philadephia, PA, United States, 2025, vol. 288.","ista":"Kresse F, Yu E, Lampert C, Henzinger TA. 2025. Logic gate neural networks are good for verification. 2nd International Conferenceon Neuro-Symbolic Systems. NeuS: International Conferenceon Neuro-Symbolic Systems, PMLR, vol. 288, 26.","short":"F. Kresse, E. Yu, C. Lampert, T.A. Henzinger, in:, 2nd International Conferenceon Neuro-Symbolic Systems, ML Research Press, 2025.","mla":"Kresse, Fabian, et al. “Logic Gate Neural Networks Are Good for Verification.” <i>2nd International Conferenceon Neuro-Symbolic Systems</i>, vol. 288, 26, ML Research Press, 2025.","chicago":"Kresse, Fabian, Emily Yu, Christoph Lampert, and Thomas A Henzinger. “Logic Gate Neural Networks Are Good for Verification.” In <i>2nd International Conferenceon Neuro-Symbolic Systems</i>, Vol. 288. ML Research Press, 2025."},"alternative_title":["PMLR"],"date_published":"2025-06-01T00:00:00Z","department":[{"_id":"ChLa"},{"_id":"ToHe"}],"project":[{"name":"Vigilant Algorithmic Monitoring of Software","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","grant_number":"101020093","call_identifier":"H2020"},{"grant_number":"COE12","name":"Bilateral Artificial Intelligence (Lampert)","_id":"d8f03aaa-b035-11f1-8588-d5147fa879e0"}],"day":"01","intvolume":"       288","publication_status":"published","type":"conference"},{"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"ddc":["000"],"oa_version":"Published Version","ec_funded":1,"file_date_updated":"2025-12-30T08:13:04Z","external_id":{"isi":["001449708900001"]},"date_created":"2025-04-06T22:01:32Z","OA_place":"publisher","related_material":{"record":[{"id":"20234","relation":"dissertation_contains","status":"public"}]},"publisher":"Springer Nature","article_processing_charge":"Yes (via OA deal)","title":"Random zero-sum dynamic games on infinite directed graphs","volume":15,"isi":1,"year":"2025","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","author":[{"last_name":"Attia","full_name":"Attia, Luc","first_name":"Luc"},{"first_name":"Lyuben","last_name":"Lichev","full_name":"Lichev, Lyuben","id":"9aa8388e-d003-11ee-8458-c4c1d7447977"},{"first_name":"Dieter","last_name":"Mitsche","full_name":"Mitsche, Dieter"},{"orcid":"0000-0001-5103-038X","last_name":"Saona Urmeneta","full_name":"Saona Urmeneta, Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J"},{"full_name":"Ziliotto, Bruno","last_name":"Ziliotto","first_name":"Bruno"}],"corr_author":"1","page":"1517-1535","language":[{"iso":"eng"}],"PlanS_conform":"1","date_updated":"2026-09-16T07:00:33Z","oa":1,"month":"11","_id":"19508","OA_type":"hybrid","publication":"Dynamic Games and Applications","abstract":[{"lang":"eng","text":"We consider random two-player zero-sum dynamic games with perfect information on a class of infinite directed graphs. Starting from a fixed vertex, the players take turns to move a token along the edges of the graph. Every vertex is assigned a payoff known in advance by both players. Every time the token visits a vertex, Player 2 pays Player 1 the corresponding payoff. We consider a distribution over such games by assigning i.i.d. payoffs to the vertices. On the one hand, for acyclic directed graphs of bounded degree and sub-exponential expansion, we show that, when the duration of the game tends to infinity, the value converges almost surely to a constant at an exponential rate dominated in terms of the expansion. On the other hand, for the infinite d-ary tree (that does not fall into the previous class of graphs), we show convergence at a double-exponential rate."}],"acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). This work was supported by the French Agence Nationale de la Recherche (ANR) under references ANR-21-CE40-0020 (CONVERGENCE project) and ANR-20-CE40-0002 (GrHyDy), by Fondecyt grant 1220174, by ANID Chile grant ACT210005, and by the ERC CoG 863818 (ForM-SMArt) grant. This collaboration was mainly conducted during a 1-year visit of Bruno Ziliotto to the Center for Mathematical Modeling (CMM) at University of Chile in 2023, under the IRL program of CNRS. This work was supported by Fondation CFM pour la Recherche. This paper has also been funded by the Agence Nationale de la Recherche under grant ANR-17-EURE-0010 (Investissements d’Avenir program).","quality_controlled":"1","doi":"10.1007/s13235-025-00636-4","citation":{"ista":"Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. 2025. Random zero-sum dynamic games on infinite directed graphs. Dynamic Games and Applications. 15, 1517–1535.","short":"L. Attia, L. Lichev, D. Mitsche, R.J. Saona Urmeneta, B. Ziliotto, Dynamic Games and Applications 15 (2025) 1517–1535.","mla":"Attia, Luc, et al. “Random Zero-Sum Dynamic Games on Infinite Directed Graphs.” <i>Dynamic Games and Applications</i>, vol. 15, Springer Nature, 2025, pp. 1517–35, doi:<a href=\"https://doi.org/10.1007/s13235-025-00636-4\">10.1007/s13235-025-00636-4</a>.","chicago":"Attia, Luc, Lyuben Lichev, Dieter Mitsche, Raimundo J Saona Urmeneta, and Bruno Ziliotto. “Random Zero-Sum Dynamic Games on Infinite Directed Graphs.” <i>Dynamic Games and Applications</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/s13235-025-00636-4\">https://doi.org/10.1007/s13235-025-00636-4</a>.","ama":"Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. Random zero-sum dynamic games on infinite directed graphs. <i>Dynamic Games and Applications</i>. 2025;15:1517-1535. doi:<a href=\"https://doi.org/10.1007/s13235-025-00636-4\">10.1007/s13235-025-00636-4</a>","ieee":"L. Attia, L. Lichev, D. Mitsche, R. J. Saona Urmeneta, and B. Ziliotto, “Random zero-sum dynamic games on infinite directed graphs,” <i>Dynamic Games and Applications</i>, vol. 15. Springer Nature, pp. 1517–1535, 2025.","apa":"Attia, L., Lichev, L., Mitsche, D., Saona Urmeneta, R. J., &#38; Ziliotto, B. (2025). Random zero-sum dynamic games on infinite directed graphs. <i>Dynamic Games and Applications</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s13235-025-00636-4\">https://doi.org/10.1007/s13235-025-00636-4</a>"},"publication_identifier":{"issn":["2153-0785"],"eissn":["2153-0793"]},"has_accepted_license":"1","file":[{"access_level":"open_access","creator":"dernst","date_created":"2025-12-30T08:13:04Z","date_updated":"2025-12-30T08:13:04Z","relation":"main_file","content_type":"application/pdf","file_size":570994,"success":1,"file_id":"20891","file_name":"2025_DynGamesAppl_Attia.pdf","checksum":"b3a1b7eef40c9ac2acf3fef563081694"}],"scopus_import":"1","department":[{"_id":"MaKw"},{"_id":"KrCh"}],"date_published":"2025-11-01T00:00:00Z","article_type":"original","project":[{"grant_number":"863818","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"fulldoi":"https://doi.org/10.1007/s13235-025-00636-4","publication_status":"published","type":"journal_article","day":"01","intvolume":"        15"},{"intvolume":"       258","day":"01","type":"conference","publication_status":"published","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020"},{"name":"Bilateral Artificial Intelligence (Chatterjee)","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","grant_number":"COE12"}],"date_published":"2025-05-01T00:00:00Z","department":[{"_id":"KrCh"}],"scopus_import":"1","alternative_title":["PMLR"],"citation":{"ieee":"R. Luo, S. U. Stich, S. Horváth, and M. Takáč, “Revisiting LocalSGD and SCAFFOLD: Improved rates and missing analysis,” in <i>The 28th International Conference on Artificial Intelligence and Statistics</i>, Mai Khao, Thailand, 2025, vol. 258, pp. 2539–2547.","apa":"Luo, R., Stich, S. U., Horváth, S., &#38; Takáč, M. (2025). Revisiting LocalSGD and SCAFFOLD: Improved rates and missing analysis. In <i>The 28th International Conference on Artificial Intelligence and Statistics</i> (Vol. 258, pp. 2539–2547). Mai Khao, Thailand: ML Research Press.","ama":"Luo R, Stich SU, Horváth S, Takáč M. Revisiting LocalSGD and SCAFFOLD: Improved rates and missing analysis. In: <i>The 28th International Conference on Artificial Intelligence and Statistics</i>. Vol 258. ML Research Press; 2025:2539-2547.","chicago":"Luo, Ruichen, Sebastian U. Stich, Samuel Horváth, and Martin Takáč. “Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis.” In <i>The 28th International Conference on Artificial Intelligence and Statistics</i>, 258:2539–47. ML Research Press, 2025.","mla":"Luo, Ruichen, et al. “Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis.” <i>The 28th International Conference on Artificial Intelligence and Statistics</i>, vol. 258, ML Research Press, 2025, pp. 2539–47.","short":"R. Luo, S.U. Stich, S. Horváth, M. Takáč, in:, The 28th International Conference on Artificial Intelligence and Statistics, ML Research Press, 2025, pp. 2539–2547.","ista":"Luo R, Stich SU, Horváth S, Takáč M. 2025. Revisiting LocalSGD and SCAFFOLD: Improved rates and missing analysis. The 28th International Conference on Artificial Intelligence and Statistics. AISTATS: Conference on Artificial Intelligence and Statistics, PMLR, vol. 258, 2539–2547."},"publication_identifier":{"eissn":["2640-3498"]},"quality_controlled":"1","acknowledgement":"The authors thank for the helpful discussions with Eduard Gorbunov, Kumar Kshitij Patel, Anton\r\nRodomanov, and Ali Zindari during the preparation of this work. This work was partially done during the first author’s stays at CISPA and at MBZUAI. The first author also acknowledges ERC CoG 863818 (ForM-SMArt) and Austrian Science Fund (FWF) 10.55776/COE12.","abstract":[{"lang":"eng","text":"LocalSGD and SCAFFOLD are widely used methods in distributed stochastic optimization, with numerous applications in machine learning, large-scale data processing, and federated learning. However, rigorously establishing their theoretical advantages over simpler methods, such as minibatch SGD (MbSGD), has proven challenging, as existing analyses often rely on strong assumptions, unrealistic premises, or overly restrictive scenarios.\r\n\r\nIn this work, we revisit the convergence properties of LocalSGD and SCAFFOLD under a variety of existing or weaker conditions, including gradient similarity, Hessian similarity, weak convexity, and Lipschitz continuity of the Hessian. Our analysis shows that (i) LocalSGD achieves faster convergence compared to MbSGD for weakly convex functions without requiring stronger gradient similarity assumptions; (ii) LocalSGD benefits significantly from higher-order similarity and smoothness; and (iii) SCAFFOLD demonstrates faster convergence than MbSGD for a broader class of non-quadratic functions. These theoretical insights provide a clearer understanding of the conditions under which LocalSGD and SCAFFOLD outperform MbSGD."}],"publication":"The 28th International Conference on Artificial Intelligence and Statistics","OA_type":"green","conference":{"end_date":"2025-05-05","name":"AISTATS: Conference on Artificial Intelligence and Statistics","start_date":"2025-05-03","location":"Mai Khao, Thailand"},"_id":"20302","month":"05","oa":1,"date_updated":"2026-09-16T07:01:32Z","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2501.04443","open_access":"1"}],"language":[{"iso":"eng"}],"page":"2539-2547","author":[{"full_name":"Luo, Ruichen","last_name":"Luo","id":"b391db08-1ffe-11ee-8b67-d18ddcfb5a14","first_name":"Ruichen"},{"full_name":"Stich, Sebastian U.","last_name":"Stich","first_name":"Sebastian U."},{"full_name":"Horváth, Samuel","last_name":"Horváth","first_name":"Samuel"},{"last_name":"Takáč","full_name":"Takáč, Martin","first_name":"Martin"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2025","volume":258,"title":"Revisiting LocalSGD and SCAFFOLD: Improved rates and missing analysis","article_processing_charge":"No","publisher":"ML Research Press","OA_place":"repository","date_created":"2025-09-07T22:01:35Z","external_id":{"arxiv":["2501.04443"]},"arxiv":1,"ec_funded":1,"oa_version":"Preprint"},{"publication_status":"published","fulldoi":"https://doi.org/10.1103/tldp-kvkd","type":"journal_article","day":"12","intvolume":"         6","project":[{"call_identifier":"H2020","grant_number":"850899","_id":"23841C26-32DE-11EA-91FC-C7463DDC885E","name":"Non-Ergodic Quantum Matter: Universality, Dynamics and Control"},{"name":"FWF Open Access Fund","_id":"3AC91DDA-15DF-11EA-824D-93A3E7B544D1","call_identifier":"FWF"},{"grant_number":"COE01","name":"Quantum Science Austria (Serbyn)","_id":"92c64506-16d5-11f0-9cad-87ce313ee832"}],"APC_amount":"3599,50 EUR","department":[{"_id":"GradSch"},{"_id":"BjHo"},{"_id":"MaSe"}],"date_published":"2025-11-12T00:00:00Z","article_type":"original","doi":"10.1103/tldp-kvkd","publication_identifier":{"eissn":["2691-3399"]},"citation":{"chicago":"Petrova, Elena, Marko Ljubotina, Gökhan Yalniz, and Maksym Serbyn. “Finding Periodic Orbits in Projected Quantum Many-Body Dynamics.” <i>PRX Quantum</i>. American Physical Society, 2025. <a href=\"https://doi.org/10.1103/tldp-kvkd\">https://doi.org/10.1103/tldp-kvkd</a>.","mla":"Petrova, Elena, et al. “Finding Periodic Orbits in Projected Quantum Many-Body Dynamics.” <i>PRX Quantum</i>, vol. 6, no. 4, 040333, American Physical Society, 2025, doi:<a href=\"https://doi.org/10.1103/tldp-kvkd\">10.1103/tldp-kvkd</a>.","short":"E. Petrova, M. Ljubotina, G. Yalniz, M. Serbyn, PRX Quantum 6 (2025).","ista":"Petrova E, Ljubotina M, Yalniz G, Serbyn M. 2025. Finding periodic orbits in projected quantum many-body dynamics. PRX Quantum. 6(4), 040333.","ieee":"E. Petrova, M. Ljubotina, G. Yalniz, and M. Serbyn, “Finding periodic orbits in projected quantum many-body dynamics,” <i>PRX Quantum</i>, vol. 6, no. 4. American Physical Society, 2025.","apa":"Petrova, E., Ljubotina, M., Yalniz, G., &#38; Serbyn, M. (2025). Finding periodic orbits in projected quantum many-body dynamics. <i>PRX Quantum</i>. American Physical Society. <a href=\"https://doi.org/10.1103/tldp-kvkd\">https://doi.org/10.1103/tldp-kvkd</a>","ama":"Petrova E, Ljubotina M, Yalniz G, Serbyn M. Finding periodic orbits in projected quantum many-body dynamics. <i>PRX Quantum</i>. 2025;6(4). doi:<a href=\"https://doi.org/10.1103/tldp-kvkd\">10.1103/tldp-kvkd</a>"},"has_accepted_license":"1","file":[{"checksum":"5d6d04ac518b4118405334e1ddc7a56d","file_name":"tldp-kvkd.pdf","file_id":"20647","success":1,"content_type":"application/pdf","file_size":2504713,"relation":"main_file","date_updated":"2025-11-14T09:44:10Z","date_created":"2025-11-14T09:44:10Z","creator":"gyalniz","access_level":"open_access"}],"scopus_import":"1","acknowledgement":"We acknowledge useful discussions with C. Kollath, A. Green, and D. Huse. E.P., M.L., and M.S. acknowledge support by the European Research Council under the European Union’s Horizon 2020 research and innovation program (Grant Agreement No. 850899). This research was funded in whole or in part by the Austrian Science Fund (FWF) (Grant No. 10.55776/COE1). For open access purposes, the author has applied a CC BY public copyright license to any author accepted manuscript version arising from this submission. M.L. acknowledges support by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy—EXC-2111—390814868. This research was supported in part by National Science Foundation (NSF) Grant No. PHY-2309135 to the Kavli Institute for Theoretical Physics (KITP) and by the Erwin Schrödinger International Institute for Mathematics and Physics (ESI).","quality_controlled":"1","publication":"PRX Quantum","abstract":[{"lang":"eng","text":"Describing general quantum many-body dynamics is a challenging task due to the exponential growth of the Hilbert space with system size. The time-dependent variational principle (TDVP) provides a powerful tool to tackle this task by projecting quantum evolution onto a classical dynamical system within a variational manifold. In classical systems, periodic orbits play a crucial role in understanding the structure of the phase space and the long-term behavior of the system. However, finding periodic orbits is generally difficult, and their existence and properties in generic TDVP dynamics over matrix product states have remained largely unexplored. In this work, we develop an algorithm to systematically identify and characterize periodic orbits in TDVP dynamics. Applying our method to the periodically kicked Ising model, we uncover both stable and unstable periodic orbits. We characterize the Kolmogorov-Arnold-Moser tori in the vicinity of stable periodic orbits and track the change of the periodic orbits as we modify the Hamiltonian parameters. We observe that periodic orbits exist at any value of the coupling constant of the kicked Ising model between prethermal and fully thermalizing regimes, but their relevance to quantum dynamics and imprint on quantum eigenstates diminishes as the system leaves the prethermal regime. Our results demonstrate that periodic orbits provide valuable insights into the TDVP approximation of quantum many-body evolution and establish a closer connection between quantum and classical chaos."}],"OA_type":"gold","oa":1,"month":"11","_id":"20646","language":[{"iso":"eng"}],"PlanS_conform":"1","date_updated":"2026-09-16T07:04:35Z","article_number":"040333","year":"2025","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","corr_author":"1","author":[{"first_name":"Elena","full_name":"Petrova, Elena","last_name":"Petrova","id":"0ac84990-897b-11ed-a09c-f5abb56a4ede"},{"last_name":"Ljubotina","full_name":"Ljubotina, Marko","id":"F75EE9BE-5C90-11EA-905D-16643DDC885E","first_name":"Marko","orcid":"0000-0003-0038-7068"},{"orcid":"0000-0002-8490-9312","id":"66E74FA2-D8BF-11E9-8249-8DE2E5697425","full_name":"Yalniz, Gökhan","last_name":"Yalniz","first_name":"Gökhan"},{"first_name":"Maksym","full_name":"Serbyn, Maksym","last_name":"Serbyn","id":"47809E7E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2399-5827"}],"volume":6,"isi":1,"DOAJ_listed":"1","article_processing_charge":"Yes","title":"Finding periodic orbits in projected quantum many-body dynamics","date_created":"2025-11-14T09:40:52Z","OA_place":"publisher","related_material":{"link":[{"relation":"press_release","url":"https://ista.ac.at/en/news/reaching-for-the-quantum-scars/","description":"News on ISTA website"}]},"publisher":"American Physical Society","external_id":{"arxiv":["2504.12472"],"isi":["001616473700003"]},"ddc":["539"],"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa_version":"Published Version","issue":"4","ec_funded":1,"file_date_updated":"2025-11-14T09:44:10Z","arxiv":1},{"article_type":"original","date_published":"2025-10-01T00:00:00Z","department":[{"_id":"MaSe"}],"scopus_import":"1","has_accepted_license":"1","file":[{"success":1,"file_id":"20715","file_name":"2025_PhysReviewResearch_Brighi.pdf","checksum":"c4e582ab64ab9f8fface70bf2fd31882","date_created":"2025-12-01T08:00:19Z","creator":"dernst","access_level":"open_access","relation":"main_file","date_updated":"2025-12-01T08:00:19Z","content_type":"application/pdf","file_size":483879}],"publication_identifier":{"eissn":["2643-1564"]},"citation":{"ama":"Brighi P, Ljubotina M, Roccati F, Balducci F. Finite steady-state current defies non-Hermitian many-body localization. <i>Physical Review Research</i>. 2025;7(4). doi:<a href=\"https://doi.org/10.1103/crwj-x7j8\">10.1103/crwj-x7j8</a>","apa":"Brighi, P., Ljubotina, M., Roccati, F., &#38; Balducci, F. (2025). Finite steady-state current defies non-Hermitian many-body localization. <i>Physical Review Research</i>. American Physical Society. <a href=\"https://doi.org/10.1103/crwj-x7j8\">https://doi.org/10.1103/crwj-x7j8</a>","ieee":"P. Brighi, M. Ljubotina, F. Roccati, and F. Balducci, “Finite steady-state current defies non-Hermitian many-body localization,” <i>Physical Review Research</i>, vol. 7, no. 4. American Physical Society, 2025.","short":"P. Brighi, M. Ljubotina, F. Roccati, F. Balducci, Physical Review Research 7 (2025).","ista":"Brighi P, Ljubotina M, Roccati F, Balducci F. 2025. Finite steady-state current defies non-Hermitian many-body localization. Physical Review Research. 7(4), L042014.","mla":"Brighi, Pietro, et al. “Finite Steady-State Current Defies Non-Hermitian Many-Body Localization.” <i>Physical Review Research</i>, vol. 7, no. 4, L042014, American Physical Society, 2025, doi:<a href=\"https://doi.org/10.1103/crwj-x7j8\">10.1103/crwj-x7j8</a>.","chicago":"Brighi, Pietro, Marko Ljubotina, Federico Roccati, and Federico Balducci. “Finite Steady-State Current Defies Non-Hermitian Many-Body Localization.” <i>Physical Review Research</i>. American Physical Society, 2025. <a href=\"https://doi.org/10.1103/crwj-x7j8\">https://doi.org/10.1103/crwj-x7j8</a>."},"doi":"10.1103/crwj-x7j8","intvolume":"         7","day":"01","type":"journal_article","publication_status":"published","fulldoi":"https://doi.org/10.1103/crwj-x7j8","project":[{"_id":"92c64506-16d5-11f0-9cad-87ce313ee832","name":"Quantum Science Austria (Serbyn)","grant_number":"COE01"}],"OA_type":"gold","_id":"20709","month":"10","oa":1,"quality_controlled":"1","acknowledgement":"F.B. thanks Giuseppe de Tomasi and Oskar A. Prośniak for discussion. P.B. acknowledges support by the Austrian Science Fund (FWF) (Grant Agreement No. 10.55776/ESP9057324). This research was funded in whole or in part by the Austrian Science Fund (FWF) [10.55776/COE1]. The numerical simulations were performed using the ITensor library [73] on the Vienna Scientific Cluster (VSC) and on the MPIPKS HPC cluster. M.L. acknowledges support by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy—EXC-2111—390814868. F.R. acknowledges support by the European Union-Next Generation EU with the project “Quantum Optics in Many-Body photonic Environments” (QOMBE) code SOE2024_0000084-CUP B77G24000480006. Open\r\naccess publication funded by Max Planck Society.","abstract":[{"text":"Non-Hermitian many-body localization (NH MBL) has emerged as a possible scenario for stable localization in open systems, as suggested by spectral indicators identifying a putative transition for finite system sizes. In this work, we shift the focus to dynamical probes, specifically the steady-state spin current, to investigate transport properties in a disordered, non-Hermitian XXZ spin chain. Through exact diagonalization for small systems and tensor-network methods for larger chains, we demonstrate that the steady-state current remains finite and decays exponentially with disorder strength, showing no evidence of a transition up to disorder values far beyond the previously claimed critical point. Our results reveal a stark discrepancy between spectral indicators, which suggest localization, and transport behavior, which indicates delocalization. This highlights the importance of dynamical observables in characterizing NH MBL and suggests that traditional spectral measures may not fully capture the physics of non-Hermitian systems. Additionally, we observe a noncommutativity of limits in system size and time, further complicating the interpretation of finite-size studies. These findings challenge the existence of NH MBL in the studied model and underscore the need for alternative approaches to understanding localization in non-Hermitian settings.","lang":"eng"}],"publication":"Physical Review Research","author":[{"id":"4115AF5C-F248-11E8-B48F-1D18A9856A87","full_name":"Brighi, Pietro","last_name":"Brighi","first_name":"Pietro","orcid":"0000-0002-7969-2729"},{"first_name":"Marko","full_name":"Ljubotina, Marko","last_name":"Ljubotina","id":"F75EE9BE-5C90-11EA-905D-16643DDC885E","orcid":"0000-0003-0038-7068"},{"last_name":"Roccati","full_name":"Roccati, Federico","first_name":"Federico"},{"first_name":"Federico","full_name":"Balducci, Federico","last_name":"Balducci"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2025","DOAJ_listed":"1","volume":7,"date_updated":"2026-09-16T07:06:16Z","PlanS_conform":"1","language":[{"iso":"eng"}],"article_number":"L042014","external_id":{"arxiv":["2504.02460"]},"file_date_updated":"2025-12-01T08:00:19Z","arxiv":1,"issue":"4","oa_version":"Published Version","tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"ddc":["530"],"title":"Finite steady-state current defies non-Hermitian many-body localization","article_processing_charge":"Yes (via OA deal)","publisher":"American Physical Society","OA_place":"publisher","date_created":"2025-11-30T23:02:08Z"},{"conference":{"name":"ATVA: Automated Technology for Verification and Analysis","end_date":"2025-10-31","location":"Bengaluru, India","start_date":"2025-10-27"},"OA_type":"green","_id":"20648","oa":1,"month":"10","quality_controlled":"1","acknowledgement":"This work was supported by the following grants: ERC CoG 863818 (ForM-SMArt), Austrian Science Fund (FWF) 10.55776/COE12, ERC StG 101222524 (SPES), the Ethereum Foundation Research Grant FY24-1793, and the Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 1 grant (Project ID:22-SISSMU-100).","abstract":[{"text":"Polynomial quantified entailments with existentially and universally quantified variables arise in many problems of verification and program analysis. We present PolyQEnt which is a tool for solving polynomial quantified entailments in which variables on both sides of the implication are real valued or unbounded integers. Our tool provides a unified framework for polynomial quantified entailment problems that arise in several papers in the literature. Our experimental evaluation over a wide range of benchmarks shows the applicability of the tool as well as its benefits as opposed to simply using existing SMT solvers to solve such constraints.","lang":"eng"}],"publication":"23rd International Symposium on Automated Technology for Verification and Analysis","date_published":"2025-10-26T00:00:00Z","department":[{"_id":"KrCh"}],"scopus_import":"1","doi":"10.1007/978-3-032-08707-2_19","alternative_title":["LNCS"],"publication_identifier":{"issn":["0302-9743"],"isbn":["9783032087065"],"eissn":["1611-3349"]},"citation":{"ama":"Chatterjee K, Goharshady AK, Goharshady E, et al. PolyQEnt: A polynomial quantified entailment solver. In: <i>23rd International Symposium on Automated Technology for Verification and Analysis</i>. Vol 16145. Springer Nature; 2025:411-424. doi:<a href=\"https://doi.org/10.1007/978-3-032-08707-2_19\">10.1007/978-3-032-08707-2_19</a>","apa":"Chatterjee, K., Goharshady, A. K., Goharshady, E., Karrabi, M., Saadat, M., Seeliger, M., &#38; Zikelic, D. (2025). PolyQEnt: A polynomial quantified entailment solver. In <i>23rd International Symposium on Automated Technology for Verification and Analysis</i> (Vol. 16145, pp. 411–424). Bengaluru, India: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-08707-2_19\">https://doi.org/10.1007/978-3-032-08707-2_19</a>","ieee":"K. Chatterjee <i>et al.</i>, “PolyQEnt: A polynomial quantified entailment solver,” in <i>23rd International Symposium on Automated Technology for Verification and Analysis</i>, Bengaluru, India, 2025, vol. 16145, pp. 411–424.","ista":"Chatterjee K, Goharshady AK, Goharshady E, Karrabi M, Saadat M, Seeliger M, Zikelic D. 2025. PolyQEnt: A polynomial quantified entailment solver. 23rd International Symposium on Automated Technology for Verification and Analysis. ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 16145, 411–424.","short":"K. Chatterjee, A.K. Goharshady, E. Goharshady, M. Karrabi, M. Saadat, M. Seeliger, D. Zikelic, in:, 23rd International Symposium on Automated Technology for Verification and Analysis, Springer Nature, 2025, pp. 411–424.","mla":"Chatterjee, Krishnendu, et al. “PolyQEnt: A Polynomial Quantified Entailment Solver.” <i>23rd International Symposium on Automated Technology for Verification and Analysis</i>, vol. 16145, Springer Nature, 2025, pp. 411–24, doi:<a href=\"https://doi.org/10.1007/978-3-032-08707-2_19\">10.1007/978-3-032-08707-2_19</a>.","chicago":"Chatterjee, Krishnendu, Amir Kafshdar Goharshady, Ehsan Goharshady, Mehrdad Karrabi, Milad Saadat, Maximilian Seeliger, and Dorde Zikelic. “PolyQEnt: A Polynomial Quantified Entailment Solver.” In <i>23rd International Symposium on Automated Technology for Verification and Analysis</i>, 16145:411–24. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-032-08707-2_19\">https://doi.org/10.1007/978-3-032-08707-2_19</a>."},"day":"26","intvolume":"     16145","fulldoi":"https://doi.org/10.1007/978-3-032-08707-2_19","publication_status":"published","type":"conference","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020"},{"name":"Bilateral Artificial Intelligence (Chatterjee)","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","grant_number":"COE12"}],"external_id":{"arxiv":["2408.03796"]},"ec_funded":1,"arxiv":1,"oa_version":"Preprint","title":"PolyQEnt: A polynomial quantified entailment solver","article_processing_charge":"No","publisher":"Springer Nature","date_created":"2025-11-16T23:01:24Z","OA_place":"repository","status":"public","author":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"orcid":"0000-0003-1702-6584","first_name":"Amir Kafshdar","id":"391365CE-F248-11E8-B48F-1D18A9856A87","last_name":"Goharshady","full_name":"Goharshady, Amir Kafshdar"},{"first_name":"Ehsan","last_name":"Kafshdar Goharshadi","full_name":"Kafshdar Goharshadi, Ehsan","id":"103b4fa0-896a-11ed-bdf8-87b697bef40d","orcid":"0000-0002-8595-0587"},{"orcid":"0009-0007-5253-9170","first_name":"Mehrdad","id":"67638922-f394-11eb-9cf6-f20423e08757","full_name":"Karrabi, Mehrdad","last_name":"Karrabi"},{"first_name":"Milad","full_name":"Saadat, Milad","last_name":"Saadat"},{"first_name":"Maximilian","full_name":"Seeliger, Maximilian","last_name":"Seeliger"},{"first_name":"Dorde","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","last_name":"Zikelic","full_name":"Zikelic, Dorde","orcid":"0000-0002-4681-1699"}],"corr_author":"1","year":"2025","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":16145,"date_updated":"2026-09-16T07:03:56Z","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2408.03796","open_access":"1"}],"page":"411-424"},{"conference":{"name":"LICS: Logic in Computer Science","end_date":"2025-06-26","location":"Singapore, Singapore","start_date":"2025-06-23"},"OA_type":"green","oa":1,"month":"10","_id":"20690","acknowledgement":"This project has received funding from the Fonds de la Recherche Scientifique - FNRS under grant No. T.0027.21, the Belgian National Lottery; the ERC CoG 863818 (ForM-SMArt), the Austrian Science Fund (FWF) 10.55776/COE12; the DFG project 427755713, GOPro, and the DFG research training group GRK 2428 Continuous Verification of Cyber-Physical Systems\r\n(ConVeY); the EU’s Horizon 2020 research and innovation programmes under the Marie Sklodowska-Curie grant agreement No. 101034413 (IST-BRIDGE) and the ERC Starting Grant DEUCE (101077178).","quality_controlled":"1","publication":"2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science","abstract":[{"text":"Cumulative prospect theory (CPT) is the first theory for decision-making under uncertainty that combines full theoretical soundness and empirically realistic features [1], [Page 2]. While CPT was originally considered in one-shot settings for risk-aware decision-making, we consider CPT in sequential decision-making. The most fundamental and well-studied models for sequential decision-making are Markov chains (MCs), and their generalization Markov decision processes (MDPs). The complexity theoretic study of MCs and MDPs with CPT is a fundamental problem that has not been addressed in the literature.Our contributions are as follows: First, we present an alternative viewpoint for the CPT-value of MCs and MDPs. This allows us to establish a connection with multi-objective reachability analysis and conclude the strategy complexity result that memoryless randomized strategies are necessary and sufficient for optimality. Second, based on this connection, we provide an algorithm for computing the CPT-value in MDPs with infinite-horizon objectives. We show that the problem is in EXPTIME and fixed-parameter tractable. Moreover, we provide a polynomial-time algorithm for the special case of MCs.","lang":"eng"}],"department":[{"_id":"KrCh"}],"date_published":"2025-10-09T00:00:00Z","publication_identifier":{"eisbn":["9798331579005"]},"citation":{"ama":"Brihaye T, Chatterjee K, Mohr S, Weininger M. Risk-aware Markov decision processes using cumulative prospect theory. In: <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE; 2025:458-471. doi:<a href=\"https://doi.org/10.1109/lics65433.2025.00041\">10.1109/lics65433.2025.00041</a>","ieee":"T. Brihaye, K. Chatterjee, S. Mohr, and M. Weininger, “Risk-aware Markov decision processes using cumulative prospect theory,” in <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Singapore, Singapore, 2025, pp. 458–471.","apa":"Brihaye, T., Chatterjee, K., Mohr, S., &#38; Weininger, M. (2025). Risk-aware Markov decision processes using cumulative prospect theory. In <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i> (pp. 458–471). Singapore, Singapore: IEEE. <a href=\"https://doi.org/10.1109/lics65433.2025.00041\">https://doi.org/10.1109/lics65433.2025.00041</a>","short":"T. Brihaye, K. Chatterjee, S. Mohr, M. Weininger, in:, 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2025, pp. 458–471.","ista":"Brihaye T, Chatterjee K, Mohr S, Weininger M. 2025. Risk-aware Markov decision processes using cumulative prospect theory. 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 458–471.","mla":"Brihaye, Thomas, et al. “Risk-Aware Markov Decision Processes Using Cumulative Prospect Theory.” <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, IEEE, 2025, pp. 458–71, doi:<a href=\"https://doi.org/10.1109/lics65433.2025.00041\">10.1109/lics65433.2025.00041</a>.","chicago":"Brihaye, Thomas, Krishnendu Chatterjee, Stefanie Mohr, and Maximilian Weininger. “Risk-Aware Markov Decision Processes Using Cumulative Prospect Theory.” In <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 458–71. IEEE, 2025. <a href=\"https://doi.org/10.1109/lics65433.2025.00041\">https://doi.org/10.1109/lics65433.2025.00041</a>."},"doi":"10.1109/lics65433.2025.00041","scopus_import":"1","publication_status":"published","fulldoi":"https://doi.org/10.1109/lics65433.2025.00041","type":"conference","day":"09","project":[{"call_identifier":"H2020","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications"},{"grant_number":"101034413","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"},{"_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","name":"Bilateral Artificial Intelligence (Chatterjee)","grant_number":"COE12"}],"external_id":{"arxiv":["2505.09514"]},"oa_version":"Preprint","ec_funded":1,"arxiv":1,"article_processing_charge":"No","title":"Risk-aware Markov decision processes using cumulative prospect theory","date_created":"2025-11-24T14:43:47Z","OA_place":"repository","publisher":"IEEE","year":"2025","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","author":[{"first_name":"Thomas","full_name":"Brihaye, Thomas","last_name":"Brihaye"},{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"full_name":"Mohr, Stefanie","last_name":"Mohr","first_name":"Stefanie"},{"first_name":"Maximilian","last_name":"Weininger","full_name":"Weininger, Maximilian","id":"02ab0197-cc70-11ed-ab61-918e71f56881","orcid":"0000-0002-0163-2152"}],"corr_author":"1","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2505.09514","open_access":"1"}],"date_updated":"2026-09-16T07:05:13Z","page":"458-471"},{"project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020"},{"grant_number":"COE12","name":"Bilateral Artificial Intelligence (Chatterjee)","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee"}],"type":"conference","fulldoi":"https://doi.org/10.1109/lics65433.2025.00044","publication_status":"published","day":"09","citation":{"ama":"Baier C, Chatterjee K, Meggendorfer T, Piribauer J. Multiplicative rewards in Markovian models. In: <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE; 2025:499-512. doi:<a href=\"https://doi.org/10.1109/lics65433.2025.00044\">10.1109/lics65433.2025.00044</a>","ieee":"C. Baier, K. Chatterjee, T. Meggendorfer, and J. Piribauer, “Multiplicative rewards in Markovian models,” in <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Singapore, Singapore, 2025, pp. 499–512.","apa":"Baier, C., Chatterjee, K., Meggendorfer, T., &#38; Piribauer, J. (2025). Multiplicative rewards in Markovian models. In <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i> (pp. 499–512). Singapore, Singapore: IEEE. <a href=\"https://doi.org/10.1109/lics65433.2025.00044\">https://doi.org/10.1109/lics65433.2025.00044</a>","short":"C. Baier, K. Chatterjee, T. Meggendorfer, J. Piribauer, in:, 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2025, pp. 499–512.","ista":"Baier C, Chatterjee K, Meggendorfer T, Piribauer J. 2025. Multiplicative rewards in Markovian models. 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 499–512.","chicago":"Baier, Christel, Krishnendu Chatterjee, Tobias Meggendorfer, and Jakob Piribauer. “Multiplicative Rewards in Markovian Models.” In <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 499–512. IEEE, 2025. <a href=\"https://doi.org/10.1109/lics65433.2025.00044\">https://doi.org/10.1109/lics65433.2025.00044</a>.","mla":"Baier, Christel, et al. “Multiplicative Rewards in Markovian Models.” <i>2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, IEEE, 2025, pp. 499–512, doi:<a href=\"https://doi.org/10.1109/lics65433.2025.00044\">10.1109/lics65433.2025.00044</a>."},"publication_identifier":{"eisbn":["9798331579005"]},"doi":"10.1109/lics65433.2025.00044","scopus_import":"1","department":[{"_id":"KrCh"}],"date_published":"2025-10-09T00:00:00Z","publication":"2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science","abstract":[{"text":"This paper studies the expected value of multiplicative rewards, where rewards obtained in each step are multiplied (instead of the usual addition), in Markov chains (MCs) and Markov decision processes (MDPs). One of the key differences to additive rewards is that the expected value may diverge to ∞ not only due to recurrent, but also due to transient states.For MCs, computing the value is shown to be possible in polynomial time given an oracle for the comparison of succinctly represented integers (CSRI), which is only known to be solvable in polynomial time subject to number-theoretic conjectures. Interestingly, distinguishing whether the value is ∞ or 0 is at least as hard as CSRI, while determining if it is one of these two can be done in polynomial time. In MDPs, the optimal value can be computed in polynomial space. Further refined complexity results and results on the complexity of optimal schedulers are presented. The techniques developed for MDPs additionally allow to solve the multiplicative variant of the stochastic shortest path problem. Finally, for MCs and MDPs where an absorbing state is reached almost surely, all considered problems are solvable in polynomial time.","lang":"eng"}],"acknowledgement":"This work was partly funded by the ERC CoG 863818 (ForM-SMArt), the Austrian Science Fund (FWF) 10.55776/COE12, the DFG Grant 389792660 as part of TRR 248 (Foundations of Perspicuous Software Systems), the Cluster of Excellence EXC 2050/1 (CeTI, project ID\r\n390696704, as part of Germany’s Excellence Strategy), and by the BMBF (Federal Ministry of Education and Research) in DAAD project 57616814 (SECAI, School of Embedded and\r\nComposite AI) as part of the program Konrad Zuse Schools of Excellence in Artificial Intelligence.","quality_controlled":"1","month":"10","oa":1,"_id":"20689","conference":{"name":"LICS: Logic in Computer Science","end_date":"2025-06-26","location":"Singapore, Singapore","start_date":"2025-06-23"},"OA_type":"green","page":"499-512","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2504.18277"}],"language":[{"iso":"eng"}],"date_updated":"2026-09-16T07:05:41Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2025","author":[{"first_name":"Christel","full_name":"Baier, Christel","last_name":"Baier"},{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","full_name":"Meggendorfer, Tobias","last_name":"Meggendorfer","first_name":"Tobias","orcid":"0000-0002-1712-2165"},{"full_name":"Piribauer, Jakob","last_name":"Piribauer","first_name":"Jakob"}],"corr_author":"1","status":"public","OA_place":"repository","date_created":"2025-11-24T14:24:00Z","publisher":"IEEE","article_processing_charge":"No","title":"Multiplicative rewards in Markovian models","oa_version":"Preprint","arxiv":1,"ec_funded":1,"external_id":{"arxiv":["2504.18277"]}}]