[{"day":"28","publication":"Cell Reports","status":"public","oa_version":"Published Version","date_updated":"2026-10-20T09:19:12Z","date_created":"2024-05-12T22:01:01Z","_id":"15374","oa":1,"project":[{"grant_number":"I03630","call_identifier":"FWF","_id":"26538374-B435-11E9-9278-68D0E5697425","name":"Molecular mechanisms of endocytic cargo recognition in plants"}],"year":"2024","volume":43,"tmp":{"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)","image":"/images/cc_by.png"},"citation":{"mla":"Adamowski, Maciek, et al. “SH3Ps Recruit Auxilin-like Vesicle Uncoating Factors for Clathrin-Mediated Endocytosis.” <i>Cell Reports</i>, vol. 43, no. 5, 114195, Cell Press, 2024, doi:<a href=\"https://doi.org/10.1016/j.celrep.2024.114195\">10.1016/j.celrep.2024.114195</a>.","apa":"Adamowski, M., Randuch, M., Matijevic, I., Narasimhan, M., &#38; Friml, J. (2024). SH3Ps recruit auxilin-like vesicle uncoating factors for clathrin-mediated endocytosis. <i>Cell Reports</i>. Cell Press. <a href=\"https://doi.org/10.1016/j.celrep.2024.114195\">https://doi.org/10.1016/j.celrep.2024.114195</a>","ieee":"M. Adamowski, M. Randuch, I. Matijevic, M. Narasimhan, and J. Friml, “SH3Ps recruit auxilin-like vesicle uncoating factors for clathrin-mediated endocytosis,” <i>Cell Reports</i>, vol. 43, no. 5. Cell Press, 2024.","ista":"Adamowski M, Randuch M, Matijevic I, Narasimhan M, Friml J. 2024. SH3Ps recruit auxilin-like vesicle uncoating factors for clathrin-mediated endocytosis. Cell Reports. 43(5), 114195.","ama":"Adamowski M, Randuch M, Matijevic I, Narasimhan M, Friml J. SH3Ps recruit auxilin-like vesicle uncoating factors for clathrin-mediated endocytosis. <i>Cell Reports</i>. 2024;43(5). doi:<a href=\"https://doi.org/10.1016/j.celrep.2024.114195\">10.1016/j.celrep.2024.114195</a>","chicago":"Adamowski, Maciek, Marek Randuch, Ivana Matijevic, Madhumitha Narasimhan, and Jiří Friml. “SH3Ps Recruit Auxilin-like Vesicle Uncoating Factors for Clathrin-Mediated Endocytosis.” <i>Cell Reports</i>. Cell Press, 2024. <a href=\"https://doi.org/10.1016/j.celrep.2024.114195\">https://doi.org/10.1016/j.celrep.2024.114195</a>.","short":"M. Adamowski, M. Randuch, I. Matijevic, M. Narasimhan, J. Friml, Cell Reports 43 (2024)."},"department":[{"_id":"JiFr"},{"_id":"MaLo"}],"das_tickbox":"1","publication_status":"published","supplementarymaterial":"yes","pmid":1,"publication_identifier":{"eissn":["2211-1247"]},"has_accepted_license":"1","external_id":{"isi":["001240362800001"],"pmid":["38717900"]},"file":[{"success":1,"creator":"dernst","file_size":5698598,"relation":"main_file","checksum":"a06bb85be4fc765c51554d27ee2da802","content_type":"application/pdf","date_updated":"2024-05-13T12:11:22Z","date_created":"2024-05-13T12:11:22Z","file_name":"2024_CellReports_Adamowski.pdf","access_level":"open_access","file_id":"15387"}],"ddc":["580"],"language":[{"iso":"eng"}],"article_type":"original","issue":"5","author":[{"orcid":"0000-0001-6463-5257","id":"45F536D2-F248-11E8-B48F-1D18A9856A87","last_name":"Adamowski","first_name":"Maciek","full_name":"Adamowski, Maciek"},{"id":"6ac4636d-15b2-11ec-abd3-fb8df79972ae","last_name":"Randuch","first_name":"Marek","full_name":"Randuch, Marek"},{"last_name":"Matijevic","id":"83c17ce3-15b2-11ec-abd3-f486545870bd","full_name":"Matijevic, Ivana","first_name":"Ivana"},{"orcid":"0000-0002-8600-0671","last_name":"Narasimhan","id":"44BF24D0-F248-11E8-B48F-1D18A9856A87","full_name":"Narasimhan, Madhumitha","first_name":"Madhumitha"},{"last_name":"Friml","id":"4159519E-F248-11E8-B48F-1D18A9856A87","full_name":"Friml, Jiří","first_name":"Jiří","orcid":"0000-0002-8302-7596"}],"month":"05","researchdata_availability":"upon request","article_number":"114195","type":"journal_article","fulldoi":"https://doi.org/10.1016/j.celrep.2024.114195","isi":1,"abstract":[{"text":"Clathrin-mediated endocytosis (CME) is an essential process of cargo uptake operating in all eukaryotes. In animals and yeast, BAR-SH3 domain proteins, endophilins and amphiphysins, function at the conclusion of CME to recruit factors for vesicle scission and uncoating. Arabidopsis thaliana contains the BAR-SH3 domain proteins SH3P1–SH3P3, but their role is poorly understood. Here, we identify SH3Ps as functional homologs of endophilin/amphiphysin. SH3P1–SH3P3 bind to discrete foci at the plasma membrane (PM), and SH3P2 recruits late to a subset of clathrin-coated pits. The SH3P2 PM recruitment pattern is nearly identical to its interactor, a putative uncoating factor, AUXILIN-LIKE1. Notably, SH3P1–SH3P3 are required for most of AUXILIN-LIKE1 recruitment to the PM. This indicates a plant-specific modification of CME, where BAR-SH3 proteins recruit auxilin-like uncoating factors rather than the uncoating phosphatases, synaptojanins. SH3P1–SH3P3 act redundantly in overall CME with the plant-specific endocytic adaptor TPLATE complex but not due to an SH3 domain in its TASH3 subunit.","lang":"eng"}],"file_date_updated":"2024-05-13T12:11:22Z","corr_author":"1","quality_controlled":"1","doi":"10.1016/j.celrep.2024.114195","article_processing_charge":"Yes","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","acknowledgement":"The authors wish to acknowledge Dr. Daniel van Damme for mRuby3/pDONRP2rP3 and Prof. Qi-Jun Chen for sharing plasmids used for CRISPR-Cas9 mutagenesis. This work was supported by the Austrian Science Fund (FWF): I 3630-B25.","dataavailabilitystatement":"All data reported in this paper will be shared by the lead contact upon request.\r\n\r\nThis paper does not report original code.\r\n\r\nAny additional information required to reanalyze the data reported in this work paper is available from the lead contact upon request.","scopus_import":"1","date_published":"2024-05-28T00:00:00Z","title":"SH3Ps recruit auxilin-like vesicle uncoating factors for clathrin-mediated endocytosis","intvolume":"        43","publisher":"Cell Press"},{"has_accepted_license":"1","pmid":1,"publication_identifier":{"eissn":["2331-8325"]},"supplementarymaterial":"no","das_tickbox":"0","publication_status":"published","language":[{"iso":"eng"}],"article_type":"original","issue":"13","ddc":["570"],"file":[{"creator":"dernst","success":1,"checksum":"c8671c0ad483da6407cb16cc3fef1990","relation":"main_file","file_size":2896048,"date_created":"2024-07-16T06:16:11Z","file_name":"2024_BioProtocol_Li.pdf","date_updated":"2024-07-16T06:16:11Z","content_type":"application/pdf","file_id":"17242","access_level":"open_access"}],"external_id":{"pmid":["39007160"]},"date_updated":"2026-10-21T07:57:41Z","oa":1,"_id":"17233","date_created":"2024-07-14T22:01:11Z","status":"public","oa_version":"Published Version","publication":"Bio-protocol","day":"05","citation":{"ieee":"Z. LI, J. Huard, E. M. Bayer, and V. Wattelet-Boyer, “Versatile cloning strategy for efficient multigene editing in Arabidopsis,” <i>Bio-protocol</i>, vol. 14, no. 13. Bio-Protocol, 2024.","ista":"LI Z, Huard J, Bayer EM, Wattelet-Boyer V. 2024. Versatile cloning strategy for efficient multigene editing in Arabidopsis. Bio-protocol. 14(13), e5029.","ama":"LI Z, Huard J, Bayer EM, Wattelet-Boyer V. Versatile cloning strategy for efficient multigene editing in Arabidopsis. <i>Bio-protocol</i>. 2024;14(13). doi:<a href=\"https://doi.org/10.21769/BioProtoc.5029\">10.21769/BioProtoc.5029</a>","short":"Z. LI, J. Huard, E.M. Bayer, V. Wattelet-Boyer, Bio-Protocol 14 (2024).","chicago":"LI, ZIQIANG, Jennifer Huard, Emmanuelle M. Bayer, and Valérie Wattelet-Boyer. “Versatile Cloning Strategy for Efficient Multigene Editing in Arabidopsis.” <i>Bio-Protocol</i>. Bio-Protocol, 2024. <a href=\"https://doi.org/10.21769/BioProtoc.5029\">https://doi.org/10.21769/BioProtoc.5029</a>.","apa":"LI, Z., Huard, J., Bayer, E. M., &#38; Wattelet-Boyer, V. (2024). Versatile cloning strategy for efficient multigene editing in Arabidopsis. <i>Bio-Protocol</i>. Bio-Protocol. <a href=\"https://doi.org/10.21769/BioProtoc.5029\">https://doi.org/10.21769/BioProtoc.5029</a>","mla":"LI, ZIQIANG, et al. “Versatile Cloning Strategy for Efficient Multigene Editing in Arabidopsis.” <i>Bio-Protocol</i>, vol. 14, no. 13, e5029, Bio-Protocol, 2024, doi:<a href=\"https://doi.org/10.21769/BioProtoc.5029\">10.21769/BioProtoc.5029</a>."},"department":[{"_id":"MiSi"}],"volume":14,"tmp":{"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)","image":"/images/cc_by.png"},"year":"2024","acknowledgement":"This work was supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (project 772103-BRIDGING to E.M.B.).","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","doi":"10.21769/BioProtoc.5029","article_processing_charge":"Yes","quality_controlled":"1","publisher":"Bio-Protocol","date_published":"2024-07-05T00:00:00Z","title":"Versatile cloning strategy for efficient multigene editing in Arabidopsis","intvolume":"        14","scopus_import":"1","researchdata_availability":"no","article_number":"e5029","author":[{"id":"922e68bb-1727-11ee-857c-966e8cc1b6c3","last_name":"Li","first_name":"Ziqiang","full_name":"Li, Ziqiang"},{"last_name":"Huard","full_name":"Huard, Jennifer","first_name":"Jennifer"},{"last_name":"Bayer","first_name":"Emmanuelle M.","full_name":"Bayer, Emmanuelle M."},{"last_name":"Wattelet-Boyer","full_name":"Wattelet-Boyer, Valérie","first_name":"Valérie"}],"month":"07","abstract":[{"lang":"eng","text":"CRISPR-Cas9 technology has become an essential tool for plant genome editing. Recent advancements have significantly improved the ability to target multiple genes simultaneously within the same genetic background through various strategies. Additionally, there has been significant progress in developing methods for inducible or tissue-specific editing. These advancements offer numerous possibilities for tailored genome modifications. Building upon existing research, we have developed an optimized and modular strategy allowing the targeting of several genes simultaneously in combination with the synchronized expression of the Cas9 endonuclease in the egg cell. This system allows significant editing efficiency while avoiding mosaicism. In addition, the versatile system we propose allows adaptation to inducible and/or tissue-specific edition according to the promoter chosen to drive the expression of the Cas9 gene. Here, we describe a step-by-step protocol for generating the binary vector necessary for establishing Arabidopsis edited lines using a versatile cloning strategy that combines Gateway® and Golden Gate technologies. We describe a versatile system that allows the cloning of as many guides as needed to target DNA, which can be multiplexed into a polycistronic gene and combined in the same construct with sequences for the expression of the Cas9 endonuclease. The expression of Cas9 is controlled by selecting from among a collection of promoters, including constitutive, inducible, ubiquitous, or tissue-specific promoters. Only one vector containing the polycistronic gene (tRNA-sgRNA) needs to be constructed. For that, sgRNA (composed of protospacers chosen to target the gene of interest and sgRNA scaffold) is cloned in tandem with the pre-tRNA sequence. Then, a single recombination reaction is required to assemble the promoter, the zCas9 coding sequence, and the tRNA-gRNA polycistronic gene. Each element is cloned in an entry vector and finally assembled according to the Multisite Gateway® Technology. Here, we detail the process to express zCas9 under the control of egg cell promoter fused to enhancer sequence (EC1.2en-EC1.1p) and to simultaneously target two multiple C2 domains and transmembrane region protein genes (MCTP3 and MCTP4, respectively at3g57880 and at1g51570), using one or two sgRNA per gene."}],"file_date_updated":"2024-07-16T06:16:11Z","fulldoi":"https://doi.org/10.21769/BioProtoc.5029","type":"journal_article"},{"oa_version":"None","status":"public","date_created":"2024-06-30T22:01:05Z","_id":"17191","date_updated":"2026-10-21T07:57:17Z","day":"21","publication":"Nature Immunology","volume":25,"department":[{"_id":"MiSi"}],"citation":{"mla":"Lembo, Sergio, and Michael K. Sixt. “Nuclear Squeezing Wakes up Dendritic Cells.” <i>Nature Immunology</i>, vol. 25, Springer Nature, 2024, pp. 1131–1132, doi:<a href=\"https://doi.org/10.1038/s41590-024-01881-2\">10.1038/s41590-024-01881-2</a>.","apa":"Lembo, S., &#38; Sixt, M. K. (2024). Nuclear squeezing wakes up dendritic cells. <i>Nature Immunology</i>. Springer Nature. <a href=\"https://doi.org/10.1038/s41590-024-01881-2\">https://doi.org/10.1038/s41590-024-01881-2</a>","ieee":"S. Lembo and M. K. Sixt, “Nuclear squeezing wakes up dendritic cells,” <i>Nature Immunology</i>, vol. 25. Springer Nature, pp. 1131–1132, 2024.","chicago":"Lembo, Sergio, and Michael K Sixt. “Nuclear Squeezing Wakes up Dendritic Cells.” <i>Nature Immunology</i>. Springer Nature, 2024. <a href=\"https://doi.org/10.1038/s41590-024-01881-2\">https://doi.org/10.1038/s41590-024-01881-2</a>.","short":"S. Lembo, M.K. Sixt, Nature Immunology 25 (2024) 1131–1132.","ama":"Lembo S, Sixt MK. Nuclear squeezing wakes up dendritic cells. <i>Nature Immunology</i>. 2024;25:1131–1132. doi:<a href=\"https://doi.org/10.1038/s41590-024-01881-2\">10.1038/s41590-024-01881-2</a>","ista":"Lembo S, Sixt MK. 2024. Nuclear squeezing wakes up dendritic cells. Nature Immunology. 25, 1131–1132."},"year":"2024","publication_identifier":{"issn":["1529-2908"],"eissn":["1529-2916"]},"pmid":1,"publication_status":"published","das_tickbox":"0","supplementarymaterial":"no","article_type":"letter_note","language":[{"iso":"eng"}],"external_id":{"isi":["001251509300001"],"pmid":["38907047"]},"month":"06","author":[{"id":"d993a7b2-292f-11ed-aaac-fb045a912e31","last_name":"Lembo","full_name":"Lembo, Sergio","first_name":"Sergio","orcid":"0000-0002-2253-8771"},{"full_name":"Sixt, Michael K","first_name":"Michael K","id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","last_name":"Sixt","orcid":"0000-0002-6620-9179"}],"researchdata_availability":"no","isi":1,"abstract":[{"text":"Dendritic cells migrate to and from lymph nodes in response to chemokine gradients.Data now show that steady-state migration of these cells can be triggered by a mechanosensitive pathway.","lang":"eng"}],"type":"journal_article","fulldoi":"https://doi.org/10.1038/s41590-024-01881-2","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","quality_controlled":"1","corr_author":"1","article_processing_charge":"No","doi":"10.1038/s41590-024-01881-2","intvolume":"        25","title":"Nuclear squeezing wakes up dendritic cells","date_published":"2024-06-21T00:00:00Z","publisher":"Springer Nature","scopus_import":"1","page":"1131–1132 "},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","doi":"10.5281/ZENODO.13833474","corr_author":"1","publisher":"Zenodo","ddc":["530"],"date_published":"2024-09-24T00:00:00Z","title":"Data for: Ab initio Auger spectrum of the ultrafast dissociating 2p3/2−1σ* resonance in HCl","_id":"18716","date_created":"2025-01-02T08:21:55Z","oa":1,"main_file_link":[{"url":"https://doi.org/10.5281/zenodo.13833474","open_access":"1"}],"date_updated":"2026-10-21T07:56:54Z","related_material":{"record":[{"id":"18710","status":"public","relation":"used_in_publication"}]},"oa_version":"None","month":"09","author":[{"full_name":"Hrast, Mateja","first_name":"Mateja","last_name":"Hrast","id":"48dbb294-2a9c-11ef-905d-f56be71f0e5d"}],"status":"public","day":"24","department":[{"_id":"MiLe"}],"abstract":[{"text":"Data for publication 10.1039/d4cp03727h","lang":"eng"}],"citation":{"ieee":"M. Hrast, “Data for: Ab initio Auger spectrum of the ultrafast dissociating 2p3/2−1σ* resonance in HCl.” Zenodo, 2024.","chicago":"Hrast, Mateja. “Data for: Ab Initio Auger Spectrum of the Ultrafast Dissociating 2p3/2−1σ* Resonance in HCl.” Zenodo, 2024. <a href=\"https://doi.org/10.5281/ZENODO.13833474\">https://doi.org/10.5281/ZENODO.13833474</a>.","short":"M. Hrast, (2024).","ama":"Hrast M. Data for: Ab initio Auger spectrum of the ultrafast dissociating 2p3/2−1σ* resonance in HCl. 2024. doi:<a href=\"https://doi.org/10.5281/ZENODO.13833474\">10.5281/ZENODO.13833474</a>","ista":"Hrast M. 2024. Data for: Ab initio Auger spectrum of the ultrafast dissociating 2p3/2−1σ* resonance in HCl, Zenodo, <a href=\"https://doi.org/10.5281/ZENODO.13833474\">10.5281/ZENODO.13833474</a>.","apa":"Hrast, M. (2024). Data for: Ab initio Auger spectrum of the ultrafast dissociating 2p3/2−1σ* resonance in HCl. Zenodo. <a href=\"https://doi.org/10.5281/ZENODO.13833474\">https://doi.org/10.5281/ZENODO.13833474</a>","mla":"Hrast, Mateja. <i>Data for: Ab Initio Auger Spectrum of the Ultrafast Dissociating 2p3/2−1σ* Resonance in HCl</i>. Zenodo, 2024, doi:<a href=\"https://doi.org/10.5281/ZENODO.13833474\">10.5281/ZENODO.13833474</a>."},"fulldoi":"https://doi.org/10.5281/ZENODO.13833474","year":"2024","type":"research_data_reference"},{"day":"24","month":"09","author":[{"first_name":"Mateja","full_name":"Hrast, Mateja","last_name":"Hrast"}],"status":"public","oa_version":"None","related_material":{"record":[{"id":"18710","status":"public","relation":"used_in_publication"}]},"date_updated":"2026-10-21T07:56:55Z","main_file_link":[{"url":"https://doi.org/10.5281/zenodo.13833475","open_access":"1"}],"_id":"22866","oa":1,"date_created":"2026-09-09T09:20:36Z","type":"research_data_reference","year":"2024","fulldoi":"https://doi.org/10.5281/zenodo.13833474","citation":{"mla":"Hrast, Mateja. <i>Data for: Ab Initio Auger Spectrum of the Ultrafast Dissociating 2p3/2−1σ* Resonance in HCl</i>. Repository, 2024, doi:<a href=\"https://doi.org/10.5281/zenodo.13833474\">10.5281/zenodo.13833474</a>.","apa":"Hrast, M. (2024). Data for: Ab initio Auger spectrum of the ultrafast dissociating 2p3/2−1σ* resonance in HCl. Repository. <a href=\"https://doi.org/10.5281/zenodo.13833474\">https://doi.org/10.5281/zenodo.13833474</a>","ieee":"M. Hrast, “Data for: Ab initio Auger spectrum of the ultrafast dissociating 2p3/2−1σ* resonance in HCl.” Repository, 2024.","chicago":"Hrast, Mateja. “Data for: Ab Initio Auger Spectrum of the Ultrafast Dissociating 2p3/2−1σ* Resonance in HCl.” Repository, 2024. <a href=\"https://doi.org/10.5281/zenodo.13833474\">https://doi.org/10.5281/zenodo.13833474</a>.","short":"M. Hrast, (2024).","ama":"Hrast M. Data for: Ab initio Auger spectrum of the ultrafast dissociating 2p3/2−1σ* resonance in HCl. 2024. doi:<a href=\"https://doi.org/10.5281/zenodo.13833474\">10.5281/zenodo.13833474</a>","ista":"Hrast M. 2024. Data for: Ab initio Auger spectrum of the ultrafast dissociating 2p3/2−1σ* resonance in HCl, Repository, <a href=\"https://doi.org/10.5281/zenodo.13833474\">10.5281/zenodo.13833474</a>."},"department":[{"_id":"MiLe"},{"_id":"MaSe"}],"doi":"10.5281/zenodo.13833474","article_processing_charge":"No","OA_place":"repository","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","OA_type":"green","title":"Data for: Ab initio Auger spectrum of the ultrafast dissociating 2p3/2−1σ* resonance in HCl","date_published":"2024-09-24T00:00:00Z","ddc":["530"],"publisher":"Repository"},{"tmp":{"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)","image":"/images/cc_by.png"},"volume":57,"department":[{"_id":"MiSi"}],"citation":{"ama":"Stark K, Kilani B, Stockhausen S, et al. Antibodies and complement are key drivers of thrombosis. <i>Immunity</i>. 2024;57(9):2140-2156. doi:<a href=\"https://doi.org/10.1016/j.immuni.2024.08.007\">10.1016/j.immuni.2024.08.007</a>","ista":"Stark K, Kilani B, Stockhausen S, Busse J, Schubert I, Tran TD, Gärtner FR, Leunig A, Pekayvaz K, Nicolai L, Fumagalli V, Stermann J, Stephan F, David C, Müller MB, Heyman B, Lux A, Da Palma Guerreiro A, Frenzel LP, Schmidt CQ, Dopler A, Moser M, Chandraratne S, Von Brühl ML, Lorenz M, Korff T, Rudelius M, Popp O, Kirchner M, Mertins P, Nimmerjahn F, Iannacone M, Sperandio M, Engelmann B, Verschoor A, Massberg S. 2024. Antibodies and complement are key drivers of thrombosis. Immunity. 57(9), 2140–2156.","short":"K. Stark, B. Kilani, S. Stockhausen, J. Busse, I. Schubert, T.D. Tran, F.R. Gärtner, A. Leunig, K. Pekayvaz, L. Nicolai, V. Fumagalli, J. Stermann, F. Stephan, C. David, M.B. Müller, B. Heyman, A. Lux, A. Da Palma Guerreiro, L.P. Frenzel, C.Q. Schmidt, A. Dopler, M. Moser, S. Chandraratne, M.L. Von Brühl, M. Lorenz, T. Korff, M. Rudelius, O. Popp, M. Kirchner, P. Mertins, F. Nimmerjahn, M. Iannacone, M. Sperandio, B. Engelmann, A. Verschoor, S. Massberg, Immunity 57 (2024) 2140–2156.","chicago":"Stark, Konstantin, Badr Kilani, Sven Stockhausen, Johanna Busse, Irene Schubert, Thuy Duong Tran, Florian R Gärtner, et al. “Antibodies and Complement Are Key Drivers of Thrombosis.” <i>Immunity</i>. Elsevier, 2024. <a href=\"https://doi.org/10.1016/j.immuni.2024.08.007\">https://doi.org/10.1016/j.immuni.2024.08.007</a>.","ieee":"K. Stark <i>et al.</i>, “Antibodies and complement are key drivers of thrombosis,” <i>Immunity</i>, vol. 57, no. 9. Elsevier, pp. 2140–2156, 2024.","apa":"Stark, K., Kilani, B., Stockhausen, S., Busse, J., Schubert, I., Tran, T. D., … Massberg, S. (2024). Antibodies and complement are key drivers of thrombosis. <i>Immunity</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.immuni.2024.08.007\">https://doi.org/10.1016/j.immuni.2024.08.007</a>","mla":"Stark, Konstantin, et al. “Antibodies and Complement Are Key Drivers of Thrombosis.” <i>Immunity</i>, vol. 57, no. 9, Elsevier, 2024, pp. 2140–56, doi:<a href=\"https://doi.org/10.1016/j.immuni.2024.08.007\">10.1016/j.immuni.2024.08.007</a>."},"year":"2024","oa_version":"Published Version","status":"public","date_created":"2024-09-22T22:01:42Z","_id":"18109","oa":1,"date_updated":"2026-10-21T08:01:09Z","day":"10","publication":"Immunity","ddc":["570"],"issue":"9","article_type":"original","language":[{"iso":"eng"}],"external_id":{"pmid":["39226900"],"isi":["001317438500001"]},"file":[{"relation":"main_file","file_size":6892750,"checksum":"4683de43d06a8fd8e3fc91af4ddc1ba2","success":1,"creator":"dernst","access_level":"open_access","file_id":"18162","content_type":"application/pdf","date_updated":"2024-09-30T09:16:03Z","date_created":"2024-09-30T09:16:03Z","file_name":"2024_Immunity_Stark.pdf"}],"publication_identifier":{"eissn":["1097-4180"]},"pmid":1,"has_accepted_license":"1","publication_status":"published","das_tickbox":"1","supplementarymaterial":"yes","isi":1,"file_date_updated":"2024-09-30T09:16:03Z","abstract":[{"text":"Venous thromboembolism (VTE) is a common, deadly disease with an increasing incidence despite preventive efforts. Clinical observations have associated elevated antibody concentrations or antibody-based therapies with thrombotic events. However, how antibodies contribute to thrombosis is unknown. Here, we show that reduced blood flow enabled immunoglobulin M (IgM) to bind to FcμR and the polymeric immunoglobulin receptor (pIgR), initiating endothelial activation and platelet recruitment. Subsequently, the procoagulant surface of activated platelets accommodated antigen- and FcγR-independent IgG deposition. This leads to classical complement activation, setting in motion a prothrombotic vicious circle. Key elements of this mechanism were present in humans in the setting of venous stasis as well as in the dysregulated immunothrombosis of COVID-19. This antibody-driven thrombosis can be prevented by pharmacologically targeting complement. Hence, our results uncover antibodies as previously unrecognized central regulators of thrombosis. These findings carry relevance for therapeutic application of antibodies and open innovative avenues to target thrombosis without compromising hemostasis.","lang":"eng"}],"type":"journal_article","fulldoi":"https://doi.org/10.1016/j.immuni.2024.08.007","author":[{"first_name":"Konstantin","full_name":"Stark, Konstantin","last_name":"Stark"},{"last_name":"Kilani","first_name":"Badr","full_name":"Kilani, Badr"},{"last_name":"Stockhausen","first_name":"Sven","full_name":"Stockhausen, Sven"},{"full_name":"Busse, Johanna","first_name":"Johanna","last_name":"Busse"},{"first_name":"Irene","full_name":"Schubert, Irene","last_name":"Schubert"},{"full_name":"Tran, Thuy Duong","first_name":"Thuy Duong","last_name":"Tran"},{"last_name":"Gärtner","id":"397A88EE-F248-11E8-B48F-1D18A9856A87","full_name":"Gärtner, Florian R","first_name":"Florian R","orcid":"0000-0001-6120-3723"},{"last_name":"Leunig","first_name":"Alexander","full_name":"Leunig, Alexander"},{"last_name":"Pekayvaz","first_name":"Kami","full_name":"Pekayvaz, Kami"},{"last_name":"Nicolai","full_name":"Nicolai, Leo","first_name":"Leo"},{"last_name":"Fumagalli","first_name":"Valeria","full_name":"Fumagalli, Valeria"},{"first_name":"Julia","full_name":"Stermann, Julia","last_name":"Stermann"},{"last_name":"Stephan","full_name":"Stephan, Felix","first_name":"Felix"},{"last_name":"David","full_name":"David, Christian","first_name":"Christian"},{"first_name":"Martin B.","full_name":"Müller, Martin B.","last_name":"Müller"},{"full_name":"Heyman, Birgitta","first_name":"Birgitta","last_name":"Heyman"},{"last_name":"Lux","full_name":"Lux, Anja","first_name":"Anja"},{"first_name":"Alexandra","full_name":"Da Palma Guerreiro, Alexandra","last_name":"Da Palma Guerreiro"},{"last_name":"Frenzel","full_name":"Frenzel, Lukas P.","first_name":"Lukas P."},{"first_name":"Christoph Q.","full_name":"Schmidt, Christoph Q.","last_name":"Schmidt"},{"last_name":"Dopler","first_name":"Arthur","full_name":"Dopler, Arthur"},{"full_name":"Moser, Markus","first_name":"Markus","last_name":"Moser"},{"full_name":"Chandraratne, Sue","first_name":"Sue","last_name":"Chandraratne"},{"last_name":"Von Brühl","full_name":"Von Brühl, Marie Luise","first_name":"Marie Luise"},{"last_name":"Lorenz","first_name":"Michael","full_name":"Lorenz, Michael"},{"first_name":"Thomas","full_name":"Korff, Thomas","last_name":"Korff"},{"last_name":"Rudelius","full_name":"Rudelius, Martina","first_name":"Martina"},{"first_name":"Oliver","full_name":"Popp, Oliver","last_name":"Popp"},{"last_name":"Kirchner","full_name":"Kirchner, Marieluise","first_name":"Marieluise"},{"first_name":"Philipp","full_name":"Mertins, Philipp","last_name":"Mertins"},{"full_name":"Nimmerjahn, Falk","first_name":"Falk","last_name":"Nimmerjahn"},{"last_name":"Iannacone","full_name":"Iannacone, Matteo","first_name":"Matteo"},{"first_name":"Markus","full_name":"Sperandio, Markus","last_name":"Sperandio"},{"last_name":"Engelmann","full_name":"Engelmann, Bernd","first_name":"Bernd"},{"last_name":"Verschoor","first_name":"Admar","full_name":"Verschoor, Admar"},{"last_name":"Massberg","full_name":"Massberg, Steffen","first_name":"Steffen"}],"month":"09","researchdata_availability":"upon request","intvolume":"        57","date_published":"2024-09-10T00:00:00Z","title":"Antibodies and complement are key drivers of thrombosis","publisher":"Elsevier","page":"2140-2156","scopus_import":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","acknowledgement":"We thank Michael Carroll (Harvard Medical School, Boston) for providing Ighmtm1Che, C4−/−, and C3−/− mice; Mark Suter (University of Zurich, Zurich) for providing Aicda−/− mice; Marina Botto (Imperial College London, London) for providing C1q−/− and fB−/− mice; Craig Gerard (Harvard Medical School, Boston) for providing C3aR−/− mice; Falk Nimmerjahn (University Erlangen-Nuernberg, Erlangen) for providing Fcgr−/−Fcgr2b−/− mice; Karl Lang (University of Duisburg-Essen, Essen) for providing Fcmr−/− mice; Hans Hengartner and Rolf Zinkernagel (ETH Zurich, Zurich) for providing KL25 mice; Mark Zabel (University Hospital of Zurich, Zurich) for providing CR2−/− mice; Christie Ballantyne (Baylor College of Medicine, Houston) for providing CD11c−/− mice; and Siamon Gordon (University of Oxford, Oxford) for providing CD11b−/− mice. A.V. wishes to thank Michael Grünaug and dedicates this work to Annette, Rita, and Hans.\r\nThis project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no. \r\n947611) (K.S.). This study was supported by the Deutsche Forschungsgemeinschaft through the collaborative research center 914 project B02 (K.S. and S.M.), project B04 (A.V.), project A01 (M.M.), project B01 (M.S.), the collaborative research center 1123 project B07 (K.S. and S.M.), the collaborative research center 359 (project A03 [K.S.] and B02 [M.S.]), the international research training group 1911 project B09 (A.V.), the clinical research unit 303 project 7 (A.V.), cluster of excellence 2167 (A.V.), collaborative research center 1526 project 05 (A.V.), the ANR-DFG project JAKPOT (K.S.), LMUexcellent (K.S.), and the Deutsche Zentrum für Herz-Kreislauf-Forschung (PostDoc Grant and partner site project [K.S. and S.M.]). M.I. is supported by the European Research Council (ERC) Advanced Grant 101141363, ERC Proof of Concept Grant 101138728, Italian Association for Cancer Research (AIRC) Grants 19891 and \r\n22737, Italian Ministry for University and Research Grants PE00000007 (INF-ACT) and PRIN \r\n2022FMESXL, Funded Research Agreement from Asher Biotherapeutics, VIR Biotechnology, and BlueJay Therapeutics. V.F. is supported by the Italian Ministry for University and Research Grants PE00000007 (INF-ACT) and Fondazione Prossimo Mio.","dataavailabilitystatement":"All data reported in this paper will be shared by the lead contact upon request. This paper does not report original codes. Any additional information required to reanalyze the data reported in this paper is available from the lead contact upon request.","quality_controlled":"1","article_processing_charge":"Yes (in subscription journal)","doi":"10.1016/j.immuni.2024.08.007"},{"intvolume":"       287","date_published":"2024-01-24T00:00:00Z","title":"Electrical flows for polylogarithmic competitive oblivious routing","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","scopus_import":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","acknowledgement":"Monika Henzinger and A. R. Sricharan: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation\r\nprogramme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) project Z\r\n422-N, project I 5982-N, and project P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nHarald Räcke: Research supported by German Research Foundation (DFG), grant 470029389\r\n(FlexNets), 2021-2024.\r\nSushant Sachdeva: SS’s work is supported by an Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant RGPIN-2018-06398 and a Sloan Research Fellowship.","quality_controlled":"1","corr_author":"1","article_processing_charge":"No","doi":"10.4230/LIPIcs.ITCS.2024.55","isi":1,"file_date_updated":"2024-02-26T10:10:48Z","abstract":[{"text":"Oblivious routing is a well-studied paradigm that uses static precomputed routing tables for selecting routing paths within a network. Existing oblivious routing schemes with polylogarithmic competitive ratio for general networks are tree-based, in the sense that routing is performed according to a convex combination of trees. However, this restriction to trees leads to a construction that has time quadratic in the size of the network and does not parallelize well. \r\nIn this paper we study oblivious routing schemes based on electrical routing. In particular, we show that general networks with n vertices and m edges admit a routing scheme that has competitive ratio O(log² n) and consists of a convex combination of only O(√m) electrical routings. This immediately leads to an improved construction algorithm with time Õ(m^{3/2}) that can also be implemented in parallel with Õ(√m) depth.","lang":"eng"}],"type":"conference","fulldoi":"https://doi.org/10.4230/LIPIcs.ITCS.2024.55","author":[{"first_name":"Gramoz","full_name":"Goranci, Gramoz","last_name":"Goranci"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"first_name":"Harald","full_name":"Räcke, Harald","last_name":"Räcke"},{"first_name":"Sushant","full_name":"Sachdeva, Sushant","last_name":"Sachdeva"},{"last_name":"Sricharan","first_name":"A. R.","full_name":"Sricharan, A. R."}],"month":"01","article_number":"55","researchdata_availability":"no","conference":{"start_date":"2024-01-30","name":"ITCS: Innovations in Theoretical Computer Science","location":"Berkeley, CA, United States","end_date":"2024-02-02"},"ec_funded":1,"ddc":["000"],"language":[{"iso":"eng"}],"external_id":{"arxiv":["2303.02491"],"isi":["001300389400055"]},"file":[{"relation":"main_file","file_size":1054754,"checksum":"b89716aae6a5599f187897e39de1e53a","creator":"dernst","success":1,"access_level":"open_access","file_id":"15030","date_created":"2024-02-26T10:10:48Z","file_name":"2024_LIPICs_Goranci.pdf","content_type":"application/pdf","date_updated":"2024-02-26T10:10:48Z"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773096"]},"has_accepted_license":"1","publication_status":"published","das_tickbox":"0","supplementarymaterial":"no","tmp":{"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)","image":"/images/cc_by.png"},"volume":287,"department":[{"_id":"MoHe"}],"citation":{"short":"G. Goranci, M. Henzinger, H. Räcke, S. Sachdeva, A.R. Sricharan, in:, 15th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","chicago":"Goranci, Gramoz, Monika Henzinger, Harald Räcke, Sushant Sachdeva, and A. R. Sricharan. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.” In <i>15th Innovations in Theoretical Computer Science Conference</i>, Vol. 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.55\">https://doi.org/10.4230/LIPIcs.ITCS.2024.55</a>.","ama":"Goranci G, Henzinger M, Räcke H, Sachdeva S, Sricharan AR. Electrical flows for polylogarithmic competitive oblivious routing. In: <i>15th Innovations in Theoretical Computer Science Conference</i>. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.55\">10.4230/LIPIcs.ITCS.2024.55</a>","ista":"Goranci G, Henzinger M, Räcke H, Sachdeva S, Sricharan AR. 2024. Electrical flows for polylogarithmic competitive oblivious routing. 15th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 287, 55.","ieee":"G. Goranci, M. Henzinger, H. Räcke, S. Sachdeva, and A. R. Sricharan, “Electrical flows for polylogarithmic competitive oblivious routing,” in <i>15th Innovations in Theoretical Computer Science Conference</i>, Berkeley, CA, United States, 2024, vol. 287.","apa":"Goranci, G., Henzinger, M., Räcke, H., Sachdeva, S., &#38; Sricharan, A. R. (2024). Electrical flows for polylogarithmic competitive oblivious routing. In <i>15th Innovations in Theoretical Computer Science Conference</i> (Vol. 287). Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.55\">https://doi.org/10.4230/LIPIcs.ITCS.2024.55</a>","mla":"Goranci, Gramoz, et al. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.” <i>15th Innovations in Theoretical Computer Science Conference</i>, vol. 287, 55, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ITCS.2024.55\">10.4230/LIPIcs.ITCS.2024.55</a>."},"project":[{"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"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775"}],"year":"2024","alternative_title":["LIPIcs"],"oa_version":"Published Version","status":"public","date_created":"2024-02-18T23:01:02Z","_id":"15008","oa":1,"date_updated":"2026-10-21T08:02:42Z","day":"24","publication":"15th Innovations in Theoretical Computer Science Conference","arxiv":1},{"fulldoi":"https://doi.org/10.1016/j.jaci.2024.03.022","type":"journal_article","file_date_updated":"2025-01-13T10:55:28Z","abstract":[{"lang":"eng","text":"Background: IgE-mediated degranulation of mast cells (MCs) provides rapid protection against environmental hazards, including animal venoms. A fraction of tissue-resident MCs intimately associates with blood vessels. These perivascular MCs were reported to extend projections into the vessel lumen and to be the first MCs to acquire intravenously injected IgE, suggesting that IgE loading of MCs depends on their vascular association.\r\nObjective: We sought to elucidate the molecular basis of the MC–blood vessel interaction and to determine its relevance for IgE-mediated immune responses.\r\nMethods: We selectively inactivated the Itgb1 gene, encoding the β1 chain of integrin adhesion molecules (ITGB1), in MCs by conditional gene targeting in mice. We analyzed skin MCs for blood vessel association, surface IgE density, and capability to bind circulating antibody specific for MC surface molecules, as well as in vivo responses to antigen administered via different routes.\r\nResults: Lack of ITGB1 expression severely compromised MC–blood vessel association. ITGB1-deficient MCs showed normal densities of surface IgE but reduced binding of intravenously injected antibodies. While their capacity to degranulate in response to IgE ligation in vivo was unimpaired, anaphylactic responses to antigen circulating in the vasculature were largely abolished.\r\nConclusions: ITGB1-mediated association of MCs with blood vessels is key for MC immune surveillance of blood vessel content, but is dispensable for slow steady-state loading of endogenous IgE onto tissue-resident MCs."}],"isi":1,"researchdata_availability":"no","author":[{"full_name":"Link, Kristina","first_name":"Kristina","last_name":"Link"},{"first_name":"Lina","full_name":"Muhandes, Lina","last_name":"Muhandes"},{"full_name":"Polikarpova, Anastasia","first_name":"Anastasia","last_name":"Polikarpova"},{"first_name":"Tim","full_name":"Lämmermann, Tim","last_name":"Lämmermann"},{"orcid":"0000-0002-6620-9179","id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","last_name":"Sixt","first_name":"Michael K","full_name":"Sixt, Michael K"},{"last_name":"Fässler","first_name":"Reinhard","full_name":"Fässler, Reinhard"},{"first_name":"Axel","full_name":"Roers, Axel","last_name":"Roers"}],"month":"09","scopus_import":"1","page":"745-753","publisher":"Elsevier","intvolume":"       154","title":"Integrin β1–mediated mast cell immune-surveillance of blood vessel content","date_published":"2024-09-01T00:00:00Z","article_processing_charge":"Yes (in subscription journal)","doi":"10.1016/j.jaci.2024.03.022","quality_controlled":"1","OA_type":"hybrid","acknowledgement":"This work was funded by Deutsche Forschungsgemeinschaft, Germany, grants RO2133/ 9-1 and RO2133/ 9-2 in the setting of FOR2599 and TR156 project C11 (Project-ID 246807620–TRR 156) to A. Roers and Springboard-to-Postdoc grant of the Dresden International Graduate School for Biomedicine and Bioengineering (DIGS-BB), Dresden, Germany, and Fond zur Förderung der Wissenschaftlichen Forschung (FWF), Austria, Hertha Firnberg grant (project number T-1219) to A. Polikarpova.\r\nWe thank Dr Michael Gerlach, Core Facility Cellular Imaging, Faculty of Medicine Carl Gustav Carus, TU Dresden, for expert support of in vivo imaging experiments; Grace Wurigamule for help with 2-photon imaging and flow cytometric analysis of mouse skin; and Christina Hiller, Livia Schulze, Madelaine Rickauer, and Christa Haase for providing expert technical assistance.","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","OA_place":"publisher","year":"2024","department":[{"_id":"MiSi"}],"citation":{"apa":"Link, K., Muhandes, L., Polikarpova, A., Lämmermann, T., Sixt, M. K., Fässler, R., &#38; Roers, A. (2024). Integrin β1–mediated mast cell immune-surveillance of blood vessel content. <i>Journal of Allergy and Clinical Immunology</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jaci.2024.03.022\">https://doi.org/10.1016/j.jaci.2024.03.022</a>","mla":"Link, Kristina, et al. “Integrin Β1–Mediated Mast Cell Immune-Surveillance of Blood Vessel Content.” <i>Journal of Allergy and Clinical Immunology</i>, vol. 154, no. 3, Elsevier, 2024, pp. 745–53, doi:<a href=\"https://doi.org/10.1016/j.jaci.2024.03.022\">10.1016/j.jaci.2024.03.022</a>.","ista":"Link K, Muhandes L, Polikarpova A, Lämmermann T, Sixt MK, Fässler R, Roers A. 2024. Integrin β1–mediated mast cell immune-surveillance of blood vessel content. Journal of Allergy and Clinical Immunology. 154(3), 745–753.","ama":"Link K, Muhandes L, Polikarpova A, et al. Integrin β1–mediated mast cell immune-surveillance of blood vessel content. <i>Journal of Allergy and Clinical Immunology</i>. 2024;154(3):745-753. doi:<a href=\"https://doi.org/10.1016/j.jaci.2024.03.022\">10.1016/j.jaci.2024.03.022</a>","short":"K. Link, L. Muhandes, A. Polikarpova, T. Lämmermann, M.K. Sixt, R. Fässler, A. Roers, Journal of Allergy and Clinical Immunology 154 (2024) 745–753.","chicago":"Link, Kristina, Lina Muhandes, Anastasia Polikarpova, Tim Lämmermann, Michael K Sixt, Reinhard Fässler, and Axel Roers. “Integrin Β1–Mediated Mast Cell Immune-Surveillance of Blood Vessel Content.” <i>Journal of Allergy and Clinical Immunology</i>. Elsevier, 2024. <a href=\"https://doi.org/10.1016/j.jaci.2024.03.022\">https://doi.org/10.1016/j.jaci.2024.03.022</a>.","ieee":"K. Link <i>et al.</i>, “Integrin β1–mediated mast cell immune-surveillance of blood vessel content,” <i>Journal of Allergy and Clinical Immunology</i>, vol. 154, no. 3. Elsevier, pp. 745–753, 2024."},"tmp":{"name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","short":"CC BY-NC-ND (4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","image":"/images/cc_by_nc_nd.png"},"volume":154,"day":"01","publication":"Journal of Allergy and Clinical Immunology","_id":"15408","date_created":"2024-05-19T22:01:13Z","oa":1,"date_updated":"2026-10-21T08:01:51Z","oa_version":"Published Version","status":"public","file":[{"access_level":"open_access","file_id":"18840","file_name":"2024_JourAllergyClinicalImm_Link.pdf","date_created":"2025-01-13T10:55:28Z","content_type":"application/pdf","date_updated":"2025-01-13T10:55:28Z","relation":"main_file","file_size":1792425,"checksum":"6a5af05082e1869d7cad6406fa4eb76c","creator":"dernst","success":1}],"external_id":{"isi":["001308886700001"],"pmid":["38636606"]},"issue":"3","article_type":"original","language":[{"iso":"eng"}],"ddc":["570"],"supplementarymaterial":"yes","license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","publication_status":"published","das_tickbox":"0","has_accepted_license":"1","publication_identifier":{"eissn":["1097-6825"],"issn":["0091-6749"]},"pmid":1},{"_id":"14933","oa":1,"date_created":"2024-02-04T23:00:53Z","date_updated":"2026-10-21T08:00:18Z","oa_version":"Published Version","status":"public","day":"10","publication":"EMBO Reports","department":[{"_id":"MiSi"}],"citation":{"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>","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.","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>.","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.","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>.","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>"},"volume":25,"tmp":{"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)","image":"/images/cc_by.png"},"year":"2024","has_accepted_license":"1","publication_identifier":{"eissn":["1469-3178"]},"pmid":1,"supplementarymaterial":"yes","publication_status":"published","das_tickbox":"1","issue":"1","article_type":"original","language":[{"iso":"eng"}],"ddc":["570"],"file":[{"checksum":"53c3ef43d9bd6d7bff3ffcf57d763cac","file_size":9645056,"relation":"main_file","creator":"dernst","success":1,"file_id":"14941","access_level":"open_access","date_created":"2024-02-05T12:35:03Z","file_name":"2023_EmboReports_PimentaMarques.pdf","content_type":"application/pdf","date_updated":"2024-02-05T12:35:03Z"}],"external_id":{"pmid":["38200359"]},"researchdata_availability":"not applicable","author":[{"full_name":"Pimenta-Marques, Ana","first_name":"Ana","last_name":"Pimenta-Marques"},{"last_name":"Perestrelo","full_name":"Perestrelo, Tania","first_name":"Tania"},{"orcid":"0000-0003-1681-508X","first_name":"Patricia","full_name":"Dos Reis Rodrigues, Patricia","id":"26E95904-5160-11E9-9C0B-C5B0DC97E90F","last_name":"Dos Reis Rodrigues"},{"last_name":"Duarte","first_name":"Paulo","full_name":"Duarte, Paulo"},{"first_name":"Ana","full_name":"Ferreira-Silva, Ana","last_name":"Ferreira-Silva"},{"first_name":"Mariana","full_name":"Lince-Faria, Mariana","last_name":"Lince-Faria"},{"first_name":"Mónica","full_name":"Bettencourt-Dias, Mónica","last_name":"Bettencourt-Dias"}],"month":"01","file_date_updated":"2024-02-05T12:35:03Z","abstract":[{"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.","lang":"eng"}],"fulldoi":"https://doi.org/10.1038/s44319-023-00020-6","type":"journal_article","dataavailabilitystatement":"This study includes no data deposited in external repositories.","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).","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"Yes (in subscription journal)","doi":"10.1038/s44319-023-00020-6","quality_controlled":"1","publisher":"Embo Press","intvolume":"        25","date_published":"2024-01-10T00:00:00Z","title":"Ana1/CEP295 is an essential player in the centrosome maintenance program regulated by Polo kinase and the PCM","page":"102-127","scopus_import":"1"},{"publication":"2024 Proceedings of the Symposium on Algorithm Engineering and Experiments","day":"04","arxiv":1,"date_updated":"2026-10-21T08:02:15Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2310.18034"}],"_id":"14769","oa":1,"date_created":"2024-01-09T16:22:47Z","status":"public","oa_version":"Preprint","year":"2024","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","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"},{"name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","grant_number":"P33775"},{"grant_number":"101034413","call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program"}],"citation":{"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>","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>.","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.","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>.","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>","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."},"department":[{"_id":"MoHe"}],"supplementarymaterial":"no","das_tickbox":"0","publication_status":"published","publication_identifier":{"eisbn":["9781611977929"]},"external_id":{"arxiv":["2310.18034"]},"language":[{"iso":"eng"}],"ec_funded":1,"conference":{"end_date":"2024-01-08","location":"Alexandria, VA, United States","name":"ALENEX: Workshop on Algorithm Engineering and Experiments","start_date":"2024-01-07"},"researchdata_availability":"no","author":[{"first_name":"Monika H","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530"},{"full_name":"Saulpic, David","first_name":"David","last_name":"Saulpic","id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964"},{"first_name":"Leonhard","full_name":"Sidl, Leonhard","id":"8b563fd0-b441-11ee-9101-a3891c61efa6","last_name":"Sidl"}],"month":"01","fulldoi":"https://doi.org/10.1137/1.9781611977929.17","type":"conference","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."}],"doi":"10.1137/1.9781611977929.17","article_processing_charge":"No","corr_author":"1","quality_controlled":"1","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","scopus_import":"1","page":"220-233","publisher":"Society for Industrial and Applied Mathematics","title":"Experimental evaluation of fully dynamic k-means via coresets","date_published":"2024-01-04T00:00:00Z"},{"year":"2024","department":[{"_id":"MiSi"}],"citation":{"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.","short":"M. Avellaneda Sarrió, M.K. Sixt, Cell Chemical Biology 31 (2024) 1242–1243.","ista":"Avellaneda Sarrió M, Sixt MK. 2024. Rescuing T cells from stiff tumors. Cell Chemical Biology. 31(7), 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>","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>.","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>","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>."},"volume":31,"publication":"Cell Chemical Biology","day":"18","_id":"17279","date_created":"2024-07-21T22:01:00Z","date_updated":"2026-10-21T07:58:00Z","oa_version":"None","status":"public","external_id":{"isi":["001275725000001"],"pmid":["39029454"]},"issue":"7","language":[{"iso":"eng"}],"article_type":"review","supplementarymaterial":"no","publication_status":"published","das_tickbox":"0","publication_identifier":{"issn":["2451-9456"],"eissn":["2451-9448"]},"pmid":1,"fulldoi":"https://doi.org/10.1016/j.chembiol.2024.06.011","type":"journal_article","abstract":[{"lang":"eng","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."}],"isi":1,"researchdata_availability":"no","author":[{"id":"DC4BA84C-56E6-11EA-AD5D-348C3DDC885E","last_name":"Avellaneda Sarrió","first_name":"Mario","full_name":"Avellaneda Sarrió, Mario","orcid":"0000-0001-6406-524X"},{"orcid":"0000-0002-6620-9179","last_name":"Sixt","id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","full_name":"Sixt, Michael K","first_name":"Michael K"}],"month":"07","page":"1242-1243","scopus_import":"1","publisher":"Elsevier","intvolume":"        31","title":"Rescuing T cells from stiff tumors","date_published":"2024-07-18T00:00:00Z","article_processing_charge":"No","doi":"10.1016/j.chembiol.2024.06.011","quality_controlled":"1","corr_author":"1","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345"},{"ec_funded":1,"conference":{"name":"DISC: Symposium on Distributed Computing","location":"Madrid, Spain","start_date":"2024-10-28","end_date":"2024-11-01"},"researchdata_availability":"no","related_material":{"record":[{"id":"22281","status":"public","relation":"dissertation_contains"}]},"article_number":"21","month":"10","author":[{"orcid":"0000-0003-4268-7368","id":"888a098e-fcac-11ee-aff7-d347be57b725","last_name":"El-Hayek","first_name":"Antoine","full_name":"El-Hayek, Antoine"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"last_name":"Schmid","first_name":"Stefan","full_name":"Schmid, Stefan"}],"fulldoi":"https://doi.org/10.4230/LIPIcs.DISC.2024.21","type":"conference","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"}],"file_date_updated":"2024-11-18T08:02:45Z","isi":1,"doi":"10.4230/LIPIcs.DISC.2024.21","article_processing_charge":"Yes","corr_author":"1","quality_controlled":"1","OA_type":"gold","OA_place":"publisher","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","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.","scopus_import":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2024-10-24T00:00:00Z","title":"Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges","intvolume":"       319","arxiv":1,"day":"24","publication":"38th International Symposium on Distributed Computing","date_updated":"2026-10-21T08:05:36Z","_id":"18557","oa":1,"date_created":"2024-11-17T23:01:47Z","status":"public","oa_version":"Published Version","alternative_title":["LIPIcs"],"year":"2024","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","call_identifier":"H2020","grant_number":"101019564"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms","grant_number":"Z00422"},{"_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions","grant_number":"I05982"}],"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>","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.","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."},"department":[{"_id":"MoHe"}],"tmp":{"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)","image":"/images/cc_by.png"},"volume":319,"supplementarymaterial":"no","das_tickbox":"0","publication_status":"published","has_accepted_license":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773522"]},"file":[{"checksum":"d6c8277331cafa188c33ba1717206cf4","file_size":809666,"relation":"main_file","creator":"dernst","success":1,"file_id":"18561","access_level":"open_access","date_created":"2024-11-18T08:02:45Z","file_name":"2024_LIPIcs_ElHayek.pdf","content_type":"application/pdf","date_updated":"2024-11-18T08:02:45Z"}],"external_id":{"isi":["001542467600021"],"arxiv":["2302.11988"]},"language":[{"iso":"eng"}],"ddc":["000"]},{"scopus_import":"1","date_published":"2024-09-16T00:00:00Z","title":"Private counting of distinct elements in the turnstile model and extensions","intvolume":"       317","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","corr_author":"1","quality_controlled":"1","doi":"10.4230/LIPIcs.APPROX/RANDOM.2024.40","article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","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.","type":"conference","fulldoi":"https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40","isi":1,"abstract":[{"lang":"eng","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]."}],"file_date_updated":"2024-10-01T10:07:14Z","conference":{"start_date":"2024-08-27","location":"London, United Kingdom","name":"APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems","end_date":"2024-08-30"},"ec_funded":1,"month":"09","author":[{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"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"}],"researchdata_availability":"no","article_number":"40","external_id":{"isi":["001545634500040"],"arxiv":["2408.11637"]},"file":[{"file_id":"18166","access_level":"open_access","date_updated":"2024-10-01T10:07:14Z","content_type":"application/pdf","file_name":"2024_LIPICs_HenzingerM.pdf","date_created":"2024-10-01T10:07:14Z","checksum":"c08b41c896e4d8c69570044808b40e0b","file_size":973917,"relation":"main_file","success":1,"creator":"dernst"}],"ddc":["000"],"language":[{"iso":"eng"}],"das_tickbox":"0","publication_status":"published","supplementarymaterial":"no","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773485"]},"has_accepted_license":"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"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms","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"}],"year":"2024","alternative_title":["LIPIcs"],"tmp":{"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)","image":"/images/cc_by.png"},"volume":317,"citation":{"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.","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>.","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.","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>","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.","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>.","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>"},"department":[{"_id":"MoHe"}],"arxiv":1,"day":"16","publication":"International Conference on Approximation Algorithms for Combinatorial Optimization Problems ","status":"public","oa_version":"Published Version","date_updated":"2026-10-21T08:04:23Z","date_created":"2024-09-29T22:01:38Z","_id":"18156","oa":1},{"conference":{"end_date":"2024-09-04","start_date":"2024-09-02","location":"London, United Kingdom","name":"ESA: European Symposium on Algorithms"},"ec_funded":1,"month":"09","author":[{"full_name":"La Tour, Max Dupré","first_name":"Max Dupré","last_name":"La Tour"},{"first_name":"Monika H","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530"},{"id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964","last_name":"Saulpic","full_name":"Saulpic, David","first_name":"David"}],"researchdata_availability":"no","article_number":"100","type":"conference","fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2024.100","isi":1,"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)."}],"file_date_updated":"2024-10-21T09:41:48Z","corr_author":"1","quality_controlled":"1","doi":"10.4230/LIPIcs.ESA.2024.100","article_processing_charge":"Yes","OA_place":"publisher","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_type":"gold","scopus_import":"1","title":"Fully dynamic k-means coreset in near-optimal update time","date_published":"2024-09-23T00:00:00Z","intvolume":"       308","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"day":"23","publication":"32nd Annual European Symposium on Algorithms","status":"public","oa_version":"Published Version","date_updated":"2026-10-21T08:04:40Z","_id":"18308","oa":1,"date_created":"2024-10-13T22:01:50Z","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"},{"name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","grant_number":"I05982"},{"_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"}],"year":"2024","alternative_title":["LIPIcs"],"volume":308,"tmp":{"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)","image":"/images/cc_by.png"},"citation":{"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>","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>.","short":"M.D. La Tour, M. Henzinger, D. Saulpic, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.","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.","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>.","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>","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."},"department":[{"_id":"MoHe"}],"das_tickbox":"0","publication_status":"published","supplementarymaterial":"no","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773386"]},"has_accepted_license":"1","external_id":{"arxiv":["2406.19926"],"isi":["001545622400100"]},"file":[{"content_type":"application/pdf","date_updated":"2024-10-21T09:41:48Z","date_created":"2024-10-21T09:41:48Z","file_name":"2024_LIPICs_DuprelaTour.pdf","file_id":"18454","access_level":"open_access","success":1,"creator":"dernst","checksum":"8e8c0b13049f11bb0133dfac22e32718","file_size":873561,"relation":"main_file"}],"ddc":["000"],"language":[{"iso":"eng"}]},{"conference":{"name":"ESA: European Symposium on Algorithms","location":"London, United Kingdom","start_date":"2024-09-02","end_date":"2024-09-04"},"researchdata_availability":"no","article_number":"72","month":"09","author":[{"last_name":"Hu","first_name":"Bingbing","full_name":"Hu, Bingbing"},{"full_name":"Kosinas, Evangelos","first_name":"Evangelos","id":"4c7f9625-dbbc-11ee-9d86-bdcc2db5a949","last_name":"Kosinas"},{"full_name":"Polak, Adam","first_name":"Adam","last_name":"Polak"}],"fulldoi":"https://doi.org/10.4230/LIPIcs.ESA.2024.72","type":"conference","abstract":[{"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 Õ(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 Õ(η⁴), 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.","lang":"eng"}],"file_date_updated":"2024-10-21T10:03:48Z","isi":1,"doi":"10.4230/LIPIcs.ESA.2024.72","article_processing_charge":"Yes","corr_author":"1","quality_controlled":"1","OA_type":"gold","OA_place":"publisher","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","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","scopus_import":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","title":"Connectivity oracles for predictable vertex failures","date_published":"2024-09-01T00:00:00Z","intvolume":"       308","publication":"32nd Annual European Symposium on Algorithms","arxiv":1,"day":"01","date_updated":"2026-10-21T08:04:56Z","date_created":"2024-10-13T22:01:50Z","_id":"18309","oa":1,"status":"public","oa_version":"Published Version","year":"2024","alternative_title":["LIPIcs"],"citation":{"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>.","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>","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.","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."},"department":[{"_id":"MoHe"}],"tmp":{"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)","image":"/images/cc_by.png"},"volume":308,"supplementarymaterial":"no","das_tickbox":"0","publication_status":"published","has_accepted_license":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959773386"]},"file":[{"access_level":"open_access","file_id":"18455","content_type":"application/pdf","date_updated":"2024-10-21T10:03:48Z","file_name":"2024_LIPICs_Hu.pdf","date_created":"2024-10-21T10:03:48Z","file_size":853914,"relation":"main_file","checksum":"ab1f2f9161549a8763eda15db40e022c","success":1,"creator":"dernst"}],"external_id":{"isi":["001545622400072"],"arxiv":["2312.08489"]},"language":[{"iso":"eng"}],"ddc":["000"]},{"conference":{"start_date":"2024-07-21","location":"Vienna, Austria","name":"ICML: International Conference on Machine Learning","end_date":"2024-07-27"},"ec_funded":1,"month":"09","author":[{"first_name":"Kyriakos","full_name":"Axiotis, Kyriakos","last_name":"Axiotis"},{"full_name":"Cohen-Addad, Vincent","first_name":"Vincent","last_name":"Cohen-Addad"},{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Jerome","first_name":"Sammy","full_name":"Jerome, Sammy"},{"full_name":"Mirrokni, Vahab","first_name":"Vahab","last_name":"Mirrokni"},{"first_name":"David","full_name":"Saulpic, David","id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964","last_name":"Saulpic"},{"first_name":"David P.","full_name":"Woodruff, David P.","last_name":"Woodruff"},{"last_name":"Wunder","full_name":"Wunder, Michael","first_name":"Michael"}],"researchdata_availability":"no","type":"conference","abstract":[{"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.","lang":"eng"}],"quality_controlled":"1","article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","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.","page":"2086-2107","scopus_import":"1","intvolume":"       235","title":"Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond","date_published":"2024-09-01T00:00:00Z","publisher":"ML Research Press","arxiv":1,"day":"01","publication":"Proceedings of the 41st International Conference on Machine Learning","oa_version":"Published Version","status":"public","oa":1,"_id":"18115","date_created":"2024-09-22T22:01:44Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2402.17327"}],"date_updated":"2026-10-21T08:03:43Z","project":[{"_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures","call_identifier":"H2020","grant_number":"101019564"},{"_id":"34def286-11ca-11ed-8bc3-da5948e1613c","name":"Efficient algorithms","grant_number":"Z00422"},{"grant_number":"I05982","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103","name":"Static and Dynamic Hierarchical Graph Decompositions"},{"grant_number":"P33775","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer"},{"_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413","call_identifier":"H2020"}],"alternative_title":["PMLR"],"year":"2024","volume":235,"department":[{"_id":"MoHe"}],"citation":{"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.","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.","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.","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.","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."},"publication_status":"published","das_tickbox":"0","supplementarymaterial":"no","publication_identifier":{"eissn":["2640-3498"]},"external_id":{"arxiv":["2402.17327"]},"ddc":["000"],"language":[{"iso":"eng"}]},{"doi":"10.1137/1.9781611977912.111","article_processing_charge":"No","corr_author":"1","quality_controlled":"1","OA_type":"free access","OA_place":"repository","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.","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","scopus_import":"1","page":"3089-3139","publisher":"Society for Industrial and Applied Mathematics","title":"Deterministic near-linear time minimum cut in weighted graphs","date_published":"2024-01-04T00:00:00Z","ec_funded":1,"conference":{"end_date":"2024-01-10","name":"SODA: Symposium on Discrete Algorithms","location":"Alexandria, VA,  United States","start_date":"2024-01-07"},"researchdata_availability":"no","month":"01","author":[{"orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Li","first_name":"Jason","full_name":"Li, Jason"},{"last_name":"Rao","first_name":"Satish","full_name":"Rao, Satish"},{"last_name":"Wang","full_name":"Wang, Di","first_name":"Di"}],"fulldoi":"https://doi.org/10.1137/1.9781611977912.111","type":"conference","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"}],"supplementarymaterial":"yes","das_tickbox":"0","publication_status":"published","publication_identifier":{"eisbn":["9781611977912"]},"external_id":{"arxiv":["2401.05627"]},"language":[{"iso":"eng"}],"publication":"35th Annual ACM-SIAM Symposium on Discrete Algorithms","arxiv":1,"day":"04","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2401.05627"}],"date_updated":"2026-10-21T08:05:18Z","_id":"18503","oa":1,"date_created":"2024-11-04T10:54:21Z","status":"public","oa_version":"Preprint","year":"2024","project":[{"name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020"},{"name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","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"}],"citation":{"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.","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.","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>.","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.","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>","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>."},"department":[{"_id":"MoHe"}]},{"conference":{"start_date":"2024-07-21","location":"Vienna, Austria","name":"ICML: International Conference on Machine Learning","end_date":"2024-07-27"},"ec_funded":1,"author":[{"first_name":"Max Dupré","full_name":"La Tour, Max Dupré","last_name":"La Tour"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Saulpic","id":"f8e48cf0-b0ff-11ed-b0e9-b4c35598f964","first_name":"David","full_name":"Saulpic, David"}],"month":"09","researchdata_availability":"no","type":"conference","abstract":[{"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.","lang":"eng"}],"quality_controlled":"1","corr_author":"1","article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","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.","scopus_import":"1","page":"12046-12086","intvolume":"       235","date_published":"2024-09-01T00:00:00Z","title":"Making old things new: A unified algorithm for differentially private clustering","publisher":"ML Research Press","publication":"Proceedings of the 41st International Conference on Machine Learning","day":"01","arxiv":1,"oa_version":"Published Version","status":"public","_id":"18116","oa":1,"date_created":"2024-09-22T22:01:44Z","date_updated":"2026-10-21T08:04:04Z","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2406.11649","open_access":"1"}],"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","_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","name":"Fast Algorithms for a Reactive Network Layer","_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe"},{"name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","call_identifier":"H2020"}],"year":"2024","alternative_title":["PMLR"],"volume":235,"department":[{"_id":"MoHe"}],"citation":{"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.","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.","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.","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.","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."},"publication_status":"published","das_tickbox":"0","supplementarymaterial":"no","publication_identifier":{"eissn":["2640-3498"]},"external_id":{"arxiv":["2406.11649"]},"ddc":["000"],"language":[{"iso":"eng"}]},{"supplementarymaterial":"no","publication_status":"published","das_tickbox":"0","publication_identifier":{"eisbn":["9781611977912"]},"external_id":{"arxiv":["2307.08970"]},"language":[{"iso":"eng"}],"publication":"Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms","arxiv":1,"day":"04","oa":1,"_id":"15253","date_created":"2024-03-31T22:01:13Z","date_updated":"2026-10-21T08:03:24Z","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2307.08970","open_access":"1"}],"oa_version":"Preprint","status":"public","year":"2024","project":[{"name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","call_identifier":"H2020"},{"name":"Efficient algorithms","_id":"34def286-11ca-11ed-8bc3-da5948e1613c","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"}],"department":[{"_id":"MoHe"}],"citation":{"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>","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.","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.","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>","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>.","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."},"volume":2024,"article_processing_charge":"No","doi":"10.1137/1.9781611977912.38","quality_controlled":"1","corr_author":"1","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","page":"995-1018","scopus_import":"1","publisher":"Society for Industrial and Applied Mathematics","intvolume":"      2024","date_published":"2024-01-04T00:00:00Z","title":"A unifying framework for differentially private sums under continual observation","ec_funded":1,"conference":{"end_date":"2024-01-10","location":"Alexandria, VA, United States","name":"SODA: Symposium on Discrete Algorithms","start_date":"2024-01-07"},"researchdata_availability":"no","author":[{"orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"first_name":"Jalaj","full_name":"Upadhyay, Jalaj","last_name":"Upadhyay"},{"first_name":"Sarvagya","full_name":"Upadhyay, Sarvagya","last_name":"Upadhyay"}],"month":"01","fulldoi":"https://doi.org/10.1137/1.9781611977912.38","type":"conference","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"}]},{"page":"62:1-62:25","scopus_import":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2024-01-24T00:00:00Z","title":"On the complexity of algorithms with predictions for dynamic graph problems","intvolume":"       287","doi":"10.4230/LIPIcs.ITCS.2024.62","article_processing_charge":"Yes","corr_author":"1","quality_controlled":"1","OA_type":"gold","OA_place":"publisher","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","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.","fulldoi":"https://doi.org/10.4230/LIPIcs.ITCS.2024.62","type":"conference","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."}],"file_date_updated":"2025-01-27T15:33:24Z","isi":1,"ec_funded":1,"conference":{"end_date":"2024-02-02","name":"ITCS: Innovations in Theoretical Computer Science","location":"Berkeley, CA, United States","start_date":"2024-01-30"},"researchdata_availability":"no","month":"01","author":[{"orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"},{"last_name":"Saha","full_name":"Saha, Barna","first_name":"Barna"},{"full_name":"Seybold, Martin P.","first_name":"Martin P.","last_name":"Seybold"},{"full_name":"Ye, Christopher","first_name":"Christopher","last_name":"Ye"}],"file":[{"success":1,"creator":"dernst","checksum":"15085a5b3697a408b92a4a7a27293927","file_size":1084372,"relation":"main_file","content_type":"application/pdf","date_updated":"2025-01-27T15:33:24Z","file_name":"2024_LIPICs_HenzingerMo.pdf","date_created":"2025-01-27T15:33:24Z","file_id":"18929","access_level":"open_access"}],"external_id":{"isi":["001300389400062"],"arxiv":["2307.16771"]},"language":[{"iso":"eng"}],"ddc":["000"],"supplementarymaterial":"no","das_tickbox":"0","publication_status":"published","has_accepted_license":"1","publication_identifier":{"eissn":["1868-8969"],"isbn":["9783959773096"]},"alternative_title":["LIPIcs"],"year":"2024","project":[{"grant_number":"101019564","call_identifier":"H2020","name":"The design and evaluation of modern fully dynamic data structures","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62"},{"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"},{"_id":"bd9e3a2e-d553-11ed-ba76-8aa684ce17fe","name":"Fast Algorithms for a Reactive Network Layer","grant_number":"P33775"}],"citation":{"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>.","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>.","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.","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>","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."},"department":[{"_id":"MoHe"}],"volume":287,"tmp":{"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)","image":"/images/cc_by.png"},"arxiv":1,"day":"24","publication":"15th Innovations in Theoretical Computer Science Conference","date_updated":"2026-10-21T08:07:36Z","oa":1,"_id":"18928","date_created":"2025-01-27T15:33:42Z","status":"public","oa_version":"Published Version"}]