[{"date_published":"2018-12-01T00:00:00Z","abstract":[{"lang":"eng","text":"This paper studies the problem of distributed stochastic optimization in an adversarial setting where, out of m machines which allegedly compute stochastic gradients every iteration, an α-fraction are Byzantine, and may behave adversarially. Our main result is a variant of stochastic gradient descent (SGD) which finds ε-approximate minimizers of convex functions in T=O~(1/ε²m+α²/ε²) iterations. In contrast, traditional mini-batch SGD needs T=O(1/ε²m) iterations, but cannot tolerate Byzantine failures. Further, we provide a lower bound showing that, up to logarithmic factors, our algorithm is information-theoretically optimal both in terms of sample complexity and time complexity."}],"citation":{"ista":"Alistarh D-A, Allen-Zhu Z, Li J. 2018. Byzantine stochastic gradient descent. Advances in Neural Information Processing Systems. NeurIPS: Conference on Neural Information Processing Systems vol. 2018, 4613–4623.","apa":"Alistarh, D.-A., Allen-Zhu, Z., &#38; Li, J. (2018). Byzantine stochastic gradient descent. In <i>Advances in Neural Information Processing Systems</i> (Vol. 2018, pp. 4613–4623). Montreal, Canada: Neural Information Processing Systems Foundation.","ieee":"D.-A. Alistarh, Z. Allen-Zhu, and J. Li, “Byzantine stochastic gradient descent,” in <i>Advances in Neural Information Processing Systems</i>, Montreal, Canada, 2018, vol. 2018, pp. 4613–4623.","mla":"Alistarh, Dan-Adrian, et al. “Byzantine Stochastic Gradient Descent.” <i>Advances in Neural Information Processing Systems</i>, vol. 2018, Neural Information Processing Systems Foundation, 2018, pp. 4613–23.","short":"D.-A. Alistarh, Z. Allen-Zhu, J. Li, in:, Advances in Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2018, pp. 4613–4623.","chicago":"Alistarh, Dan-Adrian, Zeyuan Allen-Zhu, and Jerry Li. “Byzantine Stochastic Gradient Descent.” In <i>Advances in Neural Information Processing Systems</i>, 2018:4613–23. Neural Information Processing Systems Foundation, 2018.","ama":"Alistarh D-A, Allen-Zhu Z, Li J. Byzantine stochastic gradient descent. In: <i>Advances in Neural Information Processing Systems</i>. Vol 2018. Neural Information Processing Systems Foundation; 2018:4613-4623."},"conference":{"end_date":"2018-12-08","start_date":"2018-12-02","name":"NeurIPS: Conference on Neural Information Processing Systems","location":"Montreal, Canada"},"intvolume":"      2018","date_updated":"2023-09-19T15:12:45Z","status":"public","author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh","first_name":"Dan-Adrian"},{"last_name":"Allen-Zhu","first_name":"Zeyuan","full_name":"Allen-Zhu, Zeyuan"},{"full_name":"Li, Jerry","last_name":"Li","first_name":"Jerry"}],"publication":"Advances in Neural Information Processing Systems","month":"12","volume":2018,"page":"4613-4623","language":[{"iso":"eng"}],"_id":"6558","oa_version":"Published Version","scopus_import":"1","quality_controlled":"1","isi":1,"date_created":"2019-06-13T08:22:37Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1803.08917"}],"department":[{"_id":"DaAl"}],"year":"2018","publication_status":"published","publisher":"Neural Information Processing Systems Foundation","day":"01","external_id":{"arxiv":["1803.08917"],"isi":["000461823304061"]},"oa":1,"type":"conference","article_processing_charge":"No","title":"Byzantine stochastic gradient descent","arxiv":1,"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"title":"The convergence of sparsified gradient methods","article_processing_charge":"No","type":"conference","oa":1,"day":"01","external_id":{"isi":["000461852000047"],"arxiv":["1809.10505"]},"publisher":"Neural Information Processing Systems Foundation","year":"2018","publication_status":"published","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1809.10505"}],"department":[{"_id":"DaAl"},{"_id":"ChLa"}],"date_created":"2019-06-27T09:32:55Z","isi":1,"project":[{"_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program","call_identifier":"H2020","grant_number":"665385"}],"quality_controlled":"1","scopus_import":"1","oa_version":"Preprint","_id":"6589","language":[{"iso":"eng"}],"page":"5973-5983","ec_funded":1,"volume":"Volume 2018","month":"12","publication":"Advances in Neural Information Processing Systems 31","author":[{"full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X"},{"full_name":"Hoefler, Torsten","last_name":"Hoefler","first_name":"Torsten"},{"full_name":"Johansson, Mikael","first_name":"Mikael","last_name":"Johansson"},{"first_name":"Nikola H","last_name":"Konstantinov","id":"4B9D76E4-F248-11E8-B48F-1D18A9856A87","full_name":"Konstantinov, Nikola H"},{"full_name":"Khirirat, Sarit","last_name":"Khirirat","first_name":"Sarit"},{"last_name":"Renggli","first_name":"Cedric","full_name":"Renggli, Cedric"}],"status":"public","date_updated":"2025-06-26T12:23:06Z","corr_author":"1","conference":{"name":"NeurIPS: Conference on Neural Information Processing Systems","location":"Montreal, Canada","start_date":"2018-12-02","end_date":"2018-12-08"},"abstract":[{"lang":"eng","text":"Distributed training of massive machine learning models, in particular deep neural networks, via Stochastic Gradient Descent (SGD) is becoming commonplace. Several families of communication-reduction methods, such as quantization, large-batch methods, and gradient sparsification, have been proposed. To date, gradient sparsification methods--where each node sorts gradients by magnitude, and only communicates a subset of the components, accumulating the rest locally--are known to yield some of the largest practical gains. Such methods can reduce the amount of communication per step by up to \\emph{three orders of magnitude}, while preserving model accuracy. Yet, this family of methods currently has no theoretical justification. This is the question we address in this paper. We prove that, under analytic assumptions, sparsifying gradients by magnitude with local error correction provides convergence guarantees, for both convex and non-convex smooth objectives, for data-parallel SGD. The main insight is that sparsification methods implicitly maintain bounds on the maximum impact of stale updates, thanks to selection by magnitude. Our analysis and empirical validation also reveal that these methods do require analytical conditions to converge well, justifying existing heuristics."}],"citation":{"mla":"Alistarh, Dan-Adrian, et al. “The Convergence of Sparsified Gradient Methods.” <i>Advances in Neural Information Processing Systems 31</i>, vol. Volume 2018, Neural Information Processing Systems Foundation, 2018, pp. 5973–83.","ieee":"D.-A. Alistarh, T. Hoefler, M. Johansson, N. H. Konstantinov, S. Khirirat, and C. Renggli, “The convergence of sparsified gradient methods,” in <i>Advances in Neural Information Processing Systems 31</i>, Montreal, Canada, 2018, vol. Volume 2018, pp. 5973–5983.","short":"D.-A. Alistarh, T. Hoefler, M. Johansson, N.H. Konstantinov, S. Khirirat, C. Renggli, in:, Advances in Neural Information Processing Systems 31, Neural Information Processing Systems Foundation, 2018, pp. 5973–5983.","apa":"Alistarh, D.-A., Hoefler, T., Johansson, M., Konstantinov, N. H., Khirirat, S., &#38; Renggli, C. (2018). The convergence of sparsified gradient methods. In <i>Advances in Neural Information Processing Systems 31</i> (Vol. Volume 2018, pp. 5973–5983). Montreal, Canada: Neural Information Processing Systems Foundation.","ama":"Alistarh D-A, Hoefler T, Johansson M, Konstantinov NH, Khirirat S, Renggli C. The convergence of sparsified gradient methods. In: <i>Advances in Neural Information Processing Systems 31</i>. Vol Volume 2018. Neural Information Processing Systems Foundation; 2018:5973-5983.","chicago":"Alistarh, Dan-Adrian, Torsten Hoefler, Mikael Johansson, Nikola H Konstantinov, Sarit Khirirat, and Cedric Renggli. “The Convergence of Sparsified Gradient Methods.” In <i>Advances in Neural Information Processing Systems 31</i>, Volume 2018:5973–83. Neural Information Processing Systems Foundation, 2018.","ista":"Alistarh D-A, Hoefler T, Johansson M, Konstantinov NH, Khirirat S, Renggli C. 2018. The convergence of sparsified gradient methods. Advances in Neural Information Processing Systems 31. NeurIPS: Conference on Neural Information Processing Systems vol. Volume 2018, 5973–5983."},"date_published":"2018-12-01T00:00:00Z"},{"year":"2018","publication_status":"published","publisher":"Springer","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1605.08767"}],"department":[{"_id":"LaEr"}],"type":"journal_article","day":"14","external_id":{"arxiv":["1605.08767"],"isi":["000432129600012"]},"oa":1,"article_processing_charge":"No","title":"Local law and Tracy–Widom limit for sparse random matrices","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","arxiv":1,"language":[{"iso":"eng"}],"doi":"10.1007/s00440-017-0787-8","_id":"690","scopus_import":"1","oa_version":"Preprint","project":[{"name":"Random matrices, universality and disordered quantum systems","_id":"258DCDE6-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"338804"}],"quality_controlled":"1","date_created":"2018-12-11T11:47:56Z","isi":1,"status":"public","author":[{"full_name":"Lee, Jii","first_name":"Jii","last_name":"Lee"},{"full_name":"Schnelli, Kevin","id":"434AD0AE-F248-11E8-B48F-1D18A9856A87","first_name":"Kevin","orcid":"0000-0003-0954-3231","last_name":"Schnelli"}],"issue":"1-2","publication":"Probability Theory and Related Fields","volume":171,"ec_funded":1,"article_number":"543-616","month":"06","date_published":"2018-06-14T00:00:00Z","citation":{"mla":"Lee, Jii, and Kevin Schnelli. “Local Law and Tracy–Widom Limit for Sparse Random Matrices.” <i>Probability Theory and Related Fields</i>, vol. 171, no. 1–2, 543–616, Springer, 2018, doi:<a href=\"https://doi.org/10.1007/s00440-017-0787-8\">10.1007/s00440-017-0787-8</a>.","ieee":"J. Lee and K. Schnelli, “Local law and Tracy–Widom limit for sparse random matrices,” <i>Probability Theory and Related Fields</i>, vol. 171, no. 1–2. Springer, 2018.","short":"J. Lee, K. Schnelli, Probability Theory and Related Fields 171 (2018).","apa":"Lee, J., &#38; Schnelli, K. (2018). Local law and Tracy–Widom limit for sparse random matrices. <i>Probability Theory and Related Fields</i>. Springer. <a href=\"https://doi.org/10.1007/s00440-017-0787-8\">https://doi.org/10.1007/s00440-017-0787-8</a>","ama":"Lee J, Schnelli K. Local law and Tracy–Widom limit for sparse random matrices. <i>Probability Theory and Related Fields</i>. 2018;171(1-2). doi:<a href=\"https://doi.org/10.1007/s00440-017-0787-8\">10.1007/s00440-017-0787-8</a>","chicago":"Lee, Jii, and Kevin Schnelli. “Local Law and Tracy–Widom Limit for Sparse Random Matrices.” <i>Probability Theory and Related Fields</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s00440-017-0787-8\">https://doi.org/10.1007/s00440-017-0787-8</a>.","ista":"Lee J, Schnelli K. 2018. Local law and Tracy–Widom limit for sparse random matrices. Probability Theory and Related Fields. 171(1–2), 543–616."},"abstract":[{"lang":"eng","text":"We consider spectral properties and the edge universality of sparse random matrices, the class of random matrices that includes the adjacency matrices of the Erdős–Rényi graph model G(N, p). We prove a local law for the eigenvalue density up to the spectral edges. Under a suitable condition on the sparsity, we also prove that the rescaled extremal eigenvalues exhibit GOE Tracy–Widom fluctuations if a deterministic shift of the spectral edge due to the sparsity is included. For the adjacency matrix of the Erdős–Rényi graph this establishes the Tracy–Widom fluctuations of the second largest eigenvalue when p is much larger than N−2/3 with a deterministic shift of order (Np)−1."}],"intvolume":"       171","publist_id":"7017","date_updated":"2025-09-10T14:00:58Z"},{"issue":"1","publication":"Journal of Medical Genetics","author":[{"full_name":"Marin Valencia, Isaac","last_name":"Marin Valencia","first_name":"Isaac"},{"first_name":"Gaia","last_name":"Novarino","orcid":"0000-0002-7673-7178","full_name":"Novarino, Gaia","id":"3E57A680-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Johansen","first_name":"Anide","full_name":"Johansen, Anide"},{"full_name":"Rosti, Başak","first_name":"Başak","last_name":"Rosti"},{"full_name":"Issa, Mahmoud","last_name":"Issa","first_name":"Mahmoud"},{"last_name":"Musaev","first_name":"Damir","full_name":"Musaev, Damir"},{"full_name":"Bhat, Gifty","first_name":"Gifty","last_name":"Bhat"},{"last_name":"Scott","first_name":"Eric","full_name":"Scott, Eric"},{"first_name":"Jennifer","last_name":"Silhavy","full_name":"Silhavy, Jennifer"},{"first_name":"Valentina","last_name":"Stanley","full_name":"Stanley, Valentina"},{"last_name":"Rosti","first_name":"Rasim","full_name":"Rosti, Rasim"},{"full_name":"Gleeson, Jeremy","first_name":"Jeremy","last_name":"Gleeson"},{"full_name":"Imam, Farhad","first_name":"Farhad","last_name":"Imam"},{"full_name":"Zaki, Maha","last_name":"Zaki","first_name":"Maha"},{"last_name":"Gleeson","first_name":"Joseph","full_name":"Gleeson, Joseph"}],"status":"public","page":"48 - 54","month":"01","volume":55,"citation":{"ista":"Marin Valencia I, Novarino G, Johansen A, Rosti B, Issa M, Musaev D, Bhat G, Scott E, Silhavy J, Stanley V, Rosti R, Gleeson J, Imam F, Zaki M, Gleeson J. 2018. A homozygous founder mutation in TRAPPC6B associates with a neurodevelopmental disorder characterised by microcephaly epilepsy and autistic features. Journal of Medical Genetics. 55(1), 48–54.","apa":"Marin Valencia, I., Novarino, G., Johansen, A., Rosti, B., Issa, M., Musaev, D., … Gleeson, J. (2018). A homozygous founder mutation in TRAPPC6B associates with a neurodevelopmental disorder characterised by microcephaly epilepsy and autistic features. <i>Journal of Medical Genetics</i>. BMJ Publishing Group. <a href=\"https://doi.org/10.1136/jmedgenet-2017-104627\">https://doi.org/10.1136/jmedgenet-2017-104627</a>","short":"I. Marin Valencia, G. Novarino, A. Johansen, B. Rosti, M. Issa, D. Musaev, G. Bhat, E. Scott, J. Silhavy, V. Stanley, R. Rosti, J. Gleeson, F. Imam, M. Zaki, J. Gleeson, Journal of Medical Genetics 55 (2018) 48–54.","ieee":"I. Marin Valencia <i>et al.</i>, “A homozygous founder mutation in TRAPPC6B associates with a neurodevelopmental disorder characterised by microcephaly epilepsy and autistic features,” <i>Journal of Medical Genetics</i>, vol. 55, no. 1. BMJ Publishing Group, pp. 48–54, 2018.","mla":"Marin Valencia, Isaac, et al. “A Homozygous Founder Mutation in TRAPPC6B Associates with a Neurodevelopmental Disorder Characterised by Microcephaly Epilepsy and Autistic Features.” <i>Journal of Medical Genetics</i>, vol. 55, no. 1, BMJ Publishing Group, 2018, pp. 48–54, doi:<a href=\"https://doi.org/10.1136/jmedgenet-2017-104627\">10.1136/jmedgenet-2017-104627</a>.","chicago":"Marin Valencia, Isaac, Gaia Novarino, Anide Johansen, Başak Rosti, Mahmoud Issa, Damir Musaev, Gifty Bhat, et al. “A Homozygous Founder Mutation in TRAPPC6B Associates with a Neurodevelopmental Disorder Characterised by Microcephaly Epilepsy and Autistic Features.” <i>Journal of Medical Genetics</i>. BMJ Publishing Group, 2018. <a href=\"https://doi.org/10.1136/jmedgenet-2017-104627\">https://doi.org/10.1136/jmedgenet-2017-104627</a>.","ama":"Marin Valencia I, Novarino G, Johansen A, et al. A homozygous founder mutation in TRAPPC6B associates with a neurodevelopmental disorder characterised by microcephaly epilepsy and autistic features. <i>Journal of Medical Genetics</i>. 2018;55(1):48-54. doi:<a href=\"https://doi.org/10.1136/jmedgenet-2017-104627\">10.1136/jmedgenet-2017-104627</a>"},"abstract":[{"lang":"eng","text":"Background: Transport protein particle (TRAPP) is a multisubunit complex that regulates membrane trafficking through the Golgi apparatus. The clinical phenotype associated with mutations in various TRAPP subunits has allowed elucidation of their functions in specific tissues. The role of some subunits in human disease, however, has not been fully established, and their functions remain uncertain.\r\n\r\nObjective: We aimed to expand the range of neurodevelopmental disorders associated with mutations in TRAPP subunits by exome sequencing of consanguineous families.\r\n\r\nMethods: Linkage and homozygosity mapping and candidate gene analysis were used to identify homozygous mutations in families. Patient fibroblasts were used to study splicing defect and zebrafish to model the disease.\r\n\r\nResults: We identified six individuals from three unrelated families with a founder homozygous splice mutation in TRAPPC6B, encoding a core subunit of the complex TRAPP I. Patients manifested a neurodevelopmental disorder characterised by microcephaly, epilepsy and autistic features, and showed splicing defect. Zebrafish trappc6b morphants replicated the human phenotype, displaying decreased head size and neuronal hyperexcitability, leading to a lower seizure threshold.\r\n\r\nConclusion: This study provides clinical and functional evidence of the role of TRAPPC6B in brain development and function."}],"date_published":"2018-01-01T00:00:00Z","date_updated":"2025-04-15T07:50:28Z","publist_id":"7016","intvolume":"        55","oa":1,"day":"01","pmid":1,"external_id":{"isi":["000418199800007"],"pmid":["28626029"]},"type":"journal_article","main_file_link":[{"url":"https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6056005/","open_access":"1"}],"department":[{"_id":"GaNo"}],"publisher":"BMJ Publishing Group","year":"2018","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["0022-2593"]},"title":"A homozygous founder mutation in TRAPPC6B associates with a neurodevelopmental disorder characterised by microcephaly epilepsy and autistic features","article_processing_charge":"No","oa_version":"Submitted Version","scopus_import":"1","_id":"691","doi":"10.1136/jmedgenet-2017-104627","language":[{"iso":"eng"}],"article_type":"original","isi":1,"date_created":"2018-12-11T11:47:57Z","quality_controlled":"1","project":[{"_id":"254BA948-B435-11E9-9278-68D0E5697425","name":"Probing development and reversibility of autism spectrum disorders","grant_number":"401299"}]},{"scopus_import":"1","oa_version":"Published Version","_id":"692","doi":"10.1007/s10711-017-0265-6","file_date_updated":"2020-07-14T12:47:44Z","language":[{"iso":"eng"}],"article_type":"original","isi":1,"date_created":"2018-12-11T11:47:57Z","quality_controlled":"1","project":[{"grant_number":"291734","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","name":"International IST Postdoc Fellowship Programme"}],"oa":1,"external_id":{"isi":["000431418800004"]},"day":"01","type":"journal_article","department":[{"_id":"HeEd"}],"publisher":"Springer","publication_status":"published","year":"2018","license":"https://creativecommons.org/licenses/by/4.0/","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","title":"3-Webs generated by confocal conics and circles","article_processing_charge":"Yes (via OA deal)","abstract":[{"lang":"eng","text":"We consider families of confocal conics and two pencils of Apollonian circles having the same foci. We will show that these families of curves generate trivial 3-webs and find the exact formulas describing them."}],"citation":{"chicago":"Akopyan, Arseniy. “3-Webs Generated by Confocal Conics and Circles.” <i>Geometriae Dedicata</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s10711-017-0265-6\">https://doi.org/10.1007/s10711-017-0265-6</a>.","ama":"Akopyan A. 3-Webs generated by confocal conics and circles. <i>Geometriae Dedicata</i>. 2018;194(1):55-64. doi:<a href=\"https://doi.org/10.1007/s10711-017-0265-6\">10.1007/s10711-017-0265-6</a>","apa":"Akopyan, A. (2018). 3-Webs generated by confocal conics and circles. <i>Geometriae Dedicata</i>. Springer. <a href=\"https://doi.org/10.1007/s10711-017-0265-6\">https://doi.org/10.1007/s10711-017-0265-6</a>","ieee":"A. Akopyan, “3-Webs generated by confocal conics and circles,” <i>Geometriae Dedicata</i>, vol. 194, no. 1. Springer, pp. 55–64, 2018.","short":"A. Akopyan, Geometriae Dedicata 194 (2018) 55–64.","mla":"Akopyan, Arseniy. “3-Webs Generated by Confocal Conics and Circles.” <i>Geometriae Dedicata</i>, vol. 194, no. 1, Springer, 2018, pp. 55–64, doi:<a href=\"https://doi.org/10.1007/s10711-017-0265-6\">10.1007/s10711-017-0265-6</a>.","ista":"Akopyan A. 2018. 3-Webs generated by confocal conics and circles. Geometriae Dedicata. 194(1), 55–64."},"has_accepted_license":"1","corr_author":"1","date_published":"2018-06-01T00:00:00Z","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_updated":"2025-04-15T06:50:29Z","publist_id":"7014","intvolume":"       194","publication":"Geometriae Dedicata","issue":"1","author":[{"id":"430D2C90-F248-11E8-B48F-1D18A9856A87","full_name":"Akopyan, Arseniy","first_name":"Arseniy","orcid":"0000-0002-2548-617X","last_name":"Akopyan"}],"status":"public","file":[{"date_updated":"2020-07-14T12:47:44Z","creator":"kschuh","date_created":"2020-01-03T11:35:08Z","access_level":"open_access","relation":"main_file","checksum":"1febcfc1266486053a069e3425ea3713","file_name":"2018_Springer_Akopyan.pdf","file_id":"7222","file_size":1140860,"content_type":"application/pdf"}],"page":"55 - 64","month":"06","ddc":["510"],"ec_funded":1,"volume":194},{"date_created":"2018-12-11T11:44:07Z","isi":1,"project":[{"grant_number":"243071","name":"Social Vaccination in Ant Colonies: from Individual Mechanisms to Society Effects","_id":"25DC711C-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"quality_controlled":"1","doi":"10.1126/science.aat4793","scopus_import":"1","oa_version":"Published Version","_id":"7","article_type":"original","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["1095-9203"]},"title":"Social network plasticity decreases disease transmission in a eusocial insect","article_processing_charge":"No","type":"journal_article","oa":1,"day":"23","external_id":{"isi":["000451124500041"]},"publisher":"AAAS","year":"2018","publication_status":"published","department":[{"_id":"SyCr"}],"main_file_link":[{"open_access":"1","url":"https://serval.unil.ch/resource/serval:BIB_E9228C205467.P001/REF.pdf"}],"publist_id":"8049","date_updated":"2025-04-15T08:20:52Z","intvolume":"       362","citation":{"ama":"Stroeymeyt N, Grasse AV, Crespi A, Mersch D, Cremer S, Keller L. Social network plasticity decreases disease transmission in a eusocial insect. <i>Science</i>. 2018;362(6417):941-945. doi:<a href=\"https://doi.org/10.1126/science.aat4793\">10.1126/science.aat4793</a>","chicago":"Stroeymeyt, Nathalie, Anna V Grasse, Alessandro Crespi, Danielle Mersch, Sylvia Cremer, and Laurent Keller. “Social Network Plasticity Decreases Disease Transmission in a Eusocial Insect.” <i>Science</i>. AAAS, 2018. <a href=\"https://doi.org/10.1126/science.aat4793\">https://doi.org/10.1126/science.aat4793</a>.","short":"N. Stroeymeyt, A.V. Grasse, A. Crespi, D. Mersch, S. Cremer, L. Keller, Science 362 (2018) 941–945.","mla":"Stroeymeyt, Nathalie, et al. “Social Network Plasticity Decreases Disease Transmission in a Eusocial Insect.” <i>Science</i>, vol. 362, no. 6417, AAAS, 2018, pp. 941–45, doi:<a href=\"https://doi.org/10.1126/science.aat4793\">10.1126/science.aat4793</a>.","ieee":"N. Stroeymeyt, A. V. Grasse, A. Crespi, D. Mersch, S. Cremer, and L. Keller, “Social network plasticity decreases disease transmission in a eusocial insect,” <i>Science</i>, vol. 362, no. 6417. AAAS, pp. 941–945, 2018.","apa":"Stroeymeyt, N., Grasse, A. V., Crespi, A., Mersch, D., Cremer, S., &#38; Keller, L. (2018). Social network plasticity decreases disease transmission in a eusocial insect. <i>Science</i>. AAAS. <a href=\"https://doi.org/10.1126/science.aat4793\">https://doi.org/10.1126/science.aat4793</a>","ista":"Stroeymeyt N, Grasse AV, Crespi A, Mersch D, Cremer S, Keller L. 2018. Social network plasticity decreases disease transmission in a eusocial insect. Science. 362(6417), 941–945."},"abstract":[{"lang":"eng","text":"Animal social networks are shaped by multiple selection pressures, including the need to ensure efficient communication and functioning while simultaneously limiting disease transmission. Social animals could potentially further reduce epidemic risk by altering their social networks in the presence of pathogens, yet there is currently no evidence for such pathogen-triggered responses. We tested this hypothesis experimentally in the ant Lasius niger using a combination of automated tracking, controlled pathogen exposure, transmission quantification, and temporally explicit simulations. Pathogen exposure induced behavioral changes in both exposed ants and their nestmates, which helped contain the disease by reinforcing key transmission-inhibitory properties of the colony's contact network. This suggests that social network plasticity in response to pathogens is an effective strategy for mitigating the effects of disease in social groups."}],"related_material":{"link":[{"description":"News on IST Homepage","relation":"press_release","url":"https://ist.ac.at/en/news/for-ants-unity-is-strength-and-health/"}],"record":[{"id":"13055","relation":"research_data","status":"public"}]},"date_published":"2018-11-23T00:00:00Z","page":"941 - 945","ec_funded":1,"volume":362,"acknowledgement":"This project was funded by two European Research Council Advanced Grants (Social Life, 249375, and resiliANT, 741491) and two Swiss National Science Foundation grants (CR32I3_141063 and 310030_156732) to L.K. and a European Research Council Starting Grant (SocialVaccines, 243071) to S.C.","month":"11","issue":"6417","publication":"Science","author":[{"full_name":"Stroeymeyt, Nathalie","first_name":"Nathalie","last_name":"Stroeymeyt"},{"id":"406F989C-F248-11E8-B48F-1D18A9856A87","full_name":"Grasse, Anna V","first_name":"Anna V","last_name":"Grasse"},{"last_name":"Crespi","first_name":"Alessandro","full_name":"Crespi, Alessandro"},{"first_name":"Danielle","last_name":"Mersch","full_name":"Mersch, Danielle"},{"full_name":"Cremer, Sylvia","id":"2F64EC8C-F248-11E8-B48F-1D18A9856A87","first_name":"Sylvia","last_name":"Cremer","orcid":"0000-0002-2193-3868"},{"full_name":"Keller, Laurent","last_name":"Keller","first_name":"Laurent"}],"status":"public"},{"has_accepted_license":"1","citation":{"chicago":"Nejjar, Peter. “Transition to Shocks in TASEP and Decoupling of Last Passage Times.” <i>Latin American Journal of Probability and Mathematical Statistics</i>. Instituto Nacional de Matematica Pura e Aplicada, 2018. <a href=\"https://doi.org/10.30757/ALEA.v15-49\">https://doi.org/10.30757/ALEA.v15-49</a>.","ama":"Nejjar P. Transition to shocks in TASEP and decoupling of last passage times. <i>Latin American Journal of Probability and Mathematical Statistics</i>. 2018;15(2):1311-1334. doi:<a href=\"https://doi.org/10.30757/ALEA.v15-49\">10.30757/ALEA.v15-49</a>","apa":"Nejjar, P. (2018). Transition to shocks in TASEP and decoupling of last passage times. <i>Latin American Journal of Probability and Mathematical Statistics</i>. Instituto Nacional de Matematica Pura e Aplicada. <a href=\"https://doi.org/10.30757/ALEA.v15-49\">https://doi.org/10.30757/ALEA.v15-49</a>","short":"P. Nejjar, Latin American Journal of Probability and Mathematical Statistics 15 (2018) 1311–1334.","ieee":"P. Nejjar, “Transition to shocks in TASEP and decoupling of last passage times,” <i>Latin American Journal of Probability and Mathematical Statistics</i>, vol. 15, no. 2. Instituto Nacional de Matematica Pura e Aplicada, pp. 1311–1334, 2018.","mla":"Nejjar, Peter. “Transition to Shocks in TASEP and Decoupling of Last Passage Times.” <i>Latin American Journal of Probability and Mathematical Statistics</i>, vol. 15, no. 2, Instituto Nacional de Matematica Pura e Aplicada, 2018, pp. 1311–34, doi:<a href=\"https://doi.org/10.30757/ALEA.v15-49\">10.30757/ALEA.v15-49</a>.","ista":"Nejjar P. 2018. Transition to shocks in TASEP and decoupling of last passage times. Latin American Journal of Probability and Mathematical Statistics. 15(2), 1311–1334."},"abstract":[{"text":"We consider the totally asymmetric simple exclusion process in a critical scaling parametrized by a≥0, which creates a shock in the particle density of order aT−1/3, T the observation time. When starting from step initial data, we provide bounds on the limiting law which in particular imply that in the double limit lima→∞limT→∞ one recovers the product limit law and the degeneration of the correlation length observed at shocks of order 1. This result is shown to apply to a general last-passage percolation model. We also obtain bounds on the two-point functions of several airy processes.","lang":"eng"}],"date_published":"2018-10-01T00:00:00Z","date_updated":"2025-04-14T07:27:49Z","intvolume":"        15","issue":"2","publication":"Latin American Journal of Probability and Mathematical Statistics","status":"public","author":[{"last_name":"Nejjar","first_name":"Peter","id":"4BF426E2-F248-11E8-B48F-1D18A9856A87","full_name":"Nejjar, Peter"}],"page":"1311-1334","file":[{"date_created":"2019-02-14T09:44:10Z","access_level":"open_access","date_updated":"2020-07-14T12:47:46Z","creator":"kschuh","checksum":"2ded46aa284a836a8cbb34133a64f1cb","relation":"main_file","file_id":"5981","file_name":"2018_ALEA_Nejjar.pdf","content_type":"application/pdf","file_size":394851}],"ec_funded":1,"volume":15,"ddc":["510"],"month":"10","doi":"10.30757/ALEA.v15-49","_id":"70","oa_version":"Published Version","scopus_import":"1","article_type":"original","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:47:46Z","date_created":"2018-12-11T11:44:28Z","isi":1,"project":[{"call_identifier":"FP7","name":"Random matrices, universality and disordered quantum systems","_id":"258DCDE6-B435-11E9-9278-68D0E5697425","grant_number":"338804"},{"_id":"256E75B8-B435-11E9-9278-68D0E5697425","name":"Optimal Transport and Stochastic Dynamics","call_identifier":"H2020","grant_number":"716117"}],"quality_controlled":"1","type":"journal_article","external_id":{"isi":["000460475800022"],"arxiv":["1705.08836"]},"day":"01","oa":1,"publication_status":"published","year":"2018","publisher":"Instituto Nacional de Matematica Pura e Aplicada","department":[{"_id":"LaEr"},{"_id":"JaMa"}],"publication_identifier":{"issn":["1980-0436"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","arxiv":1,"article_processing_charge":"No","title":"Transition to shocks in TASEP and decoupling of last passage times"},{"isi":1,"date_created":"2018-12-11T11:48:02Z","quality_controlled":"1","_id":"705","scopus_import":"1","oa_version":"None","doi":"10.1007/s12035-017-0688-y","language":[{"iso":"eng"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","title":"Super resolution microscopical localization of dopamine receptors 1 and 2 in rat hippocampal synaptosomes","day":"01","external_id":{"isi":["000431991500025"]},"type":"journal_article","department":[{"_id":"RySh"}],"year":"2018","publication_status":"published","publisher":"Springer","date_updated":"2023-09-19T09:58:11Z","publist_id":"6991","intvolume":"        55","abstract":[{"lang":"eng","text":"Although dopamine receptors D1 and D2 play key roles in hippocampal function, their synaptic localization within the hippocampus has not been fully elucidated. In order to understand precise functions of pre- or postsynaptic dopamine receptors (DRs), the development of protocols to differentiate pre- and postsynaptic DRs is essential. So far, most studies on determination and quantification of DRs did not discriminate between subsynaptic localization. Therefore, the aim of the study was to generate a robust workflow for the localization of DRs. This work provides the basis for future work on hippocampal DRs, in light that DRs may have different functions at pre- or postsynaptic sites. Synaptosomes from rat hippocampi isolated by a sucrose gradient protocol were prepared for super-resolution direct stochastic optical reconstruction microscopy (dSTORM) using Bassoon as a presynaptic zone and Homer1 as postsynaptic density marker. Direct labeling of primary validated antibodies against dopamine receptors D1 (D1R) and D2 (D2R) with Alexa Fluor 594 enabled unequivocal assignment of D1R and D2R to both, pre- and postsynaptic sites. D1R immunoreactivity clusters were observed within the presynaptic active zone as well as at perisynaptic sites at the edge of the presynaptic active zone. The results may be useful for the interpretation of previous studies and the design of future work on DRs in the hippocampus. Moreover, the reduction of the complexity of brain tissue by the use of synaptosomal preparations and dSTORM technology may represent a useful tool for synaptic localization of brain proteins."}],"citation":{"ista":"Miklosi A, Del Favero G, Bulat T, Höger H, Shigemoto R, Marko D, Lubec G. 2018. Super resolution microscopical localization of dopamine receptors 1 and 2 in rat hippocampal synaptosomes. Molecular Neurobiology. 55(6), 4857 – 4869.","ieee":"A. Miklosi <i>et al.</i>, “Super resolution microscopical localization of dopamine receptors 1 and 2 in rat hippocampal synaptosomes,” <i>Molecular Neurobiology</i>, vol. 55, no. 6. Springer, pp. 4857 – 4869, 2018.","short":"A. Miklosi, G. Del Favero, T. Bulat, H. Höger, R. Shigemoto, D. Marko, G. Lubec, Molecular Neurobiology 55 (2018) 4857 – 4869.","mla":"Miklosi, Andras, et al. “Super Resolution Microscopical Localization of Dopamine Receptors 1 and 2 in Rat Hippocampal Synaptosomes.” <i>Molecular Neurobiology</i>, vol. 55, no. 6, Springer, 2018, pp. 4857 – 4869, doi:<a href=\"https://doi.org/10.1007/s12035-017-0688-y\">10.1007/s12035-017-0688-y</a>.","apa":"Miklosi, A., Del Favero, G., Bulat, T., Höger, H., Shigemoto, R., Marko, D., &#38; Lubec, G. (2018). Super resolution microscopical localization of dopamine receptors 1 and 2 in rat hippocampal synaptosomes. <i>Molecular Neurobiology</i>. Springer. <a href=\"https://doi.org/10.1007/s12035-017-0688-y\">https://doi.org/10.1007/s12035-017-0688-y</a>","ama":"Miklosi A, Del Favero G, Bulat T, et al. Super resolution microscopical localization of dopamine receptors 1 and 2 in rat hippocampal synaptosomes. <i>Molecular Neurobiology</i>. 2018;55(6):4857 – 4869. doi:<a href=\"https://doi.org/10.1007/s12035-017-0688-y\">10.1007/s12035-017-0688-y</a>","chicago":"Miklosi, Andras, Giorgia Del Favero, Tanja Bulat, Harald Höger, Ryuichi Shigemoto, Doris Marko, and Gert Lubec. “Super Resolution Microscopical Localization of Dopamine Receptors 1 and 2 in Rat Hippocampal Synaptosomes.” <i>Molecular Neurobiology</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s12035-017-0688-y\">https://doi.org/10.1007/s12035-017-0688-y</a>."},"date_published":"2018-06-01T00:00:00Z","page":"4857 – 4869","month":"06","volume":55,"publication":"Molecular Neurobiology","issue":"6","status":"public","author":[{"first_name":"Andras","last_name":"Miklosi","full_name":"Miklosi, Andras"},{"full_name":"Del Favero, Giorgia","last_name":"Del Favero","first_name":"Giorgia"},{"full_name":"Bulat, Tanja","last_name":"Bulat","first_name":"Tanja"},{"last_name":"Höger","first_name":"Harald","full_name":"Höger, Harald"},{"id":"499F3ABC-F248-11E8-B48F-1D18A9856A87","full_name":"Shigemoto, Ryuichi","last_name":"Shigemoto","orcid":"0000-0001-8761-9444","first_name":"Ryuichi"},{"last_name":"Marko","first_name":"Doris","full_name":"Marko, Doris"},{"first_name":"Gert","last_name":"Lubec","full_name":"Lubec, Gert"}]},{"date_updated":"2024-10-09T20:59:05Z","date_published":"2018-03-26T00:00:00Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","image":"/images/cc_by_nc_nd.png","short":"CC BY-NC-ND (4.0)"},"conference":{"start_date":"2018-03-26","end_date":"2018-03-29","location":"Vienna, Austria","name":"EDBT: Conference on Extending Database Technology"},"abstract":[{"lang":"eng","text":"Training deep learning models has received tremendous research interest recently. In particular, there has been intensive research on reducing the communication cost of training when using multiple computational devices, through reducing the precision of the underlying data representation. Naturally, such methods induce system trade-offs—lowering communication precision could de-crease communication overheads and improve scalability; but, on the other hand, it can also reduce the accuracy of training. In this paper, we study this trade-off space, and ask:Can low-precision communication consistently improve the end-to-end performance of training modern neural networks, with no accuracy loss?From the performance point of view, the answer to this question may appear deceptively easy: compressing communication through low precision should help when the ratio between communication and computation is high. However, this answer is less straightforward when we try to generalize this principle across various neural network architectures (e.g., AlexNet vs. ResNet),number of GPUs (e.g., 2 vs. 8 GPUs), machine configurations(e.g., EC2 instances vs. NVIDIA DGX-1), communication primitives (e.g., MPI vs. NCCL), and even different GPU architectures(e.g., Kepler vs. Pascal). Currently, it is not clear how a realistic realization of all these factors maps to the speed up provided by low-precision communication. In this paper, we conduct an empirical study to answer this question and report the insights."}],"citation":{"apa":"Grubic, D., Tam, L., Alistarh, D.-A., &#38; Zhang, C. (2018). Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study. In <i>Proceedings of the 21st International Conference on Extending Database Technology</i> (pp. 145–156). Vienna, Austria: OpenProceedings. <a href=\"https://doi.org/10.5441/002/EDBT.2018.14\">https://doi.org/10.5441/002/EDBT.2018.14</a>","ieee":"D. Grubic, L. Tam, D.-A. Alistarh, and C. Zhang, “Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study,” in <i>Proceedings of the 21st International Conference on Extending Database Technology</i>, Vienna, Austria, 2018, pp. 145–156.","short":"D. Grubic, L. Tam, D.-A. Alistarh, C. Zhang, in:, Proceedings of the 21st International Conference on Extending Database Technology, OpenProceedings, 2018, pp. 145–156.","mla":"Grubic, Demjan, et al. “Synchronous Multi-GPU Training for Deep Learning with Low-Precision Communications: An Empirical Study.” <i>Proceedings of the 21st International Conference on Extending Database Technology</i>, OpenProceedings, 2018, pp. 145–56, doi:<a href=\"https://doi.org/10.5441/002/EDBT.2018.14\">10.5441/002/EDBT.2018.14</a>.","chicago":"Grubic, Demjan, Leo Tam, Dan-Adrian Alistarh, and Ce Zhang. “Synchronous Multi-GPU Training for Deep Learning with Low-Precision Communications: An Empirical Study.” In <i>Proceedings of the 21st International Conference on Extending Database Technology</i>, 145–56. OpenProceedings, 2018. <a href=\"https://doi.org/10.5441/002/EDBT.2018.14\">https://doi.org/10.5441/002/EDBT.2018.14</a>.","ama":"Grubic D, Tam L, Alistarh D-A, Zhang C. Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study. In: <i>Proceedings of the 21st International Conference on Extending Database Technology</i>. OpenProceedings; 2018:145-156. doi:<a href=\"https://doi.org/10.5441/002/EDBT.2018.14\">10.5441/002/EDBT.2018.14</a>","ista":"Grubic D, Tam L, Alistarh D-A, Zhang C. 2018. Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study. Proceedings of the 21st International Conference on Extending Database Technology. EDBT: Conference on Extending Database Technology, 145–156."},"corr_author":"1","has_accepted_license":"1","month":"03","ddc":["000"],"file":[{"checksum":"ec979b56abc71016d6e6adfdadbb4afe","relation":"main_file","access_level":"open_access","date_created":"2019-11-26T14:23:04Z","creator":"dernst","date_updated":"2020-07-14T12:47:49Z","content_type":"application/pdf","file_size":1603204,"file_id":"7118","file_name":"2018_OpenProceedings_Grubic.pdf"}],"page":"145-156","author":[{"first_name":"Demjan","last_name":"Grubic","full_name":"Grubic, Demjan"},{"first_name":"Leo","last_name":"Tam","full_name":"Tam, Leo"},{"first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Zhang, Ce","last_name":"Zhang","first_name":"Ce"}],"status":"public","publication":"Proceedings of the 21st International Conference on Extending Database Technology","quality_controlled":"1","date_created":"2019-11-26T14:19:11Z","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:47:49Z","oa_version":"Published Version","scopus_import":1,"_id":"7116","doi":"10.5441/002/EDBT.2018.14","title":"Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study","article_processing_charge":"No","license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["2367-2005"],"isbn":["9783893180783"]},"department":[{"_id":"DaAl"}],"publisher":"OpenProceedings","year":"2018","publication_status":"published","oa":1,"day":"26","type":"conference"},{"year":"2018","publication_status":"published","publisher":"ACM","main_file_link":[{"url":"https://arxiv.org/abs/1704.04947","open_access":"1"}],"department":[{"_id":"DaAl"}],"type":"conference","external_id":{"arxiv":["1704.04947"],"isi":["000483921200145"]},"day":"30","oa":1,"article_processing_charge":"No","title":"Space-optimal majority in population protocols","publication_identifier":{"isbn":["9781611975031"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","arxiv":1,"language":[{"iso":"eng"}],"doi":"10.1137/1.9781611975031.144","_id":"7123","oa_version":"Preprint","scopus_import":"1","quality_controlled":"1","date_created":"2019-11-26T15:10:55Z","isi":1,"status":"public","author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","last_name":"Alistarh"},{"first_name":"James","last_name":"Aspnes","full_name":"Aspnes, James"},{"full_name":"Gelashvili, Rati","first_name":"Rati","last_name":"Gelashvili"}],"publication":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms","month":"01","page":"2221-2239","date_published":"2018-01-30T00:00:00Z","citation":{"mla":"Alistarh, Dan-Adrian, et al. “Space-Optimal Majority in Population Protocols.” <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, ACM, 2018, pp. 2221–39, doi:<a href=\"https://doi.org/10.1137/1.9781611975031.144\">10.1137/1.9781611975031.144</a>.","ieee":"D.-A. Alistarh, J. Aspnes, and R. Gelashvili, “Space-optimal majority in population protocols,” in <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, New Orleans, LA, United States, 2018, pp. 2221–2239.","short":"D.-A. Alistarh, J. Aspnes, R. Gelashvili, in:, Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, 2018, pp. 2221–2239.","apa":"Alistarh, D.-A., Aspnes, J., &#38; Gelashvili, R. (2018). Space-optimal majority in population protocols. In <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 2221–2239). New Orleans, LA, United States: ACM. <a href=\"https://doi.org/10.1137/1.9781611975031.144\">https://doi.org/10.1137/1.9781611975031.144</a>","ama":"Alistarh D-A, Aspnes J, Gelashvili R. Space-optimal majority in population protocols. In: <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>. ACM; 2018:2221-2239. doi:<a href=\"https://doi.org/10.1137/1.9781611975031.144\">10.1137/1.9781611975031.144</a>","chicago":"Alistarh, Dan-Adrian, James Aspnes, and Rati Gelashvili. “Space-Optimal Majority in Population Protocols.” In <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2221–39. ACM, 2018. <a href=\"https://doi.org/10.1137/1.9781611975031.144\">https://doi.org/10.1137/1.9781611975031.144</a>.","ista":"Alistarh D-A, Aspnes J, Gelashvili R. 2018. Space-optimal majority in population protocols. Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 2221–2239."},"abstract":[{"text":"Population protocols are a popular model of distributed computing, in which n agents with limited local state interact randomly, and cooperate to collectively compute global predicates. Inspired by recent developments in DNA programming, an extensive series of papers, across different communities, has examined the computability and complexity characteristics of this model. Majority, or consensus, is a central task in this model, in which agents need to collectively reach a decision as to which one of two states A or B had a higher initial count. Two metrics are important: the time that a protocol requires to stabilize to an output decision, and the state space size that each agent requires to do so. It is known that majority requires Ω(log log n) states per agent to allow for fast (poly-logarithmic time) stabilization, and that O(log2 n) states are sufficient. Thus, there is an exponential gap between the space upper and lower bounds for this problem. This paper addresses this question.\r\n\r\nOn the negative side, we provide a new lower bound of Ω(log n) states for any protocol which stabilizes in O(n1–c) expected time, for any constant c > 0. This result is conditional on monotonicity and output assumptions, satisfied by all known protocols. Technically, it represents a departure from previous lower bounds, in that it does not rely on the existence of dense configurations. Instead, we introduce a new generalized surgery technique to prove the existence of incorrect executions for any algorithm which would contradict the lower bound. Subsequently, our lower bound also applies to general initial configurations, including ones with a leader. On the positive side, we give a new algorithm for majority which uses O(log n) states, and stabilizes in O(log2 n) expected time. Central to the algorithm is a new leaderless phase clock technique, which allows agents to synchronize in phases of Θ(n log n) consecutive interactions using O(log n) states per agent, exploiting a new connection between population protocols and power-of-two-choices load balancing mechanisms. We also employ our phase clock to build a leader election algorithm with a state space of size O(log n), which stabilizes in O(log2 n) expected time.","lang":"eng"}],"conference":{"name":"SODA: Symposium on Discrete Algorithms","location":"New Orleans, LA, United States","start_date":"2018-01-07","end_date":"2018-01-10"},"date_updated":"2024-10-21T06:02:41Z"},{"date_updated":"2025-04-15T08:22:22Z","publist_id":"6957","intvolume":"        80","pubrep_id":"1014","citation":{"ista":"Oliveto P, Paixao T, Pérez Heredia J, Sudholt D, Trubenova B. 2018. How to escape local optima in black box optimisation when non elitism outperforms elitism. Algorithmica. 80(5), 1604–1633.","ieee":"P. Oliveto, T. Paixao, J. Pérez Heredia, D. Sudholt, and B. Trubenova, “How to escape local optima in black box optimisation when non elitism outperforms elitism,” <i>Algorithmica</i>, vol. 80, no. 5. Springer, pp. 1604–1633, 2018.","short":"P. Oliveto, T. Paixao, J. Pérez Heredia, D. Sudholt, B. Trubenova, Algorithmica 80 (2018) 1604–1633.","mla":"Oliveto, Pietro, et al. “How to Escape Local Optima in Black Box Optimisation When Non Elitism Outperforms Elitism.” <i>Algorithmica</i>, vol. 80, no. 5, Springer, 2018, pp. 1604–33, doi:<a href=\"https://doi.org/10.1007/s00453-017-0369-2\">10.1007/s00453-017-0369-2</a>.","apa":"Oliveto, P., Paixao, T., Pérez Heredia, J., Sudholt, D., &#38; Trubenova, B. (2018). How to escape local optima in black box optimisation when non elitism outperforms elitism. <i>Algorithmica</i>. Springer. <a href=\"https://doi.org/10.1007/s00453-017-0369-2\">https://doi.org/10.1007/s00453-017-0369-2</a>","ama":"Oliveto P, Paixao T, Pérez Heredia J, Sudholt D, Trubenova B. How to escape local optima in black box optimisation when non elitism outperforms elitism. <i>Algorithmica</i>. 2018;80(5):1604-1633. doi:<a href=\"https://doi.org/10.1007/s00453-017-0369-2\">10.1007/s00453-017-0369-2</a>","chicago":"Oliveto, Pietro, Tiago Paixao, Jorge Pérez Heredia, Dirk Sudholt, and Barbora Trubenova. “How to Escape Local Optima in Black Box Optimisation When Non Elitism Outperforms Elitism.” <i>Algorithmica</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s00453-017-0369-2\">https://doi.org/10.1007/s00453-017-0369-2</a>."},"abstract":[{"text":"Escaping local optima is one of the major obstacles to function optimisation. Using the metaphor of a fitness landscape, local optima correspond to hills separated by fitness valleys that have to be overcome. We define a class of fitness valleys of tunable difficulty by considering their length, representing the Hamming path between the two optima and their depth, the drop in fitness. For this function class we present a runtime comparison between stochastic search algorithms using different search strategies. The (1+1) EA is a simple and well-studied evolutionary algorithm that has to jump across the valley to a point of higher fitness because it does not accept worsening moves (elitism). In contrast, the Metropolis algorithm and the Strong Selection Weak Mutation (SSWM) algorithm, a famous process in population genetics, are both able to cross the fitness valley by accepting worsening moves. We show that the runtime of the (1+1) EA depends critically on the length of the valley while the runtimes of the non-elitist algorithms depend crucially on the depth of the valley. Moreover, we show that both SSWM and Metropolis can also efficiently optimise a rugged function consisting of consecutive valleys.","lang":"eng"}],"has_accepted_license":"1","date_published":"2018-05-01T00:00:00Z","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"file":[{"file_id":"4674","file_name":"IST-2018-1014-v1+1_2018_Paixao_Escape.pdf","content_type":"application/pdf","file_size":691245,"access_level":"open_access","date_created":"2018-12-12T10:08:14Z","creator":"system","date_updated":"2020-07-14T12:47:54Z","checksum":"7d92f5d7be81e387edeec4f06442791c","relation":"main_file"}],"page":"1604 - 1633","month":"05","volume":80,"ec_funded":1,"ddc":["576"],"issue":"5","publication":"Algorithmica","status":"public","author":[{"full_name":"Oliveto, Pietro","first_name":"Pietro","last_name":"Oliveto"},{"first_name":"Tiago","last_name":"Paixao","orcid":"0000-0003-2361-3953","full_name":"Paixao, Tiago","id":"2C5658E6-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Pérez Heredia","first_name":"Jorge","full_name":"Pérez Heredia, Jorge"},{"full_name":"Sudholt, Dirk","last_name":"Sudholt","first_name":"Dirk"},{"id":"42302D54-F248-11E8-B48F-1D18A9856A87","full_name":"Trubenova, Barbora","first_name":"Barbora","last_name":"Trubenova","orcid":"0000-0002-6873-2967"}],"isi":1,"date_created":"2018-12-11T11:48:09Z","quality_controlled":"1","project":[{"grant_number":"618091","call_identifier":"FP7","name":"Speed of Adaptation in Population Genetics and Evolutionary Computation","_id":"25B1EC9E-B435-11E9-9278-68D0E5697425"}],"_id":"723","oa_version":"Published Version","scopus_import":"1","doi":"10.1007/s00453-017-0369-2","file_date_updated":"2020-07-14T12:47:54Z","language":[{"iso":"eng"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","title":"How to escape local optima in black box optimisation when non elitism outperforms elitism","external_id":{"isi":["000428239300010"]},"day":"01","oa":1,"type":"journal_article","department":[{"_id":"NiBa"},{"_id":"CaGu"}],"year":"2018","publication_status":"published","publisher":"Springer"},{"corr_author":"1","has_accepted_license":"1","citation":{"ista":"Chatterjee K, Pavlogiannis A, Kößler A, Schmid U. 2018. Automated competitive analysis of real time scheduling with graph games. Real-Time Systems. 54(1), 166–207.","ama":"Chatterjee K, Pavlogiannis A, Kößler A, Schmid U. Automated competitive analysis of real time scheduling with graph games. <i>Real-Time Systems</i>. 2018;54(1):166-207. doi:<a href=\"https://doi.org/10.1007/s11241-017-9293-4\">10.1007/s11241-017-9293-4</a>","chicago":"Chatterjee, Krishnendu, Andreas Pavlogiannis, Alexander Kößler, and Ulrich Schmid. “Automated Competitive Analysis of Real Time Scheduling with Graph Games.” <i>Real-Time Systems</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s11241-017-9293-4\">https://doi.org/10.1007/s11241-017-9293-4</a>.","mla":"Chatterjee, Krishnendu, et al. “Automated Competitive Analysis of Real Time Scheduling with Graph Games.” <i>Real-Time Systems</i>, vol. 54, no. 1, Springer, 2018, pp. 166–207, doi:<a href=\"https://doi.org/10.1007/s11241-017-9293-4\">10.1007/s11241-017-9293-4</a>.","ieee":"K. Chatterjee, A. Pavlogiannis, A. Kößler, and U. Schmid, “Automated competitive analysis of real time scheduling with graph games,” <i>Real-Time Systems</i>, vol. 54, no. 1. Springer, pp. 166–207, 2018.","short":"K. Chatterjee, A. Pavlogiannis, A. Kößler, U. Schmid, Real-Time Systems 54 (2018) 166–207.","apa":"Chatterjee, K., Pavlogiannis, A., Kößler, A., &#38; Schmid, U. (2018). Automated competitive analysis of real time scheduling with graph games. <i>Real-Time Systems</i>. Springer. <a href=\"https://doi.org/10.1007/s11241-017-9293-4\">https://doi.org/10.1007/s11241-017-9293-4</a>"},"abstract":[{"lang":"eng","text":"This paper is devoted to automatic competitive analysis of real-time scheduling algorithms for firm-deadline tasksets, where only completed tasks con- tribute some utility to the system. Given such a taskset T , the competitive ratio of an on-line scheduling algorithm A for T is the worst-case utility ratio of A over the utility achieved by a clairvoyant algorithm. We leverage the theory of quantitative graph games to address the competitive analysis and competitive synthesis problems. For the competitive analysis case, given any taskset T and any finite-memory on- line scheduling algorithm A , we show that the competitive ratio of A in T can be computed in polynomial time in the size of the state space of A . Our approach is flexible as it also provides ways to model meaningful constraints on the released task sequences that determine the competitive ratio. We provide an experimental study of many well-known on-line scheduling algorithms, which demonstrates the feasibility of our competitive analysis approach that effectively replaces human ingenuity (required Preliminary versions of this paper have appeared in Chatterjee et al. ( 2013 , 2014 ). B Andreas Pavlogiannis pavlogiannis@ist.ac.at Krishnendu Chatterjee krish.chat@ist.ac.at Alexander Kößler koe@ecs.tuwien.ac.at Ulrich Schmid s@ecs.tuwien.ac.at 1 IST Austria (Institute of Science and Technology Austria), Am Campus 1, 3400 Klosterneuburg, Austria 2 Embedded Computing Systems Group, Vienna University of Technology, Treitlstrasse 3, 1040 Vienna, Austria 123 Real-Time Syst for finding worst-case scenarios) by computing power. For the competitive synthesis case, we are just given a taskset T , and the goal is to automatically synthesize an opti- mal on-line scheduling algorithm A , i.e., one that guarantees the largest competitive ratio possible for T . We show how the competitive synthesis problem can be reduced to a two-player graph game with partial information, and establish that the compu- tational complexity of solving this game is Np -complete. The competitive synthesis problem is hence in Np in the size of the state space of the non-deterministic labeled transition system encoding the taskset. Overall, the proposed framework assists in the selection of suitable scheduling algorithms for a given taskset, which is in fact the most common situation in real-time systems design. "}],"related_material":{"record":[{"id":"2820","status":"public","relation":"earlier_version"}]},"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"date_published":"2018-01-01T00:00:00Z","publist_id":"6929","date_updated":"2025-04-15T08:12:27Z","pubrep_id":"960","intvolume":"        54","issue":"1","publication":"Real-Time Systems","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"full_name":"Pavlogiannis, Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722"},{"last_name":"Kößler","first_name":"Alexander","full_name":"Kößler, Alexander"},{"full_name":"Schmid, Ulrich","first_name":"Ulrich","last_name":"Schmid"}],"status":"public","page":"166 - 207","file":[{"relation":"main_file","checksum":"c2590ef160709d8054cf29ee173f1454","creator":"system","date_updated":"2020-07-14T12:47:56Z","date_created":"2018-12-12T10:17:14Z","access_level":"open_access","file_size":1163507,"content_type":"application/pdf","file_name":"IST-2018-960-v1+1_2017_Chatterjee_Automated_competetive.pdf","file_id":"5267"}],"ddc":["000"],"ec_funded":1,"volume":54,"month":"01","doi":"10.1007/s11241-017-9293-4","scopus_import":"1","oa_version":"Published Version","_id":"738","file_date_updated":"2020-07-14T12:47:56Z","language":[{"iso":"eng"}],"date_created":"2018-12-11T11:48:14Z","isi":1,"project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23"},{"grant_number":"S11407","call_identifier":"FWF","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"quality_controlled":"1","type":"journal_article","oa":1,"day":"01","external_id":{"isi":["000419955500006"]},"publisher":"Springer","publication_status":"published","year":"2018","department":[{"_id":"KrCh"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","title":"Automated competitive analysis of real time scheduling with graph games","article_processing_charge":"No"},{"author":[{"full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z"}],"status":"public","publication":"10th Innovations in Theoretical Computer Science Conference","alternative_title":["LIPIcs"],"month":"12","ddc":["000"],"ec_funded":1,"volume":124,"file":[{"relation":"main_file","checksum":"5cebb7f7849a3beda898f697d755dd96","creator":"dernst","date_updated":"2020-07-14T12:47:57Z","access_level":"open_access","date_created":"2020-02-04T08:17:52Z","file_size":822884,"content_type":"application/pdf","file_name":"2018_LIPIcs_Pietrzak.pdf","file_id":"7443"}],"page":"59:1-59:25","date_published":"2018-12-31T00:00:00Z","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"conference":{"location":"San Diego, CA, United States","name":"ITCS: Innovations in Theoretical Computer Science","end_date":"2019-01-12","start_date":"2019-01-10"},"abstract":[{"lang":"eng","text":"Proofs of space (PoS) [Dziembowski et al., CRYPTO'15] are proof systems where a prover can convince a verifier that he \"wastes\" disk space. PoS were introduced as a more ecological and economical replacement for proofs of work which are currently used to secure blockchains like Bitcoin. In this work we investigate extensions of PoS which allow the prover to embed useful data into the dedicated space, which later can be recovered. Our first contribution is a security proof for the original PoS from CRYPTO'15 in the random oracle model (the original proof only applied to a restricted class of adversaries which can store a subset of the data an honest prover would store). When this PoS is instantiated with recent constructions of maximally depth robust graphs, our proof implies basically optimal security. As a second contribution we show three different extensions of this PoS where useful data can be embedded into the space required by the prover. Our security proof for the PoS extends (non-trivially) to these constructions. We discuss how some of these variants can be used as proofs of catalytic space (PoCS), a notion we put forward in this work, and which basically is a PoS where most of the space required by the prover can be used to backup useful data. Finally we discuss how one of the extensions is a candidate construction for a proof of replication (PoR), a proof system recently suggested in the Filecoin whitepaper. "}],"citation":{"ista":"Pietrzak KZ. 2018. Proofs of catalytic space. 10th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 124, 59:1-59:25.","ieee":"K. Z. Pietrzak, “Proofs of catalytic space,” in <i>10th Innovations in Theoretical Computer Science Conference</i>, San Diego, CA, United States, 2018, vol. 124, p. 59:1-59:25.","short":"K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 59:1-59:25.","mla":"Pietrzak, Krzysztof Z. “Proofs of Catalytic Space.” <i>10th Innovations in Theoretical Computer Science Conference</i>, vol. 124, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 59:1-59:25, doi:<a href=\"https://doi.org/10.4230/LIPICS.ITCS.2019.59\">10.4230/LIPICS.ITCS.2019.59</a>.","apa":"Pietrzak, K. Z. (2018). Proofs of catalytic space. In <i>10th Innovations in Theoretical Computer Science Conference</i> (Vol. 124, p. 59:1-59:25). San Diego, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ITCS.2019.59\">https://doi.org/10.4230/LIPICS.ITCS.2019.59</a>","ama":"Pietrzak KZ. Proofs of catalytic space. In: <i>10th Innovations in Theoretical Computer Science Conference</i>. Vol 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:59:1-59:25. doi:<a href=\"https://doi.org/10.4230/LIPICS.ITCS.2019.59\">10.4230/LIPICS.ITCS.2019.59</a>","chicago":"Pietrzak, Krzysztof Z. “Proofs of Catalytic Space.” In <i>10th Innovations in Theoretical Computer Science Conference</i>, 124:59:1-59:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPICS.ITCS.2019.59\">https://doi.org/10.4230/LIPICS.ITCS.2019.59</a>."},"has_accepted_license":"1","corr_author":"1","intvolume":"       124","date_updated":"2025-07-03T11:55:28Z","department":[{"_id":"KrPi"}],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2018/194"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_status":"published","year":"2018","oa":1,"day":"31","type":"conference","title":"Proofs of catalytic space","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"isbn":["978-3-95977-095-8"],"issn":["1868-8969"]},"file_date_updated":"2020-07-14T12:47:57Z","language":[{"iso":"eng"}],"scopus_import":"1","oa_version":"Published Version","_id":"7407","doi":"10.4230/LIPICS.ITCS.2019.59","quality_controlled":"1","project":[{"grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","name":"Teaching Old Crypto New Tricks"}],"date_created":"2020-01-30T09:16:05Z"},{"date_published":"2018-08-01T00:00:00Z","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"1378"}]},"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"citation":{"short":"D. Dotterrer, T. Kaufman, U. Wagner, Geometriae Dedicata 195 (2018) 307–317.","mla":"Dotterrer, Dominic, et al. “On Expansion and Topological Overlap.” <i>Geometriae Dedicata</i>, vol. 195, no. 1, Springer, 2018, pp. 307–317, doi:<a href=\"https://doi.org/10.1007/s10711-017-0291-4\">10.1007/s10711-017-0291-4</a>.","ieee":"D. Dotterrer, T. Kaufman, and U. Wagner, “On expansion and topological overlap,” <i>Geometriae Dedicata</i>, vol. 195, no. 1. Springer, pp. 307–317, 2018.","apa":"Dotterrer, D., Kaufman, T., &#38; Wagner, U. (2018). On expansion and topological overlap. <i>Geometriae Dedicata</i>. Springer. <a href=\"https://doi.org/10.1007/s10711-017-0291-4\">https://doi.org/10.1007/s10711-017-0291-4</a>","ama":"Dotterrer D, Kaufman T, Wagner U. On expansion and topological overlap. <i>Geometriae Dedicata</i>. 2018;195(1):307–317. doi:<a href=\"https://doi.org/10.1007/s10711-017-0291-4\">10.1007/s10711-017-0291-4</a>","chicago":"Dotterrer, Dominic, Tali Kaufman, and Uli Wagner. “On Expansion and Topological Overlap.” <i>Geometriae Dedicata</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s10711-017-0291-4\">https://doi.org/10.1007/s10711-017-0291-4</a>.","ista":"Dotterrer D, Kaufman T, Wagner U. 2018. On expansion and topological overlap. Geometriae Dedicata. 195(1), 307–317."},"abstract":[{"text":"We give a detailed and easily accessible proof of Gromov’s Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map (Formula presented.) there exists a point (Formula presented.) that is contained in the images of a positive fraction (Formula presented.) of the d-cells of X. More generally, the conclusion holds if (Formula presented.) is replaced by any d-dimensional piecewise-linear manifold M, with a constant (Formula presented.) that depends only on d and on the expansion properties of X, but not on M.","lang":"eng"}],"corr_author":"1","has_accepted_license":"1","pubrep_id":"912","intvolume":"       195","date_updated":"2025-06-03T11:41:00Z","publist_id":"6925","author":[{"first_name":"Dominic","last_name":"Dotterrer","full_name":"Dotterrer, Dominic"},{"full_name":"Kaufman, Tali","last_name":"Kaufman","first_name":"Tali"},{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","orcid":"0000-0002-1494-0568","first_name":"Uli"}],"status":"public","publication":"Geometriae Dedicata","issue":"1","month":"08","ddc":["514","516"],"volume":195,"file":[{"checksum":"d2f70fc132156504aa4c626aa378a7ab","relation":"main_file","date_created":"2019-01-15T13:44:05Z","access_level":"open_access","date_updated":"2020-07-14T12:47:58Z","creator":"kschuh","content_type":"application/pdf","file_size":412486,"file_id":"5835","file_name":"s10711-017-0291-4.pdf"}],"page":"307–317","file_date_updated":"2020-07-14T12:47:58Z","language":[{"iso":"eng"}],"oa_version":"Published Version","scopus_import":"1","_id":"742","doi":"10.1007/s10711-017-0291-4","quality_controlled":"1","project":[{"name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","_id":"25FA3206-B435-11E9-9278-68D0E5697425","grant_number":"PP00P2_138948"}],"isi":1,"date_created":"2018-12-11T11:48:16Z","department":[{"_id":"UlWa"}],"publisher":"Springer","year":"2018","publication_status":"published","oa":1,"external_id":{"isi":["000437122700017"]},"day":"01","type":"journal_article","title":"On expansion and topological overlap","article_processing_charge":"Yes (via OA deal)","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1"},{"isi":1,"date_created":"2018-12-11T11:44:30Z","quality_controlled":"1","project":[{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"_id":"76","oa_version":"Published Version","scopus_import":"1","doi":"10.1007/s00446-018-0342-6","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:48:01Z","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"Yes (via OA deal)","title":"Near-optimal self-stabilising counting and firing squads","external_id":{"isi":["000475627800005"]},"day":"12","oa":1,"type":"journal_article","department":[{"_id":"DaAl"}],"year":"2018","publication_status":"published","publisher":"Springer","date_updated":"2025-04-15T06:53:15Z","publist_id":"7978","citation":{"apa":"Lenzen, C., &#38; Rybicki, J. (2018). Near-optimal self-stabilising counting and firing squads. <i>Distributed Computing</i>. Springer. <a href=\"https://doi.org/10.1007/s00446-018-0342-6\">https://doi.org/10.1007/s00446-018-0342-6</a>","ieee":"C. Lenzen and J. Rybicki, “Near-optimal self-stabilising counting and firing squads,” <i>Distributed Computing</i>. Springer, 2018.","mla":"Lenzen, Christoph, and Joel Rybicki. “Near-Optimal Self-Stabilising Counting and Firing Squads.” <i>Distributed Computing</i>, Springer, 2018, doi:<a href=\"https://doi.org/10.1007/s00446-018-0342-6\">10.1007/s00446-018-0342-6</a>.","short":"C. Lenzen, J. Rybicki, Distributed Computing (2018).","chicago":"Lenzen, Christoph, and Joel Rybicki. “Near-Optimal Self-Stabilising Counting and Firing Squads.” <i>Distributed Computing</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s00446-018-0342-6\">https://doi.org/10.1007/s00446-018-0342-6</a>.","ama":"Lenzen C, Rybicki J. Near-optimal self-stabilising counting and firing squads. <i>Distributed Computing</i>. 2018. doi:<a href=\"https://doi.org/10.1007/s00446-018-0342-6\">10.1007/s00446-018-0342-6</a>","ista":"Lenzen C, Rybicki J. 2018. Near-optimal self-stabilising counting and firing squads. Distributed Computing."},"abstract":[{"lang":"eng","text":"Consider a fully-connected synchronous distributed system consisting of n nodes, where up to f nodes may be faulty and every node starts in an arbitrary initial state. In the synchronous C-counting problem, all nodes need to eventually agree on a counter that is increased by one modulo C in each round for given C&gt;1. In the self-stabilising firing squad problem, the task is to eventually guarantee that all non-faulty nodes have simultaneous responses to external inputs: if a subset of the correct nodes receive an external “go” signal as input, then all correct nodes should agree on a round (in the not-too-distant future) in which to jointly output a “fire” signal. Moreover, no node should generate a “fire” signal without some correct node having previously received a “go” signal as input. We present a framework reducing both tasks to binary consensus at very small cost. For example, we obtain a deterministic algorithm for self-stabilising Byzantine firing squads with optimal resilience f&lt;n/3, asymptotically optimal stabilisation and response time O(f), and message size O(log f). As our framework does not restrict the type of consensus routines used, we also obtain efficient randomised solutions."}],"has_accepted_license":"1","corr_author":"1","date_published":"2018-09-12T00:00:00Z","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"file":[{"checksum":"872db70bba9b401500abe3c6ae2f1a61","relation":"main_file","access_level":"open_access","date_created":"2018-12-17T14:21:22Z","date_updated":"2020-07-14T12:48:01Z","creator":"dernst","content_type":"application/pdf","file_size":799337,"file_id":"5711","file_name":"2018_DistributedComputing_Lenzen.pdf"}],"month":"09","ddc":["000"],"publication":"Distributed Computing","status":"public","author":[{"last_name":"Lenzen","first_name":"Christoph","full_name":"Lenzen, Christoph"},{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","full_name":"Rybicki, Joel","first_name":"Joel","last_name":"Rybicki","orcid":"0000-0002-6432-6646"}]},{"month":"03","article_processing_charge":"No","title":"Implementation of the inference method in Matlab","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","department":[{"_id":"GaTk"}],"status":"public","author":[{"last_name":"Bod’Ová","first_name":"Katarína","full_name":"Bod’Ová, Katarína"},{"full_name":"Mitchell, Gabriel","id":"315BCD80-F248-11E8-B48F-1D18A9856A87","last_name":"Mitchell","first_name":"Gabriel"},{"first_name":"Roy","last_name":"Harpaz","full_name":"Harpaz, Roy"},{"full_name":"Schneidman, Elad","first_name":"Elad","last_name":"Schneidman"},{"orcid":"0000-0002-6699-1455","last_name":"Tkačik","first_name":"Gašper","id":"3D494DCA-F248-11E8-B48F-1D18A9856A87","full_name":"Tkačik, Gašper"}],"year":"2018","publisher":"Public Library of Science","day":"07","type":"research_data_reference","date_updated":"2025-04-15T06:44:30Z","date_created":"2021-08-09T07:01:24Z","date_published":"2018-03-07T00:00:00Z","related_material":{"record":[{"id":"406","relation":"used_in_publication","status":"public"}]},"abstract":[{"lang":"eng","text":"Implementation of the inference method in Matlab, including three applications of the method: The first one for the model of ant motion, the second one for bacterial chemotaxis, and the third one for the motion of fish."}],"_id":"9831","citation":{"chicago":"Bod’Ová, Katarína, Gabriel Mitchell, Roy Harpaz, Elad Schneidman, and Gašper Tkačik. “Implementation of the Inference Method in Matlab.” Public Library of Science, 2018. <a href=\"https://doi.org/10.1371/journal.pone.0193049.s001\">https://doi.org/10.1371/journal.pone.0193049.s001</a>.","ama":"Bod’Ová K, Mitchell G, Harpaz R, Schneidman E, Tkačik G. Implementation of the inference method in Matlab. 2018. doi:<a href=\"https://doi.org/10.1371/journal.pone.0193049.s001\">10.1371/journal.pone.0193049.s001</a>","apa":"Bod’Ová, K., Mitchell, G., Harpaz, R., Schneidman, E., &#38; Tkačik, G. (2018). Implementation of the inference method in Matlab. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pone.0193049.s001\">https://doi.org/10.1371/journal.pone.0193049.s001</a>","ieee":"K. Bod’Ová, G. Mitchell, R. Harpaz, E. Schneidman, and G. Tkačik, “Implementation of the inference method in Matlab.” Public Library of Science, 2018.","short":"K. Bod’Ová, G. Mitchell, R. Harpaz, E. Schneidman, G. Tkačik, (2018).","mla":"Bod’Ová, Katarína, et al. <i>Implementation of the Inference Method in Matlab</i>. Public Library of Science, 2018, doi:<a href=\"https://doi.org/10.1371/journal.pone.0193049.s001\">10.1371/journal.pone.0193049.s001</a>.","ista":"Bod’Ová K, Mitchell G, Harpaz R, Schneidman E, Tkačik G. 2018. Implementation of the inference method in Matlab, Public Library of Science, <a href=\"https://doi.org/10.1371/journal.pone.0193049.s001\">10.1371/journal.pone.0193049.s001</a>."},"oa_version":"Published Version","doi":"10.1371/journal.pone.0193049.s001"},{"date_created":"2021-08-09T12:46:39Z","date_updated":"2023-08-24T14:50:26Z","doi":"10.5061/dryad.72cg113","_id":"9837","abstract":[{"lang":"eng","text":"Both classical and recent studies suggest that chromosomal inversion polymorphisms are important in adaptation and speciation. However, biases in discovery and reporting of inversions make it difficult to assess their prevalence and biological importance. Here, we use an approach based on linkage disequilibrium among markers genotyped for samples collected across a transect between contrasting habitats to detect chromosomal rearrangements de novo. We report 17 polymorphic rearrangements in a single locality for the coastal marine snail, Littorina saxatilis. Patterns of diversity in the field and of recombination in controlled crosses provide strong evidence that at least the majority of these rearrangements are inversions. Most show clinal changes in frequency between habitats, suggestive of divergent selection, but only one appears to be fixed for different arrangements in the two habitats. Consistent with widespread evidence for balancing selection on inversion polymorphisms, we argue that a combination of heterosis and divergent selection can explain the observed patterns and should be considered in other systems spanning environmental gradients."}],"citation":{"ista":"Faria R, Chaube P, Morales HE, Larsson T, Lemmon AR, Lemmon EM, Rafajlović M, Panova M, Ravinet M, Johannesson K, Westram AM, Butlin RK. 2018. Data from: Multiple chromosomal rearrangements in a hybrid zone between Littorina saxatilis ecotypes, Dryad, <a href=\"https://doi.org/10.5061/dryad.72cg113\">10.5061/dryad.72cg113</a>.","ieee":"R. Faria <i>et al.</i>, “Data from: Multiple chromosomal rearrangements in a hybrid zone between Littorina saxatilis ecotypes.” Dryad, 2018.","short":"R. Faria, P. Chaube, H.E. Morales, T. Larsson, A.R. Lemmon, E.M. Lemmon, M. Rafajlović, M. Panova, M. Ravinet, K. Johannesson, A.M. Westram, R.K. Butlin, (2018).","mla":"Faria, Rui, et al. <i>Data from: Multiple Chromosomal Rearrangements in a Hybrid Zone between Littorina Saxatilis Ecotypes</i>. Dryad, 2018, doi:<a href=\"https://doi.org/10.5061/dryad.72cg113\">10.5061/dryad.72cg113</a>.","apa":"Faria, R., Chaube, P., Morales, H. E., Larsson, T., Lemmon, A. R., Lemmon, E. M., … Butlin, R. K. (2018). Data from: Multiple chromosomal rearrangements in a hybrid zone between Littorina saxatilis ecotypes. Dryad. <a href=\"https://doi.org/10.5061/dryad.72cg113\">https://doi.org/10.5061/dryad.72cg113</a>","ama":"Faria R, Chaube P, Morales HE, et al. Data from: Multiple chromosomal rearrangements in a hybrid zone between Littorina saxatilis ecotypes. 2018. doi:<a href=\"https://doi.org/10.5061/dryad.72cg113\">10.5061/dryad.72cg113</a>","chicago":"Faria, Rui, Pragya Chaube, Hernán E. Morales, Tomas Larsson, Alan R. Lemmon, Emily M. Lemmon, Marina Rafajlović, et al. “Data from: Multiple Chromosomal Rearrangements in a Hybrid Zone between Littorina Saxatilis Ecotypes.” Dryad, 2018. <a href=\"https://doi.org/10.5061/dryad.72cg113\">https://doi.org/10.5061/dryad.72cg113</a>."},"oa_version":"Published Version","related_material":{"record":[{"id":"6095","status":"public","relation":"used_in_publication"}]},"date_published":"2018-10-09T00:00:00Z","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","article_processing_charge":"No","title":"Data from: Multiple chromosomal rearrangements in a hybrid zone between Littorina saxatilis ecotypes","month":"10","type":"research_data_reference","day":"09","oa":1,"year":"2018","publisher":"Dryad","department":[{"_id":"NiBa"}],"status":"public","main_file_link":[{"url":"https://doi.org/10.5061/dryad.72cg113","open_access":"1"}],"author":[{"full_name":"Faria, Rui","last_name":"Faria","first_name":"Rui"},{"first_name":"Pragya","last_name":"Chaube","full_name":"Chaube, Pragya"},{"last_name":"Morales","first_name":"Hernán E.","full_name":"Morales, Hernán E."},{"full_name":"Larsson, Tomas","first_name":"Tomas","last_name":"Larsson"},{"last_name":"Lemmon","first_name":"Alan R.","full_name":"Lemmon, Alan R."},{"full_name":"Lemmon, Emily M.","first_name":"Emily M.","last_name":"Lemmon"},{"last_name":"Rafajlović","first_name":"Marina","full_name":"Rafajlović, Marina"},{"full_name":"Panova, Marina","first_name":"Marina","last_name":"Panova"},{"last_name":"Ravinet","first_name":"Mark","full_name":"Ravinet, Mark"},{"last_name":"Johannesson","first_name":"Kerstin","full_name":"Johannesson, Kerstin"},{"first_name":"Anja M","orcid":"0000-0003-1050-4969","last_name":"Westram","id":"3C147470-F248-11E8-B48F-1D18A9856A87","full_name":"Westram, Anja M"},{"last_name":"Butlin","first_name":"Roger K.","full_name":"Butlin, Roger K."}]},{"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","month":"06","article_processing_charge":"No","title":"Data from: Signals from the brain and olfactory epithelium control shaping of the mammalian nasal capsule cartilage","day":"14","oa":1,"type":"research_data_reference","status":"public","department":[{"_id":"AnKi"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.5061/dryad.f1s76f2"}],"author":[{"full_name":"Kaucka, Marketa","first_name":"Marketa","last_name":"Kaucka"},{"first_name":"Julian","last_name":"Petersen","full_name":"Petersen, Julian"},{"last_name":"Tesarova","first_name":"Marketa","full_name":"Tesarova, Marketa"},{"last_name":"Szarowska","first_name":"Bara","full_name":"Szarowska, Bara"},{"full_name":"Kastriti, Maria Eleni","last_name":"Kastriti","first_name":"Maria Eleni"},{"full_name":"Xie, Meng","last_name":"Xie","first_name":"Meng"},{"full_name":"Kicheva, Anna","id":"3959A2A0-F248-11E8-B48F-1D18A9856A87","first_name":"Anna","last_name":"Kicheva","orcid":"0000-0003-4509-4998"},{"first_name":"Karl","last_name":"Annusver","full_name":"Annusver, Karl"},{"full_name":"Kasper, Maria","last_name":"Kasper","first_name":"Maria"},{"last_name":"Symmons","first_name":"Orsolya","full_name":"Symmons, Orsolya"},{"last_name":"Pan","first_name":"Leslie","full_name":"Pan, Leslie"},{"last_name":"Spitz","first_name":"Francois","full_name":"Spitz, Francois"},{"first_name":"Jozef","last_name":"Kaiser","full_name":"Kaiser, Jozef"},{"first_name":"Maria","last_name":"Hovorakova","full_name":"Hovorakova, Maria"},{"full_name":"Zikmund, Tomas","last_name":"Zikmund","first_name":"Tomas"},{"last_name":"Sunadome","first_name":"Kazunori","full_name":"Sunadome, Kazunori"},{"full_name":"Matise, Michael P","last_name":"Matise","first_name":"Michael P"},{"full_name":"Wang, Hui","last_name":"Wang","first_name":"Hui"},{"last_name":"Marklund","first_name":"Ulrika","full_name":"Marklund, Ulrika"},{"full_name":"Abdo, Hind","last_name":"Abdo","first_name":"Hind"},{"full_name":"Ernfors, Patrik","first_name":"Patrik","last_name":"Ernfors"},{"full_name":"Maire, Pascal","last_name":"Maire","first_name":"Pascal"},{"last_name":"Wurmser","first_name":"Maud","full_name":"Wurmser, Maud"},{"full_name":"Chagin, Andrei S","last_name":"Chagin","first_name":"Andrei S"},{"last_name":"Fried","first_name":"Kaj","full_name":"Fried, Kaj"},{"full_name":"Adameyko, Igor","last_name":"Adameyko","first_name":"Igor"}],"year":"2018","publisher":"Dryad","date_updated":"2025-04-14T13:02:22Z","date_created":"2021-08-09T12:54:35Z","citation":{"ama":"Kaucka M, Petersen J, Tesarova M, et al. Data from: Signals from the brain and olfactory epithelium control shaping of the mammalian nasal capsule cartilage. 2018. doi:<a href=\"https://doi.org/10.5061/dryad.f1s76f2\">10.5061/dryad.f1s76f2</a>","chicago":"Kaucka, Marketa, Julian Petersen, Marketa Tesarova, Bara Szarowska, Maria Eleni Kastriti, Meng Xie, Anna Kicheva, et al. “Data from: Signals from the Brain and Olfactory Epithelium Control Shaping of the Mammalian Nasal Capsule Cartilage.” Dryad, 2018. <a href=\"https://doi.org/10.5061/dryad.f1s76f2\">https://doi.org/10.5061/dryad.f1s76f2</a>.","mla":"Kaucka, Marketa, et al. <i>Data from: Signals from the Brain and Olfactory Epithelium Control Shaping of the Mammalian Nasal Capsule Cartilage</i>. Dryad, 2018, doi:<a href=\"https://doi.org/10.5061/dryad.f1s76f2\">10.5061/dryad.f1s76f2</a>.","ieee":"M. Kaucka <i>et al.</i>, “Data from: Signals from the brain and olfactory epithelium control shaping of the mammalian nasal capsule cartilage.” Dryad, 2018.","short":"M. Kaucka, J. Petersen, M. Tesarova, B. Szarowska, M.E. Kastriti, M. Xie, A. Kicheva, K. Annusver, M. Kasper, O. Symmons, L. Pan, F. Spitz, J. Kaiser, M. Hovorakova, T. Zikmund, K. Sunadome, M.P. Matise, H. Wang, U. Marklund, H. Abdo, P. Ernfors, P. Maire, M. Wurmser, A.S. Chagin, K. Fried, I. Adameyko, (2018).","apa":"Kaucka, M., Petersen, J., Tesarova, M., Szarowska, B., Kastriti, M. E., Xie, M., … Adameyko, I. (2018). Data from: Signals from the brain and olfactory epithelium control shaping of the mammalian nasal capsule cartilage. Dryad. <a href=\"https://doi.org/10.5061/dryad.f1s76f2\">https://doi.org/10.5061/dryad.f1s76f2</a>","ista":"Kaucka M, Petersen J, Tesarova M, Szarowska B, Kastriti ME, Xie M, Kicheva A, Annusver K, Kasper M, Symmons O, Pan L, Spitz F, Kaiser J, Hovorakova M, Zikmund T, Sunadome K, Matise MP, Wang H, Marklund U, Abdo H, Ernfors P, Maire P, Wurmser M, Chagin AS, Fried K, Adameyko I. 2018. Data from: Signals from the brain and olfactory epithelium control shaping of the mammalian nasal capsule cartilage, Dryad, <a href=\"https://doi.org/10.5061/dryad.f1s76f2\">10.5061/dryad.f1s76f2</a>."},"_id":"9838","abstract":[{"lang":"eng","text":"Facial shape is the basis for facial recognition and categorization. Facial features reflect the underlying geometry of the skeletal structures. Here we reveal that cartilaginous nasal capsule (corresponding to upper jaw and face) is shaped by signals generated by neural structures: brain and olfactory epithelium. Brain-derived Sonic Hedgehog (SHH) enables the induction of nasal septum and posterior nasal capsule, whereas the formation of a capsule roof is controlled by signals from the olfactory epithelium. Unexpectedly, the cartilage of the nasal capsule turned out to be important for shaping membranous facial bones during development. This suggests that conserved neurosensory structures could benefit from protection and have evolved signals inducing cranial cartilages encasing them. Experiments with mutant mice revealed that the genomic regulatory regions controlling production of SHH in the nervous system contribute to facial cartilage morphogenesis, which might be a mechanism responsible for the adaptive evolution of animal faces and snouts."}],"oa_version":"Published Version","doi":"10.5061/dryad.f1s76f2","date_published":"2018-06-14T00:00:00Z","related_material":{"record":[{"relation":"used_in_publication","status":"public","id":"162"}]}},{"date_created":"2021-08-09T13:10:02Z","date_updated":"2025-04-15T08:17:50Z","doi":"10.5061/dryad.42n44","_id":"9840","abstract":[{"lang":"eng","text":"Herd immunity, a process in which resistant individuals limit the spread of a pathogen among susceptible hosts has been extensively studied in eukaryotes. Even though bacteria have evolved multiple immune systems against their phage pathogens, herd immunity in bacteria remains unexplored. Here we experimentally demonstrate that herd immunity arises during phage epidemics in structured and unstructured Escherichia coli populations consisting of differing frequencies of susceptible and resistant cells harboring CRISPR immunity. In addition, we develop a mathematical model that quantifies how herd immunity is affected by spatial population structure, bacterial growth rate, and phage replication rate. Using our model we infer a general epidemiological rule describing the relative speed of an epidemic in partially resistant spatially structured populations. Our experimental and theoretical findings indicate that herd immunity may be important in bacterial communities, allowing for stable coexistence of bacteria and their phages and the maintenance of polymorphism in bacterial immunity."}],"citation":{"ista":"Payne P, Geyrhofer L, Barton NH, Bollback JP. 2018. Data from: CRISPR-based herd immunity limits phage epidemics in bacterial populations, Dryad, <a href=\"https://doi.org/10.5061/dryad.42n44\">10.5061/dryad.42n44</a>.","ieee":"P. Payne, L. Geyrhofer, N. H. Barton, and J. P. Bollback, “Data from: CRISPR-based herd immunity limits phage epidemics in bacterial populations.” Dryad, 2018.","mla":"Payne, Pavel, et al. <i>Data from: CRISPR-Based Herd Immunity Limits Phage Epidemics in Bacterial Populations</i>. Dryad, 2018, doi:<a href=\"https://doi.org/10.5061/dryad.42n44\">10.5061/dryad.42n44</a>.","short":"P. Payne, L. Geyrhofer, N.H. Barton, J.P. Bollback, (2018).","apa":"Payne, P., Geyrhofer, L., Barton, N. H., &#38; Bollback, J. P. (2018). Data from: CRISPR-based herd immunity limits phage epidemics in bacterial populations. Dryad. <a href=\"https://doi.org/10.5061/dryad.42n44\">https://doi.org/10.5061/dryad.42n44</a>","ama":"Payne P, Geyrhofer L, Barton NH, Bollback JP. Data from: CRISPR-based herd immunity limits phage epidemics in bacterial populations. 2018. doi:<a href=\"https://doi.org/10.5061/dryad.42n44\">10.5061/dryad.42n44</a>","chicago":"Payne, Pavel, Lukas Geyrhofer, Nicholas H Barton, and Jonathan P Bollback. “Data from: CRISPR-Based Herd Immunity Limits Phage Epidemics in Bacterial Populations.” Dryad, 2018. <a href=\"https://doi.org/10.5061/dryad.42n44\">https://doi.org/10.5061/dryad.42n44</a>."},"oa_version":"Published Version","related_material":{"record":[{"id":"423","relation":"used_in_publication","status":"public"}]},"date_published":"2018-03-12T00:00:00Z","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","article_processing_charge":"No","title":"Data from: CRISPR-based herd immunity limits phage epidemics in bacterial populations","month":"03","type":"research_data_reference","day":"12","oa":1,"year":"2018","publisher":"Dryad","department":[{"_id":"NiBa"},{"_id":"JoBo"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.5061/dryad.42n44"}],"status":"public","author":[{"first_name":"Pavel","orcid":"0000-0002-2711-9453","last_name":"Payne","id":"35F78294-F248-11E8-B48F-1D18A9856A87","full_name":"Payne, Pavel"},{"full_name":"Geyrhofer, Lukas","first_name":"Lukas","last_name":"Geyrhofer"},{"orcid":"0000-0002-8548-5240","last_name":"Barton","first_name":"Nicholas H","full_name":"Barton, Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"},{"id":"2C6FA9CC-F248-11E8-B48F-1D18A9856A87","full_name":"Bollback, Jonathan P","first_name":"Jonathan P","orcid":"0000-0002-4624-4612","last_name":"Bollback"}]},{"date_updated":"2023-09-11T14:10:56Z","date_created":"2021-08-09T13:13:48Z","date_published":"2018-12-12T00:00:00Z","related_material":{"record":[{"id":"448","relation":"used_in_publication","status":"public"}]},"_id":"9841","abstract":[{"lang":"eng","text":"Around 150 million years ago, eusocial termites evolved from within the cockroaches, 50 million years before eusocial Hymenoptera, such as bees and ants, appeared. Here, we report the 2-Gb genome of the German cockroach, Blattella germanica, and the 1.3-Gb genome of the drywood termite Cryptotermes secundus. We show evolutionary signatures of termite eusociality by comparing the genomes and transcriptomes of three termites and the cockroach against the background of 16 other eusocial and non-eusocial insects. Dramatic adaptive changes in genes underlying the production and perception of pheromones confirm the importance of chemical communication in the termites. These are accompanied by major changes in gene regulation and the molecular evolution of caste determination. Many of these results parallel molecular mechanisms of eusocial evolution in Hymenoptera. However, the specific solutions are remarkably different, thus revealing a striking case of convergence in one of the major evolutionary transitions in biological complexity."}],"citation":{"apa":"Harrison, M. C., Jongepier, E., Robertson, H. M., Arning, N., Bitard-Feildel, T., Chao, H., … Bornberg-Bauer, E. (2018). Data from: Hemimetabolous genomes reveal molecular basis of termite eusociality. Dryad. <a href=\"https://doi.org/10.5061/dryad.51d4r\">https://doi.org/10.5061/dryad.51d4r</a>","ieee":"M. C. Harrison <i>et al.</i>, “Data from: Hemimetabolous genomes reveal molecular basis of termite eusociality.” Dryad, 2018.","mla":"Harrison, Mark C., et al. <i>Data from: Hemimetabolous Genomes Reveal Molecular Basis of Termite Eusociality</i>. Dryad, 2018, doi:<a href=\"https://doi.org/10.5061/dryad.51d4r\">10.5061/dryad.51d4r</a>.","short":"M.C. Harrison, E. Jongepier, H.M. Robertson, N. Arning, T. Bitard-Feildel, H. Chao, C.P. Childers, H. Dinh, H. Doddapaneni, S. Dugan, J. Gowin, C. Greiner, Y. Han, H. Hu, D.S.T. Hughes, A.K. Huylmans, C. Kemena, L.P.M. Kremer, S.L. Lee, A. Lopez-Ezquerra, L. Mallet, J.M. Monroy-Kuhn, A. Moser, S.C. Murali, D.M. Muzny, S. Otani, M.-D. Piulachs, M. Poelchau, J. Qu, F. Schaub, A. Wada-Katsumata, K.C. Worley, Q. Xie, G. Ylla, M. Poulsen, R.A. Gibbs, C. Schal, S. Richards, X. Belles, J. Korb, E. Bornberg-Bauer, (2018).","chicago":"Harrison, Mark C., Evelien Jongepier, Hugh M. Robertson, Nicolas Arning, Tristan Bitard-Feildel, Hsu Chao, Christopher P. Childers, et al. “Data from: Hemimetabolous Genomes Reveal Molecular Basis of Termite Eusociality.” Dryad, 2018. <a href=\"https://doi.org/10.5061/dryad.51d4r\">https://doi.org/10.5061/dryad.51d4r</a>.","ama":"Harrison MC, Jongepier E, Robertson HM, et al. Data from: Hemimetabolous genomes reveal molecular basis of termite eusociality. 2018. doi:<a href=\"https://doi.org/10.5061/dryad.51d4r\">10.5061/dryad.51d4r</a>","ista":"Harrison MC, Jongepier E, Robertson HM, Arning N, Bitard-Feildel T, Chao H, Childers CP, Dinh H, Doddapaneni H, Dugan S, Gowin J, Greiner C, Han Y, Hu H, Hughes DST, Huylmans AK, Kemena C, Kremer LPM, Lee SL, Lopez-Ezquerra A, Mallet L, Monroy-Kuhn JM, Moser A, Murali SC, Muzny DM, Otani S, Piulachs M-D, Poelchau M, Qu J, Schaub F, Wada-Katsumata A, Worley KC, Xie Q, Ylla G, Poulsen M, Gibbs RA, Schal C, Richards S, Belles X, Korb J, Bornberg-Bauer E. 2018. Data from: Hemimetabolous genomes reveal molecular basis of termite eusociality, Dryad, <a href=\"https://doi.org/10.5061/dryad.51d4r\">10.5061/dryad.51d4r</a>."},"oa_version":"Published Version","doi":"10.5061/dryad.51d4r","month":"12","article_processing_charge":"No","title":"Data from: Hemimetabolous genomes reveal molecular basis of termite eusociality","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","status":"public","department":[{"_id":"BeVi"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.5061/dryad.51d4r"}],"author":[{"first_name":"Mark C.","last_name":"Harrison","full_name":"Harrison, Mark C."},{"last_name":"Jongepier","first_name":"Evelien","full_name":"Jongepier, Evelien"},{"last_name":"Robertson","first_name":"Hugh M.","full_name":"Robertson, Hugh M."},{"last_name":"Arning","first_name":"Nicolas","full_name":"Arning, Nicolas"},{"full_name":"Bitard-Feildel, Tristan","first_name":"Tristan","last_name":"Bitard-Feildel"},{"last_name":"Chao","first_name":"Hsu","full_name":"Chao, Hsu"},{"full_name":"Childers, Christopher P.","last_name":"Childers","first_name":"Christopher P."},{"full_name":"Dinh, Huyen","first_name":"Huyen","last_name":"Dinh"},{"full_name":"Doddapaneni, Harshavardhan","first_name":"Harshavardhan","last_name":"Doddapaneni"},{"full_name":"Dugan, Shannon","first_name":"Shannon","last_name":"Dugan"},{"last_name":"Gowin","first_name":"Johannes","full_name":"Gowin, Johannes"},{"full_name":"Greiner, Carolin","first_name":"Carolin","last_name":"Greiner"},{"first_name":"Yi","last_name":"Han","full_name":"Han, Yi"},{"full_name":"Hu, Haofu","last_name":"Hu","first_name":"Haofu"},{"last_name":"Hughes","first_name":"Daniel S. T.","full_name":"Hughes, Daniel S. T."},{"last_name":"Huylmans","orcid":"0000-0001-8871-4961","first_name":"Ann K","id":"4C0A3874-F248-11E8-B48F-1D18A9856A87","full_name":"Huylmans, Ann K"},{"last_name":"Kemena","first_name":"Carsten","full_name":"Kemena, Carsten"},{"full_name":"Kremer, Lukas P. M.","last_name":"Kremer","first_name":"Lukas P. M."},{"last_name":"Lee","first_name":"Sandra L.","full_name":"Lee, Sandra L."},{"full_name":"Lopez-Ezquerra, Alberto","first_name":"Alberto","last_name":"Lopez-Ezquerra"},{"full_name":"Mallet, Ludovic","last_name":"Mallet","first_name":"Ludovic"},{"last_name":"Monroy-Kuhn","first_name":"Jose M.","full_name":"Monroy-Kuhn, Jose M."},{"last_name":"Moser","first_name":"Annabell","full_name":"Moser, Annabell"},{"full_name":"Murali, Shwetha C.","first_name":"Shwetha C.","last_name":"Murali"},{"full_name":"Muzny, Donna M.","first_name":"Donna M.","last_name":"Muzny"},{"last_name":"Otani","first_name":"Saria","full_name":"Otani, Saria"},{"full_name":"Piulachs, Maria-Dolors","first_name":"Maria-Dolors","last_name":"Piulachs"},{"first_name":"Monica","last_name":"Poelchau","full_name":"Poelchau, Monica"},{"full_name":"Qu, Jiaxin","first_name":"Jiaxin","last_name":"Qu"},{"full_name":"Schaub, Florentine","last_name":"Schaub","first_name":"Florentine"},{"first_name":"Ayako","last_name":"Wada-Katsumata","full_name":"Wada-Katsumata, Ayako"},{"first_name":"Kim C.","last_name":"Worley","full_name":"Worley, Kim C."},{"full_name":"Xie, Qiaolin","last_name":"Xie","first_name":"Qiaolin"},{"last_name":"Ylla","first_name":"Guillem","full_name":"Ylla, Guillem"},{"full_name":"Poulsen, Michael","last_name":"Poulsen","first_name":"Michael"},{"first_name":"Richard A.","last_name":"Gibbs","full_name":"Gibbs, Richard A."},{"last_name":"Schal","first_name":"Coby","full_name":"Schal, Coby"},{"last_name":"Richards","first_name":"Stephen","full_name":"Richards, Stephen"},{"first_name":"Xavier","last_name":"Belles","full_name":"Belles, Xavier"},{"full_name":"Korb, Judith","first_name":"Judith","last_name":"Korb"},{"full_name":"Bornberg-Bauer, Erich","first_name":"Erich","last_name":"Bornberg-Bauer"}],"year":"2018","publisher":"Dryad","day":"12","oa":1,"type":"research_data_reference"}]