[{"language":[{"iso":"eng"}],"year":"2023","intvolume":"       251","editor":[{"first_name":"Yael","last_name":"Tauman Kalai","full_name":"Tauman Kalai, Yael"}],"oa":1,"conference":{"name":"ITCS: Innovations in Theoretical Computer Science","location":"Cambridge, Massachusetts, USA","start_date":"2023-01-10","end_date":"2023-01-13"},"volume":251,"publication":"14th Innovations in Theoretical Computer Science Conference","arxiv":1,"day":"01","acknowledgement":" This project has received funding from the European Research Council (ERC) under\r\nthe European Union’s Horizon 2020 research and innovation programme (grant agreement No.\r\n101019564). This work was further supported by the Austrian Science Fund (FWF) and netIDEE\r\nSCIENCE project P 33775-N, as well as the FWF project I 4800-N (ADVISE)","scopus_import":"1","file":[{"checksum":"d7f45fdcbc5fccd61db69f56d775c636","success":1,"creator":"cchlebak","relation":"main_file","access_level":"open_access","file_id":"22383","file_size":1077427,"date_created":"2026-07-22T08:04:03Z","date_updated":"2026-07-22T08:04:03Z","file_name":"2023_LIPIcs_El-Hayek.pdf","content_type":"application/pdf"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772631"]},"author":[{"orcid":"0000-0003-4268-7368","first_name":"Antoine","full_name":"El-Hayek, Antoine","id":"888a098e-fcac-11ee-aff7-d347be57b725","last_name":"El-Hayek"},{"first_name":"Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Schmid","full_name":"Schmid, Stefan","orcid":"0000-0002-7798-1711","first_name":"Stefan"}],"quality_controlled":"1","title":"Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks","_id":"22373","date_created":"2026-07-20T11:45:04Z","extern":"1","file_date_updated":"2026-07-22T08:04:03Z","article_number":"47","alternative_title":["LIPIcs"],"has_accepted_license":"1","article_processing_charge":"No","fulldoi":"https://doi.org/10.4230/LIPICS.ITCS.2023.47","date_updated":"2026-07-24T12:48:29Z","publication_status":"published","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","keyword":["broadcast","cover","k-broadcast","dynamic radius","dynamic graphs","oblivious message adversary","time complexity","Theory of computation → Distributed algorithms","Networks → Network algorithms"],"abstract":[{"lang":"eng","text":"Data dissemination is a fundamental task in distributed computing. This paper studies broadcast problems in various innovative models where the communication network connecting n processes is dynamic (e.g., due to mobility or failures) and controlled by an adversary. \r\nIn the first model, the processes transitively communicate their ids in synchronous rounds along a rooted tree given in each round by the adversary whose goal is to maximize the number of rounds until at least one id is known by all processes. Previous research has shown a ⌈(3n-1)/2⌉-2 lower bound and an O(nlog log n) upper bound. We show the first linear upper bound for this problem, namely ⌈(1+√2) n-1⌉ ≈ 2.4n.\r\nWe extend these results to the setting where the adversary gives in each round k-disjoint forests and their goal is to maximize the number of rounds until there is a set of k ids such that each process knows of at least one of them. We give a ⌈3(n-k)/2⌉-1 lower bound and a (π²+6)/6 n+1 ≈ 2.6n upper bound for this problem.\r\nFinally, we study the setting where the adversary gives in each round a directed graph with k roots and their goal is to maximize the number of rounds until there exist k ids that are known by all processes. We give a ⌈3(n-3k)/2⌉+2 lower bound and a ⌈(1+√2)n⌉+k-1 ≈ 2.4n+k upper bound for this problem.\r\nFor the two latter problems no upper or lower bounds were previously known."}],"related_material":{"record":[{"relation":"dissertation_contains","id":"22281","status":"public"}]},"month":"02","type":"conference","external_id":{"arxiv":["2211.10151"]},"oa_version":"Published Version","citation":{"short":"A. El-Hayek, M. Henzinger, S. Schmid, in:, Y. Tauman Kalai (Ed.), 14th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","ieee":"A. El-Hayek, M. Henzinger, and S. Schmid, “Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks,” in <i>14th Innovations in Theoretical Computer Science Conference</i>, Cambridge, Massachusetts, USA, 2023, vol. 251.","chicago":"El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks.” In <i>14th Innovations in Theoretical Computer Science Conference</i>, edited by Yael Tauman Kalai, Vol. 251. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPICS.ITCS.2023.47\">https://doi.org/10.4230/LIPICS.ITCS.2023.47</a>.","ista":"El-Hayek A, Henzinger M, Schmid S. 2023. Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks. 14th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 251, 47.","ama":"El-Hayek A, Henzinger M, Schmid S. Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks. In: Tauman Kalai Y, ed. <i>14th Innovations in Theoretical Computer Science Conference</i>. Vol 251. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPICS.ITCS.2023.47\">10.4230/LIPICS.ITCS.2023.47</a>","apa":"El-Hayek, A., Henzinger, M., &#38; Schmid, S. (2023). Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks. In Y. Tauman Kalai (Ed.), <i>14th Innovations in Theoretical Computer Science Conference</i> (Vol. 251). Cambridge, Massachusetts, USA: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ITCS.2023.47\">https://doi.org/10.4230/LIPICS.ITCS.2023.47</a>","mla":"El-Hayek, Antoine, et al. “Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks.” <i>14th Innovations in Theoretical Computer Science Conference</i>, edited by Yael Tauman Kalai, vol. 251, 47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPICS.ITCS.2023.47\">10.4230/LIPICS.ITCS.2023.47</a>."},"ddc":["000"],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png"},"date_published":"2023-02-01T00:00:00Z","doi":"10.4230/LIPICS.ITCS.2023.47","status":"public"},{"_id":"22534","date_created":"2026-07-27T12:30:24Z","page":"3085-3097","extern":"1","quality_controlled":"1","title":"Satellite‐based evidence highlights a considerable increase of urban tree cooling benefits from 2000 to 2015","article_type":"original","author":[{"first_name":"Jiacheng","full_name":"Zhao, Jiacheng","last_name":"Zhao"},{"full_name":"Zhao, Xiang","last_name":"Zhao","first_name":"Xiang"},{"first_name":"Donghai","full_name":"Wu, Donghai","last_name":"Wu"},{"last_name":"Meili","full_name":"Meili, Naika","first_name":"Naika"},{"full_name":"Fatichi, Simone","last_name":"Fatichi","id":"cf8e546b-a9b0-11f0-a43b-aa89ed1b56d6","first_name":"Simone"}],"publisher":"Wiley","publication_identifier":{"issn":["1354-1013"],"eissn":["1365-2486"]},"scopus_import":"1","day":"01","publication":"Global Change Biology","volume":29,"intvolume":"        29","year":"2023","language":[{"iso":"eng"}],"status":"public","OA_type":"closed access","doi":"10.1111/gcb.16667","date_published":"2023-06-01T00:00:00Z","citation":{"ista":"Zhao J, Zhao X, Wu D, Meili N, Fatichi S. 2023. Satellite‐based evidence highlights a considerable increase of urban tree cooling benefits from 2000 to 2015. Global Change Biology. 29(11), 3085–3097.","ama":"Zhao J, Zhao X, Wu D, Meili N, Fatichi S. Satellite‐based evidence highlights a considerable increase of urban tree cooling benefits from 2000 to 2015. <i>Global Change Biology</i>. 2023;29(11):3085-3097. doi:<a href=\"https://doi.org/10.1111/gcb.16667\">10.1111/gcb.16667</a>","chicago":"Zhao, Jiacheng, Xiang Zhao, Donghai Wu, Naika Meili, and Simone Fatichi. “Satellite‐based Evidence Highlights a Considerable Increase of Urban Tree Cooling Benefits from 2000 to 2015.” <i>Global Change Biology</i>. Wiley, 2023. <a href=\"https://doi.org/10.1111/gcb.16667\">https://doi.org/10.1111/gcb.16667</a>.","ieee":"J. Zhao, X. Zhao, D. Wu, N. Meili, and S. Fatichi, “Satellite‐based evidence highlights a considerable increase of urban tree cooling benefits from 2000 to 2015,” <i>Global Change Biology</i>, vol. 29, no. 11. Wiley, pp. 3085–3097, 2023.","short":"J. Zhao, X. Zhao, D. Wu, N. Meili, S. Fatichi, Global Change Biology 29 (2023) 3085–3097.","apa":"Zhao, J., Zhao, X., Wu, D., Meili, N., &#38; Fatichi, S. (2023). Satellite‐based evidence highlights a considerable increase of urban tree cooling benefits from 2000 to 2015. <i>Global Change Biology</i>. Wiley. <a href=\"https://doi.org/10.1111/gcb.16667\">https://doi.org/10.1111/gcb.16667</a>","mla":"Zhao, Jiacheng, et al. “Satellite‐based Evidence Highlights a Considerable Increase of Urban Tree Cooling Benefits from 2000 to 2015.” <i>Global Change Biology</i>, vol. 29, no. 11, Wiley, 2023, pp. 3085–97, doi:<a href=\"https://doi.org/10.1111/gcb.16667\">10.1111/gcb.16667</a>."},"oa_version":"None","das_tickbox":"1","external_id":{"pmid":["36876991 "]},"type":"journal_article","month":"06","abstract":[{"text":"Tree planting is a prevalent strategy to mitigate urban heat. Tree cooling efficiency(TCE), defined as the temperature reduction for a 1% tree cover increase, plays animportant role in urban climate as it regulates the capacity of trees to alter the sur-face energy and water budget. However, the spatial variation and more importantly,temporal heterogeneity of TCE in global cities are not fully explored. Here, we usedLandsat-based tree cover and land surface temperature (LST) to compare TCEs at areference air temperature and tree cover level across 806 global cities and to exploretheir potential drivers with a boosted regression tree (BRT) machine learning model.From the results, we found that TCE is spatially regulated by not only leaf area index(LAI) but climate variables and anthropogenic factors especially city albedo, withouta specific variable dominating the others. However, such spatial difference is attenu-ated by the decrease of TCE with tree cover, most pronounced in midlatitude cities.During the period 2000–2015, more than 90% of analyzed cities showed an increas-ing trend in TCE, which is likely explained by a combined result of the increase in LAI,intensified solar radiation due to decreased aerosol content, increase in urban vaporpressure deficit (VPD) and decrease of city albedo. Concurrently, significant urbanafforestation occurred across many cities showing a global city-scale mean tree coverincrease of 5.3 ± 3.8% from 2000 to 2015. Over the growing season, such increasescombined with an increasing TCE were estimated to on average yield a midday sur-face cooling of 1.5 ± 1.3°C in tree-covered urban areas. These results are offeringnew insights into the use of urban afforestation as an adaptation to global warmingand urban planners may leverage them to provide more cooling benefits if trees areprimarily planted for this purpose.","lang":"eng"}],"keyword":["Climate change","Remote sensing","Tree cooling efficiency","Tree cover","Urban afforestation"],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","fulldoi":"https://doi.org/10.1111/gcb.16667","date_updated":"2026-08-12T08:28:41Z","publication_status":"published","issue":"11","article_processing_charge":"No","pmid":1},{"extern":"1","_id":"11675","page":"1057-1080","date_created":"2022-07-27T14:31:06Z","scopus_import":"1","publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]},"publisher":"Springer Nature","author":[{"first_name":"Sayan","full_name":"Bhattacharya, Sayan","last_name":"Bhattacharya"},{"last_name":"Chakrabarty","full_name":"Chakrabarty, Deeparnab","first_name":"Deeparnab"},{"full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","orcid":"0000-0002-5008-6530"}],"article_type":"original","title":"Deterministic dynamic matching in O(1) update time","quality_controlled":"1","volume":82,"publication":"Algorithmica","day":"01","language":[{"iso":"eng"}],"year":"2020","intvolume":"        82","oa":1,"citation":{"mla":"Bhattacharya, Sayan, et al. “Deterministic Dynamic Matching in O(1) Update Time.” <i>Algorithmica</i>, vol. 82, no. 4, Springer Nature, 2020, pp. 1057–80, doi:<a href=\"https://doi.org/10.1007/s00453-019-00630-4\">10.1007/s00453-019-00630-4</a>.","apa":"Bhattacharya, S., Chakrabarty, D., &#38; Henzinger, M. (2020). Deterministic dynamic matching in O(1) update time. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00453-019-00630-4\">https://doi.org/10.1007/s00453-019-00630-4</a>","ieee":"S. Bhattacharya, D. Chakrabarty, and M. Henzinger, “Deterministic dynamic matching in O(1) update time,” <i>Algorithmica</i>, vol. 82, no. 4. Springer Nature, pp. 1057–1080, 2020.","short":"S. Bhattacharya, D. Chakrabarty, M. Henzinger, Algorithmica 82 (2020) 1057–1080.","chicago":"Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika Henzinger. “Deterministic Dynamic Matching in O(1) Update Time.” <i>Algorithmica</i>. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/s00453-019-00630-4\">https://doi.org/10.1007/s00453-019-00630-4</a>.","ama":"Bhattacharya S, Chakrabarty D, Henzinger M. Deterministic dynamic matching in O(1) update time. <i>Algorithmica</i>. 2020;82(4):1057-1080. doi:<a href=\"https://doi.org/10.1007/s00453-019-00630-4\">10.1007/s00453-019-00630-4</a>","ista":"Bhattacharya S, Chakrabarty D, Henzinger M. 2020. Deterministic dynamic matching in O(1) update time. Algorithmica. 82(4), 1057–1080."},"date_published":"2020-04-01T00:00:00Z","doi":"10.1007/s00453-019-00630-4","status":"public","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s00453-019-00630-4"}],"abstract":[{"lang":"eng","text":"We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld (in: Proceedings of the ACM symposium on theory of computing (STOC), 2010), this problem has received significant attention in recent years. Very recently, extending the framework of Baswana et al. (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2011) , Solomon (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2016) gave a randomized dynamic algorithm for this problem that has an approximation ratio of 2 and an amortized update time of O(1) with high probability. This algorithm requires the assumption of an oblivious adversary, meaning that the future sequence of edge insertions/deletions in the graph cannot depend in any way on the algorithm’s past output. A natural way to remove the assumption on oblivious adversary is to give a deterministic dynamic algorithm for the same problem in O(1) update time. In this paper, we resolve this question. We present a new deterministic fully dynamic algorithm that maintains a O(1)-approximate minimum vertex cover and maximum fractional matching, with an amortized update time of O(1). Previously, the best deterministic algorithm for this problem was due to Bhattacharya et al. (in: Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), 2015); it had an approximation ratio of (2+ε) and an amortized update time of O(logn/ε2). Our result can be generalized to give a fully dynamic O(f3)-approximate algorithm with O(f2) amortized update time for the hypergraph vertex cover and fractional hypergraph matching problem, where every hyperedge has at most f vertices."}],"month":"04","type":"journal_article","oa_version":"Published Version","issue":"4","publication_status":"published","date_updated":"2024-11-06T12:07:43Z","fulldoi":"https://doi.org/10.1007/s00453-019-00630-4","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","keyword":["Dynamic algorithms","Data structures","Graph algorithms","Matching","Vertex cover"],"article_processing_charge":"No"}]