[{"day":"01","date_updated":"2026-10-16T07:53:26Z","fulldoi":"https://doi.org/10.1007/978-3-031-67695-6_4","scopus_import":"1","status":"public","type":"conference","page":"90-146","alternative_title":["LNCS"],"arxiv":1,"dataavailabilitystatement":"All model files used for the comparison, as well as the resulting log files, are available at DOI 10.5281/zenodo.8219191","department":[{"_id":"KrCh"}],"year":"2024","acknowledgement":"The authors are ordered alphabetically. This work was supported by DFG RTG 2236/2 (UnRAVeL) and DFG project TRR 248 (CPEC, ID 389792660), by the EU under MSCA grant agreements 101008233 (MISSION), 101034413 (IST-BRIDGE), and 101067199 (ProSVED), by ERC Starting Grant 101077178 (DEUCE), ERC Consolidator Grant 864075 (CAESAR), and ERC Advanced Grant 834115 (FUN2MODEL), by GAČR grant GA23-06963S (VESCAA), by National Science Foundation grant 1856733, by NextGenerationEU project D53D23008400006 (SMARTITUDE), and by NWO VENI grant 639.021.754.","quality_controlled":"1","researchdata_availability":"yes","OA_type":"green","publisher":"Springer Nature","_id":"18600","supplementarymaterial":"no","title":"Tools at the Frontiers of Quantitative Verification: QComp 2023 Competition Report","main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.2405.13583"}],"oa":1,"OA_place":"repository","date_published":"2024-11-01T00:00:00Z","das_tickbox":"1","volume":14550,"month":"11","publication":"TOOLympics Challenge 2023","citation":{"apa":"Andriushchenko, R., Bork, A., Budde, C. E., Češka, M., Grover, K., Hahn, E. M., … Zhang, Z. (2024). Tools at the Frontiers of Quantitative Verification: QComp 2023 Competition Report. In <i>TOOLympics Challenge 2023</i> (Vol. 14550, pp. 90–146). Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-67695-6_4\">https://doi.org/10.1007/978-3-031-67695-6_4</a>","mla":"Andriushchenko, Roman, et al. “Tools at the Frontiers of Quantitative Verification: QComp 2023 Competition Report.” <i>TOOLympics Challenge 2023</i>, vol. 14550, Springer Nature, 2024, pp. 90–146, doi:<a href=\"https://doi.org/10.1007/978-3-031-67695-6_4\">10.1007/978-3-031-67695-6_4</a>.","chicago":"Andriushchenko, Roman, Alexander Bork, Carlos E. Budde, Milan Češka, Kush Grover, Ernst Moritz Hahn, Arnd Hartmanns, et al. “Tools at the Frontiers of Quantitative Verification: QComp 2023 Competition Report.” In <i>TOOLympics Challenge 2023</i>, 14550:90–146. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-67695-6_4\">https://doi.org/10.1007/978-3-031-67695-6_4</a>.","ista":"Andriushchenko R, Bork A, Budde CE, Češka M, Grover K, Hahn EM, Hartmanns A, Israelsen B, Jansen N, Jeppson J, Junges S, Köhl MA, Könighofer B, Kretinsky J, Meggendorfer T, Parker D, Pranger S, Quatmann T, Ruijters E, Taylor L, Volk M, Weininger M, Zhang Z. 2024. Tools at the Frontiers of Quantitative Verification: QComp 2023 Competition Report. TOOLympics Challenge 2023. , LNCS, vol. 14550, 90–146.","ieee":"R. Andriushchenko <i>et al.</i>, “Tools at the Frontiers of Quantitative Verification: QComp 2023 Competition Report,” in <i>TOOLympics Challenge 2023</i>, 2024, vol. 14550, pp. 90–146.","short":"R. Andriushchenko, A. Bork, C.E. Budde, M. Češka, K. Grover, E.M. Hahn, A. Hartmanns, B. Israelsen, N. Jansen, J. Jeppson, S. Junges, M.A. Köhl, B. Könighofer, J. Kretinsky, T. Meggendorfer, D. Parker, S. Pranger, T. Quatmann, E. Ruijters, L. Taylor, M. Volk, M. Weininger, Z. Zhang, in:, TOOLympics Challenge 2023, Springer Nature, 2024, pp. 90–146.","ama":"Andriushchenko R, Bork A, Budde CE, et al. Tools at the Frontiers of Quantitative Verification: QComp 2023 Competition Report. In: <i>TOOLympics Challenge 2023</i>. Vol 14550. Springer Nature; 2024:90-146. doi:<a href=\"https://doi.org/10.1007/978-3-031-67695-6_4\">10.1007/978-3-031-67695-6_4</a>"},"intvolume":"     14550","language":[{"iso":"eng"}],"related_material":{"record":[{"id":"23142","status":"public","relation":"research_data"}]},"isi":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","external_id":{"isi":["001434957500004"],"arxiv":["2405.13583"]},"author":[{"first_name":"Roman","full_name":"Andriushchenko, Roman","last_name":"Andriushchenko"},{"last_name":"Bork","first_name":"Alexander","full_name":"Bork, Alexander"},{"first_name":"Carlos E.","full_name":"Budde, Carlos E.","last_name":"Budde"},{"last_name":"Češka","first_name":"Milan","full_name":"Češka, Milan"},{"first_name":"Kush","full_name":"Grover, Kush","last_name":"Grover"},{"last_name":"Hahn","first_name":"Ernst Moritz","full_name":"Hahn, Ernst Moritz"},{"last_name":"Hartmanns","first_name":"Arnd","full_name":"Hartmanns, Arnd"},{"first_name":"Bryant","full_name":"Israelsen, Bryant","last_name":"Israelsen"},{"last_name":"Jansen","first_name":"Nils","full_name":"Jansen, Nils"},{"last_name":"Jeppson","first_name":"Joshua","full_name":"Jeppson, Joshua"},{"full_name":"Junges, Sebastian","first_name":"Sebastian","last_name":"Junges"},{"last_name":"Köhl","full_name":"Köhl, Maximilian A.","first_name":"Maximilian A."},{"last_name":"Könighofer","first_name":"Bettina","full_name":"Könighofer, Bettina"},{"last_name":"Kretinsky","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8122-2881","first_name":"Jan","full_name":"Kretinsky, Jan"},{"orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","first_name":"Tobias","full_name":"Meggendorfer, Tobias","last_name":"Meggendorfer"},{"full_name":"Parker, David","first_name":"David","last_name":"Parker"},{"last_name":"Pranger","full_name":"Pranger, Stefan","first_name":"Stefan"},{"full_name":"Quatmann, Tim","first_name":"Tim","last_name":"Quatmann"},{"last_name":"Ruijters","first_name":"Enno","full_name":"Ruijters, Enno"},{"last_name":"Taylor","full_name":"Taylor, Landon","first_name":"Landon"},{"first_name":"Matthias","full_name":"Volk, Matthias","last_name":"Volk"},{"last_name":"Weininger","id":"02ab0197-cc70-11ed-ab61-918e71f56881","orcid":"0000-0002-0163-2152","first_name":"Maximilian","full_name":"Weininger, Maximilian"},{"first_name":"Zhen","full_name":"Zhang, Zhen","last_name":"Zhang"}],"abstract":[{"lang":"eng","text":"The analysis of formal models that include quantitative aspects such as timing or probabilistic choices is performed by quantitative verification tools. Broad and mature tool support is available for computing basic properties such as expected rewards on basic models such as Markov chains. Previous editions of QComp, the comparison of tools for the analysis of quantitative formal models, focused on this setting. Many application scenarios, however, require more advanced property types such as LTL and parameter synthesis queries as well as advanced models like stochastic games and partially observable MDPs. For these, tool support is in its infancy today. This paper presents the outcomes of QComp 2023: a survey of the state of the art in quantitative verification tool support for advanced property types and models. With tools ranging from first research prototypes to well-supported integrations into established toolsets, this report highlights today’s active areas and tomorrow’s challenges in tool-focused research for quantitative verification."}],"publication_status":"published","date_created":"2024-12-01T23:01:53Z","article_processing_charge":"No","doi":"10.1007/978-3-031-67695-6_4","oa_version":"Preprint","publication_identifier":{"isbn":["9783031676949"],"eissn":["1611-3349"],"issn":["0302-9743"]}},{"article_number":"5","file_date_updated":"2025-01-08T09:49:31Z","abstract":[{"lang":"eng","text":"We study two-player zero-sum concurrent stochastic games with finite state and action space played for an infinite number of steps. In every step, the two players simultaneously and independently choose an action. Given the current state and the chosen actions, the next state is obtained according to a stochastic transition function. An objective is a measurable function on plays (or infinite trajectories) of the game, and the value for an objective is the maximal expectation that the player can guarantee against the adversarial player. We consider: (a) stateful-discounted objectives, which are similar to the classical discounted-sum objectives, but states are associated with different discount factors rather than a single discount factor; and (b) parity objectives, which are a canonical representation for ω-regular objectives. For stateful-discounted objectives, given an ordering of the discount factors, the limit value is the limit of the value of the stateful-discounted objectives, as the discount factors approach zero according to the given order.\r\nThe computational problem we consider is the approximation of the value within an arbitrary\r\nadditive error. The above problem is known to be in EXPSPACE for the limit value of statefuldiscounted objectives and in PSPACE for parity objectives. The best-known algorithms for both the above problems are at least exponential time, with an exponential dependence on the number of states and actions. Our main results for the value approximation problem for the limit value of stateful-discounted objectives and parity objectives are as follows: (a) we establish TFNP[NP] complexity; and (b) we present algorithms that improve the dependency on the number of actions in the exponent from linear to logarithmic. In particular, if the number of states is constant, our algorithms run in polynomial time."}],"author":[{"last_name":"Asadi","id":"02d96aae-000e-11ec-b801-cadd0a5eefbb","first_name":"Ali","full_name":"Asadi, Ali"},{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"last_name":"Saona Urmeneta","full_name":"Saona Urmeneta, Raimundo J","first_name":"Raimundo J","orcid":"0000-0001-5103-038X","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425"},{"orcid":"0000-0002-1419-3267","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub","full_name":"Svoboda, Jakub","last_name":"Svoboda"}],"external_id":{"arxiv":["2405.02486"],"isi":["001537516500005"]},"date_created":"2024-06-03T07:44:27Z","article_processing_charge":"No","publication_status":"published","doi":"10.4230/LIPIcs.FSTTCS.2024.5","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773553"]},"oa_version":"Published Version","citation":{"mla":"Asadi, Ali, et al. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives: Complexity and Algorithms.” <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, vol. 323, 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">10.4230/LIPIcs.FSTTCS.2024.5</a>.","apa":"Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., &#38; Svoboda, J. (2024). Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. In <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i> (Vol. 323). Gujarat, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5</a>","short":"A. Asadi, K. Chatterjee, R.J. Saona Urmeneta, J. Svoboda, in:, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ama":"Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. In: <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>. Vol 323. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">10.4230/LIPIcs.FSTTCS.2024.5</a>","chicago":"Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Jakub Svoboda. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives: Complexity and Algorithms.” In <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Vol. 323. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5\">https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5</a>.","ieee":"A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and J. Svoboda, “Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms,” in <i>44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science</i>, Gujarat, India, 2024, vol. 323.","ista":"Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. 2024. Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms. 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LIPIcs, vol. 323, 5."},"intvolume":"       323","publication":"44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","related_material":{"record":[{"relation":"dissertation_contains","id":"23079","status":"public"}]},"language":[{"iso":"eng"}],"corr_author":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_published":"2024-12-05T00:00:00Z","OA_place":"publisher","das_tickbox":"0","oa":1,"month":"12","volume":323,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"17099","supplementarymaterial":"no","title":"Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms","acknowledgement":"This research was partially supported by ERC CoG 863818 (ForM-SMArt), Austrian\r\nScience Fund (FWF) 10.55776/COE12, and French Agence Nationale de la Recherche (ANR)\r\nANR-21-CE40-0020 (CONVERGENCE project)","OA_type":"gold","researchdata_availability":"no","conference":{"end_date":"2024-12-18","location":"Gujarat, India","start_date":"2024-12-16","name":"FSTTCS: Foundations of Software Technology and Theoretical Computer Science"},"quality_controlled":"1","arxiv":1,"department":[{"_id":"KrCh"}],"file":[{"success":1,"checksum":"5b544ab4692b93300b404435c036ddd4","file_id":"18777","date_created":"2025-01-08T09:49:31Z","access_level":"open_access","file_size":847960,"date_updated":"2025-01-08T09:49:31Z","creator":"dernst","relation":"main_file","file_name":"2024_LIPIcs_Asadi.pdf","content_type":"application/pdf"}],"year":"2024","has_accepted_license":"1","status":"public","license":"https://creativecommons.org/licenses/by/4.0/","type":"conference","ec_funded":1,"project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020"}],"alternative_title":["LIPIcs"],"fulldoi":"https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5","date_updated":"2026-10-16T08:00:46Z","day":"05","ddc":["000"],"scopus_import":"1"},{"acknowledgement":"This work was supported in part by the ERC-2020-CoG 863818 (FoRM-SMArt), the Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 1 grant, Google Research Award 2023 and the SBI Foundation Hub for Data and Analytics.","conference":{"name":"IJCAI: International Joint Conference on Artificial Intelligence","start_date":"2024-08-03","end_date":"2024-08-09","location":"Jeju, Korea"},"researchdata_availability":"no","quality_controlled":"1","arxiv":1,"department":[{"_id":"KrCh"}],"year":"2024","status":"public","type":"conference","page":"3-12","ec_funded":1,"project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"}],"fulldoi":"https://doi.org/10.24963/ijcai.2024/1","date_updated":"2026-10-16T08:08:15Z","day":"01","scopus_import":"1","abstract":[{"text":"Markov Decision Processes (MDPs) are a classical model for decision making in the presence of uncertainty. Often they are viewed as state transformers with planning objectives defned with respect to paths over MDP states. An increasingly\r\npopular alternative is to view them as distribution transformers, giving rise to a sequence of probability distributions over MDP states. For instance, reachability and safety properties in modeling robot swarms or chemical reaction networks are naturally defned in terms of probability distributions over states. Verifying such distributional properties is known to be hard and often beyond the reach of classical state-based verifcation techniques. In this work, we consider the problems of certifed policy (i.e. controller) verifcation and synthesis in MDPs under distributional reach-avoidance specifcations. By certifed we mean that, along with a policy, we also aim to synthesize a (checkable) certifcate ensuring that the MDP indeed satisfes the property. Thus, given the target set of distributions and an unsafe set of distributions over MDP states, our goal is to either synthesize a certifcate for a given policy or synthesize a policy along with a certifcate, proving that the target distribution can be reached while avoiding unsafe distributions. To solve this problem, we introduce the novel notion of distributional reach-avoid certifcates and present automated procedures for (1) synthesizing a certifcate for a given policy, and (2) synthesizing a policy together with the certifcate, both providing formal guarantees on certifcate correctness. Our experimental evaluation demonstrates the ability of our method to solve several non-trivial examples, including a multi-agent robot-swarm model, to synthesize certifed policies and to certify existing policies. ","lang":"eng"}],"author":[{"full_name":"Akshay, S","first_name":"S","last_name":"Akshay"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee"},{"last_name":"Meggendorfer","first_name":"Tobias","full_name":"Meggendorfer, Tobias","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","orcid":"0000-0002-1712-2165"},{"first_name":"Dorde","full_name":"Zikelic, Dorde","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4681-1699","last_name":"Zikelic"}],"external_id":{"arxiv":["2405.04015"]},"doi":"10.24963/ijcai.2024/1","date_created":"2024-09-29T22:01:38Z","publication_status":"published","article_processing_charge":"No","oa_version":"Preprint","publication_identifier":{"issn":["1045-0823"],"isbn":["9781956792041"]},"citation":{"short":"S. Akshay, K. Chatterjee, T. Meggendorfer, D. Zikelic, in:, Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence, 2024, pp. 3–12.","ama":"Akshay S, Chatterjee K, Meggendorfer T, Zikelic D. Certified policy verification and synthesis for MDPs under distributional reach-avoidance properties. In: <i>Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence</i>. International Joint Conferences on Artificial Intelligence; 2024:3-12. doi:<a href=\"https://doi.org/10.24963/ijcai.2024/1\">10.24963/ijcai.2024/1</a>","ieee":"S. Akshay, K. Chatterjee, T. Meggendorfer, and D. Zikelic, “Certified policy verification and synthesis for MDPs under distributional reach-avoidance properties,” in <i>Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence</i>, Jeju, Korea, 2024, pp. 3–12.","chicago":"Akshay, S, Krishnendu Chatterjee, Tobias Meggendorfer, and Dorde Zikelic. “Certified Policy Verification and Synthesis for MDPs under Distributional Reach-Avoidance Properties.” In <i>Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence</i>, 3–12. International Joint Conferences on Artificial Intelligence, 2024. <a href=\"https://doi.org/10.24963/ijcai.2024/1\">https://doi.org/10.24963/ijcai.2024/1</a>.","ista":"Akshay S, Chatterjee K, Meggendorfer T, Zikelic D. 2024. Certified policy verification and synthesis for MDPs under distributional reach-avoidance properties. Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence. IJCAI: International Joint Conference on Artificial Intelligence, 3–12.","apa":"Akshay, S., Chatterjee, K., Meggendorfer, T., &#38; Zikelic, D. (2024). Certified policy verification and synthesis for MDPs under distributional reach-avoidance properties. In <i>Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence</i> (pp. 3–12). Jeju, Korea: International Joint Conferences on Artificial Intelligence. <a href=\"https://doi.org/10.24963/ijcai.2024/1\">https://doi.org/10.24963/ijcai.2024/1</a>","mla":"Akshay, S., et al. “Certified Policy Verification and Synthesis for MDPs under Distributional Reach-Avoidance Properties.” <i>Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence</i>, International Joint Conferences on Artificial Intelligence, 2024, pp. 3–12, doi:<a href=\"https://doi.org/10.24963/ijcai.2024/1\">10.24963/ijcai.2024/1</a>."},"publication":"Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence","language":[{"iso":"eng"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","corr_author":"1","das_tickbox":"0","date_published":"2024-09-01T00:00:00Z","oa":1,"month":"09","publisher":"International Joint Conferences on Artificial Intelligence","supplementarymaterial":"no","_id":"18159","title":"Certified policy verification and synthesis for MDPs under distributional reach-avoidance properties","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2405.04015"}]},{"acknowledgement":"Tobias Winkler and Joost-Pieter Katoen are supported by the DFG RTG 2236 UnRAVeL and the innovation programme under the Marie Skłodowska-Curie grant agreement No. 101008233 (Mission). Krishnendu Chatterjee is supported by the ERC CoG 863818 (ForM-SMArt) and the Vienna Science and Technology Fund (WWTF) Project ICT15-003. Maximilian Weininger is supported by the DFG projects 383882557 Statistical Unbounded Verification (SUV) and 427755713 Group-By Objectives in Probabilistic Verification (GOPro). Stefanie Mohr is supported by the DFG RTG 2428 CONVEY. Open Access funding enabled and organized by Projekt DEAL.","quality_controlled":"1","OA_type":"hybrid","researchdata_availability":"yes","year":"2024","file":[{"checksum":"111e76b76163640a2c89237642af586f","date_created":"2025-01-09T07:31:31Z","file_id":"18781","access_level":"open_access","file_size":2614190,"success":1,"creator":"dernst","file_name":"2024_FromMethodsSys_Chatterjee.pdf","relation":"main_file","content_type":"application/pdf","date_updated":"2025-01-09T07:31:31Z"}],"dataavailabilitystatement":"The software and data used to generate the experimental results of this paper are available online(See https://doi.org/10.5281/zenodo.5798108 and https://doi.org/10.5281/zenodo.7233605 for the experiments described in Sect. 5.1 and Sect. 5.2, respectively.).","department":[{"_id":"KrCh"}],"type":"journal_article","status":"public","has_accepted_license":"1","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","call_identifier":"H2020"},{"grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425"}],"page":"40-80","ec_funded":1,"date_updated":"2026-10-16T08:04:16Z","day":"01","fulldoi":"https://doi.org/10.1007/s10703-023-00411-4","scopus_import":"1","ddc":["000"],"external_id":{"isi":["000946174300001"]},"author":[{"last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"last_name":"Katoen","full_name":"Katoen, Joost P","first_name":"Joost P","id":"4524F760-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6143-1926"},{"last_name":"Mohr","first_name":"Stefanie","full_name":"Mohr, Stefanie"},{"last_name":"Weininger","full_name":"Weininger, Maximilian","first_name":"Maximilian"},{"last_name":"Winkler","full_name":"Winkler, Tobias","first_name":"Tobias"}],"abstract":[{"lang":"eng","text":"We study turn-based stochastic zero-sum games with lexicographic preferences over objectives. Stochastic games are standard models in control, verification, and synthesis of stochastic reactive systems that exhibit both randomness as well as controllable and adversarial non-determinism. Lexicographic order allows one to consider multiple objectives with a strict preference order. To the best of our knowledge, stochastic games with lexicographic objectives have not been studied before. For a mixture of reachability and safety objectives, we show that deterministic lexicographically optimal strategies exist and memory is only required to remember the already satisfied and violated objectives. For a constant number of objectives, we show that the relevant decision problem is in NP∩coNP, matching the current known bound for single objectives; and in general the decision problem is PSPACE-hard and can be solved in NEXPTIME∩coNEXPTIME. We present an algorithm that computes the lexicographically optimal strategies via a reduction to the computation of optimal strategies in a sequence of single-objectives games. For omega-regular objectives, we restrict our analysis to one-player games, also known as Markov decision processes. We show that lexicographically optimal strategies exist and need either randomization or finite memory. We present an algorithm that solves the relevant decision problem in polynomial time. We have implemented our algorithms and report experimental results on various case studies."}],"file_date_updated":"2025-01-09T07:31:31Z","publication_identifier":{"eissn":["1572-8102"]},"oa_version":"Published Version","doi":"10.1007/s10703-023-00411-4","date_created":"2023-03-19T23:00:59Z","article_processing_charge":"Yes (via OA deal)","publication_status":"published","publication":"Formal Methods in System Design","citation":{"ieee":"K. Chatterjee, J. P. Katoen, S. Mohr, M. Weininger, and T. Winkler, “Stochastic games with lexicographic objectives,” <i>Formal Methods in System Design</i>, vol. 63. Springer Nature, pp. 40–80, 2024.","chicago":"Chatterjee, Krishnendu, Joost P Katoen, Stefanie Mohr, Maximilian Weininger, and Tobias Winkler. “Stochastic Games with Lexicographic Objectives.” <i>Formal Methods in System Design</i>. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/s10703-023-00411-4\">https://doi.org/10.1007/s10703-023-00411-4</a>.","ista":"Chatterjee K, Katoen JP, Mohr S, Weininger M, Winkler T. 2024. Stochastic games with lexicographic objectives. Formal Methods in System Design. 63, 40–80.","ama":"Chatterjee K, Katoen JP, Mohr S, Weininger M, Winkler T. Stochastic games with lexicographic objectives. <i>Formal Methods in System Design</i>. 2024;63:40-80. doi:<a href=\"https://doi.org/10.1007/s10703-023-00411-4\">10.1007/s10703-023-00411-4</a>","short":"K. Chatterjee, J.P. Katoen, S. Mohr, M. Weininger, T. Winkler, Formal Methods in System Design 63 (2024) 40–80.","mla":"Chatterjee, Krishnendu, et al. “Stochastic Games with Lexicographic Objectives.” <i>Formal Methods in System Design</i>, vol. 63, Springer Nature, 2024, pp. 40–80, doi:<a href=\"https://doi.org/10.1007/s10703-023-00411-4\">10.1007/s10703-023-00411-4</a>.","apa":"Chatterjee, K., Katoen, J. P., Mohr, S., Weininger, M., &#38; Winkler, T. (2024). Stochastic games with lexicographic objectives. <i>Formal Methods in System Design</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10703-023-00411-4\">https://doi.org/10.1007/s10703-023-00411-4</a>"},"intvolume":"        63","isi":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"8272"}]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"month":"10","volume":63,"oa":1,"date_published":"2024-10-01T00:00:00Z","OA_place":"publisher","das_tickbox":"1","supplementarymaterial":"no","_id":"12738","publisher":"Springer Nature","article_type":"original","title":"Stochastic games with lexicographic objectives"},{"project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"ec_funded":1,"page":"6707-6715","status":"public","type":"conference","scopus_import":"1","date_updated":"2026-10-16T08:07:05Z","day":"01","fulldoi":"https://doi.org/10.24963/ijcai.2024/741","quality_controlled":"1","researchdata_availability":"no","conference":{"location":"Jeju, South Korea","end_date":"2024-08-09","start_date":"2024-08-03","name":"IJCAI: International Joint Conference on Artificial Intelligence"},"OA_type":"green","acknowledgement":"This work was supported in part by the ERC-2020-CoG 863818 (FoRM-SMArt) and the Czech Science Foundation\r\ngrant no. GA23-06963S.","department":[{"_id":"KrCh"}],"year":"2024","arxiv":1,"oa":1,"date_published":"2024-09-01T00:00:00Z","OA_place":"repository","das_tickbox":"0","month":"09","title":"Solving long-run average reward robust MDPs via stochastic games","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2312.13912","open_access":"1"}],"publisher":"International Joint Conferences on Artificial Intelligence","supplementarymaterial":"no","_id":"18160","publication_status":"published","date_created":"2024-09-29T22:01:39Z","article_processing_charge":"No","doi":"10.24963/ijcai.2024/741","publication_identifier":{"issn":["1045-0823"],"isbn":["9781956792041"]},"oa_version":"Preprint","external_id":{"arxiv":["2312.13912"]},"author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee"},{"first_name":"Ehsan","full_name":"Kafshdar Goharshadi, Ehsan","id":"103b4fa0-896a-11ed-bdf8-87b697bef40d","orcid":"0000-0002-8595-0587","last_name":"Kafshdar Goharshadi"},{"last_name":"Karrabi","full_name":"Karrabi, Mehrdad","first_name":"Mehrdad","id":"67638922-f394-11eb-9cf6-f20423e08757","orcid":"0009-0007-5253-9170"},{"last_name":"Novotný","full_name":"Novotný, Petr","first_name":"Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Zikelic","full_name":"Zikelic, Dorde","first_name":"Dorde","orcid":"0000-0002-4681-1699","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87"}],"abstract":[{"lang":"eng","text":"Markov decision processes (MDPs) provide a standard framework for sequential decision making under uncertainty. However, MDPs do not take uncertainty in transition probabilities into account. Robust Markov decision processes (RMDPs) address this shortcoming of MDPs by assigning to each transition an uncertainty set rather than a single probability value. In this work, we consider polytopic RMDPs in which all uncertainty sets are polytopes and study the problem of solving long-run average reward polytopic RMDPs. We present a novel perspective on this problem and show that it can be reduced to solving long-run average reward turn-based stochastic games with finite state and action spaces. This reduction allows us to derive several important consequences that were hitherto not known to hold for polytopic RMDPs. First, we derive new computational complexity bounds for solving long-run average reward polytopic RMDPs, showing for the first time that the threshold decision problem for them is in NP∩CONP and that they admit a randomized algorithm with sub-exponential expected runtime. Second, we present Robust Polytopic Policy Iteration (RPPI), a novel policy iteration algorithm for solving long-run average reward polytopic RMDPs. Our experimental evaluation shows that RPPI is much more efficient in solving long-run average reward polytopic RMDPs compared to state-of-the-art methods based on value iteration. "}],"language":[{"iso":"eng"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","corr_author":"1","publication":"33rd International Joint Conference on Artificial Intelligence","citation":{"mla":"Chatterjee, Krishnendu, et al. “Solving Long-Run Average Reward Robust MDPs via Stochastic Games.” <i>33rd International Joint Conference on Artificial Intelligence</i>, International Joint Conferences on Artificial Intelligence, 2024, pp. 6707–15, doi:<a href=\"https://doi.org/10.24963/ijcai.2024/741\">10.24963/ijcai.2024/741</a>.","apa":"Chatterjee, K., Goharshady, E., Karrabi, M., Novotný, P., &#38; Zikelic, D. (2024). Solving long-run average reward robust MDPs via stochastic games. In <i>33rd International Joint Conference on Artificial Intelligence</i> (pp. 6707–6715). Jeju, South Korea: International Joint Conferences on Artificial Intelligence. <a href=\"https://doi.org/10.24963/ijcai.2024/741\">https://doi.org/10.24963/ijcai.2024/741</a>","chicago":"Chatterjee, Krishnendu, Ehsan Goharshady, Mehrdad Karrabi, Petr Novotný, and Dorde Zikelic. “Solving Long-Run Average Reward Robust MDPs via Stochastic Games.” In <i>33rd International Joint Conference on Artificial Intelligence</i>, 6707–15. International Joint Conferences on Artificial Intelligence, 2024. <a href=\"https://doi.org/10.24963/ijcai.2024/741\">https://doi.org/10.24963/ijcai.2024/741</a>.","ieee":"K. Chatterjee, E. Goharshady, M. Karrabi, P. Novotný, and D. Zikelic, “Solving long-run average reward robust MDPs via stochastic games,” in <i>33rd International Joint Conference on Artificial Intelligence</i>, Jeju, South Korea, 2024, pp. 6707–6715.","ista":"Chatterjee K, Goharshady E, Karrabi M, Novotný P, Zikelic D. 2024. Solving long-run average reward robust MDPs via stochastic games. 33rd International Joint Conference on Artificial Intelligence. IJCAI: International Joint Conference on Artificial Intelligence, 6707–6715.","ama":"Chatterjee K, Goharshady E, Karrabi M, Novotný P, Zikelic D. Solving long-run average reward robust MDPs via stochastic games. In: <i>33rd International Joint Conference on Artificial Intelligence</i>. International Joint Conferences on Artificial Intelligence; 2024:6707-6715. doi:<a href=\"https://doi.org/10.24963/ijcai.2024/741\">10.24963/ijcai.2024/741</a>","short":"K. Chatterjee, E. Goharshady, M. Karrabi, P. Novotný, D. Zikelic, in:, 33rd International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence, 2024, pp. 6707–6715."}},{"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"OA_place":"publisher","date_published":"2024-12-01T00:00:00Z","das_tickbox":"0","oa":1,"volume":301,"month":"12","publisher":"Elsevier","_id":"17474","supplementarymaterial":"no","title":"Entropic risk for turn-based stochastic games","article_type":"original","article_number":"105214","file_date_updated":"2025-01-09T13:49:03Z","author":[{"first_name":"Christel","full_name":"Baier, Christel","last_name":"Baier"},{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"first_name":"Tobias","full_name":"Meggendorfer, Tobias","orcid":"0000-0002-1712-2165","id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","last_name":"Meggendorfer"},{"first_name":"Jakob","full_name":"Piribauer, Jakob","last_name":"Piribauer"}],"abstract":[{"text":"Entropic risk (ERisk) is an established risk measure in finance, quantifying risk by an exponential re-weighting of rewards. We study ERisk for the first time in the context of turn-based stochastic games with the total reward objective. This gives rise to an objective function that demands the control of systems in a risk-averse manner. We show that the resulting games are determined and, in particular, admit optimal memoryless deterministic strategies. This contrasts risk measures that previously have been considered in the special case of Markov decision processes and that require randomization and/or memory. We provide several results on the decidability and the computational complexity of the threshold problem, i.e. whether the optimal value of ERisk exceeds a given threshold. Furthermore, an approximation algorithm for the optimal value of ERisk is provided.","lang":"eng"}],"external_id":{"arxiv":["2307.06611"],"isi":["001301143400001"]},"doi":"10.1016/j.ic.2024.105214","date_created":"2024-09-01T22:01:07Z","article_processing_charge":"Yes (in subscription journal)","publication_status":"published","publication_identifier":{"eissn":["1090-2651"],"issn":["0890-5401"]},"oa_version":"Published Version","intvolume":"       301","citation":{"mla":"Baier, Christel, et al. “Entropic Risk for Turn-Based Stochastic Games.” <i>Information and Computation</i>, vol. 301, 105214, Elsevier, 2024, doi:<a href=\"https://doi.org/10.1016/j.ic.2024.105214\">10.1016/j.ic.2024.105214</a>.","apa":"Baier, C., Chatterjee, K., Meggendorfer, T., &#38; Piribauer, J. (2024). Entropic risk for turn-based stochastic games. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2024.105214\">https://doi.org/10.1016/j.ic.2024.105214</a>","ama":"Baier C, Chatterjee K, Meggendorfer T, Piribauer J. Entropic risk for turn-based stochastic games. <i>Information and Computation</i>. 2024;301. doi:<a href=\"https://doi.org/10.1016/j.ic.2024.105214\">10.1016/j.ic.2024.105214</a>","short":"C. Baier, K. Chatterjee, T. Meggendorfer, J. Piribauer, Information and Computation 301 (2024).","chicago":"Baier, Christel, Krishnendu Chatterjee, Tobias Meggendorfer, and Jakob Piribauer. “Entropic Risk for Turn-Based Stochastic Games.” <i>Information and Computation</i>. Elsevier, 2024. <a href=\"https://doi.org/10.1016/j.ic.2024.105214\">https://doi.org/10.1016/j.ic.2024.105214</a>.","ista":"Baier C, Chatterjee K, Meggendorfer T, Piribauer J. 2024. Entropic risk for turn-based stochastic games. Information and Computation. 301, 105214.","ieee":"C. Baier, K. Chatterjee, T. Meggendorfer, and J. Piribauer, “Entropic risk for turn-based stochastic games,” <i>Information and Computation</i>, vol. 301. Elsevier, 2024."},"publication":"Information and Computation","related_material":{"record":[{"status":"public","id":"14417","relation":"earlier_version"}]},"language":[{"iso":"eng"}],"corr_author":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"has_accepted_license":"1","status":"public","type":"journal_article","fulldoi":"https://doi.org/10.1016/j.ic.2024.105214","date_updated":"2026-10-16T08:04:31Z","day":"01","ddc":["000"],"scopus_import":"1","acknowledgement":"Krishnendu Chatterjee reports financial support was provided by European Research Council.","OA_type":"hybrid","researchdata_availability":"no","quality_controlled":"1","arxiv":1,"department":[{"_id":"KrCh"}],"file":[{"date_updated":"2025-01-09T13:49:03Z","content_type":"application/pdf","relation":"main_file","file_name":"2024_InformationComputation_Baier.pdf","creator":"dernst","success":1,"file_size":724703,"file_id":"18817","date_created":"2025-01-09T13:49:03Z","access_level":"open_access","checksum":"f68e0c2f46f9b9c86815406bcf2ee2d4"}],"year":"2024"},{"type":"conference","status":"public","project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"},{"_id":"bd622a5c-d553-11ed-ba76-bae280ba8aff","grant_number":"894907","name":"Graphical Games"}],"ec_funded":1,"day":"01","date_updated":"2026-10-16T08:07:55Z","fulldoi":"https://doi.org/10.1109/noms59830.2024.10575579","scopus_import":"1","acknowledgement":"Research was supported by the Austrian Science Fund (FWF), project I 5025-N (DELTA), 2020-2024. Esra Ceylan’s research was supported by FFG, FEMtech Praktika für Studentinnen. Jakub Svoboda and Krishnendu Chatterjee were supported by the European Research Council (ERC) CoG 863818 (ForM-SMArt).","quality_controlled":"1","OA_type":"green","conference":{"end_date":"2024-05-10","location":"Seoul, Republic of Korea","name":"NOMS: Network Operations and Management Symposiu ","start_date":"2024-05-06"},"researchdata_availability":"no","year":"2024","department":[{"_id":"KrCh"}],"month":"05","oa":1,"das_tickbox":"0","OA_place":"other","date_published":"2024-05-01T00:00:00Z","_id":"18925","supplementarymaterial":"no","publisher":"IEEE","main_file_link":[{"url":"https://schmiste.github.io/noms24.pdf","open_access":"1"}],"title":"Congestion-free rerouting of network flows: Hardness and an FPT algorithm","external_id":{"isi":["001270140300143"]},"author":[{"first_name":"Esra","full_name":"Ceylan, Esra","id":"cb1ca1d8-dcc0-11ef-baa5-9f1b3ef75933","last_name":"Ceylan"},{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"},{"orcid":"0000-0002-1419-3267","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","first_name":"Jakub","full_name":"Svoboda, Jakub","last_name":"Svoboda"}],"abstract":[{"lang":"eng","text":"Given the increasingly stringent requirements on the performance and efficiency of communication networks, over the last years, great efforts have been made to render networks more flexible and programmable. In particular, modern networks support a flexible rerouting of flows, e.g., depending on the dynamically changing traffic or network conditions. However, the underlying algorithmic problems are still not well-understood today.In this paper, we revisit the k-Network Flow Update problem that asks for a schedule to reroute k unsplittable flows from their current paths to the given new paths, in a congestion-free manner in a capacitated network. We show that the problem is already NP-hard for three acyclic flows on simple directed graphs. Our main contribution is an efficient algorithm for sparse networks; specifically the algorithm is fixed parameter tractable in the number of flows and the treewidth of a graph that is the union of all flows. Our results also settle the open complexity question in the literature."}],"publication_identifier":{"eissn":["2374-9709"],"isbn":["9798350327946"]},"oa_version":"Submitted Version","article_processing_charge":"No","doi":"10.1109/noms59830.2024.10575579","date_created":"2025-01-27T15:06:45Z","publication_status":"published","publication":"NOMS 2024-2024 IEEE Network Operations and Management Symposium","citation":{"apa":"Ceylan, E., Chatterjee, K., Schmid, S., &#38; Svoboda, J. (2024). Congestion-free rerouting of network flows: Hardness and an FPT algorithm. In <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>. Seoul, Republic of Korea: IEEE. <a href=\"https://doi.org/10.1109/noms59830.2024.10575579\">https://doi.org/10.1109/noms59830.2024.10575579</a>","mla":"Ceylan, Esra, et al. “Congestion-Free Rerouting of Network Flows: Hardness and an FPT Algorithm.” <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>, IEEE, 2024, doi:<a href=\"https://doi.org/10.1109/noms59830.2024.10575579\">10.1109/noms59830.2024.10575579</a>.","chicago":"Ceylan, Esra, Krishnendu Chatterjee, Stefan Schmid, and Jakub Svoboda. “Congestion-Free Rerouting of Network Flows: Hardness and an FPT Algorithm.” In <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>. IEEE, 2024. <a href=\"https://doi.org/10.1109/noms59830.2024.10575579\">https://doi.org/10.1109/noms59830.2024.10575579</a>.","ista":"Ceylan E, Chatterjee K, Schmid S, Svoboda J. 2024. Congestion-free rerouting of network flows: Hardness and an FPT algorithm. NOMS 2024-2024 IEEE Network Operations and Management Symposium. NOMS: Network Operations and Management Symposiu .","ieee":"E. Ceylan, K. Chatterjee, S. Schmid, and J. Svoboda, “Congestion-free rerouting of network flows: Hardness and an FPT algorithm,” in <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>, Seoul, Republic of Korea, 2024.","ama":"Ceylan E, Chatterjee K, Schmid S, Svoboda J. Congestion-free rerouting of network flows: Hardness and an FPT algorithm. In: <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>. IEEE; 2024. doi:<a href=\"https://doi.org/10.1109/noms59830.2024.10575579\">10.1109/noms59830.2024.10575579</a>","short":"E. Ceylan, K. Chatterjee, S. Schmid, J. Svoboda, in:, NOMS 2024-2024 IEEE Network Operations and Management Symposium, IEEE, 2024."},"isi":1,"corr_author":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","language":[{"iso":"eng"}]},{"publication":"Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing","citation":{"mla":"Chatterjee, Krishnendu, et al. “Fully Automated Selfish Mining Analysis in Efficient Proof Systems Blockchains.” <i>Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2024, pp. 268–78, doi:<a href=\"https://doi.org/10.1145/3662158.3662769\">10.1145/3662158.3662769</a>.","apa":"Chatterjee, K., Ebrahimzadeh, A., Karrabi, M., Pietrzak, K. Z., Yeo, M. X., &#38; Zikelic, D. (2024). Fully automated selfish mining analysis in efficient proof systems blockchains. In <i>Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing</i> (pp. 268–278). Nantes, France: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3662158.3662769\">https://doi.org/10.1145/3662158.3662769</a>","short":"K. Chatterjee, A. Ebrahimzadeh, M. Karrabi, K.Z. Pietrzak, M.X. Yeo, D. Zikelic, in:, Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2024, pp. 268–278.","ama":"Chatterjee K, Ebrahimzadeh A, Karrabi M, Pietrzak KZ, Yeo MX, Zikelic D. Fully automated selfish mining analysis in efficient proof systems blockchains. In: <i>Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2024:268-278. doi:<a href=\"https://doi.org/10.1145/3662158.3662769\">10.1145/3662158.3662769</a>","ista":"Chatterjee K, Ebrahimzadeh A, Karrabi M, Pietrzak KZ, Yeo MX, Zikelic D. 2024. Fully automated selfish mining analysis in efficient proof systems blockchains. Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 268–278.","ieee":"K. Chatterjee, A. Ebrahimzadeh, M. Karrabi, K. Z. Pietrzak, M. X. Yeo, and D. Zikelic, “Fully automated selfish mining analysis in efficient proof systems blockchains,” in <i>Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing</i>, Nantes, France, 2024, pp. 268–278.","chicago":"Chatterjee, Krishnendu, Amirali Ebrahimzadeh, Mehrdad Karrabi, Krzysztof Z Pietrzak, Michelle X Yeo, and Dorde Zikelic. “Fully Automated Selfish Mining Analysis in Efficient Proof Systems Blockchains.” In <i>Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing</i>, 268–78. Association for Computing Machinery, 2024. <a href=\"https://doi.org/10.1145/3662158.3662769\">https://doi.org/10.1145/3662158.3662769</a>."},"corr_author":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","language":[{"iso":"eng"}],"external_id":{"arxiv":["2405.04420"]},"abstract":[{"text":"We study selfish mining attacks in longest-chain blockchains like Bitcoin, but where the proof of work is replaced with efficient proof systems - like proofs of stake or proofs of space - and consider the problem of computing an optimal selfish mining attack which maximizes expected relative revenue of the adversary, thus minimizing the chain quality. To this end, we propose a novel selfish mining attack that aims to maximize this objective and formally model the attack as a Markov decision process (MDP). We then present a formal analysis procedure which computes an ϵ-tight lower bound on the optimal expected relative revenue in the MDP and a strategy that achieves this ϵ-tight lower bound, where ϵ > 0 may be any specified precision. Our analysis is fully automated and provides formal guarantees on the correctness. We evaluate our selfish mining attack and observe that it achieves superior expected relative revenue compared to two considered baselines.\r\nIn concurrent work [Sarenche FC'24] does an automated analysis on selfish mining in predictable longest-chain blockchains based on efficient proof systems. Predictable means the randomness for the challenges is fixed for many blocks (as used e.g., in Ouroboros), while we consider unpredictable (Bitcoin-like) chains where the challenge is derived from the previous block.","lang":"eng"}],"author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"last_name":"Ebrahimzadeh","first_name":"Amirali","full_name":"Ebrahimzadeh, Amirali"},{"orcid":"0009-0007-5253-9170","id":"67638922-f394-11eb-9cf6-f20423e08757","full_name":"Karrabi, Mehrdad","first_name":"Mehrdad","last_name":"Karrabi"},{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak"},{"full_name":"Yeo, Michelle X","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0001-3676-4809","last_name":"Yeo"},{"first_name":"Dorde","full_name":"Zikelic, Dorde","orcid":"0000-0002-4681-1699","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","last_name":"Zikelic"}],"file_date_updated":"2024-07-29T07:18:12Z","publication_identifier":{"isbn":["9798400706684"]},"oa_version":"Published Version","publication_status":"published","doi":"10.1145/3662158.3662769","date_created":"2024-07-28T22:01:10Z","article_processing_charge":"Yes (via OA deal)","_id":"17328","supplementarymaterial":"no","publisher":"Association for Computing Machinery","title":"Fully automated selfish mining analysis in efficient proof systems blockchains","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"month":"06","oa":1,"date_published":"2024-06-17T00:00:00Z","das_tickbox":"0","arxiv":1,"year":"2024","file":[{"date_updated":"2024-07-29T07:18:12Z","content_type":"application/pdf","relation":"main_file","file_name":"2024_ACM_Chatterjee.pdf","creator":"dernst","success":1,"file_size":832034,"access_level":"open_access","date_created":"2024-07-29T07:18:12Z","file_id":"17334","checksum":"6122bd97b42751ff81c452a19970f67d"}],"department":[{"_id":"KrCh"},{"_id":"KrPi"}],"acknowledgement":"This work was supported in part by the ERC-2020-CoG 863818 (FoRM-SMArt) grant and the MOE-T2EP20122-0014 (Data-Driven Distributed Algorithms) grant.\r\n","quality_controlled":"1","conference":{"name":"PODC: Symposium on Principles of Distributed Computing","start_date":"2024-06-17","location":"Nantes, France","end_date":"2024-06-21"},"researchdata_availability":"no","day":"17","date_updated":"2026-10-16T08:09:09Z","fulldoi":"https://doi.org/10.1145/3662158.3662769","scopus_import":"1","ddc":["000"],"type":"conference","status":"public","has_accepted_license":"1","project":[{"call_identifier":"H2020","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"ec_funded":1,"page":"268-278"},{"volume":286,"month":"01","date_published":"2024-01-18T00:00:00Z","das_tickbox":"0","oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"title":"Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks","supplementarymaterial":"no","_id":"15007","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa_version":"Published Version","publication_identifier":{"isbn":["9783959773089"],"issn":["1868-8969"]},"date_created":"2024-02-18T23:01:02Z","publication_status":"published","article_processing_charge":"No","doi":"10.4230/LIPIcs.OPODIS.2023.12","author":[{"first_name":"Orestis","full_name":"Alpos, Orestis","last_name":"Alpos"},{"full_name":"Amores-Sesar, Ignacio","first_name":"Ignacio","last_name":"Amores-Sesar"},{"last_name":"Cachin","full_name":"Cachin, Christian","first_name":"Christian"},{"last_name":"Yeo","orcid":"0009-0001-3676-4809","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","full_name":"Yeo, Michelle X","first_name":"Michelle X"}],"abstract":[{"lang":"eng","text":"Traditional blockchains grant the miner of a block full control not only over which transactions but also their order. This constitutes a major flaw discovered with the introduction of decentralized finance and allows miners to perform MEV attacks. In this paper, we address the issue of sandwich attacks by providing a construction that takes as input a blockchain protocol and outputs a new blockchain protocol with the same security but in which sandwich attacks are not profitable. Furthermore, our protocol is fully decentralized with no trusted third parties or heavy cryptography primitives and carries a linear increase in latency and minimum computation overhead."}],"external_id":{"arxiv":["2307.02954"],"isi":["001585185800012"]},"article_number":"12","file_date_updated":"2024-02-26T10:16:57Z","corr_author":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"language":[{"iso":"eng"}],"intvolume":"       286","citation":{"mla":"Alpos, Orestis, et al. “Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks.” <i>27th International Conference on Principles of Distributed Systems</i>, vol. 286, 12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">10.4230/LIPIcs.OPODIS.2023.12</a>.","apa":"Alpos, O., Amores-Sesar, I., Cachin, C., &#38; Yeo, M. X. (2024). Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. In <i>27th International Conference on Principles of Distributed Systems</i> (Vol. 286). Tokyo, Japan: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.12</a>","chicago":"Alpos, Orestis, Ignacio Amores-Sesar, Christian Cachin, and Michelle X Yeo. “Eating Sandwiches: Modular and Lightweight Elimination of Transaction Reordering Attacks.” In <i>27th International Conference on Principles of Distributed Systems</i>, Vol. 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">https://doi.org/10.4230/LIPIcs.OPODIS.2023.12</a>.","ista":"Alpos O, Amores-Sesar I, Cachin C, Yeo MX. 2024. Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. 27th International Conference on Principles of Distributed Systems. OPODIS: Conference on Principles of Distributed Systems, LIPIcs, vol. 286, 12.","ieee":"O. Alpos, I. Amores-Sesar, C. Cachin, and M. X. Yeo, “Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks,” in <i>27th International Conference on Principles of Distributed Systems</i>, Tokyo, Japan, 2024, vol. 286.","ama":"Alpos O, Amores-Sesar I, Cachin C, Yeo MX. Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks. In: <i>27th International Conference on Principles of Distributed Systems</i>. Vol 286. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12\">10.4230/LIPIcs.OPODIS.2023.12</a>","short":"O. Alpos, I. Amores-Sesar, C. Cachin, M.X. Yeo, in:, 27th International Conference on Principles of Distributed Systems, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024."},"publication":"27th International Conference on Principles of Distributed Systems","alternative_title":["LIPIcs"],"type":"conference","has_accepted_license":"1","status":"public","scopus_import":"1","ddc":["000"],"fulldoi":"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12","day":"18","date_updated":"2026-10-16T08:10:21Z","researchdata_availability":"no","conference":{"end_date":"2023-12-08","location":"Tokyo, Japan","start_date":"2023-12-06","name":"OPODIS: Conference on Principles of Distributed Systems"},"quality_controlled":"1","acknowledgement":"We would like to thank Krzysztof Pietrzak and Jovana Mićić for useful discussions. This work has been funded by the Swiss National Science Foundation (SNSF) under grant agreement Nr. 200021_188443 (Advanced Consensus Protocols).\r\n","file":[{"file_size":1505994,"date_created":"2024-02-26T10:16:57Z","file_id":"15031","access_level":"open_access","checksum":"2993e810a45e8c8056106834b07aea92","success":1,"content_type":"application/pdf","relation":"main_file","file_name":"2024_LIPICs_Alpos.pdf","creator":"dernst","date_updated":"2024-02-26T10:16:57Z"}],"year":"2024","department":[{"_id":"KrPi"}],"arxiv":1},{"alternative_title":["LNCS"],"project":[{"_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1","grant_number":"F8509","name":"Security and Privacy by Design for Complex Systems"}],"page":"315-344","type":"conference","status":"public","scopus_import":"1","date_updated":"2026-10-16T08:09:46Z","day":"01","fulldoi":"https://doi.org/10.1007/978-3-031-58734-4_11","quality_controlled":"1","conference":{"end_date":"2024-05-30","location":"Zurich, Switzerland","start_date":"2024-05-26","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques"},"researchdata_availability":"no","acknowledgement":"We thank the Eurocrypt reviewers for their thorough review and for pointing out related works. This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/F85.","year":"2024","department":[{"_id":"KrPi"}],"volume":14653,"month":"05","oa":1,"date_published":"2024-05-01T00:00:00Z","das_tickbox":"0","main_file_link":[{"url":"https://eprint.iacr.org/2024/312","open_access":"1"}],"title":"Trapdoor memory-hard functions","supplementarymaterial":"no","_id":"17051","publisher":"Springer Nature","publication_identifier":{"eissn":["1611-3349"],"isbn":["9783031587337"],"issn":["0302-9743"]},"oa_version":"Preprint","doi":"10.1007/978-3-031-58734-4_11","date_created":"2024-05-26T22:00:58Z","article_processing_charge":"No","publication_status":"published","external_id":{"isi":["001274940200011"]},"abstract":[{"lang":"eng","text":"Memory-hard functions (MHF) are functions whose evaluation provably requires\r\na lot of memory. While MHFs are an unkeyed primitive, it is natural to consider the\r\nnotion of trapdoor MHFs (TMHFs). A TMHF is like an MHF, but when sampling\r\nthe public parameters one also samples a trapdoor which allows evaluating the\r\nfunction much cheaper.\r\nBiryukov and Perrin (Asiacrypt’17) were the first to consider TMHFs and put\r\nforth a candidate TMHF construction called Diodon that is based on the Scrypt\r\nMHF (Percival, BSDCan’09). To allow for a trapdoor, Scrypt’s initial hash chain\r\nis replaced by a sequence of squares in a group of unknown order where the order of\r\nthe group is the trapdoor. For a length n sequence of squares and a group of order\r\nN, Diodon’s cumulative memory complexity (CMC) is O(n2log N) without the\r\ntrapdoor and O(n log(n) log(N)2) with knowledge of it.\r\nWhile Scrypt is proven to be optimally memory-hard in the random oracle\r\nmodel (Alwen et al., Eurocrypt’17), Diodon’s memory-hardness has not been\r\nproven so far. In this work, we fill this gap by rigorously analyzing a specific\r\ninstantiation of Diodon. We show that its CMC is lower bounded by Ω( n2log nlog N)\r\nwhich almost matches the upper bound. Our proof is based Alwen et al.’s lower\r\nbound on Scrypt’s CMC but requires non-trivial modifications due to the algebraic\r\nstructure of Diodon. Most importantly, our analysis involves a more elaborate\r\ncompression argument and a solvability criterion for certain systems of Diophantine\r\nequations."}],"author":[{"orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","first_name":"Benedikt","full_name":"Auerbach, Benedikt","last_name":"Auerbach"},{"last_name":"Günther","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1","full_name":"Günther, Christoph Ullrich","first_name":"Christoph Ullrich"},{"last_name":"Pietrzak","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"isi":1,"corr_author":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","language":[{"iso":"eng"}],"publication":"43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques","intvolume":"     14653","citation":{"mla":"Auerbach, Benedikt, et al. “Trapdoor Memory-Hard Functions.” <i>43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques</i>, vol. 14653, Springer Nature, 2024, pp. 315–44, doi:<a href=\"https://doi.org/10.1007/978-3-031-58734-4_11\">10.1007/978-3-031-58734-4_11</a>.","apa":"Auerbach, B., Günther, C. U., &#38; Pietrzak, K. Z. (2024). Trapdoor memory-hard functions. In <i>43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques</i> (Vol. 14653, pp. 315–344). Zurich, Switzerland: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-58734-4_11\">https://doi.org/10.1007/978-3-031-58734-4_11</a>","ama":"Auerbach B, Günther CU, Pietrzak KZ. Trapdoor memory-hard functions. In: <i>43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques</i>. Vol 14653. Springer Nature; 2024:315-344. doi:<a href=\"https://doi.org/10.1007/978-3-031-58734-4_11\">10.1007/978-3-031-58734-4_11</a>","short":"B. Auerbach, C.U. Günther, K.Z. Pietrzak, in:, 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer Nature, 2024, pp. 315–344.","ieee":"B. Auerbach, C. U. Günther, and K. Z. Pietrzak, “Trapdoor memory-hard functions,” in <i>43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques</i>, Zurich, Switzerland, 2024, vol. 14653, pp. 315–344.","chicago":"Auerbach, Benedikt, Christoph Ullrich Günther, and Krzysztof Z Pietrzak. “Trapdoor Memory-Hard Functions.” In <i>43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques</i>, 14653:315–44. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-58734-4_11\">https://doi.org/10.1007/978-3-031-58734-4_11</a>.","ista":"Auerbach B, Günther CU, Pietrzak KZ. 2024. Trapdoor memory-hard functions. 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 14653, 315–344."}},{"_id":"17283","supplementarymaterial":"no","publisher":"Association for Computing Machinery","article_type":"original","title":"Equivalence and similarity refutation for probabilistic programs","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"month":"06","volume":8,"OA_place":"publisher","das_tickbox":"0","date_published":"2024-06-20T00:00:00Z","oa":1,"intvolume":"         8","citation":{"apa":"Chatterjee, K., Goharshady, E., Novotný, P., &#38; Zikelic, D. (2024). Equivalence and similarity refutation for probabilistic programs. <i>Proceedings of the ACM on Programming Languages</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3656462\">https://doi.org/10.1145/3656462</a>","mla":"Chatterjee, Krishnendu, et al. “Equivalence and Similarity Refutation for Probabilistic Programs.” <i>Proceedings of the ACM on Programming Languages</i>, vol. 8, 232, Association for Computing Machinery, 2024, doi:<a href=\"https://doi.org/10.1145/3656462\">10.1145/3656462</a>.","chicago":"Chatterjee, Krishnendu, Ehsan Goharshady, Petr Novotný, and Dorde Zikelic. “Equivalence and Similarity Refutation for Probabilistic Programs.” <i>Proceedings of the ACM on Programming Languages</i>. Association for Computing Machinery, 2024. <a href=\"https://doi.org/10.1145/3656462\">https://doi.org/10.1145/3656462</a>.","ista":"Chatterjee K, Goharshady E, Novotný P, Zikelic D. 2024. Equivalence and similarity refutation for probabilistic programs. Proceedings of the ACM on Programming Languages. 8, 232.","ieee":"K. Chatterjee, E. Goharshady, P. Novotný, and D. Zikelic, “Equivalence and similarity refutation for probabilistic programs,” <i>Proceedings of the ACM on Programming Languages</i>, vol. 8. Association for Computing Machinery, 2024.","short":"K. Chatterjee, E. Goharshady, P. Novotný, D. Zikelic, Proceedings of the ACM on Programming Languages 8 (2024).","ama":"Chatterjee K, Goharshady E, Novotný P, Zikelic D. Equivalence and similarity refutation for probabilistic programs. <i>Proceedings of the ACM on Programming Languages</i>. 2024;8. doi:<a href=\"https://doi.org/10.1145/3656462\">10.1145/3656462</a>"},"publication":"Proceedings of the ACM on Programming Languages","corr_author":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","language":[{"iso":"eng"}],"abstract":[{"text":"We consider the problems of statically refuting equivalence and similarity of output distributions defined by a pair of probabilistic programs. Equivalence and similarity are two fundamental relational properties of probabilistic programs that are essential for their correctness both in implementation and in compilation. In this work, we present a new method for static equivalence and similarity refutation. Our method refutes equivalence and similarity by computing a function over program outputs whose expected value with respect to the output distributions of two programs is different. The function is computed simultaneously with an upper expectation supermartingale and a lower expectation submartingale for the two programs, which we show to together provide a formal certificate for refuting equivalence and similarity. To the best of our knowledge, our method is the first approach to relational program analysis to offer the combination of the following desirable features: (1) it is fully automated, (2) it is applicable to infinite-state probabilistic programs, and (3) it provides formal guarantees on the correctness of its results. We implement a prototype of our method and our experiments demonstrate the effectiveness of our method to refute equivalence and similarity for a number of examples collected from the literature.","lang":"eng"}],"author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"last_name":"Kafshdar Goharshadi","id":"103b4fa0-896a-11ed-bdf8-87b697bef40d","orcid":"0000-0002-8595-0587","full_name":"Kafshdar Goharshadi, Ehsan","first_name":"Ehsan"},{"full_name":"Novotný, Petr","first_name":"Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","last_name":"Novotný"},{"full_name":"Zikelic, Dorde","first_name":"Dorde","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4681-1699","last_name":"Zikelic"}],"external_id":{"arxiv":["2404.03430"]},"article_number":"232","file_date_updated":"2024-07-22T07:17:14Z","publication_identifier":{"eissn":["2475-1421"]},"oa_version":"Published Version","date_created":"2024-07-21T22:01:01Z","doi":"10.1145/3656462","publication_status":"published","article_processing_charge":"Yes (via OA deal)","fulldoi":"https://doi.org/10.1145/3656462","date_updated":"2026-10-16T08:08:51Z","day":"20","scopus_import":"1","ddc":["000"],"type":"journal_article","has_accepted_license":"1","status":"public","ec_funded":1,"project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"arxiv":1,"file":[{"creator":"dernst","relation":"main_file","file_name":"2024_ACMProgLang_Chatterjee.pdf","content_type":"application/pdf","date_updated":"2024-07-22T07:17:14Z","checksum":"8cbf220f284a4a87d093db5320c5afdd","file_id":"17290","date_created":"2024-07-22T07:17:14Z","access_level":"open_access","file_size":355421,"success":1}],"year":"2024","department":[{"_id":"KrCh"},{"_id":"GradSch"}],"acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant. Petr Novotný\r\nis supported by the Czech Science Foundation grant no. GA23-06963S.\r\n","OA_type":"hybrid","researchdata_availability":"no","quality_controlled":"1"},{"keyword":["General Computer Science","Theoretical Computer Science"],"researchdata_availability":"no","quality_controlled":"1","acknowledgement":"We thank Mahsa Bastankhah and Mohammad Ali Maddah-Ali for fruitful discussions about different variants of the problem. This work is supported by the European Research Council (ERC) Consolidator Project 864228 (AdjustNet), 2020-2025, the ERC CoG 863818 (ForM-SMArt), and the German Research Foundation (DFG) grant 470029389 (FlexNets), 2021-2024.","department":[{"_id":"KrCh"},{"_id":"KrPi"}],"file":[{"date_updated":"2024-07-16T12:02:25Z","content_type":"application/pdf","file_name":"2024_TheorComputerScience_Schmid.pdf","relation":"main_file","creator":"dernst","success":1,"file_size":603570,"date_created":"2024-07-16T12:02:25Z","file_id":"17263","access_level":"open_access","checksum":"efd5b7e738bf845312ba53889a3e13e4"}],"year":"2024","ec_funded":1,"project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020"}],"has_accepted_license":"1","status":"public","type":"journal_article","ddc":["000"],"scopus_import":"1","fulldoi":"https://doi.org/10.1016/j.tcs.2023.114353","day":"21","date_updated":"2026-10-16T08:09:27Z","publication_status":"published","article_processing_charge":"Yes (via OA deal)","doi":"10.1016/j.tcs.2023.114353","date_created":"2024-01-16T13:40:41Z","publication_identifier":{"issn":["0304-3975"]},"oa_version":"Published Version","article_number":"114353","file_date_updated":"2024-07-16T12:02:25Z","author":[{"last_name":"Schmid","first_name":"Stefan","full_name":"Schmid, Stefan"},{"first_name":"Jakub","full_name":"Svoboda, Jakub","orcid":"0000-0002-1419-3267","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","last_name":"Svoboda"},{"last_name":"Yeo","full_name":"Yeo, Michelle X","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0001-3676-4809"}],"abstract":[{"lang":"eng","text":"We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link (u, v) is determined by how many nodes u and v allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given (u, v) and a packet of weight x going from u to v, node u can either accept or reject the packet. If u accepts the packet, the capacity on link (u, v) decreases by x. Correspondingly, v's capacity on \r\n increases by x. If a node rejects the packet, this will entail a cost affinely linear in the weight of the packet. A link is “rechargeable” in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on the nodes' decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of (1+E) . (1+3)  for some arbitrary E>0."}],"external_id":{"isi":["001168211400001"]},"related_material":{"record":[{"id":"19985","status":"public","relation":"earlier_version"}]},"language":[{"iso":"eng"}],"corr_author":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"citation":{"apa":"Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2024). Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">https://doi.org/10.1016/j.tcs.2023.114353</a>","mla":"Schmid, Stefan, et al. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” <i>Theoretical Computer Science</i>, vol. 989, 114353, Elsevier, 2024, doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">10.1016/j.tcs.2023.114353</a>.","ista":"Schmid S, Svoboda J, Yeo MX. 2024. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. Theoretical Computer Science. 989, 114353.","chicago":"Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” <i>Theoretical Computer Science</i>. Elsevier, 2024. <a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">https://doi.org/10.1016/j.tcs.2023.114353</a>.","ieee":"S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation,” <i>Theoretical Computer Science</i>, vol. 989. Elsevier, 2024.","short":"S. Schmid, J. Svoboda, M.X. Yeo, Theoretical Computer Science 989 (2024).","ama":"Schmid S, Svoboda J, Yeo MX. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. <i>Theoretical Computer Science</i>. 2024;989. doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">10.1016/j.tcs.2023.114353</a>"},"intvolume":"       989","publication":"Theoretical Computer Science","date_published":"2024-03-21T00:00:00Z","das_tickbox":"0","oa":1,"month":"03","volume":989,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"title":"Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation","article_type":"original","publisher":"Elsevier","_id":"14820","supplementarymaterial":"no"},{"publication":"Advances in Cryptology – EUROCRYPT 2024","intvolume":"     14652","citation":{"apa":"Tairi, E., &#38; Ünal, A. (2024). Lower bounds for lattice-based compact functional encryption. In <i>Advances in Cryptology – EUROCRYPT 2024</i> (Vol. 14652, pp. 249–279). Zurich, Switzerland: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-58723-8_9\">https://doi.org/10.1007/978-3-031-58723-8_9</a>","mla":"Tairi, Erkan, and Akin Ünal. “Lower Bounds for Lattice-Based Compact Functional Encryption.” <i>Advances in Cryptology – EUROCRYPT 2024</i>, vol. 14652, Springer Nature, 2024, pp. 249–79, doi:<a href=\"https://doi.org/10.1007/978-3-031-58723-8_9\">10.1007/978-3-031-58723-8_9</a>.","ista":"Tairi E, Ünal A. 2024. Lower bounds for lattice-based compact functional encryption. Advances in Cryptology – EUROCRYPT 2024. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 14652, 249–279.","chicago":"Tairi, Erkan, and Akin Ünal. “Lower Bounds for Lattice-Based Compact Functional Encryption.” In <i>Advances in Cryptology – EUROCRYPT 2024</i>, 14652:249–79. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-58723-8_9\">https://doi.org/10.1007/978-3-031-58723-8_9</a>.","ieee":"E. Tairi and A. Ünal, “Lower bounds for lattice-based compact functional encryption,” in <i>Advances in Cryptology – EUROCRYPT 2024</i>, Zurich, Switzerland, 2024, vol. 14652, pp. 249–279.","ama":"Tairi E, Ünal A. Lower bounds for lattice-based compact functional encryption. In: <i>Advances in Cryptology – EUROCRYPT 2024</i>. Vol 14652. Springer Nature; 2024:249-279. doi:<a href=\"https://doi.org/10.1007/978-3-031-58723-8_9\">10.1007/978-3-031-58723-8_9</a>","short":"E. Tairi, A. Ünal, in:, Advances in Cryptology – EUROCRYPT 2024, Springer Nature, 2024, pp. 249–279."},"isi":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","language":[{"iso":"eng"}],"external_id":{"isi":["001278247600009"]},"abstract":[{"text":"Functional encryption (FE) is a primitive where the holder of a master secret key can control which functions a user can evaluate on encrypted data. It is a powerful primitive that even implies indistinguishability obfuscation (iO), given sufficiently compact ciphertexts (Ananth-Jain, CRYPTO’15 and Bitansky-Vaikuntanathan, FOCS’15). However, despite being extensively studied, there are FE schemes, such as function-hiding inner-product FE (Bishop-Jain-Kowalczyk, AC’15, Abdalla-Catalano-Fiore-Gay-Ursu, CRYPTO’18) and compact quadratic FE (Baltico-Catalano-Fiore-Gay, Lin, CRYPTO’17), that can be only realized using pairings. This raises the question if there are some mathematical barriers that hinder us from realizing these FE schemes from other assumptions.\r\n\r\nIn this paper, we study the difficulty of constructing lattice-based compact FE. We generalize the impossibility results of Ünal (EC’20) for lattice-based function-hiding FE, and extend it to the case of compact FE. Concretely, we prove lower bounds for lattice-based compact FE schemes which meet some (natural) algebraic restrictions at encryption and decryption, and have ciphertexts of linear size and secret keys of minimal degree. We see our results as important indications of why it is hard to construct lattice-based FE schemes for new functionalities, and which mathematical barriers have to be overcome.","lang":"eng"}],"author":[{"last_name":"Tairi","full_name":"Tairi, Erkan","first_name":"Erkan"},{"last_name":"Ünal","full_name":"Ünal, Akin","first_name":"Akin","id":"f6b56fb6-dc63-11ee-9dbf-f6780863a85a","orcid":"0000-0002-8929-0221"}],"publication_identifier":{"issn":["0302-9743"],"isbn":["9783031587221"],"eissn":["1611-3349"]},"oa_version":"Submitted Version","publication_status":"published","date_created":"2024-06-09T22:01:03Z","article_processing_charge":"No","doi":"10.1007/978-3-031-58723-8_9","supplementarymaterial":"no","_id":"17126","publisher":"Springer Nature","main_file_link":[{"url":"https://eprint.iacr.org/2023/719.pdf","open_access":"1"}],"title":"Lower bounds for lattice-based compact functional encryption","volume":14652,"month":"05","oa":1,"das_tickbox":"0","date_published":"2024-05-08T00:00:00Z","year":"2024","department":[{"_id":"KrPi"}],"acknowledgement":"We want to thank the anonymous reviewers of TCC and Eurocrypt for their very helpful comments and suggestions. This work has received funding from the Austrian Science Fund (FWF) and netidee SCIENCE via grant P31621-N38 (PROFET).","quality_controlled":"1","researchdata_availability":"no","conference":{"name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","start_date":"2024-05-26","location":"Zurich, Switzerland","end_date":"2024-05-30"},"day":"08","date_updated":"2026-10-16T08:10:05Z","fulldoi":"https://doi.org/10.1007/978-3-031-58723-8_9","scopus_import":"1","type":"conference","status":"public","alternative_title":["LNCS"],"page":"249-279"},{"intvolume":"     15486","citation":{"ista":"Ebrahimi E, Yadav A. 2024. Strongly secure universal thresholdizer. 30th International Conference on the Theory and Application of Cryptology and Information Security. ASIACRYPT: Conference on the Theory and Application of Cryptology and Information Security vol. 15486, 207–239.","ieee":"E. Ebrahimi and A. Yadav, “Strongly secure universal thresholdizer,” in <i>30th International Conference on the Theory and Application of Cryptology and Information Security</i>, Kolkata, India, 2024, vol. 15486, pp. 207–239.","chicago":"Ebrahimi, Ehsan, and Anshu Yadav. “Strongly Secure Universal Thresholdizer.” In <i>30th International Conference on the Theory and Application of Cryptology and Information Security</i>, 15486:207–39. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-981-96-0891-1_7\">https://doi.org/10.1007/978-981-96-0891-1_7</a>.","ama":"Ebrahimi E, Yadav A. Strongly secure universal thresholdizer. In: <i>30th International Conference on the Theory and Application of Cryptology and Information Security</i>. Vol 15486. Springer Nature; 2024:207-239. doi:<a href=\"https://doi.org/10.1007/978-981-96-0891-1_7\">10.1007/978-981-96-0891-1_7</a>","short":"E. Ebrahimi, A. Yadav, in:, 30th International Conference on the Theory and Application of Cryptology and Information Security, Springer Nature, 2024, pp. 207–239.","mla":"Ebrahimi, Ehsan, and Anshu Yadav. “Strongly Secure Universal Thresholdizer.” <i>30th International Conference on the Theory and Application of Cryptology and Information Security</i>, vol. 15486, Springer Nature, 2024, pp. 207–39, doi:<a href=\"https://doi.org/10.1007/978-981-96-0891-1_7\">10.1007/978-981-96-0891-1_7</a>.","apa":"Ebrahimi, E., &#38; Yadav, A. (2024). Strongly secure universal thresholdizer. In <i>30th International Conference on the Theory and Application of Cryptology and Information Security</i> (Vol. 15486, pp. 207–239). Kolkata, India: Springer Nature. <a href=\"https://doi.org/10.1007/978-981-96-0891-1_7\">https://doi.org/10.1007/978-981-96-0891-1_7</a>"},"publication":"30th International Conference on the Theory and Application of Cryptology and Information Security","language":[{"iso":"eng"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"abstract":[{"lang":"eng","text":"A universalthresholdizer (UT), constructed from a threshold fully homomorphic encryption by Boneh et. al , Crypto 2018, is a general framework for universally thresholdizing many cryptographic schemes. However, their framework is insufficient to construct strongly secure threshold schemes, such as threshold signatures and threshold public-key encryption, etc.\r\n\r\nIn this paper, we strengthen the security definition for a universal thresholdizer and propose a scheme which satisfies our stronger security notion. Our UT scheme is an improvement of Boneh et. al ’s construction at the level of threshold fully homomorphic encryption using a key homomorphic pseudorandom function. We apply our strongly secure UT scheme to construct strongly secure threshold signatures and threshold public-key encryption."}],"author":[{"last_name":"Ebrahimi","first_name":"Ehsan","full_name":"Ebrahimi, Ehsan"},{"first_name":"Anshu","full_name":"Yadav, Anshu","id":"dc8f1524-403e-11ee-bf07-9649ad996e21","last_name":"Yadav"}],"external_id":{"isi":["001443889100007"]},"date_created":"2025-01-05T23:01:56Z","doi":"10.1007/978-981-96-0891-1_7","publication_status":"published","article_processing_charge":"No","oa_version":"Preprint","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9789819608904"]},"publisher":"Springer Nature","supplementarymaterial":"no","_id":"18755","title":"Strongly secure universal thresholdizer","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2024/2078"}],"das_tickbox":"0","date_published":"2024-12-12T00:00:00Z","OA_place":"repository","oa":1,"volume":15486,"month":"12","department":[{"_id":"KrPi"}],"year":"2024","acknowledgement":"Ehsan Ebrahimi is supported by the Luxembourg National Research Fund under the Junior CORE project QSP (C22/IS/17272217/QSP/Ebrahimi).","OA_type":"green","researchdata_availability":"no","conference":{"name":"ASIACRYPT: Conference on the Theory and Application of Cryptology and Information Security","start_date":"2024-12-09","location":"Kolkata, India","end_date":"2024-12-13"},"quality_controlled":"1","fulldoi":"https://doi.org/10.1007/978-981-96-0891-1_7","day":"12","date_updated":"2026-10-16T08:10:40Z","scopus_import":"1","status":"public","type":"conference","page":"207-239"},{"quality_controlled":"1","conference":{"end_date":"2024-07-27","location":"Vienna, Austria","name":"ICML: International Conference on Machine Learning","start_date":"2024-07-21"},"researchdata_availability":"no","OA_type":"green","department":[{"_id":"KrCh"}],"year":"2024","page":"47331-47344","alternative_title":["PMLR"],"status":"public","type":"conference","scopus_import":"1","day":"29","date_updated":"2026-10-16T08:08:33Z","date_created":"2025-01-30T07:45:22Z","publication_status":"published","article_processing_charge":"No","oa_version":"Preprint","author":[{"last_name":"Svoboda","full_name":"Svoboda, Jakub","first_name":"Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","orcid":"0000-0002-1419-3267"},{"full_name":"Bansal, Suguman","first_name":"Suguman","last_name":"Bansal"},{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"}],"abstract":[{"text":"Reinforcement Learning (RL) from temporal logical specifications is a fundamental problem in sequential decision making. One of the basic and core such specification is the reachability specification that requires a target set to be eventually visited. Despite strong empirical results for RL from such specifications, the theoretical guarantees are bleak, including the impossibility of Probably Approximately Correct (PAC) guarantee for reachability specifications. Given the impossibility result, in this work we consider the problem of RL from reachability specifications along with the information of expected conditional distance (ECD). We present (a) lower bound results which establish the necessity of ECD information for PAC guarantees and (b) an algorithm that establishes PAC-guarantees given the ECD information. To the best of our knowledge, this is the first RL from reachability specifications that does not make any assumptions on the underlying environment to learn policies.","lang":"eng"}],"language":[{"iso":"eng"}],"corr_author":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication":"41st International Conference on Machine Learning","intvolume":"       235","citation":{"apa":"Svoboda, J., Bansal, S., &#38; Chatterjee, K. (2024). Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance. In <i>41st International Conference on Machine Learning</i> (Vol. 235, pp. 47331–47344). Vienna, Austria: ML Research Press.","mla":"Svoboda, Jakub, et al. “Reinforcement Learning from Reachability Specifications: PAC Guarantees with Expected Conditional Distance.” <i>41st International Conference on Machine Learning</i>, vol. 235, ML Research Press, 2024, pp. 47331–44.","chicago":"Svoboda, Jakub, Suguman Bansal, and Krishnendu Chatterjee. “Reinforcement Learning from Reachability Specifications: PAC Guarantees with Expected Conditional Distance.” In <i>41st International Conference on Machine Learning</i>, 235:47331–44. ML Research Press, 2024.","ista":"Svoboda J, Bansal S, Chatterjee K. 2024. Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance. 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 47331–47344.","ieee":"J. Svoboda, S. Bansal, and K. Chatterjee, “Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance,” in <i>41st International Conference on Machine Learning</i>, Vienna, Austria, 2024, vol. 235, pp. 47331–47344.","ama":"Svoboda J, Bansal S, Chatterjee K. Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance. In: <i>41st International Conference on Machine Learning</i>. Vol 235. ML Research Press; 2024:47331-47344.","short":"J. Svoboda, S. Bansal, K. Chatterjee, in:, 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 47331–47344."},"oa":1,"date_published":"2024-07-29T00:00:00Z","das_tickbox":"0","OA_place":"publisher","volume":235,"month":"07","title":"Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance","main_file_link":[{"url":"https://openreview.net/forum?id=mXUDDL4r1Q","open_access":"1"}],"publisher":"ML Research Press","supplementarymaterial":"no","_id":"18974"},{"ddc":["000"],"day":"18","date_updated":"2026-10-16T08:11:08Z","fulldoi":"https://doi.org/10.15479/at:ista:18088","alternative_title":["ISTA Thesis"],"degree_awarded":"PhD","project":[{"call_identifier":"H2020","grant_number":"665385","name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}],"ec_funded":1,"page":"239","type":"dissertation","license":"https://creativecommons.org/licenses/by-nc-sa/4.0/","status":"public","has_accepted_license":"1","year":"2024","supervisor":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","last_name":"Pietrzak"}],"file":[{"date_updated":"2024-09-19T12:35:38Z","content_type":"application/x-zip-compressed","file_name":"thesis_bundle.zip","relation":"source_file","creator":"gpascual","file_size":11917734,"file_id":"18099","date_created":"2024-09-19T12:35:38Z","access_level":"closed","checksum":"ce0dca715b3df48e52e2e891b6ac1bc5"},{"creator":"gpascual","content_type":"application/pdf","file_name":"thesis_gpasper.pdf","relation":"main_file","date_updated":"2024-09-19T12:36:08Z","date_created":"2024-09-19T12:36:08Z","file_id":"18100","access_level":"open_access","checksum":"4a2c72e90f1a0ef2a13cff800f8d1265","file_size":2729427}],"doi_confirm":"1","department":[{"_id":"KrPi"},{"_id":"GradSch"}],"researchdata_availability":"yes","title":"On the efficiency and security of secure group messaging","supplementarymaterial":"not applicable","_id":"18088","publisher":"Institute of Science and Technology Austria","month":"09","oa":1,"das_tickbox":"1","OA_place":"publisher","date_published":"2024-09-18T00:00:00Z","tmp":{"short":"CC BY-NC-SA (4.0)","image":"/images/cc_by_nc_sa.png","legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)"},"corr_author":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"part_of_dissertation","status":"public","id":"10408"},{"id":"11476","status":"public","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","status":"public","id":"10049"},{"relation":"part_of_dissertation","status":"public","id":"18086"}]},"citation":{"apa":"Pascual Perez, G. (2024). <i>On the efficiency and security of secure group messaging</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:18088\">https://doi.org/10.15479/at:ista:18088</a>","mla":"Pascual Perez, Guillermo. <i>On the Efficiency and Security of Secure Group Messaging</i>. Institute of Science and Technology Austria, 2024, doi:<a href=\"https://doi.org/10.15479/at:ista:18088\">10.15479/at:ista:18088</a>.","ista":"Pascual Perez G. 2024. On the efficiency and security of secure group messaging. Institute of Science and Technology Austria.","ieee":"G. Pascual Perez, “On the efficiency and security of secure group messaging,” Institute of Science and Technology Austria, 2024.","chicago":"Pascual Perez, Guillermo. “On the Efficiency and Security of Secure Group Messaging.” Institute of Science and Technology Austria, 2024. <a href=\"https://doi.org/10.15479/at:ista:18088\">https://doi.org/10.15479/at:ista:18088</a>.","short":"G. Pascual Perez, On the Efficiency and Security of Secure Group Messaging, Institute of Science and Technology Austria, 2024.","ama":"Pascual Perez G. On the efficiency and security of secure group messaging. 2024. doi:<a href=\"https://doi.org/10.15479/at:ista:18088\">10.15479/at:ista:18088</a>"},"oa_version":"Published Version","publication_identifier":{"issn":["2663-337X"]},"date_created":"2024-09-18T12:59:49Z","article_processing_charge":"No","doi":"10.15479/at:ista:18088","publication_status":"published","author":[{"full_name":"Pascual Perez, Guillermo","first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8630-415X","last_name":"Pascual Perez"}],"abstract":[{"lang":"eng","text":"Instant messaging applications like Whatsapp, Signal or Telegram have become ubiquitous in today's society.\r\nMany of them provide not only end-to-end encryption, but also security guarantees even when the key material gets compromised.\r\nThese are achieved through frequent key update performed by users.\r\nIn particular, the compromise of a group key should preserve confidentiality of previously exchanged messages (forward secrecy), and a subsequent key update will ensure security for future ones (post-compromise security).\r\nThough great protocols for one-on-one communication have been known for some time, the design of ones that scale efficiently for larger groups while achieving akin security guarantees is a hard problem.\r\nA great deal of research has been aimed at this topic, much of it under the umbrella of the Messaging Layer Security (MLS) working group at the IETF. \r\nStarted in 2018, this joint effort by academics and industry culminated in 2023 with the publication of the first standard for secure group messaging [IETF, RFC9420].\r\n\r\nAt the core of secure group messaging is a cryptographic primitive termed Continuous Group Key Agreement, or CGKA [Alwen et al. 2021], that essentially allows a changing group of users to agree on a common key with the added functionality security against compromises is achieved by users asynchronously issuing a key update. In this thesis we contribute to the understanding of CGKA across different angles.\r\nFirst, we present a new technique to effect dynamic operations in groups, i.e., add or remove members, that can be more efficient that the one employed by MLS in certain settings.\r\nConsidering the setting of users belonging to multiple overlapping groups, we then show lowerbounds on the communication cost of constructions that leverage said overlap, at the same time showing protocols that are asymptotically optimal and efficient for practical settings, respectively. Along the way, we show that the communication cost of key updates in MLS is average-cost optimal.\r\nAn important feature in CGKA protocols, particularly for big groups, is the possibility of executing several group operations concurrently. While later versions of MLS support this, they do at the cost of worsening the communication efficiency of future group operations.\r\nIn this thesis we introduce two new protocols that permit concurrency without any negative effect on efficiency. Our protocols circumvent previously existing lower bounds by satisfying a new notion of post-compromise security that only asks for security to be re-established after a certain number of key updates have taken place. While this can be slower than MLS in terms of rounds of communication, we show that it leads to more efficient overall communication. \r\nAdditionally, we introduce a new technique that allows group members to decrease the information they need to store and download, which makes one of our protocols enjoy much lower download cost than any other existing CGKA constructions. "}],"file_date_updated":"2024-09-19T12:36:08Z"},{"intvolume":"     14974","citation":{"ama":"Alwen JF, Auerbach B, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ. DeCAF: Decentralizable CGKA with fast healing. In: Galdi C, Phan DH, eds. <i>Security and Cryptography for Networks: 14th International Conference</i>. Vol 14974. Cham: Springer Nature; 2024:294–313. doi:<a href=\"https://doi.org/10.1007/978-3-031-71073-5_14\">10.1007/978-3-031-71073-5_14</a>","short":"J.F. Alwen, B. Auerbach, M. Cueto Noval, K. Klein, G. Pascual Perez, K.Z. Pietrzak, in:, C. Galdi, D.H. Phan (Eds.), Security and Cryptography for Networks: 14th International Conference, Springer Nature, Cham, 2024, pp. 294–313.","chicago":"Alwen, Joel F, Benedikt Auerbach, Miguel Cueto Noval, Karen Klein, Guillermo Pascual Perez, and Krzysztof Z Pietrzak. “DeCAF: Decentralizable CGKA with Fast Healing.” In <i>Security and Cryptography for Networks: 14th International Conference</i>, edited by Clemente Galdi and Duong Hieu Phan, 14974:294–313. Cham: Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-71073-5_14\">https://doi.org/10.1007/978-3-031-71073-5_14</a>.","ieee":"J. F. Alwen, B. Auerbach, M. Cueto Noval, K. Klein, G. Pascual Perez, and K. Z. Pietrzak, “DeCAF: Decentralizable CGKA with fast healing,” in <i>Security and Cryptography for Networks: 14th International Conference</i>, Amalfi, Italy, 2024, vol. 14974, pp. 294–313.","ista":"Alwen JF, Auerbach B, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ. 2024. DeCAF: Decentralizable CGKA with fast healing. Security and Cryptography for Networks: 14th International Conference. SCN: Security and Cryptography for Networks, LNCS, vol. 14974, 294–313.","apa":"Alwen, J. F., Auerbach, B., Cueto Noval, M., Klein, K., Pascual Perez, G., &#38; Pietrzak, K. Z. (2024). DeCAF: Decentralizable CGKA with fast healing. In C. Galdi &#38; D. H. Phan (Eds.), <i>Security and Cryptography for Networks: 14th International Conference</i> (Vol. 14974, pp. 294–313). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-71073-5_14\">https://doi.org/10.1007/978-3-031-71073-5_14</a>","mla":"Alwen, Joel F., et al. “DeCAF: Decentralizable CGKA with Fast Healing.” <i>Security and Cryptography for Networks: 14th International Conference</i>, edited by Clemente Galdi and Duong Hieu Phan, vol. 14974, Springer Nature, 2024, pp. 294–313, doi:<a href=\"https://doi.org/10.1007/978-3-031-71073-5_14\">10.1007/978-3-031-71073-5_14</a>."},"publication":"Security and Cryptography for Networks: 14th International Conference","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"18088"}]},"language":[{"iso":"eng"}],"corr_author":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","isi":1,"author":[{"last_name":"Alwen","first_name":"Joel F","full_name":"Alwen, Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Auerbach, Benedikt","first_name":"Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","orcid":"0000-0002-7553-6606","last_name":"Auerbach"},{"id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","orcid":"0000-0002-2505-4246","first_name":"Miguel","full_name":"Cueto Noval, Miguel","last_name":"Cueto Noval"},{"last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","full_name":"Klein, Karen","first_name":"Karen"},{"last_name":"Pascual Perez","orcid":"0000-0001-8630-415X","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","first_name":"Guillermo","full_name":"Pascual Perez, Guillermo"},{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak"}],"abstract":[{"text":"Abstract. Continuous group key agreement (CGKA) allows a group of\r\nusers to maintain a continuously updated shared key in an asynchronous\r\nsetting where parties only come online sporadically and their messages\r\nare relayed by an untrusted server. CGKA captures the basic primitive\r\nunderlying group messaging schemes.\r\nCurrent solutions including TreeKEM (“Messaging Layer Security”\r\n(MLS) IETF RFC 9420) cannot handle concurrent requests while retaining low communication complexity. The exception being CoCoA, which\r\nis concurrent while having extremely low communication complexity (in\r\ngroups of size n and for m concurrent updates the communication per\r\nuser is log(n), i.e., independent of m). The main downside of CoCoA\r\nis that in groups of size n, users might have to do up to log(n) update\r\nrequests to the server to ensure their (potentially corrupted) key material has been refreshed.\r\nIn this work we present a “fast healing” concurrent CGKA protocol,\r\nnamed DeCAF, where users will heal after at most log(t) requests, with\r\nt being the number of corrupted users. While also suitable for the standard central-server setting, our protocol is particularly interesting for\r\nrealizing decentralized group messaging, where protocol messages (add,\r\nremove, update) are being posted on some append-only data structure\r\nrather than sent to a server. In this setting, concurrency is crucial once\r\nthe rate of requests exceeds, say, the rate at which new blocks are added\r\nto a blockchain.\r\nIn the central-server setting, CoCoA (the only alternative with concurrency, sub-linear communication and basic post-compromise security)\r\nenjoys much lower download communication. However, in the decentralized setting – where there is no server which can craft specific messages\r\nfor different users to reduce their download communication – our protocol\r\nsignificantly outperforms CoCoA. DeCAF heals in fewer epochs (log(t)\r\nvs. log(n)) while incurring a similar per epoch per user communication\r\ncost.","lang":"eng"}],"external_id":{"isi":["001330408000014"]},"doi":"10.1007/978-3-031-71073-5_14","article_processing_charge":"No","date_created":"2024-09-18T11:35:14Z","publication_status":"published","publication_identifier":{"isbn":["9783031710728"],"eissn":["1611-3349"],"eisbn":["9783031710735"],"issn":["0302-9743"]},"oa_version":"None","publisher":"Springer Nature","supplementarymaterial":"no","_id":"18086","title":"DeCAF: Decentralizable CGKA with fast healing","das_tickbox":"0","date_published":"2024-09-10T00:00:00Z","month":"09","volume":14974,"department":[{"_id":"GradSch"},{"_id":"KrPi"}],"place":"Cham","year":"2024","editor":[{"last_name":"Galdi","full_name":"Galdi, Clemente","first_name":"Clemente"},{"full_name":"Phan, Duong Hieu","first_name":"Duong Hieu","last_name":"Phan"}],"conference":{"location":"Amalfi, Italy","end_date":"2024-09-13","start_date":"2024-09-11","name":"SCN: Security and Cryptography for Networks"},"researchdata_availability":"no","quality_controlled":"1","fulldoi":"https://doi.org/10.1007/978-3-031-71073-5_14","date_updated":"2026-10-16T08:11:07Z","day":"10","status":"public","type":"conference","page":"294–313","alternative_title":["LNCS"]},{"publication":"Proceedings on Privacy Enhancing Technologies","citation":{"ama":"Günther CU, Pietrzak KZ. Deniability in automated contact tracing: Impossibilities and possibilities. <i>Proceedings on Privacy Enhancing Technologies</i>. 2024;2024(4):636-648. doi:<a href=\"https://doi.org/10.56553/popets-2024-0134\">10.56553/popets-2024-0134</a>","short":"C.U. Günther, K.Z. Pietrzak, Proceedings on Privacy Enhancing Technologies 2024 (2024) 636–648.","ieee":"C. U. Günther and K. Z. Pietrzak, “Deniability in automated contact tracing: Impossibilities and possibilities,” <i>Proceedings on Privacy Enhancing Technologies</i>, vol. 2024, no. 4. Privacy Enhancing Technologies Symposium Advisory Board, pp. 636–648, 2024.","chicago":"Günther, Christoph Ullrich, and Krzysztof Z Pietrzak. “Deniability in Automated Contact Tracing: Impossibilities and Possibilities.” <i>Proceedings on Privacy Enhancing Technologies</i>. Privacy Enhancing Technologies Symposium Advisory Board, 2024. <a href=\"https://doi.org/10.56553/popets-2024-0134\">https://doi.org/10.56553/popets-2024-0134</a>.","ista":"Günther CU, Pietrzak KZ. 2024. Deniability in automated contact tracing: Impossibilities and possibilities. Proceedings on Privacy Enhancing Technologies. 2024(4), 636–648.","apa":"Günther, C. U., &#38; Pietrzak, K. Z. (2024). Deniability in automated contact tracing: Impossibilities and possibilities. <i>Proceedings on Privacy Enhancing Technologies</i>. Bristol, UK/Virtual: Privacy Enhancing Technologies Symposium Advisory Board. <a href=\"https://doi.org/10.56553/popets-2024-0134\">https://doi.org/10.56553/popets-2024-0134</a>","mla":"Günther, Christoph Ullrich, and Krzysztof Z. Pietrzak. “Deniability in Automated Contact Tracing: Impossibilities and Possibilities.” <i>Proceedings on Privacy Enhancing Technologies</i>, vol. 2024, no. 4, Privacy Enhancing Technologies Symposium Advisory Board, 2024, pp. 636–48, doi:<a href=\"https://doi.org/10.56553/popets-2024-0134\">10.56553/popets-2024-0134</a>."},"intvolume":"      2024","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","corr_author":"1","language":[{"iso":"eng"}],"author":[{"last_name":"Günther","first_name":"Christoph Ullrich","full_name":"Günther, Christoph Ullrich","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","last_name":"Pietrzak"}],"abstract":[{"text":"Automated contact tracing (ACT) emerged as a promising measure to curb the spread of Covid-19. Users enable ACT on their smartphones to automatically record contacts with other users. If a user tests positive for the disease, they report their diagnosis to alert their contacts.\r\nDesigning effective ACT protocols is challenging since they need to be efficient and secure while also ensuring users' privacy. As ACT protocols necessarily leak some information by design, defining privacy is difficult. For example, a user cannot deny having met another user. Ideally, however, the user can plausibly deny everything else, in particular, when they met. We call this privacy property contact-time deniability.\r\nWhile some early works discussed contact-time deniability informally, it has received little attention since then. We investigate deniability from a rigorous, theoretical point of view and arrive at the following impossibility result:\r\nA decentralized protocol with unidirectional communication cannot be contact-time deniable and replay-secure. This holds even if malicious users treat smartphones as black-boxes.\r\n Unidirectional protocols are usually very efficient and many proposals are unidirectional, e.g., the widely-deployed Google-Apple Exposure Notifications. So the impossibility result considerably constrains the design space of efficient, secure, and private ACT protocols. However, it can also be used as a guide; we discuss several possibilities to achieve contact-time deniability in practice.","lang":"eng"}],"file_date_updated":"2025-01-29T13:44:47Z","publication_identifier":{"issn":["2299-0984"]},"oa_version":"Published Version","doi":"10.56553/popets-2024-0134","date_created":"2025-01-29T13:39:34Z","article_processing_charge":"No","publication_status":"published","_id":"18961","supplementarymaterial":"no","publisher":"Privacy Enhancing Technologies Symposium Advisory Board","article_type":"original","title":"Deniability in automated contact tracing: Impossibilities and possibilities","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"volume":2024,"month":"07","oa":1,"das_tickbox":"0","OA_place":"publisher","date_published":"2024-07-01T00:00:00Z","year":"2024","file":[{"file_id":"18962","date_created":"2025-01-29T13:44:47Z","access_level":"open_access","checksum":"348ed6adcf6ad2f925227bde1758cae6","file_size":611567,"success":1,"creator":"dernst","content_type":"application/pdf","relation":"main_file","file_name":"2024_ProcPrivacyEnhTech_Guenther.pdf","date_updated":"2025-01-29T13:44:47Z"}],"department":[{"_id":"KrPi"},{"_id":"GradSch"}],"acknowledgement":"We thank Raluca-Georgia Diugan for her initial contributions and support afterward.\r\nThis research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/F85.","quality_controlled":"1","OA_type":"gold","researchdata_availability":"no","conference":{"name":"PETs: Privacy Enhancing Technologies Symposium ","start_date":"2024-07-15","end_date":"2024-07-20","location":"Bristol, UK/Virtual"},"date_updated":"2026-10-16T08:29:47Z","day":"01","fulldoi":"https://doi.org/10.56553/popets-2024-0134","ddc":["000"],"type":"journal_article","status":"public","has_accepted_license":"1","project":[{"_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1","grant_number":"F8509","name":"Security and Privacy by Design for Complex Systems"}],"page":"636-648","issue":"4"},{"acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria).","quality_controlled":"1","researchdata_availability":"not applicable","OA_type":"hybrid","arxiv":1,"dataavailabilitystatement":"There is no data associated to this work.","department":[{"_id":"LaEr"}],"year":"2024","file":[{"date_updated":"2024-11-18T08:15:07Z","content_type":"application/pdf","file_name":"2024_CommMathPhysics_Erdoes.pdf","relation":"main_file","creator":"dernst","success":1,"file_size":1426046,"date_created":"2024-11-18T08:15:07Z","file_id":"18562","access_level":"open_access","checksum":"c9ae0ea195bd39b8b3a630d492fb00dc"}],"status":"public","has_accepted_license":"1","type":"journal_article","issue":"12","day":"01","date_updated":"2026-10-16T08:34:30Z","fulldoi":"https://doi.org/10.1007/s00220-024-05143-y","pmid":1,"ddc":["510"],"scopus_import":"1","file_date_updated":"2024-11-18T08:15:07Z","article_number":"282","external_id":{"pmid":["39526190"],"arxiv":["2403.10359"],"isi":["001348943900004"]},"author":[{"last_name":"Erdös","first_name":"László","full_name":"Erdös, László","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5366-9603"},{"id":"1949f904-edfb-11eb-afb5-e2dfddabb93b","full_name":"Riabov, Volodymyr","first_name":"Volodymyr","last_name":"Riabov"}],"abstract":[{"lang":"eng","text":"We prove the Eigenstate Thermalization Hypothesis for general Wigner-type matrices in the bulk of the self-consistent spectrum, with optimal control on the fluctuations for obs ervables of arbitrary rank. As the main technical ingredient, we prove rank-uniform optimal local laws for one and two resolvents of a Wigner-type matrix with regular observables. Our results hold under very general conditions on the variance profile, even allowing many vanishing entries, demonstrating that Eigenstate Thermalization occurs robustly across a diverse class of random matrix ensembles, for which the underlying quantum system has a non-trivial spatial structure."}],"date_created":"2024-11-17T23:01:46Z","doi":"10.1007/s00220-024-05143-y","article_processing_charge":"Yes (via OA deal)","publication_status":"published","publication_identifier":{"eissn":["1432-0916"],"issn":["0010-3616"]},"oa_version":"Published Version","publication":"Communications in Mathematical Physics","citation":{"mla":"Erdös, László, and Volodymyr Riabov. “Eigenstate Thermalization Hypothesis for Wigner-Type Matrices.” <i>Communications in Mathematical Physics</i>, vol. 405, no. 12, 282, Springer Nature, 2024, doi:<a href=\"https://doi.org/10.1007/s00220-024-05143-y\">10.1007/s00220-024-05143-y</a>.","apa":"Erdös, L., &#38; Riabov, V. (2024). Eigenstate Thermalization Hypothesis for Wigner-type matrices. <i>Communications in Mathematical Physics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00220-024-05143-y\">https://doi.org/10.1007/s00220-024-05143-y</a>","ista":"Erdös L, Riabov V. 2024. Eigenstate Thermalization Hypothesis for Wigner-type matrices. Communications in Mathematical Physics. 405(12), 282.","chicago":"Erdös, László, and Volodymyr Riabov. “Eigenstate Thermalization Hypothesis for Wigner-Type Matrices.” <i>Communications in Mathematical Physics</i>. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/s00220-024-05143-y\">https://doi.org/10.1007/s00220-024-05143-y</a>.","ieee":"L. Erdös and V. Riabov, “Eigenstate Thermalization Hypothesis for Wigner-type matrices,” <i>Communications in Mathematical Physics</i>, vol. 405, no. 12. Springer Nature, 2024.","short":"L. Erdös, V. Riabov, Communications in Mathematical Physics 405 (2024).","ama":"Erdös L, Riabov V. Eigenstate Thermalization Hypothesis for Wigner-type matrices. <i>Communications in Mathematical Physics</i>. 2024;405(12). doi:<a href=\"https://doi.org/10.1007/s00220-024-05143-y\">10.1007/s00220-024-05143-y</a>"},"intvolume":"       405","language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"20575"}]},"isi":1,"corr_author":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"oa":1,"OA_place":"publisher","das_tickbox":"1","date_published":"2024-12-01T00:00:00Z","month":"12","volume":405,"publisher":"Springer Nature","_id":"18554","supplementarymaterial":"yes","title":"Eigenstate Thermalization Hypothesis for Wigner-type matrices","article_type":"original"},{"intvolume":"        37","citation":{"ista":"Campbell AJ, O’Rourke S. 2024. Spectrum of Lévy–Khintchine random laplacian matrices. Journal of Theoretical Probability. 37, 933–973.","chicago":"Campbell, Andrew J, and Sean O’Rourke. “Spectrum of Lévy–Khintchine Random Laplacian Matrices.” <i>Journal of Theoretical Probability</i>. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/s10959-023-01275-4\">https://doi.org/10.1007/s10959-023-01275-4</a>.","ieee":"A. J. Campbell and S. O’Rourke, “Spectrum of Lévy–Khintchine random laplacian matrices,” <i>Journal of Theoretical Probability</i>, vol. 37. Springer Nature, pp. 933–973, 2024.","ama":"Campbell AJ, O’Rourke S. Spectrum of Lévy–Khintchine random laplacian matrices. <i>Journal of Theoretical Probability</i>. 2024;37:933-973. doi:<a href=\"https://doi.org/10.1007/s10959-023-01275-4\">10.1007/s10959-023-01275-4</a>","short":"A.J. Campbell, S. O’Rourke, Journal of Theoretical Probability 37 (2024) 933–973.","apa":"Campbell, A. J., &#38; O’Rourke, S. (2024). Spectrum of Lévy–Khintchine random laplacian matrices. <i>Journal of Theoretical Probability</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10959-023-01275-4\">https://doi.org/10.1007/s10959-023-01275-4</a>","mla":"Campbell, Andrew J., and Sean O’Rourke. “Spectrum of Lévy–Khintchine Random Laplacian Matrices.” <i>Journal of Theoretical Probability</i>, vol. 37, Springer Nature, 2024, pp. 933–73, doi:<a href=\"https://doi.org/10.1007/s10959-023-01275-4\">10.1007/s10959-023-01275-4</a>."},"publication":"Journal of Theoretical Probability","language":[{"iso":"eng"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","corr_author":"1","isi":1,"file_date_updated":"2024-07-22T09:41:21Z","abstract":[{"lang":"eng","text":"We consider the spectrum of random Laplacian matrices of the form Ln=An−Dn where An\r\n is a real symmetric random matrix and Dn is a diagonal matrix whose entries are equal to the corresponding row sums of An. If An is a Wigner matrix with entries in the domain of attraction of a Gaussian distribution, the empirical spectral measure of Ln is known to converge to the free convolution of a semicircle distribution and a standard real Gaussian distribution. We consider real symmetric random matrices An with independent entries (up to symmetry) whose row sums converge to a purely non-Gaussian infinitely divisible distribution, which fall into the class of Lévy–Khintchine random matrices first introduced by Jung [Trans Am Math Soc, 370, (2018)]. Our main result shows that the empirical spectral measure of Ln  converges almost surely to a deterministic limit. A key step in the proof is to use the purely non-Gaussian nature of the row sums to build a random operator to which Ln converges in an appropriate sense. This operator leads to a recursive distributional equation uniquely describing the Stieltjes transform of the limiting empirical spectral measure."}],"author":[{"last_name":"Campbell","first_name":"Andrew J","full_name":"Campbell, Andrew J","id":"582b06a9-1f1c-11ee-b076-82ffce00dde4"},{"last_name":"O’Rourke","first_name":"Sean","full_name":"O’Rourke, Sean"}],"external_id":{"arxiv":["2210.07927"],"isi":["001038341000001"]},"article_processing_charge":"Yes (via OA deal)","publication_status":"published","doi":"10.1007/s10959-023-01275-4","date_created":"2023-08-06T22:01:13Z","publication_identifier":{"issn":["0894-9840"],"eissn":["1572-9230"]},"oa_version":"Published Version","publisher":"Springer Nature","supplementarymaterial":"yes","_id":"13975","title":"Spectrum of Lévy–Khintchine random laplacian matrices","article_type":"original","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_published":"2024-03-01T00:00:00Z","das_tickbox":"1","oa":1,"month":"03","volume":37,"arxiv":1,"department":[{"_id":"LaEr"}],"dataavailabilitystatement":"All data generated or analyzed during this study are included in this published article.","file":[{"date_updated":"2024-07-22T09:41:21Z","relation":"main_file","file_name":"2024_JourTheorProbab_Campbell.pdf","content_type":"application/pdf","creator":"dernst","success":1,"file_size":555070,"checksum":"f7793d313104c70422140c5e6494c779","file_id":"17300","access_level":"open_access","date_created":"2024-07-22T09:41:21Z"}],"year":"2024","acknowledgement":"The first author thanks Yizhe Zhu for pointing out reference [30]. We thank David Renfrew for comments on an earlier draft. We thank the anonymous referee for a careful reading and helpful comments.\r\nOpen access funding provided by Institute of Science and Technology (IST Austria).","researchdata_availability":"yes (supplementary data)","quality_controlled":"1","fulldoi":"https://doi.org/10.1007/s10959-023-01275-4","date_updated":"2026-10-16T08:30:34Z","day":"01","ddc":["510"],"scopus_import":"1","has_accepted_license":"1","status":"public","type":"journal_article","page":"933-973"}]