[{"citation":{"ista":"Hashimoto K, Katsumata S, Pascual Perez G. 2025. Exploring how to authenticate application messages in MLS: More efficient, post-quantum, and anonymous blocklistable. 34th Usenix Security Symposium. USENIX: Security Symposium, 6699–6716.","short":"K. Hashimoto, S. Katsumata, G. Pascual Perez, in:, 34th Usenix Security Symposium, Usenix Association, 2025, pp. 6699–6716.","ieee":"K. Hashimoto, S. Katsumata, and G. Pascual Perez, “Exploring how to authenticate application messages in MLS: More efficient, post-quantum, and anonymous blocklistable,” in <i>34th Usenix Security Symposium</i>, Seattle, WA, USA, 2025, pp. 6699–6716.","mla":"Hashimoto, Keitaro, et al. “Exploring How to Authenticate Application Messages in MLS: More Efficient, Post-Quantum, and Anonymous Blocklistable.” <i>34th Usenix Security Symposium</i>, Usenix Association, 2025, pp. 6699–716.","ama":"Hashimoto K, Katsumata S, Pascual Perez G. Exploring how to authenticate application messages in MLS: More efficient, post-quantum, and anonymous blocklistable. In: <i>34th Usenix Security Symposium</i>. Usenix Association; 2025:6699-6716.","apa":"Hashimoto, K., Katsumata, S., &#38; Pascual Perez, G. (2025). Exploring how to authenticate application messages in MLS: More efficient, post-quantum, and anonymous blocklistable. In <i>34th Usenix Security Symposium</i> (pp. 6699–6716). Seattle, WA, USA: Usenix Association.","chicago":"Hashimoto, Keitaro, Shuichi Katsumata, and Guillermo Pascual Perez. “Exploring How to Authenticate Application Messages in MLS: More Efficient, Post-Quantum, and Anonymous Blocklistable.” In <i>34th Usenix Security Symposium</i>, 6699–6716. Usenix Association, 2025."},"page":"6699-6716","project":[{"name":"International IST Doctoral Program","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385"}],"date_updated":"2026-09-07T11:37:56Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Exploring how to authenticate application messages in MLS: More efficient, post-quantum, and anonymous blocklistable","_id":"20668","author":[{"last_name":"Hashimoto","first_name":"Keitaro","full_name":"Hashimoto, Keitaro"},{"last_name":"Katsumata","first_name":"Shuichi","full_name":"Katsumata, Shuichi"},{"last_name":"Pascual Perez","first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8630-415X","full_name":"Pascual Perez, Guillermo"}],"status":"public","date_created":"2025-11-23T23:01:40Z","type":"conference","oa_version":"Published Version","abstract":[{"lang":"eng","text":"The Message Layer Security (MLS) protocol has recently been standardized by the IETF. MLS is a scalable secure group messaging protocol expected to run more efficiently compared to the Signal protocol at scale, while offering a similar level of strong security. Even though MLS has undergone extensive examination by researchers, the majority of the works have focused on confidentiality.\r\n\r\nIn this work, we focus on the authenticity of the application messages exchanged in MLS. Currently, MLS authenticates every application message with an EdDSA signature and while manageable, the overhead is greatly amplified in the post-quantum setting as the NIST-recommended Dilithium signature results in a 40x increase in size. We view this as an invitation to explore new authentication modes that can be used instead. We start by taking a systematic view on how application messages are authenticated in MLS and categorize authenticity into four different security notions. We then propose several authentication modes, offering a range of different efficiency and security profiles. For instance, in one of our modes, COSMOS++, we replace signatures with one-time tokens and a MAC tag, offering roughly a 75x savings in the post-quantum communication overhead. While this comes at the cost of weakening security compared to the authentication mode used by MLS, the lower communication overhead seems to make it a worthwhile trade-off with security."}],"OA_type":"diamond","OA_place":"publisher","language":[{"iso":"eng"}],"publication":"34th Usenix Security Symposium","scopus_import":"1","publication_identifier":{"isbn":["9781939133526"]},"acknowledgement":"This research was partially supported by JST CREST JPMJCR22M1, Japan and funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No.665385.","ec_funded":1,"has_accepted_license":"1","conference":{"start_date":"2025-08-13","end_date":"2025-08-15","name":"USENIX: Security Symposium","location":"Seattle, WA, USA"},"file_date_updated":"2025-11-24T07:44:08Z","date_published":"2025-01-01T00:00:00Z","article_processing_charge":"No","das_tickbox":"1","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2025/426"}],"ddc":["000"],"publication_status":"published","year":"2025","quality_controlled":"1","cryptoeprintid":1,"file":[{"date_updated":"2025-11-24T07:44:08Z","content_type":"application/pdf","file_name":"2025_Usenix_Hashimoto.pdf","file_size":710733,"file_id":"20671","access_level":"open_access","creator":"dernst","relation":"main_file","success":1,"date_created":"2025-11-24T07:44:08Z","checksum":"fcfe8851aeb751af98c0b1335a0ef149"}],"day":"01","oa":1,"corr_author":"1","external_id":{"cryptoeprintid":["2025/426"]},"publisher":"Usenix Association","month":"01"},{"day":"01","corr_author":"1","oa":1,"external_id":{"unknown":["2405.13625"]},"month":"12","department":[{"_id":"VlKo"}],"publisher":"ACM","volume":59,"doi":"10.1145/3832046.3832063","year":"2025","publication_status":"published","intvolume":"        59","date_published":"2025-12-01T00:00:00Z","article_processing_charge":"No","fulldoi":"https://doi.org/10.1145/3832046.3832063","main_file_link":[{"url":"https://doi.org/10.1145/3832046.3832063","open_access":"1"}],"publication":"ACM Communications in Computer Algebra","issue":"4","scopus_import":"1","acknowledgement":"This extended abstract is based on the paper [7], accepted for publication at SIAM\r\nJ. Opt. on April 22, 2025, to which we refer for technical details and complete proofs. This work has been\r\nsupported by the Doctoral Programme Vienna Graduate School on Computational Optimization (VGSCO)\r\nwhich was funded by FWF (Austrian Science Fund), project W 1260-N35, and partially supported by the\r\nANR JCJC project ANR-21-CE48-0006-01 “HYPERSPACE”.\r\n","publication_identifier":{"eissn":["1932-2240"],"issn":["1932-2232"]},"OA_place":"publisher","OA_type":"free access","language":[{"iso":"eng"}],"_id":"22774","title":"Certifying solutions of degenerate semidefinite programs","date_created":"2026-08-30T22:01:44Z","author":[{"full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Naldi","first_name":"Simone","full_name":"Naldi, Simone"},{"id":"00223538-AF8F-11E9-A4C7-F729E6697425","first_name":"Jeferson","last_name":"Zapata","full_name":"Zapata, Jeferson"}],"status":"public","article_type":"original","oa_version":"Published Version","type":"journal_article","abstract":[{"text":"We consider the problem of certifying the feasibility of a (possibly degenerate) semidefinite programming problem represented by rational input data together with a numerical solution that is guaranteed to be sufficiently close to an exact solution of maximal rank. Our method constructs a polynomial system whose set of real solutions has an isolated point that satisfies the input program. An experimental comparison between the corresponding symbolic-numerical algorithm and the purely symbolic algorithm from [3, 5] shows that the hybrid algorithm is able to certify instances where the exact method fails.","lang":"eng"}],"project":[{"_id":"9B9290DE-BA93-11EA-9121-9846C619BF3A","name":"Vienna Graduate School on Computational Optimization","grant_number":"W1260-N35"}],"page":"147-152","citation":{"short":"V. Kolmogorov, S. Naldi, J. Zapata, ACM Communications in Computer Algebra 59 (2025) 147–152.","ista":"Kolmogorov V, Naldi S, Zapata J. 2025. Certifying solutions of degenerate semidefinite programs. ACM Communications in Computer Algebra. 59(4), 147–152.","ieee":"V. Kolmogorov, S. Naldi, and J. Zapata, “Certifying solutions of degenerate semidefinite programs,” <i>ACM Communications in Computer Algebra</i>, vol. 59, no. 4. ACM, pp. 147–152, 2025.","ama":"Kolmogorov V, Naldi S, Zapata J. Certifying solutions of degenerate semidefinite programs. <i>ACM Communications in Computer Algebra</i>. 2025;59(4):147-152. doi:<a href=\"https://doi.org/10.1145/3832046.3832063\">10.1145/3832046.3832063</a>","mla":"Kolmogorov, Vladimir, et al. “Certifying Solutions of Degenerate Semidefinite Programs.” <i>ACM Communications in Computer Algebra</i>, vol. 59, no. 4, ACM, 2025, pp. 147–52, doi:<a href=\"https://doi.org/10.1145/3832046.3832063\">10.1145/3832046.3832063</a>.","apa":"Kolmogorov, V., Naldi, S., &#38; Zapata, J. (2025). Certifying solutions of degenerate semidefinite programs. <i>ACM Communications in Computer Algebra</i>. ACM. <a href=\"https://doi.org/10.1145/3832046.3832063\">https://doi.org/10.1145/3832046.3832063</a>","chicago":"Kolmogorov, Vladimir, Simone Naldi, and Jeferson Zapata. “Certifying Solutions of Degenerate Semidefinite Programs.” <i>ACM Communications in Computer Algebra</i>. ACM, 2025. <a href=\"https://doi.org/10.1145/3832046.3832063\">https://doi.org/10.1145/3832046.3832063</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-09-09T08:17:05Z"},{"quality_controlled":"1","year":"2025","publication_status":"published","intvolume":"        38","ddc":["000"],"fulldoi":"https://doi.org/10.52202/085713-1551","das_tickbox":"0","main_file_link":[{"open_access":"1","url":"https://doi.org/10.52202/085713-1551"}],"date_published":"2025-12-02T00:00:00Z","alternative_title":["Advances in Neural Information Processing Systems"],"conference":{"location":"San Diego, CA, United States","end_date":"2025-12-07","start_date":"2025-12-02","name":"NeurIPS: Neural Information Processing Systems"},"has_accepted_license":"1","article_processing_charge":"No","department":[{"_id":"DaAl"}],"month":"12","publisher":"Neural Information Processing Systems Foundation","day":"02","oa":1,"volume":38,"doi":"10.52202/085713-1551","researchdata_availability":"no","oa_version":"Published Version","type":"conference","abstract":[{"lang":"eng","text":"Large Language Models (LLMs) have demonstrated the ability to tackle increasingly complex tasks through advanced reasoning, long-form content generation,\r\nand tool use. Solving these tasks often involves long inference-time computations.\r\nIn human problem solving, a common strategy to expedite work is collaboration: by\r\ndividing the problem into sub-tasks, exploring different strategies concurrently, etc.\r\nRecent research has shown that LLMs can also operate in parallel by implementing\r\nexplicit cooperation frameworks, such as voting mechanisms or the explicit creation of independent sub-tasks that can be executed in parallel. However, each of\r\nthese frameworks may not be suitable for all types of tasks, which can hinder their\r\napplicability. In this work, we propose a different design approach: we run LLM\r\n“workers” in parallel , allowing them to synchronize via a concurrently-updated\r\nattention cache and prompt these workers to decide how best to collaborate. Our\r\napproach allows the LLM instances to come up with their own collaboration strategy for the problem at hand, all the while “seeing” each other’s memory in the\r\nconcurrent KV cache. We implement this approach via Hogwild! Inference: a\r\nparallel LLM inference engine where multiple instances of the same LLM run in\r\nparallel with the same attention cache, with “instant” access to each other’s memory.1 Hogwild! Inference takes advantage of Rotary Position Embeddings (RoPE)\r\nto avoid recomputation while improving parallel hardware utilization. We find that\r\nmodern reasoning-capable LLMs can perform inference with shared Key-Value\r\ncache out of the box, without additional fine-tuning."}],"_id":"22826","title":"Hogwild! Inference: Parallel LLM generation via concurrent attention","date_created":"2026-09-06T22:01:59Z","status":"public","author":[{"full_name":"Rodionov, Gleb","first_name":"Gleb","last_name":"Rodionov"},{"full_name":"Garipov, Roman","first_name":"Roman","last_name":"Garipov"},{"last_name":"Shutova","first_name":"Alina","full_name":"Shutova, Alina"},{"first_name":"George","last_name":"Yakushev","full_name":"Yakushev, George"},{"id":"2786b299-e6b0-11f0-91da-9243fe3ef96b","first_name":"Erik","last_name":"Schultheis","full_name":"Schultheis, Erik"},{"full_name":"Egiazarian, Vage","id":"77451e76-92b2-11ef-a4d1-8dbaa06e16ad","last_name":"Egiazarian","first_name":"Vage"},{"full_name":"Sinitsin, Anton","first_name":"Anton","last_name":"Sinitsin"},{"last_name":"Kuznedelev","first_name":"Denis","full_name":"Kuznedelev, Denis"},{"full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","supplementarymaterial":"yes","date_updated":"2026-09-10T07:06:31Z","page":"52014-52055","citation":{"mla":"Rodionov, Gleb, et al. “Hogwild! Inference: Parallel LLM Generation via Concurrent Attention.” <i>39th Conference on Neural Information Processing Systems</i>, vol. 38, Neural Information Processing Systems Foundation, 2025, pp. 52014–55, doi:<a href=\"https://doi.org/10.52202/085713-1551\">10.52202/085713-1551</a>.","ama":"Rodionov G, Garipov R, Shutova A, et al. Hogwild! Inference: Parallel LLM generation via concurrent attention. In: <i>39th Conference on Neural Information Processing Systems</i>. Vol 38. Neural Information Processing Systems Foundation; 2025:52014-52055. doi:<a href=\"https://doi.org/10.52202/085713-1551\">10.52202/085713-1551</a>","short":"G. Rodionov, R. Garipov, A. Shutova, G. Yakushev, E. Schultheis, V. Egiazarian, A. Sinitsin, D. Kuznedelev, D.-A. Alistarh, in:, 39th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2025, pp. 52014–52055.","ista":"Rodionov G, Garipov R, Shutova A, Yakushev G, Schultheis E, Egiazarian V, Sinitsin A, Kuznedelev D, Alistarh D-A. 2025. Hogwild! Inference: Parallel LLM generation via concurrent attention. 39th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 38, 52014–52055.","ieee":"G. Rodionov <i>et al.</i>, “Hogwild! Inference: Parallel LLM generation via concurrent attention,” in <i>39th Conference on Neural Information Processing Systems</i>, San Diego, CA, United States, 2025, vol. 38, pp. 52014–52055.","chicago":"Rodionov, Gleb, Roman Garipov, Alina Shutova, George Yakushev, Erik Schultheis, Vage Egiazarian, Anton Sinitsin, Denis Kuznedelev, and Dan-Adrian Alistarh. “Hogwild! Inference: Parallel LLM Generation via Concurrent Attention.” In <i>39th Conference on Neural Information Processing Systems</i>, 38:52014–55. Neural Information Processing Systems Foundation, 2025. <a href=\"https://doi.org/10.52202/085713-1551\">https://doi.org/10.52202/085713-1551</a>.","apa":"Rodionov, G., Garipov, R., Shutova, A., Yakushev, G., Schultheis, E., Egiazarian, V., … Alistarh, D.-A. (2025). Hogwild! Inference: Parallel LLM generation via concurrent attention. In <i>39th Conference on Neural Information Processing Systems</i> (Vol. 38, pp. 52014–52055). San Diego, CA, United States: Neural Information Processing Systems Foundation. <a href=\"https://doi.org/10.52202/085713-1551\">https://doi.org/10.52202/085713-1551</a>"},"acknowledgement":"We thank Vladimir Malinovskii for his help with brainstorming, helpful\r\nfeedback and suggesting future work directions. We also thank Philip Zmushko for proofreading.","publication_identifier":{"issn":["1049-5258"],"isbn":["9798331338275"]},"publication":"39th Conference on Neural Information Processing Systems","scopus_import":"1","language":[{"iso":"eng"}],"OA_type":"gold","OA_place":"publisher"},{"scopus_import":"1","publication":"39th Conference on Neural Information Processing Systems","publication_identifier":{"issn":["1049-5258"],"isbn":["9798331338275"]},"acknowledgement":"M. M. and P. S. are funded by the European Union (ERC, INF2\r\n, project number 101161364). Views\r\nand opinions expressed are however those of the author(s) only and do not necessarily reflect those\r\nof the European Union or the European Research Council Executive Agency. Neither the European\r\nUnion nor the granting authority can be held responsible for them. This research was supported\r\nby the Scientific Service Units (SSU) of ISTA through resources provided by Scientific Computing (SciComp).","OA_place":"publisher","OA_type":"free access","language":[{"iso":"eng"}],"date_created":"2026-09-06T22:01:59Z","status":"public","author":[{"full_name":"Súkeník, Peter","id":"d64d6a8d-eb8e-11eb-b029-96fd216dec3c","first_name":"Peter","last_name":"Súkeník"},{"orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","last_name":"Lampert","first_name":"Christoph"},{"full_name":"Mondelli, Marco","orcid":"0000-0002-3242-7020","first_name":"Marco","last_name":"Mondelli","id":"27EB676C-8706-11E9-9510-7717E6697425"}],"_id":"22825","title":"Neural collapse is globally optimal in deep regularized ResNets and transformers","abstract":[{"lang":"eng","text":"The empirical emergence of neural collapse—a surprising symmetry in the feature representations of the training data in the penultimate layer of deep neural\r\nnetworks—has spurred a line of theoretical research aimed at its understanding.\r\nHowever, existing work focuses on data-agnostic models or, when data structure is\r\ntaken into account, it remains limited to multi-layer perceptrons. Our paper fills\r\nboth these gaps by analyzing modern architectures in a data-aware regime: we\r\nprove that global optima of deep regularized transformers and residual networks\r\n(ResNets) with LayerNorm trained with cross entropy or mean squared error loss\r\nare approximately collapsed, and the approximation gets tighter as the depth grows.\r\nMore generally, we formally reduce any end-to-end large-depth ResNet or transformer training into an equivalent unconstrained features model, thus justifying its\r\nwide use in the literature even beyond data-agnostic settings. Our theoretical results\r\nare supported by experiments on computer vision and language datasets showing\r\nthat, as the depth grows, neural collapse indeed becomes more prominent."}],"oa_version":"Published Version","type":"conference","project":[{"name":"Inference in High Dimensions: Light-speed Algorithms and Information Limits","_id":"911e6d1f-16d5-11f0-9cad-c5c68c6a1cdf","grant_number":"101161364"}],"page":"48646-48677","citation":{"apa":"Súkeník, P., Lampert, C., &#38; Mondelli, M. (2025). Neural collapse is globally optimal in deep regularized ResNets and transformers. In <i>39th Conference on Neural Information Processing Systems</i> (Vol. 38, pp. 48646–48677). San Diego, CA, United States: Neural Information Processing Systems Foundation. <a href=\"https://doi.org/10.52202/085713-1450\">https://doi.org/10.52202/085713-1450</a>","chicago":"Súkeník, Peter, Christoph Lampert, and Marco Mondelli. “Neural Collapse Is Globally Optimal in Deep Regularized ResNets and Transformers.” In <i>39th Conference on Neural Information Processing Systems</i>, 38:48646–77. Neural Information Processing Systems Foundation, 2025. <a href=\"https://doi.org/10.52202/085713-1450\">https://doi.org/10.52202/085713-1450</a>.","short":"P. Súkeník, C. Lampert, M. Mondelli, in:, 39th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2025, pp. 48646–48677.","ieee":"P. Súkeník, C. Lampert, and M. Mondelli, “Neural collapse is globally optimal in deep regularized ResNets and transformers,” in <i>39th Conference on Neural Information Processing Systems</i>, San Diego, CA, United States, 2025, vol. 38, pp. 48646–48677.","ista":"Súkeník P, Lampert C, Mondelli M. 2025. Neural collapse is globally optimal in deep regularized ResNets and transformers. 39th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 38, 48646–48677.","ama":"Súkeník P, Lampert C, Mondelli M. Neural collapse is globally optimal in deep regularized ResNets and transformers. In: <i>39th Conference on Neural Information Processing Systems</i>. Vol 38. Neural Information Processing Systems Foundation; 2025:48646-48677. doi:<a href=\"https://doi.org/10.52202/085713-1450\">10.52202/085713-1450</a>","mla":"Súkeník, Peter, et al. “Neural Collapse Is Globally Optimal in Deep Regularized ResNets and Transformers.” <i>39th Conference on Neural Information Processing Systems</i>, vol. 38, Neural Information Processing Systems Foundation, 2025, pp. 48646–77, doi:<a href=\"https://doi.org/10.52202/085713-1450\">10.52202/085713-1450</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","supplementarymaterial":"no","date_updated":"2026-09-10T08:11:46Z","corr_author":"1","oa":1,"day":"02","month":"12","department":[{"_id":"MaMo"},{"_id":"GradSch"},{"_id":"ChLa"}],"publisher":"Neural Information Processing Systems Foundation","external_id":{"arxiv":["2505.15239"]},"doi":"10.52202/085713-1450","researchdata_availability":"no","volume":38,"ddc":["000"],"intvolume":"        38","quality_controlled":"1","year":"2025","publication_status":"published","article_processing_charge":"No","date_published":"2025-12-02T00:00:00Z","alternative_title":["Advances in Neural Information Processing Systems"],"conference":{"location":"San Diego, CA, United States","end_date":"2025-12-07","start_date":"2025-12-02","name":"NeurIPS: Neural Information Processing Systems"},"arxiv":1,"acknowledged_ssus":[{"_id":"ScienComp"}],"main_file_link":[{"url":"https://doi.org/10.52202/085713-1450","open_access":"1"}],"fulldoi":"https://doi.org/10.52202/085713-1450","das_tickbox":"0"},{"day":"02","corr_author":"1","oa":1,"publisher":"Neural Information Processing Systems Foundation","department":[{"_id":"GradSch"},{"_id":"ChLa"}],"month":"12","volume":38,"researchdata_availability":"no","doi":"10.52202/085713-0278","publication_status":"published","year":"2025","quality_controlled":"1","intvolume":"        38","conference":{"start_date":"2025-12-02","end_date":"2025-12-07","name":"NeurIPS: Neural Information Processing Systems","location":"San Diego, CA, United States"},"alternative_title":["Advances in Neural Information Processing Systems"],"date_published":"2025-12-02T00:00:00Z","article_processing_charge":"No","das_tickbox":"0","fulldoi":"https://doi.org/10.52202/085713-0278","main_file_link":[{"open_access":"1","url":"https://doi.org/10.52202/085713-0278"}],"acknowledged_ssus":[{"_id":"ScienComp"}],"publication":"39th Conference on Neural Information Processing Systems","scopus_import":"1","acknowledgement":"This research was supported by the Scientific Service Units (SSU) of ISTA through resources provided by Scientific Computing (SciComp).","publication_identifier":{"issn":["1049-5258"],"isbn":["9798331338275"]},"OA_place":"publisher","OA_type":"free access","language":[{"iso":"eng"}],"title":"Fast rate bounds for multi-task and meta-learning with different sample sizes","_id":"22824","author":[{"id":"653bd8b6-f394-11eb-9cf6-c0bbf6cd78d4","last_name":"Zakerinia","first_name":"Hossein","full_name":"Zakerinia, Hossein","orcid":"0009-0007-3977-6462"},{"full_name":"Lampert, Christoph","orcid":"0000-0001-8622-7887","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","last_name":"Lampert","first_name":"Christoph"}],"date_created":"2026-09-06T22:01:59Z","status":"public","oa_version":"Published Version","type":"conference","abstract":[{"lang":"eng","text":"We present new fast-rate PAC-Bayesian generalization bounds for multi-task and\r\nmeta-learning in the unbalanced setting, i.e. when the tasks have training sets of\r\ndifferent sizes, as is typically the case in real-world scenarios. Previously, only\r\nstandard-rate bounds were known for this situation, while fast-rate bounds were\r\nlimited to the setting where all training sets are of equal size. Our new bounds\r\nare numerically computable as well as interpretable, and we demonstrate their\r\nflexibility in handling a number of cases where they give stronger guarantees\r\nthan previous bounds. Besides the bounds themselves, we also make conceptual\r\ncontributions: we demonstrate that the unbalanced multi-task setting has different\r\nstatistical properties than the balanced situation, specifically that proofs from\r\nthe balanced situation do not carry over to the unbalanced setting. Additionally,\r\nwe shed light on the fact that the unbalanced situation allows two meaningful\r\ndefinitions of multi-task risk, depending on whether all tasks should be considered\r\nequally important or if sample-rich tasks should receive more weight than samplepoor ones."}],"citation":{"chicago":"Zakerinia, Hossein, and Christoph Lampert. “Fast Rate Bounds for Multi-Task and Meta-Learning with Different Sample Sizes.” In <i>39th Conference on Neural Information Processing Systems</i>, 38:9062–93. Neural Information Processing Systems Foundation, 2025. <a href=\"https://doi.org/10.52202/085713-0278\">https://doi.org/10.52202/085713-0278</a>.","apa":"Zakerinia, H., &#38; Lampert, C. (2025). Fast rate bounds for multi-task and meta-learning with different sample sizes. In <i>39th Conference on Neural Information Processing Systems</i> (Vol. 38, pp. 9062–9093). San Diego, CA, United States: Neural Information Processing Systems Foundation. <a href=\"https://doi.org/10.52202/085713-0278\">https://doi.org/10.52202/085713-0278</a>","ama":"Zakerinia H, Lampert C. Fast rate bounds for multi-task and meta-learning with different sample sizes. In: <i>39th Conference on Neural Information Processing Systems</i>. Vol 38. Neural Information Processing Systems Foundation; 2025:9062-9093. doi:<a href=\"https://doi.org/10.52202/085713-0278\">10.52202/085713-0278</a>","mla":"Zakerinia, Hossein, and Christoph Lampert. “Fast Rate Bounds for Multi-Task and Meta-Learning with Different Sample Sizes.” <i>39th Conference on Neural Information Processing Systems</i>, vol. 38, Neural Information Processing Systems Foundation, 2025, pp. 9062–93, doi:<a href=\"https://doi.org/10.52202/085713-0278\">10.52202/085713-0278</a>.","ista":"Zakerinia H, Lampert C. 2025. Fast rate bounds for multi-task and meta-learning with different sample sizes. 39th Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 38, 9062–9093.","ieee":"H. Zakerinia and C. Lampert, “Fast rate bounds for multi-task and meta-learning with different sample sizes,” in <i>39th Conference on Neural Information Processing Systems</i>, San Diego, CA, United States, 2025, vol. 38, pp. 9062–9093.","short":"H. Zakerinia, C. Lampert, in:, 39th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2025, pp. 9062–9093."},"page":"9062-9093","date_updated":"2026-09-10T08:37:33Z","supplementarymaterial":"yes","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"researchdata_availability":"no","doi":"10.52202/085713-3163","volume":38,"oa":1,"day":"02","publisher":"Neural Information Processing Systems Foundation","department":[{"_id":"DaAl"}],"month":"12","external_id":{"arxiv":["2504.20039"]},"article_processing_charge":"No","conference":{"name":"NeurIPS: Neural Information Processing Systems","end_date":"2025-12-07","start_date":"2025-12-02","location":"San Diego, CA, United States"},"date_published":"2025-12-02T00:00:00Z","alternative_title":["Advances in Neural Information Processing Systems"],"main_file_link":[{"url":"https://doi.org/10.52202/085713-3163","open_access":"1"}],"arxiv":1,"das_tickbox":"0","fulldoi":"https://doi.org/10.52202/085713-3163","intvolume":"        38","publication_status":"published","quality_controlled":"1","year":"2025","OA_place":"publisher","OA_type":"free access","language":[{"iso":"eng"}],"scopus_import":"1","publication":"39th Annual Conference on Neural Information Processing Systems","publication_identifier":{"issn":["1049-5258"],"isbn":["9798331338275"]},"acknowledgement":"We would like to express our sincere gratitude to Denis Mazur for his valuable contributions to the\r\nimplementation of API calls used in Algorithm 1 and for supporting inference with the Llama 405B\r\nmodel. We are also thankful for his positive influence on the overall atmosphere and team morale\r\nthroughout the course of this project.","citation":{"ama":"Garipov R, Velikonivtsev F, Ermakov I, Svirschevski R, Egiazarian V, Ryabinin M. AutoJudge: Judge decoding without manual annotation. In: <i>39th Annual Conference on Neural Information Processing Systems</i>. Vol 38. Neural Information Processing Systems Foundation; 2025:104904-104941. doi:<a href=\"https://doi.org/10.52202/085713-3163\">10.52202/085713-3163</a>","mla":"Garipov, Roman, et al. “AutoJudge: Judge Decoding without Manual Annotation.” <i>39th Annual Conference on Neural Information Processing Systems</i>, vol. 38, Neural Information Processing Systems Foundation, 2025, pp. 104904–41, doi:<a href=\"https://doi.org/10.52202/085713-3163\">10.52202/085713-3163</a>.","ista":"Garipov R, Velikonivtsev F, Ermakov I, Svirschevski R, Egiazarian V, Ryabinin M. 2025. AutoJudge: Judge decoding without manual annotation. 39th Annual Conference on Neural Information Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 38, 104904–104941.","ieee":"R. Garipov, F. Velikonivtsev, I. Ermakov, R. Svirschevski, V. Egiazarian, and M. Ryabinin, “AutoJudge: Judge decoding without manual annotation,” in <i>39th Annual Conference on Neural Information Processing Systems</i>, San Diego, CA, United States, 2025, vol. 38, pp. 104904–104941.","short":"R. Garipov, F. Velikonivtsev, I. Ermakov, R. Svirschevski, V. Egiazarian, M. Ryabinin, in:, 39th Annual Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2025, pp. 104904–104941.","chicago":"Garipov, Roman, Fedor Velikonivtsev, Ivan Ermakov, Ruslan Svirschevski, Vage Egiazarian, and Max Ryabinin. “AutoJudge: Judge Decoding without Manual Annotation.” In <i>39th Annual Conference on Neural Information Processing Systems</i>, 38:104904–41. Neural Information Processing Systems Foundation, 2025. <a href=\"https://doi.org/10.52202/085713-3163\">https://doi.org/10.52202/085713-3163</a>.","apa":"Garipov, R., Velikonivtsev, F., Ermakov, I., Svirschevski, R., Egiazarian, V., &#38; Ryabinin, M. (2025). AutoJudge: Judge decoding without manual annotation. In <i>39th Annual Conference on Neural Information Processing Systems</i> (Vol. 38, pp. 104904–104941). San Diego, CA, United States: Neural Information Processing Systems Foundation. <a href=\"https://doi.org/10.52202/085713-3163\">https://doi.org/10.52202/085713-3163</a>"},"page":"104904-104941","supplementarymaterial":"yes","date_updated":"2026-09-10T11:08:33Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","author":[{"full_name":"Garipov, Roman","last_name":"Garipov","first_name":"Roman"},{"first_name":"Fedor","last_name":"Velikonivtsev","full_name":"Velikonivtsev, Fedor"},{"full_name":"Ermakov, Ivan","last_name":"Ermakov","first_name":"Ivan"},{"full_name":"Svirschevski, Ruslan","last_name":"Svirschevski","first_name":"Ruslan"},{"full_name":"Egiazarian, Vage","id":"77451e76-92b2-11ef-a4d1-8dbaa06e16ad","first_name":"Vage","last_name":"Egiazarian"},{"last_name":"Ryabinin","first_name":"Max","full_name":"Ryabinin, Max"}],"date_created":"2026-09-06T22:02:00Z","title":"AutoJudge: Judge decoding without manual annotation","_id":"22830","abstract":[{"lang":"eng","text":"We introduce AutoJudge, a method that accelerates large language model (LLM) inference with task-specific lossy speculative decoding. Instead of matching the original model output distribution token-by-token, we identify the generated tokens that affect the downstream quality of the response, relaxing the distribution match guarantee so that the \"unimportant\" tokens can be generated faster. Our approach relies on a semi‑greedy search algorithm to test which of the mismatches between target and draft models should be corrected to preserve quality and which ones may be skipped. We then train a lightweight classifier based on existing LLM embeddings to predict, at inference time, which mismatching tokens can be safely accepted without compromising the final answer quality. We evaluate AutoJudge with multiple draft/target model pairs on mathematical reasoning and programming benchmarks, achieving significant speedups at the cost of a minor accuracy reduction. Notably, on GSM8K with the Llama 3.1 70B target model, our approach achieves up to \r\n≈\r\n2\r\n×\r\n speedup \\textit{over speculative decoding} at the cost of a \r\n≤\r\n1\r\n%\r\n drop in accuracy. When applied to the LiveCodeBench benchmark, AutoJudge automatically detects programming-specific important tokens, accepting \r\n≥\r\n25\r\n tokens per speculation cycle at a\r\n \r\n2\r\n%\r\n drop in Pass@1. Our approach requires no human annotation and is easy to integrate with modern LLM inference frameworks."}],"type":"conference","oa_version":"Published Version"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-09-14T07:44:59Z","project":[{"_id":"1b39bd8c-ab3c-11f0-a172-a4c5bf64093b","name":"Acoustics-based drone navigation and interaction","grant_number":"863839"}],"citation":{"chicago":"Davidson, Yair, Aviad Philipp, Sabyasachi Chakraborty, Alex M. Bronstein, and Renana Gershoni-Poranne. “How Local Is ‘Local’? Deep Learning Reveals Locality of the Induced Magnetic Field of Polycyclic Aromatic Hydrocarbons.” <i>Journal of Chemical Physics</i>. AIP Publishing, 2025. <a href=\"https://doi.org/10.1063/5.0257558\">https://doi.org/10.1063/5.0257558</a>.","apa":"Davidson, Y., Philipp, A., Chakraborty, S., Bronstein, A. M., &#38; Gershoni-Poranne, R. (2025). How local is “local”? Deep learning reveals locality of the induced magnetic field of polycyclic aromatic hydrocarbons. <i>Journal of Chemical Physics</i>. AIP Publishing. <a href=\"https://doi.org/10.1063/5.0257558\">https://doi.org/10.1063/5.0257558</a>","ama":"Davidson Y, Philipp A, Chakraborty S, Bronstein AM, Gershoni-Poranne R. How local is “local”? Deep learning reveals locality of the induced magnetic field of polycyclic aromatic hydrocarbons. <i>Journal of Chemical Physics</i>. 2025;162(14). doi:<a href=\"https://doi.org/10.1063/5.0257558\">10.1063/5.0257558</a>","mla":"Davidson, Yair, et al. “How Local Is ‘Local’? Deep Learning Reveals Locality of the Induced Magnetic Field of Polycyclic Aromatic Hydrocarbons.” <i>Journal of Chemical Physics</i>, vol. 162, no. 14, 144101, AIP Publishing, 2025, doi:<a href=\"https://doi.org/10.1063/5.0257558\">10.1063/5.0257558</a>.","ieee":"Y. Davidson, A. Philipp, S. Chakraborty, A. M. Bronstein, and R. Gershoni-Poranne, “How local is ‘local’? Deep learning reveals locality of the induced magnetic field of polycyclic aromatic hydrocarbons,” <i>Journal of Chemical Physics</i>, vol. 162, no. 14. AIP Publishing, 2025.","short":"Y. Davidson, A. Philipp, S. Chakraborty, A.M. Bronstein, R. Gershoni-Poranne, Journal of Chemical Physics 162 (2025).","ista":"Davidson Y, Philipp A, Chakraborty S, Bronstein AM, Gershoni-Poranne R. 2025. How local is “local”? Deep learning reveals locality of the induced magnetic field of polycyclic aromatic hydrocarbons. Journal of Chemical Physics. 162(14), 144101."},"related_material":{"link":[{"url":"https://gitlab.com/porannegroup/magnetic_locality","relation":"software"}]},"abstract":[{"lang":"eng","text":"We investigate the locality of magnetic response in polycyclic aromatic molecules using a novel deep-learning approach. Our method employs graph neural networks (GNNs) with a graph-of-rings representation to predict nucleus independent chemical shifts (NICS) in the space around the molecule. We train a series of models, each time reducing the size of the largest molecules used in training. The accuracy of prediction remains high (MAE < 0.5 ppm), even when training the model only on molecules with up to four rings, thus providing strong evidence for the locality of magnetic response. To overcome the known problem of generalization of GNNs, we implement a k-hop expansion strategy and succeed in achieving accurate predictions for molecules with up to 15 rings (almost 4 times the size of the largest training example). Our findings have implications for understanding the magnetic response in complex molecules and demonstrate a promising approach to overcoming GNN scalability limitations. Furthermore, the trained models enable rapid characterization, without the need for more expensive DFT calculations."}],"article_type":"original","type":"journal_article","oa_version":"Published Version","author":[{"first_name":"Yair","last_name":"Davidson","full_name":"Davidson, Yair"},{"full_name":"Philipp, Aviad","first_name":"Aviad","last_name":"Philipp"},{"last_name":"Chakraborty","first_name":"Sabyasachi","full_name":"Chakraborty, Sabyasachi"},{"last_name":"Bronstein","first_name":"Alexander","id":"58f3726e-7cba-11ef-ad8b-e6e8cb3904e6","full_name":"Bronstein, Alexander","orcid":"0000-0001-9699-8730"},{"first_name":"Renana","last_name":"Gershoni-Poranne","full_name":"Gershoni-Poranne, Renana"}],"status":"public","date_created":"2025-04-20T22:01:28Z","_id":"19595","title":"How local is “local”? Deep learning reveals locality of the induced magnetic field of polycyclic aromatic hydrocarbons","language":[{"iso":"eng"}],"OA_type":"hybrid","OA_place":"publisher","acknowledgement":"The authors express their gratitude to Professor Dr. Peter Chen for his continued support. The authors acknowledge the Branco Weiss Fellowship for supporting this research as part of a Society in Science grant and the Israel Science Foundation for financial support (Grant No. 1745/23 to R.G.-P.). R.G.-P. is a Branco Weiss Fellow, a Horev Fellow, and an Alon Scholarship recipient. A.M.B. was supported by the ERC StG EARS and the Israeli Science Foundation.","publication_identifier":{"issn":["0021-9606"],"eissn":["1089-7690"]},"issue":"14","scopus_import":"1","publication":"Journal of Chemical Physics","fulldoi":"https://doi.org/10.1063/5.0257558","article_processing_charge":"Yes (in subscription journal)","date_published":"2025-04-14T00:00:00Z","file_date_updated":"2025-04-22T09:27:43Z","has_accepted_license":"1","intvolume":"       162","year":"2025","pmid":1,"quality_controlled":"1","publication_status":"published","ddc":["000"],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","short":"CC BY-NC (4.0)","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","image":"/images/cc_by_nc.png"},"file":[{"file_size":7812182,"file_name":"2025_JourChemicalPhysics_Davidson.pdf","date_updated":"2025-04-22T09:27:43Z","content_type":"application/pdf","file_id":"19606","creator":"dernst","relation":"main_file","access_level":"open_access","date_created":"2025-04-22T09:27:43Z","checksum":"20a31a4c506b52de863bab7d3ff989ef","success":1}],"doi":"10.1063/5.0257558","volume":162,"article_number":"144101","isi":1,"department":[{"_id":"AlBr"}],"month":"04","publisher":"AIP Publishing","external_id":{"pmid":["40197568"],"isi":["001466311300030"]},"corr_author":"1","oa":1,"day":"14"},{"related_material":{"link":[{"url":"https://ista.ac.at/en/news/taming-the-bad-oxygen/","description":"News on ISTA website","relation":"press_release"}]},"project":[{"grant_number":"P37169","_id":"8df062be-16d5-11f0-9cad-f559b6612c7e","name":"Singlet oxygen in non-aqueous oxygen redox chemistry"},{"grant_number":"CZI01","_id":"c08e9ad1-5a5b-11eb-8a69-9d1cf3b07473","name":"Tools for automation and feedback microscopy"},{"name":"Materials for Energy Conversion and Storage (Freunberger)","_id":"5eaf4378-b033-11f1-b276-f928018a46c1","grant_number":"COE05"}],"page":"601–605","citation":{"ista":"Mondal S, Nguyen HTK, Hauschild R, Freunberger SA. 2025. Marcus kinetics control singlet and triplet oxygen evolving from superoxide. Nature. 646(8085), 601–605.","ieee":"S. Mondal, H. T. K. Nguyen, R. Hauschild, and S. A. Freunberger, “Marcus kinetics control singlet and triplet oxygen evolving from superoxide,” <i>Nature</i>, vol. 646, no. 8085. Springer Nature, pp. 601–605, 2025.","short":"S. Mondal, H.T.K. Nguyen, R. Hauschild, S.A. Freunberger, Nature 646 (2025) 601–605.","ama":"Mondal S, Nguyen HTK, Hauschild R, Freunberger SA. Marcus kinetics control singlet and triplet oxygen evolving from superoxide. <i>Nature</i>. 2025;646(8085):601–605. doi:<a href=\"https://doi.org/10.1038/s41586-025-09587-7\">10.1038/s41586-025-09587-7</a>","mla":"Mondal, Soumyadip, et al. “Marcus Kinetics Control Singlet and Triplet Oxygen Evolving from Superoxide.” <i>Nature</i>, vol. 646, no. 8085, Springer Nature, 2025, pp. 601–605, doi:<a href=\"https://doi.org/10.1038/s41586-025-09587-7\">10.1038/s41586-025-09587-7</a>.","apa":"Mondal, S., Nguyen, H. T. K., Hauschild, R., &#38; Freunberger, S. A. (2025). Marcus kinetics control singlet and triplet oxygen evolving from superoxide. <i>Nature</i>. Springer Nature. <a href=\"https://doi.org/10.1038/s41586-025-09587-7\">https://doi.org/10.1038/s41586-025-09587-7</a>","chicago":"Mondal, Soumyadip, Huyen T.K. Nguyen, Robert Hauschild, and Stefan Alexander Freunberger. “Marcus Kinetics Control Singlet and Triplet Oxygen Evolving from Superoxide.” <i>Nature</i>. Springer Nature, 2025. <a href=\"https://doi.org/10.1038/s41586-025-09587-7\">https://doi.org/10.1038/s41586-025-09587-7</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-09-16T06:53:54Z","PlanS_conform":"1","_id":"17468","title":"Marcus kinetics control singlet and triplet oxygen evolving from superoxide","author":[{"full_name":"Mondal, Soumyadip","last_name":"Mondal","first_name":"Soumyadip","id":"d25d21ef-dc8d-11ea-abe3-ec4576307f48"},{"full_name":"Nguyen, Huyen T.K.","last_name":"Nguyen","first_name":"Huyen T.K."},{"orcid":"0000-0001-9843-3522","full_name":"Hauschild, Robert","id":"4E01D6B4-F248-11E8-B48F-1D18A9856A87","first_name":"Robert","last_name":"Hauschild"},{"full_name":"Freunberger, Stefan Alexander","orcid":"0000-0003-2902-5319","id":"A8CA28E6-CE23-11E9-AD2D-EC27E6697425","last_name":"Freunberger","first_name":"Stefan Alexander"}],"status":"public","date_created":"2024-08-29T10:40:23Z","article_type":"original","oa_version":"Published Version","type":"journal_article","abstract":[{"lang":"eng","text":"Oxygen redox chemistry is central to life1 and many human-made technologies, such as in energy storage2,3,4. The large energy gain from oxygen redox reactions is often connected with the occurrence of harmful reactive oxygen species3,5,6. Key species are superoxide and the highly reactive singlet oxygen3,4,5,6,7, which may evolve from superoxide. However, the factors determining the formation of singlet oxygen, rather than the relatively unreactive triplet oxygen, are unknown. Here we report that the release of triplet or singlet oxygen is governed by individual Marcus normal and inverted region behaviour. We found that as the driving force for the reaction increases, the initially dominant evolution of triplet oxygen slows down, and singlet oxygen evolution becomes predominant with higher maximum kinetics. This behaviour also applies to the widely observed superoxide disproportionation, in which one superoxide is oxidized by another, in both non-aqueous and aqueous systems, with Lewis and Brønsted acidity controlling the driving forces. Singlet oxygen yields governed by these conditions are relevant, for example, in batteries or cellular organelles in which superoxide forms. Our findings suggest ways to understand and control spin states and kinetics in oxygen redox chemistry, with implications for fields, including life sciences, pure chemistry and energy storage."}],"OA_type":"hybrid","OA_place":"publisher","language":[{"iso":"eng"}],"publication":"Nature","issue":"8085","scopus_import":"1","acknowledgement":"S.A.F. thanks the Institute of Science and Technology Austria (ISTA) for the support. The Scientific Service Units of ISTA supported this research through resources provided by the Imaging and Optics Facility, the Lab Support Facility, the Miba Machine Shop and Scientific Computing. This research was partly funded by the Austrian Science Fund (FWF) (10.55776/P37169 and 10.55776/COE5). For open access purposes, the author has applied for a CC BY public copyright licence to any author-accepted manuscript version arising from this submission. R.H. acknowledges funding through CZI grant DAF2020-225401 (10.37921/120055ratwvi) from the Chan Zuckerberg Initiative DAF, an advised fund of Silicon Valley Community Foundation (10.13039/100014989). H.T.K.N. acknowledges funding by the European Commission Erasmus Mundus Joint Masters programme. We thank M. Sixt and M. Chinon for the discussions about O-redox in life and R. Jethwa for proofreading. Open access funding was provided by ISTA.","publication_identifier":{"issn":["0028-0836"],"eissn":["1476-4687"]},"file_date_updated":"2025-10-20T10:26:13Z","date_published":"2025-10-16T00:00:00Z","has_accepted_license":"1","article_processing_charge":"Yes (via OA deal)","fulldoi":"https://doi.org/10.1038/s41586-025-09587-7","acknowledged_ssus":[{"_id":"Bio"},{"_id":"LifeSc"},{"_id":"M-Shop"},{"_id":"ScienComp"}],"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":["540"],"quality_controlled":"1","year":"2025","pmid":1,"publication_status":"published","intvolume":"       646","isi":1,"volume":646,"file":[{"creator":"dernst","relation":"main_file","access_level":"open_access","checksum":"b507ddd23df0388aa65d04dc9b00fe3d","date_created":"2025-10-20T10:26:13Z","success":1,"file_size":3809247,"date_updated":"2025-10-20T10:26:13Z","content_type":"application/pdf","file_name":"2025_Nature_Mondal.pdf","file_id":"20500"}],"doi":"10.1038/s41586-025-09587-7","day":"16","corr_author":"1","oa":1,"external_id":{"isi":["001586378900001"],"pmid":["41044415"]},"month":"10","department":[{"_id":"StFr"},{"_id":"Bio"}],"publisher":"Springer Nature"},{"intvolume":"     15697","year":"2025","quality_controlled":"1","publication_status":"published","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)"},"arxiv":1,"fulldoi":"https://doi.org/10.1007/978-3-031-90653-4_7","article_processing_charge":"No","date_published":"2025-05-01T00:00:00Z","alternative_title":["LNCS"],"file_date_updated":"2025-06-02T10:49:52Z","has_accepted_license":"1","conference":{"name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","start_date":"2025-05-03","end_date":"2025-05-08","location":"Hamilton, ON, Canada"},"department":[{"_id":"KrCh"}],"month":"05","publisher":"Springer Nature","external_id":{"arxiv":["2501.11467"]},"corr_author":"1","oa":1,"day":"01","file":[{"access_level":"open_access","creator":"dernst","relation":"main_file","success":1,"date_created":"2025-06-02T10:49:52Z","checksum":"64b7f46ef05649b87b827248045c7645","file_name":"2025_TACAS_ChatterjeeKrish.pdf","date_updated":"2025-06-02T10:49:52Z","content_type":"application/pdf","file_size":732136,"file_id":"19772"}],"doi":"10.1007/978-3-031-90653-4_7","volume":15697,"abstract":[{"text":"The possibility of errors in human-engineered formal verification software, such as model checkers, poses a serious threat to the purpose of these tools. An established approach to mitigate this problem are certificates—lightweight, easy-to-check proofs of the verification results. In this paper, we develop novel certificates for model checking of Markov decision processes (MDPs) with quantitative reachability and expected reward properties. Our approach is conceptually simple and relies almost exclusively on elementary fixed point theory. Our certificates work for arbitrary finite MDPs and can be readily computed with little overhead using standard algorithms. We formalize the soundness of our certificates in Isabelle/HOL and provide a formally verified certificate checker. Moreover, we augment existing algorithms in the probabilistic model checker Storm with the ability to produce certificates and demonstrate practical applicability by conducting the first formal certification of the reference results in the Quantitative Verification Benchmark Set.","lang":"eng"}],"oa_version":"Published Version","type":"conference","date_created":"2025-05-25T22:17:09Z","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Quatmann, Tim","first_name":"Tim","last_name":"Quatmann"},{"full_name":"Schäffeler, Maximilian","last_name":"Schäffeler","first_name":"Maximilian"},{"first_name":"Maximilian","last_name":"Weininger","id":"02ab0197-cc70-11ed-ab61-918e71f56881","orcid":"0000-0002-0163-2152","full_name":"Weininger, Maximilian"},{"full_name":"Winkler, Tobias","first_name":"Tobias","last_name":"Winkler"},{"id":"d8ebc24a-3f98-11f0-9044-8296d4f39ab3","last_name":"Zilken","first_name":"Daniel","full_name":"Zilken, Daniel"}],"status":"public","_id":"19743","title":"Fixed point certificates for reachability and expected rewards in MDPs","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-09-16T06:57:17Z","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","grant_number":"863818"},{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","call_identifier":"H2020","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413"},{"_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","name":"Bilateral Artificial Intelligence (Chatterjee)","grant_number":"COE12"}],"citation":{"apa":"Chatterjee, K., Quatmann, T., Schäffeler, M., Weininger, M., Winkler, T., &#38; Zilken, D. (2025). Fixed point certificates for reachability and expected rewards in MDPs. In <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i> (Vol. 15697, pp. 130–151). Hamilton, ON, Canada: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-90653-4_7\">https://doi.org/10.1007/978-3-031-90653-4_7</a>","chicago":"Chatterjee, Krishnendu, Tim Quatmann, Maximilian Schäffeler, Maximilian Weininger, Tobias Winkler, and Daniel Zilken. “Fixed Point Certificates for Reachability and Expected Rewards in MDPs.” In <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, 15697:130–51. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-031-90653-4_7\">https://doi.org/10.1007/978-3-031-90653-4_7</a>.","ista":"Chatterjee K, Quatmann T, Schäffeler M, Weininger M, Winkler T, Zilken D. 2025. Fixed point certificates for reachability and expected rewards in MDPs. 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, 130–151.","short":"K. Chatterjee, T. Quatmann, M. Schäffeler, M. Weininger, T. Winkler, D. Zilken, in:, 31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Springer Nature, 2025, pp. 130–151.","ieee":"K. Chatterjee, T. Quatmann, M. Schäffeler, M. Weininger, T. Winkler, and D. Zilken, “Fixed point certificates for reachability and expected rewards in MDPs,” in <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, Hamilton, ON, Canada, 2025, vol. 15697, pp. 130–151.","ama":"Chatterjee K, Quatmann T, Schäffeler M, Weininger M, Winkler T, Zilken D. Fixed point certificates for reachability and expected rewards in MDPs. In: <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>. Vol 15697. Springer Nature; 2025:130-151. doi:<a href=\"https://doi.org/10.1007/978-3-031-90653-4_7\">10.1007/978-3-031-90653-4_7</a>","mla":"Chatterjee, Krishnendu, et al. “Fixed Point Certificates for Reachability and Expected Rewards in MDPs.” <i>31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems</i>, vol. 15697, Springer Nature, 2025, pp. 130–51, doi:<a href=\"https://doi.org/10.1007/978-3-031-90653-4_7\">10.1007/978-3-031-90653-4_7</a>."},"page":"130-151","related_material":{"record":[{"relation":"research_data","id":"19771","status":"public"}]},"ec_funded":1,"publication_identifier":{"isbn":["9783031906527"],"issn":["0302-9743"],"eissn":["1611-3349"]},"acknowledgement":"This project has received funding from the ERC CoG 863818 (ForM-SMArt), the Austrian Science Fund (FWF) 10.55776/COE12, a KI-Starter grant from the Ministerium für Kultur und Wissenschaft NRW, the DFG RTG 378803395 (ConVeY), the EU’s Horizon 2020 research and innovation programmes under the Marie Sklodowska-Curie grant agreement Nos. 101034413 (IST-BRIDGE) and 101008233 (MISSION), and the DFG RTG 2236 (UnRAVeL). Experiments were performed with computing resources granted by RWTH Aachen University under project rwth1632.","scopus_import":"1","publication":"31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems","language":[{"iso":"eng"}],"OA_place":"publisher","OA_type":"hybrid"},{"date_updated":"2026-09-16T06:56:56Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"217-236","citation":{"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>","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>.","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.","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.","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.","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>.","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>"},"project":[{"grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"},{"name":"Bilateral Artificial Intelligence (Chatterjee)","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","grant_number":"COE12"}],"abstract":[{"text":"Two standard models for probabilistic systems are Markov chains (MCs) and Markov decision processes (MDPs). Classic objectives for such probabilistic models for control and planning problems are reachability and stochastic shortest path. The widely studied algorithmic approach for these problems is the Value Iteration (VI) algorithm which iteratively applies local updates called Bellman updates. There are many practical approaches for VI in the literature but they all require exponentially many Bellman updates for MCs in the worst case. A preprocessing step is an algorithm that is discrete, graph-theoretical, and requires linear space. An important open question is whether, after a polynomial-time preprocessing, VI can be achieved with sub-exponentially many Bellman updates. In this work, we present a new approach for VI based on guessing values. Our theoretical contributions are twofold. First, for MCs, we present an almost-linear-time preprocessing algorithm after which, along with guessing values, VI requires only subexponentially many Bellman updates. Second, we present an improved analysis of the speed of convergence of VI for MDPs. Finally, we present a practical algorithm for MDPs based on our new approach. Experimental results show that our approach provides a considerable improvement over existing VI-based approaches on several benchmark examples from the literature.","lang":"eng"}],"type":"conference","oa_version":"Published Version","date_created":"2025-05-25T22:17:06Z","status":"public","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"Jafariraviz, Mahdi","first_name":"Mahdi","last_name":"Jafariraviz"},{"first_name":"Raimundo J","last_name":"Saona Urmeneta","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","orcid":"0000-0001-5103-038X","full_name":"Saona Urmeneta, Raimundo J"},{"orcid":"0000-0002-1419-3267","full_name":"Svoboda, Jakub","last_name":"Svoboda","first_name":"Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425"}],"title":"Value iteration with guessing for Markov chains and Markov decision processes","_id":"19740","language":[{"iso":"eng"}],"OA_type":"hybrid","OA_place":"publisher","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant and Austrian Science Fund (FWF) 10.55776/COE12 grant.","ec_funded":1,"publication_identifier":{"issn":["0302-9743"],"isbn":["9783031906527"],"eissn":["1611-3349"]},"scopus_import":"1","publication":"31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems","arxiv":1,"fulldoi":"https://doi.org/10.1007/978-3-031-90653-4_11","article_processing_charge":"No","conference":{"location":"Hamilton, ON, Canada","start_date":"2025-05-03","end_date":"2025-05-08","name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems"},"has_accepted_license":"1","alternative_title":["LNCS"],"date_published":"2025-05-01T00:00:00Z","file_date_updated":"2025-06-02T07:31:12Z","intvolume":"     15697","publication_status":"published","quality_controlled":"1","year":"2025","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)"},"doi":"10.1007/978-3-031-90653-4_11","file":[{"date_created":"2025-06-02T07:31:12Z","checksum":"45da6efbcbed20aada16c48c8e55e2d6","success":1,"relation":"main_file","creator":"dernst","access_level":"open_access","file_id":"19767","file_size":557481,"file_name":"2025_TACAS_Chatterjee.pdf","content_type":"application/pdf","date_updated":"2025-06-02T07:31:12Z"}],"volume":15697,"publisher":"Springer Nature","department":[{"_id":"KrCh"}],"month":"05","external_id":{"arxiv":["2505.06769"]},"oa":1,"corr_author":"1","day":"01"},{"publication":"31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems","scopus_import":"1","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783031906527"]},"ec_funded":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.","OA_type":"hybrid","OA_place":"publisher","language":[{"iso":"eng"}],"title":"Refuting equivalence in probabilistic programs with conditioning","_id":"19744","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"103b4fa0-896a-11ed-bdf8-87b697bef40d","first_name":"Ehsan","last_name":"Kafshdar Goharshadi","orcid":"0000-0002-8595-0587","full_name":"Kafshdar Goharshadi, Ehsan"},{"last_name":"Novotný","first_name":"Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","full_name":"Novotný, Petr"},{"orcid":"0000-0002-4681-1699","full_name":"Zikelic, Dorde","first_name":"Dorde","last_name":"Zikelic","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87"}],"status":"public","date_created":"2025-05-25T22:17:10Z","oa_version":"Published Version","type":"conference","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."}],"page":"279-300","citation":{"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.","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.","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.","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>.","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>","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>."},"project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"},{"grant_number":"COE12","name":"Bilateral Artificial Intelligence (Chatterjee)","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee"}],"date_updated":"2026-09-16T06:57:43Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"01","oa":1,"corr_author":"1","external_id":{"arxiv":["2501.06579"]},"publisher":"Springer Nature","month":"05","department":[{"_id":"KrCh"}],"volume":15697,"doi":"10.1007/978-3-031-90653-4_14","file":[{"relation":"main_file","creator":"dernst","access_level":"open_access","checksum":"7dcd85e7e753bfa994c10b3cf9ebc185","date_created":"2025-06-02T11:13:49Z","success":1,"file_size":532181,"file_name":"2025_TACAS_Chatterjee_Goharshadi.pdf","content_type":"application/pdf","date_updated":"2025-06-02T11:13:49Z","file_id":"19773"}],"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"],"publication_status":"published","year":"2025","quality_controlled":"1","intvolume":"     15697","conference":{"name":"TACAS: Tools and Algorithms for the Construction and Analysis of Systems","start_date":"2025-05-03","end_date":"2025-05-08","location":"Hamilton, ON, Canada"},"has_accepted_license":"1","alternative_title":["LNCS"],"file_date_updated":"2025-06-02T11:13:49Z","date_published":"2025-05-01T00:00:00Z","article_processing_charge":"No","fulldoi":"https://doi.org/10.1007/978-3-031-90653-4_14","arxiv":1},{"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>","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>.","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.","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.","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.","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>.","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>"},"page":"11158-11166","project":[{"grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020"},{"name":"Bilateral Artificial Intelligence (Chatterjee)","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","grant_number":"COE12"}],"date_updated":"2026-09-16T06:55:21Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee"},{"id":"103b4fa0-896a-11ed-bdf8-87b697bef40d","last_name":"Kafshdar Goharshadi","first_name":"Ehsan","full_name":"Kafshdar Goharshadi, Ehsan","orcid":"0000-0002-8595-0587"},{"id":"67638922-f394-11eb-9cf6-f20423e08757","first_name":"Mehrdad","last_name":"Karrabi","full_name":"Karrabi, Mehrdad","orcid":"0009-0007-5253-9170"},{"full_name":"Motwani, Harshit J.","first_name":"Harshit J.","last_name":"Motwani"},{"full_name":"Seeliger, Maximilian","last_name":"Seeliger","first_name":"Maximilian"},{"full_name":"Zikelic, Dorde","orcid":"0000-0002-4681-1699","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","first_name":"Dorde","last_name":"Zikelic"}],"status":"public","date_created":"2025-05-11T22:02:39Z","title":"Quantified linear and polynomial arithmetic satisfiability via template-based skolemization","_id":"19667","abstract":[{"lang":"eng","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."}],"type":"conference","oa_version":"Preprint","OA_place":"repository","OA_type":"green","language":[{"iso":"eng"}],"scopus_import":"1","issue":"11","publication":"Proceedings of the 39th AAAI Conference on Artificial Intelligence","acknowledgement":"This work was partially funded by ERC CoG 863818 (ForM-SMArt) and Austrian Science Fund (FWF) 10.55776/COE12.","publication_identifier":{"issn":["2159-5399"],"eissn":["2374-3468"]},"ec_funded":1,"article_processing_charge":"No","conference":{"name":"AAAI: Conference on Artificial Intelligence","start_date":"2025-02-25","end_date":"2025-03-04","location":"Philadelphia, PA, United States"},"date_published":"2025-04-11T00:00:00Z","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2412.16226","open_access":"1"}],"arxiv":1,"fulldoi":"https://doi.org/10.1609/aaai.v39i11.33213","intvolume":"        39","publication_status":"published","quality_controlled":"1","year":"2025","doi":"10.1609/aaai.v39i11.33213","volume":39,"corr_author":"1","oa":1,"day":"11","publisher":"Association for the Advancement of Artificial Intelligence","month":"04","department":[{"_id":"KrCh"}],"external_id":{"arxiv":["2412.16226"]}},{"citation":{"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>","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.","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.","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.","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>.","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>"},"page":"11150-11157","project":[{"grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"},{"grant_number":"COE12","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","name":"Bilateral Artificial Intelligence (Chatterjee)"}],"date_updated":"2026-09-16T06:55:47Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","date_created":"2025-05-11T22:02:40Z","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"b391db08-1ffe-11ee-8b67-d18ddcfb5a14","first_name":"Ruichen","last_name":"Luo","full_name":"Luo, Ruichen"},{"id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","last_name":"Saona Urmeneta","first_name":"Raimundo J","full_name":"Saona Urmeneta, Raimundo J","orcid":"0000-0001-5103-038X"},{"id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub","last_name":"Svoboda","full_name":"Svoboda, Jakub","orcid":"0000-0002-1419-3267"}],"title":"Linear equations with min and max operators: Computational complexity","_id":"19669","abstract":[{"text":"We consider a class of optimization problems defined by a system of linear equations with min and max operators. This class of optimization problems has been studied under restrictive conditions, such as, (C1) the halting or stability condition; (C2) the non-negative coefficients condition; (C3) the sum upto 1 condition; and (C4) the only min or only max operator condition. Several seminal results in the literature focus on special cases. For example, turn-based stochastic games correspond to conditions C2 and C3; and Markov decision process to conditions C2, C3, and C4. However, the systematic computational complexity study of all the cases has not been explored, which we address in this work. Some highlights of our results are: with conditions C2 and C4, and with conditions C3 and C4, the problem is NP-complete, whereas with condition C1 only, the problem is in UP intersects coUP. Finally, we establish the computational complexity of the decision problem of checking the respective conditions.","lang":"eng"}],"type":"conference","oa_version":"Preprint","OA_place":"repository","OA_type":"green","language":[{"iso":"eng"}],"scopus_import":"1","issue":"11","publication":"Proceedings of the 39th AAAI Conference on Artificial Intelligence","acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant and the Austrian Science Fund (FWF) 10.55776/COE12 grant.","publication_identifier":{"eissn":["2374-3468"],"issn":["2159-5399"]},"ec_funded":1,"article_processing_charge":"No","conference":{"location":"Philadelphia, PA, United States","start_date":"2025-02-25","end_date":"2025-03-04","name":"AAAI: Conference on Artificial Intelligence"},"date_published":"2025-04-11T00:00:00Z","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2412.12228","open_access":"1"}],"arxiv":1,"fulldoi":"https://doi.org/10.1609/aaai.v39i11.33212","intvolume":"        39","publication_status":"published","year":"2025","quality_controlled":"1","doi":"10.1609/aaai.v39i11.33212","volume":39,"corr_author":"1","oa":1,"day":"11","publisher":"Association for the Advancement of Artificial Intelligence","month":"04","department":[{"_id":"KrCh"}],"external_id":{"arxiv":["2412.12228"]}},{"doi":"10.5281/ZENODO.14626585","OA_place":"repository","OA_type":"green","month":"01","department":[{"_id":"KrCh"}],"publisher":"Zenodo","day":"09","oa":1,"fulldoi":"https://doi.org/10.5281/ZENODO.14626585","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-09-16T06:57:17Z","main_file_link":[{"url":"https://doi.org/10.5281/ZENODO.14626585","open_access":"1"}],"related_material":{"record":[{"status":"public","id":"19743","relation":"used_in_publication"}]},"date_published":"2025-01-09T00:00:00Z","citation":{"short":"K. Chatterjee, T. Quatmann, M. Schäffeler, M. Weininger, T. Winkler, D. Zilken, (2025).","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.","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>.","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>.","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>","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>","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>."},"article_processing_charge":"No","year":"2025","type":"research_data_reference","oa_version":"Published Version","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."}],"_id":"19771","title":"Artifact: Fixed point certificates for reachability and expected rewards in MDPs","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"first_name":"Tim","last_name":"Quatmann","full_name":"Quatmann, Tim"},{"full_name":"Schäffeler, Maximilian","first_name":"Maximilian","last_name":"Schäffeler"},{"id":"02ab0197-cc70-11ed-ab61-918e71f56881","last_name":"Weininger","first_name":"Maximilian","orcid":"0000-0002-0163-2152","full_name":"Weininger, Maximilian"},{"full_name":"Winkler, Tobias","first_name":"Tobias","last_name":"Winkler"},{"last_name":"Zilken","first_name":"Daniel","id":"d8ebc24a-3f98-11f0-9044-8296d4f39ab3","full_name":"Zilken, Daniel"}],"date_created":"2025-06-02T10:13:24Z","status":"public","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"]},{"DOAJ_listed":"1","citation":{"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>.","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>","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.","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.","short":"V. Hübner, L. Schmid, C. Hilbe, K. Chatterjee, PNAS Nexus 4 (2025).","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>.","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>"},"project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"}],"related_material":{"record":[{"id":"19903","relation":"dissertation_contains","status":"public"}]},"date_updated":"2026-09-16T06:58:23Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2025-06-15T22:01:30Z","author":[{"orcid":"0009-0001-5009-4987","full_name":"Hübner, Valentin","id":"2c8aa207-dc7d-11ea-9b2f-f22972ecd910","first_name":"Valentin","last_name":"Hübner"},{"orcid":"0000-0002-6978-7329","full_name":"Schmid, Laura","first_name":"Laura","last_name":"Schmid","id":"38B437DE-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Christian","last_name":"Hilbe","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5116-955X","full_name":"Hilbe, Christian"},{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"}],"status":"public","title":"Stable strategies of direct and indirect reciprocity across all social dilemmas","_id":"19843","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"}],"oa_version":"Published Version","type":"journal_article","article_type":"original","OA_place":"publisher","OA_type":"gold","language":[{"iso":"eng"}],"scopus_import":"1","issue":"5","publication":"PNAS Nexus","ec_funded":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.).","publication_identifier":{"eissn":["2752-6542"]},"article_processing_charge":"Yes","has_accepted_license":"1","date_published":"2025-05-01T00:00:00Z","file_date_updated":"2025-06-23T08:09:50Z","fulldoi":"https://doi.org/10.1093/pnasnexus/pgaf154","ddc":["000"],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc/4.0/legalcode","short":"CC BY-NC (4.0)","name":"Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)","image":"/images/cc_by_nc.png"},"intvolume":"         4","publication_status":"published","year":"2025","quality_controlled":"1","pmid":1,"article_number":"pgaf154","doi":"10.1093/pnasnexus/pgaf154","file":[{"content_type":"application/pdf","date_updated":"2025-06-23T08:09:50Z","file_name":"2025_PNASNexus_Huebner.pdf","file_size":2551195,"file_id":"19867","access_level":"open_access","creator":"dernst","relation":"main_file","success":1,"date_created":"2025-06-23T08:09:50Z","checksum":"efd6648db3fc3ea0cdd7155d667e5f11"}],"volume":4,"oa":1,"corr_author":"1","day":"01","publisher":"Oxford University Press","department":[{"_id":"KrCh"}],"month":"05","external_id":{"pmid":["40417077"]}},{"project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"},{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}],"citation":{"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>.","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>","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>","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.","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."},"page":"1617-1645","related_material":{"record":[{"id":"19903","relation":"dissertation_contains","status":"public"}]},"PlanS_conform":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-09-16T06:58:23Z","status":"public","author":[{"first_name":"Valentin","last_name":"Hübner","id":"2c8aa207-dc7d-11ea-9b2f-f22972ecd910","full_name":"Hübner, Valentin","orcid":"0009-0001-5009-4987"},{"full_name":"Hilbe, Christian","orcid":"0000-0001-5116-955X","id":"2FDF8F3C-F248-11E8-B48F-1D18A9856A87","first_name":"Christian","last_name":"Hilbe"},{"last_name":"Staab","first_name":"Manuel","full_name":"Staab, Manuel"},{"id":"4E21749C-F248-11E8-B48F-1D18A9856A87","first_name":"Maria","last_name":"Kleshnina","orcid":"0000-0002-5518-8317","full_name":"Kleshnina, Maria"},{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"}],"date_created":"2025-02-23T23:01:57Z","_id":"19074","title":"Time-dependent strategies in repeated asymmetric public goods games","abstract":[{"lang":"eng","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."}],"article_type":"original","oa_version":"Published Version","type":"journal_article","OA_type":"hybrid","OA_place":"publisher","language":[{"iso":"eng"}],"scopus_import":"1","publication":"Dynamic Games and Applications","publication_identifier":{"issn":["2153-0785"],"eissn":["2153-0793"]},"ec_funded":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.), 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).","article_processing_charge":"Yes (via OA deal)","date_published":"2025-11-01T00:00:00Z","file_date_updated":"2025-12-30T08:01:35Z","has_accepted_license":"1","fulldoi":"https://doi.org/10.1007/s13235-025-00627-5","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"],"intvolume":"        15","quality_controlled":"1","year":"2025","publication_status":"published","isi":1,"file":[{"file_size":1126178,"file_name":"2025_DynGamesAppl_Huebner.pdf","content_type":"application/pdf","date_updated":"2025-12-30T08:01:35Z","file_id":"20888","relation":"main_file","creator":"dernst","access_level":"open_access","checksum":"de0a412cbb7d98bf5e6a551c26acbefa","date_created":"2025-12-30T08:01:35Z","success":1}],"doi":"10.1007/s13235-025-00627-5","volume":15,"oa":1,"corr_author":"1","day":"01","month":"11","department":[{"_id":"KrCh"}],"publisher":"Springer Nature","external_id":{"isi":["001415587800001"]}},{"language":[{"iso":"eng"}],"OA_place":"publisher","OA_type":"diamond","ec_funded":1,"acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant and Austrian Science Fund (FWF) 10.55776/COE12.\r\n","publication_identifier":{"eissn":["2640-3498"]},"publication":"The 41st Conference on Uncertainty in Artificial Intelligence","scopus_import":"1","date_updated":"2026-09-16T07:01:05Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"223-232","citation":{"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.","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.","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.","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.","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.","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."},"project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"},{"name":"Bilateral Artificial Intelligence (Chatterjee)","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","grant_number":"COE12"}],"type":"conference","oa_version":"Published Version","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."}],"title":"Lower bound on Howard policy iteration for deterministic Markov Decision Processes","_id":"20299","author":[{"first_name":"Ali","last_name":"Asadi","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","full_name":"Asadi, Ali"},{"first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"full_name":"De Raaij, Jakob","first_name":"Jakob","last_name":"De Raaij"}],"status":"public","date_created":"2025-09-07T22:01:34Z","volume":286,"file":[{"file_size":317097,"date_updated":"2025-09-09T06:27:59Z","content_type":"application/pdf","file_name":"2025_UAI_Asadi.pdf","file_id":"20313","relation":"main_file","creator":"dernst","access_level":"open_access","date_created":"2025-09-09T06:27:59Z","checksum":"4180c81bb6ed3b4f5c7a8e48d06520c6","success":1}],"external_id":{"arxiv":["2506.12254"]},"publisher":"ML Research Press","month":"01","department":[{"_id":"KrCh"},{"_id":"GradSch"}],"day":"01","corr_author":"1","oa":1,"arxiv":1,"has_accepted_license":"1","conference":{"location":"Rio de Janeiro, Brazil","name":"UAI: Conference on Uncertainty in Artificial Intelligence","end_date":"2025-07-25","start_date":"2025-07-21"},"alternative_title":["PMLR"],"date_published":"2025-01-01T00:00:00Z","file_date_updated":"2025-09-09T06:27:59Z","article_processing_charge":"No","publication_status":"published","quality_controlled":"1","year":"2025","intvolume":"       286","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"]},{"file_date_updated":"2025-09-09T08:19:41Z","alternative_title":["PMLR"],"date_published":"2025-07-01T00:00:00Z","conference":{"location":"Rio de Janeiro, Brazil","name":"UAI: Conference on Uncertainty in Artificial Intelligence","start_date":"2025-07-21","end_date":"2025-07-25"},"has_accepted_license":"1","article_processing_charge":"No","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)"},"year":"2025","quality_controlled":"1","publication_status":"published","intvolume":"       286","volume":286,"file":[{"relation":"main_file","creator":"dernst","access_level":"open_access","checksum":"1a37ebe7ba73ab6985765bf0d17a0acc","date_created":"2025-09-09T08:19:41Z","success":1,"file_size":307458,"file_name":"2025_UAI_AsadiAli.pdf","content_type":"application/pdf","date_updated":"2025-09-09T08:19:41Z","file_id":"20315"}],"day":"01","oa":1,"corr_author":"1","external_id":{"arxiv":["2412.00941"]},"month":"07","department":[{"_id":"KrCh"},{"_id":"GradSch"}],"publisher":"ML Research Press","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"},{"grant_number":"COE12","_id":"4029cfc7-b034-11f1-9e55-88ab2ff3b6ee","name":"Bilateral Artificial Intelligence (Chatterjee)"}],"page":"238-247","citation":{"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.","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.","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.","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.","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.","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."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-09-16T07:03:02Z","_id":"20297","title":"Limit-sure reachability for small memory policies in POMDPs is NP-complete","author":[{"full_name":"Asadi, Ali","last_name":"Asadi","first_name":"Ali","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb"},{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0001-5103-038X","full_name":"Saona Urmeneta, Raimundo J","first_name":"Raimundo J","last_name":"Saona Urmeneta","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425"},{"first_name":"Ali","last_name":"Shafiee","id":"2783031a-7378-11f0-b2d0-f17f1db2ebad","full_name":"Shafiee, Ali"}],"date_created":"2025-09-07T22:01:34Z","status":"public","type":"conference","oa_version":"Published Version","abstract":[{"lang":"eng","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."}],"OA_place":"publisher","OA_type":"diamond","language":[{"iso":"eng"}],"publication":"The 41st Conference on Uncertainty in Artificial Intelligence","scopus_import":"1","publication_identifier":{"eissn":["2640-3498"]},"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.","ec_funded":1},{"article_number":"26","volume":288,"file":[{"file_size":295466,"file_name":"2025_NeuS_Kresse.pdf","date_updated":"2025-09-09T08:10:13Z","content_type":"application/pdf","file_id":"20314","creator":"dernst","relation":"main_file","access_level":"open_access","checksum":"90a32defed34787e771a5c1623b6b0d2","date_created":"2025-09-09T08:10:13Z","success":1}],"day":"01","corr_author":"1","oa":1,"external_id":{"arxiv":["2505.19932"]},"publisher":"ML Research Press","department":[{"_id":"ChLa"},{"_id":"ToHe"}],"month":"06","has_accepted_license":"1","conference":{"location":"Philadephia, PA, United States","name":"NeuS: International Conferenceon Neuro-Symbolic Systems","end_date":"2025-05-30","start_date":"2025-05-28"},"date_published":"2025-06-01T00:00:00Z","file_date_updated":"2025-09-09T08:10:13Z","alternative_title":["PMLR"],"article_processing_charge":"No","acknowledged_ssus":[{"_id":"ScienComp"}],"arxiv":1,"ddc":["000"],"publication_status":"published","year":"2025","quality_controlled":"1","intvolume":"       288","OA_place":"publisher","OA_type":"diamond","language":[{"iso":"eng"}],"publication":"2nd International Conferenceon Neuro-Symbolic Systems","scopus_import":"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).","publication_identifier":{"eissn":["2640-3498"]},"ec_funded":1,"citation":{"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.","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.","short":"F. Kresse, E. Yu, C. Lampert, T.A. Henzinger, in:, 2nd International Conferenceon Neuro-Symbolic Systems, ML Research Press, 2025.","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.","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.","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.","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."},"project":[{"grant_number":"101020093","_id":"62781420-2b32-11ec-9570-8d9b63373d4d","name":"Vigilant Algorithmic Monitoring of Software","call_identifier":"H2020"},{"name":"Bilateral Artificial Intelligence (Lampert)","_id":"d8f03aaa-b035-11f1-8588-d5147fa879e0","grant_number":"COE12"}],"date_updated":"2026-09-16T07:02:18Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Logic gate neural networks are good for verification","_id":"20296","date_created":"2025-09-07T22:01:34Z","author":[{"id":"faff3c84-23f6-11ef-9085-e5187b51c604","last_name":"Kresse","first_name":"Fabian","full_name":"Kresse, Fabian"},{"first_name":"Zhengqi","last_name":"Yu","id":"20aa2ae8-f2f1-11ed-bbfa-8205053f1342","orcid":"0000-0002-4993-773X","full_name":"Yu, Zhengqi"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","last_name":"Lampert","first_name":"Christoph","orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph"},{"first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724"}],"status":"public","oa_version":"Published Version","type":"conference","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."}]},{"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).","ec_funded":1,"publication_identifier":{"eissn":["2153-0793"],"issn":["2153-0785"]},"scopus_import":"1","publication":"Dynamic Games and Applications","language":[{"iso":"eng"}],"OA_type":"hybrid","OA_place":"publisher","abstract":[{"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.","lang":"eng"}],"article_type":"original","type":"journal_article","oa_version":"Published Version","author":[{"first_name":"Luc","last_name":"Attia","full_name":"Attia, Luc"},{"full_name":"Lichev, Lyuben","last_name":"Lichev","first_name":"Lyuben","id":"9aa8388e-d003-11ee-8458-c4c1d7447977"},{"full_name":"Mitsche, Dieter","last_name":"Mitsche","first_name":"Dieter"},{"id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","last_name":"Saona Urmeneta","first_name":"Raimundo J","orcid":"0000-0001-5103-038X","full_name":"Saona Urmeneta, Raimundo J"},{"last_name":"Ziliotto","first_name":"Bruno","full_name":"Ziliotto, Bruno"}],"status":"public","date_created":"2025-04-06T22:01:32Z","_id":"19508","title":"Random zero-sum dynamic games on infinite directed graphs","PlanS_conform":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-09-16T07:00:33Z","project":[{"grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020"}],"page":"1517-1535","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.","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.","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>","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>.","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>","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>."},"related_material":{"record":[{"status":"public","id":"20234","relation":"dissertation_contains"}]},"month":"11","department":[{"_id":"MaKw"},{"_id":"KrCh"}],"publisher":"Springer Nature","external_id":{"isi":["001449708900001"]},"corr_author":"1","oa":1,"day":"01","file":[{"file_id":"20891","file_size":570994,"file_name":"2025_DynGamesAppl_Attia.pdf","content_type":"application/pdf","date_updated":"2025-12-30T08:13:04Z","checksum":"b3a1b7eef40c9ac2acf3fef563081694","date_created":"2025-12-30T08:13:04Z","success":1,"relation":"main_file","creator":"dernst","access_level":"open_access"}],"doi":"10.1007/s13235-025-00636-4","volume":15,"isi":1,"intvolume":"        15","year":"2025","quality_controlled":"1","publication_status":"published","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"],"fulldoi":"https://doi.org/10.1007/s13235-025-00636-4","article_processing_charge":"Yes (via OA deal)","date_published":"2025-11-01T00:00:00Z","file_date_updated":"2025-12-30T08:13:04Z","has_accepted_license":"1"}]