[{"has_accepted_license":"1","department":[{"_id":"GradSch"},{"_id":"KrPi"}],"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}],"title":"On the adaptive security of graph-based games","ddc":["519"],"day":"23","alternative_title":["ISTA Thesis"],"oa_version":"Published Version","date_updated":"2026-04-16T09:52:03Z","abstract":[{"text":"Many security definitions come in two flavors: a stronger “adaptive” flavor, where the adversary can arbitrarily make various choices during the course of the attack, and a weaker “selective” flavor where the adversary must commit to some or all of their choices a-priori. For example, in the context of identity-based encryption, selective security requires the adversary to decide on the identity of the attacked party at the very beginning of the game whereas adaptive security allows the attacker to first see the master public key and some secret keys before making this choice. Often, it appears to be much easier to achieve selective security than it is to achieve adaptive security. A series of several recent works shows how to cleverly achieve adaptive security in several such scenarios including generalized selective decryption [Pan07][FJP15], constrained PRFs [FKPR14], and Yao’s garbled circuits [JW16]. Although the above works expressed vague intuition that they share a common technique, the connection was never made precise. In this work we present a new framework (published at Crypto ’17 [JKK+17a]) that connects all of these works and allows us to present them in a unified and simplified fashion. Having the framework in place, we show how to achieve adaptive security for proxy re-encryption schemes (published at PKC ’19 [FKKP19]) and provide the first adaptive security proofs for continuous group key agreement protocols (published at S&P ’21 [KPW+21]). Questioning optimality of our framework, we then show that currently used proof techniques cannot lead to significantly better security guarantees for \"graph-building\" games (published at TCC ’21 [KKPW21a]). These games cover generalized selective decryption, as well as the security of prominent constructions for constrained PRFs, continuous group key agreement, and proxy re-encryption. Finally, we revisit the adaptive security of Yao’s garbled circuits and extend the analysis of Jafargholi and Wichs in two directions: While they prove adaptive security only for a modified construction with increased online complexity, we provide the first positive results for the original construction by Yao (published at TCC ’21 [KKP21a]). On the negative side, we prove that the results of Jafargholi and Wichs are essentially optimal by showing that no black-box reduction can provide a significantly better security bound (published at Crypto ’21 [KKPW21c]).","lang":"eng"}],"author":[{"full_name":"Klein, Karen","last_name":"Klein","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"}],"license":"https://creativecommons.org/licenses/by/4.0/","article_processing_charge":"No","date_created":"2021-09-23T07:31:44Z","status":"public","file_date_updated":"2022-03-10T12:15:18Z","acknowledgement":"I want to acknowledge the funding by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).\r\n","related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"10044"},{"status":"public","relation":"part_of_dissertation","id":"10048"},{"id":"10041","relation":"part_of_dissertation","status":"public"},{"relation":"part_of_dissertation","id":"10049","status":"public"},{"relation":"part_of_dissertation","id":"637","status":"public"},{"relation":"part_of_dissertation","id":"6430","status":"public"}]},"ec_funded":1,"publication_identifier":{"issn":["2663-337X"]},"_id":"10035","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"month":"09","publication_status":"published","citation":{"ieee":"K. Klein, “On the adaptive security of graph-based games,” Institute of Science and Technology Austria, 2021.","apa":"Klein, K. (2021). <i>On the adaptive security of graph-based games</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:10035\">https://doi.org/10.15479/at:ista:10035</a>","ama":"Klein K. On the adaptive security of graph-based games. 2021. doi:<a href=\"https://doi.org/10.15479/at:ista:10035\">10.15479/at:ista:10035</a>","ista":"Klein K. 2021. On the adaptive security of graph-based games. Institute of Science and Technology Austria.","chicago":"Klein, Karen. “On the Adaptive Security of Graph-Based Games.” Institute of Science and Technology Austria, 2021. <a href=\"https://doi.org/10.15479/at:ista:10035\">https://doi.org/10.15479/at:ista:10035</a>.","mla":"Klein, Karen. <i>On the Adaptive Security of Graph-Based Games</i>. Institute of Science and Technology Austria, 2021, doi:<a href=\"https://doi.org/10.15479/at:ista:10035\">10.15479/at:ista:10035</a>.","short":"K. Klein, On the Adaptive Security of Graph-Based Games, Institute of Science and Technology Austria, 2021."},"supervisor":[{"full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"degree_awarded":"PhD","corr_author":"1","type":"dissertation","OA_place":"publisher","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","file":[{"date_created":"2021-10-04T12:22:33Z","creator":"cchlebak","relation":"main_file","success":1,"file_id":"10082","file_name":"thesis_pdfa.pdf","checksum":"73a44345c683e81f3e765efbf86fdcc5","access_level":"open_access","content_type":"application/pdf","date_updated":"2021-10-04T12:22:33Z","file_size":2104726},{"file_id":"10085","file_name":"thesis_final (1).zip","access_level":"closed","checksum":"7b80df30a0e686c3ef6a56d4e1c59e29","content_type":"application/x-zip-compressed","date_updated":"2022-03-10T12:15:18Z","file_size":9538359,"date_created":"2021-10-05T07:04:37Z","creator":"cchlebak","relation":"source_file"}],"oa":1,"publisher":"Institute of Science and Technology Austria","date_published":"2021-09-23T00:00:00Z","language":[{"iso":"eng"}],"doi":"10.15479/at:ista:10035","year":"2021","page":"276"},{"year":"2021","quality_controlled":"1","page":"486-515","external_id":{"isi":["000696697800017"]},"doi":"10.1007/978-3-030-84245-1_17","language":[{"iso":"eng"}],"date_published":"2021-08-11T00:00:00Z","publisher":"Springer Nature","oa":1,"type":"conference","volume":12826,"citation":{"short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, D. Wichs, in:, 41st Annual International Cryptology Conference, Part II , Springer Nature, Cham, 2021, pp. 486–515.","mla":"Kamath Hosdurg, Chethan, et al. “Limits on the Adaptive Security of Yao’s Garbling.” <i>41st Annual International Cryptology Conference, Part II </i>, vol. 12826, Springer Nature, 2021, pp. 486–515, doi:<a href=\"https://doi.org/10.1007/978-3-030-84245-1_17\">10.1007/978-3-030-84245-1_17</a>.","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. 2021. Limits on the Adaptive Security of Yao’s Garbling. 41st Annual International Cryptology Conference, Part II . CRYPTO: Annual International Cryptology Conference, LCNS, vol. 12826, 486–515.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Daniel Wichs. “Limits on the Adaptive Security of Yao’s Garbling.” In <i>41st Annual International Cryptology Conference, Part II </i>, 12826:486–515. Cham: Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-84245-1_17\">https://doi.org/10.1007/978-3-030-84245-1_17</a>.","ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and D. Wichs, “Limits on the Adaptive Security of Yao’s Garbling,” in <i>41st Annual International Cryptology Conference, Part II </i>, Virtual, 2021, vol. 12826, pp. 486–515.","apa":"Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., &#38; Wichs, D. (2021). Limits on the Adaptive Security of Yao’s Garbling. In <i>41st Annual International Cryptology Conference, Part II </i> (Vol. 12826, pp. 486–515). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-84245-1_17\">https://doi.org/10.1007/978-3-030-84245-1_17</a>","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. Limits on the Adaptive Security of Yao’s Garbling. In: <i>41st Annual International Cryptology Conference, Part II </i>. Vol 12826. Cham: Springer Nature; 2021:486-515. doi:<a href=\"https://doi.org/10.1007/978-3-030-84245-1_17\">10.1007/978-3-030-84245-1_17</a>"},"publication_status":"published","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","_id":"10041","scopus_import":"1","month":"08","related_material":{"record":[{"status":"public","id":"10035","relation":"dissertation_contains"}]},"publication":"41st Annual International Cryptology Conference, Part II ","publication_identifier":{"eissn":["1611-3349"],"isbn":["978-3-030-84244-4"],"issn":["0302-9743"],"eisbn":["978-3-030-84245-1"]},"conference":{"start_date":"2021-08-16","location":"Virtual","name":"CRYPTO: Annual International Cryptology Conference","end_date":"2021-08-20"},"ec_funded":1,"article_processing_charge":"No","acknowledgement":"We would like to thank the anonymous reviewers of Crypto’21 whose detailed comments helped us considerably improve the presentation of the paper.","status":"public","date_created":"2021-09-23T14:06:15Z","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/945"}],"abstract":[{"text":"Yao’s garbling scheme is one of the most fundamental cryptographic constructions. Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security in the selective setting where the adversary chooses the challenge inputs before seeing the garbled circuit assuming secure symmetric-key encryption (and hence one-way functions). This was followed by results, both positive and negative, concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto 2013) showed that it cannot satisfy adaptive security as is, due to a simple incompressibility argument. Jafargholi and Wichs (TCC 2017) considered a natural adaptation of Yao’s scheme (where the output mapping is sent in the online phase, together with the garbled input) that circumvents this negative result, and proved that it is adaptively secure, at least for shallow circuits. In particular, they showed that for the class of circuits of depth   δ , the loss in security is at most exponential in   δ . The above results all concern the simulation-based notion of security. In this work, we show that the upper bound of Jafargholi and Wichs is basically optimal in a strong sense. As our main result, we show that there exists a family of Boolean circuits, one for each depth  δ∈N , such that any black-box reduction proving the adaptive indistinguishability of the natural adaptation of Yao’s scheme from any symmetric-key encryption has to lose a factor that is exponential in   δ√ . Since indistinguishability is a weaker notion than simulation, our bound also applies to adaptive simulation. To establish our results, we build on the recent approach of Kamath et al. (Eprint 2021), which uses pebbling lower bounds in conjunction with oracle separations to prove fine-grained lower bounds on loss in cryptographic security.","lang":"eng"}],"date_updated":"2026-04-08T07:01:43Z","intvolume":"     12826","oa_version":"Preprint","author":[{"last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0006-6812-7317"},{"last_name":"Klein","full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen"},{"full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"},{"first_name":"Daniel","last_name":"Wichs","full_name":"Wichs, Daniel"}],"project":[{"name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815"}],"department":[{"_id":"KrPi"}],"isi":1,"day":"11","alternative_title":["LCNS"],"place":"Cham","title":"Limits on the Adaptive Security of Yao’s Garbling"},{"abstract":[{"text":"We show that Yao’s garbling scheme is adaptively indistinguishable for the class of Boolean circuits of size S and treewidth w with only a S^O(w) loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly O(d w log(S)), d being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity.","lang":"eng"}],"type":"conference","article_number":"2021/926","oa_version":"Preprint","publication_status":"published","date_updated":"2026-04-08T07:01:43Z","citation":{"ieee":"C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators and Yao’s garbling,” in <i>19th Theory of Cryptography Conference 2021</i>, Raleigh, NC, United States, 2021.","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s garbling. In: <i>19th Theory of Cryptography Conference 2021</i>. International Association for Cryptologic Research; 2021.","apa":"Kamath Hosdurg, C., Klein, K., &#38; Pietrzak, K. Z. (2021). On treewidth, separators and Yao’s garbling. In <i>19th Theory of Cryptography Conference 2021</i>. Raleigh, NC, United States: International Association for Cryptologic Research.","mla":"Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.” <i>19th Theory of Cryptography Conference 2021</i>, 2021/926, International Association for Cryptologic Research, 2021.","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ. 2021. On treewidth, separators and Yao’s garbling. 19th Theory of Cryptography Conference 2021. TCC: Theory of Cryptography Conference, 2021/926.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth, Separators and Yao’s Garbling.” In <i>19th Theory of Cryptography Conference 2021</i>. International Association for Cryptologic Research, 2021.","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th Theory of Cryptography Conference 2021, International Association for Cryptologic Research, 2021."},"author":[{"full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","orcid":"0009-0006-6812-7317","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Klein","full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654"}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","department":[{"_id":"KrPi"}],"project":[{"call_identifier":"H2020","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks"}],"_id":"10044","month":"07","day":"08","title":"On treewidth, separators and Yao's garbling","related_material":{"record":[{"id":"10409","relation":"later_version","status":"public"},{"status":"public","id":"10035","relation":"dissertation_contains"}]},"publication":"19th Theory of Cryptography Conference 2021","quality_controlled":"1","year":"2021","ec_funded":1,"conference":{"end_date":"2021-11-11","name":"TCC: Theory of Cryptography Conference","start_date":"2021-11-08","location":"Raleigh, NC, United States"},"article_processing_charge":"No","publisher":"International Association for Cryptologic Research","language":[{"iso":"eng"}],"date_published":"2021-07-08T00:00:00Z","acknowledgement":"We would like to thank Daniel Wichs for helpful discussions on the landscape of adaptive security of Yao’s garbling.  ","date_created":"2021-09-24T12:01:34Z","main_file_link":[{"url":"https://eprint.iacr.org/2021/926","open_access":"1"}],"status":"public","oa":1},{"publication_status":"published","oa_version":"Preprint","citation":{"mla":"Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on Graphs.” <i>19th Theory of Cryptography Conference 2021</i>, International Association for Cryptologic Research, 2021.","chicago":"Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael Walter. “The Cost of Adaptivity in Security Games on Graphs.” In <i>19th Theory of Cryptography Conference 2021</i>. International Association for Cryptologic Research, 2021.","ista":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity in security games on graphs. 19th Theory of Cryptography Conference 2021. TCC: Theory of Cryptography Conference.","short":"C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th Theory of Cryptography Conference 2021, International Association for Cryptologic Research, 2021.","ieee":"C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity in security games on graphs,” in <i>19th Theory of Cryptography Conference 2021</i>, Raleigh, NC, United States, 2021.","ama":"Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in security games on graphs. In: <i>19th Theory of Cryptography Conference 2021</i>. International Association for Cryptologic Research; 2021.","apa":"Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., &#38; Walter, M. (2021). The cost of adaptivity in security games on graphs. In <i>19th Theory of Cryptography Conference 2021</i>. Raleigh, NC, United States: International Association for Cryptologic Research."},"date_updated":"2026-04-08T07:01:43Z","abstract":[{"lang":"eng","text":"The security of cryptographic primitives and protocols against adversaries that are allowed to make adaptive choices (e.g., which parties to corrupt or which queries to make) is notoriously difficult to establish. A broad theoretical\r\nframework was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper we initiate the study of lower bounds on loss in adaptive security for certain cryptographic protocols considered in the framework. We prove lower\r\nbounds that almost match the upper bounds (proven using the framework) for proxy re-encryption, prefix-constrained PRFs and generalized selective decryption, a security game that captures the security of certain group messaging and\r\nbroadcast encryption schemes. Those primitives have in common that their security game involves an underlying graph that can be adaptively built by the adversary. Some of our lower bounds only apply to a restricted class of black-box reductions which we term “oblivious” (the existing upper bounds are of this restricted type), some apply to the broader but still restricted class of non-rewinding reductions, while our lower bound for proxy re-encryption applies to all black-box reductions. The fact that some of our lower bounds seem to crucially rely on obliviousness or at least a non-rewinding reduction hints to the exciting possibility that the existing upper bounds can be improved by using more sophisticated reductions. Our main conceptual contribution is a two-player multi-stage game called the Builder-Pebbler Game. We can translate bounds on the winning probabilities for various instantiations of this game into cryptographic lower bounds for the above-mentioned primitives using oracle separation techniques.\r\n"}],"type":"conference","author":[{"first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0006-6812-7317","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan"},{"last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z"},{"first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482","last_name":"Walter","full_name":"Walter, Michael"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"10048","department":[{"_id":"KrPi"}],"title":"The cost of adaptivity in security games on graphs","month":"07","day":"08","quality_controlled":"1","year":"2021","publication":"19th Theory of Cryptography Conference 2021","related_material":{"record":[{"status":"public","id":"10410","relation":"later_version"},{"status":"public","relation":"dissertation_contains","id":"10035"}]},"conference":{"end_date":"2021-11-11","name":"TCC: Theory of Cryptography Conference","start_date":"2021-11-08","location":"Raleigh, NC, United States"},"article_processing_charge":"No","main_file_link":[{"open_access":"1","url":"https://ia.cr/2021/059"}],"date_created":"2021-09-27T12:52:05Z","status":"public","oa":1,"language":[{"iso":"eng"}],"date_published":"2021-07-08T00:00:00Z","publisher":"International Association for Cryptologic Research"},{"author":[{"full_name":"Klein, Karen","last_name":"Klein","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez","orcid":"0000-0001-8630-415X","first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Walter","full_name":"Walter, Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","orcid":"0000-0003-3186-2482"},{"orcid":"0009-0006-6812-7317","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan","full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg"},{"first_name":"Margarita","last_name":"Capretto","full_name":"Capretto, Margarita"},{"last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","first_name":"Miguel","orcid":"0000-0002-2505-4246"},{"last_name":"Markov","full_name":"Markov, Ilia","id":"D0CF4148-C985-11E9-8066-0BDEE5697425","first_name":"Ilia"},{"full_name":"Yeo, Michelle X","last_name":"Yeo","orcid":"0009-0001-3676-4809","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Alwen, Joel F","last_name":"Alwen","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F"},{"full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"oa_version":"Preprint","date_updated":"2026-04-08T07:01:44Z","abstract":[{"text":"While messaging systems with strong security guarantees are widely used in practice, designing a protocol that scales efficiently to large groups and enjoys similar security guarantees remains largely open. The two existing proposals to date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer Security Protocol, draft). TreeKEM is the currently considered candidate by the IETF MLS working group, but dynamic group operations (i.e. adding and removing users) can cause efficiency issues. In this paper we formalize and analyze a variant of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying TTKEM was suggested by Millican (MLS mailing list, February 2018). This version is more efficient than TreeKEM for some natural distributions of group operations, we quantify this through simulations.Our second contribution is two security proofs for TTKEM which establish post compromise and forward secrecy even against adaptive attackers. The security loss (to the underlying PKE) in the Random Oracle Model is a polynomial factor, and a quasipolynomial one in the Standard Model. Our proofs can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like protocol establishing tight security against an adversary who can adaptively choose the sequence of operations was known. We also are the first to prove (or even formalize) active security where the server can arbitrarily deviate from the protocol specification. Proving fully active security – where also the users can arbitrarily deviate – remains open.","lang":"eng"}],"title":"Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement","day":"26","isi":1,"department":[{"_id":"KrPi"},{"_id":"DaAl"}],"project":[{"name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"665385"},{"name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815"}],"ec_funded":1,"conference":{"name":"SP: Symposium on Security and Privacy","end_date":"2021-05-27","start_date":"2021-05-24","location":"San Francisco, CA, United States"},"publication":"2021 IEEE Symposium on Security and Privacy ","related_material":{"record":[{"relation":"dissertation_contains","id":"18088","status":"public"},{"status":"public","id":"10035","relation":"dissertation_contains"}]},"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/1489"}],"date_created":"2021-09-27T13:46:27Z","status":"public","acknowledgement":"The first three authors contributed equally to this work. Funded by the European Research Council (ERC) under the European Union’s Horizon2020 research and innovation programme (682815-TOCNeT). Funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No.665385.","article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication_status":"published","citation":{"ieee":"K. Klein <i>et al.</i>, “Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement,” in <i>2021 IEEE Symposium on Security and Privacy </i>, San Francisco, CA, United States, 2021, pp. 268–284.","apa":"Klein, K., Pascual Perez, G., Walter, M., Kamath Hosdurg, C., Capretto, M., Cueto Noval, M., … Pietrzak, K. Z. (2021). Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In <i>2021 IEEE Symposium on Security and Privacy </i> (pp. 268–284). San Francisco, CA, United States: IEEE. <a href=\"https://doi.org/10.1109/sp40001.2021.00035\">https://doi.org/10.1109/sp40001.2021.00035</a>","ama":"Klein K, Pascual Perez G, Walter M, et al. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. In: <i>2021 IEEE Symposium on Security and Privacy </i>. IEEE; 2021:268-284. doi:<a href=\"https://doi.org/10.1109/sp40001.2021.00035\">10.1109/sp40001.2021.00035</a>","short":"K. Klein, G. Pascual Perez, M. Walter, C. Kamath Hosdurg, M. Capretto, M. Cueto Noval, I. Markov, M.X. Yeo, J.F. Alwen, K.Z. Pietrzak, in:, 2021 IEEE Symposium on Security and Privacy , IEEE, 2021, pp. 268–284.","chicago":"Klein, Karen, Guillermo Pascual Perez, Michael Walter, Chethan Kamath Hosdurg, Margarita Capretto, Miguel Cueto Noval, Ilia Markov, Michelle X Yeo, Joel F Alwen, and Krzysztof Z Pietrzak. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” In <i>2021 IEEE Symposium on Security and Privacy </i>, 268–84. IEEE, 2021. <a href=\"https://doi.org/10.1109/sp40001.2021.00035\">https://doi.org/10.1109/sp40001.2021.00035</a>.","mla":"Klein, Karen, et al. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement.” <i>2021 IEEE Symposium on Security and Privacy </i>, IEEE, 2021, pp. 268–84, doi:<a href=\"https://doi.org/10.1109/sp40001.2021.00035\">10.1109/sp40001.2021.00035</a>.","ista":"Klein K, Pascual Perez G, Walter M, Kamath Hosdurg C, Capretto M, Cueto Noval M, Markov I, Yeo MX, Alwen JF, Pietrzak KZ. 2021. Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement. 2021 IEEE Symposium on Security and Privacy . SP: Symposium on Security and Privacy, 268–284."},"type":"conference","corr_author":"1","scopus_import":"1","month":"08","_id":"10049","external_id":{"isi":["001316065000016"]},"page":"268-284","quality_controlled":"1","year":"2021","oa":1,"language":[{"iso":"eng"}],"publisher":"IEEE","doi":"10.1109/sp40001.2021.00035","date_published":"2021-08-26T00:00:00Z"},{"publication":"Journal of Neuroscience","publication_identifier":{"issn":["0270-6474"],"eissn":["1529-2401"]},"article_processing_charge":"No","date_created":"2021-09-27T14:33:13Z","status":"public","file_date_updated":"2022-05-31T09:10:15Z","acknowledgement":"This work was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) through the Collaborative Sensory Research Center 1286 [to C.W. (A4) and T.M. (B5)] and under Germany’s Excellence Strategy Grant EXC 2067/1-390729940. We thank S. Gerke, A.J. Goldak, and C. Senger-Freitag for expert technical assistance; G. Hoch for developing image analysis routines; and S. Chepurwar and N. Strenzke for technical support and discussion regarding in vivo experiments. We also thank Dr. Christian Rosenmund, Dr. Katharina Grauel, and Dr. Stephan Sigrist for providing RIM-BP2 KO mice and Dr. Masahiko Watanabe for providing the anti-neurexin-antibody, and Dr. Toshihisa Ohtsuka for the anti-ELKS-antibody. J. Neef for help with the STED imaging and image analysis; E. Neher and S. Rizzoli for discussion and comments on the manuscript; K. Eguchi for help with the statistical analysis; and C. H. Huang and J. Neef for constant support and scientific discussion.","oa_version":"Published Version","date_updated":"2023-08-14T06:56:30Z","intvolume":"        41","abstract":[{"text":"Rab-interacting molecule (RIM)-binding protein 2 (BP2) is a multidomain protein of the presynaptic active zone (AZ). By binding to RIM, bassoon (Bsn), and voltage-gated Ca2+ channels (CaV), it is considered to be a central organizer of the topography of CaV and release sites of synaptic vesicles (SVs) at the AZ. Here, we used RIM-BP2 knock-out (KO) mice and their wild-type (WT) littermates of either sex to investigate the role of RIM-BP2 at the endbulb of Held synapse of auditory nerve fibers (ANFs) with bushy cells (BCs) of the cochlear nucleus, a fast relay of the auditory pathway with high release probability. Disruption of RIM-BP2 lowered release probability altering short-term plasticity and reduced evoked EPSCs. Analysis of SV pool dynamics during high-frequency train stimulation indicated a reduction of SVs with high release probability but an overall normal size of the readily releasable SV pool (RRP). The Ca2+-dependent fast component of SV replenishment after RRP depletion was slowed. Ultrastructural analysis by superresolution light and electron microscopy revealed an impaired topography of presynaptic CaV and a reduction of docked and membrane-proximal SVs at the AZ. We conclude that RIM-BP2 organizes the topography of CaV, and promotes SV tethering and docking. This way RIM-BP2 is critical for establishing a high initial release probability as required to reliably signal sound onset information that we found to be degraded in BCs of RIM-BP2-deficient mice in vivo. SIGNIFICANCE STATEMENT: Rab-interacting molecule (RIM)-binding proteins (BPs) are key organizers of the active zone (AZ). Using a multidisciplinary approach to the calyceal endbulb of Held synapse that transmits auditory information at rates of up to hundreds of Hertz with submillisecond precision we demonstrate a requirement for RIM-BP2 for normal auditory signaling. Endbulb synapses lacking RIM-BP2 show a reduced release probability despite normal whole-terminal Ca2+ influx and abundance of the key priming protein Munc13-1, a reduced rate of SV replenishment, as well as an altered topography of voltage-gated (CaV)2.1 Ca2+ channels, and fewer docked and membrane proximal synaptic vesicles (SVs). This hampers transmission of sound onset information likely affecting downstream neural computations such as of sound localization.","lang":"eng"}],"author":[{"first_name":"Tanvi","last_name":"Butola","full_name":"Butola, Tanvi"},{"last_name":"Alvanos","full_name":"Alvanos, Theocharis","first_name":"Theocharis"},{"last_name":"Hintze","full_name":"Hintze, Anika","first_name":"Anika"},{"full_name":"Koppensteiner, Peter","last_name":"Koppensteiner","orcid":"0000-0002-3509-1948","id":"3B8B25A8-F248-11E8-B48F-1D18A9856A87","first_name":"Peter"},{"last_name":"Kleindienst","full_name":"Kleindienst, David","id":"42E121A4-F248-11E8-B48F-1D18A9856A87","first_name":"David"},{"full_name":"Shigemoto, Ryuichi","last_name":"Shigemoto","orcid":"0000-0001-8761-9444","id":"499F3ABC-F248-11E8-B48F-1D18A9856A87","first_name":"Ryuichi"},{"last_name":"Wichmann","full_name":"Wichmann, Carolin","first_name":"Carolin"},{"full_name":"Moser, Tobias","last_name":"Moser","first_name":"Tobias"}],"has_accepted_license":"1","isi":1,"department":[{"_id":"RySh"}],"title":"RIM-binding protein 2 organizes Ca<sup>21</sup> channel topography and regulates release probability and vesicle replenishment at a fast central synapse","ddc":["570"],"day":"15","quality_controlled":"1","year":"2021","external_id":{"pmid":["34353898"],"isi":["000752287700005"]},"page":"7742-7767","article_type":"original","file":[{"file_size":11571961,"date_updated":"2022-05-31T09:10:15Z","content_type":"application/pdf","checksum":"769ab627c7355a50ccfd445e43a5f351","access_level":"open_access","file_name":"2021_JourNeuroscience_Butola.pdf","file_id":"11423","success":1,"creator":"dernst","relation":"main_file","date_created":"2022-05-31T09:10:15Z"}],"oa":1,"language":[{"iso":"eng"}],"doi":"10.1523/JNEUROSCI.0586-21.2021","publisher":"Society for Neuroscience","date_published":"2021-09-15T00:00:00Z","issue":"37","publication_status":"published","citation":{"short":"T. Butola, T. Alvanos, A. Hintze, P. Koppensteiner, D. Kleindienst, R. Shigemoto, C. Wichmann, T. Moser, Journal of Neuroscience 41 (2021) 7742–7767.","chicago":"Butola, Tanvi, Theocharis Alvanos, Anika Hintze, Peter Koppensteiner, David Kleindienst, Ryuichi Shigemoto, Carolin Wichmann, and Tobias Moser. “RIM-Binding Protein 2 Organizes Ca<sup>21</sup> Channel Topography and Regulates Release Probability and Vesicle Replenishment at a Fast Central Synapse.” <i>Journal of Neuroscience</i>. Society for Neuroscience, 2021. <a href=\"https://doi.org/10.1523/JNEUROSCI.0586-21.2021\">https://doi.org/10.1523/JNEUROSCI.0586-21.2021</a>.","mla":"Butola, Tanvi, et al. “RIM-Binding Protein 2 Organizes Ca<sup>21</sup> Channel Topography and Regulates Release Probability and Vesicle Replenishment at a Fast Central Synapse.” <i>Journal of Neuroscience</i>, vol. 41, no. 37, Society for Neuroscience, 2021, pp. 7742–67, doi:<a href=\"https://doi.org/10.1523/JNEUROSCI.0586-21.2021\">10.1523/JNEUROSCI.0586-21.2021</a>.","ista":"Butola T, Alvanos T, Hintze A, Koppensteiner P, Kleindienst D, Shigemoto R, Wichmann C, Moser T. 2021. RIM-binding protein 2 organizes Ca<sup>21</sup> channel topography and regulates release probability and vesicle replenishment at a fast central synapse. Journal of Neuroscience. 41(37), 7742–7767.","ieee":"T. Butola <i>et al.</i>, “RIM-binding protein 2 organizes Ca<sup>21</sup> channel topography and regulates release probability and vesicle replenishment at a fast central synapse,” <i>Journal of Neuroscience</i>, vol. 41, no. 37. Society for Neuroscience, pp. 7742–7767, 2021.","apa":"Butola, T., Alvanos, T., Hintze, A., Koppensteiner, P., Kleindienst, D., Shigemoto, R., … Moser, T. (2021). RIM-binding protein 2 organizes Ca<sup>21</sup> channel topography and regulates release probability and vesicle replenishment at a fast central synapse. <i>Journal of Neuroscience</i>. Society for Neuroscience. <a href=\"https://doi.org/10.1523/JNEUROSCI.0586-21.2021\">https://doi.org/10.1523/JNEUROSCI.0586-21.2021</a>","ama":"Butola T, Alvanos T, Hintze A, et al. RIM-binding protein 2 organizes Ca<sup>21</sup> channel topography and regulates release probability and vesicle replenishment at a fast central synapse. <i>Journal of Neuroscience</i>. 2021;41(37):7742-7767. doi:<a href=\"https://doi.org/10.1523/JNEUROSCI.0586-21.2021\">10.1523/JNEUROSCI.0586-21.2021</a>"},"type":"journal_article","volume":41,"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"10051","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"pmid":1,"month":"09","scopus_import":"1"},{"_id":"10052","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"scopus_import":"1","month":"08","arxiv":1,"type":"conference","volume":203,"publication_status":"published","citation":{"ieee":"I. R. Jecker, N. Mazzocchi, and P. Wolf, “Decomposing permutation automata,” in <i>32nd International Conference on Concurrency Theory</i>, Paris, France, 2021, vol. 203.","apa":"Jecker, I. R., Mazzocchi, N., &#38; Wolf, P. (2021). Decomposing permutation automata. In <i>32nd International Conference on Concurrency Theory</i> (Vol. 203). Paris, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2021.18\">https://doi.org/10.4230/LIPIcs.CONCUR.2021.18</a>","ama":"Jecker IR, Mazzocchi N, Wolf P. Decomposing permutation automata. In: <i>32nd International Conference on Concurrency Theory</i>. Vol 203. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2021.18\">10.4230/LIPIcs.CONCUR.2021.18</a>","short":"I.R. Jecker, N. Mazzocchi, P. Wolf, in:, 32nd International Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","ista":"Jecker IR, Mazzocchi N, Wolf P. 2021. Decomposing permutation automata. 32nd International Conference on Concurrency Theory. CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 203, 18.","chicago":"Jecker, Ismael R, Nicolas Mazzocchi, and Petra Wolf. “Decomposing Permutation Automata.” In <i>32nd International Conference on Concurrency Theory</i>, Vol. 203. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2021.18\">https://doi.org/10.4230/LIPIcs.CONCUR.2021.18</a>.","mla":"Jecker, Ismael R., et al. “Decomposing Permutation Automata.” <i>32nd International Conference on Concurrency Theory</i>, vol. 203, 18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2021.18\">10.4230/LIPIcs.CONCUR.2021.18</a>."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"date_published":"2021-08-13T00:00:00Z","doi":"10.4230/LIPIcs.CONCUR.2021.18","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file":[{"relation":"main_file","creator":"cchlebak","success":1,"date_created":"2021-10-01T11:10:53Z","date_updated":"2021-10-01T11:10:53Z","content_type":"application/pdf","file_size":1003552,"file_id":"10064","checksum":"4722c81be82265cf45e78adf9db91250","access_level":"open_access","file_name":"2021_CONCUR_Jecker.pdf"}],"oa":1,"quality_controlled":"1","year":"2021","external_id":{"arxiv":["2107.04683"]},"department":[{"_id":"KrCh"}],"project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"}],"has_accepted_license":"1","ddc":["000"],"day":"13","alternative_title":["LIPIcs"],"title":"Decomposing permutation automata","abstract":[{"lang":"eng","text":"A deterministic finite automaton (DFA) 𝒜 is composite if its language L(𝒜) can be decomposed into an intersection ⋂_{i = 1}^k L(𝒜_i) of languages of smaller DFAs. Otherwise, 𝒜 is prime. This notion of primality was introduced by Kupferman and Mosheiff in 2013, and while they proved that we can decide whether a DFA is composite, the precise complexity of this problem is still open, with a doubly-exponential gap between the upper and lower bounds. In this work, we focus on permutation DFAs, i.e., those for which the transition monoid is a group. We provide an NP algorithm to decide whether a permutation DFA is composite, and show that the difficulty of this problem comes from the number of non-accepting states of the instance: we give a fixed-parameter tractable algorithm with the number of rejecting states as the parameter. Moreover, we investigate the class of commutative permutation DFAs. Their structural properties allow us to decide compositionality in NL, and even in LOGSPACE if the alphabet size is fixed. Despite this low complexity, we show that complex behaviors still arise in this class: we provide a family of composite DFAs each requiring polynomially many factors with respect to its size. We also consider the variant of the problem that asks whether a DFA is k-factor composite, that is, decomposable into k smaller DFAs, for some given integer k ∈ ℕ. We show that, for commutative permutation DFAs, restricting the number of factors makes the decision computationally harder, and yields a problem with tight bounds: it is NP-complete. Finally, we show that in general, this problem is in PSPACE, and it is in LOGSPACE for DFAs with a singleton alphabet."}],"article_number":"18","oa_version":"Published Version","intvolume":"       203","date_updated":"2025-05-14T10:55:28Z","author":[{"full_name":"Jecker, Ismael R","last_name":"Jecker","id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","first_name":"Ismael R"},{"last_name":"Mazzocchi","full_name":"Mazzocchi, Nicolas","first_name":"Nicolas"},{"first_name":"Petra","last_name":"Wolf","full_name":"Wolf, Petra"}],"article_processing_charge":"No","acknowledgement":"Ismaël Jecker: Marie Skłodowska-Curie Grant Agreement No. 754411. Nicolas Mazzocchi: BOSCO project PGC2018-102210-B-I00 (MCIU/AEI/FEDER, UE), BLOQUESCM project S2018/TCS-4339, and MINECO grant RYC-2016-20281.\r\nPetra Wolf : DFG project FE 560/9-1.\r\n","date_created":"2021-09-27T14:33:14Z","status":"public","file_date_updated":"2021-10-01T11:10:53Z","publication":"32nd International Conference on Concurrency Theory","publication_identifier":{"isbn":["978-3-9597-7203-7"],"issn":["1868-8969"]},"ec_funded":1,"conference":{"start_date":"2021-08-23","location":"Paris, France","name":"CONCUR: Conference on Concurrency Theory","end_date":"2021-08-27"}},{"publisher":"Institute of Electrical and Electronics Engineers","doi":"10.1109/ISIT45174.2021.9518153","date_published":"2021-09-01T00:00:00Z","language":[{"iso":"eng"}],"oa":1,"page":"2369-2374","external_id":{"arxiv":["2012.13378"],"isi":["000701502202078"]},"quality_controlled":"1","year":"2021","month":"09","scopus_import":"1","arxiv":1,"_id":"10053","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","type":"conference","publication_status":"published","citation":{"apa":"Hashemi, S. A., Mondelli, M., Fazeli, A., Vardy, A., Cioffi, J., &#38; Goldsmith, A. (2021). Parallelism versus latency in simplified successive-cancellation decoding of polar codes. In <i>2021 IEEE International Symposium on Information Theory</i> (pp. 2369–2374). Melbourne, Australia: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/ISIT45174.2021.9518153\">https://doi.org/10.1109/ISIT45174.2021.9518153</a>","ama":"Hashemi SA, Mondelli M, Fazeli A, Vardy A, Cioffi J, Goldsmith A. Parallelism versus latency in simplified successive-cancellation decoding of polar codes. In: <i>2021 IEEE International Symposium on Information Theory</i>. Institute of Electrical and Electronics Engineers; 2021:2369-2374. doi:<a href=\"https://doi.org/10.1109/ISIT45174.2021.9518153\">10.1109/ISIT45174.2021.9518153</a>","ieee":"S. A. Hashemi, M. Mondelli, A. Fazeli, A. Vardy, J. Cioffi, and A. Goldsmith, “Parallelism versus latency in simplified successive-cancellation decoding of polar codes,” in <i>2021 IEEE International Symposium on Information Theory</i>, Melbourne, Australia, 2021, pp. 2369–2374.","mla":"Hashemi, Seyyed Ali, et al. “Parallelism versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes.” <i>2021 IEEE International Symposium on Information Theory</i>, Institute of Electrical and Electronics Engineers, 2021, pp. 2369–74, doi:<a href=\"https://doi.org/10.1109/ISIT45174.2021.9518153\">10.1109/ISIT45174.2021.9518153</a>.","chicago":"Hashemi, Seyyed Ali, Marco Mondelli, Arman Fazeli, Alexander Vardy, John Cioffi, and Andrea Goldsmith. “Parallelism versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes.” In <i>2021 IEEE International Symposium on Information Theory</i>, 2369–74. Institute of Electrical and Electronics Engineers, 2021. <a href=\"https://doi.org/10.1109/ISIT45174.2021.9518153\">https://doi.org/10.1109/ISIT45174.2021.9518153</a>.","ista":"Hashemi SA, Mondelli M, Fazeli A, Vardy A, Cioffi J, Goldsmith A. 2021. Parallelism versus latency in simplified successive-cancellation decoding of polar codes. 2021 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory, 2369–2374.","short":"S.A. Hashemi, M. Mondelli, A. Fazeli, A. Vardy, J. Cioffi, A. Goldsmith, in:, 2021 IEEE International Symposium on Information Theory, Institute of Electrical and Electronics Engineers, 2021, pp. 2369–2374."},"acknowledgement":"S. A. Hashemi is supported by a Postdoctoral Fellowship from the Natural Sciences and Engineering Research Council\r\nof Canada (NSERC) and by Huawei. M. Mondelli is partially supported by the 2019 Lopez-Loreta Prize. A. Fazeli and A. Vardy were supported in part by the National Science Foundation under Grant CCF-1764104.","date_created":"2021-09-27T14:33:14Z","main_file_link":[{"url":"https://arxiv.org/abs/2012.13378","open_access":"1"}],"status":"public","article_processing_charge":"No","publication_identifier":{"eisbn":["978-1-5386-8209-8"],"issn":["2157-8095"],"isbn":["978-1-5386-8210-4"]},"conference":{"end_date":"2021-07-20","name":"ISIT: International Symposium on Information Theory","start_date":"2021-07-12","location":"Melbourne, Australia"},"related_material":{"record":[{"status":"public","id":"10364","relation":"later_version"}]},"publication":"2021 IEEE International Symposium on Information Theory","day":"01","title":"Parallelism versus latency in simplified successive-cancellation decoding of polar codes","department":[{"_id":"MaMo"}],"project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"isi":1,"author":[{"first_name":"Seyyed Ali","last_name":"Hashemi","full_name":"Hashemi, Seyyed Ali"},{"full_name":"Mondelli, Marco","last_name":"Mondelli","orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","first_name":"Marco"},{"last_name":"Fazeli","full_name":"Fazeli, Arman","first_name":"Arman"},{"first_name":"Alexander","full_name":"Vardy, Alexander","last_name":"Vardy"},{"first_name":"John","last_name":"Cioffi","full_name":"Cioffi, John"},{"first_name":"Andrea","last_name":"Goldsmith","full_name":"Goldsmith, Andrea"}],"abstract":[{"lang":"eng","text":"This paper characterizes the latency of the simplified successive-cancellation (SSC) decoding scheme for polar codes under hardware resource constraints. In particular, when the number of processing elements P that can perform SSC decoding operations in parallel is limited, as is the case in practice, the latency of SSC decoding is O(N1−1 μ+NPlog2log2NP), where N is the block length of the code and μ is the scaling exponent of polar codes for the channel. Three direct consequences of this bound are presented. First, in a fully-parallel implementation where P=N2 , the latency of SSC decoding is O(N1−1/μ) , which is sublinear in the block length. This recovers a result from an earlier work. Second, in a fully-serial implementation where P=1 , the latency of SSC decoding scales as O(Nlog2log2N) . The multiplicative constant is also calculated: we show that the latency of SSC decoding when P=1 is given by (2+o(1))Nlog2log2N . Third, in a semi-parallel implementation, the smallest P that gives the same latency as that of the fully-parallel implementation is P=N1/μ . The tightness of our bound on SSC decoding latency and the applicability of the foregoing results is validated through extensive simulations."}],"oa_version":"Preprint","date_updated":"2025-04-15T07:50:11Z"},{"publication":"48th International Colloquium on Automata, Languages, and Programming","ec_funded":1,"conference":{"location":"Glasgow, Scotland","start_date":"2021-07-12","end_date":"2021-07-16","name":"ICALP: Automata, Languages and Programming"},"publication_identifier":{"isbn":["978-3-95977-195-5"],"issn":["1868-8969"]},"article_processing_charge":"No","date_created":"2021-09-27T14:33:15Z","status":"public","file_date_updated":"2021-10-01T08:49:26Z","acknowledgement":"Krishnendu Chatterjee: Supported by the ERC CoG 863818 (ForM-SMArt). Monika Henzinger: Supported by the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N. Sagar Sudhir Kale: Partially supported by the Vienna Science and Technology Fund (WWTF) through project ICT15-003. Alexander Svozil: Fully supported by the Vienna Science and Technology Fund (WWTF) through project ICT15-003.","article_number":"124","oa_version":"Published Version","date_updated":"2025-05-14T10:55:19Z","intvolume":"       198","abstract":[{"text":"Graphs and games on graphs are fundamental models for the analysis of reactive systems, in particular, for model-checking and the synthesis of reactive systems. The class of ω-regular languages provides a robust specification formalism for the desired properties of reactive systems. In the classical infinitary formulation of the liveness part of an ω-regular specification, a \"good\" event must happen eventually without any bound between the good events. A stronger notion of liveness is bounded liveness, which requires that good events happen within d transitions. Given a graph or a game graph with n vertices, m edges, and a bounded liveness objective, the previous best-known algorithmic bounds are as follows: (i) O(dm) for graphs, which in the worst-case is O(n³); and (ii) O(n² d²) for games on graphs. Our main contributions improve these long-standing algorithmic bounds. For graphs we present: (i) a randomized algorithm with one-sided error with running time O(n^{2.5} log n) for the bounded liveness objectives; and (ii) a deterministic linear-time algorithm for the complement of bounded liveness objectives. For games on graphs, we present an O(n² d) time algorithm for the bounded liveness objectives.","lang":"eng"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"full_name":"Henzinger, Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"},{"last_name":"Kale","full_name":"Kale, Sagar Sudhir","first_name":"Sagar Sudhir"},{"full_name":"Svozil, Alexander","last_name":"Svozil","first_name":"Alexander"}],"has_accepted_license":"1","department":[{"_id":"KrCh"}],"project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"title":"Faster algorithms for bounded liveness in graphs and game graphs","ddc":["000"],"day":"02","alternative_title":["LIPIcs"],"quality_controlled":"1","year":"2021","file":[{"relation":"main_file","creator":"cchlebak","success":1,"date_created":"2021-10-01T08:49:26Z","date_updated":"2021-10-01T08:49:26Z","content_type":"application/pdf","file_size":854576,"file_id":"10062","access_level":"open_access","checksum":"5a3fed8dbba8c088cbeac1e24cc10bc5","file_name":"2021_LIPIcs_Chatterjee.pdf"}],"oa":1,"date_published":"2021-07-02T00:00:00Z","doi":"10.4230/LIPIcs.ICALP.2021.124","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","citation":{"ista":"Chatterjee K, Henzinger M, Kale SS, Svozil A. 2021. Faster algorithms for bounded liveness in graphs and game graphs. 48th International Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 198, 124.","mla":"Chatterjee, Krishnendu, et al. “Faster Algorithms for Bounded Liveness in Graphs and Game Graphs.” <i>48th International Colloquium on Automata, Languages, and Programming</i>, vol. 198, 124, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2021.124\">10.4230/LIPIcs.ICALP.2021.124</a>.","chicago":"Chatterjee, Krishnendu, Monika Henzinger, Sagar Sudhir Kale, and Alexander Svozil. “Faster Algorithms for Bounded Liveness in Graphs and Game Graphs.” In <i>48th International Colloquium on Automata, Languages, and Programming</i>, Vol. 198. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2021.124\">https://doi.org/10.4230/LIPIcs.ICALP.2021.124</a>.","short":"K. Chatterjee, M. Henzinger, S.S. Kale, A. Svozil, in:, 48th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","ieee":"K. Chatterjee, M. Henzinger, S. S. Kale, and A. Svozil, “Faster algorithms for bounded liveness in graphs and game graphs,” in <i>48th International Colloquium on Automata, Languages, and Programming</i>, Glasgow, Scotland, 2021, vol. 198.","ama":"Chatterjee K, Henzinger M, Kale SS, Svozil A. Faster algorithms for bounded liveness in graphs and game graphs. In: <i>48th International Colloquium on Automata, Languages, and Programming</i>. Vol 198. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2021.124\">10.4230/LIPIcs.ICALP.2021.124</a>","apa":"Chatterjee, K., Henzinger, M., Kale, S. S., &#38; Svozil, A. (2021). Faster algorithms for bounded liveness in graphs and game graphs. In <i>48th International Colloquium on Automata, Languages, and Programming</i> (Vol. 198). Glasgow, Scotland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2021.124\">https://doi.org/10.4230/LIPIcs.ICALP.2021.124</a>"},"type":"conference","volume":198,"corr_author":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"_id":"10054","month":"07","scopus_import":"1"},{"article_processing_charge":"No","status":"public","file_date_updated":"2021-10-01T09:55:00Z","date_created":"2021-09-27T14:33:15Z","acknowledgement":"This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411. I wish to thank Michaël Cadilhac, Emmanuel Filiot and Charles Paperman for their valuable insights concerning Green’s relations.","publication":"38th International Symposium on Theoretical Aspects of Computer Science","conference":{"end_date":"2021-03-19","name":"STACS: Symposium on Theoretical Aspects of Computer Science","start_date":"2021-03-16","location":"Saarbrücken, Germany"},"ec_funded":1,"publication_identifier":{"isbn":["978-3-9597-7180-1"],"issn":["1868-8969"]},"has_accepted_license":"1","isi":1,"project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"department":[{"_id":"KrCh"}],"title":"A Ramsey theorem for finite monoids","day":"10","alternative_title":["LIPIcs"],"ddc":["000"],"date_updated":"2025-05-14T10:55:11Z","intvolume":"       187","oa_version":"Published Version","article_number":"44","abstract":[{"text":"Repeated idempotent elements are commonly used to characterise iterable behaviours in abstract models of computation. Therefore, given a monoid M, it is natural to ask how long a sequence of elements of M needs to be to ensure the presence of consecutive idempotent factors. This question is formalised through the notion of the Ramsey function R_M associated to M, obtained by mapping every k ∈ ℕ to the minimal integer R_M(k) such that every word u ∈ M^* of length R_M(k) contains k consecutive non-empty factors that correspond to the same idempotent element of M. In this work, we study the behaviour of the Ramsey function R_M by investigating the regular 𝒟-length of M, defined as the largest size L(M) of a submonoid of M isomorphic to the set of natural numbers {1,2, …, L(M)} equipped with the max operation. We show that the regular 𝒟-length of M determines the degree of R_M, by proving that k^L(M) ≤ R_M(k) ≤ (k|M|⁴)^L(M). To allow applications of this result, we provide the value of the regular 𝒟-length of diverse monoids. In particular, we prove that the full monoid of n × n Boolean matrices, which is used to express transition monoids of non-deterministic automata, has a regular 𝒟-length of (n²+n+2)/2.","lang":"eng"}],"author":[{"first_name":"Ismael R","id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","last_name":"Jecker","full_name":"Jecker, Ismael R"}],"oa":1,"file":[{"creator":"cchlebak","relation":"main_file","success":1,"date_created":"2021-10-01T09:55:00Z","date_updated":"2021-10-01T09:55:00Z","content_type":"application/pdf","file_size":720250,"file_id":"10063","access_level":"open_access","checksum":"17432a05733f408de300e17e390a90e4","file_name":"2021_LIPIcs_Jecker.pdf"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","language":[{"iso":"eng"}],"date_published":"2021-03-10T00:00:00Z","doi":"10.4230/LIPIcs.STACS.2021.44","year":"2021","quality_controlled":"1","external_id":{"isi":["000635691700044"]},"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"_id":"10055","month":"03","scopus_import":"1","citation":{"short":"I.R. Jecker, in:, 38th International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","chicago":"Jecker, Ismael R. “A Ramsey Theorem for Finite Monoids.” In <i>38th International Symposium on Theoretical Aspects of Computer Science</i>, Vol. 187. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.44\">https://doi.org/10.4230/LIPIcs.STACS.2021.44</a>.","mla":"Jecker, Ismael R. “A Ramsey Theorem for Finite Monoids.” <i>38th International Symposium on Theoretical Aspects of Computer Science</i>, vol. 187, 44, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.44\">10.4230/LIPIcs.STACS.2021.44</a>.","ista":"Jecker IR. 2021. A Ramsey theorem for finite monoids. 38th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 187, 44.","ama":"Jecker IR. A Ramsey theorem for finite monoids. In: <i>38th International Symposium on Theoretical Aspects of Computer Science</i>. Vol 187. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.44\">10.4230/LIPIcs.STACS.2021.44</a>","apa":"Jecker, I. R. (2021). A Ramsey theorem for finite monoids. In <i>38th International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 187). Saarbrücken, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2021.44\">https://doi.org/10.4230/LIPIcs.STACS.2021.44</a>","ieee":"I. R. Jecker, “A Ramsey theorem for finite monoids,” in <i>38th International Symposium on Theoretical Aspects of Computer Science</i>, Saarbrücken, Germany, 2021, vol. 187."},"publication_status":"published","volume":187,"type":"conference","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"day":"30","title":"Entanglement transitions from restricted Boltzmann machines","project":[{"_id":"23841C26-32DE-11EA-91FC-C7463DDC885E","grant_number":"850899","call_identifier":"H2020","name":"Non-Ergodic Quantum Matter: Universality, Dynamics and Control"}],"department":[{"_id":"MaSe"}],"isi":1,"author":[{"full_name":"Medina Ramos, Raimel A","last_name":"Medina Ramos","orcid":"0000-0002-5383-2869","id":"CE680B90-D85A-11E9-B684-C920E6697425","first_name":"Raimel A"},{"full_name":"Vasseur, Romain","last_name":"Vasseur","first_name":"Romain"},{"orcid":"0000-0002-2399-5827","first_name":"Maksym","id":"47809E7E-F248-11E8-B48F-1D18A9856A87","full_name":"Serbyn, Maksym","last_name":"Serbyn"}],"abstract":[{"lang":"eng","text":"The search for novel entangled phases of matter has lead to the recent discovery of a new class of “entanglement transitions,” exemplified by random tensor networks and monitored quantum circuits. Most known examples can be understood as some classical ordering transitions in an underlying statistical mechanics model, where entanglement maps onto the free-energy cost of inserting a domain wall. In this paper we study the possibility of entanglement transitions driven by physics beyond such statistical mechanics mappings. Motivated by recent applications of neural-network-inspired variational Ansätze, we investigate under what conditions on the variational parameters these Ansätze can capture an entanglement transition. We study the entanglement scaling of short-range restricted Boltzmann machine (RBM) quantum states with random phases. For uncorrelated random phases, we analytically demonstrate the absence of an entanglement transition and reveal subtle finite-size effects in finite-size numerical simulations. Introducing phases with correlations decaying as 1/r^α in real space, we observe three regions with a different scaling of entanglement entropy depending on the exponent α. We study the nature of the transition between these regions, finding numerical evidence for critical behavior. Our work establishes the presence of long-range correlated phases in RBM-based wave functions as a required ingredient for entanglement transitions."}],"date_updated":"2026-04-07T12:43:22Z","intvolume":"       104","oa_version":"Preprint","article_number":"104205","acknowledgement":"We would like to thank S. De Nicola, P. Brighi, and V. Karle for fruitful discussions and valuable feedback on the manuscript. R.M. and M.S. acknowledge support by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (Grant Agreement No. 850899). R.V. acknowledges support from the US Department of Energy, Office of Science, Basic Energy Sciences, under Early Career Award No. DE-SC0019168, and the Alfred P. Sloan Foundation through a Sloan Research Fellowship.","status":"public","date_created":"2021-10-02T09:03:42Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2107.05735"}],"article_processing_charge":"No","publication_identifier":{"eissn":["2469-9969"],"issn":["2469-9950"]},"ec_funded":1,"related_material":{"record":[{"status":"public","id":"17208","relation":"dissertation_contains"}]},"publication":"Physical Review B","scopus_import":"1","month":"09","arxiv":1,"_id":"10067","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","volume":104,"type":"journal_article","corr_author":"1","citation":{"ista":"Medina Ramos RA, Vasseur R, Serbyn M. 2021. Entanglement transitions from restricted Boltzmann machines. Physical Review B. 104(10), 104205.","chicago":"Medina Ramos, Raimel A, Romain Vasseur, and Maksym Serbyn. “Entanglement Transitions from Restricted Boltzmann Machines.” <i>Physical Review B</i>. American Physical Society, 2021. <a href=\"https://doi.org/10.1103/physrevb.104.104205\">https://doi.org/10.1103/physrevb.104.104205</a>.","mla":"Medina Ramos, Raimel A., et al. “Entanglement Transitions from Restricted Boltzmann Machines.” <i>Physical Review B</i>, vol. 104, no. 10, 104205, American Physical Society, 2021, doi:<a href=\"https://doi.org/10.1103/physrevb.104.104205\">10.1103/physrevb.104.104205</a>.","short":"R.A. Medina Ramos, R. Vasseur, M. Serbyn, Physical Review B 104 (2021).","ieee":"R. A. Medina Ramos, R. Vasseur, and M. Serbyn, “Entanglement transitions from restricted Boltzmann machines,” <i>Physical Review B</i>, vol. 104, no. 10. American Physical Society, 2021.","ama":"Medina Ramos RA, Vasseur R, Serbyn M. Entanglement transitions from restricted Boltzmann machines. <i>Physical Review B</i>. 2021;104(10). doi:<a href=\"https://doi.org/10.1103/physrevb.104.104205\">10.1103/physrevb.104.104205</a>","apa":"Medina Ramos, R. A., Vasseur, R., &#38; Serbyn, M. (2021). Entanglement transitions from restricted Boltzmann machines. <i>Physical Review B</i>. American Physical Society. <a href=\"https://doi.org/10.1103/physrevb.104.104205\">https://doi.org/10.1103/physrevb.104.104205</a>"},"publication_status":"published","issue":"10","language":[{"iso":"eng"}],"doi":"10.1103/physrevb.104.104205","publisher":"American Physical Society","date_published":"2021-09-30T00:00:00Z","oa":1,"article_type":"original","external_id":{"isi":["000704414400002"],"arxiv":["2107.05735"]},"year":"2021","quality_controlled":"1"},{"publication_identifier":{"eissn":["2045-2322"]},"publication":"Scientific Reports","acknowledgement":"This project was funded by an SNSF Eccellenza Grant to MRR (PCEGP3-181181), and by core funding from the Institute of Science and Technology Austria. We would like to thank the participants of the study and all the midwives and doctors for the computerized obstetrical data.","date_created":"2021-10-03T22:01:21Z","status":"public","file_date_updated":"2021-10-05T14:56:48Z","article_processing_charge":"Yes","author":[{"last_name":"Robinson","full_name":"Robinson, Matthew Richard","id":"E5D42276-F5DA-11E9-8E24-6303E6697425","first_name":"Matthew Richard","orcid":"0000-0001-8982-8813"},{"first_name":"Marion","last_name":"Patxot","full_name":"Patxot, Marion"},{"first_name":"Miloš","last_name":"Stojanov","full_name":"Stojanov, Miloš"},{"first_name":"Sabine","last_name":"Blum","full_name":"Blum, Sabine"},{"first_name":"David","last_name":"Baud","full_name":"Baud, David"}],"abstract":[{"text":"The extent to which women differ in the course of blood cell counts throughout pregnancy, and the importance of these changes to pregnancy outcomes has not been well defined. Here, we develop a series of statistical analyses of repeated measures data to reveal the degree to which women differ in the course of pregnancy, predict the changes that occur, and determine the importance of these changes for post-partum hemorrhage (PPH) which is one of the leading causes of maternal mortality. We present a prospective cohort of 4082 births recorded at the University Hospital, Lausanne, Switzerland between 2009 and 2014 where full labour records could be obtained, along with complete blood count data taken at hospital admission. We find significant differences, at a [Formula: see text] level, among women in how blood count values change through pregnancy for mean corpuscular hemoglobin, mean corpuscular volume, mean platelet volume, platelet count and red cell distribution width. We find evidence that almost all complete blood count values show trimester-specific associations with PPH. For example, high platelet count (OR 1.20, 95% CI 1.01-1.53), high mean platelet volume (OR 1.58, 95% CI 1.04-2.08), and high erythrocyte levels (OR 1.36, 95% CI 1.01-1.57) in trimester 1 increased PPH, but high values in trimester 3 decreased PPH risk (OR 0.85, 0.79, 0.67 respectively). We show that differences among women in the course of blood cell counts throughout pregnancy have an important role in shaping pregnancy outcome and tracking blood count value changes through pregnancy improves identification of women at increased risk of postpartum hemorrhage. This study provides greater understanding of the complex changes in blood count values that occur through pregnancy and provides indicators to guide the stratification of patients into risk groups.","lang":"eng"}],"article_number":"19238","oa_version":"Published Version","date_updated":"2024-10-09T21:00:57Z","intvolume":"        11","ddc":["618"],"day":"28","title":"Postpartum hemorrhage risk is driven by changes in blood composition through pregnancy","department":[{"_id":"MaRo"}],"isi":1,"has_accepted_license":"1","external_id":{"isi":["000701575500083"],"pmid":["34584125"]},"quality_controlled":"1","year":"2021","language":[{"iso":"eng"}],"date_published":"2021-09-28T00:00:00Z","publisher":"Springer Nature","doi":"10.1038/s41598-021-98411-z","file":[{"date_created":"2021-10-05T14:56:48Z","success":1,"relation":"main_file","creator":"cchlebak","access_level":"open_access","checksum":"f002ec22f609f58e1263b79e7f79601e","file_name":"2021_ScientificReports_Robinson.pdf","file_id":"10091","file_size":6970368,"date_updated":"2021-10-05T14:56:48Z","content_type":"application/pdf"}],"oa":1,"article_type":"original","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","type":"journal_article","corr_author":"1","volume":11,"publication_status":"published","citation":{"ieee":"M. R. Robinson, M. Patxot, M. Stojanov, S. Blum, and D. Baud, “Postpartum hemorrhage risk is driven by changes in blood composition through pregnancy,” <i>Scientific Reports</i>, vol. 11. Springer Nature, 2021.","apa":"Robinson, M. R., Patxot, M., Stojanov, M., Blum, S., &#38; Baud, D. (2021). Postpartum hemorrhage risk is driven by changes in blood composition through pregnancy. <i>Scientific Reports</i>. Springer Nature. <a href=\"https://doi.org/10.1038/s41598-021-98411-z\">https://doi.org/10.1038/s41598-021-98411-z</a>","ama":"Robinson MR, Patxot M, Stojanov M, Blum S, Baud D. Postpartum hemorrhage risk is driven by changes in blood composition through pregnancy. <i>Scientific Reports</i>. 2021;11. doi:<a href=\"https://doi.org/10.1038/s41598-021-98411-z\">10.1038/s41598-021-98411-z</a>","mla":"Robinson, Matthew Richard, et al. “Postpartum Hemorrhage Risk Is Driven by Changes in Blood Composition through Pregnancy.” <i>Scientific Reports</i>, vol. 11, 19238, Springer Nature, 2021, doi:<a href=\"https://doi.org/10.1038/s41598-021-98411-z\">10.1038/s41598-021-98411-z</a>.","ista":"Robinson MR, Patxot M, Stojanov M, Blum S, Baud D. 2021. Postpartum hemorrhage risk is driven by changes in blood composition through pregnancy. Scientific Reports. 11, 19238.","chicago":"Robinson, Matthew Richard, Marion Patxot, Miloš Stojanov, Sabine Blum, and David Baud. “Postpartum Hemorrhage Risk Is Driven by Changes in Blood Composition through Pregnancy.” <i>Scientific Reports</i>. Springer Nature, 2021. <a href=\"https://doi.org/10.1038/s41598-021-98411-z\">https://doi.org/10.1038/s41598-021-98411-z</a>.","short":"M.R. Robinson, M. Patxot, M. Stojanov, S. Blum, D. Baud, Scientific Reports 11 (2021)."},"pmid":1,"month":"09","scopus_import":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"_id":"10069"},{"scopus_import":"1","month":"09","arxiv":1,"_id":"10070","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","type":"journal_article","volume":281,"corr_author":"1","publication_status":"published","citation":{"ama":"Dello Schiavo L, Suzuki K. Rademacher-type theorems and Sobolev-to-Lipschitz properties for strongly local Dirichlet spaces. <i>Journal of Functional Analysis</i>. 2021;281(11). doi:<a href=\"https://doi.org/10.1016/j.jfa.2021.109234\">10.1016/j.jfa.2021.109234</a>","apa":"Dello Schiavo, L., &#38; Suzuki, K. (2021). Rademacher-type theorems and Sobolev-to-Lipschitz properties for strongly local Dirichlet spaces. <i>Journal of Functional Analysis</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jfa.2021.109234\">https://doi.org/10.1016/j.jfa.2021.109234</a>","ieee":"L. Dello Schiavo and K. Suzuki, “Rademacher-type theorems and Sobolev-to-Lipschitz properties for strongly local Dirichlet spaces,” <i>Journal of Functional Analysis</i>, vol. 281, no. 11. Elsevier, 2021.","ista":"Dello Schiavo L, Suzuki K. 2021. Rademacher-type theorems and Sobolev-to-Lipschitz properties for strongly local Dirichlet spaces. Journal of Functional Analysis. 281(11), 109234.","mla":"Dello Schiavo, Lorenzo, and Kohei Suzuki. “Rademacher-Type Theorems and Sobolev-to-Lipschitz Properties for Strongly Local Dirichlet Spaces.” <i>Journal of Functional Analysis</i>, vol. 281, no. 11, 109234, Elsevier, 2021, doi:<a href=\"https://doi.org/10.1016/j.jfa.2021.109234\">10.1016/j.jfa.2021.109234</a>.","chicago":"Dello Schiavo, Lorenzo, and Kohei Suzuki. “Rademacher-Type Theorems and Sobolev-to-Lipschitz Properties for Strongly Local Dirichlet Spaces.” <i>Journal of Functional Analysis</i>. Elsevier, 2021. <a href=\"https://doi.org/10.1016/j.jfa.2021.109234\">https://doi.org/10.1016/j.jfa.2021.109234</a>.","short":"L. Dello Schiavo, K. Suzuki, Journal of Functional Analysis 281 (2021)."},"language":[{"iso":"eng"}],"doi":"10.1016/j.jfa.2021.109234","date_published":"2021-09-15T00:00:00Z","publisher":"Elsevier","issue":"11","oa":1,"article_type":"original","external_id":{"isi":["000703896600005"],"arxiv":["2008.01492"]},"quality_controlled":"1","year":"2021","day":"15","title":"Rademacher-type theorems and Sobolev-to-Lipschitz properties for strongly local Dirichlet spaces","department":[{"_id":"JaMa"}],"project":[{"name":"Taming Complexity in Partial Differential Systems","_id":"fc31cba2-9c52-11eb-aca3-ff467d239cd2","grant_number":"F6504"},{"name":"Optimal Transport and Stochastic Dynamics","_id":"256E75B8-B435-11E9-9278-68D0E5697425","grant_number":"716117","call_identifier":"H2020"}],"isi":1,"author":[{"full_name":"Dello Schiavo, Lorenzo","last_name":"Dello Schiavo","orcid":"0000-0002-9881-6870","id":"ECEBF480-9E4F-11EA-B557-B0823DDC885E","first_name":"Lorenzo"},{"first_name":"Kohei","last_name":"Suzuki","full_name":"Suzuki, Kohei"}],"abstract":[{"text":"We extensively discuss the Rademacher and Sobolev-to-Lipschitz properties for generalized intrinsic distances on strongly local Dirichlet spaces possibly without square field operator. We present many non-smooth and infinite-dimensional examples. As an application, we prove the integral Varadhan short-time asymptotic with respect to a given distance function for a large class of strongly local Dirichlet forms.","lang":"eng"}],"article_number":"109234","oa_version":"Preprint","date_updated":"2025-04-14T07:27:45Z","intvolume":"       281","acknowledgement":"The authors are grateful to Professor Kazuhiro Kuwae for kindly providing a copy of [49]. They are also grateful to Dr. Bang-Xian Han for helpful discussions on the Sobolev-to-Lipschitz property on metric measure spaces. They wish to express their deepest gratitude to an anonymous Reviewer, whose punctual remarks and comments greatly improved the accessibility and overall quality of the initial submission. This work was completed while L.D.S. was a member of the Institut für Angewandte Mathematik of the University of Bonn. He acknowledges funding of his position at that time by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) through the Sonderforschungsbereich (Sfb, Collaborative Research Center) 1060 - project number 211504053. He also acknowledges funding of his current position by the Austrian Science Fund (FWF) grant F65, and by the European Research Council (ERC, grant No. 716117, awarded to Prof. Dr. Jan Maas). K.S. gratefully acknowledges funding by: the JSPS Overseas Research Fellowships, Grant Nr. 290142; World Premier International Research Center Initiative (WPI), MEXT, Japan; and JSPS Grant-in-Aid for Scientific Research on Innovative Areas “Discrete Geometric Analysis for Materials Design”, Grant Number 17H06465.","date_created":"2021-10-03T22:01:21Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2008.01492"}],"status":"public","article_processing_charge":"No","publication_identifier":{"eissn":["1096-0783"],"issn":["0022-1236"]},"ec_funded":1,"publication":"Journal of Functional Analysis"},{"scopus_import":"1","month":"10","_id":"10071","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","citation":{"ama":"Adams H, Kourimska H, Heiss T, Percival S, Ziegelmeier L. How to tutorial-a-thon. <i>Notices of the American Mathematical Society</i>. 2021;68(9):1511-1514. doi:<a href=\"https://doi.org/10.1090/noti2349\">10.1090/noti2349</a>","apa":"Adams, H., Kourimska, H., Heiss, T., Percival, S., &#38; Ziegelmeier, L. (2021). How to tutorial-a-thon. <i>Notices of the American Mathematical Society</i>. American Mathematical Society. <a href=\"https://doi.org/10.1090/noti2349\">https://doi.org/10.1090/noti2349</a>","ieee":"H. Adams, H. Kourimska, T. Heiss, S. Percival, and L. Ziegelmeier, “How to tutorial-a-thon,” <i>Notices of the American Mathematical Society</i>, vol. 68, no. 9. American Mathematical Society, pp. 1511–1514, 2021.","short":"H. Adams, H. Kourimska, T. Heiss, S. Percival, L. Ziegelmeier, Notices of the American Mathematical Society 68 (2021) 1511–1514.","ista":"Adams H, Kourimska H, Heiss T, Percival S, Ziegelmeier L. 2021. How to tutorial-a-thon. Notices of the American Mathematical Society. 68(9), 1511–1514.","mla":"Adams, Henry, et al. “How to Tutorial-a-Thon.” <i>Notices of the American Mathematical Society</i>, vol. 68, no. 9, American Mathematical Society, 2021, pp. 1511–14, doi:<a href=\"https://doi.org/10.1090/noti2349\">10.1090/noti2349</a>.","chicago":"Adams, Henry, Hana Kourimska, Teresa Heiss, Sarah Percival, and Lori Ziegelmeier. “How to Tutorial-a-Thon.” <i>Notices of the American Mathematical Society</i>. American Mathematical Society, 2021. <a href=\"https://doi.org/10.1090/noti2349\">https://doi.org/10.1090/noti2349</a>."},"volume":68,"type":"journal_article","oa":1,"language":[{"iso":"eng"}],"date_published":"2021-10-01T00:00:00Z","doi":"10.1090/noti2349","publisher":"American Mathematical Society","issue":"9","article_type":"letter_note","page":"1511-1514","quality_controlled":"1","year":"2021","title":"How to tutorial-a-thon","ddc":["500"],"day":"01","alternative_title":["Early Career"],"department":[{"_id":"HeEd"}],"author":[{"full_name":"Adams, Henry","last_name":"Adams","first_name":"Henry"},{"last_name":"Kourimska","full_name":"Kourimska, Hana","id":"D9B8E14C-3C26-11EA-98F5-1F833DDC885E","first_name":"Hana","orcid":"0000-0001-7841-0091"},{"last_name":"Heiss","full_name":"Heiss, Teresa","first_name":"Teresa","id":"4879BB4E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1780-2689"},{"full_name":"Percival, Sarah","last_name":"Percival","first_name":"Sarah"},{"last_name":"Ziegelmeier","full_name":"Ziegelmeier, Lori","first_name":"Lori"}],"oa_version":"Published Version","intvolume":"        68","date_updated":"2026-06-18T08:36:13Z","main_file_link":[{"open_access":"1","url":"http://www.ams.org/notices/"}],"date_created":"2021-10-03T22:01:22Z","status":"public","article_processing_charge":"No","publication_identifier":{"issn":["0002-9920"],"eissn":["1088-9477"]},"publication":"Notices of the American Mathematical Society"},{"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"_id":"10072","arxiv":1,"month":"09","scopus_import":"1","publication_status":"published","citation":{"mla":"Harris, David G., et al. “A New Notion of Commutativity for the Algorithmic Lovász Local Lemma.” <i>Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques</i>, vol. 207, 31, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31\">10.4230/LIPIcs.APPROX/RANDOM.2021.31</a>.","ista":"Harris DG, Iliopoulos F, Kolmogorov V. 2021. A new notion of commutativity for the algorithmic Lovász Local Lemma. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX/RANDOM: Approximation Algorithms for Combinatorial Optimization Problems/ Randomization and Computation, LIPIcs, vol. 207, 31.","chicago":"Harris, David G., Fotis Iliopoulos, and Vladimir Kolmogorov. “A New Notion of Commutativity for the Algorithmic Lovász Local Lemma.” In <i>Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques</i>, Vol. 207. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31\">https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31</a>.","short":"D.G. Harris, F. Iliopoulos, V. Kolmogorov, in:, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","ieee":"D. G. Harris, F. Iliopoulos, and V. Kolmogorov, “A new notion of commutativity for the algorithmic Lovász Local Lemma,” in <i>Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques</i>, Virtual, 2021, vol. 207.","ama":"Harris DG, Iliopoulos F, Kolmogorov V. A new notion of commutativity for the algorithmic Lovász Local Lemma. In: <i>Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques</i>. Vol 207. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31\">10.4230/LIPIcs.APPROX/RANDOM.2021.31</a>","apa":"Harris, D. G., Iliopoulos, F., &#38; Kolmogorov, V. (2021). A new notion of commutativity for the algorithmic Lovász Local Lemma. In <i>Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques</i> (Vol. 207). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31\">https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31</a>"},"type":"conference","volume":207,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"creator":"cchlebak","relation":"main_file","success":1,"date_created":"2021-10-06T13:51:54Z","date_updated":"2021-10-06T13:51:54Z","content_type":"application/pdf","file_size":804472,"file_id":"10098","checksum":"9d2544d53aa5b01565c6891d97a4d765","access_level":"open_access","file_name":"2021_LIPIcs_Harris.pdf"}],"oa":1,"language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2021-09-15T00:00:00Z","doi":"10.4230/LIPIcs.APPROX/RANDOM.2021.31","quality_controlled":"1","year":"2021","external_id":{"arxiv":["2008.05569"]},"has_accepted_license":"1","department":[{"_id":"VlKo"}],"project":[{"name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7","grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"title":"A new notion of commutativity for the algorithmic Lovász Local Lemma","ddc":["000"],"alternative_title":["LIPIcs"],"day":"15","article_number":"31","oa_version":"Published Version","intvolume":"       207","date_updated":"2026-02-10T09:59:59Z","abstract":[{"text":"The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combinatorics which can be used to establish the existence of objects that satisfy certain properties. The breakthrough paper of Moser and Tardos and follow-up works revealed that the LLL has intimate connections with a class of stochastic local search algorithms for finding such desirable objects. In particular, it can be seen as a sufficient condition for this type of algorithms to converge fast. Besides conditions for existence of and fast convergence to desirable objects, one may naturally ask further questions regarding properties of these algorithms. For instance, \"are they parallelizable?\", \"how many solutions can they output?\", \"what is the expected \"weight\" of a solution?\", etc. These questions and more have been answered for a class of LLL-inspired algorithms called commutative. In this paper we introduce a new, very natural and more general notion of commutativity (essentially matrix commutativity) which allows us to show a number of new refined properties of LLL-inspired local search algorithms with significantly simpler proofs.","lang":"eng"}],"author":[{"first_name":"David G.","last_name":"Harris","full_name":"Harris, David G."},{"first_name":"Fotis","full_name":"Iliopoulos, Fotis","last_name":"Iliopoulos"},{"first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov"}],"article_processing_charge":"Yes","date_created":"2021-10-03T22:01:22Z","status":"public","file_date_updated":"2021-10-06T13:51:54Z","acknowledgement":"Fotis Iliopoulos: This material is based upon work directly supported by the IAS Fund for Math and indirectly supported by the National Science Foundation Grant No. CCF-1900460. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. This work is also supported by the National Science Foundation Grant No. CCF-1815328.\r\nVladimir Kolmogorov: Supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160.","publication":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","related_material":{"record":[{"relation":"later_version","id":"21143","status":"public"}]},"ec_funded":1,"conference":{"end_date":"2021-08-18","name":"APPROX/RANDOM: Approximation Algorithms for Combinatorial Optimization Problems/ Randomization and Computation","start_date":"2021-08-16","location":"Virtual"},"publication_identifier":{"isbn":["978-3-9597-7207-5"],"issn":["1868-8969"]}},{"oa":1,"file":[{"date_updated":"2021-10-14T11:56:39Z","content_type":"application/pdf","file_size":4404141,"file_id":"10140","access_level":"open_access","checksum":"4929dfc673a3ae77c010b6174279cc1d","file_name":"2021_Materials_Chang.pdf","creator":"cchlebak","relation":"main_file","success":1,"date_created":"2021-10-14T11:56:39Z"}],"issue":"18","doi":"10.3390/ma14185416","publisher":"MDPI","language":[{"iso":"eng"}],"date_published":"2021-09-19T00:00:00Z","article_type":"original","external_id":{"isi":["000700689400001"],"pmid":["34576640"]},"year":"2021","quality_controlled":"1","scopus_import":"1","month":"09","pmid":1,"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"_id":"10073","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"apa":"Chang, C., &#38; Ibáñez, M. (2021). Enhanced thermoelectric performance by surface engineering in SnTe-PbS nanocomposites. <i>Materials</i>. MDPI. <a href=\"https://doi.org/10.3390/ma14185416\">https://doi.org/10.3390/ma14185416</a>","ama":"Chang C, Ibáñez M. Enhanced thermoelectric performance by surface engineering in SnTe-PbS nanocomposites. <i>Materials</i>. 2021;14(18). doi:<a href=\"https://doi.org/10.3390/ma14185416\">10.3390/ma14185416</a>","ieee":"C. Chang and M. Ibáñez, “Enhanced thermoelectric performance by surface engineering in SnTe-PbS nanocomposites,” <i>Materials</i>, vol. 14, no. 18. MDPI, 2021.","short":"C. Chang, M. Ibáñez, Materials 14 (2021).","mla":"Chang, Cheng, and Maria Ibáñez. “Enhanced Thermoelectric Performance by Surface Engineering in SnTe-PbS Nanocomposites.” <i>Materials</i>, vol. 14, no. 18, 5416, MDPI, 2021, doi:<a href=\"https://doi.org/10.3390/ma14185416\">10.3390/ma14185416</a>.","ista":"Chang C, Ibáñez M. 2021. Enhanced thermoelectric performance by surface engineering in SnTe-PbS nanocomposites. Materials. 14(18), 5416.","chicago":"Chang, Cheng, and Maria Ibáñez. “Enhanced Thermoelectric Performance by Surface Engineering in SnTe-PbS Nanocomposites.” <i>Materials</i>. MDPI, 2021. <a href=\"https://doi.org/10.3390/ma14185416\">https://doi.org/10.3390/ma14185416</a>."},"publication_status":"published","volume":14,"type":"journal_article","corr_author":"1","status":"public","file_date_updated":"2021-10-14T11:56:39Z","date_created":"2021-10-03T22:01:23Z","acknowledgement":"The authors thank the EMF facility in IST Austria for providing SEM and EDX measurements.\r\n","article_processing_charge":"Yes","publication_identifier":{"eissn":["1996-1944"]},"acknowledged_ssus":[{"_id":"EM-Fac"}],"publication":"Materials","title":"Enhanced thermoelectric performance by surface engineering in SnTe-PbS nanocomposites","day":"19","ddc":["540"],"isi":1,"has_accepted_license":"1","project":[{"grant_number":"M02889","_id":"9B8804FC-BA93-11EA-9121-9846C619BF3A","name":"Bottom-up Engineering for Thermoelectric Applications"}],"department":[{"_id":"MaIb"}],"author":[{"full_name":"Chang, Cheng","last_name":"Chang","orcid":"0000-0002-9515-4277","id":"9E331C2E-9F27-11E9-AE48-5033E6697425","first_name":"Cheng"},{"full_name":"Ibáñez, Maria","last_name":"Ibáñez","orcid":"0000-0001-5013-2843","id":"43C61214-F248-11E8-B48F-1D18A9856A87","first_name":"Maria"}],"intvolume":"        14","date_updated":"2025-04-14T09:29:32Z","oa_version":"Published Version","article_number":"5416","abstract":[{"lang":"eng","text":"Thermoelectric materials enable the direct conversion between heat and electricity. SnTe is a promising candidate due to its high charge transport performance. Here, we prepared SnTe nanocomposites by employing an aqueous method to synthetize SnTe nanoparticles (NP), followed by a unique surface treatment prior NP consolidation. This synthetic approach allowed optimizing the charge and phonon transport synergistically. The novelty of this strategy was the use of a soluble PbS molecular complex prepared using a thiol-amine solvent mixture that upon blending is adsorbed on the SnTe NP surface. Upon consolidation with spark plasma sintering, SnTe-PbS nanocomposite is formed. The presence of PbS complexes significantly compensates for the Sn vacancy and increases the average grain size of the nanocomposite, thus improving the carrier mobility. Moreover, lattice thermal conductivity is also reduced by the Pb and S-induced mass and strain fluctuation. As a result, an enhanced ZT of ca. 0.8 is reached at 873 K. Our finding provides a novel strategy to conduct rational surface treatment on NP-based thermoelectrics."}]},{"date_created":"2021-10-03T22:01:23Z","status":"public","file_date_updated":"2021-10-06T12:44:05Z","acknowledgement":"Ismaël Jecker: Funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 754411. Karoliina Lehtinen: Funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 892704.","article_processing_charge":"No","ec_funded":1,"conference":{"start_date":"2021-08-23","location":"Tallinn, Estonia","end_date":"2021-08-27","name":"MFCS: Mathematical Foundations of Computer Science"},"publication_identifier":{"isbn":["978-3-9597-7201-3"],"issn":["1868-8969"]},"publication":"46th International Symposium on Mathematical Foundations of Computer Science","title":"A bit of nondeterminism makes pushdown automata expressive and succinct","ddc":["000"],"alternative_title":["LIPIcs"],"day":"18","has_accepted_license":"1","department":[{"_id":"KrCh"}],"project":[{"name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"754411"}],"author":[{"first_name":"Shibashis","last_name":"Guha","full_name":"Guha, Shibashis"},{"id":"85D7C63E-7D5D-11E9-9C0F-98C4E5697425","first_name":"Ismael R","full_name":"Jecker, Ismael R","last_name":"Jecker"},{"first_name":"Karoliina","last_name":"Lehtinen","full_name":"Lehtinen, Karoliina"},{"last_name":"Zimmermann","full_name":"Zimmermann, Martin","first_name":"Martin"}],"article_number":"53","oa_version":"Published Version","intvolume":"       202","date_updated":"2025-05-14T10:54:50Z","abstract":[{"text":"We study the expressiveness and succinctness of good-for-games pushdown automata (GFG-PDA) over finite words, that is, pushdown automata whose nondeterminism can be resolved based on the run constructed so far, but independently of the remainder of the input word. We prove that GFG-PDA recognise more languages than deterministic PDA (DPDA) but not all context-free languages (CFL). This class is orthogonal to unambiguous CFL. We further show that GFG-PDA can be exponentially more succinct than DPDA, while PDA can be double-exponentially more succinct than GFG-PDA. We also study GFGness in visibly pushdown automata (VPA), which enjoy better closure properties than PDA, and for which we show GFGness to be ExpTime-complete. GFG-VPA can be exponentially more succinct than deterministic VPA, while VPA can be exponentially more succinct than GFG-VPA. Both of these lower bounds are tight. Finally, we study the complexity of resolving nondeterminism in GFG-PDA. Every GFG-PDA has a positional resolver, a function that resolves nondeterminism and that is only dependant on the current configuration. Pushdown transducers are sufficient to implement the resolvers of GFG-VPA, but not those of GFG-PDA. GFG-PDA with finite-state resolvers are determinisable.","lang":"eng"}],"file":[{"success":1,"creator":"cchlebak","relation":"main_file","date_created":"2021-10-06T12:44:05Z","file_size":825567,"date_updated":"2021-10-06T12:44:05Z","content_type":"application/pdf","checksum":"f4d407d43a97330c3fb11e6a7a6fbfb2","access_level":"open_access","file_name":"2021_LIPIcs_Guha.pdf","file_id":"10097"}],"oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2021-08-18T00:00:00Z","language":[{"iso":"eng"}],"doi":"10.4230/LIPIcs.MFCS.2021.53","external_id":{"arxiv":["2105.02611"]},"quality_controlled":"1","year":"2021","arxiv":1,"month":"08","scopus_import":"1","_id":"10075","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","citation":{"short":"S. Guha, I.R. Jecker, K. Lehtinen, M. Zimmermann, in:, 46th International Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.","chicago":"Guha, Shibashis, Ismael R Jecker, Karoliina Lehtinen, and Martin Zimmermann. “A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct.” In <i>46th International Symposium on Mathematical Foundations of Computer Science</i>, Vol. 202. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2021.53\">https://doi.org/10.4230/LIPIcs.MFCS.2021.53</a>.","mla":"Guha, Shibashis, et al. “A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct.” <i>46th International Symposium on Mathematical Foundations of Computer Science</i>, vol. 202, 53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2021.53\">10.4230/LIPIcs.MFCS.2021.53</a>.","ista":"Guha S, Jecker IR, Lehtinen K, Zimmermann M. 2021. A bit of nondeterminism makes pushdown automata expressive and succinct. 46th International Symposium on Mathematical Foundations of Computer Science. MFCS: Mathematical Foundations of Computer Science, LIPIcs, vol. 202, 53.","apa":"Guha, S., Jecker, I. R., Lehtinen, K., &#38; Zimmermann, M. (2021). A bit of nondeterminism makes pushdown automata expressive and succinct. In <i>46th International Symposium on Mathematical Foundations of Computer Science</i> (Vol. 202). Tallinn, Estonia: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2021.53\">https://doi.org/10.4230/LIPIcs.MFCS.2021.53</a>","ama":"Guha S, Jecker IR, Lehtinen K, Zimmermann M. A bit of nondeterminism makes pushdown automata expressive and succinct. In: <i>46th International Symposium on Mathematical Foundations of Computer Science</i>. Vol 202. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2021.53\">10.4230/LIPIcs.MFCS.2021.53</a>","ieee":"S. Guha, I. R. Jecker, K. Lehtinen, and M. Zimmermann, “A bit of nondeterminism makes pushdown automata expressive and succinct,” in <i>46th International Symposium on Mathematical Foundations of Computer Science</i>, Tallinn, Estonia, 2021, vol. 202."},"volume":202,"type":"conference"},{"page":"431-450","external_id":{"isi":["000713005000034"]},"quality_controlled":"1","year":"2021","date_published":"2021-09-17T00:00:00Z","publisher":"Springer Nature","doi":"10.1007/978-3-662-63958-0_34","language":[{"iso":"eng"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":"12676 ","type":"conference","publication_status":"published","citation":{"ama":"Blackshear S, Chalkias K, Chatzigiannis P, et al. Reactive key-loss protection in blockchains. In: <i>FC 2021 Workshops</i>. Vol 12676. Springer Nature; 2021:431-450. doi:<a href=\"https://doi.org/10.1007/978-3-662-63958-0_34\">10.1007/978-3-662-63958-0_34</a>","apa":"Blackshear, S., Chalkias, K., Chatzigiannis, P., Faizullabhoy, R., Khaburzaniya, I., Kokoris Kogias, E., … Zakian, T. (2021). Reactive key-loss protection in blockchains. In <i>FC 2021 Workshops</i> (Vol. 12676, pp. 431–450). Virtual: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-63958-0_34\">https://doi.org/10.1007/978-3-662-63958-0_34</a>","ieee":"S. Blackshear <i>et al.</i>, “Reactive key-loss protection in blockchains,” in <i>FC 2021 Workshops</i>, Virtual, 2021, vol. 12676, pp. 431–450.","short":"S. Blackshear, K. Chalkias, P. Chatzigiannis, R. Faizullabhoy, I. Khaburzaniya, E. Kokoris Kogias, J. Lind, D. Wong, T. Zakian, in:, FC 2021 Workshops, Springer Nature, 2021, pp. 431–450.","ista":"Blackshear S, Chalkias K, Chatzigiannis P, Faizullabhoy R, Khaburzaniya I, Kokoris Kogias E, Lind J, Wong D, Zakian T. 2021. Reactive key-loss protection in blockchains. FC 2021 Workshops. FC: Financial Cryptography and Data Security, LNCS, vol. 12676, 431–450.","mla":"Blackshear, Sam, et al. “Reactive Key-Loss Protection in Blockchains.” <i>FC 2021 Workshops</i>, vol. 12676, Springer Nature, 2021, pp. 431–50, doi:<a href=\"https://doi.org/10.1007/978-3-662-63958-0_34\">10.1007/978-3-662-63958-0_34</a>.","chicago":"Blackshear, Sam, Konstantinos Chalkias, Panagiotis Chatzigiannis, Riyaz Faizullabhoy, Irakliy Khaburzaniya, Eleftherios Kokoris Kogias, Joshua Lind, David Wong, and Tim Zakian. “Reactive Key-Loss Protection in Blockchains.” In <i>FC 2021 Workshops</i>, 12676:431–50. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-662-63958-0_34\">https://doi.org/10.1007/978-3-662-63958-0_34</a>."},"month":"09","scopus_import":"1","_id":"10076","publication_identifier":{"isbn":["978-3-6626-3957-3"],"eissn":["1611-3349"],"eisbn":["978-3-662-63958-0"],"issn":["0302-9743"]},"conference":{"name":"FC: Financial Cryptography and Data Security","end_date":"2021-03-05","start_date":"2021-03-01","location":"Virtual"},"publication":"FC 2021 Workshops","acknowledgement":"The authors would like to thank all anonymous reviewers of FC21 WTSC workshop for comments and suggestions that greatly improved the quality of this paper.","main_file_link":[{"url":"https://research.fb.com/publications/reactive-key-loss-protection-in-blockchains/","open_access":"1"}],"date_created":"2021-10-03T22:01:24Z","status":"public","article_processing_charge":"No","author":[{"full_name":"Blackshear, Sam","last_name":"Blackshear","first_name":"Sam"},{"first_name":"Konstantinos","full_name":"Chalkias, Konstantinos","last_name":"Chalkias"},{"first_name":"Panagiotis","last_name":"Chatzigiannis","full_name":"Chatzigiannis, Panagiotis"},{"first_name":"Riyaz","last_name":"Faizullabhoy","full_name":"Faizullabhoy, Riyaz"},{"first_name":"Irakliy","full_name":"Khaburzaniya, Irakliy","last_name":"Khaburzaniya"},{"id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","first_name":"Eleftherios","full_name":"Kokoris Kogias, Eleftherios","last_name":"Kokoris Kogias"},{"last_name":"Lind","full_name":"Lind, Joshua","first_name":"Joshua"},{"full_name":"Wong, David","last_name":"Wong","first_name":"David"},{"full_name":"Zakian, Tim","last_name":"Zakian","first_name":"Tim"}],"abstract":[{"lang":"eng","text":"We present a novel approach for blockchain asset owners to reclaim their funds in case of accidental private-key loss or transfer to a mistyped address. Our solution can be deployed upon failure or absence of proactively implemented backup mechanisms, such as secret sharing and cold storage. The main advantages against previous proposals is it does not require any prior action from users and works with both single-key and multi-sig accounts. We achieve this by a 3-phase   Commit()→Reveal()→Claim()−or−Challenge()  smart contract that enables accessing funds of addresses for which the spending key is not available. We provide an analysis of the threat and incentive models and formalize the concept of reactive KEy-Loss Protection (KELP)."}],"oa_version":"Preprint","date_updated":"2025-07-10T11:49:40Z","day":"17","alternative_title":["LNCS"],"title":"Reactive key-loss protection in blockchains","department":[{"_id":"ElKo"}],"isi":1},{"ec_funded":1,"publication":"bioRxiv","year":"2021","doi":"10.1101/2021.09.30.462269","publisher":"Cold Spring Harbor Laboratory","language":[{"iso":"eng"}],"date_published":"2021-10-02T00:00:00Z","acknowledgement":"We thank Federico Stella for invaluable suggestions and discussions. We thank Yosman BapatDhar and Andrea Cumpelik for comments, help and suggestions on the exposure of the text. We thank Predrag Živadinović and Juliana Couras for comments on the text and the figures. This work was supported by the EU-FP7 MC-ITN IN-SENS (grant 607616).","date_created":"2021-10-04T06:28:32Z","main_file_link":[{"open_access":"1","url":"https://www.biorxiv.org/content/10.1101/2021.09.30.462269"}],"status":"public","oa":1,"article_processing_charge":"No","author":[{"last_name":"Nardin","full_name":"Nardin, Michele","id":"30BD0376-F248-11E8-B48F-1D18A9856A87","first_name":"Michele","orcid":"0000-0001-8849-6570"},{"id":"2DAA49AA-F248-11E8-B48F-1D18A9856A87","first_name":"Karola","last_name":"Käfer","full_name":"Käfer, Karola"},{"full_name":"Csicsvari, Jozsef L","last_name":"Csicsvari","orcid":"0000-0002-5193-4036","id":"3FA14672-F248-11E8-B48F-1D18A9856A87","first_name":"Jozsef L"}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","type":"preprint","abstract":[{"lang":"eng","text":"Hippocampal and neocortical neural activity is modulated by the position of the individual in space. While hippocampal neurons provide the basis for a spatial map, prefrontal cortical neurons generalize over environmental features. Whether these generalized representations result from a bidirectional interaction with, or are mainly derived from hippocampal spatial representations is not known. By examining simultaneously recorded hippocampal and medial prefrontal neurons, we observed that prefrontal spatial representations show a delayed coherence with hippocampal ones. We also identified subpopulations of cells in the hippocampus and medial prefrontal cortex that formed functional cross-area couplings; these resembled the optimal connections predicted by a probabilistic model of spatial information transfer and generalization. Moreover, cross-area couplings were strongest and had the shortest delay preceding spatial decision-making. Our results suggest that generalized spatial coding in the medial prefrontal cortex is inherited from spatial representations in the hippocampus, and that the routing of information can change dynamically with behavioral demands."}],"oa_version":"Preprint","publication_status":"submitted","citation":{"short":"M. Nardin, K. Käfer, J.L. Csicsvari, BioRxiv (n.d.).","ista":"Nardin M, Käfer K, Csicsvari JL. The generalized spatial representation in the prefrontal cortex is inherited from the hippocampus. bioRxiv, <a href=\"https://doi.org/10.1101/2021.09.30.462269\">10.1101/2021.09.30.462269</a>.","chicago":"Nardin, Michele, Karola Käfer, and Jozsef L Csicsvari. “The Generalized Spatial Representation in the Prefrontal Cortex Is Inherited from the Hippocampus.” <i>BioRxiv</i>. Cold Spring Harbor Laboratory, n.d. <a href=\"https://doi.org/10.1101/2021.09.30.462269\">https://doi.org/10.1101/2021.09.30.462269</a>.","mla":"Nardin, Michele, et al. “The Generalized Spatial Representation in the Prefrontal Cortex Is Inherited from the Hippocampus.” <i>BioRxiv</i>, Cold Spring Harbor Laboratory, doi:<a href=\"https://doi.org/10.1101/2021.09.30.462269\">10.1101/2021.09.30.462269</a>.","ama":"Nardin M, Käfer K, Csicsvari JL. The generalized spatial representation in the prefrontal cortex is inherited from the hippocampus. <i>bioRxiv</i>. doi:<a href=\"https://doi.org/10.1101/2021.09.30.462269\">10.1101/2021.09.30.462269</a>","apa":"Nardin, M., Käfer, K., &#38; Csicsvari, J. L. (n.d.). The generalized spatial representation in the prefrontal cortex is inherited from the hippocampus. <i>bioRxiv</i>. Cold Spring Harbor Laboratory. <a href=\"https://doi.org/10.1101/2021.09.30.462269\">https://doi.org/10.1101/2021.09.30.462269</a>","ieee":"M. Nardin, K. Käfer, and J. L. Csicsvari, “The generalized spatial representation in the prefrontal cortex is inherited from the hippocampus,” <i>bioRxiv</i>. Cold Spring Harbor Laboratory."},"date_updated":"2025-04-15T06:48:21Z","month":"10","day":"02","title":"The generalized spatial representation in the prefrontal cortex is inherited from the hippocampus","department":[{"_id":"GradSch"},{"_id":"JoCs"}],"project":[{"_id":"257BBB4C-B435-11E9-9278-68D0E5697425","grant_number":"607616","call_identifier":"FP7","name":"inter-and intracellular signalling in schizophrenia"}],"_id":"10080"},{"citation":{"short":"M. Obr, F.K. Schur, R.A. Dick, Viruses 13 (2021).","ista":"Obr M, Schur FK, Dick RA. 2021. A structural perspective of the role of IP6 in immature and mature retroviral assembly. Viruses. 13(9), 1853.","chicago":"Obr, Martin, Florian KM Schur, and Robert A. Dick. “A Structural Perspective of the Role of IP6 in Immature and Mature Retroviral Assembly.” <i>Viruses</i>. MDPI, 2021. <a href=\"https://doi.org/10.3390/v13091853\">https://doi.org/10.3390/v13091853</a>.","mla":"Obr, Martin, et al. “A Structural Perspective of the Role of IP6 in Immature and Mature Retroviral Assembly.” <i>Viruses</i>, vol. 13, no. 9, 1853, MDPI, 2021, doi:<a href=\"https://doi.org/10.3390/v13091853\">10.3390/v13091853</a>.","apa":"Obr, M., Schur, F. K., &#38; Dick, R. A. (2021). A structural perspective of the role of IP6 in immature and mature retroviral assembly. <i>Viruses</i>. MDPI. <a href=\"https://doi.org/10.3390/v13091853\">https://doi.org/10.3390/v13091853</a>","ama":"Obr M, Schur FK, Dick RA. A structural perspective of the role of IP6 in immature and mature retroviral assembly. <i>Viruses</i>. 2021;13(9). doi:<a href=\"https://doi.org/10.3390/v13091853\">10.3390/v13091853</a>","ieee":"M. Obr, F. K. Schur, and R. A. Dick, “A structural perspective of the role of IP6 in immature and mature retroviral assembly,” <i>Viruses</i>, vol. 13, no. 9. MDPI, 2021."},"publication_status":"published","corr_author":"1","volume":13,"type":"journal_article","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"10103","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"scopus_import":"1","month":"09","pmid":1,"year":"2021","quality_controlled":"1","external_id":{"pmid":["34578434"],"isi":["000699841100001"]},"article_type":"original","keyword":["virology","infectious diseases"],"oa":1,"file":[{"checksum":"bcfd72a12977d48e22df3d0cc55aacf1","access_level":"open_access","file_name":"2021_Viruses_Obr.pdf","file_id":"10115","file_size":4146796,"date_updated":"2021-10-08T10:38:15Z","content_type":"application/pdf","date_created":"2021-10-08T10:38:15Z","success":1,"creator":"cchlebak","relation":"main_file"}],"issue":"9","doi":"10.3390/v13091853","date_published":"2021-09-17T00:00:00Z","publisher":"MDPI","language":[{"iso":"eng"}],"date_updated":"2025-04-15T08:24:49Z","intvolume":"        13","article_number":"1853","oa_version":"Published Version","abstract":[{"lang":"eng","text":"The small cellular molecule inositol hexakisphosphate (IP6) has been known for ~20 years to promote the in vitro assembly of HIV-1 into immature virus-like particles. However, the molecular details underlying this effect have been determined only recently, with the identification of the IP6 binding site in the immature Gag lattice. IP6 also promotes formation of the mature capsid protein (CA) lattice via a second IP6 binding site, and enhances core stability, creating a favorable environment for reverse transcription. IP6 also enhances assembly of other retroviruses, from both the Lentivirus and the Alpharetrovirus genera. These findings suggest that IP6 may have a conserved function throughout the family Retroviridae. Here, we discuss the different steps in the viral life cycle that are influenced by IP6, and describe in detail how IP6 interacts with the immature and mature lattices of different retroviruses."}],"author":[{"full_name":"Obr, Martin","last_name":"Obr","orcid":"0000-0003-1756-6564","id":"4741CA5A-F248-11E8-B48F-1D18A9856A87","first_name":"Martin"},{"full_name":"Schur, Florian KM","last_name":"Schur","orcid":"0000-0003-4790-8078","first_name":"Florian KM","id":"48AD8942-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Dick","full_name":"Dick, Robert A.","first_name":"Robert A."}],"has_accepted_license":"1","isi":1,"project":[{"name":"Structural conservation and diversity in retroviral capsid","grant_number":"P31445","call_identifier":"FWF","_id":"26736D6A-B435-11E9-9278-68D0E5697425"}],"department":[{"_id":"FlSc"}],"title":"A structural perspective of the role of IP6 in immature and mature retroviral assembly","day":"17","ddc":["616"],"publication":"Viruses","publication_identifier":{"issn":["1999-4915"]},"article_processing_charge":"Yes","file_date_updated":"2021-10-08T10:38:15Z","status":"public","date_created":"2021-10-07T09:13:29Z","acknowledgement":"We thank Volker M. Vogt for his critical comments in preparation of the review."}]