[{"corr_author":"1","has_accepted_license":"1","status":"public","department":[{"_id":"GradSch"},{"_id":"ToHe"}],"project":[{"call_identifier":"H2020","name":"International IST Doctoral Program","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"},{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020"}],"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"11362"}]},"doi":"10.1609/aaai.v35i5.16496","scopus_import":"1","file":[{"file_name":"16496-Article Text-19990-1-2-20210518 (1).pdf","date_updated":"2022-01-26T07:41:16Z","checksum":"2bc8155b2526a70fba5b7301bc89dbd1","creator":"mlechner","content_type":"application/pdf","relation":"main_file","file_size":137235,"date_created":"2022-01-26T07:41:16Z","file_id":"10684","success":1,"access_level":"open_access"}],"ddc":["000"],"main_file_link":[{"open_access":"1","url":"https://ojs.aaai.org/index.php/AAAI/article/view/16496"}],"quality_controlled":"1","month":"05","language":[{"iso":"eng"}],"volume":35,"external_id":{"arxiv":["2012.08185"]},"oa_version":"Published Version","type":"conference","date_published":"2021-05-28T00:00:00Z","intvolume":"        35","publication_identifier":{"issn":["2159-5399"],"isbn":["978-1-57735-866-4"],"eissn":["2374-3468"]},"alternative_title":["Technical Tracks"],"_id":"10665","year":"2021","conference":{"location":"Virtual","name":"AAAI: Association for the Advancement of Artificial Intelligence","end_date":"2021-02-09","start_date":"2021-02-02"},"page":"3787-3795","abstract":[{"lang":"eng","text":"Formal verification of neural networks is an active topic of research, and recent advances have significantly increased the size of the networks that verification tools can handle. However, most methods are designed for verification of an idealized model of the actual network which works over real arithmetic and ignores rounding imprecisions. This idealization is in stark contrast to network quantization, which is a technique that trades numerical precision for computational efficiency and is, therefore, often applied in practice. Neglecting rounding errors of such low-bit quantized neural networks has been shown to lead to wrong conclusions about the network’s correctness. Thus, the desired approach for verifying quantized neural networks would be one that takes these rounding errors\r\ninto account. In this paper, we show that verifying the bitexact implementation of quantized neural networks with bitvector specifications is PSPACE-hard, even though verifying idealized real-valued networks and satisfiability of bit-vector specifications alone are each in NP. Furthermore, we explore several practical heuristics toward closing the complexity gap between idealized and bit-exact verification. In particular, we propose three techniques for making SMT-based verification of quantized neural networks more scalable. Our experiments demonstrate that our proposed methods allow a speedup of up to three orders of magnitude over existing approaches."}],"publication":"Proceedings of the AAAI Conference on Artificial Intelligence","author":[{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","orcid":"0000-0002-2985-7724","full_name":"Henzinger, Thomas A","last_name":"Henzinger"},{"last_name":"Lechner","full_name":"Lechner, Mathias","first_name":"Mathias","id":"3DC22916-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Zikelic","full_name":"Zikelic, Dorde","id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","first_name":"Dorde","orcid":"0000-0002-4681-1699"}],"title":"Scalable verification of quantized neural networks","date_updated":"2026-08-19T09:28:05Z","arxiv":1,"ec_funded":1,"article_processing_charge":"No","day":"28","publication_status":"published","fulldoi":"https://doi.org/10.1609/aaai.v35i5.16496","acknowledgement":"This research was supported in part by the Austrian Science Fund (FWF) under grant Z211-N23 (Wittgenstein\r\nAward), ERC CoG 863818 (FoRM-SMArt), and the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385.\r\n","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2022-01-25T15:15:02Z","publisher":"AAAI Press","issue":"5A","file_date_updated":"2022-01-26T07:41:16Z","citation":{"short":"T.A. Henzinger, M. Lechner, D. Zikelic, in:, Proceedings of the AAAI Conference on Artificial Intelligence, AAAI Press, 2021, pp. 3787–3795.","chicago":"Henzinger, Thomas A, Mathias Lechner, and Dorde Zikelic. “Scalable Verification of Quantized Neural Networks.” In <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, 35:3787–95. AAAI Press, 2021. <a href=\"https://doi.org/10.1609/aaai.v35i5.16496\">https://doi.org/10.1609/aaai.v35i5.16496</a>.","ieee":"T. A. Henzinger, M. Lechner, and D. Zikelic, “Scalable verification of quantized neural networks,” in <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, Virtual, 2021, vol. 35, no. 5A, pp. 3787–3795.","mla":"Henzinger, Thomas A., et al. “Scalable Verification of Quantized Neural Networks.” <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, vol. 35, no. 5A, AAAI Press, 2021, pp. 3787–95, doi:<a href=\"https://doi.org/10.1609/aaai.v35i5.16496\">10.1609/aaai.v35i5.16496</a>.","ama":"Henzinger TA, Lechner M, Zikelic D. Scalable verification of quantized neural networks. In: <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. Vol 35. AAAI Press; 2021:3787-3795. doi:<a href=\"https://doi.org/10.1609/aaai.v35i5.16496\">10.1609/aaai.v35i5.16496</a>","apa":"Henzinger, T. A., Lechner, M., &#38; Zikelic, D. (2021). Scalable verification of quantized neural networks. In <i>Proceedings of the AAAI Conference on Artificial Intelligence</i> (Vol. 35, pp. 3787–3795). Virtual: AAAI Press. <a href=\"https://doi.org/10.1609/aaai.v35i5.16496\">https://doi.org/10.1609/aaai.v35i5.16496</a>","ista":"Henzinger TA, Lechner M, Zikelic D. 2021. Scalable verification of quantized neural networks. Proceedings of the AAAI Conference on Artificial Intelligence. AAAI: Association for the Advancement of Artificial Intelligence, Technical Tracks, vol. 35, 3787–3795."},"oa":1},{"doi":"10.1609/aaai.v35i9.16936","corr_author":"1","has_accepted_license":"1","status":"public","project":[{"call_identifier":"FWF","grant_number":"Z211","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425"}],"department":[{"_id":"GradSch"},{"_id":"ToHe"}],"external_id":{"arxiv":["2006.04439"]},"volume":35,"language":[{"iso":"eng"}],"oa_version":"Published Version","intvolume":"        35","date_published":"2021-05-28T00:00:00Z","type":"conference","ddc":["000"],"file":[{"relation":"main_file","file_size":4302669,"date_created":"2022-01-26T07:36:03Z","file_id":"10678","success":1,"access_level":"open_access","file_name":"16936-Article Text-20430-1-2-20210518 (1).pdf","date_updated":"2022-01-26T07:36:03Z","checksum":"0f06995fba06dbcfa7ed965fc66027ff","creator":"mlechner","content_type":"application/pdf"}],"main_file_link":[{"open_access":"1","url":"https://ojs.aaai.org/index.php/AAAI/article/view/16936"}],"quality_controlled":"1","month":"05","date_updated":"2026-08-19T09:24:30Z","arxiv":1,"publication_status":"published","day":"28","article_processing_charge":"No","publication_identifier":{"eissn":["2374-3468"],"isbn":["978-1-57735-866-4"],"issn":["2159-5399"]},"_id":"10671","conference":{"start_date":"2021-02-02","end_date":"2021-02-09","name":"AAAI: Association for the Advancement of Artificial Intelligence","location":"Virtual"},"year":"2021","alternative_title":["Technical Tracks"],"abstract":[{"text":"We introduce a new class of time-continuous recurrent neural network models. Instead of declaring a learning system’s dynamics by implicit nonlinearities, we construct networks of linear first-order dynamical systems modulated via nonlinear interlinked gates. The resulting models represent dynamical systems with varying (i.e., liquid) time-constants coupled to their hidden state, with outputs being computed by numerical differential equation solvers. These neural networks exhibit stable and bounded behavior, yield superior expressivity within the family of neural ordinary differential equations, and give rise to improved performance on time-series prediction tasks. To demonstrate these properties, we first take a theoretical approach to find bounds over their dynamics, and compute their expressive power by the trajectory length measure in a latent trajectory space. We then conduct a series of time-series prediction experiments to manifest the approximation capability of Liquid Time-Constant Networks (LTCs) compared to classical and modern RNNs.","lang":"eng"}],"page":"7657-7666","publication":"Proceedings of the AAAI Conference on Artificial Intelligence","author":[{"last_name":"Hasani","full_name":"Hasani, Ramin","first_name":"Ramin"},{"first_name":"Mathias","id":"3DC22916-F248-11E8-B48F-1D18A9856A87","full_name":"Lechner, Mathias","last_name":"Lechner"},{"first_name":"Alexander","full_name":"Amini, Alexander","last_name":"Amini"},{"first_name":"Daniela","last_name":"Rus","full_name":"Rus, Daniela"},{"last_name":"Grosu","full_name":"Grosu, Radu","first_name":"Radu"}],"title":"Liquid time-constant networks","issue":"9","citation":{"ista":"Hasani R, Lechner M, Amini A, Rus D, Grosu R. 2021. Liquid time-constant networks. Proceedings of the AAAI Conference on Artificial Intelligence. AAAI: Association for the Advancement of Artificial Intelligence, Technical Tracks, vol. 35, 7657–7666.","apa":"Hasani, R., Lechner, M., Amini, A., Rus, D., &#38; Grosu, R. (2021). Liquid time-constant networks. In <i>Proceedings of the AAAI Conference on Artificial Intelligence</i> (Vol. 35, pp. 7657–7666). Virtual: AAAI Press. <a href=\"https://doi.org/10.1609/aaai.v35i9.16936\">https://doi.org/10.1609/aaai.v35i9.16936</a>","mla":"Hasani, Ramin, et al. “Liquid Time-Constant Networks.” <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, vol. 35, no. 9, AAAI Press, 2021, pp. 7657–66, doi:<a href=\"https://doi.org/10.1609/aaai.v35i9.16936\">10.1609/aaai.v35i9.16936</a>.","ama":"Hasani R, Lechner M, Amini A, Rus D, Grosu R. Liquid time-constant networks. In: <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. Vol 35. AAAI Press; 2021:7657-7666. doi:<a href=\"https://doi.org/10.1609/aaai.v35i9.16936\">10.1609/aaai.v35i9.16936</a>","ieee":"R. Hasani, M. Lechner, A. Amini, D. Rus, and R. Grosu, “Liquid time-constant networks,” in <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, Virtual, 2021, vol. 35, no. 9, pp. 7657–7666.","short":"R. Hasani, M. Lechner, A. Amini, D. Rus, R. Grosu, in:, Proceedings of the AAAI Conference on Artificial Intelligence, AAAI Press, 2021, pp. 7657–7666.","chicago":"Hasani, Ramin, Mathias Lechner, Alexander Amini, Daniela Rus, and Radu Grosu. “Liquid Time-Constant Networks.” In <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, 35:7657–66. AAAI Press, 2021. <a href=\"https://doi.org/10.1609/aaai.v35i9.16936\">https://doi.org/10.1609/aaai.v35i9.16936</a>."},"file_date_updated":"2022-01-26T07:36:03Z","oa":1,"acknowledgement":"R.H. and D.R. are partially supported by Boeing. R.H. and R.G. were partially supported by the Horizon-2020 ECSEL\r\nProject grant No. 783163 (iDev40). M.L. was supported in part by the Austrian Science Fund (FWF) under grant Z211-N23 (Wittgenstein Award). A.A. is supported by the National Science Foundation (NSF) Graduate Research Fellowship Program. This research work is partially drawn from the PhD dissertation of R.H.","fulldoi":"https://doi.org/10.1609/aaai.v35i9.16936","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"AAAI Press","date_created":"2022-01-25T15:48:36Z"},{"main_file_link":[{"open_access":"1","url":" https://doi.org/10.48550/arXiv.1905.11845"}],"quality_controlled":"1","month":"05","language":[{"iso":"eng"}],"external_id":{"arxiv":["1905.11845"]},"volume":35,"oa_version":"Preprint","type":"conference","date_published":"2021-05-18T00:00:00Z","intvolume":"        35","status":"public","department":[{"_id":"DaAl"}],"project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"},{"call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223"}],"doi":"10.1609/aaai.v35i9.16999","scopus_import":"1","acknowledgement":"Vyacheslav Kungurtsev was supported by the OP VVV project CZ.02.1.01/0.0/0.0/16 019/0000765 “Research Center for Informatics. Bapi Chatterjee was supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 754411 (ISTPlus). Dan Alistarh has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).","fulldoi":"https://doi.org/10.1609/aaai.v35i9.16999","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2022-06-05T22:01:52Z","publisher":"AAAI Press","issue":"9B","citation":{"ieee":"V. Kungurtsev, M. Egan, B. Chatterjee, and D.-A. Alistarh, “Asynchronous optimization methods for efficient training of deep neural networks with guarantees,” in <i>35th AAAI Conference on Artificial Intelligence, AAAI 2021</i>, Virtual, Online, 2021, vol. 35, no. 9B, pp. 8209–8216.","ista":"Kungurtsev V, Egan M, Chatterjee B, Alistarh D-A. 2021. Asynchronous optimization methods for efficient training of deep neural networks with guarantees. 35th AAAI Conference on Artificial Intelligence, AAAI 2021. AAAI: Conference on Artificial Intelligence vol. 35, 8209–8216.","apa":"Kungurtsev, V., Egan, M., Chatterjee, B., &#38; Alistarh, D.-A. (2021). Asynchronous optimization methods for efficient training of deep neural networks with guarantees. In <i>35th AAAI Conference on Artificial Intelligence, AAAI 2021</i> (Vol. 35, pp. 8209–8216). Virtual, Online: AAAI Press. <a href=\"https://doi.org/10.1609/aaai.v35i9.16999\">https://doi.org/10.1609/aaai.v35i9.16999</a>","mla":"Kungurtsev, Vyacheslav, et al. “Asynchronous Optimization Methods for Efficient Training of Deep Neural Networks with Guarantees.” <i>35th AAAI Conference on Artificial Intelligence, AAAI 2021</i>, vol. 35, no. 9B, AAAI Press, 2021, pp. 8209–16, doi:<a href=\"https://doi.org/10.1609/aaai.v35i9.16999\">10.1609/aaai.v35i9.16999</a>.","ama":"Kungurtsev V, Egan M, Chatterjee B, Alistarh D-A. Asynchronous optimization methods for efficient training of deep neural networks with guarantees. In: <i>35th AAAI Conference on Artificial Intelligence, AAAI 2021</i>. Vol 35. AAAI Press; 2021:8209-8216. doi:<a href=\"https://doi.org/10.1609/aaai.v35i9.16999\">10.1609/aaai.v35i9.16999</a>","chicago":"Kungurtsev, Vyacheslav, Malcolm Egan, Bapi Chatterjee, and Dan-Adrian Alistarh. “Asynchronous Optimization Methods for Efficient Training of Deep Neural Networks with Guarantees.” In <i>35th AAAI Conference on Artificial Intelligence, AAAI 2021</i>, 35:8209–16. AAAI Press, 2021. <a href=\"https://doi.org/10.1609/aaai.v35i9.16999\">https://doi.org/10.1609/aaai.v35i9.16999</a>.","short":"V. Kungurtsev, M. Egan, B. Chatterjee, D.-A. Alistarh, in:, 35th AAAI Conference on Artificial Intelligence, AAAI 2021, AAAI Press, 2021, pp. 8209–8216."},"oa":1,"publication_identifier":{"issn":["2159-5399"],"isbn":["9781713835974"],"eissn":["2374-3468"]},"_id":"11436","year":"2021","conference":{"name":"AAAI: Conference on Artificial Intelligence","location":"Virtual, Online","end_date":"2021-02-09","start_date":"2021-02-02"},"page":"8209-8216","abstract":[{"text":"Asynchronous distributed algorithms are a popular way to reduce synchronization costs in large-scale optimization, and in particular for neural network training. However, for nonsmooth and nonconvex objectives, few convergence guarantees exist beyond cases where closed-form proximal operator solutions are available. As training most popular deep neural networks corresponds to optimizing nonsmooth and nonconvex objectives, there is a pressing need for such convergence guarantees. In this paper, we analyze for the first time the convergence of stochastic asynchronous optimization for this general class of objectives. In particular, we focus on stochastic subgradient methods allowing for block variable partitioning, where the shared model is asynchronously updated by concurrent processes. To this end, we use a probabilistic model which captures key features of real asynchronous scheduling between concurrent processes. Under this model, we establish convergence with probability one to an invariant set for stochastic subgradient methods with momentum. From a practical perspective, one issue with the family of algorithms that we consider is that they are not efficiently supported by machine learning frameworks, which mostly focus on distributed data-parallel strategies. To address this, we propose a new implementation strategy for shared-memory based training of deep neural networks for a partitioned but shared model in single- and multi-GPU settings. Based on this implementation, we achieve on average1.2x speed-up in comparison to state-of-the-art training methods for popular image classification tasks, without compromising accuracy.","lang":"eng"}],"author":[{"first_name":"Vyacheslav","full_name":"Kungurtsev, Vyacheslav","last_name":"Kungurtsev"},{"last_name":"Egan","full_name":"Egan, Malcolm","first_name":"Malcolm"},{"orcid":"0000-0002-2742-4028","first_name":"Bapi","id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Bapi","last_name":"Chatterjee"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh"}],"title":"Asynchronous optimization methods for efficient training of deep neural networks with guarantees","publication":"35th AAAI Conference on Artificial Intelligence, AAAI 2021","date_updated":"2026-08-19T09:25:06Z","arxiv":1,"ec_funded":1,"article_processing_charge":"No","day":"18","publication_status":"published"},{"oa_version":"Published Version","intvolume":"        35","type":"conference","date_published":"2021-05-28T00:00:00Z","volume":35,"external_id":{"arxiv":["2012.08863"]},"language":[{"iso":"eng"}],"month":"05","ddc":["000"],"file":[{"creator":"mlechner","checksum":"468d07041e282a1d46ffdae92f709630","content_type":"application/pdf","file_name":"17372-Article Text-20866-1-2-20210518.pdf","date_updated":"2022-01-26T07:38:08Z","date_created":"2022-01-26T07:38:08Z","access_level":"open_access","file_id":"10680","success":1,"relation":"main_file","file_size":286906}],"quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://ojs.aaai.org/index.php/AAAI/article/view/17372"}],"doi":"10.1609/aaai.v35i13.17372","status":"public","has_accepted_license":"1","project":[{"call_identifier":"FWF","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"}],"department":[{"_id":"GradSch"},{"_id":"ToHe"}],"corr_author":"1","citation":{"ieee":"S. Grunbacher, R. Hasani, M. Lechner, J. Cyranka, S. A. Smolka, and R. Grosu, “On the verification of neural ODEs with stochastic guarantees,” in <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, Virtual, 2021, vol. 35, no. 13, pp. 11525–11535.","ista":"Grunbacher S, Hasani R, Lechner M, Cyranka J, Smolka SA, Grosu R. 2021. On the verification of neural ODEs with stochastic guarantees. Proceedings of the AAAI Conference on Artificial Intelligence. AAAI: Association for the Advancement of Artificial Intelligence, Technical Tracks, vol. 35, 11525–11535.","ama":"Grunbacher S, Hasani R, Lechner M, Cyranka J, Smolka SA, Grosu R. On the verification of neural ODEs with stochastic guarantees. In: <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. Vol 35. AAAI Press; 2021:11525-11535. doi:<a href=\"https://doi.org/10.1609/aaai.v35i13.17372\">10.1609/aaai.v35i13.17372</a>","mla":"Grunbacher, Sophie, et al. “On the Verification of Neural ODEs with Stochastic Guarantees.” <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, vol. 35, no. 13, AAAI Press, 2021, pp. 11525–35, doi:<a href=\"https://doi.org/10.1609/aaai.v35i13.17372\">10.1609/aaai.v35i13.17372</a>.","apa":"Grunbacher, S., Hasani, R., Lechner, M., Cyranka, J., Smolka, S. A., &#38; Grosu, R. (2021). On the verification of neural ODEs with stochastic guarantees. In <i>Proceedings of the AAAI Conference on Artificial Intelligence</i> (Vol. 35, pp. 11525–11535). Virtual: AAAI Press. <a href=\"https://doi.org/10.1609/aaai.v35i13.17372\">https://doi.org/10.1609/aaai.v35i13.17372</a>","chicago":"Grunbacher, Sophie, Ramin Hasani, Mathias Lechner, Jacek Cyranka, Scott A Smolka, and Radu Grosu. “On the Verification of Neural ODEs with Stochastic Guarantees.” In <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, 35:11525–35. AAAI Press, 2021. <a href=\"https://doi.org/10.1609/aaai.v35i13.17372\">https://doi.org/10.1609/aaai.v35i13.17372</a>.","short":"S. Grunbacher, R. Hasani, M. Lechner, J. Cyranka, S.A. Smolka, R. Grosu, in:, Proceedings of the AAAI Conference on Artificial Intelligence, AAAI Press, 2021, pp. 11525–11535."},"file_date_updated":"2022-01-26T07:38:08Z","oa":1,"issue":"13","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"AAAI Press","date_created":"2022-01-25T15:47:20Z","acknowledgement":"The authors would like to thank the reviewers for their insightful comments. RH and RG were partially supported by\r\nHorizon-2020 ECSEL Project grant No. 783163 (iDev40). RH was partially supported by Boeing. ML was supported\r\nin part by the Austrian Science Fund (FWF) under grant Z211-N23 (Wittgenstein Award). SG was funded by FWF\r\nproject W1255-N23. JC was partially supported by NAWA Polish Returns grant PPN/PPO/2018/1/00029. SS was supported by NSF awards DCL-2040599, CCF-1918225, and CPS-1446832.\r\n","fulldoi":"https://doi.org/10.1609/aaai.v35i13.17372","publication_status":"published","article_processing_charge":"No","day":"28","date_updated":"2026-08-19T09:29:48Z","arxiv":1,"abstract":[{"text":"We show that Neural ODEs, an emerging class of timecontinuous neural networks, can be verified by solving a set of global-optimization problems. For this purpose, we introduce Stochastic Lagrangian Reachability (SLR), an\r\nabstraction-based technique for constructing a tight Reachtube (an over-approximation of the set of reachable states\r\nover a given time-horizon), and provide stochastic guarantees in the form of confidence intervals for the Reachtube bounds. SLR inherently avoids the infamous wrapping effect (accumulation of over-approximation errors) by performing local optimization steps to expand safe regions instead of repeatedly forward-propagating them as is done by deterministic reachability methods. To enable fast local optimizations, we introduce a novel forward-mode adjoint sensitivity method to compute gradients without the need for backpropagation. Finally, we establish asymptotic and non-asymptotic convergence rates for SLR.","lang":"eng"}],"page":"11525-11535","title":"On the verification of neural ODEs with stochastic guarantees","publication":"Proceedings of the AAAI Conference on Artificial Intelligence","author":[{"full_name":"Grunbacher, Sophie","last_name":"Grunbacher","first_name":"Sophie"},{"first_name":"Ramin","last_name":"Hasani","full_name":"Hasani, Ramin"},{"last_name":"Lechner","full_name":"Lechner, Mathias","id":"3DC22916-F248-11E8-B48F-1D18A9856A87","first_name":"Mathias"},{"first_name":"Jacek","full_name":"Cyranka, Jacek","last_name":"Cyranka"},{"first_name":"Scott A","full_name":"Smolka, Scott A","last_name":"Smolka"},{"first_name":"Radu","last_name":"Grosu","full_name":"Grosu, Radu"}],"publication_identifier":{"issn":["2159-5399"],"eissn":["2374-3468"],"isbn":["978-1-57735-866-4"]},"conference":{"location":"Virtual","name":"AAAI: Association for the Advancement of Artificial Intelligence","start_date":"2021-02-02","end_date":"2021-02-09"},"_id":"10669","year":"2021","alternative_title":["Technical Tracks"]},{"supervisor":[{"full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2026-08-19T09:30:23Z","article_processing_charge":"No","day":"09","publication_status":"published","ec_funded":1,"alternative_title":["ISTA Thesis"],"_id":"10429","year":"2021","publication_identifier":{"issn":["2663-337X"]},"title":"On achieving scalability through relaxation","author":[{"full_name":"Nadiradze, Giorgi","last_name":"Nadiradze","orcid":"0000-0001-5634-0731","first_name":"Giorgi","id":"3279A00C-F248-11E8-B48F-1D18A9856A87"}],"page":"132","abstract":[{"text":"The scalability of concurrent data structures and distributed algorithms strongly depends on\r\nreducing the contention for shared resources and the costs of synchronization and communication. We show how such cost reductions can be attained by relaxing the strict consistency conditions required by sequential implementations. In the first part of the thesis, we consider relaxation in the context of concurrent data structures. Specifically, in data structures \r\nsuch as priority queues, imposing strong semantics renders scalability impossible, since a correct implementation of the remove operation should return only the element with highest priority. Intuitively, attempting to invoke remove operations concurrently  creates a race condition. This bottleneck  can be circumvented by relaxing semantics of the affected data structure, thus allowing removal of the elements which are no longer required to have the highest priority. We prove that the randomized implementations of relaxed data structures provide provable guarantees on the priority of the removed elements even under concurrency. Additionally, we show that in some cases the relaxed data structures can be used to scale the classical algorithms which are usually implemented with the exact ones. In the second part, we study parallel variants of the  stochastic gradient descent (SGD) algorithm, which distribute computation  among the multiple processors, thus reducing the running time. Unfortunately, in order for standard parallel SGD to succeed, each processor has to maintain a local copy of the necessary model parameter, which is identical to the local copies of other processors; the overheads from this perfect consistency in terms of communication and synchronization can negate the speedup gained by distributing the computation. We show that the consistency conditions required by SGD can be  relaxed, allowing the algorithm to be more flexible in terms of tolerating quantized communication, asynchrony, or even crash faults, while its convergence remains asymptotically the same.","lang":"eng"}],"oa":1,"file_date_updated":"2022-03-28T12:55:12Z","citation":{"ama":"Nadiradze G. On achieving scalability through relaxation. 2021. doi:<a href=\"https://doi.org/10.15479/at:ista:10429\">10.15479/at:ista:10429</a>","apa":"Nadiradze, G. (2021). <i>On achieving scalability through relaxation</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:10429\">https://doi.org/10.15479/at:ista:10429</a>","mla":"Nadiradze, Giorgi. <i>On Achieving Scalability through Relaxation</i>. Institute of Science and Technology Austria, 2021, doi:<a href=\"https://doi.org/10.15479/at:ista:10429\">10.15479/at:ista:10429</a>.","ista":"Nadiradze G. 2021. On achieving scalability through relaxation. Institute of Science and Technology Austria.","ieee":"G. Nadiradze, “On achieving scalability through relaxation,” Institute of Science and Technology Austria, 2021.","chicago":"Nadiradze, Giorgi. “On Achieving Scalability through Relaxation.” Institute of Science and Technology Austria, 2021. <a href=\"https://doi.org/10.15479/at:ista:10429\">https://doi.org/10.15479/at:ista:10429</a>.","short":"G. Nadiradze, On Achieving Scalability through Relaxation, Institute of Science and Technology Austria, 2021."},"fulldoi":"https://doi.org/10.15479/at:ista:10429","date_created":"2021-12-08T21:52:28Z","publisher":"Institute of Science and Technology Austria","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"6673"},{"relation":"part_of_dissertation","id":"5965","status":"public"},{"id":"10435","relation":"part_of_dissertation","status":"public"},{"relation":"part_of_dissertation","id":"10432","status":"public"}]},"doi":"10.15479/at:ista:10429","corr_author":"1","department":[{"_id":"GradSch"},{"_id":"DaAl"}],"OA_place":"publisher","project":[{"call_identifier":"H2020","grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"status":"public","has_accepted_license":"1","language":[{"iso":"eng"}],"date_published":"2021-12-09T00:00:00Z","type":"dissertation","degree_awarded":"PhD","oa_version":"Published Version","file":[{"file_size":2370859,"relation":"main_file","success":1,"file_id":"10436","access_level":"open_access","date_created":"2021-12-09T17:47:49Z","date_updated":"2021-12-09T17:47:49Z","file_name":"Thesis_Final_09_12_2021.pdf","content_type":"application/pdf","checksum":"6bf14e9a523387328f016c0689f5e10e","creator":"gnadirad"},{"content_type":"application/zip","checksum":"914d6c5ca86bd0add471971a8f4c4341","creator":"gnadirad","date_updated":"2022-03-28T12:55:12Z","file_name":"Thesis_Final_09_12_2021.zip","file_id":"10437","access_level":"closed","date_created":"2021-12-09T17:47:49Z","file_size":2596924,"relation":"source_file"}],"ddc":["000"],"month":"12"},{"month":"05","ddc":["000"],"quality_controlled":"1","main_file_link":[{"url":"https://ojs.aaai.org/index.php/AAAI/article/view/17092","open_access":"1"}],"oa_version":"Published Version","type":"conference","date_published":"2021-05-18T00:00:00Z","intvolume":"        35","language":[{"iso":"eng"}],"volume":35,"external_id":{"arxiv":["2001.05918"]},"status":"public","department":[{"_id":"DaAl"}],"project":[{"call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"},{"call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223"}],"related_material":{"record":[{"id":"10429","relation":"dissertation_contains","status":"public"}]},"doi":"10.1609/aaai.v35i10.17092","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2021-12-09T09:21:35Z","fulldoi":"https://doi.org/10.1609/aaai.v35i10.17092","acknowledgement":"We would like to thank Christopher De Sa for his feedback on an earlier draft of this paper, as well as the anonymous AAAI reviewers for their useful comments. This project has received\r\nfunding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). Bapi\r\nChatterjee was supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No. 754411 (ISTPlus).","citation":{"ieee":"G. Nadiradze, I. Markov, B. Chatterjee, V. Kungurtsev, and D.-A. Alistarh, “Elastic consistency: A practical consistency model for distributed stochastic gradient descent,” in <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, Virtual, 2021, vol. 35, no. 10, pp. 9037–9045.","apa":"Nadiradze, G., Markov, I., Chatterjee, B., Kungurtsev, V., &#38; Alistarh, D.-A. (2021). Elastic consistency: A practical consistency model for distributed stochastic gradient descent. In <i>Proceedings of the AAAI Conference on Artificial Intelligence</i> (Vol. 35, pp. 9037–9045). Virtual. <a href=\"https://doi.org/10.1609/aaai.v35i10.17092\">https://doi.org/10.1609/aaai.v35i10.17092</a>","ama":"Nadiradze G, Markov I, Chatterjee B, Kungurtsev V, Alistarh D-A. Elastic consistency: A practical consistency model for distributed stochastic gradient descent. In: <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>. Vol 35. ; 2021:9037-9045. doi:<a href=\"https://doi.org/10.1609/aaai.v35i10.17092\">10.1609/aaai.v35i10.17092</a>","mla":"Nadiradze, Giorgi, et al. “Elastic Consistency: A Practical Consistency Model for Distributed Stochastic Gradient Descent.” <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, vol. 35, no. 10, 2021, pp. 9037–45, doi:<a href=\"https://doi.org/10.1609/aaai.v35i10.17092\">10.1609/aaai.v35i10.17092</a>.","ista":"Nadiradze G, Markov I, Chatterjee B, Kungurtsev V, Alistarh D-A. 2021. Elastic consistency: A practical consistency model for distributed stochastic gradient descent. Proceedings of the AAAI Conference on Artificial Intelligence. AAAI: Association for the Advancement of Artificial Intelligence vol. 35, 9037–9045.","chicago":"Nadiradze, Giorgi, Ilia Markov, Bapi Chatterjee, Vyacheslav  Kungurtsev, and Dan-Adrian Alistarh. “Elastic Consistency: A Practical Consistency Model for Distributed Stochastic Gradient Descent.” In <i>Proceedings of the AAAI Conference on Artificial Intelligence</i>, 35:9037–45, 2021. <a href=\"https://doi.org/10.1609/aaai.v35i10.17092\">https://doi.org/10.1609/aaai.v35i10.17092</a>.","short":"G. Nadiradze, I. Markov, B. Chatterjee, V. Kungurtsev, D.-A. Alistarh, in:, Proceedings of the AAAI Conference on Artificial Intelligence, 2021, pp. 9037–9045."},"oa":1,"issue":"10","page":"9037-9045","abstract":[{"text":"One key element behind the recent progress of machine learning has been the ability to train machine learning models in large-scale distributed shared-memory and message-passing environments. Most of these models are trained employing variants of stochastic gradient descent (SGD) based optimization, but most methods involve some type of consistency relaxation relative to sequential SGD, to mitigate its large communication or synchronization costs at scale. In this paper, we introduce a general consistency condition covering communication-reduced and asynchronous distributed SGD implementations. Our framework, called elastic consistency, decouples the system-specific aspects of the implementation from the SGD convergence requirements, giving a general way to obtain convergence bounds for a wide variety of distributed SGD methods used in practice. Elastic consistency can be used to re-derive or improve several previous convergence bounds in message-passing and shared-memory settings, but also to analyze new models and distribution schemes. As a direct application, we propose and analyze a new synchronization-avoiding scheduling scheme for distributed SGD, and show that it can be used to efficiently train deep convolutional models for image classification.","lang":"eng"}],"title":"Elastic consistency: A practical consistency model for distributed stochastic gradient descent","publication":"Proceedings of the AAAI Conference on Artificial Intelligence","author":[{"orcid":"0000-0001-5634-0731","id":"3279A00C-F248-11E8-B48F-1D18A9856A87","first_name":"Giorgi","full_name":"Nadiradze, Giorgi","last_name":"Nadiradze"},{"full_name":"Markov, Ilia","last_name":"Markov","first_name":"Ilia","id":"D0CF4148-C985-11E9-8066-0BDEE5697425"},{"full_name":"Chatterjee, Bapi","last_name":"Chatterjee","first_name":"Bapi","id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2742-4028"},{"last_name":"Kungurtsev","full_name":"Kungurtsev, Vyacheslav ","first_name":"Vyacheslav "},{"full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian"}],"year":"2021","_id":"10432","conference":{"name":"AAAI: Association for the Advancement of Artificial Intelligence","location":"Virtual","start_date":"2021-02-02","end_date":"2021-02-09"},"ec_funded":1,"day":"18","article_processing_charge":"No","publication_status":"published","arxiv":1,"date_updated":"2026-08-19T09:30:23Z"},{"abstract":[{"text":"We compare the Manin-type conjecture for Campana points recently formulated\r\nby Pieropan, Smeets, Tanimoto and V\\'{a}rilly-Alvarado with an alternative\r\nprediction of Browning and Van Valckenborgh in the special case of the orbifold\r\n$(\\mathbb{P}^1,D)$, where $D =\\frac{1}{2}[0]+\\frac{1}{2}[1]+\\frac{1}{2}[\\infty]$. We find that the two predicted leading constants do not agree, and we discuss whether thin sets\r\ncould explain this discrepancy. Motivated by this, we provide a counterexample\r\nto the Manin-type conjecture for Campana points, by considering orbifolds\r\ncorresponding to squareful values of binary quadratic forms.","lang":"eng"}],"author":[{"orcid":"0000-0002-1812-2810","first_name":"Alec L","id":"440EB050-F248-11E8-B48F-1D18A9856A87","last_name":"Shute","full_name":"Shute, Alec L"}],"publication":"arXiv","title":"On the leading constant in the Manin-type conjecture for Campana points","_id":"12077","year":"2021","day":"30","article_processing_charge":"No","publication_status":"draft","arxiv":1,"date_updated":"2026-08-19T12:54:58Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_created":"2022-09-09T10:43:17Z","acknowledgement":"The author would like to thank Damaris Schindler and Florian Wilsch for their helpful comments on the heights and Tamagawa measures used in Section 3, together with Marta Pieropan, Sho Tanimoto and Sam Streeter for providing valuable feedback on an earlier version of this paper, and Tim Browning for many useful comments and discussions during the development of this work. The author is also grateful to the anonymous referee for providing many valuable comments and suggestions that improved the quality of the paper.","fulldoi":"https://doi.org/10.48550/arXiv.2104.14946","das_tickbox":"0","supplementarymaterial":"no","citation":{"ieee":"A. L. Shute, “On the leading constant in the Manin-type conjecture for Campana points,” <i>arXiv</i>. .","ista":"Shute AL. On the leading constant in the Manin-type conjecture for Campana points. arXiv, 2104.14946.","apa":"Shute, A. L. (n.d.). On the leading constant in the Manin-type conjecture for Campana points. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.2104.14946\">https://doi.org/10.48550/arXiv.2104.14946</a>","mla":"Shute, Alec L. “On the Leading Constant in the Manin-Type Conjecture for Campana Points.” <i>ArXiv</i>, 2104.14946, doi:<a href=\"https://doi.org/10.48550/arXiv.2104.14946\">10.48550/arXiv.2104.14946</a>.","ama":"Shute AL. On the leading constant in the Manin-type conjecture for Campana points. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.2104.14946\">10.48550/arXiv.2104.14946</a>","short":"A.L. Shute, ArXiv (n.d.).","chicago":"Shute, Alec L. “On the Leading Constant in the Manin-Type Conjecture for Campana Points.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.2104.14946\">https://doi.org/10.48550/arXiv.2104.14946</a>."},"researchdata_availability":"no","oa":1,"article_number":"2104.14946","status":"public","department":[{"_id":"TiBr"}],"corr_author":"1","related_material":{"record":[{"id":"12072","relation":"dissertation_contains","status":"public"},{"id":"17058","relation":"later_version","status":"public"}]},"doi":"10.48550/arXiv.2104.14946","month":"04","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2104.14946"}],"oa_version":"Preprint","type":"preprint","date_published":"2021-04-30T00:00:00Z","language":[{"iso":"eng"}],"external_id":{"arxiv":["2104.14946"]}},{"citation":{"short":"G. Yalniz, B. Hof, N.B. Budanur, Physical Review Letters 126 (2021).","chicago":"Yalniz, Gökhan, Björn Hof, and Nazmi B Budanur. “Coarse Graining the State Space of a Turbulent Flow Using Periodic Orbits.” <i>Physical Review Letters</i>. American Physical Society, 2021. <a href=\"https://doi.org/10.1103/PhysRevLett.126.244502\">https://doi.org/10.1103/PhysRevLett.126.244502</a>.","ieee":"G. Yalniz, B. Hof, and N. B. Budanur, “Coarse graining the state space of a turbulent flow using periodic orbits,” <i>Physical Review Letters</i>, vol. 126, no. 24. American Physical Society, 2021.","apa":"Yalniz, G., Hof, B., &#38; Budanur, N. B. (2021). Coarse graining the state space of a turbulent flow using periodic orbits. <i>Physical Review Letters</i>. American Physical Society. <a href=\"https://doi.org/10.1103/PhysRevLett.126.244502\">https://doi.org/10.1103/PhysRevLett.126.244502</a>","ama":"Yalniz G, Hof B, Budanur NB. Coarse graining the state space of a turbulent flow using periodic orbits. <i>Physical Review Letters</i>. 2021;126(24). doi:<a href=\"https://doi.org/10.1103/PhysRevLett.126.244502\">10.1103/PhysRevLett.126.244502</a>","mla":"Yalniz, Gökhan, et al. “Coarse Graining the State Space of a Turbulent Flow Using Periodic Orbits.” <i>Physical Review Letters</i>, vol. 126, no. 24, 244502, American Physical Society, 2021, doi:<a href=\"https://doi.org/10.1103/PhysRevLett.126.244502\">10.1103/PhysRevLett.126.244502</a>.","ista":"Yalniz G, Hof B, Budanur NB. 2021. Coarse graining the state space of a turbulent flow using periodic orbits. Physical Review Letters. 126(24), 244502."},"article_number":"244502","oa":1,"issue":"24","article_type":"letter_note","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","isi":1,"publisher":"American Physical Society","date_created":"2021-06-16T15:45:36Z","acknowledgement":"We thank the referees for improving this Letter with their comments. We acknowledge stimulating discussions with\r\nH. Edelsbrunner. This work was supported by Grant No. 662960 from the Simons Foundation (B. H.). The numerical calculations were performed at TUBITAK ULAKBIM High Performance and Grid Computing Center (TRUBA resources) and IST Austria High Performance Computing cluster.","fulldoi":"https://doi.org/10.1103/PhysRevLett.126.244502","publication_status":"published","article_processing_charge":"No","day":"18","arxiv":1,"date_updated":"2026-09-02T08:16:31Z","abstract":[{"text":"We show that turbulent dynamics that arise in simulations of the three-dimensional Navier--Stokes equations in a triply-periodic domain under sinusoidal forcing can be described as transient visits to the neighborhoods of unstable time-periodic solutions. Based on this description, we reduce the original system with more than 10^5 degrees of freedom to a 17-node Markov chain where each node corresponds to the neighborhood of a periodic orbit. The model accurately reproduces long-term averages of the system's observables as weighted sums over the periodic orbits.\r\n","lang":"eng"}],"author":[{"last_name":"Yalniz","full_name":"Yalniz, Gökhan","first_name":"Gökhan","id":"66E74FA2-D8BF-11E9-8249-8DE2E5697425","orcid":"0000-0002-8490-9312"},{"first_name":"Björn","id":"3A374330-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2057-2754","last_name":"Hof","full_name":"Hof, Björn"},{"last_name":"Budanur","full_name":"Budanur, Nazmi B","first_name":"Nazmi B","id":"3EA1010E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-0423-5010"}],"publication":"Physical Review Letters","title":"Coarse graining the state space of a turbulent flow using periodic orbits","publication_identifier":{"eissn":["1079-7114"],"issn":["0031-9007"]},"year":"2021","_id":"9558","oa_version":"Preprint","acknowledged_ssus":[{"_id":"ScienComp"}],"intvolume":"       126","type":"journal_article","date_published":"2021-06-18T00:00:00Z","external_id":{"arxiv":["2007.02584"],"isi":["000663310100008"]},"volume":126,"language":[{"iso":"eng"}],"month":"06","main_file_link":[{"url":"https://arxiv.org/abs/2007.02584","open_access":"1"}],"quality_controlled":"1","scopus_import":"1","doi":"10.1103/PhysRevLett.126.244502","related_material":{"record":[{"status":"returned","relation":"popular_science","id":"19591"},{"id":"19684","relation":"dissertation_contains","status":"public"}],"link":[{"relation":"press_release","url":"https://ist.ac.at/en/news/turbulent-flow-simplified/","description":"News on IST Homepage"}]},"status":"public","project":[{"name":"Revisiting the Turbulence Problem Using Statistical Mechanics","_id":"238598C6-32DE-11EA-91FC-C7463DDC885E","grant_number":"662960"}],"department":[{"_id":"GradSch"},{"_id":"BjHo"}],"corr_author":"1"},{"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_created":"2021-12-05T23:01:42Z","isi":1,"publisher":"Springer Nature","acknowledgement":"B. Auerbach, M.A. Baig and K. Pietrzak—received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT); Karen Klein was supported in part by ERC CoG grant 724307 and conducted part of this work at IST Austria, funded by the ERC under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT); Guillermo Pascual-Perez was funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385; Michael Walter conducted part of this work at IST Austria, funded by the ERC under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).","fulldoi":"https://doi.org/10.1007/978-3-030-90456-2_8","citation":{"ama":"Alwen JF, Auerbach B, Baig MA, et al. Grafting key trees: Efficient key management for overlapping groups. In: <i>19th International Conference</i>. Vol 13044. Springer Nature; 2021:222-253. doi:<a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">10.1007/978-3-030-90456-2_8</a>","mla":"Alwen, Joel F., et al. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” <i>19th International Conference</i>, vol. 13044, Springer Nature, 2021, pp. 222–53, doi:<a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">10.1007/978-3-030-90456-2_8</a>.","apa":"Alwen, J. F., Auerbach, B., Baig, M. A., Cueto Noval, M., Klein, K., Pascual Perez, G., … Walter, M. (2021). Grafting key trees: Efficient key management for overlapping groups. In <i>19th International Conference</i> (Vol. 13044, pp. 222–253). Raleigh, NC, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">https://doi.org/10.1007/978-3-030-90456-2_8</a>","ista":"Alwen JF, Auerbach B, Baig MA, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ, Walter M. 2021. Grafting key trees: Efficient key management for overlapping groups. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13044, 222–253.","ieee":"J. F. Alwen <i>et al.</i>, “Grafting key trees: Efficient key management for overlapping groups,” in <i>19th International Conference</i>, Raleigh, NC, United States, 2021, vol. 13044, pp. 222–253.","chicago":"Alwen, Joel F, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” In <i>19th International Conference</i>, 13044:222–53. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">https://doi.org/10.1007/978-3-030-90456-2_8</a>.","short":"J.F. Alwen, B. Auerbach, M.A. Baig, M. Cueto Noval, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, pp. 222–253."},"oa":1,"page":"222-253","abstract":[{"text":"Key trees are often the best solution in terms of transmission cost and storage requirements for managing keys in a setting where a group needs to share a secret key, while being able to efficiently rotate the key material of users (in order to recover from a potential compromise, or to add or remove users). Applications include multicast encryption protocols like LKH (Logical Key Hierarchies) or group messaging like the current IETF proposal TreeKEM. A key tree is a (typically balanced) binary tree, where each node is identified with a key: leaf nodes hold users’ secret keys while the root is the shared group key. For a group of size N, each user just holds   log(N)  keys (the keys on the path from its leaf to the root) and its entire key material can be rotated by broadcasting   2log(N)  ciphertexts (encrypting each fresh key on the path under the keys of its parents). In this work we consider the natural setting where we have many groups with partially overlapping sets of users, and ask if we can find solutions where the cost of rotating a key is better than in the trivial one where we have a separate key tree for each group. We show that in an asymptotic setting (where the number m of groups is fixed while the number N of users grows) there exist more general key graphs whose cost converges to the cost of a single group, thus saving a factor linear in the number of groups over the trivial solution. As our asymptotic “solution” converges very slowly and performs poorly on concrete examples, we propose an algorithm that uses a natural heuristic to compute a key graph for any given group structure. Our algorithm combines two greedy algorithms, and is thus very efficient: it first converts the group structure into a “lattice graph”, which is then turned into a key graph by repeatedly applying the algorithm for constructing a Huffman code. To better understand how far our proposal is from an optimal solution, we prove lower bounds on the update cost of continuous group-key agreement and multicast encryption in a symbolic model admitting (asymmetric) encryption, pseudorandom generators, and secret sharing as building blocks.","lang":"eng"}],"author":[{"last_name":"Alwen","full_name":"Alwen, Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F"},{"orcid":"0000-0002-7553-6606","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","first_name":"Benedikt","full_name":"Auerbach, Benedikt","last_name":"Auerbach"},{"first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","last_name":"Baig","full_name":"Baig, Mirza Ahad"},{"orcid":"0000-0002-2505-4246","first_name":"Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel"},{"full_name":"Klein, Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen"},{"orcid":"0000-0001-8630-415X","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","first_name":"Guillermo","full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez"},{"full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"},{"orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","full_name":"Walter, Michael","last_name":"Walter"}],"publication":"19th International Conference","title":"Grafting key trees: Efficient key management for overlapping groups","publication_identifier":{"issn":["0302-9743"],"eisbn":["978-3-030-90456-2"],"isbn":["9-783-0309-0455-5"],"eissn":["1611-3349"]},"alternative_title":["LNCS"],"year":"2021","_id":"10408","conference":{"name":"TCC: Theory of Cryptography","location":"Raleigh, NC, United States","start_date":"2021-11-08","end_date":"2021-11-11"},"ec_funded":1,"day":"04","article_processing_charge":"No","publication_status":"published","date_updated":"2026-09-07T14:12:36Z","month":"11","main_file_link":[{"url":"https://eprint.iacr.org/2021/1158","open_access":"1"}],"quality_controlled":"1","oa_version":"Preprint","type":"conference","date_published":"2021-11-04T00:00:00Z","intvolume":"     13044","language":[{"iso":"eng"}],"volume":13044,"external_id":{"isi":["000728363700008"]},"status":"public","department":[{"_id":"KrPi"}],"project":[{"grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"},{"call_identifier":"H2020","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program"}],"scopus_import":"1","related_material":{"record":[{"relation":"dissertation_contains","id":"18088","status":"public"}]},"doi":"10.1007/978-3-030-90456-2_8"},{"alternative_title":["ISTA Thesis"],"_id":"10035","year":"2021","publication_identifier":{"issn":["2663-337X"]},"title":"On the adaptive security of graph-based games","author":[{"last_name":"Klein","full_name":"Klein, Karen","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"}],"page":"276","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"}],"supervisor":[{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z"}],"date_updated":"2026-09-07T14:12:38Z","day":"23","article_processing_charge":"No","publication_status":"published","ec_funded":1,"tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"fulldoi":"https://doi.org/10.15479/at:ista:10035","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","date_created":"2021-09-23T07:31:44Z","publisher":"Institute of Science and Technology Austria","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","oa":1,"file_date_updated":"2022-03-10T12:15:18Z","citation":{"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>.","short":"K. Klein, On the Adaptive Security of Graph-Based Games, Institute of Science and Technology Austria, 2021.","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>","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>.","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."},"corr_author":"1","department":[{"_id":"GradSch"},{"_id":"KrPi"}],"project":[{"call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"OA_place":"publisher","status":"public","has_accepted_license":"1","related_material":{"record":[{"status":"public","id":"637","relation":"part_of_dissertation"},{"status":"public","id":"6430","relation":"part_of_dissertation"},{"id":"10044","relation":"part_of_dissertation","status":"public"},{"relation":"part_of_dissertation","id":"10048","status":"public"},{"status":"public","id":"10041","relation":"part_of_dissertation"},{"status":"public","id":"10049","relation":"part_of_dissertation"}]},"doi":"10.15479/at:ista:10035","file":[{"content_type":"application/pdf","creator":"cchlebak","checksum":"73a44345c683e81f3e765efbf86fdcc5","date_updated":"2021-10-04T12:22:33Z","file_name":"thesis_pdfa.pdf","access_level":"open_access","file_id":"10082","success":1,"date_created":"2021-10-04T12:22:33Z","file_size":2104726,"relation":"main_file"},{"date_updated":"2022-03-10T12:15:18Z","file_name":"thesis_final (1).zip","content_type":"application/x-zip-compressed","checksum":"7b80df30a0e686c3ef6a56d4e1c59e29","creator":"cchlebak","file_size":9538359,"relation":"source_file","file_id":"10085","access_level":"closed","date_created":"2021-10-05T07:04:37Z"}],"ddc":["519"],"month":"09","language":[{"iso":"eng"}],"type":"dissertation","date_published":"2021-09-23T00:00:00Z","oa_version":"Published Version","degree_awarded":"PhD"},{"volume":12704,"language":[{"iso":"eng"}],"intvolume":"     12704","date_published":"2021-05-11T00:00:00Z","type":"conference","oa_version":"Submitted Version","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2020/670"}],"quality_controlled":"1","month":"05","doi":"10.1007/978-3-030-75539-3_17","scopus_import":"1","corr_author":"1","project":[{"name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385","call_identifier":"H2020"},{"name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","call_identifier":"H2020"}],"department":[{"_id":"KrPi"},{"_id":"GradSch"}],"status":"public","oa":1,"citation":{"ieee":"B. Auerbach <i>et al.</i>, “Inverse-Sybil attacks in automated contact tracing,” in <i>Topics in Cryptology – CT-RSA 2021</i>, Virtual Event, 2021, vol. 12704, pp. 399–421.","mla":"Auerbach, Benedikt, et al. “Inverse-Sybil Attacks in Automated Contact Tracing.” <i>Topics in Cryptology – CT-RSA 2021</i>, vol. 12704, Springer Nature, 2021, pp. 399–421, doi:<a href=\"https://doi.org/10.1007/978-3-030-75539-3_17\">10.1007/978-3-030-75539-3_17</a>.","apa":"Auerbach, B., Chakraborty, S., Klein, K., Pascual Perez, G., Pietrzak, K. Z., Walter, M., &#38; Yeo, M. X. (2021). Inverse-Sybil attacks in automated contact tracing. In <i>Topics in Cryptology – CT-RSA 2021</i> (Vol. 12704, pp. 399–421). Virtual Event: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-75539-3_17\">https://doi.org/10.1007/978-3-030-75539-3_17</a>","ama":"Auerbach B, Chakraborty S, Klein K, et al. Inverse-Sybil attacks in automated contact tracing. In: <i>Topics in Cryptology – CT-RSA 2021</i>. Vol 12704. Springer Nature; 2021:399-421. doi:<a href=\"https://doi.org/10.1007/978-3-030-75539-3_17\">10.1007/978-3-030-75539-3_17</a>","ista":"Auerbach B, Chakraborty S, Klein K, Pascual Perez G, Pietrzak KZ, Walter M, Yeo MX. 2021. Inverse-Sybil attacks in automated contact tracing. Topics in Cryptology – CT-RSA 2021. CT-RSA: Cryptographers’ Track at the RSA Conference, LNCS, vol. 12704, 399–421.","chicago":"Auerbach, Benedikt, Suvradip Chakraborty, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, Michael Walter, and Michelle X Yeo. “Inverse-Sybil Attacks in Automated Contact Tracing.” In <i>Topics in Cryptology – CT-RSA 2021</i>, 12704:399–421. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-75539-3_17\">https://doi.org/10.1007/978-3-030-75539-3_17</a>.","short":"B. Auerbach, S. Chakraborty, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M. Walter, M.X. Yeo, in:, Topics in Cryptology – CT-RSA 2021, Springer Nature, 2021, pp. 399–421."},"fulldoi":"https://doi.org/10.1007/978-3-030-75539-3_17","acknowledgement":"Guillermo Pascual-Perez and Michelle Yeo were funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska–Curie Grant Agreement No. 665385; the remaining contributors to this project have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).","publisher":"Springer Nature","date_created":"2021-08-08T22:01:30Z","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","date_updated":"2026-09-07T11:37:54Z","publication_status":"published","article_processing_charge":"No","day":"11","ec_funded":1,"_id":"9826","conference":{"start_date":"2021-05-17","end_date":"2021-05-20","location":"Virtual Event","name":"CT-RSA: Cryptographers’ Track at the RSA Conference"},"year":"2021","alternative_title":["LNCS"],"publication_identifier":{"issn":["0302-9743"],"isbn":["9783030755386"],"eissn":["1611-3349"]},"publication":"Topics in Cryptology – CT-RSA 2021","title":"Inverse-Sybil attacks in automated contact tracing","author":[{"orcid":"0000-0002-7553-6606","first_name":"Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","full_name":"Auerbach, Benedikt","last_name":"Auerbach"},{"first_name":"Suvradip","id":"B9CD0494-D033-11E9-B219-A439E6697425","last_name":"Chakraborty","full_name":"Chakraborty, Suvradip"},{"last_name":"Klein","full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen"},{"full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez","orcid":"0000-0001-8630-415X","first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z"},{"orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","full_name":"Walter, Michael","last_name":"Walter"},{"orcid":"0009-0001-3676-4809","first_name":"Michelle X","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","last_name":"Yeo","full_name":"Yeo, Michelle X"}],"abstract":[{"text":"Automated contract tracing aims at supporting manual contact tracing during pandemics by alerting users of encounters with infected people. There are currently many proposals for protocols (like the “decentralized” DP-3T and PACT or the “centralized” ROBERT and DESIRE) to be run on mobile phones, where the basic idea is to regularly broadcast (using low energy Bluetooth) some values, and at the same time store (a function of) incoming messages broadcasted by users in their proximity. In the existing proposals one can trigger false positives on a massive scale by an “inverse-Sybil” attack, where a large number of devices (malicious users or hacked phones) pretend to be the same user, such that later, just a single person needs to be diagnosed (and allowed to upload) to trigger an alert for all users who were in proximity to any of this large group of devices.\r\n\r\nWe propose the first protocols that do not succumb to such attacks assuming the devices involved in the attack do not constantly communicate, which we observe is a necessary assumption. The high level idea of the protocols is to derive the values to be broadcasted by a hash chain, so that two (or more) devices who want to launch an inverse-Sybil attack will not be able to connect their respective chains and thus only one of them will be able to upload. Our protocols also achieve security against replay, belated replay, and one of them even against relay attacks.","lang":"eng"}],"page":"399-421"},{"language":[{"iso":"eng"}],"external_id":{"isi":["001316065000016"]},"oa_version":"Preprint","type":"conference","date_published":"2021-08-26T00:00:00Z","quality_controlled":"1","main_file_link":[{"url":"https://eprint.iacr.org/2019/1489","open_access":"1"}],"month":"08","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"10035"},{"status":"public","id":"18088","relation":"dissertation_contains"}]},"doi":"10.1109/sp40001.2021.00035","scopus_import":"1","corr_author":"1","status":"public","department":[{"_id":"KrPi"},{"_id":"DaAl"}],"project":[{"call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385","name":"International IST Doctoral Program"},{"call_identifier":"H2020","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815"}],"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.","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>","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>","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.","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>."},"oa":1,"fulldoi":"https://doi.org/10.1109/sp40001.2021.00035","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.","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_created":"2021-09-27T13:46:27Z","publisher":"IEEE","isi":1,"date_updated":"2026-09-07T14:12:38Z","ec_funded":1,"day":"26","article_processing_charge":"No","publication_status":"published","conference":{"location":"San Francisco, CA, United States","name":"SP: Symposium on Security and Privacy","end_date":"2021-05-27","start_date":"2021-05-24"},"_id":"10049","year":"2021","page":"268-284","abstract":[{"lang":"eng","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."}],"title":"Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous group key agreement","author":[{"id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen","full_name":"Klein, Karen","last_name":"Klein"},{"orcid":"0000-0001-8630-415X","first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo"},{"orcid":"0000-0003-3186-2482","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","first_name":"Michael","full_name":"Walter, Michael","last_name":"Walter"},{"last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan","orcid":"0009-0006-6812-7317","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan"},{"full_name":"Capretto, Margarita","last_name":"Capretto","first_name":"Margarita"},{"last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","first_name":"Miguel","orcid":"0000-0002-2505-4246"},{"full_name":"Markov, Ilia","last_name":"Markov","first_name":"Ilia","id":"D0CF4148-C985-11E9-8066-0BDEE5697425"},{"full_name":"Yeo, Michelle X","last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","first_name":"Michelle X","orcid":"0009-0001-3676-4809"},{"first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","last_name":"Alwen"},{"full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"}],"publication":"2021 IEEE Symposium on Security and Privacy "},{"has_accepted_license":"1","status":"public","project":[{"name":"Alpha Shape Theory Extended","grant_number":"788183","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"name":"Persistent Homology, Algorithms and Stochastic Geometry","_id":"0aa4bc98-070f-11eb-9043-e6fff9c6a316","grant_number":"I4887"},{"call_identifier":"FWF","_id":"25C5A090-B435-11E9-9278-68D0E5697425","grant_number":"Z00312","name":"Synaptic communication in neuronal microcircuits"},{"_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020"}],"department":[{"_id":"HeEd"}],"scopus_import":"1","doi":"10.4230/LIPIcs.SoCG.2021.32","related_material":{"record":[{"relation":"dissertation_contains","id":"18667","status":"public"}]},"month":"06","ddc":["004","516"],"file":[{"file_name":"df_socg_final_version.pdf","date_updated":"2021-04-22T08:08:14Z","creator":"mwintrae","checksum":"1787baef1523d6d93753b90d0c109a6d","content_type":"application/pdf","relation":"main_file","file_size":3117435,"date_created":"2021-04-22T08:08:14Z","access_level":"open_access","success":1,"file_id":"9346"}],"quality_controlled":"1","oa_version":"Published Version","intvolume":"       189","type":"conference","date_published":"2021-06-02T00:00:00Z","volume":189,"language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functionsthat facilitates the efficient search for new materials and material properties. We prove invarianceunder isometries, continuity, and completeness in the generic case, which are necessary featuresfor the reliable comparison of crystals. The proof of continuity integrates methods from discretegeometry and lattice theory, while the proof of generic completeness combines techniques fromgeometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and relatedinclusion-exclusion formulae. We have implemented the algorithm and describe its application tocrystal structure prediction."}],"page":"32:1-32:16","title":"The density fingerprint of a periodic point set","publication":"37th International Symposium on Computational Geometry","author":[{"orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert"},{"full_name":"Heiss, Teresa","last_name":"Heiss","first_name":"Teresa","id":"4879BB4E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1780-2689"},{"last_name":" Kurlin ","full_name":" Kurlin , Vitaliy","first_name":"Vitaliy"},{"full_name":"Smith, Philip","last_name":"Smith","first_name":"Philip"},{"orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","first_name":"Mathijs","full_name":"Wintraecken, Mathijs","last_name":"Wintraecken"}],"publication_identifier":{"issn":["1868-8969"]},"_id":"9345","conference":{"location":"Virtual","name":"SoCG: Symposium on Computational Geometry","end_date":"2021-06-11","start_date":"2021-06-07"},"year":"2021","alternative_title":["LIPIcs"],"ec_funded":1,"publication_status":"published","day":"02","article_processing_charge":"No","date_updated":"2026-10-02T11:24:33Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_created":"2021-04-22T08:09:58Z","fulldoi":"https://doi.org/10.4230/LIPIcs.SoCG.2021.32","acknowledgement":"The authors thank Janos Pach for insightful discussions on the topic of thispaper, Morteza Saghafian for finding the one-dimensional counterexample mentioned in Section 5,and Larry Andrews for generously sharing his crystallographic perspective.","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"citation":{"ama":"Edelsbrunner H, Heiss T,  Kurlin  V, Smith P, Wintraecken M. The density fingerprint of a periodic point set. In: <i>37th International Symposium on Computational Geometry</i>. Vol 189. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021:32:1-32:16. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.32\">10.4230/LIPIcs.SoCG.2021.32</a>","mla":"Edelsbrunner, Herbert, et al. “The Density Fingerprint of a Periodic Point Set.” <i>37th International Symposium on Computational Geometry</i>, vol. 189, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 32:1-32:16, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.32\">10.4230/LIPIcs.SoCG.2021.32</a>.","apa":"Edelsbrunner, H., Heiss, T.,  Kurlin , V., Smith, P., &#38; Wintraecken, M. (2021). The density fingerprint of a periodic point set. In <i>37th International Symposium on Computational Geometry</i> (Vol. 189, p. 32:1-32:16). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.32\">https://doi.org/10.4230/LIPIcs.SoCG.2021.32</a>","ista":"Edelsbrunner H, Heiss T,  Kurlin  V, Smith P, Wintraecken M. 2021. The density fingerprint of a periodic point set. 37th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 189, 32:1-32:16.","ieee":"H. Edelsbrunner, T. Heiss, V.  Kurlin , P. Smith, and M. Wintraecken, “The density fingerprint of a periodic point set,” in <i>37th International Symposium on Computational Geometry</i>, Virtual, 2021, vol. 189, p. 32:1-32:16.","short":"H. Edelsbrunner, T. Heiss, V.  Kurlin , P. Smith, M. Wintraecken, in:, 37th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 32:1-32:16.","chicago":"Edelsbrunner, Herbert, Teresa Heiss, Vitaliy  Kurlin , Philip Smith, and Mathijs Wintraecken. “The Density Fingerprint of a Periodic Point Set.” In <i>37th International Symposium on Computational Geometry</i>, 189:32:1-32:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2021.32\">https://doi.org/10.4230/LIPIcs.SoCG.2021.32</a>."},"das_tickbox":"1","file_date_updated":"2021-04-22T08:08:14Z","oa":1},{"abstract":[{"text":"There are two elementary superconducting qubit types that derive directly from the quantum harmonic oscillator. In one, the inductor is replaced by a nonlinear Josephson junction to realize the widely used charge qubits with a compact phase variable and a discrete charge wave function. In the other, the junction is added in parallel, which gives rise to an extended phase variable, continuous wave functions, and a rich energy-level structure due to the loop topology. While the corresponding rf superconducting quantum interference device Hamiltonian was introduced as a quadratic quasi-one-dimensional potential approximation to describe the fluxonium qubit implemented with long Josephson-junction arrays, in this work we implement it directly using a linear superinductor formed by a single uninterrupted aluminum wire. We present a large variety of qubits, all stemming from the same circuit but with drastically different characteristic energy scales. This includes flux and fluxonium qubits but also the recently introduced quasicharge qubit with strongly enhanced zero-point phase fluctuations and a heavily suppressed flux dispersion. The use of a geometric inductor results in high reproducibility of the inductive energy as guaranteed by top-down lithography—a key ingredient for intrinsically protected superconducting qubits.","lang":"eng"}],"page":"040341","publication":"PRX Quantum","title":"Geometric superinductance qubits: Controlling phase delocalization across a single Josephson junction","author":[{"full_name":"Peruzzo, Matilda","last_name":"Peruzzo","id":"3F920B30-F248-11E8-B48F-1D18A9856A87","first_name":"Matilda","orcid":"0000-0002-3415-4628"},{"orcid":"0000-0001-6937-5773","first_name":"Farid","id":"2AED110C-F248-11E8-B48F-1D18A9856A87","last_name":"Hassani","full_name":"Hassani, Farid"},{"first_name":"Gregory","full_name":"Szep, Gregory","last_name":"Szep"},{"first_name":"Andrea","id":"42F71B44-F248-11E8-B48F-1D18A9856A87","full_name":"Trioni, Andrea","last_name":"Trioni"},{"full_name":"Redchenko, Elena","last_name":"Redchenko","first_name":"Elena","id":"2C21D6E8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Martin","id":"2DCF8DE6-F248-11E8-B48F-1D18A9856A87","orcid":"0009-0005-0878-3032","full_name":"Zemlicka, Martin","last_name":"Zemlicka"},{"last_name":"Fink","full_name":"Fink, Johannes M","first_name":"Johannes M","id":"4B591CBA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8112-028X"}],"publication_identifier":{"eissn":["2691-3399"]},"year":"2021","_id":"9928","ec_funded":1,"publication_status":"published","article_processing_charge":"No","day":"24","arxiv":1,"date_updated":"2026-10-02T11:28:16Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","isi":1,"publisher":"American Physical Society","date_created":"2021-08-17T08:14:18Z","fulldoi":"https://doi.org/10.1103/PRXQuantum.2.040341","acknowledgement":"We thank W. Hughes for analytic and numerical modeling during the early stages of this work, J. Koch for discussions and support with the scqubits package, R. Sett, P. Zielinski, and L. Drmic for software development, and G. Katsaros for equipment support, as well as the MIBA workshop and the Institute of Science and Technology Austria nanofabrication facility. We thank I. Pop, S. Deleglise, and E. Flurin for discussions. This work was supported by a NOMIS Foundation research grant, the Austrian Science Fund (FWF) through BeyondC (F7105), and IST Austria. M.P. is the recipient of a Pöttinger scholarship at IST Austria. E.R. is the recipient of a DOC fellowship of the Austrian Academy of Sciences at IST Austria.","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"citation":{"ieee":"M. Peruzzo <i>et al.</i>, “Geometric superinductance qubits: Controlling phase delocalization across a single Josephson junction,” <i>PRX Quantum</i>, vol. 2, no. 4. American Physical Society, p. 040341, 2021.","ista":"Peruzzo M, Hassani F, Szep G, Trioni A, Redchenko E, Zemlicka M, Fink JM. 2021. Geometric superinductance qubits: Controlling phase delocalization across a single Josephson junction. PRX Quantum. 2(4), 040341.","mla":"Peruzzo, Matilda, et al. “Geometric Superinductance Qubits: Controlling Phase Delocalization across a Single Josephson Junction.” <i>PRX Quantum</i>, vol. 2, no. 4, American Physical Society, 2021, p. 040341, doi:<a href=\"https://doi.org/10.1103/PRXQuantum.2.040341\">10.1103/PRXQuantum.2.040341</a>.","ama":"Peruzzo M, Hassani F, Szep G, et al. Geometric superinductance qubits: Controlling phase delocalization across a single Josephson junction. <i>PRX Quantum</i>. 2021;2(4):040341. doi:<a href=\"https://doi.org/10.1103/PRXQuantum.2.040341\">10.1103/PRXQuantum.2.040341</a>","apa":"Peruzzo, M., Hassani, F., Szep, G., Trioni, A., Redchenko, E., Zemlicka, M., &#38; Fink, J. M. (2021). Geometric superinductance qubits: Controlling phase delocalization across a single Josephson junction. <i>PRX Quantum</i>. American Physical Society. <a href=\"https://doi.org/10.1103/PRXQuantum.2.040341\">https://doi.org/10.1103/PRXQuantum.2.040341</a>","chicago":"Peruzzo, Matilda, Farid Hassani, Gregory Szep, Andrea Trioni, Elena Redchenko, Martin Zemlicka, and Johannes M Fink. “Geometric Superinductance Qubits: Controlling Phase Delocalization across a Single Josephson Junction.” <i>PRX Quantum</i>. American Physical Society, 2021. <a href=\"https://doi.org/10.1103/PRXQuantum.2.040341\">https://doi.org/10.1103/PRXQuantum.2.040341</a>.","short":"M. Peruzzo, F. Hassani, G. Szep, A. Trioni, E. Redchenko, M. Zemlicka, J.M. Fink, PRX Quantum 2 (2021) 040341."},"file_date_updated":"2022-01-18T11:29:33Z","oa":1,"issue":"4","article_type":"original","status":"public","has_accepted_license":"1","project":[{"_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385","name":"International IST Doctoral Program","call_identifier":"H2020"},{"name":"Hybrid Semiconductor - Superconductor Quantum Devices","_id":"2622978C-B435-11E9-9278-68D0E5697425"},{"_id":"bdb108fd-d553-11ed-ba76-83dc74a9864f","grant_number":"F07105","name":"QUANTUM INFORMATION SYSTEMS BEYOND CLASSICAL CAPABILITIES / P5- Integration of Superconducting Quantum Circuits"}],"department":[{"_id":"JoFi"},{"_id":"NanoFab"},{"_id":"M-Shop"}],"corr_author":"1","scopus_import":"1","doi":"10.1103/PRXQuantum.2.040341","related_material":{"record":[{"id":"13057","relation":"research_data","status":"public"},{"id":"9920","relation":"dissertation_contains","status":"public"},{"status":"public","relation":"dissertation_contains","id":"17133"}]},"month":"11","ddc":["530"],"file":[{"file_name":"2021_PRXQuantum_Peruzzo.pdf","date_updated":"2022-01-18T11:29:33Z","checksum":"36eb41ea43d8ca22b0efab12419e4eb2","creator":"cchlebak","content_type":"application/pdf","relation":"main_file","file_size":4247422,"date_created":"2022-01-18T11:29:33Z","success":1,"file_id":"10641","access_level":"open_access"}],"quality_controlled":"1","oa_version":"Published Version","intvolume":"         2","acknowledged_ssus":[{"_id":"NanoFab"},{"_id":"M-Shop"}],"date_published":"2021-11-24T00:00:00Z","type":"journal_article","volume":2,"external_id":{"arxiv":["2106.05882"],"isi":["000723015100001"]},"keyword":["quantum physics","mesoscale and nanoscale physics"],"language":[{"iso":"eng"}]},{"arxiv":1,"date_updated":"2026-10-02T11:36:06Z","ec_funded":1,"publication_status":"published","article_processing_charge":"No","day":"30","publication_identifier":{"issn":["2469-9950"],"eissn":["2469-9969"]},"year":"2021","_id":"10067","abstract":[{"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.","lang":"eng"}],"title":"Entanglement transitions from restricted Boltzmann machines","author":[{"full_name":"Medina Ramos, Raimel A","last_name":"Medina Ramos","id":"CE680B90-D85A-11E9-B684-C920E6697425","first_name":"Raimel A","orcid":"0000-0002-5383-2869"},{"first_name":"Romain","last_name":"Vasseur","full_name":"Vasseur, Romain"},{"id":"47809E7E-F248-11E8-B48F-1D18A9856A87","first_name":"Maksym","orcid":"0000-0002-2399-5827","full_name":"Serbyn, Maksym","last_name":"Serbyn"}],"publication":"Physical Review B","issue":"10","article_type":"original","citation":{"ista":"Medina Ramos RA, Vasseur R, Serbyn M. 2021. Entanglement transitions from restricted Boltzmann machines. Physical Review B. 104(10), 104205.","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>","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>.","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>","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.","short":"R.A. Medina Ramos, R. Vasseur, M. Serbyn, Physical Review B 104 (2021).","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>."},"article_number":"104205","oa":1,"fulldoi":"https://doi.org/10.1103/physrevb.104.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.","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"American Physical Society","isi":1,"date_created":"2021-10-02T09:03:42Z","doi":"10.1103/physrevb.104.104205","related_material":{"record":[{"id":"17208","relation":"dissertation_contains","status":"public"}]},"scopus_import":"1","corr_author":"1","status":"public","project":[{"call_identifier":"H2020","name":"Non-Ergodic Quantum Matter: Universality, Dynamics and Control","grant_number":"850899","_id":"23841C26-32DE-11EA-91FC-C7463DDC885E"}],"department":[{"_id":"MaSe"}],"external_id":{"isi":["000704414400002"],"arxiv":["2107.05735"]},"volume":104,"language":[{"iso":"eng"}],"oa_version":"Preprint","intvolume":"       104","type":"journal_article","date_published":"2021-09-30T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/2107.05735","open_access":"1"}],"quality_controlled":"1","month":"09"},{"volume":104,"external_id":{"isi":["000753659200004"],"arxiv":["2106.06344"]},"language":[{"iso":"eng"}],"oa_version":"Preprint","intvolume":"       104","type":"journal_article","date_published":"2021-12-14T00:00:00Z","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2106.06344"}],"month":"12","doi":"10.1103/physreva.104.062423","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"17208"}]},"scopus_import":"1","status":"public","project":[{"call_identifier":"H2020","grant_number":"850899","_id":"23841C26-32DE-11EA-91FC-C7463DDC885E","name":"Non-Ergodic Quantum Matter: Universality, Dynamics and Control"}],"department":[{"_id":"MaSe"}],"issue":"6","article_type":"original","citation":{"chicago":"Medina Ramos, Raimel A, and Maksym Serbyn. “Duality Approach to Quantum Annealing of the 3-Variable Exclusive-or Satisfiability Problem (3-XORSAT).” <i>Physical Review A</i>. American Physical Society, 2021. <a href=\"https://doi.org/10.1103/physreva.104.062423\">https://doi.org/10.1103/physreva.104.062423</a>.","short":"R.A. Medina Ramos, M. Serbyn, Physical Review A 104 (2021).","ieee":"R. A. Medina Ramos and M. Serbyn, “Duality approach to quantum annealing of the 3-variable exclusive-or satisfiability problem (3-XORSAT),” <i>Physical Review A</i>, vol. 104, no. 6. American Physical Society, 2021.","apa":"Medina Ramos, R. A., &#38; Serbyn, M. (2021). Duality approach to quantum annealing of the 3-variable exclusive-or satisfiability problem (3-XORSAT). <i>Physical Review A</i>. American Physical Society. <a href=\"https://doi.org/10.1103/physreva.104.062423\">https://doi.org/10.1103/physreva.104.062423</a>","ama":"Medina Ramos RA, Serbyn M. Duality approach to quantum annealing of the 3-variable exclusive-or satisfiability problem (3-XORSAT). <i>Physical Review A</i>. 2021;104(6). doi:<a href=\"https://doi.org/10.1103/physreva.104.062423\">10.1103/physreva.104.062423</a>","mla":"Medina Ramos, Raimel A., and Maksym Serbyn. “Duality Approach to Quantum Annealing of the 3-Variable Exclusive-or Satisfiability Problem (3-XORSAT).” <i>Physical Review A</i>, vol. 104, no. 6, 062423, American Physical Society, 2021, doi:<a href=\"https://doi.org/10.1103/physreva.104.062423\">10.1103/physreva.104.062423</a>.","ista":"Medina Ramos RA, Serbyn M. 2021. Duality approach to quantum annealing of the 3-variable exclusive-or satisfiability problem (3-XORSAT). Physical Review A. 104(6), 062423."},"article_number":"062423","oa":1,"acknowledgement":"We would like to thank S. De Nicola, A. Michaidilis, T. Gulden, Y. Nez-Fernndez, P. Brighi, and S. Sack for fruitful discussions and valuable feedback on the manuscript. M.S. acknowledges useful discussions with E. Altman, L. Cugliandolo, and C. Laumann. We acknowledge support from the European Research Council (ERC) under the European Union's Horizon 2020 Research and Innovation Programme Grant Agreement No. 850899.","fulldoi":"https://doi.org/10.1103/physreva.104.062423","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"American Physical Society","isi":1,"date_created":"2021-12-14T20:46:07Z","arxiv":1,"date_updated":"2026-10-02T11:36:06Z","ec_funded":1,"publication_status":"published","article_processing_charge":"No","day":"14","publication_identifier":{"issn":["2469-9926"],"eissn":["2469-9934"]},"year":"2021","_id":"10545","abstract":[{"lang":"eng","text":"Classical models with complex energy landscapes represent a perspective avenue for the near-term application of quantum simulators. Until now, many theoretical works studied the performance of quantum algorithms for models with a unique ground state. However, when the classical problem is in a so-called clustering phase, the ground state manifold is highly degenerate. As an example, we consider a 3-XORSAT model defined on simple hypergraphs. The degeneracy of classical ground state manifold translates into the emergence of an extensive number of Z2 symmetries, which remain intact even in the presence of a quantum transverse magnetic field. We establish a general duality approach that restricts the quantum problem to a given sector of conserved Z2 charges and use it to study how the outcome of the quantum adiabatic algorithm depends on the hypergraph geometry. We show that the tree hypergraph which corresponds to a classically solvable instance of the 3-XORSAT problem features a constant gap, whereas the closed hypergraph encounters a second-order phase transition with a gap vanishing as a power-law in the problem size. The duality developed in this work provides a practical tool for studies of quantum models with classically degenerate energy manifold and reveals potential connections between glasses and gauge theories."}],"author":[{"orcid":"0000-0002-5383-2869","id":"CE680B90-D85A-11E9-B684-C920E6697425","first_name":"Raimel A","full_name":"Medina Ramos, Raimel A","last_name":"Medina Ramos"},{"last_name":"Serbyn","full_name":"Serbyn, Maksym","id":"47809E7E-F248-11E8-B48F-1D18A9856A87","first_name":"Maksym","orcid":"0000-0002-2399-5827"}],"title":"Duality approach to quantum annealing of the 3-variable exclusive-or satisfiability problem (3-XORSAT)","publication":"Physical Review A"},{"month":"04","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1101/848374"}],"intvolume":"       109","type":"journal_article","date_published":"2021-04-07T00:00:00Z","oa_version":"Preprint","volume":109,"external_id":{"isi":["000637809600006"],"pmid":["33592180"]},"language":[{"iso":"eng"}],"project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"department":[{"_id":"GaTk"}],"status":"public","corr_author":"1","pmid":1,"scopus_import":"1","doi":"10.1016/j.neuron.2021.01.020","related_material":{"link":[{"description":"News on IST Homepage","relation":"press_release","url":"https://ist.ac.at/en/news/can-evolution-be-predicted/"}],"record":[{"relation":"dissertation_contains","id":"15020","status":"public"}]},"publisher":"Cell Press","isi":1,"date_created":"2020-02-28T11:00:12Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","fulldoi":"https://doi.org/10.1016/j.neuron.2021.01.020","acknowledgement":"The authors thank Dario Ringach for providing the V1 receptive fields and Olivier Marre for providing the retinal receptive fields. W.M. was funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement no. 754411. M.H. was funded in part by Human Frontiers Science grant no. HFSP RGP0032/2018.","oa":1,"citation":{"chicago":"Mlynarski, Wiktor F, Michal Hledik, Thomas R Sokolowski, and Gašper Tkačik. “Statistical Analysis and Optimality of Neural Systems.” <i>Neuron</i>. Cell Press, 2021. <a href=\"https://doi.org/10.1016/j.neuron.2021.01.020\">https://doi.org/10.1016/j.neuron.2021.01.020</a>.","short":"W.F. Mlynarski, M. Hledik, T.R. Sokolowski, G. Tkačik, Neuron 109 (2021) 1227–1241.e5.","ista":"Mlynarski WF, Hledik M, Sokolowski TR, Tkačik G. 2021. Statistical analysis and optimality of neural systems. Neuron. 109(7), 1227–1241.e5.","mla":"Mlynarski, Wiktor F., et al. “Statistical Analysis and Optimality of Neural Systems.” <i>Neuron</i>, vol. 109, no. 7, Cell Press, 2021, p. 1227–1241.e5, doi:<a href=\"https://doi.org/10.1016/j.neuron.2021.01.020\">10.1016/j.neuron.2021.01.020</a>.","apa":"Mlynarski, W. F., Hledik, M., Sokolowski, T. R., &#38; Tkačik, G. (2021). Statistical analysis and optimality of neural systems. <i>Neuron</i>. Cell Press. <a href=\"https://doi.org/10.1016/j.neuron.2021.01.020\">https://doi.org/10.1016/j.neuron.2021.01.020</a>","ama":"Mlynarski WF, Hledik M, Sokolowski TR, Tkačik G. Statistical analysis and optimality of neural systems. <i>Neuron</i>. 2021;109(7):1227-1241.e5. doi:<a href=\"https://doi.org/10.1016/j.neuron.2021.01.020\">10.1016/j.neuron.2021.01.020</a>","ieee":"W. F. Mlynarski, M. Hledik, T. R. Sokolowski, and G. Tkačik, “Statistical analysis and optimality of neural systems,” <i>Neuron</i>, vol. 109, no. 7. Cell Press, p. 1227–1241.e5, 2021."},"issue":"7","publication":"Neuron","author":[{"first_name":"Wiktor F","id":"358A453A-F248-11E8-B48F-1D18A9856A87","last_name":"Mlynarski","full_name":"Mlynarski, Wiktor F"},{"last_name":"Hledik","full_name":"Hledik, Michal","id":"4171253A-F248-11E8-B48F-1D18A9856A87","first_name":"Michal"},{"last_name":"Sokolowski","full_name":"Sokolowski, Thomas R","first_name":"Thomas R","id":"3E999752-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1287-3779"},{"last_name":"Tkačik","full_name":"Tkačik, Gašper","orcid":"0000-0002-6699-1455","id":"3D494DCA-F248-11E8-B48F-1D18A9856A87","first_name":"Gašper"}],"title":"Statistical analysis and optimality of neural systems","abstract":[{"lang":"eng","text":"Normative theories and statistical inference provide complementary approaches for the study of biological systems. A normative theory postulates that organisms have adapted to efficiently solve essential tasks, and proceeds to mathematically work out testable consequences of such optimality; parameters that maximize the hypothesized organismal function can be derived ab initio, without reference to experimental data. In contrast, statistical inference focuses on efficient utilization of data to learn model parameters, without reference to any a priori notion of biological function, utility, or fitness. Traditionally, these two approaches were developed independently and applied separately. Here we unify them in a coherent Bayesian framework that embeds a normative theory into a family of maximum-entropy “optimization priors.” This family defines a smooth interpolation between a data-rich inference regime (characteristic of “bottom-up” statistical models), and a data-limited ab inito prediction regime (characteristic of “top-down” normative theory). We demonstrate the applicability of our framework using data from the visual cortex, and argue that the flexibility it affords is essential to address a number of fundamental challenges relating to inference and prediction in complex, high-dimensional biological problems."}],"page":"1227-1241.e5","year":"2021","_id":"7553","publication_status":"published","day":"07","article_processing_charge":"No","ec_funded":1,"date_updated":"2026-10-02T11:40:30Z"},{"_id":"8602","year":"2021","publication_identifier":{"issn":["1745-2473"],"eissn":["1745-2481"]},"title":"Theory of mechanochemical patterning and optimal migration in cell monolayers","author":[{"last_name":"Boocock","full_name":"Boocock, Daniel R","id":"453AF628-F248-11E8-B48F-1D18A9856A87","first_name":"Daniel R","orcid":"0000-0002-1585-2631"},{"first_name":"Naoya","full_name":"Hino, Naoya","last_name":"Hino"},{"full_name":"Ruzickova, Natalia","last_name":"Ruzickova","first_name":"Natalia","id":"D2761128-D73D-11E9-A1BF-BA0DE6697425"},{"first_name":"Tsuyoshi","last_name":"Hirashima","full_name":"Hirashima, Tsuyoshi"},{"orcid":"0000-0001-6005-1561","id":"3A9DB764-F248-11E8-B48F-1D18A9856A87","first_name":"Edouard B","full_name":"Hannezo, Edouard B","last_name":"Hannezo"}],"publication":"Nature Physics","abstract":[{"text":"Collective cell migration offers a rich field of study for non-equilibrium physics and cellular biology, revealing phenomena such as glassy dynamics, pattern formation and active turbulence. However, how mechanical and chemical signalling are integrated at the cellular level to give rise to such collective behaviours remains unclear. We address this by focusing on the highly conserved phenomenon of spatiotemporal waves of density and extracellular signal-regulated kinase (ERK) activation, which appear both in vitro and in vivo during collective cell migration and wound healing. First, we propose a biophysical theory, backed by mechanical and optogenetic perturbation experiments, showing that patterns can be quantitatively explained by a mechanochemical coupling between active cellular tensions and the mechanosensitive ERK pathway. Next, we demonstrate how this biophysical mechanism can robustly induce long-ranged order and migration in a desired orientation, and we determine the theoretically optimal wavelength and period for inducing maximal migration towards free edges, which fits well with experimentally observed dynamics. We thereby provide a bridge between the biophysical origin of spatiotemporal instabilities and the design principles of robust and efficient long-ranged migration.","lang":"eng"}],"page":"267-274","date_updated":"2026-10-02T22:30:07Z","publication_status":"published","article_processing_charge":"No","day":"01","ec_funded":1,"acknowledgement":"We would like to thank G. Tkacik and all of the members of the Hannezo and Hirashima groups for useful discussions, X. Trepat for help on traction force microscopy and M. Matsuda for use of the lab facility. E.H. acknowledges grants from the Austrian Science Fund (FWF) (P 31639) and the European Research Council (851288). T.H. acknowledges a grant from JST, PRESTO (JPMJPR1949). 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. 665385 (to D.B.), from JSPS KAKENHI grant no. 17J02107 (to N.H.) and from the SPIRITS 2018 of Kyoto University (to E.H. and T.H.).","fulldoi":"https://doi.org/10.1038/s41567-020-01037-7","publisher":"Springer Nature","isi":1,"date_created":"2020-10-04T22:01:37Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_type":"original","oa":1,"citation":{"ieee":"D. R. Boocock, N. Hino, N. Ruzickova, T. Hirashima, and E. B. Hannezo, “Theory of mechanochemical patterning and optimal migration in cell monolayers,” <i>Nature Physics</i>, vol. 17. Springer Nature, pp. 267–274, 2021.","ama":"Boocock DR, Hino N, Ruzickova N, Hirashima T, Hannezo EB. Theory of mechanochemical patterning and optimal migration in cell monolayers. <i>Nature Physics</i>. 2021;17:267-274. doi:<a href=\"https://doi.org/10.1038/s41567-020-01037-7\">10.1038/s41567-020-01037-7</a>","mla":"Boocock, Daniel R., et al. “Theory of Mechanochemical Patterning and Optimal Migration in Cell Monolayers.” <i>Nature Physics</i>, vol. 17, Springer Nature, 2021, pp. 267–74, doi:<a href=\"https://doi.org/10.1038/s41567-020-01037-7\">10.1038/s41567-020-01037-7</a>.","apa":"Boocock, D. R., Hino, N., Ruzickova, N., Hirashima, T., &#38; Hannezo, E. B. (2021). Theory of mechanochemical patterning and optimal migration in cell monolayers. <i>Nature Physics</i>. Springer Nature. <a href=\"https://doi.org/10.1038/s41567-020-01037-7\">https://doi.org/10.1038/s41567-020-01037-7</a>","ista":"Boocock DR, Hino N, Ruzickova N, Hirashima T, Hannezo EB. 2021. Theory of mechanochemical patterning and optimal migration in cell monolayers. Nature Physics. 17, 267–274.","short":"D.R. Boocock, N. Hino, N. Ruzickova, T. Hirashima, E.B. Hannezo, Nature Physics 17 (2021) 267–274.","chicago":"Boocock, Daniel R, Naoya Hino, Natalia Ruzickova, Tsuyoshi Hirashima, and Edouard B Hannezo. “Theory of Mechanochemical Patterning and Optimal Migration in Cell Monolayers.” <i>Nature Physics</i>. Springer Nature, 2021. <a href=\"https://doi.org/10.1038/s41567-020-01037-7\">https://doi.org/10.1038/s41567-020-01037-7</a>."},"corr_author":"1","project":[{"name":"Active mechano-chemical description of the cell cytoskeleton","grant_number":"P31639","_id":"268294B6-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"05943252-7A3F-11EA-A408-12923DDC885E","grant_number":"851288","name":"Design Principles of Branching Morphogenesis","call_identifier":"H2020"},{"call_identifier":"H2020","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program"}],"department":[{"_id":"EdHa"}],"status":"public","doi":"10.1038/s41567-020-01037-7","related_material":{"record":[{"relation":"dissertation_contains","id":"12964","status":"public"}],"link":[{"relation":"press_release","url":"https://ist.ac.at/en/news/wound-healing-waves/","description":"News on IST Homepage"}]},"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1101/2020.05.15.096479"}],"quality_controlled":"1","month":"02","volume":17,"external_id":{"isi":["000573519500002"]},"language":[{"iso":"eng"}],"intvolume":"        17","date_published":"2021-02-01T00:00:00Z","type":"journal_article","oa_version":"Preprint"},{"scopus_import":"1","doi":"10.1145/3450626.3459800","related_material":{"link":[{"url":"https://ist.ac.at/en/news/designing-with-elastic-structures/","relation":"press_release","description":"News on IST Website"}],"record":[{"id":"12897","relation":"dissertation_contains","status":"public"}]},"status":"public","has_accepted_license":"1","project":[{"call_identifier":"H2020","grant_number":"715767","name":"MATERIALIZABLE: Intelligent fabrication-oriented Computational Design and Modeling","_id":"24F9549A-B435-11E9-9278-68D0E5697425"}],"department":[{"_id":"BeBi"}],"oa_version":"Published Version","intvolume":"        40","date_published":"2021-07-19T00:00:00Z","type":"journal_article","volume":40,"external_id":{"isi":["000674930900091"]},"keyword":["Computing methodologies","shape modeling","modeling and simulation","theory of computation","computational geometry","mathematics of computing","mathematical optimization"],"language":[{"iso":"eng"}],"month":"07","ddc":["516"],"file":[{"date_created":"2021-10-18T10:42:15Z","file_id":"10150","success":1,"access_level":"open_access","relation":"main_file","file_size":17064290,"checksum":"7e5d08ce46b0451b3102eacd3d00f85f","creator":"chafner","content_type":"application/pdf","file_name":"elastic-curves-paper.pdf","date_updated":"2021-10-18T10:42:15Z"},{"access_level":"open_access","file_id":"10151","date_created":"2021-10-18T10:42:22Z","file_size":547156,"relation":"supplementary_material","content_type":"application/pdf","creator":"chafner","checksum":"0088643478be7c01a703b5b10767348f","date_updated":"2021-10-18T10:42:22Z","file_name":"elastic-curves-supp.pdf"}],"quality_controlled":"1","ec_funded":1,"publication_status":"published","article_processing_charge":"No","day":"19","date_updated":"2026-10-02T22:30:08Z","abstract":[{"text":"Elastic bending of initially flat slender elements allows the realization and economic fabrication of intriguing curved shapes. In this work, we derive an intuitive but rigorous geometric characterization of the design space of plane elastic rods with variable stiffness. It enables designers to determine which shapes are physically viable with active bending by visual inspection alone. Building on these insights, we propose a method for efficiently designing the geometry of a flat elastic rod that realizes a target equilibrium curve, which only requires solving a linear program. We implement this method in an interactive computational design tool that gives feedback about the feasibility of a design, and computes the geometry of the structural elements necessary to realize it within an instant. The tool also offers an iterative optimization routine that improves the fabricability of a model while modifying it as little as possible. In addition, we use our geometric characterization to derive an algorithm for analyzing and recovering the stability of elastic curves that would otherwise snap out of their unstable equilibrium shapes by buckling. We show the efficacy of our approach by designing and manufacturing several physical models that are assembled from flat elements.","lang":"eng"}],"author":[{"full_name":"Hafner, Christian","last_name":"Hafner","first_name":"Christian","id":"400429CC-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0001-6511-9385","id":"49876194-F248-11E8-B48F-1D18A9856A87","first_name":"Bernd","full_name":"Bickel, Bernd","last_name":"Bickel"}],"title":"The design space of plane elastic curves","publication":"ACM Transactions on Graphics","publication_identifier":{"issn":["0730-0301"],"eissn":["1557-7368"]},"year":"2021","_id":"9817","conference":{"start_date":"2021-08-09","end_date":"2021-08-13","location":"Virtual","name":"SIGGRAF: Special Interest Group on Computer Graphics and Interactive Techniques"},"citation":{"chicago":"Hafner, Christian, and Bernd Bickel. “The Design Space of Plane Elastic Curves.” <i>ACM Transactions on Graphics</i>. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3450626.3459800\">https://doi.org/10.1145/3450626.3459800</a>.","short":"C. Hafner, B. Bickel, ACM Transactions on Graphics 40 (2021).","ama":"Hafner C, Bickel B. The design space of plane elastic curves. <i>ACM Transactions on Graphics</i>. 2021;40(4). doi:<a href=\"https://doi.org/10.1145/3450626.3459800\">10.1145/3450626.3459800</a>","apa":"Hafner, C., &#38; Bickel, B. (2021). The design space of plane elastic curves. <i>ACM Transactions on Graphics</i>. Virtual: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3450626.3459800\">https://doi.org/10.1145/3450626.3459800</a>","mla":"Hafner, Christian, and Bernd Bickel. “The Design Space of Plane Elastic Curves.” <i>ACM Transactions on Graphics</i>, vol. 40, no. 4, 126, Association for Computing Machinery, 2021, doi:<a href=\"https://doi.org/10.1145/3450626.3459800\">10.1145/3450626.3459800</a>.","ista":"Hafner C, Bickel B. 2021. The design space of plane elastic curves. ACM Transactions on Graphics. 40(4), 126.","ieee":"C. Hafner and B. Bickel, “The design space of plane elastic curves,” <i>ACM Transactions on Graphics</i>, vol. 40, no. 4. Association for Computing Machinery, 2021."},"file_date_updated":"2021-10-18T10:42:22Z","article_number":"126","oa":1,"issue":"4","article_type":"original","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publisher":"Association for Computing Machinery","isi":1,"date_created":"2021-08-08T22:01:26Z","fulldoi":"https://doi.org/10.1145/3450626.3459800","acknowledgement":"We thank the anonymous reviewers for their generous feedback, and Michal Piovarči for his help in producing the supplemental video. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 715767).\r\n","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"}},{"scopus_import":"1","doi":"10.1038/s41467-021-23123-x","related_material":{"record":[{"status":"public","id":"19557","relation":"dissertation_contains"},{"relation":"earlier_version","id":"7800","status":"public"},{"id":"12401","relation":"dissertation_contains","status":"public"}],"link":[{"relation":"press_release","url":"https://ist.ac.at/en/news/defective-gene-slows-down-brain-cells/"}]},"has_accepted_license":"1","status":"public","project":[{"call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"},{"call_identifier":"H2020","name":"Probing the Reversibility of Autism Spectrum Disorders by Employing in vivo and in vitro Models","grant_number":"715508","_id":"25444568-B435-11E9-9278-68D0E5697425"},{"_id":"2548AE96-B435-11E9-9278-68D0E5697425","grant_number":"W1232","name":"Molecular Drug Targets","call_identifier":"FWF"},{"grant_number":"F7807","_id":"05A0D778-7A3F-11EA-A408-12923DDC885E","name":"Stem Cell Modulation in Neural Development and Regeneration/ P07-Neural stem cells in autism and epilepsy"},{"grant_number":"I03600","_id":"265CB4D0-B435-11E9-9278-68D0E5697425","name":"Optical control of synaptic function via adhesion molecules","call_identifier":"FWF"}],"department":[{"_id":"GaNo"},{"_id":"JoDa"},{"_id":"FlSc"},{"_id":"MiSi"},{"_id":"LifeSc"},{"_id":"Bio"}],"corr_author":"1","oa_version":"Published Version","intvolume":"        12","acknowledged_ssus":[{"_id":"PreCl"}],"type":"journal_article","date_published":"2021-05-24T00:00:00Z","external_id":{"isi":["000658769900010"]},"volume":12,"language":[{"iso":"eng"}],"keyword":["General Biochemistry","Genetics and Molecular Biology"],"month":"05","ddc":["572"],"file":[{"file_name":"2021_NatureCommunications_Morandell.pdf","date_updated":"2021-05-28T12:39:43Z","creator":"kschuh","checksum":"337e0f7959c35ec959984cacdcb472ba","content_type":"application/pdf","relation":"main_file","file_size":9358599,"date_created":"2021-05-28T12:39:43Z","access_level":"open_access","file_id":"9430","success":1}],"quality_controlled":"1","ec_funded":1,"publication_status":"published","article_processing_charge":"No","day":"24","date_updated":"2026-10-02T22:30:15Z","abstract":[{"text":"De novo loss of function mutations in the ubiquitin ligase-encoding gene Cullin3 lead to autism spectrum disorder (ASD). In mouse, constitutive haploinsufficiency leads to motor coordination deficits as well as ASD-relevant social and cognitive impairments. However, induction of Cul3 haploinsufficiency later in life does not lead to ASD-relevant behaviors, pointing to an important role of Cul3 during a critical developmental window. Here we show that Cul3 is essential to regulate neuronal migration and, therefore, constitutive Cul3 heterozygous mutant mice display cortical lamination abnormalities. At the molecular level, we found that Cul3 controls neuronal migration by tightly regulating the amount of Plastin3 (Pls3), a previously unrecognized player of neural migration. Furthermore, we found that Pls3 cell-autonomously regulates cell migration by regulating actin cytoskeleton organization, and its levels are inversely proportional to neural migration speed. Finally, we provide evidence that cellular phenotypes associated with autism-linked gene haploinsufficiency can be rescued by transcriptional activation of the intact allele in vitro, offering a proof of concept for a potential therapeutic approach for ASDs.","lang":"eng"}],"publication":"Nature Communications","title":"Cul3 regulates cytoskeleton protein homeostasis and cell migration during a critical window of brain development","author":[{"last_name":"Morandell","full_name":"Morandell, Jasmin","id":"4739D480-F248-11E8-B48F-1D18A9856A87","first_name":"Jasmin"},{"id":"29A8453C-F248-11E8-B48F-1D18A9856A87","first_name":"Lena A","last_name":"Schwarz","full_name":"Schwarz, Lena A"},{"full_name":"Basilico, Bernadette","last_name":"Basilico","orcid":"0000-0003-1843-3173","first_name":"Bernadette","id":"36035796-5ACA-11E9-A75E-7AF2E5697425"},{"first_name":"Saren","id":"4323B49C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-1671-393X","last_name":"Tasciyan","full_name":"Tasciyan, Saren"},{"last_name":"Dimchev","full_name":"Dimchev, Georgi A","id":"38C393BE-F248-11E8-B48F-1D18A9856A87","first_name":"Georgi A","orcid":"0000-0001-8370-6161"},{"full_name":"Nicolas, Armel","last_name":"Nicolas","id":"2A103192-F248-11E8-B48F-1D18A9856A87","first_name":"Armel"},{"full_name":"Sommer, Christoph M","last_name":"Sommer","first_name":"Christoph M","id":"4DF26D8C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-1216-9105"},{"id":"382077BA-F248-11E8-B48F-1D18A9856A87","first_name":"Caroline","full_name":"Kreuzinger, Caroline","last_name":"Kreuzinger"},{"last_name":"Dotter","full_name":"Dotter, Christoph","first_name":"Christoph","id":"4C66542E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9033-9096"},{"id":"3B2ABCF4-F248-11E8-B48F-1D18A9856A87","first_name":"Lisa","full_name":"Knaus, Lisa","last_name":"Knaus"},{"id":"D23090A2-9057-11EA-883A-A8396FC7A38F","first_name":"Zoe","last_name":"Dobler","full_name":"Dobler, Zoe"},{"full_name":"Cacci, Emanuele","last_name":"Cacci","first_name":"Emanuele"},{"first_name":"Florian KM","id":"48AD8942-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-4790-8078","last_name":"Schur","full_name":"Schur, Florian KM"},{"id":"42EFD3B6-F248-11E8-B48F-1D18A9856A87","first_name":"Johann G","orcid":"0000-0001-8559-3973","full_name":"Danzl, Johann G","last_name":"Danzl"},{"orcid":"0000-0002-7673-7178","id":"3E57A680-F248-11E8-B48F-1D18A9856A87","first_name":"Gaia","last_name":"Novarino","full_name":"Novarino, Gaia"}],"publication_identifier":{"eissn":["2041-1723"]},"year":"2021","_id":"9429","citation":{"ista":"Morandell J, Schwarz LA, Basilico B, Tasciyan S, Dimchev GA, Nicolas A, Sommer CM, Kreuzinger C, Dotter C, Knaus L, Dobler Z, Cacci E, Schur FK, Danzl JG, Novarino G. 2021. Cul3 regulates cytoskeleton protein homeostasis and cell migration during a critical window of brain development. Nature Communications. 12(1), 3058.","apa":"Morandell, J., Schwarz, L. A., Basilico, B., Tasciyan, S., Dimchev, G. A., Nicolas, A., … Novarino, G. (2021). Cul3 regulates cytoskeleton protein homeostasis and cell migration during a critical window of brain development. <i>Nature Communications</i>. Springer Nature. <a href=\"https://doi.org/10.1038/s41467-021-23123-x\">https://doi.org/10.1038/s41467-021-23123-x</a>","ama":"Morandell J, Schwarz LA, Basilico B, et al. Cul3 regulates cytoskeleton protein homeostasis and cell migration during a critical window of brain development. <i>Nature Communications</i>. 2021;12(1). doi:<a href=\"https://doi.org/10.1038/s41467-021-23123-x\">10.1038/s41467-021-23123-x</a>","mla":"Morandell, Jasmin, et al. “Cul3 Regulates Cytoskeleton Protein Homeostasis and Cell Migration during a Critical Window of Brain Development.” <i>Nature Communications</i>, vol. 12, no. 1, 3058, Springer Nature, 2021, doi:<a href=\"https://doi.org/10.1038/s41467-021-23123-x\">10.1038/s41467-021-23123-x</a>.","ieee":"J. Morandell <i>et al.</i>, “Cul3 regulates cytoskeleton protein homeostasis and cell migration during a critical window of brain development,” <i>Nature Communications</i>, vol. 12, no. 1. Springer Nature, 2021.","chicago":"Morandell, Jasmin, Lena A Schwarz, Bernadette Basilico, Saren Tasciyan, Georgi A Dimchev, Armel Nicolas, Christoph M Sommer, et al. “Cul3 Regulates Cytoskeleton Protein Homeostasis and Cell Migration during a Critical Window of Brain Development.” <i>Nature Communications</i>. Springer Nature, 2021. <a href=\"https://doi.org/10.1038/s41467-021-23123-x\">https://doi.org/10.1038/s41467-021-23123-x</a>.","short":"J. Morandell, L.A. Schwarz, B. Basilico, S. Tasciyan, G.A. Dimchev, A. Nicolas, C.M. Sommer, C. Kreuzinger, C. Dotter, L. Knaus, Z. Dobler, E. Cacci, F.K. Schur, J.G. Danzl, G. Novarino, Nature Communications 12 (2021)."},"file_date_updated":"2021-05-28T12:39:43Z","article_number":"3058","oa":1,"issue":"1","article_type":"original","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","isi":1,"publisher":"Springer Nature","date_created":"2021-05-28T11:49:46Z","fulldoi":"https://doi.org/10.1038/s41467-021-23123-x","acknowledgement":"We thank A. Coll Manzano, F. Freeman, M. Ladron de Guevara, and A. Ç. Yahya for technical assistance, S. Deixler, A. Lepold, and A. Schlerka for the management of our animal colony, as well as M. Schunn and the Preclinical Facility team for technical assistance. We thank K. Heesom and her team at the University of Bristol Proteomics Facility for the proteomics sample preparation, data generation, and analysis support. We thank Y. B. Simon for kindly providing the plasmid for lentiviral labeling. Further, we thank M. Sixt for his advice regarding cell migration and the fruitful discussions. This work was supported by the ISTPlus postdoctoral fellowship (Grant Agreement No. 754411) to B.B., by the European Union’s Horizon 2020 research and innovation program (ERC) grant 715508 (REVERSEAUTISM), and by the Austrian Science Fund (FWF) to G.N. (DK W1232-B24 and SFB F7807-B) and to J.G.D (I3600-B27).","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"}}]