[{"author":[{"full_name":"Pimenta-Marques, Ana","first_name":"Ana","last_name":"Pimenta-Marques"},{"first_name":"Tania","full_name":"Perestrelo, Tania","last_name":"Perestrelo"},{"id":"26E95904-5160-11E9-9C0B-C5B0DC97E90F","first_name":"Patricia","full_name":"Dos Reis Rodrigues, Patricia","orcid":"0000-0003-1681-508X","last_name":"Dos Reis Rodrigues"},{"last_name":"Duarte","full_name":"Duarte, Paulo","first_name":"Paulo"},{"first_name":"Ana","full_name":"Ferreira-Silva, Ana","last_name":"Ferreira-Silva"},{"full_name":"Lince-Faria, Mariana","first_name":"Mariana","last_name":"Lince-Faria"},{"first_name":"Mónica","full_name":"Bettencourt-Dias, Mónica","last_name":"Bettencourt-Dias"}],"year":"2024","page":"102-127","publication_status":"published","scopus_import":"1","quality_controlled":"1","department":[{"_id":"MiSi"}],"article_processing_charge":"Yes (in subscription journal)","file_date_updated":"2024-02-05T12:35:03Z","language":[{"iso":"eng"}],"dataavailabilitystatement":"This study includes no data deposited in external repositories.","_id":"14933","date_published":"2024-01-10T00:00:00Z","issue":"1","citation":{"ista":"Pimenta-Marques A, Perestrelo T, Dos Reis Rodrigues P, Duarte P, Ferreira-Silva A, Lince-Faria M, Bettencourt-Dias M. 2024. Ana1/CEP295 is an essential player in the centrosome maintenance program regulated by Polo kinase and the PCM. EMBO Reports. 25(1), 102–127.","short":"A. Pimenta-Marques, T. Perestrelo, P. Dos Reis Rodrigues, P. Duarte, A. Ferreira-Silva, M. Lince-Faria, M. Bettencourt-Dias, EMBO Reports 25 (2024) 102–127.","ama":"Pimenta-Marques A, Perestrelo T, Dos Reis Rodrigues P, et al. Ana1/CEP295 is an essential player in the centrosome maintenance program regulated by Polo kinase and the PCM. <i>EMBO Reports</i>. 2024;25(1):102-127. doi:<a href=\"https://doi.org/10.1038/s44319-023-00020-6\">10.1038/s44319-023-00020-6</a>","chicago":"Pimenta-Marques, Ana, Tania Perestrelo, Patricia Dos Reis Rodrigues, Paulo Duarte, Ana Ferreira-Silva, Mariana Lince-Faria, and Mónica Bettencourt-Dias. “Ana1/CEP295 Is an Essential Player in the Centrosome Maintenance Program Regulated by Polo Kinase and the PCM.” <i>EMBO Reports</i>. Embo Press, 2024. <a href=\"https://doi.org/10.1038/s44319-023-00020-6\">https://doi.org/10.1038/s44319-023-00020-6</a>.","mla":"Pimenta-Marques, Ana, et al. “Ana1/CEP295 Is an Essential Player in the Centrosome Maintenance Program Regulated by Polo Kinase and the PCM.” <i>EMBO Reports</i>, vol. 25, no. 1, Embo Press, 2024, pp. 102–27, doi:<a href=\"https://doi.org/10.1038/s44319-023-00020-6\">10.1038/s44319-023-00020-6</a>.","ieee":"A. Pimenta-Marques <i>et al.</i>, “Ana1/CEP295 is an essential player in the centrosome maintenance program regulated by Polo kinase and the PCM,” <i>EMBO Reports</i>, vol. 25, no. 1. Embo Press, pp. 102–127, 2024.","apa":"Pimenta-Marques, A., Perestrelo, T., Dos Reis Rodrigues, P., Duarte, P., Ferreira-Silva, A., Lince-Faria, M., &#38; Bettencourt-Dias, M. (2024). Ana1/CEP295 is an essential player in the centrosome maintenance program regulated by Polo kinase and the PCM. <i>EMBO Reports</i>. Embo Press. <a href=\"https://doi.org/10.1038/s44319-023-00020-6\">https://doi.org/10.1038/s44319-023-00020-6</a>"},"abstract":[{"lang":"eng","text":"Centrioles are part of centrosomes and cilia, which are microtubule organising centres (MTOC) with diverse functions. Despite their stability, centrioles can disappear during differentiation, such as in oocytes, but little is known about the regulation of their structural integrity. Our previous research revealed that the pericentriolar material (PCM) that surrounds centrioles and its recruiter, Polo kinase, are downregulated in oogenesis and sufficient for maintaining both centrosome structural integrity and MTOC activity. We now show that the expression of specific components of the centriole cartwheel and wall, including ANA1/CEP295, is essential for maintaining centrosome integrity. We find that Polo kinase requires ANA1 to promote centriole stability in cultured cells and eggs. In addition, ANA1 expression prevents the loss of centrioles observed upon PCM-downregulation. However, the centrioles maintained by overexpressing and tethering ANA1 are inactive, unlike the MTOCs observed upon tethering Polo kinase. These findings demonstrate that several centriole components are needed to maintain centrosome structure. Our study also highlights that centrioles are more dynamic than previously believed, with their structural stability relying on the continuous expression of multiple components."}],"article_type":"original","date_updated":"2026-10-21T08:00:18Z","publication_identifier":{"eissn":["1469-3178"]},"publication":"EMBO Reports","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"das_tickbox":"1","acknowledgement":"We thank all members of the Cell Cycle and Regulation Lab for the discussions and for the critical reading of the manuscript. We thank Tomer Avidor-Reiss (University of Toledo, Toledo, OH), Daniel St. Johnston (The Gurdon Institute, Cambridge, UK), David Glover (University of Cambridge, Cambridge, UK), Jingyan Fu (Agricultural University, Beijing, China) Jordan Raff (University of Oxford, Oxford, UK) and Timothy Megraw (Florida State University, Tallahassee, FL) for sharing tools. We acknowledge the technical support of Instituto Gulbenkian de Ciência (IGC)‘s Advanced Imaging Facility, in particular Gabriel Martins, Nuno Pimpão Martins and José Marques. We also thank Tiago Paixão from the IGC’s Quantitative & Digital Science Unit and Marco Louro from the CCR lab for the support provided on statistical analysis. IGC’s Advanced Imaging Facility (AIF-UIC) is supported by the national Portuguese funding ref# PPBI-POCI-01-0145-FEDER -022122. We thank the IGC’s Fly Facility, supported by CONGENTO (LISBOA-01-0145-FEDER-022170). This work was supported by an ERC grant (ERC-2015-CoG-683258) awarded to MBD and a grant from the Portuguese Research Council (FCT) awarded to APM (PTDC/BIA-BID/32225/2017).","type":"journal_article","volume":25,"oa_version":"Published Version","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"day":"10","ddc":["570"],"doi":"10.1038/s44319-023-00020-6","fulldoi":"https://doi.org/10.1038/s44319-023-00020-6","external_id":{"pmid":["38200359"]},"supplementarymaterial":"yes","has_accepted_license":"1","file":[{"success":1,"content_type":"application/pdf","file_size":9645056,"relation":"main_file","file_name":"2023_EmboReports_PimentaMarques.pdf","file_id":"14941","checksum":"53c3ef43d9bd6d7bff3ffcf57d763cac","access_level":"open_access","creator":"dernst","date_updated":"2024-02-05T12:35:03Z","date_created":"2024-02-05T12:35:03Z"}],"intvolume":"        25","title":"Ana1/CEP295 is an essential player in the centrosome maintenance program regulated by Polo kinase and the PCM","month":"01","researchdata_availability":"not applicable","date_created":"2024-02-04T23:00:53Z","publisher":"Embo Press","status":"public","pmid":1},{"type":"conference","acknowledgement":"This   project   has   received   funding   from   the   Euro-pean  Research  Council  (ERC)  under  the  EuropeanUnion’s  Horizon  2020  research  and  innovation  programme  (Grant  agreement  No.   101019564  “The  De-sign  of  Modern  Fully  Dynamic  Data  Structures  (Mo-DynStruct)”  and  the  Austrian  Science  Fund  (FWF)project Z 422-N, project “Static and Dynamic Hierar-chical  Graph  Decompositions”,  I  5982-N,  and  project“Fast  Algorithms  for  a  Reactive  Network  Layer  (Re-actNet)”, P 33775-N, with additional funding from thenetidee SCIENCE Stiftung, 2020–2024.D.  Sauplic  has  received  funding  from  the  Euro-pean  Union’s  Horizon  2020  research  and  innovation programme under the Marie Sklodowska-Curie    grant    agreementNo 101034413.","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"day":"04","doi":"10.1137/1.9781611977929.17","oa_version":"Preprint","month":"01","ec_funded":1,"project":[{"name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020","grant_number":"101019564"},{"grant_number":"Z00422","name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"},{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020","grant_number":"101034413"}],"researchdata_availability":"no","fulldoi":"https://doi.org/10.1137/1.9781611977929.17","external_id":{"arxiv":["2310.18034"]},"supplementarymaterial":"no","title":"Experimental evaluation of fully dynamic k-means via coresets","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2310.18034","open_access":"1"}],"date_created":"2024-01-09T16:22:47Z","publisher":"Society for Industrial and Applied Mathematics","status":"public","page":"220-233","author":[{"last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"},{"full_name":"Saulpic, David","id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964","first_name":"David","last_name":"Saulpic"},{"last_name":"Sidl","full_name":"Sidl, Leonhard","id":"8b563fd0-b441-11ee-9101-a3891c61efa6","first_name":"Leonhard"}],"year":"2024","conference":{"name":"ALENEX: Workshop on Algorithm Engineering and Experiments","location":"Alexandria, VA, United States","start_date":"2024-01-07","end_date":"2024-01-08"},"scopus_import":"1","quality_controlled":"1","article_processing_charge":"No","department":[{"_id":"MoHe"}],"publication_status":"published","arxiv":1,"date_published":"2024-01-04T00:00:00Z","language":[{"iso":"eng"}],"_id":"14769","publication":"2024 Proceedings of the Symposium on Algorithm Engineering and Experiments","das_tickbox":"0","corr_author":"1","citation":{"ista":"Henzinger M, Saulpic D, Sidl L. 2024. Experimental evaluation of fully dynamic k-means via coresets. 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments. ALENEX: Workshop on Algorithm Engineering and Experiments, 220–233.","short":"M. Henzinger, D. Saulpic, L. Sidl, in:, 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2024, pp. 220–233.","ama":"Henzinger M, Saulpic D, Sidl L. Experimental evaluation of fully dynamic k-means via coresets. In: <i>2024 Proceedings of the Symposium on Algorithm Engineering and Experiments</i>. Society for Industrial and Applied Mathematics; 2024:220-233. doi:<a href=\"https://doi.org/10.1137/1.9781611977929.17\">10.1137/1.9781611977929.17</a>","chicago":"Henzinger, Monika, David Saulpic, and Leonhard Sidl. “Experimental Evaluation of Fully Dynamic K-Means via Coresets.” In <i>2024 Proceedings of the Symposium on Algorithm Engineering and Experiments</i>, 220–33. Society for Industrial and Applied Mathematics, 2024. <a href=\"https://doi.org/10.1137/1.9781611977929.17\">https://doi.org/10.1137/1.9781611977929.17</a>.","mla":"Henzinger, Monika, et al. “Experimental Evaluation of Fully Dynamic K-Means via Coresets.” <i>2024 Proceedings of the Symposium on Algorithm Engineering and Experiments</i>, Society for Industrial and Applied Mathematics, 2024, pp. 220–33, doi:<a href=\"https://doi.org/10.1137/1.9781611977929.17\">10.1137/1.9781611977929.17</a>.","ieee":"M. Henzinger, D. Saulpic, and L. Sidl, “Experimental evaluation of fully dynamic k-means via coresets,” in <i>2024 Proceedings of the Symposium on Algorithm Engineering and Experiments</i>, Alexandria, VA, United States, 2024, pp. 220–233.","apa":"Henzinger, M., Saulpic, D., &#38; Sidl, L. (2024). Experimental evaluation of fully dynamic k-means via coresets. In <i>2024 Proceedings of the Symposium on Algorithm Engineering and Experiments</i> (pp. 220–233). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977929.17\">https://doi.org/10.1137/1.9781611977929.17</a>"},"abstract":[{"lang":"eng","text":"For a set of points in Rd, the Euclidean k-means problems consists of finding k centers such that the sum of distances squared from each data point to its closest center is minimized. Coresets are one the main tools developed recently to solve this problem in a big data context. They allow to compress the initial dataset while preserving its structure: running any algorithm on the coreset provides a guarantee almost equivalent to running it on the full data. In this work, we study coresets in a fully-dynamic setting: points are added and deleted with the goal to efficiently maintain a coreset with which a k-means solution can be computed. Based on an algorithm from Henzinger and Kale [ESA'20], we present an efficient and practical implementation of a fully dynamic coreset algorithm, that improves the running time by up to a factor of 20 compared to our non-optimized implementation of the algorithm by Henzinger and Kale, without sacrificing more than 7% on the quality of the k-means solution."}],"date_updated":"2026-10-21T08:02:15Z","publication_identifier":{"eisbn":["9781611977929"]}},{"language":[{"iso":"eng"}],"_id":"17279","date_published":"2024-07-18T00:00:00Z","abstract":[{"text":"In a recent issue of Cell, Zhang et al.1 demonstrate that mechanical features of a solid tumor can drive T cells into dysfunctionality and identify pathways that revert this “exhausted” state.","lang":"eng"}],"article_type":"review","citation":{"mla":"Avellaneda Sarrió, Mario, and Michael K. Sixt. “Rescuing T Cells from Stiff Tumors.” <i>Cell Chemical Biology</i>, vol. 31, no. 7, Elsevier, 2024, pp. 1242–43, doi:<a href=\"https://doi.org/10.1016/j.chembiol.2024.06.011\">10.1016/j.chembiol.2024.06.011</a>.","apa":"Avellaneda Sarrió, M., &#38; Sixt, M. K. (2024). Rescuing T cells from stiff tumors. <i>Cell Chemical Biology</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.chembiol.2024.06.011\">https://doi.org/10.1016/j.chembiol.2024.06.011</a>","ieee":"M. Avellaneda Sarrió and M. K. Sixt, “Rescuing T cells from stiff tumors,” <i>Cell Chemical Biology</i>, vol. 31, no. 7. Elsevier, pp. 1242–1243, 2024.","chicago":"Avellaneda Sarrió, Mario, and Michael K Sixt. “Rescuing T Cells from Stiff Tumors.” <i>Cell Chemical Biology</i>. Elsevier, 2024. <a href=\"https://doi.org/10.1016/j.chembiol.2024.06.011\">https://doi.org/10.1016/j.chembiol.2024.06.011</a>.","ista":"Avellaneda Sarrió M, Sixt MK. 2024. Rescuing T cells from stiff tumors. Cell Chemical Biology. 31(7), 1242–1243.","short":"M. Avellaneda Sarrió, M.K. Sixt, Cell Chemical Biology 31 (2024) 1242–1243.","ama":"Avellaneda Sarrió M, Sixt MK. Rescuing T cells from stiff tumors. <i>Cell Chemical Biology</i>. 2024;31(7):1242-1243. doi:<a href=\"https://doi.org/10.1016/j.chembiol.2024.06.011\">10.1016/j.chembiol.2024.06.011</a>"},"corr_author":"1","date_updated":"2026-10-21T07:58:00Z","publication_identifier":{"issn":["2451-9456"],"eissn":["2451-9448"]},"issue":"7","das_tickbox":"0","publication":"Cell Chemical Biology","year":"2024","author":[{"last_name":"Avellaneda Sarrió","orcid":"0000-0001-6406-524X","first_name":"Mario","id":"DC4BA84C-56E6-11EA-AD5D-348C3DDC885E","full_name":"Avellaneda Sarrió, Mario"},{"last_name":"Sixt","orcid":"0000-0002-6620-9179","id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","first_name":"Michael K","full_name":"Sixt, Michael K"}],"page":"1242-1243","publication_status":"published","department":[{"_id":"MiSi"}],"article_processing_charge":"No","scopus_import":"1","quality_controlled":"1","intvolume":"        31","title":"Rescuing T cells from stiff tumors","fulldoi":"https://doi.org/10.1016/j.chembiol.2024.06.011","external_id":{"isi":["001275725000001"],"pmid":["39029454"]},"supplementarymaterial":"no","researchdata_availability":"no","month":"07","status":"public","date_created":"2024-07-21T22:01:00Z","isi":1,"publisher":"Elsevier","pmid":1,"type":"journal_article","volume":31,"oa_version":"None","doi":"10.1016/j.chembiol.2024.06.011","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","day":"18"},{"oa_version":"Published Version","volume":319,"doi":"10.4230/LIPIcs.DISC.2024.21","ddc":["000"],"day":"24","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"acknowledgement":"Antoine El-Hayek: This project has received funding from the Austrian Science Fund\r\n(FWF) grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung,\r\n2020–2024.\r\nMonika Henzinger: This project has received funding from the European Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation programme (MoDynStruct,\r\nNo. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI\r\n10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE\r\nStiftung, 2020–2024.\r\nStefan Schmid: This project has received funding from the German Research Foundation (DFG),\r\nSPP 2378 (project ReNO), 2023-2027.","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"22281"}]},"type":"conference","status":"public","isi":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_created":"2024-11-17T23:01:47Z","title":"Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges","intvolume":"       319","file":[{"file_id":"18561","checksum":"d6c8277331cafa188c33ba1717206cf4","access_level":"open_access","date_updated":"2024-11-18T08:02:45Z","creator":"dernst","date_created":"2024-11-18T08:02:45Z","success":1,"content_type":"application/pdf","file_size":809666,"relation":"main_file","file_name":"2024_LIPIcs_ElHayek.pdf"}],"external_id":{"arxiv":["2302.11988"],"isi":["001542467600021"]},"fulldoi":"https://doi.org/10.4230/LIPIcs.DISC.2024.21","supplementarymaterial":"no","has_accepted_license":"1","researchdata_availability":"no","project":[{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"},{"name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms","grant_number":"Z00422"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"ec_funded":1,"month":"10","publication_status":"published","file_date_updated":"2024-11-18T08:02:45Z","department":[{"_id":"MoHe"}],"article_processing_charge":"Yes","scopus_import":"1","quality_controlled":"1","conference":{"name":"DISC: Symposium on Distributed Computing","location":"Madrid, Spain","start_date":"2024-10-28","end_date":"2024-11-01"},"article_number":"21","year":"2024","alternative_title":["LIPIcs"],"OA_type":"gold","author":[{"id":"888a098e-fcac-11ee-aff7-d347be57b725","first_name":"Antoine","full_name":"El-Hayek, Antoine","last_name":"El-Hayek","orcid":"0000-0003-4268-7368"},{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Schmid, Stefan","first_name":"Stefan","last_name":"Schmid"}],"OA_place":"publisher","date_updated":"2026-10-21T08:05:36Z","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773522"]},"abstract":[{"text":"Broadcast and Consensus are most fundamental tasks in distributed computing. These tasks are particularly challenging in dynamic networks where communication across the network links may be unreliable, e.g., due to mobility or failures. Over the last years, researchers have derived several impossibility results and high time complexity lower bounds for these tasks. Specifically for the setting where in each round of communication the adversary is allowed to choose one rooted tree along which the information is disseminated, there is a lower as well as an upper bound that is linear in the number n of nodes for Broadcast and for n ≥ 3 the adversary can guarantee that Consensus never happens. This setting is called the oblivious message adversary for rooted trees. Also note that if the adversary is allowed to choose a graph that does not contain a rooted tree, then it can guarantee that Broadcast and Consensus will never happen. However, such deterministic adversarial models may be overly pessimistic, as many processes in real-world settings are stochastic in nature rather than worst-case. This paper studies Broadcast on stochastic dynamic networks and shows that the situation is very different to the deterministic case. In particular, we show that if information dissemination occurs along random rooted trees and directed Erdős–Rényi graphs, Broadcast completes in O(log n) rounds of communication with high probability. The fundamental insight in our analysis is that key variables are mutually independent. We then study two adversarial models, (a) one with Byzantine nodes and (b) one where an adversary controls the edges. (a) Our techniques without Byzantine nodes are general enough so that they can be extended to Byzantine nodes. (b) In the spirit of smoothed analysis, we introduce the notion of randomized oblivious message adversary, where in each round, an adversary picks k ≤ 2n/3 edges to appear in the communication network, and then a graph (e.g. rooted tree or directed Erdős–Rényi graph) is chosen uniformly at random among the set of all such graphs that include these edges. We show that Broadcast completes in a finite number of rounds, which is, e.g., O(k+log n) rounds in rooted trees. We then extend these results to All-to-All Broadcast, and Consensus, and give lower bounds that show that most of our upper bounds are tight.","lang":"eng"}],"citation":{"apa":"El-Hayek, A., Henzinger, M., &#38; Schmid, S. (2024). Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. In <i>38th International Symposium on Distributed Computing</i> (Vol. 319). Madrid, Spain: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2024.21\">https://doi.org/10.4230/LIPIcs.DISC.2024.21</a>","ieee":"A. El-Hayek, M. Henzinger, and S. Schmid, “Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges,” in <i>38th International Symposium on Distributed Computing</i>, Madrid, Spain, 2024, vol. 319.","mla":"El-Hayek, Antoine, et al. “Broadcast and Consensus in Stochastic Dynamic Networks with Byzantine Nodes and Adversarial Edges.” <i>38th International Symposium on Distributed Computing</i>, vol. 319, 21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2024.21\">10.4230/LIPIcs.DISC.2024.21</a>.","chicago":"El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Broadcast and Consensus in Stochastic Dynamic Networks with Byzantine Nodes and Adversarial Edges.” In <i>38th International Symposium on Distributed Computing</i>, Vol. 319. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2024.21\">https://doi.org/10.4230/LIPIcs.DISC.2024.21</a>.","short":"A. El-Hayek, M. Henzinger, S. Schmid, in:, 38th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ama":"El-Hayek A, Henzinger M, Schmid S. Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. In: <i>38th International Symposium on Distributed Computing</i>. Vol 319. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2024.21\">10.4230/LIPIcs.DISC.2024.21</a>","ista":"El-Hayek A, Henzinger M, Schmid S. 2024. Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. 38th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 319, 21."},"corr_author":"1","das_tickbox":"0","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"publication":"38th International Symposium on Distributed Computing","_id":"18557","language":[{"iso":"eng"}],"date_published":"2024-10-24T00:00:00Z","arxiv":1},{"arxiv":1,"date_published":"2024-09-16T00:00:00Z","language":[{"iso":"eng"}],"_id":"18156","publication":"International Conference on Approximation Algorithms for Combinatorial Optimization Problems ","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"das_tickbox":"0","abstract":[{"text":"Privately counting distinct elements in a stream is a fundamental data analysis problem with many applications in machine learning. In the turnstile model, Jain et al. [NeurIPS2023] initiated the study of this problem parameterized by the maximum flippancy of any element, i.e., the number of times that the count of an element changes from 0 to above 0 or vice versa. They give an item-level (ε,δ)-differentially private algorithm whose additive error is tight with respect to that parameterization. In this work, we show that a very simple algorithm based on the sparse vector technique achieves a tight additive error for item-level (ε,δ)-differential privacy and item-level ε-differential privacy with regards to a different parameterization, namely the sum of all flippancies. Our second result is a bound which shows that for a large class of algorithms, including all existing differentially private algorithms for this problem, the lower bound from item-level differential privacy extends to event-level differential privacy. This partially answers an open question by Jain et al. [NeurIPS2023].","lang":"eng"}],"corr_author":"1","citation":{"chicago":"Henzinger, Monika, A. R. Sricharan, and Teresa Anna Steiner. “Private Counting of Distinct Elements in the Turnstile Model and Extensions.” In <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i>, Vol. 317. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40\">https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>.","ama":"Henzinger M, Sricharan AR, Steiner TA. Private counting of distinct elements in the turnstile model and extensions. In: <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i>. Vol 317. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40\">10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>","short":"M. Henzinger, A.R. Sricharan, T.A. Steiner, in:, International Conference on Approximation Algorithms for Combinatorial Optimization Problems , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ista":"Henzinger M, Sricharan AR, Steiner TA. 2024. Private counting of distinct elements in the turnstile model and extensions. International Conference on Approximation Algorithms for Combinatorial Optimization Problems . APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems, LIPIcs, vol. 317, 40.","ieee":"M. Henzinger, A. R. Sricharan, and T. A. Steiner, “Private counting of distinct elements in the turnstile model and extensions,” in <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i>, London, United Kingdom, 2024, vol. 317.","apa":"Henzinger, M., Sricharan, A. R., &#38; Steiner, T. A. (2024). Private counting of distinct elements in the turnstile model and extensions. In <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i> (Vol. 317). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40\">https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>","mla":"Henzinger, Monika, et al. “Private Counting of Distinct Elements in the Turnstile Model and Extensions.” <i>International Conference on Approximation Algorithms for Combinatorial Optimization Problems </i>, vol. 317, 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40\">10.4230/LIPIcs.APPROX/RANDOM.2024.40</a>."},"publication_identifier":{"isbn":["9783959773485"],"issn":["1868-8969"]},"date_updated":"2026-10-21T08:04:23Z","author":[{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"last_name":"Sricharan","full_name":"Sricharan, A. R.","first_name":"A. R."},{"first_name":"Teresa Anna","full_name":"Steiner, Teresa Anna","last_name":"Steiner"}],"alternative_title":["LIPIcs"],"year":"2024","article_number":"40","conference":{"name":"APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems","start_date":"2024-08-27","location":"London, United Kingdom","end_date":"2024-08-30"},"scopus_import":"1","quality_controlled":"1","article_processing_charge":"No","department":[{"_id":"MoHe"}],"file_date_updated":"2024-10-01T10:07:14Z","publication_status":"published","month":"09","ec_funded":1,"project":[{"name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020","grant_number":"101019564"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms","grant_number":"Z00422"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982"},{"grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"researchdata_availability":"no","supplementarymaterial":"no","fulldoi":"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40","external_id":{"isi":["001545634500040"],"arxiv":["2408.11637"]},"has_accepted_license":"1","file":[{"success":1,"content_type":"application/pdf","file_size":973917,"file_name":"2024_LIPICs_HenzingerM.pdf","relation":"main_file","file_id":"18166","checksum":"c08b41c896e4d8c69570044808b40e0b","creator":"dernst","date_updated":"2024-10-01T10:07:14Z","access_level":"open_access","date_created":"2024-10-01T10:07:14Z"}],"intvolume":"       317","title":"Private counting of distinct elements in the turnstile model and extensions","date_created":"2024-09-29T22:01:38Z","isi":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","status":"public","type":"conference","acknowledgement":"Monika Henzinger: This project has received funding from the European Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct,No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nTeresa Anna Steiner: Supported by a research grant (VIL51463) from VILLUM FONDEN.","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"day":"16","ddc":["000"],"doi":"10.4230/LIPIcs.APPROX/RANDOM.2024.40","volume":317,"oa_version":"Published Version"},{"month":"09","ec_funded":1,"project":[{"call_identifier":"H2020","grant_number":"101019564","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures"},{"grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"},{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020","grant_number":"101034413"}],"researchdata_availability":"no","fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2024.100","supplementarymaterial":"no","has_accepted_license":"1","external_id":{"arxiv":["2406.19926"],"isi":["001545622400100"]},"file":[{"success":1,"relation":"main_file","file_name":"2024_LIPICs_DuprelaTour.pdf","content_type":"application/pdf","file_size":873561,"checksum":"8e8c0b13049f11bb0133dfac22e32718","file_id":"18454","date_created":"2024-10-21T09:41:48Z","access_level":"open_access","date_updated":"2024-10-21T09:41:48Z","creator":"dernst"}],"intvolume":"       308","title":"Fully dynamic k-means coreset in near-optimal update time","date_created":"2024-10-13T22:01:50Z","isi":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","status":"public","type":"conference","acknowledgement":"Monika Henzinger: This project has received funding from the European Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct Grant agreement No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nDavid Saulpic: Work partially done while at ISTA. Received funding from the European Union’s\r\nHorizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 101034413. This work was partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR).","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"day":"23","doi":"10.4230/LIPIcs.ESA.2024.100","ddc":["000"],"volume":308,"oa_version":"Published Version","arxiv":1,"date_published":"2024-09-23T00:00:00Z","language":[{"iso":"eng"}],"_id":"18308","publication":"32nd Annual European Symposium on Algorithms","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"das_tickbox":"0","abstract":[{"lang":"eng","text":"We study in this paper the problem of maintaining a solution to k-median and k-means clustering in a fully dynamic setting. To do so, we present an algorithm to efficiently maintain a coreset, a compressed version of the dataset, that allows easy computation of a clustering solution at query time. Our coreset algorithm has near-optimal update time of Õ(k) in general metric spaces, which reduces to Õ(d) in the Euclidean space ℝ^d. The query time is O(k²) in general metrics, and O(kd) in ℝ^d. To maintain a constant-factor approximation for k-median and k-means clustering in Euclidean space, this directly leads to an algorithm with update time Õ(d), and query time Õ(kd + k²). To maintain a O(polylog k)-approximation, the query time is reduced to Õ(kd)."}],"citation":{"chicago":"La Tour, Max Dupré, Monika Henzinger, and David Saulpic. “Fully Dynamic K-Means Coreset in near-Optimal Update Time.” In <i>32nd Annual European Symposium on Algorithms</i>, Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.100\">https://doi.org/10.4230/LIPIcs.ESA.2024.100</a>.","ista":"La Tour MD, Henzinger M, Saulpic D. 2024. Fully dynamic k-means coreset in near-optimal update time. 32nd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 308, 100.","ama":"La Tour MD, Henzinger M, Saulpic D. Fully dynamic k-means coreset in near-optimal update time. In: <i>32nd Annual European Symposium on Algorithms</i>. Vol 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.100\">10.4230/LIPIcs.ESA.2024.100</a>","short":"M.D. La Tour, M. Henzinger, D. Saulpic, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","mla":"La Tour, Max Dupré, et al. “Fully Dynamic K-Means Coreset in near-Optimal Update Time.” <i>32nd Annual European Symposium on Algorithms</i>, vol. 308, 100, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.100\">10.4230/LIPIcs.ESA.2024.100</a>.","apa":"La Tour, M. D., Henzinger, M., &#38; Saulpic, D. (2024). Fully dynamic k-means coreset in near-optimal update time. In <i>32nd Annual European Symposium on Algorithms</i> (Vol. 308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.100\">https://doi.org/10.4230/LIPIcs.ESA.2024.100</a>","ieee":"M. D. La Tour, M. Henzinger, and D. Saulpic, “Fully dynamic k-means coreset in near-optimal update time,” in <i>32nd Annual European Symposium on Algorithms</i>, London, United Kingdom, 2024, vol. 308."},"corr_author":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773386"]},"date_updated":"2026-10-21T08:04:40Z","OA_place":"publisher","author":[{"full_name":"La Tour, Max Dupré","first_name":"Max Dupré","last_name":"La Tour"},{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"},{"id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964","first_name":"David","full_name":"Saulpic, David","last_name":"Saulpic"}],"OA_type":"gold","alternative_title":["LIPIcs"],"year":"2024","article_number":"100","conference":{"name":"ESA: European Symposium on Algorithms","start_date":"2024-09-02","location":"London, United Kingdom","end_date":"2024-09-04"},"quality_controlled":"1","scopus_import":"1","article_processing_charge":"Yes","department":[{"_id":"MoHe"}],"file_date_updated":"2024-10-21T09:41:48Z","publication_status":"published"},{"_id":"18309","language":[{"iso":"eng"}],"date_published":"2024-09-01T00:00:00Z","arxiv":1,"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773386"]},"date_updated":"2026-10-21T08:04:56Z","corr_author":"1","citation":{"chicago":"Hu, Bingbing, Evangelos Kosinas, and Adam Polak. “Connectivity Oracles for Predictable Vertex Failures.” In <i>32nd Annual European Symposium on Algorithms</i>, Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.72\">https://doi.org/10.4230/LIPIcs.ESA.2024.72</a>.","short":"B. Hu, E. Kosinas, A. Polak, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","ama":"Hu B, Kosinas E, Polak A. Connectivity oracles for predictable vertex failures. In: <i>32nd Annual European Symposium on Algorithms</i>. Vol 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.72\">10.4230/LIPIcs.ESA.2024.72</a>","ista":"Hu B, Kosinas E, Polak A. 2024. Connectivity oracles for predictable vertex failures. 32nd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 308, 72.","ieee":"B. Hu, E. Kosinas, and A. Polak, “Connectivity oracles for predictable vertex failures,” in <i>32nd Annual European Symposium on Algorithms</i>, London, United Kingdom, 2024, vol. 308.","apa":"Hu, B., Kosinas, E., &#38; Polak, A. (2024). Connectivity oracles for predictable vertex failures. In <i>32nd Annual European Symposium on Algorithms</i> (Vol. 308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.72\">https://doi.org/10.4230/LIPIcs.ESA.2024.72</a>","mla":"Hu, Bingbing, et al. “Connectivity Oracles for Predictable Vertex Failures.” <i>32nd Annual European Symposium on Algorithms</i>, vol. 308, 72, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2024.72\">10.4230/LIPIcs.ESA.2024.72</a>."},"abstract":[{"lang":"eng","text":"The problem of designing connectivity oracles supporting vertex failures is one of the basic data structures problems for undirected graphs. It is already well understood: previous works [Duan-Pettie STOC'10; Long-Saranurak FOCS'22] achieve query time linear in the number of failed vertices, and it is conditionally optimal as long as we require preprocessing time polynomial in the size of the graph and update time polynomial in the number of failed vertices. We revisit this problem in the paradigm of algorithms with predictions: we ask if the query time can be improved if the set of failed vertices can be predicted beforehand up to a small number of errors. More specifically, we design a data structure that, given a graph G = (V,E) and a set of vertices predicted to fail D̂ ⊆ V of size d = |D̂|, preprocesses it in time Õ(d|E|) and then can receive an update given as the symmetric difference between the predicted and the actual set of failed vertices D̂△D = (D̂ ⧵ D) ∪ (D ⧵ D̂) of size η = |D̂△D|, process it in time Õ(η⁴), and after that answer connectivity queries in G ⧵ D in time O(η). Viewed from another perspective, our data structure provides an improvement over the state of the art for the fully dynamic subgraph connectivity problem in the sensitivity setting [Henzinger-Neumann ESA'16]. We argue that the preprocessing time and query time of our data structure are conditionally optimal under standard fine-grained complexity assumptions."}],"das_tickbox":"0","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"publication":"32nd Annual European Symposium on Algorithms","year":"2024","alternative_title":["LIPIcs"],"OA_type":"gold","author":[{"last_name":"Hu","full_name":"Hu, Bingbing","first_name":"Bingbing"},{"last_name":"Kosinas","id":"4c7f9625-dbbc-11ee-9d86-bdcc2db5a949","first_name":"Evangelos","full_name":"Kosinas, Evangelos"},{"last_name":"Polak","first_name":"Adam","full_name":"Polak, Adam"}],"OA_place":"publisher","publication_status":"published","file_date_updated":"2024-10-21T10:03:48Z","article_processing_charge":"Yes","department":[{"_id":"MoHe"}],"quality_controlled":"1","scopus_import":"1","conference":{"location":"London, United Kingdom","start_date":"2024-09-02","name":"ESA: European Symposium on Algorithms","end_date":"2024-09-04"},"article_number":"72","title":"Connectivity oracles for predictable vertex failures","intvolume":"       308","file":[{"content_type":"application/pdf","file_size":853914,"relation":"main_file","file_name":"2024_LIPICs_Hu.pdf","success":1,"access_level":"open_access","date_updated":"2024-10-21T10:03:48Z","creator":"dernst","date_created":"2024-10-21T10:03:48Z","file_id":"18455","checksum":"ab1f2f9161549a8763eda15db40e022c"}],"supplementarymaterial":"no","fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2024.72","external_id":{"isi":["001545622400072"],"arxiv":["2312.08489"]},"has_accepted_license":"1","researchdata_availability":"no","month":"09","status":"public","isi":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_created":"2024-10-13T22:01:50Z","acknowledgement":"Part of this work was done when Evangelos Kosinas was at University of Ioannina and Adam Polak was at Max Planck Institute of Informatics.\r\n","type":"conference","oa_version":"Published Version","volume":308,"ddc":["000"],"doi":"10.4230/LIPIcs.ESA.2024.72","day":"01","oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345"},{"department":[{"_id":"MoHe"}],"article_processing_charge":"No","conference":{"end_date":"2024-07-27","start_date":"2024-07-21","location":"Vienna, Austria","name":"ICML: International Conference on Machine Learning"},"quality_controlled":"1","scopus_import":"1","publication_status":"published","page":"2086-2107","year":"2024","author":[{"last_name":"Axiotis","full_name":"Axiotis, Kyriakos","first_name":"Kyriakos"},{"last_name":"Cohen-Addad","first_name":"Vincent","full_name":"Cohen-Addad, Vincent"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger"},{"first_name":"Sammy","full_name":"Jerome, Sammy","last_name":"Jerome"},{"first_name":"Vahab","full_name":"Mirrokni, Vahab","last_name":"Mirrokni"},{"last_name":"Saulpic","id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964","first_name":"David","full_name":"Saulpic, David"},{"last_name":"Woodruff","full_name":"Woodruff, David P.","first_name":"David P."},{"first_name":"Michael","full_name":"Wunder, Michael","last_name":"Wunder"}],"alternative_title":["PMLR"],"das_tickbox":"0","publication":"Proceedings of the 41st International Conference on Machine Learning","abstract":[{"lang":"eng","text":"We study the data selection problem, whose aim is to select a small representative subset of data that can be used to efficiently train a machine learning model. We present a new data selection approach based on k-means clustering and sensitivity sampling. Assuming access to an embedding representation of the data with respect to which the model loss is Holder continuous, our approach provably allows selecting a set of “typical” k+1/ε2 elements whose average loss corresponds to the average loss of the whole dataset, up to a multiplicative (1±ε)\r\n factor and an additive ελΦk, where Φk represents the k-means cost for the input embeddings and λ is the Holder constant. We furthermore demonstrate the performance and scalability of our approach on fine-tuning foundation models and show that it outperforms state-of-the-art methods. We also show how it can be applied on linear regression, leading to a new sampling strategy that surprisingly matches the performance of leverage score sampling, while being conceptually simpler and more scalable."}],"citation":{"chicago":"Axiotis, Kyriakos, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David P. Woodruff, and Michael Wunder. “Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond.” In <i>Proceedings of the 41st International Conference on Machine Learning</i>, 235:2086–2107. ML Research Press, 2024.","ama":"Axiotis K, Cohen-Addad V, Henzinger M, et al. Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond. In: <i>Proceedings of the 41st International Conference on Machine Learning</i>. Vol 235. ML Research Press; 2024:2086-2107.","short":"K. Axiotis, V. Cohen-Addad, M. Henzinger, S. Jerome, V. Mirrokni, D. Saulpic, D.P. Woodruff, M. Wunder, in:, Proceedings of the 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 2086–2107.","ista":"Axiotis K, Cohen-Addad V, Henzinger M, Jerome S, Mirrokni V, Saulpic D, Woodruff DP, Wunder M. 2024. Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond. Proceedings of the 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 2086–2107.","ieee":"K. Axiotis <i>et al.</i>, “Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond,” in <i>Proceedings of the 41st International Conference on Machine Learning</i>, Vienna, Austria, 2024, vol. 235, pp. 2086–2107.","apa":"Axiotis, K., Cohen-Addad, V., Henzinger, M., Jerome, S., Mirrokni, V., Saulpic, D., … Wunder, M. (2024). Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond. In <i>Proceedings of the 41st International Conference on Machine Learning</i> (Vol. 235, pp. 2086–2107). Vienna, Austria: ML Research Press.","mla":"Axiotis, Kyriakos, et al. “Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond.” <i>Proceedings of the 41st International Conference on Machine Learning</i>, vol. 235, ML Research Press, 2024, pp. 2086–107."},"date_updated":"2026-10-21T08:03:43Z","publication_identifier":{"eissn":["2640-3498"]},"arxiv":1,"date_published":"2024-09-01T00:00:00Z","language":[{"iso":"eng"}],"_id":"18115","ddc":["000"],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"day":"01","volume":235,"oa_version":"Published Version","type":"conference","acknowledgement":"Monika Henzinger: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024. This work was partially done while David Saulpic was at the Institute for Science and Technology, Austria (ISTA). David Sauplic has received funding from the European Union’s Horizon 2020 research and innovation programme under the\r\nMarie Sklodowska-Curie grant agreement No 101034413. Work was done while David Woodruff was visiting Google Research.","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2402.17327"}],"status":"public","date_created":"2024-09-22T22:01:44Z","publisher":"ML Research Press","researchdata_availability":"no","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","grant_number":"101019564"},{"name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422"},{"grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775"},{"name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","call_identifier":"H2020"}],"month":"09","ec_funded":1,"intvolume":"       235","title":"Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond","external_id":{"arxiv":["2402.17327"]},"supplementarymaterial":"no"},{"author":[{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"last_name":"Li","full_name":"Li, Jason","first_name":"Jason"},{"last_name":"Rao","first_name":"Satish","full_name":"Rao, Satish"},{"last_name":"Wang","first_name":"Di","full_name":"Wang, Di"}],"OA_type":"free access","year":"2024","page":"3089-3139","OA_place":"repository","publication_status":"published","conference":{"start_date":"2024-01-07","location":"Alexandria, VA,  United States","name":"SODA: Symposium on Discrete Algorithms","end_date":"2024-01-10"},"quality_controlled":"1","scopus_import":"1","department":[{"_id":"MoHe"}],"article_processing_charge":"No","language":[{"iso":"eng"}],"_id":"18503","arxiv":1,"date_published":"2024-01-04T00:00:00Z","abstract":[{"text":"In 1996, Karger [Kar96] gave a startling randomized algorithm that finds a minimum-cut in a (weighted) graph in time O(m log3 n) which he termed near-linear time meaning linear (in the size of the input) times a polylogarthmic factor. In this paper, we give the first deterministic algorithm which runs in near-linear time for weighted graphs.\r\nPreviously, the breakthrough results of Kawarabayashi and Thorup [KT19] gave a near-linear time algorithm for simple graphs (which was improved to have running time O(m log2 n log log n) in [HRW20].) The main technique here is a clustering procedure that perfectly preserves minimum cuts. Recently, Li [Li21] gave an m1+o(1) deterministic minimum-cut algorithm for weighted graphs; this form of running time has been termed “almost-linear”. Li uses almost-linear time deterministic expander decompositions which do not perfectly preserve minimum cuts, but he can use these clusterings to, in a sense, “derandomize” the methods of Karger.\r\nIn terms of techniques, we provide a structural theorem that says there exists a sparse clustering that preserves minimum cuts in a weighted graph with o(1) error. In addition, we construct it deterministically in near linear time. This was done exactly for simple graphs in [KT19, HRW20] and with polylogarithmic error for weighted graphs in [Li21]. Extending the techniques in [KT19, HRW20] to weighted graphs presents significant challenges, and moreover, the algorithm can only polylogarithmically approximately preserve minimum cuts. A remaining challenge is to reduce the polylogarithmic-approximate clusterings to 1 + o(1/ log n)-approximate so that they can be applied recursively as in [Li21] over O(log n) many levels. This is an additional challenge that requires building on properties of tree-packings in the presence of a wide range of edge weights to, for example, find sources for local flow computations which identify minimum cuts that cross clusters.","lang":"eng"}],"corr_author":"1","citation":{"chicago":"Henzinger, Monika, Jason Li, Satish Rao, and Di Wang. “Deterministic Near-Linear Time Minimum Cut in Weighted Graphs.” In <i>35th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 3089–3139. Society for Industrial and Applied Mathematics, 2024. <a href=\"https://doi.org/10.1137/1.9781611977912.111\">https://doi.org/10.1137/1.9781611977912.111</a>.","short":"M. Henzinger, J. Li, S. Rao, D. Wang, in:, 35th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2024, pp. 3089–3139.","ama":"Henzinger M, Li J, Rao S, Wang D. Deterministic near-linear time minimum cut in weighted graphs. In: <i>35th Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2024:3089-3139. doi:<a href=\"https://doi.org/10.1137/1.9781611977912.111\">10.1137/1.9781611977912.111</a>","ista":"Henzinger M, Li J, Rao S, Wang D. 2024. Deterministic near-linear time minimum cut in weighted graphs. 35th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 3089–3139.","apa":"Henzinger, M., Li, J., Rao, S., &#38; Wang, D. (2024). Deterministic near-linear time minimum cut in weighted graphs. In <i>35th Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 3089–3139). Alexandria, VA,  United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977912.111\">https://doi.org/10.1137/1.9781611977912.111</a>","ieee":"M. Henzinger, J. Li, S. Rao, and D. Wang, “Deterministic near-linear time minimum cut in weighted graphs,” in <i>35th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Alexandria, VA,  United States, 2024, pp. 3089–3139.","mla":"Henzinger, Monika, et al. “Deterministic Near-Linear Time Minimum Cut in Weighted Graphs.” <i>35th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2024, pp. 3089–139, doi:<a href=\"https://doi.org/10.1137/1.9781611977912.111\">10.1137/1.9781611977912.111</a>."},"publication_identifier":{"eisbn":["9781611977912"]},"date_updated":"2026-10-21T08:05:18Z","publication":"35th Annual ACM-SIAM Symposium on Discrete Algorithms","das_tickbox":"0","acknowledgement":"This project has received funding from the European Research Council(ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDyn-Struct)” and the Austrian Science Fund (FWF) project Z 422-N, project “Static and Dynamic Hierarchical Graph Decompositions”, I 5982-N, and project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.","type":"conference","oa_version":"Preprint","oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","day":"04","doi":"10.1137/1.9781611977912.111","fulldoi":"https://doi.org/10.1137/1.9781611977912.111","external_id":{"arxiv":["2401.05627"]},"supplementarymaterial":"yes","title":"Deterministic near-linear time minimum cut in weighted graphs","month":"01","ec_funded":1,"researchdata_availability":"no","project":[{"grant_number":"101019564","call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures"},{"name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","grant_number":"Z00422"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775"}],"date_created":"2024-11-04T10:54:21Z","publisher":"Society for Industrial and Applied Mathematics","status":"public","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2401.05627"}]},{"page":"12046-12086","year":"2024","alternative_title":["PMLR"],"author":[{"full_name":"La Tour, Max Dupré","first_name":"Max Dupré","last_name":"La Tour"},{"last_name":"Henzinger","orcid":"0000-0002-5008-6530","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"last_name":"Saulpic","full_name":"Saulpic, David","first_name":"David","id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964"}],"article_processing_charge":"No","department":[{"_id":"MoHe"}],"quality_controlled":"1","scopus_import":"1","conference":{"end_date":"2024-07-27","start_date":"2024-07-21","location":"Vienna, Austria","name":"ICML: International Conference on Machine Learning"},"publication_status":"published","date_published":"2024-09-01T00:00:00Z","arxiv":1,"_id":"18116","language":[{"iso":"eng"}],"das_tickbox":"0","publication":"Proceedings of the 41st International Conference on Machine Learning","publication_identifier":{"eissn":["2640-3498"]},"date_updated":"2026-10-21T08:04:04Z","abstract":[{"lang":"eng","text":"As a staple of data analysis and unsupervised learning, the problem of private clustering has been widely studied, under various privacy models. Centralized differential privacy is the first of them, and the problem has also been studied for the local and the shuffle variation. In each case, the goal is to design an algorithm that computes privately a clustering, with the smallest possible error. The study of each variation gave rise to new algorithm: the landscape of private clustering algorithm is therefore quite intricate. In this paper, we show that a 20 year-old algorithm can be slightly modified to work for any of those models. This provides a unified picture: while matching almost all previously known results, it allows us to improve some of them, and extend to a new privacy model, the continual observation setting, where the input is changing over time and the algorithm must output a new solution at each time step."}],"corr_author":"1","citation":{"ista":"La Tour MD, Henzinger M, Saulpic D. 2024. Making old things new: A unified algorithm for differentially private clustering. Proceedings of the 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 12046–12086.","short":"M.D. La Tour, M. Henzinger, D. Saulpic, in:, Proceedings of the 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 12046–12086.","ama":"La Tour MD, Henzinger M, Saulpic D. Making old things new: A unified algorithm for differentially private clustering. In: <i>Proceedings of the 41st International Conference on Machine Learning</i>. Vol 235. ML Research Press; 2024:12046-12086.","chicago":"La Tour, Max Dupré, Monika Henzinger, and David Saulpic. “Making Old Things New: A Unified Algorithm for Differentially Private Clustering.” In <i>Proceedings of the 41st International Conference on Machine Learning</i>, 235:12046–86. ML Research Press, 2024.","mla":"La Tour, Max Dupré, et al. “Making Old Things New: A Unified Algorithm for Differentially Private Clustering.” <i>Proceedings of the 41st International Conference on Machine Learning</i>, vol. 235, ML Research Press, 2024, pp. 12046–86.","ieee":"M. D. La Tour, M. Henzinger, and D. Saulpic, “Making old things new: A unified algorithm for differentially private clustering,” in <i>Proceedings of the 41st International Conference on Machine Learning</i>, Vienna, Austria, 2024, vol. 235, pp. 12046–12086.","apa":"La Tour, M. D., Henzinger, M., &#38; Saulpic, D. (2024). Making old things new: A unified algorithm for differentially private clustering. In <i>Proceedings of the 41st International Conference on Machine Learning</i> (Vol. 235, pp. 12046–12086). Vienna, Austria: ML Research Press."},"type":"conference","acknowledgement":"Monika Henzinger: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024.This work was partially done while David Saulpic was at the Institute for Science and Technology, Austria (ISTA). David Sauplic has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 101034413.","ddc":["000"],"day":"01","oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa_version":"Published Version","volume":235,"researchdata_availability":"no","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","grant_number":"101019564"},{"grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982"},{"grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer"},{"call_identifier":"H2020","grant_number":"101034413","name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"ec_funded":1,"month":"09","title":"Making old things new: A unified algorithm for differentially private clustering","intvolume":"       235","external_id":{"arxiv":["2406.11649"]},"supplementarymaterial":"no","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2406.11649"}],"status":"public","publisher":"ML Research Press","date_created":"2024-09-22T22:01:44Z"},{"month":"01","ec_funded":1,"researchdata_availability":"no","project":[{"name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","call_identifier":"H2020","grant_number":"101019564"},{"grant_number":"Z00422","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775"}],"external_id":{"arxiv":["2307.08970"]},"fulldoi":"https://doi.org/10.1137/1.9781611977912.38","supplementarymaterial":"no","intvolume":"      2024","title":"A unifying framework for differentially private sums under continual observation","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2307.08970","open_access":"1"}],"date_created":"2024-03-31T22:01:13Z","publisher":"Society for Industrial and Applied Mathematics","status":"public","type":"conference","acknowledgement":"This  project  has  received  funding  from  the  European  Research  Council  (ERC)under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No.101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and the AustrianScience Fund (FWF) project Z 422-N, project “Static and Dynamic Hierarchical Graph Decompositions”, I 5982-N, andproject “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the netideeSCIENCE  Stiftung,  2020–2024.   JU’s  research  was  funded  by  the  Decanal  Research  Grant.   We  thank  the  anonymousreviewers for their useful feedback and pointing us to the results in Matousek et al","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"day":"04","doi":"10.1137/1.9781611977912.38","volume":2024,"oa_version":"Preprint","arxiv":1,"date_published":"2024-01-04T00:00:00Z","language":[{"iso":"eng"}],"_id":"15253","publication":"Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms","das_tickbox":"0","citation":{"mla":"Henzinger, Monika, et al. “A Unifying Framework for Differentially Private Sums under Continual Observation.” <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, vol. 2024, Society for Industrial and Applied Mathematics, 2024, pp. 995–1018, doi:<a href=\"https://doi.org/10.1137/1.9781611977912.38\">10.1137/1.9781611977912.38</a>.","ieee":"M. Henzinger, J. Upadhyay, and S. Upadhyay, “A unifying framework for differentially private sums under continual observation,” in <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Alexandria, VA, United States, 2024, vol. 2024, pp. 995–1018.","apa":"Henzinger, M., Upadhyay, J., &#38; Upadhyay, S. (2024). A unifying framework for differentially private sums under continual observation. In <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms</i> (Vol. 2024, pp. 995–1018). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611977912.38\">https://doi.org/10.1137/1.9781611977912.38</a>","chicago":"Henzinger, Monika, Jalaj Upadhyay, and Sarvagya Upadhyay. “A Unifying Framework for Differentially Private Sums under Continual Observation.” In <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2024:995–1018. Society for Industrial and Applied Mathematics, 2024. <a href=\"https://doi.org/10.1137/1.9781611977912.38\">https://doi.org/10.1137/1.9781611977912.38</a>.","ista":"Henzinger M, Upadhyay J, Upadhyay S. 2024. A unifying framework for differentially private sums under continual observation. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2024, 995–1018.","short":"M. Henzinger, J. Upadhyay, S. Upadhyay, in:, Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2024, pp. 995–1018.","ama":"Henzinger M, Upadhyay J, Upadhyay S. A unifying framework for differentially private sums under continual observation. In: <i>Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 2024. Society for Industrial and Applied Mathematics; 2024:995-1018. doi:<a href=\"https://doi.org/10.1137/1.9781611977912.38\">10.1137/1.9781611977912.38</a>"},"abstract":[{"text":"We study the problem of maintaining a differentially private decaying sum under continual observation. We give a unifying framework and an efficient algorithm for this problem for any sufficiently smooth function. Our algorithm is the first differentially private algorithm that does not have a multiplicative error for polynomially decaying weights. Our algorithm improves on all prior works on differentially private decaying sums under continual observation and recovers exactly the additive error for the special case of continual counting from Henzinger et al. (SODA 2023) as a corollary.\r\nOur algorithm is a variant of the matrix mechanism whose error depends on the γ2 and γF norm of the underlying matrix. We give a constructive proof for an almost exact upper bound on the γ2 and γF norm and an almost tight lower bound on the γ2 norm for a large class of lower-triangular matrices. This is the first non-trivial lower bound for lower-triangular matrices whose non-zero entries are not all the same. It includes matrices for all continual decaying sums problems, resulting in an upper bound on the additive error of any differentially private decaying sums algorithm under continual observation.\r\nWe also explore some implications of our result in discrepancy theory and operator algebra. Given the importance of the γ2 norm in computer science and the extensive work in mathematics, we believe our result will have further applications.","lang":"eng"}],"corr_author":"1","publication_identifier":{"eisbn":["9781611977912"]},"date_updated":"2026-10-21T08:03:24Z","page":"995-1018","author":[{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Upadhyay","full_name":"Upadhyay, Jalaj","first_name":"Jalaj"},{"first_name":"Sarvagya","full_name":"Upadhyay, Sarvagya","last_name":"Upadhyay"}],"year":"2024","conference":{"end_date":"2024-01-10","name":"SODA: Symposium on Discrete Algorithms","start_date":"2024-01-07","location":"Alexandria, VA, United States"},"scopus_import":"1","quality_controlled":"1","article_processing_charge":"No","department":[{"_id":"MoHe"}],"publication_status":"published"},{"ec_funded":1,"month":"01","project":[{"call_identifier":"H2020","grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"grant_number":"Z00422","name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c"},{"grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"grant_number":"P33775","name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"}],"researchdata_availability":"no","file":[{"file_name":"2024_LIPICs_HenzingerMo.pdf","relation":"main_file","file_size":1084372,"content_type":"application/pdf","success":1,"date_created":"2025-01-27T15:33:24Z","date_updated":"2025-01-27T15:33:24Z","creator":"dernst","access_level":"open_access","checksum":"15085a5b3697a408b92a4a7a27293927","file_id":"18929"}],"has_accepted_license":"1","fulldoi":"https://doi.org/10.4230/LIPIcs.ITCS.2024.62","supplementarymaterial":"no","external_id":{"arxiv":["2307.16771"],"isi":["001300389400062"]},"title":"On the complexity of algorithms with predictions for dynamic graph problems","intvolume":"       287","isi":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_created":"2025-01-27T15:33:42Z","status":"public","type":"conference","acknowledgement":"Henzinger, Monika: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) project Z 422-N, project I 5982-N, and project P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020-2024.\r\nSaha, Barna: This project is partially supported by NSF grants 1652303, 1909046, 2112533, and HDR TRIPODS Phase II grant 2217058.\r\nWe would like to thank Andrea Lincoln for many helpful discussions and insightful comments.","day":"24","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"ddc":["000"],"doi":"10.4230/LIPIcs.ITCS.2024.62","oa_version":"Published Version","volume":287,"date_published":"2024-01-24T00:00:00Z","arxiv":1,"_id":"18928","language":[{"iso":"eng"}],"publication":"15th Innovations in Theoretical Computer Science Conference","das_tickbox":"0","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"publication_identifier":{"isbn":["9783959773096"],"eissn":["1868-8969"]},"date_updated":"2026-10-21T08:07:36Z","abstract":[{"lang":"eng","text":"Algorithms with predictions is a new research direction that leverages machine learned predictions for algorithm design. So far a plethora of recent works have incorporated predictions to improve on worst-case bounds for online problems. In this paper, we initiate the study of complexity of dynamic data structures with predictions, including dynamic graph algorithms. Unlike online algorithms, the goal in dynamic data structures is to maintain the solution efficiently with every update.\r\nWe investigate three natural models of prediction: (1) δ-accurate predictions where each predicted request matches the true request with probability δ, (2) list-accurate predictions where a true request comes from a list of possible requests, and (3) bounded delay predictions where the true requests are a permutation of the predicted requests. We give general reductions among the prediction models, showing that bounded delay is the strongest prediction model, followed by list-accurate, and δ-accurate.\r\nFurther, we identify two broad problem classes based on lower bounds due to the Online Matrix Vector (OMv) conjecture. Specifically, we show that locally correctable dynamic problems have strong conditional lower bounds for list-accurate predictions that are equivalent to the non-prediction setting, unless list-accurate predictions are perfect. Moreover, we show that locally reducible dynamic problems have time complexity that degrades gracefully with the quality of bounded delay predictions. We categorize problems with known OMv lower bounds accordingly and give several upper bounds in the delay model that show that our lower bounds are almost tight.\r\nWe note that concurrent work by v.d.Brand et al. [SODA '24] and Liu and Srinivas [arXiv:2307.08890] independently study dynamic graph algorithms with predictions, but their work is mostly focused on showing upper bounds."}],"corr_author":"1","citation":{"ieee":"M. Henzinger, B. Saha, M. P. Seybold, and C. Ye, “On the complexity of algorithms with predictions for dynamic graph problems,” in <i>15th Innovations in Theoretical Computer Science Conference</i>, Berkeley, CA, United States, 2024, vol. 287, p. 62:1-62:25.","apa":"Henzinger, M., Saha, B., Seybold, M. P., &#38; Ye, C. (2024). On the complexity of algorithms with predictions for dynamic graph problems. In <i>15th Innovations in Theoretical Computer Science Conference</i> (Vol. 287, p. 62:1-62:25). Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.62\">https://doi.org/10.4230/LIPIcs.ITCS.2024.62</a>","mla":"Henzinger, Monika, et al. “On the Complexity of Algorithms with Predictions for Dynamic Graph Problems.” <i>15th Innovations in Theoretical Computer Science Conference</i>, vol. 287, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 62:1-62:25, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.62\">10.4230/LIPIcs.ITCS.2024.62</a>.","short":"M. Henzinger, B. Saha, M.P. Seybold, C. Ye, in:, 15th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 62:1-62:25.","ama":"Henzinger M, Saha B, Seybold MP, Ye C. On the complexity of algorithms with predictions for dynamic graph problems. In: <i>15th Innovations in Theoretical Computer Science Conference</i>. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:62:1-62:25. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.62\">10.4230/LIPIcs.ITCS.2024.62</a>","ista":"Henzinger M, Saha B, Seybold MP, Ye C. 2024. On the complexity of algorithms with predictions for dynamic graph problems. 15th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 287, 62:1-62:25.","chicago":"Henzinger, Monika, Barna Saha, Martin P. Seybold, and Christopher Ye. “On the Complexity of Algorithms with Predictions for Dynamic Graph Problems.” In <i>15th Innovations in Theoretical Computer Science Conference</i>, 287:62:1-62:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.62\">https://doi.org/10.4230/LIPIcs.ITCS.2024.62</a>."},"page":"62:1-62:25","OA_place":"publisher","alternative_title":["LIPIcs"],"OA_type":"gold","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger"},{"full_name":"Saha, Barna","first_name":"Barna","last_name":"Saha"},{"last_name":"Seybold","first_name":"Martin P.","full_name":"Seybold, Martin P."},{"first_name":"Christopher","full_name":"Ye, Christopher","last_name":"Ye"}],"year":"2024","quality_controlled":"1","scopus_import":"1","conference":{"end_date":"2024-02-02","location":"Berkeley, CA, United States","start_date":"2024-01-30","name":"ITCS: Innovations in Theoretical Computer Science"},"file_date_updated":"2025-01-27T15:33:24Z","department":[{"_id":"MoHe"}],"article_processing_charge":"Yes","publication_status":"published"},{"month":"09","researchdata_availability":"no","supplementarymaterial":"yes","fulldoi":"https://doi.org/10.1021/acsphotonics.4c00485","has_accepted_license":"1","external_id":{"isi":["001298164600001"],"pmid":["39310295"],"arxiv":["2408.09811"]},"file":[{"file_size":2664512,"content_type":"application/pdf","relation":"main_file","file_name":"2024_ACSPhotonics_TaboadaGutierrez_.pdf","success":1,"access_level":"open_access","creator":"dernst","date_updated":"2025-01-09T14:01:06Z","date_created":"2025-01-09T14:01:06Z","file_id":"18819","checksum":"bd7e6a138c406e93eaf0a6268fc42bfe"}],"intvolume":"        11","title":"Unveiling the mechanism of phonon-polariton damping in α‑MoO3","pmid":1,"date_created":"2024-09-01T22:01:09Z","isi":1,"publisher":"American Chemical Society","status":"public","type":"journal_article","acknowledgement":"Funding Sources ─ A.I.F.T.-M. and G.Á.-P. acknowledge support through the Severo Ochoa program from the Government of the Principality of Asturias (references PA-21-PF-BP20-117 and PA20-PF-BP19-053, respectively). A.B.K. and J.T.-G. acknowledge support from the Swiss National Science Foundation (grant # 200020_201096). J.M.-S. acknowledges financial support from the Ramón y Cajal Program of the Government of Spain and FSE (RYC2018-026196-I), the Spanish Ministry of Science and Innovation (State Plan for Scientific and Technical Research and Innovation grant number PID2019-110308GA-I00/AEI/10.13039/501100011033) and project PCI2022-132953 funded by MCIN/AEI/10.13039/501100011033 and the EU “NextGenerationEU”/PRTR”. P.A.-G. acknowledges support from the European Research Council under starting grant no. 715496, 2DNANOPTICA and the Spanish Ministry of Science and Innovation (State Plan for Scientific and Technical Research and Innovation grant number PID2019-111156GB-I00). A.Y.N. acknowledges the Spanish Ministry of Science and Innovation (grant PID2020-115221GB-C42) and the Basque Department of Education (grant PIBA-2023-1-0007). M.V. and J.I.M. acknowledge support by Spanish MCIN/AEI/10.13039/501100011033/FEDER, UE under grant PID2022-136784NB and by Asturias FICYT under grant AYUD/2021/51185 with the support of FEDER funds. I.E. acknowledges funding from the Spanish Ministry of Science and Innovation (Grant No. PID2022-142861NA-I00) and the Department of Education, Universities, and Research of the Eusko Jaurlaritza and the University of the Basque Country UPV/EHU (Grant No. IT1527-22). J. Duan acknowledges the support from the Beijing Natural Science Foundation (Grant No. Z240005), and National Natural Science Foundation of China.","oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","day":"01","ddc":["530"],"doi":"10.1021/acsphotonics.4c00485","volume":11,"oa_version":"Published Version","arxiv":1,"date_published":"2024-09-01T00:00:00Z","language":[{"iso":"eng"}],"_id":"17479","publication":"ACS Photonics","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"das_tickbox":"0","issue":"9","article_type":"original","abstract":[{"text":"Phonon polaritons (PhPs), light coupled to lattice vibrations, in the highly anisotropic polar layered material molybdenum trioxide (α-MoO3) are currently the focus of intense research efforts due to their extreme subwavelength field confinement, directional propagation, and unprecedented low losses. Nevertheless, prior research has primarily concentrated on exploiting the squeezing and steering capabilities of α-MoO3 PhPs, without inquiring much into the dominant microscopic mechanism that determines their long lifetimes, which is key for their implementation in nanophotonic applications. This study delves into the fundamental processes that govern PhP damping in α-MoO3 by combining ab initio calculations with scattering-type scanning near-field optical microscopy (s-SNOM) and Fourier transform infrared (FTIR) spectroscopy measurements across a broad temperature range (8–300 K). The remarkable agreement between our theoretical predictions and experimental observations allows us to identify third-order anharmonic phonon–phonon scattering as the main damping mechanism of α-MoO3 PhPs. These findings shed light on the fundamental limits of low-loss PhPs, which is a crucial factor for assessing their implementation into nanophotonic devices.","lang":"eng"}],"citation":{"ieee":"J. Taboada-Gutiérrez <i>et al.</i>, “Unveiling the mechanism of phonon-polariton damping in α‑MoO3,” <i>ACS Photonics</i>, vol. 11, no. 9. American Chemical Society, pp. 3570–3577, 2024.","apa":"Taboada-Gutiérrez, J., Zhou, Y., Tresguerres-Mata, A. I. F., Lanza, C., Martínez-Suárez, A., Álvarez-Pérez, G., … Alonso-González, P. (2024). Unveiling the mechanism of phonon-polariton damping in α‑MoO3. <i>ACS Photonics</i>. American Chemical Society. <a href=\"https://doi.org/10.1021/acsphotonics.4c00485\">https://doi.org/10.1021/acsphotonics.4c00485</a>","mla":"Taboada-Gutiérrez, Javier, et al. “Unveiling the Mechanism of Phonon-Polariton Damping in Α‑MoO3.” <i>ACS Photonics</i>, vol. 11, no. 9, American Chemical Society, 2024, pp. 3570–77, doi:<a href=\"https://doi.org/10.1021/acsphotonics.4c00485\">10.1021/acsphotonics.4c00485</a>.","chicago":"Taboada-Gutiérrez, Javier, Yixi Zhou, Ana I.F. Tresguerres-Mata, Christian Lanza, Abel Martínez-Suárez, Gonzalo Álvarez-Pérez, Jiahua Duan, et al. “Unveiling the Mechanism of Phonon-Polariton Damping in Α‑MoO3.” <i>ACS Photonics</i>. American Chemical Society, 2024. <a href=\"https://doi.org/10.1021/acsphotonics.4c00485\">https://doi.org/10.1021/acsphotonics.4c00485</a>.","ama":"Taboada-Gutiérrez J, Zhou Y, Tresguerres-Mata AIF, et al. Unveiling the mechanism of phonon-polariton damping in α‑MoO3. <i>ACS Photonics</i>. 2024;11(9):3570-3577. doi:<a href=\"https://doi.org/10.1021/acsphotonics.4c00485\">10.1021/acsphotonics.4c00485</a>","short":"J. Taboada-Gutiérrez, Y. Zhou, A.I.F. Tresguerres-Mata, C. Lanza, A. Martínez-Suárez, G. Álvarez-Pérez, J. Duan, J.I. Martín, M. Vélez, I. Prieto Gonzalez, A. Bercher, J. Teyssier, I. Errea, A.Y. Nikitin, J. Martín-Sánchez, A.B. Kuzmenko, P. Alonso-González, ACS Photonics 11 (2024) 3570–3577.","ista":"Taboada-Gutiérrez J, Zhou Y, Tresguerres-Mata AIF, Lanza C, Martínez-Suárez A, Álvarez-Pérez G, Duan J, Martín JI, Vélez M, Prieto Gonzalez I, Bercher A, Teyssier J, Errea I, Nikitin AY, Martín-Sánchez J, Kuzmenko AB, Alonso-González P. 2024. Unveiling the mechanism of phonon-polariton damping in α‑MoO3. ACS Photonics. 11(9), 3570–3577."},"publication_identifier":{"eissn":["2330-4022"]},"date_updated":"2026-10-21T08:08:01Z","page":"3570-3577","OA_place":"publisher","author":[{"last_name":"Taboada-Gutiérrez","full_name":"Taboada-Gutiérrez, Javier","first_name":"Javier"},{"last_name":"Zhou","full_name":"Zhou, Yixi","first_name":"Yixi"},{"last_name":"Tresguerres-Mata","first_name":"Ana I.F.","full_name":"Tresguerres-Mata, Ana I.F."},{"last_name":"Lanza","first_name":"Christian","full_name":"Lanza, Christian"},{"last_name":"Martínez-Suárez","first_name":"Abel","full_name":"Martínez-Suárez, Abel"},{"last_name":"Álvarez-Pérez","full_name":"Álvarez-Pérez, Gonzalo","first_name":"Gonzalo"},{"last_name":"Duan","first_name":"Jiahua","full_name":"Duan, Jiahua"},{"first_name":"José Ignacio","full_name":"Martín, José Ignacio","last_name":"Martín"},{"last_name":"Vélez","full_name":"Vélez, María","first_name":"María"},{"id":"2A307FE2-F248-11E8-B48F-1D18A9856A87","first_name":"Ivan","full_name":"Prieto Gonzalez, Ivan","orcid":"0000-0002-7370-5357","last_name":"Prieto Gonzalez"},{"last_name":"Bercher","full_name":"Bercher, Adrien","first_name":"Adrien"},{"last_name":"Teyssier","first_name":"Jérémie","full_name":"Teyssier, Jérémie"},{"full_name":"Errea, Ion","first_name":"Ion","last_name":"Errea"},{"last_name":"Nikitin","full_name":"Nikitin, Alexey Y.","first_name":"Alexey Y."},{"last_name":"Martín-Sánchez","full_name":"Martín-Sánchez, Javier","first_name":"Javier"},{"first_name":"Alexey B.","full_name":"Kuzmenko, Alexey B.","last_name":"Kuzmenko"},{"last_name":"Alonso-González","first_name":"Pablo","full_name":"Alonso-González, Pablo"}],"OA_type":"hybrid","year":"2024","scopus_import":"1","quality_controlled":"1","department":[{"_id":"NanoFab"}],"article_processing_charge":"No","file_date_updated":"2025-01-09T14:01:06Z","publication_status":"published"},{"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"day":"01","ddc":["000"],"doi":"10.1145/3637528.3671978","oa_version":"Published Version","type":"conference","acknowledgement":"Monika Henzinger: This project has received funding from the European Research\r\nCouncil (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nHarald Räcke, Robin Münk: This project has received funding from the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 498605858 and 470029389.","date_created":"2025-01-27T13:20:26Z","publisher":"ACM","isi":1,"status":"public","month":"09","ec_funded":1,"researchdata_availability":"no","project":[{"call_identifier":"H2020","grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms","grant_number":"Z00422"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982"}],"fulldoi":"https://doi.org/10.1145/3637528.3671978","external_id":{"isi":["001324524201013"]},"has_accepted_license":"1","supplementarymaterial":"yes","file":[{"checksum":"1265d5cf6aa5f94157631651723c4a2b","file_id":"18907","date_created":"2025-01-27T13:25:23Z","creator":"dernst","date_updated":"2025-01-27T13:25:23Z","access_level":"open_access","success":1,"file_name":"2024_ACMKDD_Hanauer.pdf","relation":"main_file","file_size":1450331,"content_type":"application/pdf"}],"title":"Expander hierarchies for normalized cuts on graphs","conference":{"end_date":"2024-08-29","name":"KDD: Knowledge Discovery and Data Mining","location":"Barcelona, Spain","start_date":"2024-08-05"},"quality_controlled":"1","scopus_import":"1","article_processing_charge":"Yes (in subscription journal)","department":[{"_id":"MoHe"}],"file_date_updated":"2025-01-27T13:25:23Z","publication_status":"published","page":"1016-1027","OA_place":"publisher","author":[{"full_name":"Hanauer, Kathrin","first_name":"Kathrin","last_name":"Hanauer"},{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530"},{"last_name":"Münk","full_name":"Münk, Robin","first_name":"Robin"},{"last_name":"Räcke","full_name":"Räcke, Harald","first_name":"Harald"},{"last_name":"Vötsch","first_name":"Maximilian","full_name":"Vötsch, Maximilian"}],"OA_type":"hybrid","year":"2024","publication":"Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"das_tickbox":"0","abstract":[{"text":"Expander decompositions of graphs have significantly advanced the understanding of many classical graph problems and led to numerous fundamental theoretical results. However, their adoption in practice has been hindered due to their inherent intricacies and large hidden factors in their asymptotic running times. Here, we introduce the first practically efficient algorithm for computing expander decompositions and their hierarchies and demonstrate its effectiveness and utility by incorporating it as the core component in a novel solver for the normalized cut graph clustering objective.\r\nOur extensive experiments on a variety of large graphs show that our expander-based algorithm outperforms state-of-the-art solvers for normalized cut with respect to solution quality by a large margin on a variety of graph classes such as citation, e-mail, and social networks or web graphs while remaining competitive in running time.","lang":"eng"}],"citation":{"mla":"Hanauer, Kathrin, et al. “Expander Hierarchies for Normalized Cuts on Graphs.” <i>Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining</i>, ACM, 2024, pp. 1016–27, doi:<a href=\"https://doi.org/10.1145/3637528.3671978\">10.1145/3637528.3671978</a>.","ieee":"K. Hanauer, M. Henzinger, R. Münk, H. Räcke, and M. Vötsch, “Expander hierarchies for normalized cuts on graphs,” in <i>Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining</i>, Barcelona, Spain, 2024, pp. 1016–1027.","apa":"Hanauer, K., Henzinger, M., Münk, R., Räcke, H., &#38; Vötsch, M. (2024). Expander hierarchies for normalized cuts on graphs. In <i>Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining</i> (pp. 1016–1027). Barcelona, Spain: ACM. <a href=\"https://doi.org/10.1145/3637528.3671978\">https://doi.org/10.1145/3637528.3671978</a>","chicago":"Hanauer, Kathrin, Monika Henzinger, Robin Münk, Harald Räcke, and Maximilian Vötsch. “Expander Hierarchies for Normalized Cuts on Graphs.” In <i>Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining</i>, 1016–27. ACM, 2024. <a href=\"https://doi.org/10.1145/3637528.3671978\">https://doi.org/10.1145/3637528.3671978</a>.","ista":"Hanauer K, Henzinger M, Münk R, Räcke H, Vötsch M. 2024. Expander hierarchies for normalized cuts on graphs. Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. KDD: Knowledge Discovery and Data Mining, 1016–1027.","short":"K. Hanauer, M. Henzinger, R. Münk, H. Räcke, M. Vötsch, in:, Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, ACM, 2024, pp. 1016–1027.","ama":"Hanauer K, Henzinger M, Münk R, Räcke H, Vötsch M. Expander hierarchies for normalized cuts on graphs. In: <i>Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining</i>. ACM; 2024:1016-1027. doi:<a href=\"https://doi.org/10.1145/3637528.3671978\">10.1145/3637528.3671978</a>"},"date_updated":"2026-10-21T08:06:58Z","publication_identifier":{"isbn":["9798400704901"]},"date_published":"2024-09-01T00:00:00Z","language":[{"iso":"eng"}],"_id":"18906"},{"acknowledgement":"Hahn gratefully acknowledges the support of GIF grant I-1419-118.4/2017. Hoefer gratefully acknowledges the support of GIF grant I-1419-118.4/2017, DFG Research Unit ADYN (project number 411362735), and DFG grant Ho 3831/9-1 (project number 514505843).","type":"journal_article","oa_version":"Published Version","volume":334,"doi":"10.1016/j.artint.2024.104171","ddc":["000"],"day":"01","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"title":"Delegated online search","intvolume":"       334","file":[{"file_id":"18806","checksum":"f02a56bc7ea88f41fcc68968e4ceddf3","creator":"dernst","date_updated":"2025-01-09T10:45:24Z","access_level":"open_access","date_created":"2025-01-09T10:45:24Z","success":1,"file_size":772226,"content_type":"application/pdf","file_name":"2024_ArtificialIntelligence_Braun.pdf","relation":"main_file"}],"supplementarymaterial":"no","fulldoi":"https://doi.org/10.1016/j.artint.2024.104171","external_id":{"isi":["001260448100001"],"arxiv":["2203.01084"]},"has_accepted_license":"1","researchdata_availability":"not applicable","month":"09","status":"public","publisher":"Elsevier","isi":1,"date_created":"2024-06-30T22:01:05Z","year":"2024","OA_type":"hybrid","author":[{"last_name":"Braun","full_name":"Braun, Pirmin","first_name":"Pirmin"},{"first_name":"Niklas","id":"0a01c7b2-b823-11ed-9928-cc3f874f9ffd","full_name":"Hahn, Niklas","last_name":"Hahn"},{"first_name":"Martin","full_name":"Hoefer, Martin","last_name":"Hoefer"},{"full_name":"Schecker, Conrad","first_name":"Conrad","last_name":"Schecker"}],"OA_place":"publisher","publication_status":"published","file_date_updated":"2025-01-09T10:45:24Z","article_processing_charge":"Yes (in subscription journal)","department":[{"_id":"MoHe"}],"quality_controlled":"1","scopus_import":"1","article_number":"104171","dataavailabilitystatement":"No data was used for the research described in the article.\r\n","_id":"17188","language":[{"iso":"eng"}],"date_published":"2024-09-01T00:00:00Z","arxiv":1,"publication_identifier":{"issn":["0004-3702"]},"date_updated":"2026-10-21T08:06:15Z","article_type":"original","corr_author":"1","citation":{"ista":"Braun P, Hahn N, Hoefer M, Schecker C. 2024. Delegated online search. Artificial Intelligence. 334, 104171.","ama":"Braun P, Hahn N, Hoefer M, Schecker C. Delegated online search. <i>Artificial Intelligence</i>. 2024;334. doi:<a href=\"https://doi.org/10.1016/j.artint.2024.104171\">10.1016/j.artint.2024.104171</a>","short":"P. Braun, N. Hahn, M. Hoefer, C. Schecker, Artificial Intelligence 334 (2024).","chicago":"Braun, Pirmin, Niklas Hahn, Martin Hoefer, and Conrad Schecker. “Delegated Online Search.” <i>Artificial Intelligence</i>. Elsevier, 2024. <a href=\"https://doi.org/10.1016/j.artint.2024.104171\">https://doi.org/10.1016/j.artint.2024.104171</a>.","mla":"Braun, Pirmin, et al. “Delegated Online Search.” <i>Artificial Intelligence</i>, vol. 334, 104171, Elsevier, 2024, doi:<a href=\"https://doi.org/10.1016/j.artint.2024.104171\">10.1016/j.artint.2024.104171</a>.","apa":"Braun, P., Hahn, N., Hoefer, M., &#38; Schecker, C. (2024). Delegated online search. <i>Artificial Intelligence</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.artint.2024.104171\">https://doi.org/10.1016/j.artint.2024.104171</a>","ieee":"P. Braun, N. Hahn, M. Hoefer, and C. Schecker, “Delegated online search,” <i>Artificial Intelligence</i>, vol. 334. Elsevier, 2024."},"abstract":[{"lang":"eng","text":"In a delegation problem, a principal P with commitment power tries to pick one out of 𝑛 options.\r\nEach option is drawn independently from a known distribution. Instead of inspecting the options\r\nherself, P delegates the information acquisition to a rational and self-interested agent A. After\r\ninspection, A proposes one of the options, and P can accept or reject.\r\nDelegation is a classic setting in economic information design with many prominent applications,\r\nbut the computational problems are only poorly understood. In this paper, we study a natural\r\nonline variant of delegation, in which the agent searches through the options in an online fashion.\r\nFor each option, he has to irrevocably decide if he wants to propose the current option or discard\r\nit, before seeing information on the next option(s). How can we design algorithms for P that\r\napproximate the utility of her best option in hindsight?\r\nWe show that in general P can obtain a Θ(1∕𝑛)-approximation and extend this result to ratios\r\nof Θ(𝑘∕𝑛) in case (1) A has a lookahead of 𝑘 rounds, or (2) A can propose up to 𝑘 different\r\noptions. We provide fine-grained bounds independent of 𝑛 based on three parameters. If the ratio\r\nof maximum and minimum utility for A is bounded by a factor 𝛼, we obtain an Ω(loglog 𝛼∕ log 𝛼)-\r\napproximation algorithm, and we show that this is best possible. Additionally, if P cannot\r\ndistinguish options with the same value for herself, we show that ratios polynomial in 1∕𝛼 cannot\r\nbe avoided. If there are at most 𝛽 different utility values for A, we show a Θ(1∕𝛽)-approximation.\r\nIf the utilities of P and A for each option are related by a factor 𝛾, we obtain an Ω(1∕ log 𝛾)-\r\napproximation, where 𝑂(log log 𝛾∕ log 𝛾) is best possible."}],"das_tickbox":"1","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"publication":"Artificial Intelligence"},{"title":"Limits to species' range: The tension between local and global adaptation","intvolume":"        37","file":[{"success":1,"file_size":1194263,"content_type":"application/pdf","relation":"main_file","file_name":"2024_JourEvolutionaryBiology_Barton.pdf","file_id":"17241","checksum":"94e6b68bddf6cadcec29c7f41647359f","access_level":"open_access","creator":"dernst","date_updated":"2024-07-15T09:45:25Z","date_created":"2024-07-15T09:45:25Z"}],"external_id":{"isi":["001225323900001"],"pmid":["38683160"]},"fulldoi":"https://doi.org/10.1093/jeb/voae052","has_accepted_license":"1","supplementarymaterial":"yes","project":[{"_id":"bd6958e0-d553-11ed-ba76-86eba6a76c00","name":"Understanding the evolution of continuous genomes","grant_number":"101055327"}],"researchdata_availability":"yes (supplementary data)","month":"06","status":"public","isi":1,"publisher":"Oxford University Press","date_created":"2024-07-14T22:01:12Z","pmid":1,"acknowledgement":"This work was supported by a grant from the ERC, 101055327, “HaplotypeStructure”. I thank Himani Sachdeva, Michal Hledik, Jitka Polechova, and the reviewers for their helpful comments.","type":"journal_article","oa_version":"Published Version","volume":37,"doi":"10.1093/jeb/voae052","ddc":["570"],"day":"01","oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","dataavailabilitystatement":"All code used to generate the figures is in the accompanying Mathematica notebook.","_id":"17238","language":[{"iso":"eng"}],"date_published":"2024-06-01T00:00:00Z","date_updated":"2026-10-21T08:11:09Z","publication_identifier":{"issn":["1010-061X"],"eissn":["1420-9101"]},"article_type":"review","corr_author":"1","citation":{"chicago":"Barton, Nicholas H. “Limits to Species’ Range: The Tension between Local and Global Adaptation.” <i>Journal of Evolutionary Biology</i>. Oxford University Press, 2024. <a href=\"https://doi.org/10.1093/jeb/voae052\">https://doi.org/10.1093/jeb/voae052</a>.","ista":"Barton NH. 2024. Limits to species’ range: The tension between local and global adaptation. Journal of Evolutionary Biology. 37(6), 605–615.","ama":"Barton NH. Limits to species’ range: The tension between local and global adaptation. <i>Journal of Evolutionary Biology</i>. 2024;37(6):605-615. doi:<a href=\"https://doi.org/10.1093/jeb/voae052\">10.1093/jeb/voae052</a>","short":"N.H. Barton, Journal of Evolutionary Biology 37 (2024) 605–615.","mla":"Barton, Nicholas H. “Limits to Species’ Range: The Tension between Local and Global Adaptation.” <i>Journal of Evolutionary Biology</i>, vol. 37, no. 6, Oxford University Press, 2024, pp. 605–15, doi:<a href=\"https://doi.org/10.1093/jeb/voae052\">10.1093/jeb/voae052</a>.","ieee":"N. H. Barton, “Limits to species’ range: The tension between local and global adaptation,” <i>Journal of Evolutionary Biology</i>, vol. 37, no. 6. Oxford University Press, pp. 605–615, 2024.","apa":"Barton, N. H. (2024). Limits to species’ range: The tension between local and global adaptation. <i>Journal of Evolutionary Biology</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/jeb/voae052\">https://doi.org/10.1093/jeb/voae052</a>"},"abstract":[{"text":"We know that heritable variation is abundant, and that selection causes all but the smallest populations to rapidly shift beyond their original trait distribution. So then, what limits the range of a species? There are physical constraints and also population genetic limits to the effectiveness of selection, ultimately set by population size. Global adaptation, where the same genotype is favoured over the whole range, is most efficient when based on a multitude of weakly selected alleles and is effective even when local demes are small, provided that there is some gene flow. In contrast, local adaptation is sensitive to gene flow and may require alleles with substantial effect. How can populations combine the advantages of large effective size with the ability to specialise into local niches? To what extent does reproductive isolation help resolve this tension? I address these questions using eco-evolutionary models of polygenic adaptation, contrasting discrete demes with continuousspace.","lang":"eng"}],"issue":"6","das_tickbox":"1","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"publication":"Journal of Evolutionary Biology","year":"2024","author":[{"orcid":"0000-0002-8548-5240","last_name":"Barton","full_name":"Barton, Nicholas H","first_name":"Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87"}],"page":"605-615","publication_status":"published","file_date_updated":"2024-07-15T09:45:25Z","article_processing_charge":"Yes (via OA deal)","department":[{"_id":"NiBa"}],"scopus_import":"1","quality_controlled":"1"},{"publication":"Journal of Evolutionary Biology","das_tickbox":"1","issue":"6","abstract":[{"text":"The impact of climate change on populations will be contingent upon their contemporary adaptive evolution. In this study, we investigated the contemporary evolution of 4 populations of the cold-water kelp Laminaria digitata by analyzing their spatial and temporal genomic variations using ddRAD-sequencing. These populations were sampled from the center to the southern margin of its north-eastern Atlantic distribution at 2 time points, spanning at least 2 generations. Through genome scans for local adaptation at a single time point, we identified candidate loci that showed clinal variation correlated with changes in sea surface temperature (SST) along latitudinal gradients. This finding suggests that SST may drive the adaptive response of these kelp populations, although factors such as species’ demographic history should also be considered. Additionally, we performed a simulation approach to distinguish the effect of selection from genetic drift in allele frequency changes over time. This enabled the detection of loci in the southernmost population that exhibited temporal differentiation beyond what would be expected from genetic drift alone: these are candidate loci which could have evolved under selection over time. In contrast, we did not detect any outlier locus based on temporal differentiation in the population from the North Sea, which also displayed low and decreasing levels of genetic diversity. The diverse evolutionary scenarios observed among populations can be attributed to variations in the prevalence of selection relative to genetic drift across different environments. Therefore, our study highlights the potential of temporal genomics to offer valuable insights into the contemporary evolution of marine foundation species facing climate change.","lang":"eng"}],"citation":{"short":"L. Reynes, L. Fouqueau, D. Aurelle, S. Mauger, C. Destombe, M. Valero, Journal of Evolutionary Biology 37 (2024) 677–692.","ama":"Reynes L, Fouqueau L, Aurelle D, Mauger S, Destombe C, Valero M. Temporal genomics help in deciphering neutral and adaptive patterns in the contemporary evolution of kelp populations. <i>Journal of Evolutionary Biology</i>. 2024;37(6):677-692. doi:<a href=\"https://doi.org/10.1093/jeb/voae048\">10.1093/jeb/voae048</a>","ista":"Reynes L, Fouqueau L, Aurelle D, Mauger S, Destombe C, Valero M. 2024. Temporal genomics help in deciphering neutral and adaptive patterns in the contemporary evolution of kelp populations. Journal of Evolutionary Biology. 37(6), 677–692.","chicago":"Reynes, Lauric, Louise Fouqueau, Didier Aurelle, Stephane Mauger, Christophe Destombe, and Myriam Valero. “Temporal Genomics Help in Deciphering Neutral and Adaptive Patterns in the Contemporary Evolution of Kelp Populations.” <i>Journal of Evolutionary Biology</i>. Oxford University Press, 2024. <a href=\"https://doi.org/10.1093/jeb/voae048\">https://doi.org/10.1093/jeb/voae048</a>.","ieee":"L. Reynes, L. Fouqueau, D. Aurelle, S. Mauger, C. Destombe, and M. Valero, “Temporal genomics help in deciphering neutral and adaptive patterns in the contemporary evolution of kelp populations,” <i>Journal of Evolutionary Biology</i>, vol. 37, no. 6. Oxford University Press, pp. 677–692, 2024.","apa":"Reynes, L., Fouqueau, L., Aurelle, D., Mauger, S., Destombe, C., &#38; Valero, M. (2024). Temporal genomics help in deciphering neutral and adaptive patterns in the contemporary evolution of kelp populations. <i>Journal of Evolutionary Biology</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/jeb/voae048\">https://doi.org/10.1093/jeb/voae048</a>","mla":"Reynes, Lauric, et al. “Temporal Genomics Help in Deciphering Neutral and Adaptive Patterns in the Contemporary Evolution of Kelp Populations.” <i>Journal of Evolutionary Biology</i>, vol. 37, no. 6, Oxford University Press, 2024, pp. 677–92, doi:<a href=\"https://doi.org/10.1093/jeb/voae048\">10.1093/jeb/voae048</a>."},"article_type":"original","date_updated":"2026-10-21T08:10:14Z","publication_identifier":{"eissn":["1420-9101"],"issn":["1010-061X"]},"arxiv":1,"date_published":"2024-06-01T00:00:00Z","language":[{"iso":"eng"}],"_id":"17237","dataavailabilitystatement":"Individual high-quality reads (paired-end reads) generated in the present study (fq.gz files) and the filtered vcf file can be accessed via the Dryad repository at https://doi.org/10.5061/dryad.tb2rbp064. Additionally, the scaffolds assembly of the Laminaria digitata genome, utilized for read mapping and produced by Gernot Glöckner, is also available in the same repository. Furthermore, the custom R script developed for identifying temporal outlier SNPs, along with the FST datasets comparing observed and simulated FST between time points, can be found on GitHub at https://doi.org/10.5281/zenodo.10946282.","scopus_import":"1","quality_controlled":"1","article_processing_charge":"No","department":[{"_id":"NiBa"}],"publication_status":"published","page":"677-692","author":[{"first_name":"Lauric","full_name":"Reynes, Lauric","last_name":"Reynes"},{"full_name":"Fouqueau, Louise","first_name":"Louise","id":"1676e173-8143-11ed-8927-fe165216a93f","last_name":"Fouqueau","orcid":"0000-0003-0371-9339"},{"first_name":"Didier","full_name":"Aurelle, Didier","last_name":"Aurelle"},{"first_name":"Stephane","full_name":"Mauger, Stephane","last_name":"Mauger"},{"full_name":"Destombe, Christophe","first_name":"Christophe","last_name":"Destombe"},{"last_name":"Valero","full_name":"Valero, Myriam","first_name":"Myriam"}],"year":"2024","pmid":1,"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2404.14003","open_access":"1"}],"date_created":"2024-07-14T22:01:12Z","publisher":"Oxford University Press","status":"public","month":"06","researchdata_availability":"yes","fulldoi":"https://doi.org/10.1093/jeb/voae048","external_id":{"pmid":["38629140"],"arxiv":["2404.14003"]},"supplementarymaterial":"yes","intvolume":"        37","title":"Temporal genomics help in deciphering neutral and adaptive patterns in the contemporary evolution of kelp populations","oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","day":"01","doi":"10.1093/jeb/voae048","volume":37,"oa_version":"Preprint","type":"journal_article","acknowledgement":"This work was funded by the EU project MARFOR Biodiversa/004/2015. L.F. was additionally funded by the Region Bretagne (ARED 2017 REEALG) and the NOMIS Foundation. The project leading to this publication has received funding from the EC2CO (CNRS) fund and from the European FEDER Fund under project 1166-39417.\r\nThis work is especially dedicated to the memory of Gernot Glöckner who contributed to the sequencing of Laminaria digitata genome and passed away in very recent time. The authors thank the ABiMS platform of the Roscoff biological station (http://abims.sb-roscoff.fr) for providing the HPC resources that contributed to the search results reported in this document. We also acknowledge the staff of the “Cluster de calcul intensif HPC” Platform of the OSU Institut Pythéas (Aix-Marseille Université, INSU-CNRS) for providing the computing facilities.","related_material":{"record":[{"status":"public","id":"22867","relation":"research_data"}]}},{"publication_status":"published","scopus_import":"1","quality_controlled":"1","conference":{"name":"FOCS: Foundations of Computer Science","start_date":"2024-10-27","location":"Chicago, IL, United States","end_date":"2024-10-30"},"article_processing_charge":"No","department":[{"_id":"MoHe"}],"OA_type":"closed access","author":[{"first_name":"Loukas","full_name":"Georgiadis, Loukas","last_name":"Georgiadis"},{"last_name":"Italiano","first_name":"Giuseppe F.","full_name":"Italiano, Giuseppe F."},{"last_name":"Kosinas","full_name":"Kosinas, Evangelos","first_name":"Evangelos","id":"4c7f9625-dbbc-11ee-9d86-bdcc2db5a949"}],"year":"2024","page":"62-85","date_updated":"2026-10-21T08:07:18Z","publication_identifier":{"isbn":["9798331516741"]},"corr_author":"1","abstract":[{"text":"Let G be a directed graph with m edges and n vertices. We present a deterministic linear-time algorithm for computing the 3-edge-connected components of G. This is a significant improvement over the previous best bound by Georgiadis et al. [SODA 2023], which is Õ(m√{m}) and randomized. Our result is based on a novel characterization of 2-edge cuts in directed graphs and on a new technique that exploits the concept of divergent spanning trees and 2-connectivity-light graphs, and requires a careful modification of the minset-poset technique of Gabow [TALG 2016]. As a side result, our new technique yields also an oracle for providing in constant time a minimum edge-cut for any two vertices that are not 3-edge-connected. The oracle uses space O(n) and can be built in O(mlog n) time: given two query vertices, it determines in constant time whether they are 3-edge-connected, or provides a k-edge cut, with k≤ 2, that separates them.","lang":"eng"}],"citation":{"ista":"Georgiadis L, Italiano GF, Kosinas E. 2024. Computing the 3-edge-connected components of directed graphs in linear time. 65th Annual Symposium on Foundations of Computer Science. FOCS: Foundations of Computer Science, 62–85.","ama":"Georgiadis L, Italiano GF, Kosinas E. Computing the 3-edge-connected components of directed graphs in linear time. In: <i>65th Annual Symposium on Foundations of Computer Science</i>. IEEE; 2024:62-85. doi:<a href=\"https://doi.org/10.1109/focs61266.2024.00015\">10.1109/focs61266.2024.00015</a>","short":"L. Georgiadis, G.F. Italiano, E. Kosinas, in:, 65th Annual Symposium on Foundations of Computer Science, IEEE, 2024, pp. 62–85.","chicago":"Georgiadis, Loukas, Giuseppe F. Italiano, and Evangelos Kosinas. “Computing the 3-Edge-Connected Components of Directed Graphs in Linear Time.” In <i>65th Annual Symposium on Foundations of Computer Science</i>, 62–85. IEEE, 2024. <a href=\"https://doi.org/10.1109/focs61266.2024.00015\">https://doi.org/10.1109/focs61266.2024.00015</a>.","mla":"Georgiadis, Loukas, et al. “Computing the 3-Edge-Connected Components of Directed Graphs in Linear Time.” <i>65th Annual Symposium on Foundations of Computer Science</i>, IEEE, 2024, pp. 62–85, doi:<a href=\"https://doi.org/10.1109/focs61266.2024.00015\">10.1109/focs61266.2024.00015</a>.","ieee":"L. Georgiadis, G. F. Italiano, and E. Kosinas, “Computing the 3-edge-connected components of directed graphs in linear time,” in <i>65th Annual Symposium on Foundations of Computer Science</i>, Chicago, IL, United States, 2024, pp. 62–85.","apa":"Georgiadis, L., Italiano, G. F., &#38; Kosinas, E. (2024). Computing the 3-edge-connected components of directed graphs in linear time. In <i>65th Annual Symposium on Foundations of Computer Science</i> (pp. 62–85). Chicago, IL, United States: IEEE. <a href=\"https://doi.org/10.1109/focs61266.2024.00015\">https://doi.org/10.1109/focs61266.2024.00015</a>"},"publication":"65th Annual Symposium on Foundations of Computer Science","das_tickbox":"0","_id":"18922","language":[{"iso":"eng"}],"date_published":"2024-10-01T00:00:00Z","oa_version":"None","day":"01","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","doi":"10.1109/focs61266.2024.00015","acknowledgement":"Giuseppe F. Italiano was partially supported by the Italian Ministry of\r\nUniversity and Reseach under PRIN Project n. 2022TS4Y3N - EXPAND: scalable algorithms for EXPloratory Analyses of heterogeneous and dynamic Networked Data.\r\n","type":"conference","publisher":"IEEE","isi":1,"date_created":"2025-01-27T14:50:23Z","status":"public","external_id":{"isi":["001419526400005"]},"fulldoi":"https://doi.org/10.1109/focs61266.2024.00015","supplementarymaterial":"no","title":"Computing the 3-edge-connected components of directed graphs in linear time","month":"10","researchdata_availability":"no"},{"isi":1,"publisher":"Oxford University Press","date_created":"2024-07-07T22:01:04Z","status":"public","pmid":1,"main_file_link":[{"url":"https://doi.org/10.1093/jeb/voae067","open_access":"1"}],"supplementarymaterial":"no","fulldoi":"https://doi.org/10.1093/jeb/voae067","external_id":{"isi":["001258359900001"],"pmid":["38941551"]},"title":"Eco-evolutionary dynamics in changing environments: Integrating theory with data","intvolume":"        37","month":"06","researchdata_availability":"no","project":[{"_id":"c08d3278-5a5b-11eb-8a69-fdb09b55f4b8","name":"Causes and consequences of population fragmentation","grant_number":"P32896"},{"name":"NOMIS Fellowship Program","_id":"9B861AAC-BA93-11EA-9121-9846C619BF3A"}],"oa_version":"Published Version","volume":37,"day":"28","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa":1,"doi":"10.1093/jeb/voae067","ddc":["570"],"acknowledgement":"This research was funded by the Austrian Science Fund (FWF), project doi: 10.55776/P32896, Institutional Identifier: 501100002428, grant number: P32896 and L.F. acknowledges the support of the NOMIS-ISTA Fellowship Program.\r\nWe would like to thank Nick Barton, Roger Butlin, Stuart Baird, Patrik Nosil, and Jason Sexton for their insightful comments on the earlier drafts, and to John Carchrae for his valuable contribution in refining phrasing and enhancing clarity. For open access purposes, the author has applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission.","type":"journal_article","issue":"6","date_updated":"2026-10-21T08:08:57Z","publication_identifier":{"eissn":["1420-9101"]},"citation":{"mla":"Fouqueau, Louise, and Jitka Polechova. “Eco-Evolutionary Dynamics in Changing Environments: Integrating Theory with Data.” <i>Journal of Evolutionary Biology</i>, vol. 37, no. 6, Oxford University Press, 2024, pp. 579–87, doi:<a href=\"https://doi.org/10.1093/jeb/voae067\">10.1093/jeb/voae067</a>.","apa":"Fouqueau, L., &#38; Polechova, J. (2024). Eco-evolutionary dynamics in changing environments: Integrating theory with data. <i>Journal of Evolutionary Biology</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/jeb/voae067\">https://doi.org/10.1093/jeb/voae067</a>","ieee":"L. Fouqueau and J. Polechova, “Eco-evolutionary dynamics in changing environments: Integrating theory with data,” <i>Journal of evolutionary biology</i>, vol. 37, no. 6. Oxford University Press, pp. 579–587, 2024.","chicago":"Fouqueau, Louise, and Jitka Polechova. “Eco-Evolutionary Dynamics in Changing Environments: Integrating Theory with Data.” <i>Journal of Evolutionary Biology</i>. Oxford University Press, 2024. <a href=\"https://doi.org/10.1093/jeb/voae067\">https://doi.org/10.1093/jeb/voae067</a>.","ista":"Fouqueau L, Polechova J. 2024. Eco-evolutionary dynamics in changing environments: Integrating theory with data. Journal of evolutionary biology. 37(6), 579–587.","short":"L. Fouqueau, J. Polechova, Journal of Evolutionary Biology 37 (2024) 579–587.","ama":"Fouqueau L, Polechova J. Eco-evolutionary dynamics in changing environments: Integrating theory with data. <i>Journal of evolutionary biology</i>. 2024;37(6):579-587. doi:<a href=\"https://doi.org/10.1093/jeb/voae067\">10.1093/jeb/voae067</a>"},"article_type":"letter_note","publication":"Journal of evolutionary biology","das_tickbox":"0","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"_id":"17207","language":[{"iso":"eng"}],"date_published":"2024-06-28T00:00:00Z","publication_status":"published","scopus_import":"1","quality_controlled":"1","article_processing_charge":"No","department":[{"_id":"NiBa"}],"author":[{"full_name":"Fouqueau, Louise","first_name":"Louise","id":"1676e173-8143-11ed-8927-fe165216a93f","orcid":"0000-0003-0371-9339","last_name":"Fouqueau"},{"full_name":"Polechova, Jitka","id":"3BBFB084-F248-11E8-B48F-1D18A9856A87","first_name":"Jitka","orcid":"0000-0003-0951-3112","last_name":"Polechova"}],"year":"2024","page":"579-587"},{"file_date_updated":"2024-09-11T07:14:03Z","article_processing_charge":"Yes (via OA deal)","department":[{"_id":"NiBa"}],"scopus_import":"1","quality_controlled":"1","article_number":"172","publication_status":"published","year":"2024","author":[{"last_name":"Pocull Belles","full_name":"Pocull Belles, Guillem","first_name":"Guillem","id":"54359172-700c-11ef-a103-c1d91ceac6d6"},{"full_name":"Baskett, Carina","id":"3B4A7CE2-F248-11E8-B48F-1D18A9856A87","first_name":"Carina","last_name":"Baskett","orcid":"0000-0002-7354-8574"},{"full_name":"Barton, Nicholas H","first_name":"Nicholas H","id":"4880FE40-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8548-5240","last_name":"Barton"}],"das_tickbox":"1","tmp":{"image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"publication":"Landscape Ecology","publication_identifier":{"eissn":["1572-9761"],"issn":["0921-2973"]},"date_updated":"2026-10-21T08:12:11Z","corr_author":"1","citation":{"ama":"Pocull Belles G, Baskett C, Barton NH. Multiscale spatial analysis of two plant–insect interactions: Effects of landscape, resource distribution, and other insects. <i>Landscape Ecology</i>. 2024;39(9). doi:<a href=\"https://doi.org/10.1007/s10980-024-01899-9\">10.1007/s10980-024-01899-9</a>","short":"G. Pocull Belles, C. Baskett, N.H. Barton, Landscape Ecology 39 (2024).","ista":"Pocull Belles G, Baskett C, Barton NH. 2024. Multiscale spatial analysis of two plant–insect interactions: Effects of landscape, resource distribution, and other insects. Landscape Ecology. 39(9), 172.","chicago":"Pocull Belles, Guillem, Carina Baskett, and Nicholas H Barton. “Multiscale Spatial Analysis of Two Plant–Insect Interactions: Effects of Landscape, Resource Distribution, and Other Insects.” <i>Landscape Ecology</i>. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/s10980-024-01899-9\">https://doi.org/10.1007/s10980-024-01899-9</a>.","ieee":"G. Pocull Belles, C. Baskett, and N. H. Barton, “Multiscale spatial analysis of two plant–insect interactions: Effects of landscape, resource distribution, and other insects,” <i>Landscape Ecology</i>, vol. 39, no. 9. Springer Nature, 2024.","apa":"Pocull Belles, G., Baskett, C., &#38; Barton, N. H. (2024). Multiscale spatial analysis of two plant–insect interactions: Effects of landscape, resource distribution, and other insects. <i>Landscape Ecology</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s10980-024-01899-9\">https://doi.org/10.1007/s10980-024-01899-9</a>","mla":"Pocull Belles, Guillem, et al. “Multiscale Spatial Analysis of Two Plant–Insect Interactions: Effects of Landscape, Resource Distribution, and Other Insects.” <i>Landscape Ecology</i>, vol. 39, no. 9, 172, Springer Nature, 2024, doi:<a href=\"https://doi.org/10.1007/s10980-024-01899-9\">10.1007/s10980-024-01899-9</a>."},"abstract":[{"text":"Context: Biotic resource exploitation is a critical determinant of species’ distributions. However, quantifying resource exploitation patterns through space and time can be difficult, complicating their incorporation in spatial ecology studies. Therefore, understanding the local drivers of spatial patterns of resource exploitation may contribute to better large-scale species distribution models.\r\nObjectives: We investigated (1) how the resource exploitation patterns of two trophic interactions (plant–insect) are explained by insect behaviour, resource aggregation, and potential insect-insect interactions. We also analyzed how (2) resource patch size and (3) resource accessibility in a heterogeneous landscape affected host exploitation patterns.\r\nMethods: We quantified nectar robbing by insects in the genus Bombus (bumblebees) and seed predation by Brachypterolus vestitus larvae (Antirrhinum beetle) on Antirrhinum majus L. (wild snapdragons) in the Pyrenees Mountains, Catalonia, Spain. We tested hypotheses about resource exploitation by integrating spatial analyses at multiple scales.\r\nResults: Both trophic interactions were aggregated, explained by the aggregation of their resource. At some scales, nectar robbing is more aggregated than the resource. Trophic interaction abundance is proportional to resource patch size, following the ideal free distribution model. Landscape features do not explain the locations exploited. Nectar robbing and seed predation occur together more often than expected.\r\nConclusions: Our findings suggest that multiple biotic and ecological spatial factors may simultaneously affect resource exploitation at a local scale. These findings should be considered when developing agricultural projects, management plans and conservation policies.","lang":"eng"}],"article_type":"original","issue":"9","date_published":"2024-09-01T00:00:00Z","_id":"17888","dataavailabilitystatement":"The datasets generated and analysed during the current study will be deposited to the ISTA Research Explorer repository upon manuscript acceptance. Voucher specimens of insects are deposited in the Museo Nacional de Ciencias Naturales, Spain.","language":[{"iso":"eng"}],"doi":"10.1007/s10980-024-01899-9","ddc":["570"],"day":"01","oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa_version":"Published Version","volume":39,"type":"journal_article","acknowledgement":"For the beetle barcoding, we are very thankful to Brent Emerson’s laboratory at the Consejo Superior de Investigaciones Científicas (CSIC) at the Instituto de Productos Naturales y Agrobiología (IPNA) in La Laguna, Tenerife. Many thanks to numerous field assistants, especially Sandra Cuevas Gallego, Beatriz Pablo Carmona, Luís Santos Cid and Alex Fuster, for their assistance in data collection. Finally, we thank Jesús Muñoz, Virgilio Gómez-Rubio, and two anonymous reviewers for comments that greatly improved the quality of the manuscript.\r\nOpen access funding provided by Institute of Science and Technology (IST Austria). CB received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411. NB was funded by the FWF grant “Löwenmaul speciation” P 32166-B32.","status":"public","isi":1,"publisher":"Springer Nature","date_created":"2024-09-08T22:01:11Z","researchdata_availability":"yes","project":[{"grant_number":"754411","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"_id":"05959E1C-7A3F-11EA-A408-12923DDC885E","name":"Snapdragon Speciation","grant_number":"P32166"}],"ec_funded":1,"month":"09","title":"Multiscale spatial analysis of two plant–insect interactions: Effects of landscape, resource distribution, and other insects","intvolume":"        39","file":[{"success":1,"file_name":"2024_LandscapeEcology_Pocull.pdf","relation":"main_file","file_size":1494987,"content_type":"application/pdf","checksum":"2e1cbc320ec1b4447a5a8562a90bcbc3","file_id":"18054","date_created":"2024-09-11T07:14:03Z","creator":"dernst","date_updated":"2024-09-11T07:14:03Z","access_level":"open_access"}],"has_accepted_license":"1","fulldoi":"https://doi.org/10.1007/s10980-024-01899-9","external_id":{"isi":["001304011900001"]},"supplementarymaterial":"yes"}]
