[{"doi":"10.1007/s00446-022-00439-5","year":"2023","external_id":{"isi":["000890138700001"]},"title":"Long-lived counters with polylogarithmic amortized step complexity","main_file_link":[{"open_access":"1","url":"https://drops.dagstuhl.de/opus/volltexte/2019/11310/"}],"isi":1,"publication_status":"published","citation":{"chicago":"Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers. “Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” <i>Distributed Computing</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00446-022-00439-5\">https://doi.org/10.1007/s00446-022-00439-5</a>.","ieee":"M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived counters with polylogarithmic amortized step complexity,” <i>Distributed Computing</i>, vol. 36. Springer Nature, pp. 29–43, 2023.","apa":"Baig, M. A., Hendler, D., Milani, A., &#38; Travers, C. (2023). Long-lived counters with polylogarithmic amortized step complexity. <i>Distributed Computing</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00446-022-00439-5\">https://doi.org/10.1007/s00446-022-00439-5</a>","ista":"Baig MA, Hendler D, Milani A, Travers C. 2023. Long-lived counters with polylogarithmic amortized step complexity. Distributed Computing. 36, 29–43.","short":"M.A. Baig, D. Hendler, A. Milani, C. Travers, Distributed Computing 36 (2023) 29–43.","mla":"Baig, Mirza Ahad, et al. “Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” <i>Distributed Computing</i>, vol. 36, Springer Nature, 2023, pp. 29–43, doi:<a href=\"https://doi.org/10.1007/s00446-022-00439-5\">10.1007/s00446-022-00439-5</a>.","ama":"Baig MA, Hendler D, Milani A, Travers C. Long-lived counters with polylogarithmic amortized step complexity. <i>Distributed Computing</i>. 2023;36:29-43. doi:<a href=\"https://doi.org/10.1007/s00446-022-00439-5\">10.1007/s00446-022-00439-5</a>"},"abstract":[{"text":"A shared-memory counter is a widely-used and well-studied concurrent object. It supports two operations: An Inc operation that increases its value by 1 and a Read operation that returns its current value. In Jayanti et al (SIAM J Comput, 30(2), 2000), Jayanti, Tan and Toueg proved a linear lower bound on the worst-case step complexity of obstruction-free implementations, from read-write registers, of a large class of shared objects that includes counters. The lower bound leaves open the question of finding counter implementations with sub-linear amortized step complexity. In this work, we address this gap. We show that n-process, wait-free and linearizable counters can be implemented from read-write registers with O(log2n) amortized step complexity. This is the first counter algorithm from read-write registers that provides sub-linear amortized step complexity in executions of arbitrary length. Since a logarithmic lower bound on the amortized step complexity of obstruction-free counter implementations exists, our upper bound is within a logarithmic factor of the optimal. The worst-case step complexity of the construction remains linear, which is optimal. This is obtained thanks to a new max register construction with O(logn) amortized step complexity in executions of arbitrary length in which the value stored in the register does not grow too quickly. We then leverage an existing counter algorithm by Aspnes, Attiya and Censor-Hillel [1] in which we “plug” our max register implementation to show that it remains linearizable while achieving O(log2n) amortized step complexity.","lang":"eng"}],"author":[{"last_name":"Baig","full_name":"Baig, Mirza Ahad","first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425"},{"first_name":"Danny","full_name":"Hendler, Danny","last_name":"Hendler"},{"last_name":"Milani","full_name":"Milani, Alessia","first_name":"Alessia"},{"first_name":"Corentin","full_name":"Travers, Corentin","last_name":"Travers"}],"keyword":["Computational Theory and Mathematics","Computer Networks and Communications","Hardware and Architecture","Theoretical Computer Science"],"date_updated":"2023-08-16T08:39:36Z","oa":1,"volume":36,"article_processing_charge":"No","_id":"12164","publication_identifier":{"eissn":["1432-0452"],"issn":["0178-2770"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"A preliminary version of this work appeared in DISC’19. Mirza Ahad Baig, Alessia Milani and Corentin Travers are supported by ANR projects Descartes and FREDDA. Mirza Ahad Baig is supported by UMI Relax. Danny Hendler is supported by the Israel Science Foundation (Grants 380/18 and 1425/22).","quality_controlled":"1","oa_version":"Preprint","month":"03","date_published":"2023-03-01T00:00:00Z","article_type":"original","publisher":"Springer Nature","scopus_import":"1","language":[{"iso":"eng"}],"department":[{"_id":"KrPi"}],"date_created":"2023-01-12T12:10:08Z","day":"01","type":"journal_article","intvolume":"        36","status":"public","publication":"Distributed Computing","page":"29-43"},{"scopus_import":"1","publisher":"Springer Nature","language":[{"iso":"eng"}],"month":"07","date_published":"2022-07-01T00:00:00Z","article_type":"original","date_created":"2022-03-10T12:16:19Z","department":[{"_id":"GradSch"}],"intvolume":"        14","status":"public","day":"01","type":"journal_article","publication":"Cryptography and Communications","issue":"4","page":"933-948","title":"Factorization of some polynomials over finite local commutative rings and applications to certain self-dual and LCD codes","external_id":{"isi":["000766422000002"]},"year":"2022","doi":"10.1007/s12095-022-00557-8","isi":1,"abstract":[{"text":"We determine the unique factorization of some polynomials over a finite local commutative ring with identity explicitly. This solves and generalizes the main conjecture of Qian, Shi and Solé in [13]. We also give some applications to enumeration of certain generalized double circulant self-dual and linear complementary dual (LCD) codes over some finite rings together with an application in asymptotic coding theory.","lang":"eng"}],"keyword":["Applied Mathematics","Computational Theory and Mathematics","Computer Networks and Communications"],"author":[{"id":"8ba3170d-dc85-11ea-9058-c4251c96a6eb","last_name":"Köse","full_name":"Köse, Seyda","first_name":"Seyda"},{"full_name":"Özbudak, Ferruh","last_name":"Özbudak","first_name":"Ferruh"}],"citation":{"ieee":"S. Köse and F. Özbudak, “Factorization of some polynomials over finite local commutative rings and applications to certain self-dual and LCD codes,” <i>Cryptography and Communications</i>, vol. 14, no. 4. Springer Nature, pp. 933–948, 2022.","apa":"Köse, S., &#38; Özbudak, F. (2022). Factorization of some polynomials over finite local commutative rings and applications to certain self-dual and LCD codes. <i>Cryptography and Communications</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s12095-022-00557-8\">https://doi.org/10.1007/s12095-022-00557-8</a>","chicago":"Köse, Seyda, and Ferruh Özbudak. “Factorization of Some Polynomials over Finite Local Commutative Rings and Applications to Certain Self-Dual and LCD Codes.” <i>Cryptography and Communications</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s12095-022-00557-8\">https://doi.org/10.1007/s12095-022-00557-8</a>.","mla":"Köse, Seyda, and Ferruh Özbudak. “Factorization of Some Polynomials over Finite Local Commutative Rings and Applications to Certain Self-Dual and LCD Codes.” <i>Cryptography and Communications</i>, vol. 14, no. 4, Springer Nature, 2022, pp. 933–48, doi:<a href=\"https://doi.org/10.1007/s12095-022-00557-8\">10.1007/s12095-022-00557-8</a>.","ama":"Köse S, Özbudak F. Factorization of some polynomials over finite local commutative rings and applications to certain self-dual and LCD codes. <i>Cryptography and Communications</i>. 2022;14(4):933-948. doi:<a href=\"https://doi.org/10.1007/s12095-022-00557-8\">10.1007/s12095-022-00557-8</a>","short":"S. Köse, F. Özbudak, Cryptography and Communications 14 (2022) 933–948.","ista":"Köse S, Özbudak F. 2022. Factorization of some polynomials over finite local commutative rings and applications to certain self-dual and LCD codes. Cryptography and Communications. 14(4), 933–948."},"publication_status":"published","publication_identifier":{"eissn":["1936-2455"],"issn":["1936-2447"]},"_id":"10842","quality_controlled":"1","oa_version":"None","acknowledgement":"The authors would like to thank Prof. Dr. Minjia Shi for bringing [13, Conjecture 3.5] to our attention. We would also like to thank the associate editor and anonymous reviewers for their valuable comments and suggestions which improved and clarified the manuscript.","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","volume":14,"date_updated":"2023-09-05T15:35:55Z"},{"publication_status":"published","citation":{"mla":"Kretinsky, Jan, et al. “Index Appearance Record with Preorders.” <i>Acta Informatica</i>, vol. 59, Springer Nature, 2022, pp. 585–618, doi:<a href=\"https://doi.org/10.1007/s00236-021-00412-y\">10.1007/s00236-021-00412-y</a>.","ama":"Kretinsky J, Meggendorfer T, Waldmann C, Weininger M. Index appearance record with preorders. <i>Acta Informatica</i>. 2022;59:585-618. doi:<a href=\"https://doi.org/10.1007/s00236-021-00412-y\">10.1007/s00236-021-00412-y</a>","short":"J. Kretinsky, T. Meggendorfer, C. Waldmann, M. Weininger, Acta Informatica 59 (2022) 585–618.","ista":"Kretinsky J, Meggendorfer T, Waldmann C, Weininger M. 2022. Index appearance record with preorders. Acta Informatica. 59, 585–618.","apa":"Kretinsky, J., Meggendorfer, T., Waldmann, C., &#38; Weininger, M. (2022). Index appearance record with preorders. <i>Acta Informatica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00236-021-00412-y\">https://doi.org/10.1007/s00236-021-00412-y</a>","ieee":"J. Kretinsky, T. Meggendorfer, C. Waldmann, and M. Weininger, “Index appearance record with preorders,” <i>Acta Informatica</i>, vol. 59. Springer Nature, pp. 585–618, 2022.","chicago":"Kretinsky, Jan, Tobias Meggendorfer, Clara Waldmann, and Maximilian Weininger. “Index Appearance Record with Preorders.” <i>Acta Informatica</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s00236-021-00412-y\">https://doi.org/10.1007/s00236-021-00412-y</a>."},"keyword":["computer networks and communications","information systems","software"],"author":[{"first_name":"Jan","orcid":"0000-0002-8122-2881","last_name":"Kretinsky","full_name":"Kretinsky, Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87"},{"id":"b21b0c15-30a2-11eb-80dc-f13ca25802e1","first_name":"Tobias","orcid":"0000-0002-1712-2165","last_name":"Meggendorfer","full_name":"Meggendorfer, Tobias"},{"last_name":"Waldmann","full_name":"Waldmann, Clara","first_name":"Clara"},{"first_name":"Maximilian","last_name":"Weininger","full_name":"Weininger, Maximilian"}],"abstract":[{"lang":"eng","text":"Transforming ω-automata into parity automata is traditionally done using appearance records. We present an efficient variant of this idea, tailored to Rabin automata, and several optimizations applicable to all appearance records. We compare the methods experimentally and show that our method produces significantly smaller automata than previous approaches."}],"oa":1,"date_updated":"2023-08-02T13:49:28Z","volume":59,"article_processing_charge":"Yes (via OA deal)","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","acknowledgement":"This work is partially funded by the German Research Foundation (DFG) projects Verified Model Checkers (No. 317422601) and Statistical Unbounded Verification (No. 383882557), and the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research. It is an extended version of [21], including all proofs together with further explanations and examples. Moreover, we provide a new, more efficient construction based on (total) preorders, unifying previous optimizations. Experiments are performed with a new, performant implementation, comparing our approach to the current state of the art.","oa_version":"Published Version","quality_controlled":"1","project":[{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"_id":"10602","publication_identifier":{"issn":["0001-5903"],"eissn":["1432-0525"]},"doi":"10.1007/s00236-021-00412-y","year":"2022","title":"Index appearance record with preorders","external_id":{"isi":["000735765500001"]},"isi":1,"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ddc":["000"],"type":"journal_article","day":"01","status":"public","intvolume":"        59","page":"585-618","file_date_updated":"2022-01-07T07:50:31Z","publication":"Acta Informatica","article_type":"original","date_published":"2022-10-01T00:00:00Z","month":"10","language":[{"iso":"eng"}],"publisher":"Springer Nature","scopus_import":"1","department":[{"_id":"KrCh"}],"has_accepted_license":"1","file":[{"date_updated":"2022-01-07T07:50:31Z","access_level":"open_access","file_name":"2021_ActaInfor_Křetínský.pdf","file_size":1066082,"date_created":"2022-01-07T07:50:31Z","checksum":"bf1c195b6aaf59e8530cf9e3a9d731f7","content_type":"application/pdf","relation":"main_file","creator":"cchlebak","file_id":"10603","success":1}],"date_created":"2022-01-06T12:37:27Z"},{"year":"2022","doi":"10.1088/2632-072x/ac99cd","title":"Explosive transitions in epidemic dynamics","article_number":"04LT02","tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ddc":["530"],"citation":{"ama":"Börner G, Schröder M, Scarselli D, Budanur NB, Hof B, Timme M. Explosive transitions in epidemic dynamics. <i>Journal of Physics: Complexity</i>. 2022;3(4). doi:<a href=\"https://doi.org/10.1088/2632-072x/ac99cd\">10.1088/2632-072x/ac99cd</a>","mla":"Börner, Georg, et al. “Explosive Transitions in Epidemic Dynamics.” <i>Journal of Physics: Complexity</i>, vol. 3, no. 4, 04LT02, IOP Publishing, 2022, doi:<a href=\"https://doi.org/10.1088/2632-072x/ac99cd\">10.1088/2632-072x/ac99cd</a>.","short":"G. Börner, M. Schröder, D. Scarselli, N.B. Budanur, B. Hof, M. Timme, Journal of Physics: Complexity 3 (2022).","ista":"Börner G, Schröder M, Scarselli D, Budanur NB, Hof B, Timme M. 2022. Explosive transitions in epidemic dynamics. Journal of Physics: Complexity. 3(4), 04LT02.","apa":"Börner, G., Schröder, M., Scarselli, D., Budanur, N. B., Hof, B., &#38; Timme, M. (2022). Explosive transitions in epidemic dynamics. <i>Journal of Physics: Complexity</i>. IOP Publishing. <a href=\"https://doi.org/10.1088/2632-072x/ac99cd\">https://doi.org/10.1088/2632-072x/ac99cd</a>","ieee":"G. Börner, M. Schröder, D. Scarselli, N. B. Budanur, B. Hof, and M. Timme, “Explosive transitions in epidemic dynamics,” <i>Journal of Physics: Complexity</i>, vol. 3, no. 4. IOP Publishing, 2022.","chicago":"Börner, Georg, Malte Schröder, Davide Scarselli, Nazmi B Budanur, Björn Hof, and Marc Timme. “Explosive Transitions in Epidemic Dynamics.” <i>Journal of Physics: Complexity</i>. IOP Publishing, 2022. <a href=\"https://doi.org/10.1088/2632-072x/ac99cd\">https://doi.org/10.1088/2632-072x/ac99cd</a>."},"publication_status":"published","author":[{"full_name":"Börner, Georg","last_name":"Börner","first_name":"Georg"},{"first_name":"Malte","last_name":"Schröder","full_name":"Schröder, Malte"},{"id":"40315C30-F248-11E8-B48F-1D18A9856A87","full_name":"Scarselli, Davide","last_name":"Scarselli","orcid":"0000-0001-5227-4271","first_name":"Davide"},{"id":"3EA1010E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-0423-5010","full_name":"Budanur, Nazmi B","last_name":"Budanur","first_name":"Nazmi B"},{"id":"3A374330-F248-11E8-B48F-1D18A9856A87","first_name":"Björn","orcid":"0000-0003-2057-2754","full_name":"Hof, Björn","last_name":"Hof"},{"first_name":"Marc","full_name":"Timme, Marc","last_name":"Timme"}],"keyword":["Artificial Intelligence","Computer Networks and Communications","Computer Science Applications","Information Systems"],"abstract":[{"lang":"eng","text":"Standard epidemic models exhibit one continuous, second order phase transition to macroscopic outbreaks. However, interventions to control outbreaks may fundamentally alter epidemic dynamics. Here we reveal how such interventions modify the type of phase transition. In particular, we uncover three distinct types of explosive phase transitions for epidemic dynamics with capacity-limited interventions. Depending on the capacity limit, interventions may (i) leave the standard second order phase transition unchanged but exponentially suppress the probability of large outbreaks, (ii) induce a first-order discontinuous transition to macroscopic outbreaks, or (iii) cause a secondary explosive yet continuous third-order transition. These insights highlight inherent limitations in predicting and containing epidemic outbreaks. More generally our study offers a cornerstone example of a third-order explosive phase transition in complex systems."}],"article_processing_charge":"No","volume":3,"date_updated":"2023-02-13T09:15:13Z","oa":1,"quality_controlled":"1","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"We acknowledge support from the Volkswagen Foundation under Grant No. 99720 and the German Federal Ministry for Education and Research (BMBF) under Grant No. 16ICR01. This research was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy—EXC-2068—390729961—Cluster of Excellence Physics of Life of TU Dresden.","publication_identifier":{"issn":["2632-072X"]},"_id":"12134","article_type":"original","date_published":"2022-10-25T00:00:00Z","month":"10","language":[{"iso":"eng"}],"scopus_import":"1","publisher":"IOP Publishing","department":[{"_id":"BjHo"}],"has_accepted_license":"1","file":[{"success":1,"content_type":"application/pdf","relation":"main_file","file_id":"12350","creator":"dernst","file_name":"2022_JourPhysics_Boerner.pdf","file_size":1006106,"date_created":"2023-01-24T07:24:37Z","checksum":"35c5c5cb0eb17ea1b5184755daab9fc9","date_updated":"2023-01-24T07:24:37Z","access_level":"open_access"}],"date_created":"2023-01-12T12:03:43Z","type":"journal_article","day":"25","status":"public","intvolume":"         3","file_date_updated":"2023-01-24T07:24:37Z","publication":"Journal of Physics: Complexity","issue":"4"},{"title":"Closed-form continuous-time neural networks","external_id":{"arxiv":["2106.13898"],"isi":["000884215600003"]},"doi":"10.1038/s42256-022-00556-7","year":"2022","ddc":["000"],"related_material":{"link":[{"url":"https://doi.org/10.1038/s42256-022-00597-y","relation":"erratum"}]},"isi":1,"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"keyword":["Artificial Intelligence","Computer Networks and Communications","Computer Vision and Pattern Recognition","Human-Computer Interaction","Software"],"author":[{"first_name":"Ramin","full_name":"Hasani, Ramin","last_name":"Hasani"},{"id":"3DC22916-F248-11E8-B48F-1D18A9856A87","full_name":"Lechner, Mathias","last_name":"Lechner","first_name":"Mathias"},{"first_name":"Alexander","full_name":"Amini, Alexander","last_name":"Amini"},{"first_name":"Lucas","full_name":"Liebenwein, Lucas","last_name":"Liebenwein"},{"last_name":"Ray","full_name":"Ray, Aaron","first_name":"Aaron"},{"last_name":"Tschaikowski","full_name":"Tschaikowski, Max","first_name":"Max"},{"first_name":"Gerald","last_name":"Teschl","full_name":"Teschl, Gerald"},{"last_name":"Rus","full_name":"Rus, Daniela","first_name":"Daniela"}],"abstract":[{"lang":"eng","text":"Continuous-time neural networks are a class of machine learning systems that can tackle representation learning on spatiotemporal decision-making tasks. These models are typically represented by continuous differential equations. However, their expressive power when they are deployed on computers is bottlenecked by numerical differential equation solvers. This limitation has notably slowed down the scaling and understanding of numerous natural physical phenomena such as the dynamics of nervous systems. Ideally, we would circumvent this bottleneck by solving the given dynamical system in closed form. This is known to be intractable in general. Here, we show that it is possible to closely approximate the interaction between neurons and synapses—the building blocks of natural and artificial neural networks—constructed by liquid time-constant networks efficiently in closed form. To this end, we compute a tightly bounded approximation of the solution of an integral appearing in liquid time-constant dynamics that has had no known closed-form solution so far. This closed-form solution impacts the design of continuous-time and continuous-depth neural models. For instance, since time appears explicitly in closed form, the formulation relaxes the need for complex numerical solvers. Consequently, we obtain models that are between one and five orders of magnitude faster in training and inference compared with differential equation-based counterparts. More importantly, in contrast to ordinary differential equation-based continuous networks, closed-form networks can scale remarkably well compared with other deep learning instances. Lastly, as these models are derived from liquid networks, they show good performance in time-series modelling compared with advanced recurrent neural network models."}],"publication_status":"published","citation":{"chicago":"Hasani, Ramin, Mathias Lechner, Alexander Amini, Lucas Liebenwein, Aaron Ray, Max Tschaikowski, Gerald Teschl, and Daniela Rus. “Closed-Form Continuous-Time Neural Networks.” <i>Nature Machine Intelligence</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1038/s42256-022-00556-7\">https://doi.org/10.1038/s42256-022-00556-7</a>.","apa":"Hasani, R., Lechner, M., Amini, A., Liebenwein, L., Ray, A., Tschaikowski, M., … Rus, D. (2022). Closed-form continuous-time neural networks. <i>Nature Machine Intelligence</i>. Springer Nature. <a href=\"https://doi.org/10.1038/s42256-022-00556-7\">https://doi.org/10.1038/s42256-022-00556-7</a>","ieee":"R. Hasani <i>et al.</i>, “Closed-form continuous-time neural networks,” <i>Nature Machine Intelligence</i>, vol. 4, no. 11. Springer Nature, pp. 992–1003, 2022.","ista":"Hasani R, Lechner M, Amini A, Liebenwein L, Ray A, Tschaikowski M, Teschl G, Rus D. 2022. Closed-form continuous-time neural networks. Nature Machine Intelligence. 4(11), 992–1003.","short":"R. Hasani, M. Lechner, A. Amini, L. Liebenwein, A. Ray, M. Tschaikowski, G. Teschl, D. Rus, Nature Machine Intelligence 4 (2022) 992–1003.","ama":"Hasani R, Lechner M, Amini A, et al. Closed-form continuous-time neural networks. <i>Nature Machine Intelligence</i>. 2022;4(11):992-1003. doi:<a href=\"https://doi.org/10.1038/s42256-022-00556-7\">10.1038/s42256-022-00556-7</a>","mla":"Hasani, Ramin, et al. “Closed-Form Continuous-Time Neural Networks.” <i>Nature Machine Intelligence</i>, vol. 4, no. 11, Springer Nature, 2022, pp. 992–1003, doi:<a href=\"https://doi.org/10.1038/s42256-022-00556-7\">10.1038/s42256-022-00556-7</a>."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","acknowledgement":"This research was supported in part by the AI2050 program at Schmidt Futures (grant G-22-63172), the Boeing Company, and the United States Air Force Research Laboratory and the United States Air Force Artificial Intelligence Accelerator and was accomplished under cooperative agreement number FA8750-19-2-1000. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the United States Air Force or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes, notwithstanding any copyright notation herein. This work was further supported by The Boeing Company and Office of Naval Research grant N00014-18-1-2830. M.T. is supported by the Poul Due Jensen Foundation, grant 883901. M.L. was supported in part by the Austrian Science Fund under grant Z211-N23 (Wittgenstein Award). A.A. was supported by the National Science Foundation Graduate Research Fellowship Program. We thank T.-H. Wang, P. Kao, M. Chahine, W. Xiao, X. Li, L. Yin and Y. Ben for useful suggestions and for testing of CfC models to confirm the results across other domains.","quality_controlled":"1","project":[{"grant_number":"Z211","name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"oa_version":"Published Version","_id":"12147","publication_identifier":{"issn":["2522-5839"]},"oa":1,"volume":4,"date_updated":"2023-08-04T09:00:10Z","article_processing_charge":"No","arxiv":1,"language":[{"iso":"eng"}],"publisher":"Springer Nature","scopus_import":"1","article_type":"original","date_published":"2022-11-15T00:00:00Z","month":"11","file":[{"success":1,"file_id":"12355","creator":"dernst","content_type":"application/pdf","relation":"main_file","date_created":"2023-01-24T09:49:44Z","checksum":"b4789122ce04bfb4ac042390f59aaa8b","file_name":"2022_NatureMachineIntelligence_Hasani.pdf","file_size":3259553,"date_updated":"2023-01-24T09:49:44Z","access_level":"open_access"}],"date_created":"2023-01-12T12:07:21Z","department":[{"_id":"ToHe"}],"has_accepted_license":"1","status":"public","intvolume":"         4","type":"journal_article","day":"15","file_date_updated":"2023-01-24T09:49:44Z","page":"992-1003","issue":"11","publication":"Nature Machine Intelligence"},{"ec_funded":1,"doi":"10.1145/3447384","year":"2021","title":"Input-dynamic distributed algorithms for communication networks","external_id":{"arxiv":["2005.07637"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2005.07637"}],"related_material":{"record":[{"status":"public","id":"10854","relation":"shorter_version"}]},"publication_status":"published","citation":{"ista":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. 2021. Input-dynamic distributed algorithms for communication networks. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 5(1), 1–33.","short":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, S. Schmid, Proceedings of the ACM on Measurement and Analysis of Computing Systems 5 (2021) 1–33.","mla":"Foerster, Klaus-Tycho, et al. “Input-Dynamic Distributed Algorithms for Communication Networks.” <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>, vol. 5, no. 1, Association for Computing Machinery, 2021, pp. 1–33, doi:<a href=\"https://doi.org/10.1145/3447384\">10.1145/3447384</a>.","ama":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. Input-dynamic distributed algorithms for communication networks. <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>. 2021;5(1):1-33. doi:<a href=\"https://doi.org/10.1145/3447384\">10.1145/3447384</a>","chicago":"Foerster, Klaus-Tycho, Janne Korhonen, Ami Paz, Joel Rybicki, and Stefan Schmid. “Input-Dynamic Distributed Algorithms for Communication Networks.” <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3447384\">https://doi.org/10.1145/3447384</a>.","ieee":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, and S. Schmid, “Input-dynamic distributed algorithms for communication networks,” <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>, vol. 5, no. 1. Association for Computing Machinery, pp. 1–33, 2021.","apa":"Foerster, K.-T., Korhonen, J., Paz, A., Rybicki, J., &#38; Schmid, S. (2021). Input-dynamic distributed algorithms for communication networks. <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3447384\">https://doi.org/10.1145/3447384</a>"},"author":[{"first_name":"Klaus-Tycho","last_name":"Foerster","full_name":"Foerster, Klaus-Tycho"},{"id":"C5402D42-15BC-11E9-A202-CA2BE6697425","full_name":"Korhonen, Janne","last_name":"Korhonen","first_name":"Janne"},{"first_name":"Ami","last_name":"Paz","full_name":"Paz, Ami"},{"last_name":"Rybicki","full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Schmid, Stefan","last_name":"Schmid","first_name":"Stefan"}],"keyword":["Computer Networks and Communications","Hardware and Architecture","Safety","Risk","Reliability and Quality","Computer Science (miscellaneous)"],"abstract":[{"text":"Consider a distributed task where the communication network is fixed but the local inputs given to the nodes of the distributed system may change over time. In this work, we explore the following question: if some of the local inputs change, can an existing solution be updated efficiently, in a dynamic and distributed manner? To address this question, we define the batch dynamic \\congest model in which we are given a bandwidth-limited communication network and a dynamic edge labelling defines the problem input. The task is to maintain a solution to a graph problem on the labeled graph under batch changes. We investigate, when a batch of α edge label changes arrive, \\beginitemize \\item how much time as a function of α we need to update an existing solution, and \\item how much information the nodes have to keep in local memory between batches in order to update the solution quickly. \\enditemize Our work lays the foundations for the theory of input-dynamic distributed network algorithms. We give a general picture of the complexity landscape in this model, design both universal algorithms and algorithms for concrete problems, and present a general framework for lower bounds. In particular, we derive non-trivial upper bounds for two selected, contrasting problems: maintaining a minimum spanning tree and detecting cliques.","lang":"eng"}],"oa":1,"volume":5,"date_updated":"2023-09-26T10:40:55Z","article_processing_charge":"No","arxiv":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"We thank Jukka Suomela for discussions. We also thank our shepherd Mohammad Hajiesmaili\r\nand the reviewers for their time and suggestions on how to improve the paper. This project\r\nhas received funding from the European Research Council (ERC) under the European Union’s\r\nHorizon 2020 research and innovation programme (grant agreement No 805223 ScaleML), from the European Union’s Horizon 2020 research and innovation programme under the Marie\r\nSk lodowska–Curie grant agreement No. 840605, from the Vienna Science and Technology Fund (WWTF) project WHATIF, ICT19-045, 2020-2024, and from the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N.","project":[{"grant_number":"840605","name":"Coordination in constrained and natural distributed systems","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"grant_number":"805223","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}],"oa_version":"Preprint","quality_controlled":"1","_id":"10855","publication_identifier":{"issn":["2476-1249"]},"date_published":"2021-03-01T00:00:00Z","article_type":"original","month":"03","language":[{"iso":"eng"}],"publisher":"Association for Computing Machinery","scopus_import":"1","department":[{"_id":"DaAl"}],"date_created":"2022-03-18T09:10:27Z","type":"journal_article","day":"01","status":"public","intvolume":"         5","page":"1-33","issue":"1","publication":"Proceedings of the ACM on Measurement and Analysis of Computing Systems"},{"title":"New inertial projection methods for solving multivalued variational inequality problems beyond monotonicity","external_id":{"isi":["000625002100001"]},"ec_funded":1,"doi":"10.1007/s11067-021-09517-w","year":"2021","ddc":["510"],"isi":1,"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"author":[{"full_name":"Izuchukwu, Chinedu","last_name":"Izuchukwu","first_name":"Chinedu"},{"first_name":"Yekini","full_name":"Shehu, Yekini","last_name":"Shehu","orcid":"0000-0001-9224-7139","id":"3FC7CB58-F248-11E8-B48F-1D18A9856A87"}],"keyword":["Computer Networks and Communications","Software","Artificial Intelligence"],"abstract":[{"text":"In this paper, we present two new inertial projection-type methods for solving multivalued variational inequality problems in finite-dimensional spaces. We establish the convergence of the sequence generated by these methods when the multivalued mapping associated with the problem is only required to be locally bounded without any monotonicity assumption. Furthermore, the inertial techniques that we employ in this paper are quite different from the ones used in most papers. Moreover, based on the weaker assumptions on the inertial factor in our methods, we derive several special cases of our methods. Finally, we present some experimental results to illustrate the profits that we gain by introducing the inertial extrapolation steps.","lang":"eng"}],"publication_status":"published","citation":{"chicago":"Izuchukwu, Chinedu, and Yekini Shehu. “New Inertial Projection Methods for Solving Multivalued Variational Inequality Problems beyond Monotonicity.” <i>Networks and Spatial Economics</i>. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/s11067-021-09517-w\">https://doi.org/10.1007/s11067-021-09517-w</a>.","apa":"Izuchukwu, C., &#38; Shehu, Y. (2021). New inertial projection methods for solving multivalued variational inequality problems beyond monotonicity. <i>Networks and Spatial Economics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s11067-021-09517-w\">https://doi.org/10.1007/s11067-021-09517-w</a>","ieee":"C. Izuchukwu and Y. Shehu, “New inertial projection methods for solving multivalued variational inequality problems beyond monotonicity,” <i>Networks and Spatial Economics</i>, vol. 21, no. 2. Springer Nature, pp. 291–323, 2021.","short":"C. Izuchukwu, Y. Shehu, Networks and Spatial Economics 21 (2021) 291–323.","ista":"Izuchukwu C, Shehu Y. 2021. New inertial projection methods for solving multivalued variational inequality problems beyond monotonicity. Networks and Spatial Economics. 21(2), 291–323.","ama":"Izuchukwu C, Shehu Y. New inertial projection methods for solving multivalued variational inequality problems beyond monotonicity. <i>Networks and Spatial Economics</i>. 2021;21(2):291-323. doi:<a href=\"https://doi.org/10.1007/s11067-021-09517-w\">10.1007/s11067-021-09517-w</a>","mla":"Izuchukwu, Chinedu, and Yekini Shehu. “New Inertial Projection Methods for Solving Multivalued Variational Inequality Problems beyond Monotonicity.” <i>Networks and Spatial Economics</i>, vol. 21, no. 2, Springer Nature, 2021, pp. 291–323, doi:<a href=\"https://doi.org/10.1007/s11067-021-09517-w\">10.1007/s11067-021-09517-w</a>."},"acknowledgement":"The authors sincerely thank the Editor-in-Chief and anonymous referees for their careful reading, constructive comments and fruitful suggestions that help improve the manuscript. The research of the first author is supported by the National Research Foundation (NRF) South Africa (S& F-DSI/NRF Free Standing Postdoctoral Fellowship; Grant Number: 120784). The first author also acknowledges the financial support from DSI/NRF, South Africa Center of Excellence in Mathematical and Statistical Sciences (CoE-MaSS) Postdoctoral Fellowship. The second author has received funding from the European Research Council (ERC) under the European Union’s Seventh Framework Program (FP7 - 2007-2013) (Grant agreement No. 616160). Open Access funding provided by Institute of Science and Technology (IST Austria).","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa_version":"Published Version","project":[{"call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160"},{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"quality_controlled":"1","_id":"9234","publication_identifier":{"issn":["1566-113X"],"eissn":["1572-9427"]},"date_updated":"2023-09-05T15:32:32Z","volume":21,"oa":1,"article_processing_charge":"Yes (via OA deal)","language":[{"iso":"eng"}],"publisher":"Springer Nature","scopus_import":"1","article_type":"original","date_published":"2021-06-01T00:00:00Z","month":"06","file":[{"content_type":"application/pdf","relation":"main_file","file_id":"9884","creator":"kschuh","success":1,"date_updated":"2021-08-11T12:44:16Z","access_level":"open_access","file_name":"2021_NetworksSpatialEconomics_Shehu.pdf","file_size":834964,"date_created":"2021-08-11T12:44:16Z","checksum":"22b4253a2e5da843622a2df713784b4c"}],"date_created":"2021-03-10T12:18:47Z","department":[{"_id":"VlKo"}],"has_accepted_license":"1","status":"public","intvolume":"        21","type":"journal_article","day":"01","file_date_updated":"2021-08-11T12:44:16Z","page":"291-323","issue":"2","publication":"Networks and Spatial Economics"},{"scopus_import":"1","publisher":"Wiley","language":[{"iso":"eng"}],"month":"05","date_published":"2020-05-01T00:00:00Z","article_type":"original","file":[{"relation":"main_file","content_type":"application/pdf","creator":"dernst","file_id":"8796","success":1,"access_level":"open_access","date_updated":"2020-11-23T09:05:13Z","file_size":38969122,"file_name":"2020_poff_revisited.pdf","checksum":"7605f605acd84d0942b48bc7a1c2d72e","date_created":"2020-11-23T09:05:13Z"}],"date_created":"2020-11-17T09:35:10Z","has_accepted_license":"1","department":[{"_id":"ChWo"}],"intvolume":"        39","status":"public","day":"01","type":"journal_article","publication":"Computer Graphics Forum","issue":"2","page":"89-99","file_date_updated":"2020-11-23T09:05:13Z","external_id":{"isi":["000548709600008"]},"title":"A practical method for animating anisotropic elastoplastic materials","year":"2020","doi":"10.1111/cgf.13914","acknowledged_ssus":[{"_id":"ScienComp"}],"ec_funded":1,"ddc":["000"],"isi":1,"abstract":[{"text":"This paper introduces a simple method for simulating highly anisotropic elastoplastic material behaviors like the dissolution of fibrous phenomena (splintering wood, shredding bales of hay) and materials composed of large numbers of irregularly‐shaped bodies (piles of twigs, pencils, or cards). We introduce a simple transformation of the anisotropic problem into an equivalent isotropic one, and we solve this new “fictitious” isotropic problem using an existing simulator based on the material point method. Our approach results in minimal changes to existing simulators, and it allows us to re‐use popular isotropic plasticity models like the Drucker‐Prager yield criterion instead of inventing new anisotropic plasticity models for every phenomenon we wish to simulate.","lang":"eng"}],"author":[{"full_name":"Schreck, Camille","last_name":"Schreck","first_name":"Camille","id":"2B14B676-F248-11E8-B48F-1D18A9856A87"},{"id":"3C61F1D2-F248-11E8-B48F-1D18A9856A87","first_name":"Christopher J","last_name":"Wojtan","full_name":"Wojtan, Christopher J","orcid":"0000-0001-6646-5546"}],"keyword":["Computer Networks and Communications"],"citation":{"mla":"Schreck, Camille, and Chris Wojtan. “A Practical Method for Animating Anisotropic Elastoplastic Materials.” <i>Computer Graphics Forum</i>, vol. 39, no. 2, Wiley, 2020, pp. 89–99, doi:<a href=\"https://doi.org/10.1111/cgf.13914\">10.1111/cgf.13914</a>.","ama":"Schreck C, Wojtan C. A practical method for animating anisotropic elastoplastic materials. <i>Computer Graphics Forum</i>. 2020;39(2):89-99. doi:<a href=\"https://doi.org/10.1111/cgf.13914\">10.1111/cgf.13914</a>","ista":"Schreck C, Wojtan C. 2020. A practical method for animating anisotropic elastoplastic materials. Computer Graphics Forum. 39(2), 89–99.","short":"C. Schreck, C. Wojtan, Computer Graphics Forum 39 (2020) 89–99.","apa":"Schreck, C., &#38; Wojtan, C. (2020). A practical method for animating anisotropic elastoplastic materials. <i>Computer Graphics Forum</i>. Wiley. <a href=\"https://doi.org/10.1111/cgf.13914\">https://doi.org/10.1111/cgf.13914</a>","ieee":"C. Schreck and C. Wojtan, “A practical method for animating anisotropic elastoplastic materials,” <i>Computer Graphics Forum</i>, vol. 39, no. 2. Wiley, pp. 89–99, 2020.","chicago":"Schreck, Camille, and Chris Wojtan. “A Practical Method for Animating Anisotropic Elastoplastic Materials.” <i>Computer Graphics Forum</i>. Wiley, 2020. <a href=\"https://doi.org/10.1111/cgf.13914\">https://doi.org/10.1111/cgf.13914</a>."},"publication_status":"published","publication_identifier":{"issn":["0167-7055"],"eissn":["1467-8659"]},"_id":"8765","quality_controlled":"1","oa_version":"Submitted Version","project":[{"grant_number":"638176","_id":"2533E772-B435-11E9-9278-68D0E5697425","name":"Efficient Simulation of Natural Phenomena at Extremely Large Scales","call_identifier":"H2020"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","acknowledgement":"We wish to thank the anonymous reviewers and the members of the Visual Computing Group at IST Austria for their valuable feedback. This research was supported by the Scientific Service Units (SSU) of IST Austria through resources provided by Scientific Computing. We would also like to thank Joseph Teran and Chenfanfu Jiang for the helpful discussions.\r\nThis project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant agreement No. 638176.","article_processing_charge":"No","oa":1,"date_updated":"2023-09-05T16:00:13Z","volume":39},{"date_updated":"2022-09-12T08:51:57Z","volume":7,"article_processing_charge":"No","_id":"11671","extern":"1","publication_identifier":{"issn":["1559-1131"],"eissn":["1559-114X"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","oa_version":"None","publication_status":"published","citation":{"chicago":"Baykan, Eda, Ingmar Weber, and Monika H Henzinger. “A Comprehensive Study of Techniques for URL-Based Web Page Language Classification.” <i>ACM Transactions on the Web</i>. Association for Computing Machinery, 2013. <a href=\"https://doi.org/10.1145/2435215.2435218\">https://doi.org/10.1145/2435215.2435218</a>.","apa":"Baykan, E., Weber, I., &#38; Henzinger, M. H. (2013). A comprehensive study of techniques for URL-based web page language classification. <i>ACM Transactions on the Web</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2435215.2435218\">https://doi.org/10.1145/2435215.2435218</a>","ieee":"E. Baykan, I. Weber, and M. H. Henzinger, “A comprehensive study of techniques for URL-based web page language classification,” <i>ACM Transactions on the Web</i>, vol. 7, no. 1. Association for Computing Machinery, 2013.","short":"E. Baykan, I. Weber, M.H. Henzinger, ACM Transactions on the Web 7 (2013).","ista":"Baykan E, Weber I, Henzinger MH. 2013. A comprehensive study of techniques for URL-based web page language classification. ACM Transactions on the Web. 7(1), 3.","mla":"Baykan, Eda, et al. “A Comprehensive Study of Techniques for URL-Based Web Page Language Classification.” <i>ACM Transactions on the Web</i>, vol. 7, no. 1, 3, Association for Computing Machinery, 2013, doi:<a href=\"https://doi.org/10.1145/2435215.2435218\">10.1145/2435215.2435218</a>.","ama":"Baykan E, Weber I, Henzinger MH. A comprehensive study of techniques for URL-based web page language classification. <i>ACM Transactions on the Web</i>. 2013;7(1). doi:<a href=\"https://doi.org/10.1145/2435215.2435218\">10.1145/2435215.2435218</a>"},"abstract":[{"text":"Given only the URL of a Web page, can we identify its language? In this article we examine this question. URL-based language classification is useful when the content of the Web page is not available or downloading the content is a waste of bandwidth and time.\r\nWe built URL-based language classifiers for English, German, French, Spanish, and Italian by applying a variety of algorithms and features. As algorithms we used machine learning algorithms which are widely applied for text classification and state-of-art algorithms for language identification of text. As features we used words, various sized n-grams, and custom-made features (our novel feature set). We compared our approaches with two baseline methods, namely classification by country code top-level domains and classification by IP addresses of the hosting Web servers.\r\n\r\nWe trained and tested our classifiers in a 10-fold cross-validation setup on a dataset obtained from the Open Directory Project and from querying a commercial search engine. We obtained the lowest F1-measure for English (94) and the highest F1-measure for German (98) with the best performing classifiers.\r\n\r\nWe also evaluated the performance of our methods: (i) on a set of Web pages written in Adobe Flash and (ii) as part of a language-focused crawler. In the first case, the content of the Web page is hard to extract and in the second page downloading pages of the “wrong” language constitutes a waste of bandwidth. In both settings the best classifiers have a high accuracy with an F1-measure between 95 (for English) and 98 (for Italian) for the Adobe Flash pages and a precision between 90 (for Italian) and 97 (for French) for the language-focused crawler.","lang":"eng"}],"author":[{"first_name":"Eda","last_name":"Baykan","full_name":"Baykan, Eda"},{"first_name":"Ingmar","last_name":"Weber","full_name":"Weber, Ingmar"},{"first_name":"Monika H","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"}],"keyword":["Computer Networks and Communications"],"article_number":"3","year":"2013","doi":"10.1145/2435215.2435218","title":"A comprehensive study of techniques for URL-based web page language classification","issue":"1","publication":"ACM Transactions on the Web","day":"01","type":"journal_article","intvolume":"         7","status":"public","date_created":"2022-07-27T12:50:18Z","month":"03","article_type":"original","date_published":"2013-03-01T00:00:00Z","publisher":"Association for Computing Machinery","scopus_import":"1","language":[{"iso":"eng"}]}]