[{"status":"public","OA_place":"other","language":[{"iso":"eng"}],"isi":1,"date_created":"2025-01-27T15:06:45Z","date_updated":"2026-10-16T08:07:55Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"No","conference":{"location":"Seoul, Republic of Korea","end_date":"2024-05-10","start_date":"2024-05-06","name":"NOMS: Network Operations and Management Symposiu "},"citation":{"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 .","short":"E. Ceylan, K. Chatterjee, S. Schmid, J. Svoboda, in:, NOMS 2024-2024 IEEE Network Operations and Management Symposium, IEEE, 2024.","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>.","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>","apa":"Ceylan, E., Chatterjee, K., Schmid, S., &#38; Svoboda, J. (2024). Congestion-free rerouting of network flows: Hardness and an FPT algorithm. In <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>. Seoul, Republic of Korea: IEEE. <a href=\"https://doi.org/10.1109/noms59830.2024.10575579\">https://doi.org/10.1109/noms59830.2024.10575579</a>","ieee":"E. Ceylan, K. Chatterjee, S. Schmid, and J. Svoboda, “Congestion-free rerouting of network flows: Hardness and an FPT algorithm,” in <i>NOMS 2024-2024 IEEE Network Operations and Management Symposium</i>, Seoul, Republic of Korea, 2024."},"oa_version":"Submitted Version","month":"05","publication_status":"published","type":"conference","author":[{"full_name":"Ceylan, Esra","first_name":"Esra","last_name":"Ceylan","id":"cb1ca1d8-dcc0-11ef-baa5-9f1b3ef75933"},{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"},{"last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","orcid":"0000-0002-1419-3267","full_name":"Svoboda, Jakub","first_name":"Jakub"}],"quality_controlled":"1","day":"01","OA_type":"green","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).","fulldoi":"https://doi.org/10.1109/noms59830.2024.10575579","das_tickbox":"0","year":"2024","doi":"10.1109/noms59830.2024.10575579","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","grant_number":"863818"},{"_id":"bd622a5c-d553-11ed-ba76-bae280ba8aff","name":"Graphical Games","grant_number":"894907"}],"abstract":[{"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.","lang":"eng"}],"ec_funded":1,"main_file_link":[{"url":"https://schmiste.github.io/noms24.pdf","open_access":"1"}],"publisher":"IEEE","supplementarymaterial":"no","publication":"NOMS 2024-2024 IEEE Network Operations and Management Symposium","external_id":{"isi":["001270140300143"]},"publication_identifier":{"isbn":["9798350327946"],"eissn":["2374-9709"]},"corr_author":"1","oa":1,"department":[{"_id":"KrCh"}],"_id":"18925","researchdata_availability":"no","scopus_import":"1","title":"Congestion-free rerouting of network flows: Hardness and an FPT algorithm","date_published":"2024-05-01T00:00:00Z"},{"title":"Fully automated selfish mining analysis in efficient proof systems blockchains","scopus_import":"1","researchdata_availability":"no","license":"https://creativecommons.org/licenses/by/4.0/","date_published":"2024-06-17T00:00:00Z","department":[{"_id":"KrCh"},{"_id":"KrPi"}],"oa":1,"corr_author":"1","publication_identifier":{"isbn":["9798400706684"]},"_id":"17328","supplementarymaterial":"no","external_id":{"arxiv":["2405.04420"]},"page":"268-278","publication":"Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed Computing","arxiv":1,"publisher":"Association for Computing Machinery","doi":"10.1145/3662158.3662769","das_tickbox":"0","year":"2024","fulldoi":"https://doi.org/10.1145/3662158.3662769","day":"17","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","ec_funded":1,"abstract":[{"lang":"eng","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."}],"project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","call_identifier":"H2020"}],"author":[{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"last_name":"Ebrahimzadeh","full_name":"Ebrahimzadeh, Amirali","first_name":"Amirali"},{"full_name":"Karrabi, Mehrdad","first_name":"Mehrdad","last_name":"Karrabi","id":"67638922-f394-11eb-9cf6-f20423e08757","orcid":"0009-0007-5253-9170"},{"orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"},{"last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0001-3676-4809","full_name":"Yeo, Michelle X","first_name":"Michelle X"},{"first_name":"Dorde","full_name":"Zikelic, Dorde","orcid":"0000-0002-4681-1699","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","last_name":"Zikelic"}],"type":"conference","publication_status":"published","quality_controlled":"1","file_date_updated":"2024-07-29T07:18:12Z","conference":{"end_date":"2024-06-21","start_date":"2024-06-17","name":"PODC: Symposium on Principles of Distributed Computing","location":"Nantes, France"},"article_processing_charge":"Yes (via OA deal)","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","month":"06","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"oa_version":"Published Version","citation":{"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>","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>","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>.","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>.","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.","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."},"file":[{"success":1,"creator":"dernst","file_name":"2024_ACM_Chatterjee.pdf","date_updated":"2024-07-29T07:18:12Z","date_created":"2024-07-29T07:18:12Z","relation":"main_file","content_type":"application/pdf","checksum":"6122bd97b42751ff81c452a19970f67d","file_id":"17334","access_level":"open_access","file_size":832034}],"date_created":"2024-07-28T22:01:10Z","date_updated":"2026-10-16T08:09:09Z","has_accepted_license":"1","status":"public","language":[{"iso":"eng"}],"ddc":["000"]},{"author":[{"last_name":"Alpos","full_name":"Alpos, Orestis","first_name":"Orestis"},{"last_name":"Amores-Sesar","full_name":"Amores-Sesar, Ignacio","first_name":"Ignacio"},{"last_name":"Cachin","first_name":"Christian","full_name":"Cachin, Christian"},{"full_name":"Yeo, Michelle X","first_name":"Michelle X","orcid":"0009-0001-3676-4809","last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","publication_status":"published","alternative_title":["LIPIcs"],"quality_controlled":"1","file_date_updated":"2024-02-26T10:16:57Z","conference":{"location":"Tokyo, Japan","start_date":"2023-12-06","name":"OPODIS: Conference on Principles of Distributed Systems","end_date":"2023-12-08"},"article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","month":"01","oa_version":"Published Version","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"citation":{"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>.","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>","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.","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.","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>."},"file":[{"content_type":"application/pdf","checksum":"2993e810a45e8c8056106834b07aea92","creator":"dernst","file_name":"2024_LIPICs_Alpos.pdf","success":1,"date_updated":"2024-02-26T10:16:57Z","date_created":"2024-02-26T10:16:57Z","relation":"main_file","file_size":1505994,"access_level":"open_access","file_id":"15031"}],"date_created":"2024-02-18T23:01:02Z","date_updated":"2026-10-16T08:10:21Z","has_accepted_license":"1","status":"public","isi":1,"ddc":["000"],"language":[{"iso":"eng"}],"scopus_import":"1","title":"Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks","article_number":"12","intvolume":"       286","researchdata_availability":"no","date_published":"2024-01-18T00:00:00Z","oa":1,"department":[{"_id":"KrPi"}],"corr_author":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773089"]},"_id":"15007","publication":"27th International Conference on Principles of Distributed Systems","supplementarymaterial":"no","external_id":{"isi":["001585185800012"],"arxiv":["2307.02954"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"year":"2024","doi":"10.4230/LIPIcs.OPODIS.2023.12","das_tickbox":"0","fulldoi":"https://doi.org/10.4230/LIPIcs.OPODIS.2023.12","day":"18","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","abstract":[{"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.","lang":"eng"}],"volume":286},{"status":"public","language":[{"iso":"eng"}],"isi":1,"date_updated":"2026-10-16T08:09:46Z","date_created":"2024-05-26T22:00:58Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"No","conference":{"end_date":"2024-05-30","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","start_date":"2024-05-26","location":"Zurich, Switzerland"},"citation":{"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>","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>","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>.","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>.","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.","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."},"oa_version":"Preprint","month":"05","publication_status":"published","alternative_title":["LNCS"],"type":"conference","author":[{"last_name":"Auerbach","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","orcid":"0000-0002-7553-6606","full_name":"Auerbach, Benedikt","first_name":"Benedikt"},{"first_name":"Christoph Ullrich","full_name":"Günther, Christoph Ullrich","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1","last_name":"Günther"},{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654"}],"quality_controlled":"1","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.","day":"01","fulldoi":"https://doi.org/10.1007/978-3-031-58734-4_11","doi":"10.1007/978-3-031-58734-4_11","das_tickbox":"0","year":"2024","project":[{"name":"Security and Privacy by Design for Complex Systems","_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1","grant_number":"F8509"}],"volume":14653,"abstract":[{"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.","lang":"eng"}],"main_file_link":[{"url":"https://eprint.iacr.org/2024/312","open_access":"1"}],"publisher":"Springer Nature","external_id":{"isi":["001274940200011"]},"supplementarymaterial":"no","page":"315-344","publication":"43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques","publication_identifier":{"isbn":["9783031587337"],"eissn":["1611-3349"],"issn":["0302-9743"]},"corr_author":"1","department":[{"_id":"KrPi"}],"oa":1,"_id":"17051","researchdata_availability":"no","intvolume":"     14653","title":"Trapdoor memory-hard functions","scopus_import":"1","date_published":"2024-05-01T00:00:00Z"},{"_id":"17283","department":[{"_id":"KrCh"},{"_id":"GradSch"}],"oa":1,"corr_author":"1","publication_identifier":{"eissn":["2475-1421"]},"date_published":"2024-06-20T00:00:00Z","article_type":"original","scopus_import":"1","title":"Equivalence and similarity refutation for probabilistic programs","intvolume":"         8","article_number":"232","researchdata_availability":"no","ec_funded":1,"abstract":[{"lang":"eng","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."}],"volume":8,"project":[{"call_identifier":"H2020","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"doi":"10.1145/3656462","das_tickbox":"0","year":"2024","fulldoi":"https://doi.org/10.1145/3656462","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","day":"20","OA_type":"hybrid","external_id":{"arxiv":["2404.03430"]},"supplementarymaterial":"no","publication":"Proceedings of the ACM on Programming Languages","arxiv":1,"publisher":"Association for Computing Machinery","month":"06","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"oa_version":"Published Version","citation":{"short":"K. Chatterjee, E. Goharshady, P. Novotný, D. Zikelic, Proceedings of the ACM on Programming Languages 8 (2024).","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.","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>.","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.","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>","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>"},"article_processing_charge":"Yes (via OA deal)","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","quality_controlled":"1","file_date_updated":"2024-07-22T07:17:14Z","author":[{"last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu"},{"id":"103b4fa0-896a-11ed-bdf8-87b697bef40d","last_name":"Kafshdar Goharshadi","orcid":"0000-0002-8595-0587","first_name":"Ehsan","full_name":"Kafshdar Goharshadi, Ehsan"},{"id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","last_name":"Novotný","first_name":"Petr","full_name":"Novotný, Petr"},{"first_name":"Dorde","full_name":"Zikelic, Dorde","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","last_name":"Zikelic","orcid":"0000-0002-4681-1699"}],"type":"journal_article","publication_status":"published","language":[{"iso":"eng"}],"OA_place":"publisher","ddc":["000"],"has_accepted_license":"1","status":"public","date_updated":"2026-10-16T08:08:51Z","date_created":"2024-07-21T22:01:01Z","file":[{"content_type":"application/pdf","checksum":"8cbf220f284a4a87d093db5320c5afdd","file_name":"2024_ACMProgLang_Chatterjee.pdf","creator":"dernst","success":1,"relation":"main_file","date_updated":"2024-07-22T07:17:14Z","date_created":"2024-07-22T07:17:14Z","file_size":355421,"access_level":"open_access","file_id":"17290"}]},{"day":"21","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.","keyword":["General Computer Science","Theoretical Computer Science"],"fulldoi":"https://doi.org/10.1016/j.tcs.2023.114353","das_tickbox":"0","year":"2024","doi":"10.1016/j.tcs.2023.114353","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","call_identifier":"H2020"}],"volume":989,"abstract":[{"text":"We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link (u, v) is determined by how 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.","lang":"eng"}],"ec_funded":1,"publisher":"Elsevier","publication":"Theoretical Computer Science","supplementarymaterial":"no","external_id":{"isi":["001168211400001"]},"publication_identifier":{"issn":["0304-3975"]},"corr_author":"1","department":[{"_id":"KrCh"},{"_id":"KrPi"}],"oa":1,"_id":"14820","researchdata_availability":"no","article_number":"114353","intvolume":"       989","title":"Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation","scopus_import":"1","article_type":"original","date_published":"2024-03-21T00:00:00Z","status":"public","has_accepted_license":"1","related_material":{"record":[{"status":"public","id":"19985","relation":"earlier_version"}]},"ddc":["000"],"language":[{"iso":"eng"}],"isi":1,"file":[{"file_name":"2024_TheorComputerScience_Schmid.pdf","creator":"dernst","success":1,"relation":"main_file","date_created":"2024-07-16T12:02:25Z","date_updated":"2024-07-16T12:02:25Z","content_type":"application/pdf","checksum":"efd5b7e738bf845312ba53889a3e13e4","file_id":"17263","file_size":603570,"access_level":"open_access"}],"date_updated":"2026-10-16T08:09:27Z","date_created":"2024-01-16T13:40:41Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"Yes (via OA deal)","citation":{"mla":"Schmid, Stefan, et al. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” <i>Theoretical Computer Science</i>, vol. 989, 114353, Elsevier, 2024, doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">10.1016/j.tcs.2023.114353</a>.","short":"S. Schmid, J. Svoboda, M.X. Yeo, Theoretical Computer Science 989 (2024).","ista":"Schmid S, Svoboda J, Yeo MX. 2024. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. Theoretical Computer Science. 989, 114353.","ama":"Schmid S, Svoboda J, Yeo MX. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. <i>Theoretical Computer Science</i>. 2024;989. doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">10.1016/j.tcs.2023.114353</a>","apa":"Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2024). Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">https://doi.org/10.1016/j.tcs.2023.114353</a>","ieee":"S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation,” <i>Theoretical Computer Science</i>, vol. 989. Elsevier, 2024.","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>."},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"oa_version":"Published Version","month":"03","publication_status":"published","type":"journal_article","author":[{"first_name":"Stefan","full_name":"Schmid, Stefan","last_name":"Schmid"},{"orcid":"0000-0002-1419-3267","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","full_name":"Svoboda, Jakub","first_name":"Jakub"},{"full_name":"Yeo, Michelle X","first_name":"Michelle X","last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0001-3676-4809"}],"file_date_updated":"2024-07-16T12:02:25Z","quality_controlled":"1"},{"oa":1,"department":[{"_id":"KrPi"}],"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783031587221"]},"_id":"17126","title":"Lower bounds for lattice-based compact functional encryption","scopus_import":"1","intvolume":"     14652","researchdata_availability":"no","date_published":"2024-05-08T00:00:00Z","das_tickbox":"0","year":"2024","doi":"10.1007/978-3-031-58723-8_9","fulldoi":"https://doi.org/10.1007/978-3-031-58723-8_9","day":"08","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).","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"}],"volume":14652,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2023/719.pdf"}],"supplementarymaterial":"no","external_id":{"isi":["001278247600009"]},"page":"249-279","publication":"Advances in Cryptology – EUROCRYPT 2024","publisher":"Springer Nature","conference":{"location":"Zurich, Switzerland","end_date":"2024-05-30","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","start_date":"2024-05-26"},"article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","month":"05","citation":{"short":"E. Tairi, A. Ünal, in:, Advances in Cryptology – EUROCRYPT 2024, Springer Nature, 2024, pp. 249–279.","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.","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>.","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>.","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>","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.","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>"},"oa_version":"Submitted Version","author":[{"last_name":"Tairi","first_name":"Erkan","full_name":"Tairi, Erkan"},{"first_name":"Akin","full_name":"Ünal, Akin","id":"f6b56fb6-dc63-11ee-9dbf-f6780863a85a","last_name":"Ünal","orcid":"0000-0002-8929-0221"}],"type":"conference","publication_status":"published","alternative_title":["LNCS"],"quality_controlled":"1","status":"public","isi":1,"language":[{"iso":"eng"}],"date_updated":"2026-10-16T08:10:05Z","date_created":"2024-06-09T22:01:03Z"},{"researchdata_availability":"no","intvolume":"     15486","scopus_import":"1","title":"Strongly secure universal thresholdizer","date_published":"2024-12-12T00:00:00Z","publication_identifier":{"isbn":["9789819608904"],"eissn":["1611-3349"],"issn":["0302-9743"]},"department":[{"_id":"KrPi"}],"oa":1,"_id":"18755","main_file_link":[{"url":"https://eprint.iacr.org/2024/2078","open_access":"1"}],"publisher":"Springer Nature","supplementarymaterial":"no","publication":"30th International Conference on the Theory and Application of Cryptology and Information Security","external_id":{"isi":["001443889100007"]},"page":"207-239","day":"12","OA_type":"green","acknowledgement":"Ehsan Ebrahimi is supported by the Luxembourg National Research Fund under the Junior CORE project QSP (C22/IS/17272217/QSP/Ebrahimi).","fulldoi":"https://doi.org/10.1007/978-981-96-0891-1_7","year":"2024","das_tickbox":"0","doi":"10.1007/978-981-96-0891-1_7","volume":15486,"abstract":[{"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.","lang":"eng"}],"publication_status":"published","type":"conference","author":[{"full_name":"Ebrahimi, Ehsan","first_name":"Ehsan","last_name":"Ebrahimi"},{"full_name":"Yadav, Anshu","first_name":"Anshu","last_name":"Yadav","id":"dc8f1524-403e-11ee-bf07-9649ad996e21"}],"quality_controlled":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"No","conference":{"location":"Kolkata, India","name":"ASIACRYPT: Conference on the Theory and Application of Cryptology and Information Security","start_date":"2024-12-09","end_date":"2024-12-13"},"citation":{"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>.","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.","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.","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>","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.","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>","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>."},"oa_version":"Preprint","month":"12","date_updated":"2026-10-16T08:10:40Z","date_created":"2025-01-05T23:01:56Z","status":"public","OA_place":"repository","language":[{"iso":"eng"}],"isi":1},{"language":[{"iso":"eng"}],"OA_place":"publisher","status":"public","date_created":"2025-01-30T07:45:22Z","date_updated":"2026-10-16T08:08:33Z","oa_version":"Preprint","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.","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.","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.","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.","short":"J. Svoboda, S. Bansal, K. Chatterjee, in:, 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 47331–47344.","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."},"month":"07","article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","conference":{"location":"Vienna, Austria","end_date":"2024-07-27","name":"ICML: International Conference on Machine Learning","start_date":"2024-07-21"},"quality_controlled":"1","publication_status":"published","alternative_title":["PMLR"],"author":[{"full_name":"Svoboda, Jakub","first_name":"Jakub","orcid":"0000-0002-1419-3267","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425"},{"first_name":"Suguman","full_name":"Bansal, Suguman","last_name":"Bansal"},{"first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"}],"type":"conference","volume":235,"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"}],"OA_type":"green","day":"29","year":"2024","das_tickbox":"0","publication":"41st International Conference on Machine Learning","supplementarymaterial":"no","page":"47331-47344","publisher":"ML Research Press","main_file_link":[{"url":"https://openreview.net/forum?id=mXUDDL4r1Q","open_access":"1"}],"_id":"18974","corr_author":"1","oa":1,"department":[{"_id":"KrCh"}],"date_published":"2024-07-29T00:00:00Z","researchdata_availability":"no","title":"Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance","scopus_import":"1","intvolume":"       235"},{"alternative_title":["ISTA Thesis"],"publication_status":"published","supervisor":[{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654"}],"author":[{"orcid":"0000-0001-8630-415X","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","last_name":"Pascual Perez","first_name":"Guillermo","full_name":"Pascual Perez, Guillermo"}],"type":"dissertation","file_date_updated":"2024-09-19T12:36:08Z","article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa_version":"Published Version","tmp":{"name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","image":"/images/cc_by_nc_sa.png","short":"CC BY-NC-SA (4.0)"},"citation":{"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>.","short":"G. Pascual Perez, On the Efficiency and Security of Secure Group Messaging, Institute of Science and Technology Austria, 2024.","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.","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>","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>","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>."},"month":"09","file":[{"file_size":11917734,"access_level":"closed","file_id":"18099","content_type":"application/x-zip-compressed","checksum":"ce0dca715b3df48e52e2e891b6ac1bc5","creator":"gpascual","file_name":"thesis_bundle.zip","relation":"source_file","date_created":"2024-09-19T12:35:38Z","date_updated":"2024-09-19T12:35:38Z"},{"file_id":"18100","file_size":2729427,"access_level":"open_access","creator":"gpascual","file_name":"thesis_gpasper.pdf","date_updated":"2024-09-19T12:36:08Z","relation":"main_file","date_created":"2024-09-19T12:36:08Z","content_type":"application/pdf","checksum":"4a2c72e90f1a0ef2a13cff800f8d1265"}],"date_created":"2024-09-18T12:59:49Z","date_updated":"2026-10-16T08:11:08Z","doi_confirm":"1","has_accepted_license":"1","status":"public","ddc":["000"],"OA_place":"publisher","related_material":{"record":[{"status":"public","id":"10408","relation":"part_of_dissertation"},{"status":"public","id":"11476","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","id":"10049","status":"public"},{"status":"public","id":"18086","relation":"part_of_dissertation"}]},"language":[{"iso":"eng"}],"degree_awarded":"PhD","researchdata_availability":"yes","license":"https://creativecommons.org/licenses/by-nc-sa/4.0/","title":"On the efficiency and security of secure group messaging","date_published":"2024-09-18T00:00:00Z","corr_author":"1","publication_identifier":{"issn":["2663-337X"]},"department":[{"_id":"KrPi"},{"_id":"GradSch"}],"oa":1,"_id":"18088","supplementarymaterial":"not applicable","page":"239","publisher":"Institute of Science and Technology Austria","fulldoi":"https://doi.org/10.15479/at:ista:18088","day":"18","doi":"10.15479/at:ista:18088","year":"2024","das_tickbox":"1","project":[{"name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"665385"}],"ec_funded":1,"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. "}]},{"department":[{"_id":"GradSch"},{"_id":"KrPi"}],"editor":[{"last_name":"Galdi","first_name":"Clemente","full_name":"Galdi, Clemente"},{"first_name":"Duong Hieu","full_name":"Phan, Duong Hieu","last_name":"Phan"}],"publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9783031710728"],"eisbn":["9783031710735"]},"corr_author":"1","_id":"18086","intvolume":"     14974","title":"DeCAF: Decentralizable CGKA with fast healing","researchdata_availability":"no","date_published":"2024-09-10T00:00:00Z","das_tickbox":"0","doi":"10.1007/978-3-031-71073-5_14","year":"2024","day":"10","fulldoi":"https://doi.org/10.1007/978-3-031-71073-5_14","abstract":[{"lang":"eng","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."}],"place":"Cham","volume":14974,"publisher":"Springer Nature","external_id":{"isi":["001330408000014"]},"supplementarymaterial":"no","page":"294–313","publication":"Security and Cryptography for Networks: 14th International Conference","conference":{"location":"Amalfi, Italy","start_date":"2024-09-11","name":"SCN: Security and Cryptography for Networks","end_date":"2024-09-13"},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"No","month":"09","citation":{"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.","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.","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>.","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>.","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>","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.","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>"},"oa_version":"None","type":"conference","author":[{"last_name":"Alwen","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","first_name":"Joel F"},{"first_name":"Benedikt","full_name":"Auerbach, Benedikt","orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","last_name":"Auerbach"},{"orcid":"0000-0002-2505-4246","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","last_name":"Cueto Noval","first_name":"Miguel","full_name":"Cueto Noval, Miguel"},{"full_name":"Klein, Karen","first_name":"Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","last_name":"Pascual Perez","orcid":"0000-0001-8630-415X","first_name":"Guillermo","full_name":"Pascual Perez, Guillermo"},{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak"}],"publication_status":"published","alternative_title":["LNCS"],"quality_controlled":"1","status":"public","isi":1,"related_material":{"record":[{"status":"public","id":"18088","relation":"dissertation_contains"}]},"language":[{"iso":"eng"}],"date_created":"2024-09-18T11:35:14Z","date_updated":"2026-10-16T08:11:07Z"},{"file_date_updated":"2025-01-29T13:44:47Z","quality_controlled":"1","publication_status":"published","author":[{"id":"ec98511c-eb8e-11eb-b029-edd25d7271a1","last_name":"Günther","first_name":"Christoph Ullrich","full_name":"Günther, Christoph Ullrich"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"}],"type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"oa_version":"Published Version","citation":{"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>.","ista":"Günther CU, Pietrzak KZ. 2024. Deniability in automated contact tracing: Impossibilities and possibilities. Proceedings on Privacy Enhancing Technologies. 2024(4), 636–648.","short":"C.U. Günther, K.Z. Pietrzak, Proceedings on Privacy Enhancing Technologies 2024 (2024) 636–648.","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>","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.","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>","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>."},"month":"07","article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","conference":{"end_date":"2024-07-20","start_date":"2024-07-15","name":"PETs: Privacy Enhancing Technologies Symposium ","location":"Bristol, UK/Virtual"},"date_updated":"2026-10-16T08:29:47Z","date_created":"2025-01-29T13:39:34Z","file":[{"file_id":"18962","access_level":"open_access","file_size":611567,"relation":"main_file","date_created":"2025-01-29T13:44:47Z","date_updated":"2025-01-29T13:44:47Z","success":1,"file_name":"2024_ProcPrivacyEnhTech_Guenther.pdf","creator":"dernst","checksum":"348ed6adcf6ad2f925227bde1758cae6","content_type":"application/pdf"}],"ddc":["000"],"OA_place":"publisher","language":[{"iso":"eng"}],"issue":"4","has_accepted_license":"1","status":"public","date_published":"2024-07-01T00:00:00Z","article_type":"original","researchdata_availability":"no","title":"Deniability in automated contact tracing: Impossibilities and possibilities","intvolume":"      2024","_id":"18961","corr_author":"1","publication_identifier":{"issn":["2299-0984"]},"department":[{"_id":"KrPi"},{"_id":"GradSch"}],"oa":1,"supplementarymaterial":"no","page":"636-648","publication":"Proceedings on Privacy Enhancing Technologies","publisher":"Privacy Enhancing Technologies Symposium Advisory Board","volume":2024,"project":[{"_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1","name":"Security and Privacy by Design for Complex Systems","grant_number":"F8509"}],"abstract":[{"lang":"eng","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."}],"fulldoi":"https://doi.org/10.56553/popets-2024-0134","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.","day":"01","OA_type":"gold","year":"2024","das_tickbox":"0","doi":"10.56553/popets-2024-0134"},{"file_date_updated":"2024-11-18T08:15:07Z","quality_controlled":"1","publication_status":"published","type":"journal_article","dataavailabilitystatement":"There is no data associated to this work.","author":[{"first_name":"László","full_name":"Erdös, László","orcid":"0000-0001-5366-9603","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","last_name":"Erdös"},{"full_name":"Riabov, Volodymyr","first_name":"Volodymyr","last_name":"Riabov","id":"1949f904-edfb-11eb-afb5-e2dfddabb93b"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"oa_version":"Published Version","citation":{"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>","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.","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>","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>.","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>.","short":"L. Erdös, V. Riabov, Communications in Mathematical Physics 405 (2024).","ista":"Erdös L, Riabov V. 2024. Eigenstate Thermalization Hypothesis for Wigner-type matrices. Communications in Mathematical Physics. 405(12), 282."},"month":"12","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"Yes (via OA deal)","date_updated":"2026-10-16T08:34:30Z","date_created":"2024-11-17T23:01:46Z","file":[{"relation":"main_file","date_created":"2024-11-18T08:15:07Z","date_updated":"2024-11-18T08:15:07Z","creator":"dernst","file_name":"2024_CommMathPhysics_Erdoes.pdf","success":1,"checksum":"c9ae0ea195bd39b8b3a630d492fb00dc","content_type":"application/pdf","file_id":"18562","file_size":1426046,"access_level":"open_access"}],"language":[{"iso":"eng"}],"ddc":["510"],"OA_place":"publisher","related_material":{"record":[{"status":"public","id":"20575","relation":"dissertation_contains"}]},"issue":"12","isi":1,"status":"public","has_accepted_license":"1","article_type":"original","date_published":"2024-12-01T00:00:00Z","researchdata_availability":"not applicable","article_number":"282","intvolume":"       405","title":"Eigenstate Thermalization Hypothesis for Wigner-type matrices","scopus_import":"1","_id":"18554","publication_identifier":{"eissn":["1432-0916"],"issn":["0010-3616"]},"corr_author":"1","oa":1,"department":[{"_id":"LaEr"}],"publisher":"Springer Nature","arxiv":1,"publication":"Communications in Mathematical Physics","external_id":{"arxiv":["2403.10359"],"isi":["001348943900004"],"pmid":["39526190"]},"supplementarymaterial":"yes","pmid":1,"volume":405,"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."}],"day":"01","acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria).","OA_type":"hybrid","fulldoi":"https://doi.org/10.1007/s00220-024-05143-y","doi":"10.1007/s00220-024-05143-y","year":"2024","das_tickbox":"1"},{"day":"01","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).","fulldoi":"https://doi.org/10.1007/s10959-023-01275-4","year":"2024","das_tickbox":"1","doi":"10.1007/s10959-023-01275-4","volume":37,"abstract":[{"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.","lang":"eng"}],"arxiv":1,"publisher":"Springer Nature","page":"933-973","publication":"Journal of Theoretical Probability","supplementarymaterial":"yes","external_id":{"arxiv":["2210.07927"],"isi":["001038341000001"]},"publication_identifier":{"eissn":["1572-9230"],"issn":["0894-9840"]},"corr_author":"1","oa":1,"department":[{"_id":"LaEr"}],"_id":"13975","researchdata_availability":"yes (supplementary data)","intvolume":"        37","title":"Spectrum of Lévy–Khintchine random laplacian matrices","scopus_import":"1","article_type":"original","date_published":"2024-03-01T00:00:00Z","status":"public","has_accepted_license":"1","language":[{"iso":"eng"}],"ddc":["510"],"isi":1,"file":[{"content_type":"application/pdf","checksum":"f7793d313104c70422140c5e6494c779","success":1,"file_name":"2024_JourTheorProbab_Campbell.pdf","creator":"dernst","date_created":"2024-07-22T09:41:21Z","relation":"main_file","date_updated":"2024-07-22T09:41:21Z","access_level":"open_access","file_size":555070,"file_id":"17300"}],"date_updated":"2026-10-16T08:30:34Z","date_created":"2023-08-06T22:01:13Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"Yes (via OA deal)","citation":{"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>.","short":"A.J. Campbell, S. O’Rourke, Journal of Theoretical Probability 37 (2024) 933–973.","ista":"Campbell AJ, O’Rourke S. 2024. Spectrum of Lévy–Khintchine random laplacian matrices. Journal of Theoretical Probability. 37, 933–973.","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.","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>","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>","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>."},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"oa_version":"Published Version","month":"03","publication_status":"published","type":"journal_article","author":[{"first_name":"Andrew J","full_name":"Campbell, Andrew J","id":"582b06a9-1f1c-11ee-b076-82ffce00dde4","last_name":"Campbell"},{"last_name":"O’Rourke","first_name":"Sean","full_name":"O’Rourke, Sean"}],"dataavailabilitystatement":"All data generated or analyzed during this study are included in this published article.","file_date_updated":"2024-07-22T09:41:21Z","quality_controlled":"1"},{"has_accepted_license":"1","status":"public","issue":"13","isi":1,"ddc":["510"],"language":[{"iso":"eng"}],"file":[{"relation":"main_file","date_created":"2024-07-22T06:40:19Z","date_updated":"2024-07-22T06:40:19Z","file_name":"2024_IMRN_Campbell.pdf","creator":"dernst","success":1,"checksum":"f36a7dbf53f23d5833db711052e69b49","content_type":"application/pdf","file_id":"17288","file_size":1233508,"access_level":"open_access"}],"date_updated":"2026-10-16T08:32:45Z","date_created":"2024-07-21T22:01:01Z","article_processing_charge":"Yes (via OA deal)","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","month":"07","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"citation":{"chicago":"Campbell, Andrew J, Sean O’Rourke, and David T Renfrew. “The Fractional Free Convolution of R-Diagonal Elements and Random Polynomials under Repeated Differentiation.” <i>International Mathematics Research Notices</i>. Oxford University Press, 2024. <a href=\"https://doi.org/10.1093/imrn/rnae062\">https://doi.org/10.1093/imrn/rnae062</a>.","ieee":"A. J. Campbell, S. O’Rourke, and D. T. Renfrew, “The fractional free convolution of R-diagonal elements and random polynomials under repeated differentiation,” <i>International Mathematics Research Notices</i>, vol. 2024, no. 13. Oxford University Press, pp. 10189–10218, 2024.","apa":"Campbell, A. J., O’Rourke, S., &#38; Renfrew, D. T. (2024). The fractional free convolution of R-diagonal elements and random polynomials under repeated differentiation. <i>International Mathematics Research Notices</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/imrn/rnae062\">https://doi.org/10.1093/imrn/rnae062</a>","ama":"Campbell AJ, O’Rourke S, Renfrew DT. The fractional free convolution of R-diagonal elements and random polynomials under repeated differentiation. <i>International Mathematics Research Notices</i>. 2024;2024(13):10189-10218. doi:<a href=\"https://doi.org/10.1093/imrn/rnae062\">10.1093/imrn/rnae062</a>","short":"A.J. Campbell, S. O’Rourke, D.T. Renfrew, International Mathematics Research Notices 2024 (2024) 10189–10218.","ista":"Campbell AJ, O’Rourke S, Renfrew DT. 2024. The fractional free convolution of R-diagonal elements and random polynomials under repeated differentiation. International Mathematics Research Notices. 2024(13), 10189–10218.","mla":"Campbell, Andrew J., et al. “The Fractional Free Convolution of R-Diagonal Elements and Random Polynomials under Repeated Differentiation.” <i>International Mathematics Research Notices</i>, vol. 2024, no. 13, Oxford University Press, 2024, pp. 10189–218, doi:<a href=\"https://doi.org/10.1093/imrn/rnae062\">10.1093/imrn/rnae062</a>."},"oa_version":"Published Version","author":[{"first_name":"Andrew J","full_name":"Campbell, Andrew J","id":"582b06a9-1f1c-11ee-b076-82ffce00dde4","last_name":"Campbell"},{"last_name":"O'Rourke","first_name":"Sean","full_name":"O'Rourke, Sean"},{"full_name":"Renfrew, David T","first_name":"David T","last_name":"Renfrew","id":"4845BF6A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3493-121X"}],"type":"journal_article","publication_status":"published","quality_controlled":"1","file_date_updated":"2024-07-22T06:40:19Z","das_tickbox":"0","year":"2024","doi":"10.1093/imrn/rnae062","fulldoi":"https://doi.org/10.1093/imrn/rnae062","acknowledgement":"This work was supported by the National Science Foundation [Grant No. DMS-2143142 to S.O.]; and the European Research Council [Grant No. 101020331].The third author acknowledges the support of the University of Colorado Boulder, where a portion of this work was completed. The authors thank Martin Auer, Vadim Gorin, Brian Hall, and Noah Williams for comments, corrections, and references. The authors also wish to thank the anonymous referees for useful feedback and corrections.","day":"01","abstract":[{"text":"We extend the free convolution of Brown measures of R-diagonal elements introduced by Kösters and Tikhomirov [ 28] to fractional powers. We then show how this fractional free convolution arises naturally when studying the roots of random polynomials with independent coefficients under repeated differentiation. When the proportion of derivatives to the degree approaches one, we establish central limit theorem-type behavior and discuss stable distributions.","lang":"eng"}],"volume":2024,"publication":"International Mathematics Research Notices","supplementarymaterial":"yes","page":"10189-10218","external_id":{"isi":["001198019500001"]},"publisher":"Oxford University Press","department":[{"_id":"LaEr"}],"oa":1,"corr_author":"1","publication_identifier":{"issn":["1073-7928"],"eissn":["1687-0247"]},"_id":"17281","title":"The fractional free convolution of R-diagonal elements and random polynomials under repeated differentiation","scopus_import":"1","intvolume":"      2024","researchdata_availability":"no","date_published":"2024-07-01T00:00:00Z","article_type":"original"},{"_id":"14408","publication_identifier":{"eissn":["1432-2064"],"issn":["0178-8051"]},"oa":1,"department":[{"_id":"LaEr"}],"date_published":"2024-04-01T00:00:00Z","article_type":"original","researchdata_availability":"no","title":"Mesoscopic central limit theorem for non-Hermitian random matrices","scopus_import":"1","intvolume":"       188","volume":188,"project":[{"_id":"62796744-2b32-11ec-9570-940b20777f1d","name":"Random matrices beyond Wigner-Dyson-Mehta","grant_number":"101020331","call_identifier":"H2020"}],"ec_funded":1,"abstract":[{"lang":"eng","text":"We prove that the mesoscopic linear statistics ∑if(na(σi−z0)) of the eigenvalues {σi}i of large n×n non-Hermitian random matrices with complex centred i.i.d. entries are asymptotically Gaussian for any H20-functions f around any point z0 in the bulk of the spectrum on any mesoscopic scale 0<a<1/2. This extends our previous result (Cipolloni et al. in Commun Pure Appl Math, 2019. arXiv:1912.04100), that was valid on the macroscopic scale, a=0\r\n, to cover the entire mesoscopic regime. The main novelty is a local law for the product of resolvents for the Hermitization of X at spectral parameters z1,z2 with an improved error term in the entire mesoscopic regime |z1−z2|≫n−1/2. The proof is dynamical; it relies on a recursive tandem of the characteristic flow method and the Green function comparison idea combined with a separation of the unstable mode of the underlying stability operator."}],"fulldoi":"https://doi.org/10.1007/s00440-023-01229-1","acknowledgement":"The authors are grateful to Joscha Henheik for his help with the formulas in Appendix B.\r\nLászló Erdős supported by ERC Advanced Grant “RMTBeyond” No. 101020331. Dominik Schröder supported by the SNSF Ambizione Grant PZ00P2 209089.","day":"01","doi":"10.1007/s00440-023-01229-1","das_tickbox":"0","year":"2024","external_id":{"arxiv":["2210.12060"],"isi":["001118972500001"]},"publication":"Probability Theory and Related Fields","supplementarymaterial":"yes","page":"1131-1182","publisher":"Springer Nature","arxiv":1,"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2210.12060","open_access":"1"}],"oa_version":"Preprint","citation":{"chicago":"Cipolloni, Giorgio, László Erdös, and Dominik J Schröder. “Mesoscopic Central Limit Theorem for Non-Hermitian Random Matrices.” <i>Probability Theory and Related Fields</i>. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/s00440-023-01229-1\">https://doi.org/10.1007/s00440-023-01229-1</a>.","ama":"Cipolloni G, Erdös L, Schröder DJ. Mesoscopic central limit theorem for non-Hermitian random matrices. <i>Probability Theory and Related Fields</i>. 2024;188:1131-1182. doi:<a href=\"https://doi.org/10.1007/s00440-023-01229-1\">10.1007/s00440-023-01229-1</a>","apa":"Cipolloni, G., Erdös, L., &#38; Schröder, D. J. (2024). Mesoscopic central limit theorem for non-Hermitian random matrices. <i>Probability Theory and Related Fields</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00440-023-01229-1\">https://doi.org/10.1007/s00440-023-01229-1</a>","ieee":"G. Cipolloni, L. Erdös, and D. J. Schröder, “Mesoscopic central limit theorem for non-Hermitian random matrices,” <i>Probability Theory and Related Fields</i>, vol. 188. Springer Nature, pp. 1131–1182, 2024.","short":"G. Cipolloni, L. Erdös, D.J. Schröder, Probability Theory and Related Fields 188 (2024) 1131–1182.","ista":"Cipolloni G, Erdös L, Schröder DJ. 2024. Mesoscopic central limit theorem for non-Hermitian random matrices. Probability Theory and Related Fields. 188, 1131–1182.","mla":"Cipolloni, Giorgio, et al. “Mesoscopic Central Limit Theorem for Non-Hermitian Random Matrices.” <i>Probability Theory and Related Fields</i>, vol. 188, Springer Nature, 2024, pp. 1131–82, doi:<a href=\"https://doi.org/10.1007/s00440-023-01229-1\">10.1007/s00440-023-01229-1</a>."},"month":"04","article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","quality_controlled":"1","publication_status":"published","author":[{"first_name":"Giorgio","full_name":"Cipolloni, Giorgio","orcid":"0000-0002-4901-7992","id":"42198EFA-F248-11E8-B48F-1D18A9856A87","last_name":"Cipolloni"},{"id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","last_name":"Erdös","orcid":"0000-0001-5366-9603","first_name":"László","full_name":"Erdös, László"},{"id":"408ED176-F248-11E8-B48F-1D18A9856A87","last_name":"Schröder","orcid":"0000-0002-2904-1856","first_name":"Dominik J","full_name":"Schröder, Dominik J"}],"type":"journal_article","language":[{"iso":"eng"}],"isi":1,"status":"public","date_created":"2023-10-08T22:01:17Z","date_updated":"2026-10-16T08:31:03Z"},{"corr_author":"1","publication_identifier":{"issn":["0022-2488"]},"oa":1,"department":[{"_id":"LaEr"}],"_id":"17375","researchdata_availability":"not applicable","title":"Precise asymptotics for the spectral radius of a large random matrix","scopus_import":"1","intvolume":"        65","article_number":"063302","date_published":"2024-06-01T00:00:00Z","article_type":"original","fulldoi":"https://doi.org/10.1063/5.0209705","acknowledgement":"L.E. and Y.X. were supported by the ERC Advanced Grant “RMTBeyond” Grant No. 101020331.","day":"01","doi":"10.1063/5.0209705","year":"2024","das_tickbox":"1","volume":65,"project":[{"_id":"62796744-2b32-11ec-9570-940b20777f1d","name":"Random matrices beyond Wigner-Dyson-Mehta","grant_number":"101020331","call_identifier":"H2020"}],"ec_funded":1,"abstract":[{"text":"We consider the spectral radius of a large random matrix X with independent, identically distributed entries. We show that its typical size is given by a precise three-term asymptotics with an optimal error term beyond the radius of the celebrated circular law. The coefficients in this asymptotics are universal but they differ from a similar asymptotics recently proved for the rightmost eigenvalue of X in Cipolloni et al., Ann. Probab. 51(6), 2192–2242 (2023). To access the more complicated spectral radius, we need to establish a new decorrelation mechanism for the low-lying singular values of X − z for different complex shift parameters z using the Dyson Brownian Motion.","lang":"eng"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2210.15643"}],"external_id":{"arxiv":["2210.15643"],"isi":["001252240700002"]},"publication":"Journal of Mathematical Physics","supplementarymaterial":"yes","publisher":"AIP Publishing","arxiv":1,"article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa_version":"Preprint","citation":{"short":"G. Cipolloni, L. Erdös, Y. Xu, Journal of Mathematical Physics 65 (2024).","ista":"Cipolloni G, Erdös L, Xu Y. 2024. Precise asymptotics for the spectral radius of a large random matrix. Journal of Mathematical Physics. 65(6), 063302.","mla":"Cipolloni, Giorgio, et al. “Precise Asymptotics for the Spectral Radius of a Large Random Matrix.” <i>Journal of Mathematical Physics</i>, vol. 65, no. 6, 063302, AIP Publishing, 2024, doi:<a href=\"https://doi.org/10.1063/5.0209705\">10.1063/5.0209705</a>.","chicago":"Cipolloni, Giorgio, László Erdös, and Yuanyuan Xu. “Precise Asymptotics for the Spectral Radius of a Large Random Matrix.” <i>Journal of Mathematical Physics</i>. AIP Publishing, 2024. <a href=\"https://doi.org/10.1063/5.0209705\">https://doi.org/10.1063/5.0209705</a>.","apa":"Cipolloni, G., Erdös, L., &#38; Xu, Y. (2024). Precise asymptotics for the spectral radius of a large random matrix. <i>Journal of Mathematical Physics</i>. AIP Publishing. <a href=\"https://doi.org/10.1063/5.0209705\">https://doi.org/10.1063/5.0209705</a>","ieee":"G. Cipolloni, L. Erdös, and Y. Xu, “Precise asymptotics for the spectral radius of a large random matrix,” <i>Journal of Mathematical Physics</i>, vol. 65, no. 6. AIP Publishing, 2024.","ama":"Cipolloni G, Erdös L, Xu Y. Precise asymptotics for the spectral radius of a large random matrix. <i>Journal of Mathematical Physics</i>. 2024;65(6). doi:<a href=\"https://doi.org/10.1063/5.0209705\">10.1063/5.0209705</a>"},"month":"06","publication_status":"published","dataavailabilitystatement":"Data sharing is not applicable to this article as no new data were created or analyzed in this study.\r\n\r\n","author":[{"orcid":"0000-0002-4901-7992","last_name":"Cipolloni","id":"42198EFA-F248-11E8-B48F-1D18A9856A87","full_name":"Cipolloni, Giorgio","first_name":"Giorgio"},{"first_name":"László","full_name":"Erdös, László","orcid":"0000-0001-5366-9603","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","last_name":"Erdös"},{"first_name":"Yuanyuan","full_name":"Xu, Yuanyuan","orcid":"0000-0003-1559-1205","id":"7902bdb1-a2a4-11eb-a164-c9216f71aea3","last_name":"Xu"}],"type":"journal_article","quality_controlled":"1","status":"public","language":[{"iso":"eng"}],"isi":1,"issue":"6","date_created":"2024-08-04T22:01:22Z","date_updated":"2026-10-16T08:33:32Z"},{"status":"public","issue":"1B","isi":1,"language":[{"iso":"eng"}],"date_updated":"2026-10-16T08:33:55Z","date_created":"2024-02-25T23:00:56Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"No","month":"02","citation":{"ista":"Erdös L, McKenna B. 2024. Extremal statistics of quadratic forms of GOE/GUE eigenvectors. Annals of Applied Probability. 34(1B), 1623–1662.","short":"L. Erdös, B. McKenna, Annals of Applied Probability 34 (2024) 1623–1662.","mla":"Erdös, László, and Benjamin McKenna. “Extremal Statistics of Quadratic Forms of GOE/GUE Eigenvectors.” <i>Annals of Applied Probability</i>, vol. 34, no. 1B, Institute of Mathematical Statistics, 2024, pp. 1623–62, doi:<a href=\"https://doi.org/10.1214/23-AAP2000\">10.1214/23-AAP2000</a>.","chicago":"Erdös, László, and Benjamin McKenna. “Extremal Statistics of Quadratic Forms of GOE/GUE Eigenvectors.” <i>Annals of Applied Probability</i>. Institute of Mathematical Statistics, 2024. <a href=\"https://doi.org/10.1214/23-AAP2000\">https://doi.org/10.1214/23-AAP2000</a>.","ama":"Erdös L, McKenna B. Extremal statistics of quadratic forms of GOE/GUE eigenvectors. <i>Annals of Applied Probability</i>. 2024;34(1B):1623-1662. doi:<a href=\"https://doi.org/10.1214/23-AAP2000\">10.1214/23-AAP2000</a>","ieee":"L. Erdös and B. McKenna, “Extremal statistics of quadratic forms of GOE/GUE eigenvectors,” <i>Annals of Applied Probability</i>, vol. 34, no. 1B. Institute of Mathematical Statistics, pp. 1623–1662, 2024.","apa":"Erdös, L., &#38; McKenna, B. (2024). Extremal statistics of quadratic forms of GOE/GUE eigenvectors. <i>Annals of Applied Probability</i>. Institute of Mathematical Statistics. <a href=\"https://doi.org/10.1214/23-AAP2000\">https://doi.org/10.1214/23-AAP2000</a>"},"oa_version":"Preprint","type":"journal_article","author":[{"first_name":"László","full_name":"Erdös, László","orcid":"0000-0001-5366-9603","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","last_name":"Erdös"},{"orcid":"0000-0003-2625-495X","id":"b0cc634c-d549-11ee-96c8-87338c7ad808","last_name":"McKenna","first_name":"Benjamin","full_name":"McKenna, Benjamin"}],"publication_status":"published","quality_controlled":"1","das_tickbox":"0","doi":"10.1214/23-AAP2000","year":"2024","acknowledgement":"The first author was supported by the ERC Advanced Grant “RMTBeyond” No. 101020331. The second author was supported by Fulbright Austria and the Austrian Marshall Plan Foundation.","day":"01","fulldoi":"https://doi.org/10.1214/23-AAP2000","ec_funded":1,"abstract":[{"lang":"eng","text":"We consider quadratic forms of deterministic matrices A evaluated at the random eigenvectors of a large N×N GOE or GUE matrix, or equivalently evaluated at the columns of a Haar-orthogonal or Haar-unitary random matrix. We prove that, as long as the deterministic matrix has rank much smaller than √N, the distributions of the extrema of these quadratic forms are asymptotically the same as if the eigenvectors were independent Gaussians. This reduces the problem to Gaussian computations, which we carry out in several cases to illustrate our result, finding Gumbel or Weibull limiting distributions depending on the signature of A. Our result also naturally applies to the eigenvectors of any invariant ensemble."}],"project":[{"call_identifier":"H2020","grant_number":"101020331","name":"Random matrices beyond Wigner-Dyson-Mehta","_id":"62796744-2b32-11ec-9570-940b20777f1d"}],"volume":34,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2208.12206"}],"arxiv":1,"publisher":"Institute of Mathematical Statistics","external_id":{"isi":["001163006100021"],"arxiv":["2208.12206"]},"publication":"Annals of Applied Probability","page":"1623-1662","supplementarymaterial":"yes","oa":1,"department":[{"_id":"LaEr"}],"publication_identifier":{"issn":["1050-5164"]},"corr_author":"1","_id":"15025","intvolume":"        34","title":"Extremal statistics of quadratic forms of GOE/GUE eigenvectors","scopus_import":"1","researchdata_availability":"no","article_type":"original","date_published":"2024-02-01T00:00:00Z"},{"date_published":"2024-06-26T00:00:00Z","researchdata_availability":"no","title":"Central limit theorems for random matrices: From resolvents to free probability","_id":"17164","corr_author":"1","publication_identifier":{"issn":["2663-337X"]},"department":[{"_id":"GradSch"},{"_id":"LaEr"}],"oa":1,"supplementarymaterial":"no","page":"206","publisher":"Institute of Science and Technology Austria","project":[{"_id":"62796744-2b32-11ec-9570-940b20777f1d","name":"Random matrices beyond Wigner-Dyson-Mehta","grant_number":"101020331","call_identifier":"H2020"}],"abstract":[{"text":"This thesis is structured into two parts. In the first part, we consider the random\r\nvariable X := Tr(f1(W)A1 . . . fk(W)Ak) where W is an N × N Hermitian Wigner matrix, k ∈ N, and we choose (possibly N-dependent) regular functions f1, . . . , fk as well as\r\nbounded deterministic matrices A1, . . . , Ak. In this context, we prove a functional central\r\nlimit theorem on macroscopic and mesoscopic scales, showing that the fluctuations of X\r\naround its expectation are Gaussian and that the limiting covariance structure is given\r\nby a deterministic recursion. We further give explicit error bounds in terms of the scaling\r\nof f1, . . . , fk and the number of traceless matrices among A1, . . . , Ak, thus extending\r\nthe results of Cipolloni, Erdős and Schröder [40] to products of arbitrary length k ≥ 2.\r\nAnalyzing the underlying combinatorics leads to a non-recursive formula for the variance\r\nof X as well as the covariance of X and Y := Tr(fk+1(W)Ak+1 . . . fk+ℓ(W)Ak+ℓ) of similar\r\nbuild. When restricted to polynomials, these formulas reproduce recent results of Male,\r\nMingo, Peché, and Speicher [107], showing that the underlying combinatorics of noncrossing partitions and annular non-crossing permutations continue to stay valid beyond\r\nthe setting of second-order free probability theory. As an application, we consider the\r\nfluctuation of Tr(eitW A1e\r\n−itW A2)/N around its thermal value Tr(A1) Tr(A2)/N2 when t\r\nis large and give an explicit formula for the variance.\r\nThe second part of the thesis collects three smaller projects focusing on different random\r\nmatrix models. In the first project, we show that a class of weakly perturbed Hamiltonians\r\nof the form Hλ = H0 + λW, where W is a Wigner matrix, exhibits prethermalization.\r\nThat is, the time evolution generated by Hλ relaxes to its ultimate thermal state via an\r\nintermediate prethermal state with a lifetime of order λ\r\n−2\r\n. As the main result, we obtain\r\na general relaxation formula, expressing the perturbed dynamics via the unperturbed\r\ndynamics and the ultimate thermal state. The proof relies on a two-resolvent global law\r\nfor the deformed Wigner matrix Hλ.\r\nThe second project focuses on correlated random matrices, more precisely on a correlated N × N Hermitian random matrix with a polynomially decaying metric correlation\r\nstructure. A trivial a priori bound shows that the operator norm of this model is stochastically dominated by √\r\nN. However, by calculating the trace of the moments of the matrix\r\nand using the summable decay of the cumulants, the norm estimate can be improved to a\r\nbound of order one.\r\nIn the third project, we consider a multiplicative perturbation of the form UA(t) where U\r\nis a unitary random matrix and A = diag(t, 1, ..., 1). This so-called UA model was\r\nfirst introduced by Fyodorov [73] for its applications in scattering theory. We give a\r\ngeneral description of the eigenvalue trajectories obtained by varying the parameter t and\r\nintroduce a flow of deterministic domains that separates the outlier resulting from the\r\nrank-one perturbation from the typical eigenvalues for all sub-critical timescales. The\r\nresults are obtained under generic assumptions on U that hold for various unitary random\r\nmatrices, including the circular unitary ensemble (CUE) in the original formulation of\r\nthe model.","lang":"eng"}],"ec_funded":1,"keyword":["Random Matrices","Spectrum","Central Limit Theorem","Resolvent","Free Probability"],"fulldoi":"https://doi.org/10.15479/at:ista:17164","day":"26","doi":"10.15479/at:ista:17164","year":"2024","das_tickbox":"0","file_date_updated":"2024-06-26T12:44:53Z","supervisor":[{"full_name":"Erdös, László","first_name":"László","orcid":"0000-0001-5366-9603","last_name":"Erdös","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87"}],"alternative_title":["ISTA Thesis"],"publication_status":"published","author":[{"first_name":"Jana","full_name":"Reker, Jana","id":"e796e4f9-dc8d-11ea-abe3-97e26a0323e9","last_name":"Reker"}],"type":"dissertation","citation":{"short":"J. Reker, Central Limit Theorems for Random Matrices: From Resolvents to Free Probability, Institute of Science and Technology Austria, 2024.","ista":"Reker J. 2024. Central limit theorems for random matrices: From resolvents to free probability. Institute of Science and Technology Austria.","mla":"Reker, Jana. <i>Central Limit Theorems for Random Matrices: From Resolvents to Free Probability</i>. Institute of Science and Technology Austria, 2024, doi:<a href=\"https://doi.org/10.15479/at:ista:17164\">10.15479/at:ista:17164</a>.","chicago":"Reker, Jana. “Central Limit Theorems for Random Matrices: From Resolvents to Free Probability.” Institute of Science and Technology Austria, 2024. <a href=\"https://doi.org/10.15479/at:ista:17164\">https://doi.org/10.15479/at:ista:17164</a>.","ama":"Reker J. Central limit theorems for random matrices: From resolvents to free probability. 2024. doi:<a href=\"https://doi.org/10.15479/at:ista:17164\">10.15479/at:ista:17164</a>","ieee":"J. Reker, “Central limit theorems for random matrices: From resolvents to free probability,” Institute of Science and Technology Austria, 2024.","apa":"Reker, J. (2024). <i>Central limit theorems for random matrices: From resolvents to free probability</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:17164\">https://doi.org/10.15479/at:ista:17164</a>"},"tmp":{"name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","image":"/images/cc_by_nc_sa.png","short":"CC BY-NC-SA (4.0)"},"oa_version":"Published Version","month":"06","article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_created":"2024-06-24T11:23:29Z","date_updated":"2026-10-16T08:35:03Z","doi_confirm":"1","file":[{"creator":"jreker","file_name":"ISTA_Thesis_JReker.pdf","date_created":"2024-06-26T12:39:36Z","date_updated":"2024-06-26T12:44:53Z","relation":"main_file","content_type":"application/pdf","checksum":"fb16d86e1f2753dc3a9e14d2bdfd84cd","file_id":"17176","file_size":2783027,"access_level":"open_access"},{"file_size":3054878,"access_level":"closed","file_id":"17177","content_type":"application/zip","checksum":"cb1e54009d47c1dcf5b866c4566fa27f","file_name":"ISTA_Thesis_JReker_SourceFiles.zip","creator":"jreker","date_created":"2024-06-26T12:39:42Z","date_updated":"2024-06-26T12:44:53Z","relation":"source_file"}],"ddc":["519"],"OA_place":"publisher","related_material":{"record":[{"id":"17173","relation":"part_of_dissertation","status":"public"},{"status":"public","relation":"part_of_dissertation","id":"11135"},{"status":"public","id":"17174","relation":"part_of_dissertation"},{"status":"public","relation":"part_of_dissertation","id":"17047"},{"status":"public","id":"17154","relation":"part_of_dissertation"}]},"language":[{"iso":"eng"}],"degree_awarded":"PhD","has_accepted_license":"1","status":"public"},{"publisher":"Elsevier","publication":"Journal of Functional Analysis","supplementarymaterial":"yes","external_id":{"isi":["001325502400001"]},"project":[{"name":"Random matrices beyond Wigner-Dyson-Mehta","_id":"62796744-2b32-11ec-9570-940b20777f1d","call_identifier":"H2020","grant_number":"101020331"}],"volume":287,"abstract":[{"lang":"eng","text":"We consider large non-Hermitian NxN matrices with an additive independent, identically distributed (i.i.d.) noise for each matrix elements. We show that already a small noise of variance 1/N completely thermalises the bulk singular vectors, in particular they satisfy the strong form of Quantum Unique Ergodicity (QUE) with an optimal speed of convergence. In physics terms, we thus extend the Eigenstate Thermalisation Hypothesis, formulated originally by Deutsch [34] and proven for Wigner matrices in [23], to arbitrary non-Hermitian matrices with an i.i.d. noise. As a consequence we obtain an optimal lower bound on the diagonal overlaps of the corresponding non-Hermitian eigenvectors. This quantity, also known as the (square of the) eigenvalue condition number measuring the sensitivity of the eigenvalue to small perturbations, has notoriously escaped rigorous treatment beyond the explicitly computable Ginibre ensemble apart from the very recent upper bounds given in [7] and [45]. As a key tool, we develop a new systematic decomposition of general observables in random matrix theory that governs the size of products of resolvents with deterministic matrices in between."}],"ec_funded":1,"acknowledgement":"Supported by ERC Advanced Grant “RMTBeyond” No. 101020331.\r\nSupported by the SNSF Ambizione Grant PZ00P2_209089.","day":"15","OA_type":"hybrid","fulldoi":"https://doi.org/10.1016/j.jfa.2024.110495","doi":"10.1016/j.jfa.2024.110495","year":"2024","das_tickbox":"1","article_type":"original","date_published":"2024-08-15T00:00:00Z","researchdata_availability":"not applicable","intvolume":"       287","article_number":"110495","scopus_import":"1","title":"Optimal lower bound on eigenvector overlaps for non-Hermitian random matrices","_id":"17049","publication_identifier":{"issn":["0022-1236"],"eissn":["1096-0783"]},"corr_author":"1","oa":1,"department":[{"_id":"LaEr"}],"date_updated":"2026-10-16T08:36:18Z","date_created":"2024-05-26T22:00:57Z","file":[{"file_size":1374854,"access_level":"open_access","file_id":"19891","checksum":"07d3f73e0c56e68eb110851842c22ee0","content_type":"application/pdf","date_created":"2025-06-24T13:14:21Z","relation":"main_file","date_updated":"2025-06-24T13:14:21Z","file_name":"2025_JourFunctionalAnalysis_Cipolloni.pdf","creator":"dernst","success":1}],"language":[{"iso":"eng"}],"OA_place":"publisher","related_material":{"record":[{"id":"19540","relation":"dissertation_contains","status":"public"}]},"ddc":["510"],"issue":"4","isi":1,"status":"public","has_accepted_license":"1","file_date_updated":"2025-06-24T13:14:21Z","quality_controlled":"1","publication_status":"published","type":"journal_article","author":[{"first_name":"Giorgio","full_name":"Cipolloni, Giorgio","orcid":"0000-0002-4901-7992","id":"42198EFA-F248-11E8-B48F-1D18A9856A87","last_name":"Cipolloni"},{"id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","last_name":"Erdös","orcid":"0000-0001-5366-9603","first_name":"László","full_name":"Erdös, László"},{"orcid":"0000-0003-1106-327X","id":"31d731d7-d235-11ea-ad11-b50331c8d7fb","last_name":"Henheik","first_name":"Sven Joscha","full_name":"Henheik, Sven Joscha"},{"orcid":"0000-0002-2904-1856","last_name":"Schröder","id":"408ED176-F248-11E8-B48F-1D18A9856A87","full_name":"Schröder, Dominik J","first_name":"Dominik J"}],"dataavailabilitystatement":"No data was used for the research described in the article.","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)"},"citation":{"chicago":"Cipolloni, Giorgio, László Erdös, Sven Joscha Henheik, and Dominik J Schröder. “Optimal Lower Bound on Eigenvector Overlaps for Non-Hermitian Random Matrices.” <i>Journal of Functional Analysis</i>. Elsevier, 2024. <a href=\"https://doi.org/10.1016/j.jfa.2024.110495\">https://doi.org/10.1016/j.jfa.2024.110495</a>.","ama":"Cipolloni G, Erdös L, Henheik SJ, Schröder DJ. Optimal lower bound on eigenvector overlaps for non-Hermitian random matrices. <i>Journal of Functional Analysis</i>. 2024;287(4). doi:<a href=\"https://doi.org/10.1016/j.jfa.2024.110495\">10.1016/j.jfa.2024.110495</a>","ieee":"G. Cipolloni, L. Erdös, S. J. Henheik, and D. J. Schröder, “Optimal lower bound on eigenvector overlaps for non-Hermitian random matrices,” <i>Journal of Functional Analysis</i>, vol. 287, no. 4. Elsevier, 2024.","apa":"Cipolloni, G., Erdös, L., Henheik, S. J., &#38; Schröder, D. J. (2024). Optimal lower bound on eigenvector overlaps for non-Hermitian random matrices. <i>Journal of Functional Analysis</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jfa.2024.110495\">https://doi.org/10.1016/j.jfa.2024.110495</a>","ista":"Cipolloni G, Erdös L, Henheik SJ, Schröder DJ. 2024. Optimal lower bound on eigenvector overlaps for non-Hermitian random matrices. Journal of Functional Analysis. 287(4), 110495.","short":"G. Cipolloni, L. Erdös, S.J. Henheik, D.J. Schröder, Journal of Functional Analysis 287 (2024).","mla":"Cipolloni, Giorgio, et al. “Optimal Lower Bound on Eigenvector Overlaps for Non-Hermitian Random Matrices.” <i>Journal of Functional Analysis</i>, vol. 287, no. 4, 110495, Elsevier, 2024, doi:<a href=\"https://doi.org/10.1016/j.jfa.2024.110495\">10.1016/j.jfa.2024.110495</a>."},"oa_version":"Published Version","month":"08","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"Yes (via OA deal)"}]