[{"title":"A deamortization approach for dynamic spanner and dynamic maximal matching","main_file_link":[{"url":"https://arxiv.org/abs/1810.10932","open_access":"1"}],"external_id":{"arxiv":["1810.10932"]},"author":[{"last_name":"Bernstein","first_name":"Aaron","full_name":"Bernstein, Aaron"},{"last_name":"Forster","full_name":"Forster, Sebastian","first_name":"Sebastian"},{"full_name":"Henzinger, Monika H","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"}],"oa_version":"Preprint","issue":"4","publication":"ACM Transactions on Algorithms","day":"04","abstract":[{"text":"Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, where each individual operation has to be executed quickly. For this reason, there exist many recent randomized results that aim to provide a guarantee stronger than amortized expected. The strongest possible guarantee for a randomized algorithm is that it is always correct (Las Vegas) and has high-probability worst-case update time, which gives a bound on the time for each individual operation that holds with high probability.\r\n\r\nIn this article, we present the first polylogarithmic high-probability worst-case time bounds for the dynamic spanner and the dynamic maximal matching problem.\r\n\r\n(1)\r\n\r\nFor dynamic spanner, the only known o(n) worst-case bounds were O(n3/4) high-probability worst-case update time for maintaining a 3-spanner and O(n5/9) for maintaining a 5-spanner. We give a O(1)k log3 (n) high-probability worst-case time bound for maintaining a (2k-1)-spanner, which yields the first worst-case polylog update time for all constant k. (All the results above maintain the optimal tradeoff of stretch 2k-1 and Õ(n1+1/k) edges.)\r\n\r\n(2)\r\n\r\nFor dynamic maximal matching, or dynamic 2-approximate maximum matching, no algorithm with o(n) worst-case time bound was known and we present an algorithm with O(log 5 (n)) high-probability worst-case time; similar worst-case bounds existed only for maintaining a matching that was (2+ϵ)-approximate, and hence not maximal.\r\n\r\nOur results are achieved using a new approach for converting amortized guarantees to worst-case ones for randomized data structures by going through a third type of guarantee, which is a middle ground between the two above: An algorithm is said to have worst-case expected update time ɑ if for every update σ, the expected time to process σ is at most ɑ. Although stronger than amortized expected, the worst-case expected guarantee does not resolve the fundamental problem of amortization: A worst-case expected update time of O(1) still allows for the possibility that every 1/f(n) updates requires ϴ (f(n)) time to process, for arbitrarily high f(n). In this article, we present a black-box reduction that converts any data structure with worst-case expected update time into one with a high-probability worst-case update time: The query time remains the same, while the update time increases by a factor of O(log 2(n)).\r\n\r\nThus, we achieve our results in two steps:\r\n\r\n(1) First, we show how to convert existing dynamic graph algorithms with amortized expected polylogarithmic running times into algorithms with worst-case expected polylogarithmic running times.\r\n\r\n(2) Then, we use our black-box reduction to achieve the polylogarithmic high-probability worst-case time bound. All our algorithms are Las-Vegas-type algorithms.","lang":"eng"}],"extern":"1","publication_status":"published","scopus_import":"1","article_number":"29","date_published":"2021-10-04T00:00:00Z","article_processing_charge":"No","month":"10","volume":17,"oa":1,"citation":{"short":"A. Bernstein, S. Forster, M. Henzinger, ACM Transactions on Algorithms 17 (2021).","ista":"Bernstein A, Forster S, Henzinger M. 2021. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms. 17(4), 29.","ama":"Bernstein A, Forster S, Henzinger M. A deamortization approach for dynamic spanner and dynamic maximal matching. <i>ACM Transactions on Algorithms</i>. 2021;17(4). doi:<a href=\"https://doi.org/10.1145/3469833\">10.1145/3469833</a>","chicago":"Bernstein, Aaron, Sebastian Forster, and Monika Henzinger. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.” <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3469833\">https://doi.org/10.1145/3469833</a>.","ieee":"A. Bernstein, S. Forster, and M. Henzinger, “A deamortization approach for dynamic spanner and dynamic maximal matching,” <i>ACM Transactions on Algorithms</i>, vol. 17, no. 4. Association for Computing Machinery, 2021.","mla":"Bernstein, Aaron, et al. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.” <i>ACM Transactions on Algorithms</i>, vol. 17, no. 4, 29, Association for Computing Machinery, 2021, doi:<a href=\"https://doi.org/10.1145/3469833\">10.1145/3469833</a>.","apa":"Bernstein, A., Forster, S., &#38; Henzinger, M. (2021). A deamortization approach for dynamic spanner and dynamic maximal matching. <i>ACM Transactions on Algorithms</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3469833\">https://doi.org/10.1145/3469833</a>"},"date_created":"2022-07-27T11:09:06Z","arxiv":1,"language":[{"iso":"eng"}],"publication_identifier":{"issn":["1549-6325"],"eissn":["1549-6333"]},"quality_controlled":"1","_id":"11663","year":"2021","article_type":"original","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","type":"journal_article","publisher":"Association for Computing Machinery","date_updated":"2024-11-06T12:05:37Z","intvolume":"        17","doi":"10.1145/3469833","acknowledgement":"The conference version of this article [10] had an error in the analysis of the dynamic matching algorithm. In particular, Lemma 4.5 assumed an independence between adversarial updates to the hierarchy that is in fact true, but which requires a sophisticated proof. We are very grateful to the anonymous reviewers of Transactions on Algorithms for pointing out this mistake in our analysis. The mistake is fixed in Section 4.5. Almost the entire fix is a matter of analysis: the only change to the algorithm itself is the introduction of responsible bits in Algorithm 2. The first author would like to thank Mikkel Thorup and Alan Roytman for a very helpful discussion of the proof of Theorem 1.1."},{"year":"2021","_id":"11756","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_type":"original","intvolume":"       281","type":"journal_article","publisher":"Elsevier","status":"public","date_updated":"2024-11-06T12:09:22Z","doi":"10.1016/j.ic.2021.104805","date_published":"2021-12-01T00:00:00Z","citation":{"apa":"Henzinger, M., &#38; Peng, P. (2021). Constant-time dynamic weight approximation for minimum spanning forest. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2021.104805\">https://doi.org/10.1016/j.ic.2021.104805</a>","mla":"Henzinger, Monika, and Pan Peng. “Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest.” <i>Information and Computation</i>, vol. 281, no. 12, 104805, Elsevier, 2021, doi:<a href=\"https://doi.org/10.1016/j.ic.2021.104805\">10.1016/j.ic.2021.104805</a>.","ieee":"M. Henzinger and P. Peng, “Constant-time dynamic weight approximation for minimum spanning forest,” <i>Information and Computation</i>, vol. 281, no. 12. Elsevier, 2021.","ama":"Henzinger M, Peng P. Constant-time dynamic weight approximation for minimum spanning forest. <i>Information and Computation</i>. 2021;281(12). doi:<a href=\"https://doi.org/10.1016/j.ic.2021.104805\">10.1016/j.ic.2021.104805</a>","chicago":"Henzinger, Monika, and Pan Peng. “Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest.” <i>Information and Computation</i>. Elsevier, 2021. <a href=\"https://doi.org/10.1016/j.ic.2021.104805\">https://doi.org/10.1016/j.ic.2021.104805</a>.","ista":"Henzinger M, Peng P. 2021. Constant-time dynamic weight approximation for minimum spanning forest. Information and Computation. 281(12), 104805.","short":"M. Henzinger, P. Peng, Information and Computation 281 (2021)."},"month":"12","volume":281,"article_processing_charge":"No","oa":1,"date_created":"2022-08-08T10:58:29Z","arxiv":1,"quality_controlled":"1","publication_identifier":{"issn":["0890-5401"]},"language":[{"iso":"eng"}],"oa_version":"Preprint","day":"01","abstract":[{"lang":"eng","text":"We give two fully dynamic algorithms that maintain a (1 + ε)-approximation of the weight M of a minimum spanning forest (MSF) of an n-node graph G with edges weights in [1, W ], for any ε > 0. (1) Our deterministic algorithm takes O (W 2 log W /ε3) worst-case update time, which is O (1) if both W and ε are constants. (2) Our randomized (Monte-Carlo style) algorithm works with high probability and runs in worst-case O (log W /ε4) update time if W = O ((m∗)1/6/log2/3 n), where m∗ is the minimum number of edges in the graph throughout all the updates. It works even against an adaptive adversary. We complement our algorithmic results with two cell-probe lower bounds for dynamically maintaining an approximation of the weight of an MSF of a graph."}],"publication":"Information and Computation","issue":"12","scopus_import":"1","publication_status":"published","extern":"1","article_number":"104805","title":"Constant-time dynamic weight approximation for minimum spanning forest","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2011.00977"}],"external_id":{"arxiv":["2011.00977"]},"author":[{"full_name":"Henzinger, Monika H","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"first_name":"Pan","full_name":"Peng, Pan","last_name":"Peng"}]},{"main_file_link":[{"url":"https://arxiv.org/abs/1910.03332","open_access":"1"}],"title":"Upper and lower bounds for fully retroactive graph problems","author":[{"full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"last_name":"Wu","first_name":"Xiaowei","full_name":"Wu, Xiaowei"}],"external_id":{"arxiv":["1910.03332"]},"day":"09","abstract":[{"lang":"eng","text":"Classic dynamic data structure problems maintain a data structure subject to a sequence S of updates and they answer queries using the latest version of the data structure, i.e., the data structure after processing the whole sequence. To handle operations that change the sequence S of updates, Demaine et al. [7] introduced retroactive data structures (RDS). A retroactive operation modifies the update sequence S in a given position t, called time, and either creates or cancels an update in S at time t. A fully retroactive data structure supports queries at any time t: a query at time t is answered using only the updates of S up to time t. While efficient RDS have been proposed for classic data structures, e.g., stack, priority queue and binary search tree, the retroactive version of graph problems are rarely studied.\r\n\r\nIn this paper we study retroactive graph problems including connectivity, minimum spanning forest (MSF), maximum degree, etc. We show that under the OMv conjecture (proposed by Henzinger et al. [15]), there does not exist fully RDS maintaining connectivity or MSF, or incremental fully RDS maintaining the maximum degree with 𝑂(𝑛1−𝜖) time per operation, for any constant 𝜖>0. Furthermore, We provide RDS with almost tight time per operation. We give fully RDS for maintaining the maximum degree, connectivity and MSF in 𝑂̃ (𝑛) time per operation. We also give an algorithm for the incremental (insertion-only) fully retroactive connectivity with 𝑂̃ (1) time per operation, showing that the lower bound cannot be extended to this setting.\r\n\r\nWe also study a restricted version of RDS, where the only change to S is the swap of neighboring updates and show that for this problem we can beat the above hardness result. This also implies the first non-trivial dynamic Reeb graph computation algorithm."}],"publication":"17th International Symposium on Algorithms and Data Structures","oa_version":"Preprint","alternative_title":["LNCS"],"scopus_import":"1","extern":"1","publication_status":"published","citation":{"apa":"Henzinger, M., &#38; Wu, X. (2021). Upper and lower bounds for fully retroactive graph problems. In <i>17th International Symposium on Algorithms and Data Structures</i> (Vol. 12808, pp. 471–484). Virtual: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-83508-8_34\">https://doi.org/10.1007/978-3-030-83508-8_34</a>","ieee":"M. Henzinger and X. Wu, “Upper and lower bounds for fully retroactive graph problems,” in <i>17th International Symposium on Algorithms and Data Structures</i>, Virtual, 2021, vol. 12808, pp. 471–484.","mla":"Henzinger, Monika, and Xiaowei Wu. “Upper and Lower Bounds for Fully Retroactive Graph Problems.” <i>17th International Symposium on Algorithms and Data Structures</i>, vol. 12808, Springer Nature, 2021, pp. 471–484, doi:<a href=\"https://doi.org/10.1007/978-3-030-83508-8_34\">10.1007/978-3-030-83508-8_34</a>.","ama":"Henzinger M, Wu X. Upper and lower bounds for fully retroactive graph problems. In: <i>17th International Symposium on Algorithms and Data Structures</i>. Vol 12808. Springer Nature; 2021:471–484. doi:<a href=\"https://doi.org/10.1007/978-3-030-83508-8_34\">10.1007/978-3-030-83508-8_34</a>","chicago":"Henzinger, Monika, and Xiaowei Wu. “Upper and Lower Bounds for Fully Retroactive Graph Problems.” In <i>17th International Symposium on Algorithms and Data Structures</i>, 12808:471–484. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-83508-8_34\">https://doi.org/10.1007/978-3-030-83508-8_34</a>.","ista":"Henzinger M, Wu X. 2021. Upper and lower bounds for fully retroactive graph problems. 17th International Symposium on Algorithms and Data Structures. WADS: Workshop on Algorithms and Data Structures, LNCS, vol. 12808, 471–484.","short":"M. Henzinger, X. Wu, in:, 17th International Symposium on Algorithms and Data Structures, Springer Nature, 2021, pp. 471–484."},"oa":1,"month":"08","volume":12808,"article_processing_charge":"No","date_published":"2021-08-09T00:00:00Z","publication_identifier":{"isbn":["9783030835071"],"eissn":["1611-3349"],"eisbn":["9783030835088"],"issn":["0302-9743"]},"quality_controlled":"1","language":[{"iso":"eng"}],"conference":{"name":"WADS: Workshop on Algorithms and Data Structures","end_date":"2021-08-11","location":"Virtual","start_date":"2021-08-09"},"arxiv":1,"date_created":"2022-08-08T13:01:29Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2021","_id":"11771","page":"471–484","doi":"10.1007/978-3-030-83508-8_34","intvolume":"     12808","date_updated":"2024-11-06T12:10:14Z","publisher":"Springer Nature","status":"public","type":"conference"},{"language":[{"iso":"eng"}],"quality_controlled":"1","publication_identifier":{"isbn":["9783959772044"],"issn":["1868-8969"]},"arxiv":1,"date_created":"2022-08-12T07:04:44Z","conference":{"location":"Lisbon, Portual","start_date":"2021-09-06","name":"ESA: Annual European Symposium on Algorithms","end_date":"2021-09-08"},"oa":1,"month":"08","article_processing_charge":"No","volume":204,"citation":{"apa":"Fichtenberger, H., Henzinger, M., &#38; Ost, W. (2021). Differentially private algorithms for graphs under continual observation. In <i>29th Annual European Symposium on Algorithms</i> (Vol. 204). Lisbon, Portual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2021.42\">https://doi.org/10.4230/LIPIcs.ESA.2021.42</a>","ieee":"H. Fichtenberger, M. Henzinger, and W. Ost, “Differentially private algorithms for graphs under continual observation,” in <i>29th Annual European Symposium on Algorithms</i>, Lisbon, Portual, 2021, vol. 204.","mla":"Fichtenberger, Hendrik, et al. “Differentially Private Algorithms for Graphs under Continual Observation.” <i>29th Annual European Symposium on Algorithms</i>, vol. 204, 42, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2021.42\">10.4230/LIPIcs.ESA.2021.42</a>.","ama":"Fichtenberger H, Henzinger M, Ost W. Differentially private algorithms for graphs under continual observation. In: <i>29th Annual European Symposium on Algorithms</i>. Vol 204. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2021.42\">10.4230/LIPIcs.ESA.2021.42</a>","chicago":"Fichtenberger, Hendrik, Monika Henzinger, and Wolfgang Ost. “Differentially Private Algorithms for Graphs under Continual Observation.” In <i>29th Annual European Symposium on Algorithms</i>, Vol. 204. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2021.42\">https://doi.org/10.4230/LIPIcs.ESA.2021.42</a>.","ista":"Fichtenberger H, Henzinger M, Ost W. 2021. Differentially private algorithms for graphs under continual observation. 29th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 204, 42.","short":"H. Fichtenberger, M. Henzinger, W. Ost, in:, 29th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021."},"date_published":"2021-08-31T00:00:00Z","doi":"10.4230/LIPIcs.ESA.2021.42","date_updated":"2024-11-06T08:22:28Z","status":"public","type":"conference","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","intvolume":"       204","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11814","year":"2021","author":[{"last_name":"Fichtenberger","first_name":"Hendrik","full_name":"Fichtenberger, Hendrik"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530"},{"last_name":"Ost","first_name":"Wolfgang","full_name":"Ost, Wolfgang"}],"external_id":{"arxiv":["2106.14756"]},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.ESA.2021.42"}],"title":"Differentially private algorithms for graphs under continual observation","alternative_title":["LIPIcs"],"article_number":"42","extern":"1","publication_status":"published","scopus_import":"1","publication":"29th Annual European Symposium on Algorithms","abstract":[{"text":"Differentially private algorithms protect individuals in data analysis scenarios by ensuring that there is only a weak correlation between the existence of the user in the data and the result of the analysis. Dynamic graph algorithms maintain the solution to a problem (e.g., a matching) on an evolving input, i.e., a graph where nodes or edges are inserted or deleted over time. They output the value of the solution after each update operation, i.e., continuously. We study (event-level and user-level) differentially private algorithms for graph problems under continual observation, i.e., differentially private dynamic graph algorithms. We present event-level private algorithms for partially dynamic counting-based problems such as triangle count that improve the additive error by a polynomial factor (in the length T of the update sequence) on the state of the art, resulting in the first algorithms with additive error polylogarithmic in T.\r\nWe also give ε-differentially private and partially dynamic algorithms for minimum spanning tree, minimum cut, densest subgraph, and maximum matching. The additive error of our improved MST algorithm is O(W log^{3/2}T / ε), where W is the maximum weight of any edge, which, as we show, is tight up to a (√{log T} / ε)-factor. For the other problems, we present a partially-dynamic algorithm with multiplicative error (1+β) for any constant β > 0 and additive error O(W log(nW) log(T) / (ε β)). Finally, we show that the additive error for a broad class of dynamic graph algorithms with user-level privacy must be linear in the value of the output solution’s range.","lang":"eng"}],"day":"31","oa_version":"Published Version"},{"main_file_link":[{"url":"https://arxiv.org/abs/1504.07056","open_access":"1"}],"title":"A deterministic almost-tight distributed algorithm for approximating single-source shortest paths","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","last_name":"Henzinger","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Krinninger","full_name":"Krinninger, Sebastian","first_name":"Sebastian"},{"last_name":"Nanongkai","first_name":"Danupon","full_name":"Nanongkai, Danupon"}],"external_id":{"arxiv":["1504.07056"]},"day":"01","abstract":[{"lang":"eng","text":"We present a deterministic (1+𝑜(1))-approximation (𝑛1/2+𝑜(1)+𝐷1+𝑜(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the \\sf CONGEST model); here 𝑛 is the number of nodes in the network, 𝐷 is its (hop) diameter, and edge weights are positive integers from 1 to poly(𝑛). This is the first nontrivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+𝑜(1))-approximation 𝑂̃ (𝑛√𝐷1/4+𝐷)-time algorithm of Nanongkai [in Proceedings of STOC, 2014, pp. 565--573] by a factor of as large as 𝑛1/8, and (ii) the 𝑂(𝜖−1log𝜖−1)-approximation factor of Lenzen and Patt-Shamir's 𝑂̃ (𝑛1/2+𝜖+𝐷)-time algorithm [in Proceedings of STOC, 2013, pp. 381--390] within the same running time. (Throughout, we use 𝑂̃ (⋅) to hide polylogarithmic factors in 𝑛.) Our running time matches the known time lower bound of Ω(𝑛/log𝑛‾‾‾‾‾‾‾√+𝐷) [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433--456], thus essentially settling the status of this problem which was raised at least a decade ago [M. Elkin, SIGACT News, 35 (2004), pp. 40--57]. It also implies a (2+𝑜(1))-approximation (𝑛1/2+𝑜(1)+𝐷1+𝑜(1))-time algorithm for approximating a network's weighted diameter which almost matches the lower bound by Holzer and Pinsker [in Proceedings of OPODIS, 2015, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2016, 6]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the “hitting set argument” commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic construction of an (𝑛𝑜(1),𝑜(1))-hop set of size 𝑛1+𝑜(1). We combine these techniques with many distributed algorithmic techniques, some of which are from problems that are not directly related to shortest paths, e.g., ruling sets [A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, SIAM J. Discrete Math., 1 (1988), pp. 434--446], source detection [C. Lenzen and D. Peleg, in Proceedings of PODC, 2013, pp. 375--382], and partial distance estimation [C. Lenzen and B. Patt-Shamir, in Proceedings of PODC, 2015, pp. 153--162]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+𝑜(1))-approximation 𝑛𝑜(1)-time algorithm on congested cliques, and (ii) a (1+𝑜(1))-approximation 𝑛𝑜(1)-pass 𝑛1+𝑜(1)-space streaming algorithm. The first result answers an open problem in [D. Nanongkai, in Proceedings of STOC, 2014, pp. 565--573]. The second result partially answers an open problem raised by McGregor in 2006 [List of Open Problems in Sublinear Algorithms: Problem 14]."}],"publication":"SIAM Journal on Computing","issue":"3","oa_version":"Preprint","scopus_import":"1","extern":"1","publication_status":"published","citation":{"short":"M. Henzinger, S. Krinninger, D. Nanongkai, SIAM Journal on Computing 50 (2021) STOC16-98-STOC16-137.","ista":"Henzinger M, Krinninger S, Nanongkai D. 2021. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM Journal on Computing. 50(3), STOC16-98-STOC16-137.","mla":"Henzinger, Monika, et al. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” <i>SIAM Journal on Computing</i>, vol. 50, no. 3, Society for Industrial &#38; Applied Mathematics, 2021, pp. STOC16-98-STOC16-137, doi:<a href=\"https://doi.org/10.1137/16m1097808\">10.1137/16m1097808</a>.","ieee":"M. Henzinger, S. Krinninger, and D. Nanongkai, “A deterministic almost-tight distributed algorithm for approximating single-source shortest paths,” <i>SIAM Journal on Computing</i>, vol. 50, no. 3. Society for Industrial &#38; Applied Mathematics, pp. STOC16-98-STOC16-137, 2021.","apa":"Henzinger, M., Krinninger, S., &#38; Nanongkai, D. (2021). A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/16m1097808\">https://doi.org/10.1137/16m1097808</a>","chicago":"Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics, 2021. <a href=\"https://doi.org/10.1137/16m1097808\">https://doi.org/10.1137/16m1097808</a>.","ama":"Henzinger M, Krinninger S, Nanongkai D. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. <i>SIAM Journal on Computing</i>. 2021;50(3):STOC16-98-STOC16-137. doi:<a href=\"https://doi.org/10.1137/16m1097808\">10.1137/16m1097808</a>"},"article_processing_charge":"No","volume":50,"month":"05","oa":1,"date_published":"2021-05-01T00:00:00Z","quality_controlled":"1","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"language":[{"iso":"eng"}],"date_created":"2022-08-17T07:54:45Z","arxiv":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_type":"original","year":"2021","page":"STOC16-98-STOC16-137","_id":"11886","doi":"10.1137/16m1097808","intvolume":"        50","type":"journal_article","publisher":"Society for Industrial & Applied Mathematics","status":"public","date_updated":"2024-11-06T12:22:31Z"},{"doi":"10.1137/1.9781611976465.110","type":"conference","status":"public","publisher":"Society for Industrial and Applied Mathematics","date_updated":"2024-11-06T12:26:04Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2021","page":"1836-1855","_id":"11919","quality_controlled":"1","publication_identifier":{"eisbn":["978-1-61197-646-5"]},"language":[{"iso":"eng"}],"conference":{"end_date":"2021-01-13","name":"SODA: Symposium on Discrete Algorithms","location":"Alexandria, VA, United States","start_date":"2021-01-10"},"date_created":"2022-08-18T07:37:36Z","arxiv":1,"citation":{"apa":"Bergamaschi, T., Henzinger, M., Gutenberg, M. P., Williams, V. V., &#38; Wein, N. (2021). New techniques and fine-grained hardness for dynamic near-additive spanners. In <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 1836–1855). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611976465.110\">https://doi.org/10.1137/1.9781611976465.110</a>","ieee":"T. Bergamaschi, M. Henzinger, M. P. Gutenberg, V. V. Williams, and N. Wein, “New techniques and fine-grained hardness for dynamic near-additive spanners,” in <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Alexandria, VA, United States, 2021, pp. 1836–1855.","mla":"Bergamaschi, Thiago, et al. “New Techniques and Fine-Grained Hardness for Dynamic near-Additive Spanners.” <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2021, pp. 1836–55, doi:<a href=\"https://doi.org/10.1137/1.9781611976465.110\">10.1137/1.9781611976465.110</a>.","ama":"Bergamaschi T, Henzinger M, Gutenberg MP, Williams VV, Wein N. New techniques and fine-grained hardness for dynamic near-additive spanners. In: <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2021:1836-1855. doi:<a href=\"https://doi.org/10.1137/1.9781611976465.110\">10.1137/1.9781611976465.110</a>","chicago":"Bergamaschi, Thiago, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. “New Techniques and Fine-Grained Hardness for Dynamic near-Additive Spanners.” In <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 1836–55. Society for Industrial and Applied Mathematics, 2021. <a href=\"https://doi.org/10.1137/1.9781611976465.110\">https://doi.org/10.1137/1.9781611976465.110</a>.","ista":"Bergamaschi T, Henzinger M, Gutenberg MP, Williams VV, Wein N. 2021. New techniques and fine-grained hardness for dynamic near-additive spanners. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1836–1855.","short":"T. Bergamaschi, M. Henzinger, M.P. Gutenberg, V.V. Williams, N. Wein, in:, 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2021, pp. 1836–1855."},"article_processing_charge":"No","month":"01","oa":1,"date_published":"2021-01-01T00:00:00Z","scopus_import":"1","extern":"1","publication_status":"published","day":"01","abstract":[{"lang":"eng","text":"Maintaining and updating shortest paths information in a graph is a fundamental problem with many applications. As computations on dense graphs can be prohibitively expensive, and it is preferable to perform the computations on a sparse skeleton of the given graph that roughly preserves the shortest paths information. Spanners and emulators serve this purpose. Unfortunately, very little is known about dynamically maintaining sparse spanners and emulators as the graph is modified by a sequence of edge insertions and deletions. This paper develops fast dynamic algorithms for spanner and emulator maintenance and provides evidence from fine-grained complexity that these algorithms are tight. For unweighted undirected m-edge n-node graphs we obtain the following results.\r\n\r\nUnder the popular OMv conjecture, there can be no decremental or incremental algorithm that maintains an n1+o(1) edge (purely additive) +nδ-emulator for any δ < 1/2 with arbitrary polynomial preprocessing time and total update time m1+o(1). Also, under the Combinatorial k-Clique hypothesis, any fully dynamic combinatorial algorithm that maintains an n1+o(1) edge (1 + ∊, no(1))-spanner or emulator for small ∊ must either have preprocessing time mn1–o(1) or amortized update time m1–o(1). Both of our conditional lower bounds are tight.\r\n\r\nAs the above fully dynamic lower bound only applies to combinatorial algorithms, we also develop an algebraic spanner algorithm that improves over the m1–o(1) update time for dense graphs. For any constant ∊ ∊ (0, 1], there is a fully dynamic algorithm with worst-case update time O(n1.529) that whp maintains an n1+o(1) edge (1 + ∊, no(1))-spanner.\r\n\r\nOur new algebraic techniques allow us to also obtain a new fully dynamic algorithm for All-Pairs Shortest Paths (APSP) that can perform both edge updates and can report shortest paths in worst-case time O(n1.9), which are correct whp. This is the first path-reporting fully dynamic APSP algorithm with a truly subquadratic query time that beats O(n2.5) update time. It works against an oblivious adversary.\r\n\r\nFinally, we give two applications of our new dynamic spanner algorithms: (1) a fully dynamic (1 + ∊)-approximate APSP algorithm with update time O(n1.529) that can report approximate shortest paths in n1+o(1) time per query; previous subquadratic update/query algorithms could only report the distance, but not obtain the paths; (2) a fully dynamic algorithm for near-2-approximate Steiner tree maintenance with both terminal and edge updates."}],"publication":"32nd Annual ACM-SIAM Symposium on Discrete Algorithms","oa_version":"Preprint","author":[{"last_name":"Bergamaschi","first_name":"Thiago","full_name":"Bergamaschi, Thiago"},{"first_name":"Monika H","full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"full_name":"Gutenberg, Maximilian Probst","first_name":"Maximilian Probst","last_name":"Gutenberg"},{"last_name":"Williams","first_name":"Virginia Vassilevska","full_name":"Williams, Virginia Vassilevska"},{"full_name":"Wein, Nicole","last_name":"Wein","first_name":"Nicole"}],"external_id":{"arxiv":["2010.10134"]},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2010.10134"}],"title":"New techniques and fine-grained hardness for dynamic near-additive spanners"},{"main_file_link":[{"url":"https://arxiv.org/abs/2002.11171","open_access":"1"}],"title":"Dynamic set cover: Improved amortized and worst-case update time","author":[{"last_name":"Bhattacharya","first_name":"Sayan","full_name":"Bhattacharya, Sayan"},{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"first_name":"Danupon","full_name":"Nanongkai, Danupon","last_name":"Nanongkai"},{"full_name":"Wu, Xiaowei","last_name":"Wu","first_name":"Xiaowei"}],"external_id":{"arxiv":["2002.11171"]},"publication":"32nd Annual ACM-SIAM Symposium on Discrete Algorithms","abstract":[{"lang":"eng","text":"In the dynamic minimum set cover problem, a challenge is to minimize the update time while guaranteeing close to the optimal min(O(log n), f) approximation factor. (Throughout, m, n, f, and C are parameters denoting the maximum number of sets, number of elements, frequency, and the cost range.) In the high-frequency range, when f = Ω(log n), this was achieved by a deterministic O(log n)-approximation algorithm with O(f log n) amortized update time [Gupta et al. STOC'17]. In the low-frequency range, the line of work by Gupta et al. [STOC'17], Abboud et al. [STOC'19], and Bhattacharya et al. [ICALP'15, IPCO'17, FOCS'19] led to a deterministic (1 + ∊) f-approximation algorithm with O(f log(Cn)/∊2) amortized update time. In this paper we improve the latter update time and provide the first bounds that subsume (and sometimes improve) the state-of-the-art dynamic vertex cover algorithms. We obtain: (1) (1 + ∊) f-approximation ratio in O(f log2(Cn)/∊3) worst-case update time: No non-trivial worst-case update time was previously known for dynamic set cover. Our bound subsumes and improves by a logarithmic factor the O(log3 n/poly(∊)) worst-case update time for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1) by Bhattacharya et al. [SODA'17]. (2) (1 + ∊) f-approximation ratio in O ((f2/∊3) + (f/∊2) log C) amortized update time: This result improves the previous O(f log (Cn)/∊2) update time bound for most values of f in the low-frequency range, i.e. whenever f = o(log n). It is the first that is independent of m and n. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [SODA'19] for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1). These results are achieved by leveraging the approximate complementary slackness and background schedulers techniques. These techniques were used in the local update scheme for dynamic vertex cover. Our main technical contribution is to adapt these techniques within the global update scheme of Bhattacharya et al. [FOCS'19] for the dynamic set cover problem."}],"day":"01","oa_version":"Preprint","extern":"1","publication_status":"published","scopus_import":"1","month":"01","article_processing_charge":"No","oa":1,"citation":{"ista":"Bhattacharya S, Henzinger M, Nanongkai D, Wu X. 2021. Dynamic set cover: Improved amortized and worst-case update time. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 2537–2549.","short":"S. Bhattacharya, M. Henzinger, D. Nanongkai, X. Wu, in:, 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2021, pp. 2537–2549.","apa":"Bhattacharya, S., Henzinger, M., Nanongkai, D., &#38; Wu, X. (2021). Dynamic set cover: Improved amortized and worst-case update time. In <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 2537–2549). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611976465.150\">https://doi.org/10.1137/1.9781611976465.150</a>","mla":"Bhattacharya, Sayan, et al. “Dynamic Set Cover: Improved Amortized and Worst-Case Update Time.” <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2021, pp. 2537–49, doi:<a href=\"https://doi.org/10.1137/1.9781611976465.150\">10.1137/1.9781611976465.150</a>.","ieee":"S. Bhattacharya, M. Henzinger, D. Nanongkai, and X. Wu, “Dynamic set cover: Improved amortized and worst-case update time,” in <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Alexandria, VA, United States, 2021, pp. 2537–2549.","ama":"Bhattacharya S, Henzinger M, Nanongkai D, Wu X. Dynamic set cover: Improved amortized and worst-case update time. In: <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2021:2537-2549. doi:<a href=\"https://doi.org/10.1137/1.9781611976465.150\">10.1137/1.9781611976465.150</a>","chicago":"Bhattacharya, Sayan, Monika Henzinger, Danupon Nanongkai, and Xiaowei Wu. “Dynamic Set Cover: Improved Amortized and Worst-Case Update Time.” In <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2537–49. Society for Industrial and Applied Mathematics, 2021. <a href=\"https://doi.org/10.1137/1.9781611976465.150\">https://doi.org/10.1137/1.9781611976465.150</a>."},"date_published":"2021-01-01T00:00:00Z","language":[{"iso":"eng"}],"publication_identifier":{"eisbn":["978-1-61197-646-5"]},"quality_controlled":"1","date_created":"2022-08-18T07:46:54Z","arxiv":1,"conference":{"start_date":"2021-01-10","location":"Alexandria, VA, United States","name":"SODA: Symposium on Discrete Algorithms","end_date":"2021-01-13"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"2537-2549","_id":"11920","year":"2021","doi":"10.1137/1.9781611976465.150","publisher":"Society for Industrial and Applied Mathematics","status":"public","type":"conference","date_updated":"2024-11-06T12:26:16Z"},{"conference":{"name":"SODA: Symposium on Discrete Algorithms","end_date":"2021-01-13","start_date":"2021-01-10","location":"Alexandria, VA, United States"},"date_created":"2022-08-18T10:31:58Z","arxiv":1,"publication_identifier":{"eisbn":["978-161197646-5"]},"quality_controlled":"1","language":[{"iso":"eng"}],"date_published":"2021-01-01T00:00:00Z","citation":{"ama":"Henzinger M, Neumann S, Räcke H, Schmid S. Tight bounds for online graph partitioning. In: <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2021:2799-2818. doi:<a href=\"https://doi.org/10.1137/1.9781611976465.166\">10.1137/1.9781611976465.166</a>","chicago":"Henzinger, Monika, Stefan Neumann, Harald Räcke, and Stefan Schmid. “Tight Bounds for Online Graph Partitioning.” In <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2799–2818. Society for Industrial and Applied Mathematics, 2021. <a href=\"https://doi.org/10.1137/1.9781611976465.166\">https://doi.org/10.1137/1.9781611976465.166</a>.","apa":"Henzinger, M., Neumann, S., Räcke, H., &#38; Schmid, S. (2021). Tight bounds for online graph partitioning. In <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 2799–2818). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611976465.166\">https://doi.org/10.1137/1.9781611976465.166</a>","mla":"Henzinger, Monika, et al. “Tight Bounds for Online Graph Partitioning.” <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2021, pp. 2799–818, doi:<a href=\"https://doi.org/10.1137/1.9781611976465.166\">10.1137/1.9781611976465.166</a>.","ieee":"M. Henzinger, S. Neumann, H. Räcke, and S. Schmid, “Tight bounds for online graph partitioning,” in <i>32nd Annual ACM-SIAM Symposium on Discrete Algorithms</i>, Alexandria, VA, United States, 2021, pp. 2799–2818.","ista":"Henzinger M, Neumann S, Räcke H, Schmid S. 2021. Tight bounds for online graph partitioning. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 2799–2818.","short":"M. Henzinger, S. Neumann, H. Räcke, S. Schmid, in:, 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2021, pp. 2799–2818."},"month":"01","article_processing_charge":"No","oa":1,"type":"conference","publisher":"Society for Industrial and Applied Mathematics","status":"public","date_updated":"2024-11-06T12:26:29Z","doi":"10.1137/1.9781611976465.166","year":"2021","page":"2799-2818","_id":"11923","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["2011.01017"]},"author":[{"full_name":"Henzinger, Monika H","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"full_name":"Neumann, Stefan","first_name":"Stefan","last_name":"Neumann"},{"full_name":"Räcke, Harald","first_name":"Harald","last_name":"Räcke"},{"last_name":"Schmid","first_name":"Stefan","full_name":"Schmid, Stefan"}],"title":"Tight bounds for online graph partitioning","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2011.01017"}],"scopus_import":"1","publication_status":"published","extern":"1","oa_version":"Preprint","day":"01","abstract":[{"lang":"eng","text":"We consider the following online optimization problem. We are given a graph G and each vertex of the graph is assigned to one of ℓ servers, where servers have capacity k and we assume that the graph has ℓ · k vertices. Initially, G does not contain any edges and then the edges of G are revealed one-by-one. The goal is to design an online algorithm ONL, which always places the connected components induced by the revealed edges on the same server and never exceeds the server capacities by more than ∊k for constant ∊ > 0. Whenever ONL learns about a new edge, the algorithm is allowed to move vertices from one server to another. Its objective is to minimize the number of vertex moves. More specifically, ONL should minimize the competitive ratio: the total cost ONL incurs compared to an optimal offline algorithm OPT.\r\n\r\nThe problem was recently introduced by Henzinger et al. (SIGMETRICS'2019) and is related to classic online problems such as online paging and scheduling. It finds applications in the context of resource allocation in the cloud and for optimizing distributed data structures such as union–find data structures.\r\n\r\nOur main contribution is a polynomial-time randomized algorithm, that is asymptotically optimal: we derive an upper bound of O(log ℓ + log k) on its competitive ratio and show that no randomized online algorithm can achieve a competitive ratio of less than Ω(log ℓ + log k). We also settle the open problem of the achievable competitive ratio by deterministic online algorithms, by deriving a competitive ratio of Θ(ℓ log k); to this end, we present an improved lower bound as well as a deterministic polynomial-time online algorithm.\r\n\r\nOur algorithms rely on a novel technique which combines efficient integer programming with a combinatorial approach for maintaining ILP solutions. More precisely, we use an ILP to assign the connected components induced by the revealed edges to the servers; this is similar to existing approximation schemes for scheduling algorithms. However, we cannot obtain our competitive ratios if we run the ILP after each edge insertion. Instead, we identify certain types of edge insertions, after which we can manually obtain an optimal ILP solution at zero cost without resolving the ILP. We believe this technique is of independent interest and will find further applications in the future."}],"publication":"32nd Annual ACM-SIAM Symposium on Discrete Algorithms"},{"date_created":"2022-08-19T07:33:37Z","conference":{"start_date":"2021-01-10","location":"Alexandria, VA, United States","end_date":"2021-01-11","name":"ALENEX: Symposium on Algorithm Engineering and Experiments"},"language":[{"iso":"eng"}],"author":[{"full_name":"Goranci, Gramoz","first_name":"Gramoz","last_name":"Goranci"},{"first_name":"Monika H","full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530"},{"last_name":"Leniowski","full_name":"Leniowski, Dariusz","first_name":"Dariusz"},{"last_name":"Schulz","full_name":"Schulz, Christian","first_name":"Christian"},{"full_name":"Svozil, Alexander","first_name":"Alexander","last_name":"Svozil"}],"quality_controlled":"1","publication_identifier":{"issn":["2164-0300"],"eisbn":["978-1-61197-647-2"]},"date_published":"2021-01-01T00:00:00Z","title":"Fully dynamic k-center clustering in low dimensional metrics","month":"01","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1137/1.9781611976472.11"}],"article_processing_charge":"No","oa":1,"citation":{"ista":"Goranci G, Henzinger M, Leniowski D, Schulz C, Svozil A. 2021. Fully dynamic k-center clustering in low dimensional metrics. 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 143–153.","short":"G. Goranci, M. Henzinger, D. Leniowski, C. Schulz, A. Svozil, in:, 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2021, pp. 143–153.","apa":"Goranci, G., Henzinger, M., Leniowski, D., Schulz, C., &#38; Svozil, A. (2021). Fully dynamic k-center clustering in low dimensional metrics. In <i>2021 Proceedings of the Workshop on Algorithm Engineering and Experiments</i> (pp. 143–153). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611976472.11\">https://doi.org/10.1137/1.9781611976472.11</a>","ieee":"G. Goranci, M. Henzinger, D. Leniowski, C. Schulz, and A. Svozil, “Fully dynamic k-center clustering in low dimensional metrics,” in <i>2021 Proceedings of the Workshop on Algorithm Engineering and Experiments</i>, Alexandria, VA, United States, 2021, pp. 143–153.","mla":"Goranci, Gramoz, et al. “Fully Dynamic K-Center Clustering in Low Dimensional Metrics.” <i>2021 Proceedings of the Workshop on Algorithm Engineering and Experiments</i>, Society for Industrial and Applied Mathematics, 2021, pp. 143–53, doi:<a href=\"https://doi.org/10.1137/1.9781611976472.11\">10.1137/1.9781611976472.11</a>.","chicago":"Goranci, Gramoz, Monika Henzinger, Dariusz Leniowski, Christian Schulz, and Alexander Svozil. “Fully Dynamic K-Center Clustering in Low Dimensional Metrics.” In <i>2021 Proceedings of the Workshop on Algorithm Engineering and Experiments</i>, 143–53. Society for Industrial and Applied Mathematics, 2021. <a href=\"https://doi.org/10.1137/1.9781611976472.11\">https://doi.org/10.1137/1.9781611976472.11</a>.","ama":"Goranci G, Henzinger M, Leniowski D, Schulz C, Svozil A. Fully dynamic k-center clustering in low dimensional metrics. In: <i>2021 Proceedings of the Workshop on Algorithm Engineering and Experiments</i>. Society for Industrial and Applied Mathematics; 2021:143-153. doi:<a href=\"https://doi.org/10.1137/1.9781611976472.11\">10.1137/1.9781611976472.11</a>"},"publisher":"Society for Industrial and Applied Mathematics","extern":"1","type":"conference","publication_status":"published","status":"public","date_updated":"2024-11-06T12:27:01Z","scopus_import":"1","doi":"10.1137/1.9781611976472.11","page":"143 -153","_id":"11931","year":"2021","oa_version":"Published Version","publication":"2021 Proceedings of the Workshop on Algorithm Engineering and Experiments","abstract":[{"lang":"eng","text":"Clustering is one of the most fundamental problems in unsupervised learning with a large number of applications. However, classical clustering algorithms assume that the data is static, thus failing to capture many real-world applications where data is constantly changing and evolving. Driven by this, we study the metric k-center clustering problem in the fully dynamic setting, where the goal is to efficiently maintain a clustering while supporting an intermixed sequence of insertions and deletions of points. This model also supports queries of the form (1) report whether a given point is a center or (2) determine the cluster a point is assigned to. We present a deterministic dynamic algorithm for the k-center clustering problem that provably achieves a (2 + ∊)-approximation in nearly logarithmic update and query time, if the underlying metric has bounded doubling dimension, its aspect ratio is bounded by a polynomial and ∊ is a constant. An important feature of our algorithm is that the update and query times are independent of k. We confirm the practical relevance of this feature via an extensive experimental study which shows that for large values of k, our algorithmic construction outperforms the state-of-the-art algorithm in terms of solution quality and running time."}],"day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"abstract":[{"lang":"eng","text":"Controlling the selectivity of a chemical reaction with external stimuli is common in thermal processes, but rare in visible-light photocatalysis. Here we show that the redox potential of a carbon nitride photocatalyst (CN-OA-m) can be tuned by changing the irradiation wavelength to generate electron holes with different oxidation potentials. This tuning was the key to realizing photo-chemo-enzymatic cascades that give either the (S)- or the (R)-enantiomer of phenylethanol. In combination with an unspecific peroxygenase from Agrocybe aegerita, green light irradiation of CN-OA-m led to the enantioselective hydroxylation of ethylbenzene to (R)-1-phenylethanol (99 % ee). In contrast, blue light irradiation triggered the photocatalytic oxidation of ethylbenzene to acetophenone, which in turn was enantioselectively reduced with an alcohol dehydrogenase from Rhodococcus ruber to form (S)-1-phenylethanol (93 % ee)."}],"day":"22","issue":"13","publication":"Angewandte Chemie International Edition","oa_version":"Published Version","scopus_import":"1","publication_status":"published","extern":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1002/anie.202100164"}],"title":"Chromoselective photocatalysis enables stereocomplementary biocatalytic pathways","author":[{"last_name":"Schmermund","first_name":"Luca","full_name":"Schmermund, Luca"},{"full_name":"Reischauer, Susanne","last_name":"Reischauer","first_name":"Susanne"},{"first_name":"Sarah","full_name":"Bierbaumer, Sarah","last_name":"Bierbaumer"},{"full_name":"Winkler, Christoph K.","first_name":"Christoph K.","last_name":"Winkler"},{"full_name":"Diaz‐Rodriguez, Alba","first_name":"Alba","last_name":"Diaz‐Rodriguez"},{"first_name":"Lee J.","full_name":"Edwards, Lee J.","last_name":"Edwards"},{"last_name":"Kara","first_name":"Selin","full_name":"Kara, Selin"},{"last_name":"Mielke","first_name":"Tamara","full_name":"Mielke, Tamara"},{"full_name":"Cartwright, Jared","last_name":"Cartwright","first_name":"Jared"},{"full_name":"Grogan, Gideon","last_name":"Grogan","first_name":"Gideon"},{"first_name":"Bartholomäus","last_name":"Pieber","id":"93e5e5b2-0da6-11ed-8a41-af589a024726","full_name":"Pieber, Bartholomäus","orcid":"0000-0001-8689-388X"},{"last_name":"Kroutil","full_name":"Kroutil, Wolfgang","first_name":"Wolfgang"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_type":"original","year":"2021","_id":"11956","page":"6965-6969","doi":"10.1002/anie.202100164","intvolume":"        60","date_updated":"2024-10-14T11:43:06Z","type":"journal_article","publisher":"Wiley","status":"public","citation":{"ista":"Schmermund L, Reischauer S, Bierbaumer S, Winkler CK, Diaz‐Rodriguez A, Edwards LJ, Kara S, Mielke T, Cartwright J, Grogan G, Pieber B, Kroutil W. 2021. Chromoselective photocatalysis enables stereocomplementary biocatalytic pathways. Angewandte Chemie International Edition. 60(13), 6965–6969.","short":"L. Schmermund, S. Reischauer, S. Bierbaumer, C.K. Winkler, A. Diaz‐Rodriguez, L.J. Edwards, S. Kara, T. Mielke, J. Cartwright, G. Grogan, B. Pieber, W. Kroutil, Angewandte Chemie International Edition 60 (2021) 6965–6969.","apa":"Schmermund, L., Reischauer, S., Bierbaumer, S., Winkler, C. K., Diaz‐Rodriguez, A., Edwards, L. J., … Kroutil, W. (2021). Chromoselective photocatalysis enables stereocomplementary biocatalytic pathways. <i>Angewandte Chemie International Edition</i>. Wiley. <a href=\"https://doi.org/10.1002/anie.202100164\">https://doi.org/10.1002/anie.202100164</a>","ieee":"L. Schmermund <i>et al.</i>, “Chromoselective photocatalysis enables stereocomplementary biocatalytic pathways,” <i>Angewandte Chemie International Edition</i>, vol. 60, no. 13. Wiley, pp. 6965–6969, 2021.","mla":"Schmermund, Luca, et al. “Chromoselective Photocatalysis Enables Stereocomplementary Biocatalytic Pathways.” <i>Angewandte Chemie International Edition</i>, vol. 60, no. 13, Wiley, 2021, pp. 6965–69, doi:<a href=\"https://doi.org/10.1002/anie.202100164\">10.1002/anie.202100164</a>.","ama":"Schmermund L, Reischauer S, Bierbaumer S, et al. Chromoselective photocatalysis enables stereocomplementary biocatalytic pathways. <i>Angewandte Chemie International Edition</i>. 2021;60(13):6965-6969. doi:<a href=\"https://doi.org/10.1002/anie.202100164\">10.1002/anie.202100164</a>","chicago":"Schmermund, Luca, Susanne Reischauer, Sarah Bierbaumer, Christoph K. Winkler, Alba Diaz‐Rodriguez, Lee J. Edwards, Selin Kara, et al. “Chromoselective Photocatalysis Enables Stereocomplementary Biocatalytic Pathways.” <i>Angewandte Chemie International Edition</i>. Wiley, 2021. <a href=\"https://doi.org/10.1002/anie.202100164\">https://doi.org/10.1002/anie.202100164</a>."},"oa":1,"month":"03","article_processing_charge":"No","volume":60,"date_published":"2021-03-22T00:00:00Z","publication_identifier":{"eissn":["1521-3773"],"issn":["1433-7851"]},"quality_controlled":"1","language":[{"iso":"eng"}],"date_created":"2022-08-24T10:47:16Z"},{"doi":"10.1002/cptc.202100062","intvolume":"         5","type":"journal_article","publisher":"Wiley","status":"public","date_updated":"2024-10-14T11:43:32Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_type":"letter_note","year":"2021","page":"716-720","_id":"11965","quality_controlled":"1","publication_identifier":{"eissn":["2367-0932"]},"language":[{"iso":"eng"}],"date_created":"2022-08-25T08:31:11Z","citation":{"chicago":"Reischauer, Susanne, and Bartholomäus Pieber. “Recyclable, Bifunctional Metallaphotocatalysts for C−S Cross‐coupling Reactions.” <i>ChemPhotoChem</i>. Wiley, 2021. <a href=\"https://doi.org/10.1002/cptc.202100062\">https://doi.org/10.1002/cptc.202100062</a>.","ama":"Reischauer S, Pieber B. Recyclable, bifunctional metallaphotocatalysts for C−S cross‐coupling reactions. <i>ChemPhotoChem</i>. 2021;5(8):716-720. doi:<a href=\"https://doi.org/10.1002/cptc.202100062\">10.1002/cptc.202100062</a>","apa":"Reischauer, S., &#38; Pieber, B. (2021). Recyclable, bifunctional metallaphotocatalysts for C−S cross‐coupling reactions. <i>ChemPhotoChem</i>. Wiley. <a href=\"https://doi.org/10.1002/cptc.202100062\">https://doi.org/10.1002/cptc.202100062</a>","ieee":"S. Reischauer and B. Pieber, “Recyclable, bifunctional metallaphotocatalysts for C−S cross‐coupling reactions,” <i>ChemPhotoChem</i>, vol. 5, no. 8. Wiley, pp. 716–720, 2021.","mla":"Reischauer, Susanne, and Bartholomäus Pieber. “Recyclable, Bifunctional Metallaphotocatalysts for C−S Cross‐coupling Reactions.” <i>ChemPhotoChem</i>, vol. 5, no. 8, Wiley, 2021, pp. 716–20, doi:<a href=\"https://doi.org/10.1002/cptc.202100062\">10.1002/cptc.202100062</a>.","ista":"Reischauer S, Pieber B. 2021. Recyclable, bifunctional metallaphotocatalysts for C−S cross‐coupling reactions. ChemPhotoChem. 5(8), 716–720.","short":"S. Reischauer, B. Pieber, ChemPhotoChem 5 (2021) 716–720."},"article_processing_charge":"No","month":"08","volume":5,"oa":1,"date_published":"2021-08-01T00:00:00Z","scopus_import":"1","publication_status":"published","extern":"1","day":"01","abstract":[{"lang":"eng","text":"Metallaphotocatalytic cross-coupling reactions are typically carried out by combining homogeneous or heterogeneous photocatalysts with a soluble nickel complex. Previous attempts to realize recyclable catalytic systems use immobilized iridium complexes to harvest light. We present bifunctional materials based on semiconductors for metallaphotocatalytic C−S cross-coupling reactions that can be reused without losing their catalytic activity. Key to the success is the permanent immobilization of a nickel complex on the surface of a heterogeneous semiconductor through phosphonic acid anchors. The optimized catalyst harvests a broad range of the visible light spectrum and requires a nickel loading of only ∼0.1 mol %."}],"publication":"ChemPhotoChem","issue":"8","oa_version":"Published Version","author":[{"full_name":"Reischauer, Susanne","last_name":"Reischauer","first_name":"Susanne"},{"id":"93e5e5b2-0da6-11ed-8a41-af589a024726","first_name":"Bartholomäus","last_name":"Pieber","full_name":"Pieber, Bartholomäus","orcid":"0000-0001-8689-388X"}],"main_file_link":[{"url":"https://doi.org/10.1002/cptc.202100062","open_access":"1"}],"title":"Recyclable, bifunctional metallaphotocatalysts for C−S cross‐coupling reactions"},{"issue":"12","publication":"Green Chemistry","abstract":[{"text":"Carbon dots have been previosly immobilized on titanium dioxide to generate photocatalysts for pollutant degradation and water splitting. Here we demonstrate that these nanocomposites are valuable photocatalysts for metallaphotocatalytic carbon–heteroatom cross-couplings. These sustainable materials show a large applicability, high photostability, excellent reusability, and broadly absorb across the visible-light spectrum.","lang":"eng"}],"day":"21","oa_version":"Published Version","extern":"1","publication_status":"published","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1039/D1GC01284C"}],"title":"Carbon dot/TiO₂ nanocomposites as photocatalysts for metallaphotocatalytic carbon-heteroatom cross-couplings","author":[{"first_name":"Zhouxiang","full_name":"Zhao, Zhouxiang","last_name":"Zhao"},{"full_name":"Reischauer, Susanne","last_name":"Reischauer","first_name":"Susanne"},{"orcid":"0000-0001-8689-388X","first_name":"Bartholomäus","last_name":"Pieber","full_name":"Pieber, Bartholomäus","id":"93e5e5b2-0da6-11ed-8a41-af589a024726"},{"first_name":"Martina","full_name":"Delbianco, Martina","last_name":"Delbianco"}],"article_type":"original","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11972","page":"4524-4530","year":"2021","doi":"10.1039/d1gc01284c","date_updated":"2024-10-14T12:05:41Z","type":"journal_article","publisher":"Royal Society of Chemistry","status":"public","intvolume":"        23","oa":1,"volume":23,"article_processing_charge":"No","month":"06","citation":{"chicago":"Zhao, Zhouxiang, Susanne Reischauer, Bartholomäus Pieber, and Martina Delbianco. “Carbon Dot/TiO₂ Nanocomposites as Photocatalysts for Metallaphotocatalytic Carbon-Heteroatom Cross-Couplings.” <i>Green Chemistry</i>. Royal Society of Chemistry, 2021. <a href=\"https://doi.org/10.1039/d1gc01284c\">https://doi.org/10.1039/d1gc01284c</a>.","ama":"Zhao Z, Reischauer S, Pieber B, Delbianco M. Carbon dot/TiO₂ nanocomposites as photocatalysts for metallaphotocatalytic carbon-heteroatom cross-couplings. <i>Green Chemistry</i>. 2021;23(12):4524-4530. doi:<a href=\"https://doi.org/10.1039/d1gc01284c\">10.1039/d1gc01284c</a>","mla":"Zhao, Zhouxiang, et al. “Carbon Dot/TiO₂ Nanocomposites as Photocatalysts for Metallaphotocatalytic Carbon-Heteroatom Cross-Couplings.” <i>Green Chemistry</i>, vol. 23, no. 12, Royal Society of Chemistry, 2021, pp. 4524–30, doi:<a href=\"https://doi.org/10.1039/d1gc01284c\">10.1039/d1gc01284c</a>.","ieee":"Z. Zhao, S. Reischauer, B. Pieber, and M. Delbianco, “Carbon dot/TiO₂ nanocomposites as photocatalysts for metallaphotocatalytic carbon-heteroatom cross-couplings,” <i>Green Chemistry</i>, vol. 23, no. 12. Royal Society of Chemistry, pp. 4524–4530, 2021.","apa":"Zhao, Z., Reischauer, S., Pieber, B., &#38; Delbianco, M. (2021). Carbon dot/TiO₂ nanocomposites as photocatalysts for metallaphotocatalytic carbon-heteroatom cross-couplings. <i>Green Chemistry</i>. Royal Society of Chemistry. <a href=\"https://doi.org/10.1039/d1gc01284c\">https://doi.org/10.1039/d1gc01284c</a>","short":"Z. Zhao, S. Reischauer, B. Pieber, M. Delbianco, Green Chemistry 23 (2021) 4524–4530.","ista":"Zhao Z, Reischauer S, Pieber B, Delbianco M. 2021. Carbon dot/TiO₂ nanocomposites as photocatalysts for metallaphotocatalytic carbon-heteroatom cross-couplings. Green Chemistry. 23(12), 4524–4530."},"date_published":"2021-06-21T00:00:00Z","language":[{"iso":"eng"}],"quality_controlled":"1","publication_identifier":{"eissn":["1463-9270"],"issn":["1463-9262"]},"date_created":"2022-08-25T10:25:46Z"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_type":"review","year":"2021","_id":"11974","doi":"10.1016/j.isci.2021.102209","intvolume":"        24","publisher":"Elsevier","status":"public","type":"journal_article","date_updated":"2024-10-14T12:05:29Z","citation":{"mla":"Reischauer, Susanne, and Bartholomäus Pieber. “Emerging Concepts in Photocatalytic Organic Synthesis.” <i>IScience</i>, vol. 24, no. 3, 102209, Elsevier, 2021, doi:<a href=\"https://doi.org/10.1016/j.isci.2021.102209\">10.1016/j.isci.2021.102209</a>.","ieee":"S. Reischauer and B. Pieber, “Emerging concepts in photocatalytic organic synthesis,” <i>iScience</i>, vol. 24, no. 3. Elsevier, 2021.","apa":"Reischauer, S., &#38; Pieber, B. (2021). Emerging concepts in photocatalytic organic synthesis. <i>IScience</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.isci.2021.102209\">https://doi.org/10.1016/j.isci.2021.102209</a>","chicago":"Reischauer, Susanne, and Bartholomäus Pieber. “Emerging Concepts in Photocatalytic Organic Synthesis.” <i>IScience</i>. Elsevier, 2021. <a href=\"https://doi.org/10.1016/j.isci.2021.102209\">https://doi.org/10.1016/j.isci.2021.102209</a>.","ama":"Reischauer S, Pieber B. Emerging concepts in photocatalytic organic synthesis. <i>iScience</i>. 2021;24(3). doi:<a href=\"https://doi.org/10.1016/j.isci.2021.102209\">10.1016/j.isci.2021.102209</a>","short":"S. Reischauer, B. Pieber, IScience 24 (2021).","ista":"Reischauer S, Pieber B. 2021. Emerging concepts in photocatalytic organic synthesis. iScience. 24(3), 102209."},"article_processing_charge":"No","volume":24,"month":"03","oa":1,"date_published":"2021-03-19T00:00:00Z","publication_identifier":{"eissn":["2589-0042"]},"quality_controlled":"1","language":[{"iso":"eng"}],"date_created":"2022-08-25T10:31:44Z","day":"19","abstract":[{"lang":"eng","text":"Visible light photocatalysis has become a powerful tool in organic synthesis that uses photons as traceless, sustainable reagents. Most of the activities in the field focus on the development of new reactions via common photoredox cycles, but recently a number of exciting new concepts and strategies entered less charted territories. We survey approaches that enable the use of longer wavelengths and show that the wavelength and intensity of photons are import parameters that enable tuning of the reactivity of a photocatalyst to control or change the selectivity of chemical reactions. In addition, we discuss recent efforts to substitute strong reductants, such as elemental lithium and sodium, by light and technological advances in the field."}],"publication":"iScience","issue":"3","oa_version":"Published Version","article_number":"102209","scopus_import":"1","publication_status":"published","extern":"1","main_file_link":[{"url":"https://doi.org/10.1016/j.isci.2021.102209","open_access":"1"}],"title":"Emerging concepts in photocatalytic organic synthesis","author":[{"last_name":"Reischauer","first_name":"Susanne","full_name":"Reischauer, Susanne"},{"orcid":"0000-0001-8689-388X","first_name":"Bartholomäus","last_name":"Pieber","id":"93e5e5b2-0da6-11ed-8a41-af589a024726","full_name":"Pieber, Bartholomäus"}]},{"language":[{"iso":"eng"}],"quality_controlled":"1","publication_identifier":{"eissn":["1523-7052"],"issn":["1523-7060"]},"date_created":"2022-08-25T11:13:05Z","oa":1,"volume":23,"month":"01","article_processing_charge":"No","citation":{"ista":"Cavedon C, Sletten ET, Madani A, Niemeyer O, Seeberger PH, Pieber B. 2021. Visible-light-mediated oxidative debenzylation enables the use of benzyl ethers as temporary protecting groups. Organic Letters. 23(2), 514–518.","short":"C. Cavedon, E.T. Sletten, A. Madani, O. Niemeyer, P.H. Seeberger, B. Pieber, Organic Letters 23 (2021) 514–518.","ama":"Cavedon C, Sletten ET, Madani A, Niemeyer O, Seeberger PH, Pieber B. Visible-light-mediated oxidative debenzylation enables the use of benzyl ethers as temporary protecting groups. <i>Organic Letters</i>. 2021;23(2):514-518. doi:<a href=\"https://doi.org/10.1021/acs.orglett.0c04026\">10.1021/acs.orglett.0c04026</a>","chicago":"Cavedon, Cristian, Eric T. Sletten, Amiera Madani, Olaf Niemeyer, Peter H. Seeberger, and Bartholomäus Pieber. “Visible-Light-Mediated Oxidative Debenzylation Enables the Use of Benzyl Ethers as Temporary Protecting Groups.” <i>Organic Letters</i>. American Chemical Society, 2021. <a href=\"https://doi.org/10.1021/acs.orglett.0c04026\">https://doi.org/10.1021/acs.orglett.0c04026</a>.","apa":"Cavedon, C., Sletten, E. T., Madani, A., Niemeyer, O., Seeberger, P. H., &#38; Pieber, B. (2021). Visible-light-mediated oxidative debenzylation enables the use of benzyl ethers as temporary protecting groups. <i>Organic Letters</i>. American Chemical Society. <a href=\"https://doi.org/10.1021/acs.orglett.0c04026\">https://doi.org/10.1021/acs.orglett.0c04026</a>","ieee":"C. Cavedon, E. T. Sletten, A. Madani, O. Niemeyer, P. H. Seeberger, and B. Pieber, “Visible-light-mediated oxidative debenzylation enables the use of benzyl ethers as temporary protecting groups,” <i>Organic Letters</i>, vol. 23, no. 2. American Chemical Society, pp. 514–518, 2021.","mla":"Cavedon, Cristian, et al. “Visible-Light-Mediated Oxidative Debenzylation Enables the Use of Benzyl Ethers as Temporary Protecting Groups.” <i>Organic Letters</i>, vol. 23, no. 2, American Chemical Society, 2021, pp. 514–18, doi:<a href=\"https://doi.org/10.1021/acs.orglett.0c04026\">10.1021/acs.orglett.0c04026</a>."},"date_published":"2021-01-15T00:00:00Z","doi":"10.1021/acs.orglett.0c04026","date_updated":"2024-10-14T12:05:18Z","type":"journal_article","publisher":"American Chemical Society","status":"public","intvolume":"        23","article_type":"letter_note","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11981","page":"514-518","pmid":1,"year":"2021","author":[{"full_name":"Cavedon, Cristian","first_name":"Cristian","last_name":"Cavedon"},{"full_name":"Sletten, Eric T.","first_name":"Eric T.","last_name":"Sletten"},{"last_name":"Madani","full_name":"Madani, Amiera","first_name":"Amiera"},{"full_name":"Niemeyer, Olaf","first_name":"Olaf","last_name":"Niemeyer"},{"last_name":"Seeberger","full_name":"Seeberger, Peter H.","first_name":"Peter H."},{"id":"93e5e5b2-0da6-11ed-8a41-af589a024726","last_name":"Pieber","first_name":"Bartholomäus","full_name":"Pieber, Bartholomäus","orcid":"0000-0001-8689-388X"}],"external_id":{"pmid":["33400534"]},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1021/acs.orglett.0c04026"}],"title":"Visible-light-mediated oxidative debenzylation enables the use of benzyl ethers as temporary protecting groups","publication_status":"published","extern":"1","scopus_import":"1","issue":"2","publication":"Organic Letters","abstract":[{"lang":"eng","text":"The cleavage of benzyl ethers by catalytic hydrogenolysis or Birch reduction suffers from poor functional group compatibility and limits their use as a protecting group. The visible-light-mediated debenzylation disclosed here renders benzyl ethers temporary protective groups, enabling new orthogonal protection strategies. Using 2,3-dichloro-5,6-dicyano-1,4-benzoquinone (DDQ) as a stoichiometric or catalytic photooxidant, benzyl ethers can be cleaved in the presence of azides, alkenes, and alkynes. The reaction time can be reduced from hours to minutes in continuous flow."}],"day":"15","oa_version":"Published Version"},{"language":[{"iso":"eng"}],"author":[{"full_name":"Cavedon, Cristian","first_name":"Cristian","last_name":"Cavedon"},{"first_name":"Sebastian","full_name":"Gisbertz, Sebastian","last_name":"Gisbertz"},{"first_name":"Sarah","full_name":"Vogl, Sarah","last_name":"Vogl"},{"full_name":"Richter, Noah","last_name":"Richter","first_name":"Noah"},{"full_name":"Schrottke, Stefanie","last_name":"Schrottke","first_name":"Stefanie"},{"last_name":"Teutloff","full_name":"Teutloff, Christian","first_name":"Christian"},{"full_name":"Seeberger, Peter H.","first_name":"Peter H.","last_name":"Seeberger"},{"last_name":"Thomas","full_name":"Thomas, Arne","first_name":"Arne"},{"orcid":"0000-0001-8689-388X","last_name":"Pieber","full_name":"Pieber, Bartholomäus","id":"93e5e5b2-0da6-11ed-8a41-af589a024726","first_name":"Bartholomäus"}],"date_created":"2022-09-08T11:42:02Z","oa":1,"main_file_link":[{"url":"https://doi.org/10.26434/chemrxiv-2021-kt2wr","open_access":"1"}],"month":"08","article_processing_charge":"No","citation":{"ista":"Cavedon C, Gisbertz S, Vogl S, Richter N, Schrottke S, Teutloff C, Seeberger PH, Thomas A, Pieber B. Photocatalyst-free, visible-light-mediated nickel catalyzed carbon–heteroatom cross-couplings. <a href=\"https://doi.org/10.26434/chemrxiv-2021-kt2wr\">10.26434/chemrxiv-2021-kt2wr</a>.","short":"C. Cavedon, S. Gisbertz, S. Vogl, N. Richter, S. Schrottke, C. Teutloff, P.H. Seeberger, A. Thomas, B. Pieber, (n.d.).","ama":"Cavedon C, Gisbertz S, Vogl S, et al. Photocatalyst-free, visible-light-mediated nickel catalyzed carbon–heteroatom cross-couplings. doi:<a href=\"https://doi.org/10.26434/chemrxiv-2021-kt2wr\">10.26434/chemrxiv-2021-kt2wr</a>","chicago":"Cavedon, Cristian, Sebastian Gisbertz, Sarah Vogl, Noah Richter, Stefanie Schrottke, Christian Teutloff, Peter H. Seeberger, Arne Thomas, and Bartholomäus Pieber. “Photocatalyst-Free, Visible-Light-Mediated Nickel Catalyzed Carbon–Heteroatom Cross-Couplings.” ChemRxiv, n.d. <a href=\"https://doi.org/10.26434/chemrxiv-2021-kt2wr\">https://doi.org/10.26434/chemrxiv-2021-kt2wr</a>.","apa":"Cavedon, C., Gisbertz, S., Vogl, S., Richter, N., Schrottke, S., Teutloff, C., … Pieber, B. (n.d.). Photocatalyst-free, visible-light-mediated nickel catalyzed carbon–heteroatom cross-couplings. ChemRxiv. <a href=\"https://doi.org/10.26434/chemrxiv-2021-kt2wr\">https://doi.org/10.26434/chemrxiv-2021-kt2wr</a>","mla":"Cavedon, Cristian, et al. <i>Photocatalyst-Free, Visible-Light-Mediated Nickel Catalyzed Carbon–Heteroatom Cross-Couplings</i>. ChemRxiv, doi:<a href=\"https://doi.org/10.26434/chemrxiv-2021-kt2wr\">10.26434/chemrxiv-2021-kt2wr</a>.","ieee":"C. Cavedon <i>et al.</i>, “Photocatalyst-free, visible-light-mediated nickel catalyzed carbon–heteroatom cross-couplings.” ChemRxiv."},"title":"Photocatalyst-free, visible-light-mediated nickel catalyzed carbon–heteroatom cross-couplings","date_published":"2021-08-04T00:00:00Z","doi":"10.26434/chemrxiv-2021-kt2wr","date_updated":"2024-10-14T12:05:05Z","type":"preprint","status":"public","extern":"1","publication_status":"submitted","publisher":"ChemRxiv","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"Metallaphotocatalysis typically requires a photocatalyst to harness the energy of visible-light and transfer it to a transition metal catalyst to trigger chemical reactions. The most prominent example is the merger of photo- and nickel catalysis that unlocked various cross-couplings. However, the high reactivity of excited photocatalyst can lead to unwanted side reactions thus limiting this approach. Here we show that a bipyridine ligand that is subtly decorated with two carbazole groups forms a nickel complex that absorbs visible-light and promotes several carbon–heteroatom cross-couplings in the absence of an exogenous photocatalysts. The ligand can be polymerized in a simple one-step procedure to afford a porous organic polymer that can be used for heterogeneous nickel catalysis in the same reactions. The material can be easily recovered and reused multiple times maintaining high catalytic activity and selectivity."}],"day":"04","_id":"12068","oa_version":"Preprint","year":"2021"},{"doi":"10.26434/chemrxiv.13521527","extern":"1","publication_status":"submitted","status":"public","publisher":"ChemRxiv","type":"preprint","date_updated":"2022-09-08T11:49:16Z","abstract":[{"text":"Controlling the selectivity of a chemical reaction with external stimuli is common in thermal processes, but rare in visible-light photocatalysis. Here we show that the redox potential of a carbon nitride photocatalyst (CN-OA-m) can be tuned by changing the irradiation wavelength to generate electron holes with different oxidation potentials. This tuning was the key to realizing photo-chemo-enzymatic cascades that give either the (S)- or the (R)-enantiomer of phenylethanol. In combination with an unspecific peroxygenase from Agrocybe aegerita, green light irradiation of CN-OA-m led to the enantioselective hydroxylation of ethylbenzene to (R)-1-phenylethanol (99% ee). In contrast, blue light irradiation triggered the photocatalytic oxidation of ethylbenzene to acetophenone, which in turn was enantioselectively reduced with an alcohol dehydrogenase from Rhodococcus ruber to form (S)-1-phenylethanol (93% ee).","lang":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","day":"06","year":"2021","oa_version":"Preprint","_id":"12070","author":[{"full_name":"Schmermund, Luca","last_name":"Schmermund","first_name":"Luca"},{"full_name":"Reischauer, Susanne","last_name":"Reischauer","first_name":"Susanne"},{"last_name":"Bierbaumer","full_name":"Bierbaumer, Sarah","first_name":"Sarah"},{"last_name":"Winkler","first_name":"Christoph","full_name":"Winkler, Christoph"},{"last_name":"Diaz-Rodriguez","full_name":"Diaz-Rodriguez, Alba","first_name":"Alba"},{"last_name":"Edwards","first_name":"Lee J.","full_name":"Edwards, Lee J."},{"full_name":"Kara, Selin","first_name":"Selin","last_name":"Kara"},{"first_name":"Tamara","full_name":"Mielke, Tamara","last_name":"Mielke"},{"full_name":"Cartwright, Jared","last_name":"Cartwright","first_name":"Jared"},{"last_name":"Grogan","full_name":"Grogan, Gideon","first_name":"Gideon"},{"first_name":"Bartholomäus","id":"93e5e5b2-0da6-11ed-8a41-af589a024726","last_name":"Pieber","full_name":"Pieber, Bartholomäus","orcid":"0000-0001-8689-388X"},{"full_name":"Kroutil, Wolfgang","last_name":"Kroutil","first_name":"Wolfgang"}],"language":[{"iso":"eng"}],"date_created":"2022-09-08T11:46:45Z","citation":{"short":"L. Schmermund, S. Reischauer, S. Bierbaumer, C. Winkler, A. Diaz-Rodriguez, L.J. Edwards, S. Kara, T. Mielke, J. Cartwright, G. Grogan, B. Pieber, W. Kroutil, (n.d.).","ista":"Schmermund L, Reischauer S, Bierbaumer S, Winkler C, Diaz-Rodriguez A, Edwards LJ, Kara S, Mielke T, Cartwright J, Grogan G, Pieber B, Kroutil W. Switching between enantiomers by combining chromoselective photocatalysis and biocatalysis. <a href=\"https://doi.org/10.26434/chemrxiv.13521527\">10.26434/chemrxiv.13521527</a>.","chicago":"Schmermund, Luca, Susanne Reischauer, Sarah Bierbaumer, Christoph Winkler, Alba Diaz-Rodriguez, Lee J. Edwards, Selin Kara, et al. “Switching between Enantiomers by Combining Chromoselective Photocatalysis and Biocatalysis.” ChemRxiv, n.d. <a href=\"https://doi.org/10.26434/chemrxiv.13521527\">https://doi.org/10.26434/chemrxiv.13521527</a>.","ama":"Schmermund L, Reischauer S, Bierbaumer S, et al. Switching between enantiomers by combining chromoselective photocatalysis and biocatalysis. doi:<a href=\"https://doi.org/10.26434/chemrxiv.13521527\">10.26434/chemrxiv.13521527</a>","mla":"Schmermund, Luca, et al. <i>Switching between Enantiomers by Combining Chromoselective Photocatalysis and Biocatalysis</i>. ChemRxiv, doi:<a href=\"https://doi.org/10.26434/chemrxiv.13521527\">10.26434/chemrxiv.13521527</a>.","ieee":"L. Schmermund <i>et al.</i>, “Switching between enantiomers by combining chromoselective photocatalysis and biocatalysis.” ChemRxiv.","apa":"Schmermund, L., Reischauer, S., Bierbaumer, S., Winkler, C., Diaz-Rodriguez, A., Edwards, L. J., … Kroutil, W. (n.d.). Switching between enantiomers by combining chromoselective photocatalysis and biocatalysis. ChemRxiv. <a href=\"https://doi.org/10.26434/chemrxiv.13521527\">https://doi.org/10.26434/chemrxiv.13521527</a>"},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.26434/chemrxiv.13521527"}],"month":"01","article_processing_charge":"No","oa":1,"date_published":"2021-01-06T00:00:00Z","title":"Switching between enantiomers by combining chromoselective photocatalysis and biocatalysis"},{"date_created":"2022-09-08T15:01:16Z","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2643-1564"]},"quality_controlled":"1","file_date_updated":"2022-09-09T07:23:40Z","date_published":"2021-04-27T00:00:00Z","oa":1,"article_processing_charge":"No","volume":3,"month":"04","citation":{"chicago":"Sun, Zhixiang, Jose M. Guevara, Steffen Sykora, Ekaterina Paerschke, Kaustuv Manna, Andrey Maljuk, Sabine Wurmehl, Jeroen van den Brink, Bernd Büchner, and Christian Hess. “Evidence for a Percolative Mott Insulator-Metal Transition in Doped Sr₂IrO₄.” <i>Physical Review Research</i>. American Physical Society, 2021. <a href=\"https://doi.org/10.1103/physrevresearch.3.023075\">https://doi.org/10.1103/physrevresearch.3.023075</a>.","ama":"Sun Z, Guevara JM, Sykora S, et al. Evidence for a percolative Mott insulator-metal transition in doped Sr₂IrO₄. <i>Physical Review Research</i>. 2021;3(2). doi:<a href=\"https://doi.org/10.1103/physrevresearch.3.023075\">10.1103/physrevresearch.3.023075</a>","apa":"Sun, Z., Guevara, J. M., Sykora, S., Paerschke, E., Manna, K., Maljuk, A., … Hess, C. (2021). Evidence for a percolative Mott insulator-metal transition in doped Sr₂IrO₄. <i>Physical Review Research</i>. American Physical Society. <a href=\"https://doi.org/10.1103/physrevresearch.3.023075\">https://doi.org/10.1103/physrevresearch.3.023075</a>","mla":"Sun, Zhixiang, et al. “Evidence for a Percolative Mott Insulator-Metal Transition in Doped Sr₂IrO₄.” <i>Physical Review Research</i>, vol. 3, no. 2, 023075, American Physical Society, 2021, doi:<a href=\"https://doi.org/10.1103/physrevresearch.3.023075\">10.1103/physrevresearch.3.023075</a>.","ieee":"Z. Sun <i>et al.</i>, “Evidence for a percolative Mott insulator-metal transition in doped Sr₂IrO₄,” <i>Physical Review Research</i>, vol. 3, no. 2. American Physical Society, 2021.","ista":"Sun Z, Guevara JM, Sykora S, Paerschke E, Manna K, Maljuk A, Wurmehl S, van den Brink J, Büchner B, Hess C. 2021. Evidence for a percolative Mott insulator-metal transition in doped Sr₂IrO₄. Physical Review Research. 3(2), 023075.","short":"Z. Sun, J.M. Guevara, S. Sykora, E. Paerschke, K. Manna, A. Maljuk, S. Wurmehl, J. van den Brink, B. Büchner, C. Hess, Physical Review Research 3 (2021)."},"date_updated":"2022-09-09T07:26:01Z","type":"journal_article","publisher":"American Physical Society","status":"public","intvolume":"         3","doi":"10.1103/physrevresearch.3.023075","_id":"12071","year":"2021","article_type":"original","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Zhixiang","last_name":"Sun","full_name":"Sun, Zhixiang"},{"full_name":"Guevara, Jose M.","last_name":"Guevara","first_name":"Jose M."},{"last_name":"Sykora","full_name":"Sykora, Steffen","first_name":"Steffen"},{"last_name":"Paerschke","full_name":"Paerschke, Ekaterina","id":"8275014E-6063-11E9-9B7F-6338E6697425","first_name":"Ekaterina","orcid":"0000-0003-0853-8182"},{"first_name":"Kaustuv","full_name":"Manna, Kaustuv","last_name":"Manna"},{"last_name":"Maljuk","first_name":"Andrey","full_name":"Maljuk, Andrey"},{"first_name":"Sabine","last_name":"Wurmehl","full_name":"Wurmehl, Sabine"},{"last_name":"van den Brink","first_name":"Jeroen","full_name":"van den Brink, Jeroen"},{"first_name":"Bernd","last_name":"Büchner","full_name":"Büchner, Bernd"},{"last_name":"Hess","full_name":"Hess, Christian","first_name":"Christian"}],"title":"Evidence for a percolative Mott insulator-metal transition in doped Sr₂IrO₄","file":[{"creator":"dernst","checksum":"73f1331b9716295849e87a7d3acd9323","file_id":"12075","date_updated":"2022-09-09T07:23:40Z","relation":"main_file","access_level":"open_access","date_created":"2022-09-09T07:23:40Z","file_name":"2021_PhysicalRevResearch_Sun.pdf","success":1,"content_type":"application/pdf","file_size":4020901}],"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"},"publication_status":"published","extern":"1","scopus_import":"1","article_number":"023075","has_accepted_license":"1","oa_version":"Published Version","issue":"2","publication":"Physical Review Research","abstract":[{"lang":"eng","text":"Despite many efforts to rationalize the strongly correlated electronic ground states in doped Mott insulators, the nature of the doping-induced insulator-to-metal transition is still a subject under intensive investigation. Here, we probe the nanoscale electronic structure of the Mott insulator Sr₂IrO₄δ with low-temperature scanning tunneling microscopy and find an enhanced local density of states (LDOS) inside the Mott gap at the location of individual defects which we interpret as defects at apical oxygen sites. A chiral behavior in the topography for those defects has been observed. We also visualize the local enhanced conductance arising from the overlapping of defect states which induces finite LDOS inside of the Mott gap. By combining these findings with the typical spatial extension of isolated defects of about 2 nm, our results indicate that the insulator-to-metal transition in Sr₂IrO₄−δ could be percolative in nature."}],"day":"27","ddc":["530"]},{"author":[{"full_name":"Ding, Pingtao","first_name":"Pingtao","last_name":"Ding"},{"full_name":"Sakai, Toshiyuki","first_name":"Toshiyuki","last_name":"Sakai"},{"last_name":"Krishna Shrestha","first_name":"Ram","full_name":"Krishna Shrestha, Ram"},{"last_name":"Manosalva Perez","full_name":"Manosalva Perez, Nicolas","first_name":"Nicolas"},{"last_name":"Guo","full_name":"Guo, Wenbin","first_name":"Wenbin"},{"full_name":"Ngou, Bruno Pok Man","first_name":"Bruno Pok Man","last_name":"Ngou"},{"full_name":"He, Shengbo","last_name":"He","first_name":"Shengbo"},{"full_name":"Liu, Chang","first_name":"Chang","last_name":"Liu"},{"orcid":"0000-0002-4008-1234","id":"e0164712-22ee-11ed-b12a-d80fcdf35958","full_name":"Feng, Xiaoqi","first_name":"Xiaoqi","last_name":"Feng"},{"full_name":"Zhang, Runxuan","last_name":"Zhang","first_name":"Runxuan"},{"first_name":"Klaas","last_name":"Vandepoele","full_name":"Vandepoele, Klaas"},{"last_name":"MacLean","full_name":"MacLean, Dan","first_name":"Dan"},{"last_name":"Jones","full_name":"Jones, Jonathan D G","first_name":"Jonathan D G"}],"external_id":{"pmid":["34387350"]},"department":[{"_id":"XiFe"}],"title":"Chromatin accessibility landscapes activated by cell-surface and intracellular immune receptors","extern":"1","publication_status":"published","scopus_import":"1","publication":"Journal of Experimental Botany","issue":"22","abstract":[{"lang":"eng","text":"Activation of cell-surface and intracellular receptor-mediated immunity results in rapid transcriptional reprogramming that underpins disease resistance. However, the mechanisms by which co-activation of both immune systems lead to transcriptional changes are not clear. Here, we combine RNA-seq and ATAC-seq to define changes in gene expression and chromatin accessibility. Activation of cell-surface or intracellular receptor-mediated immunity, or both, increases chromatin accessibility at induced defence genes. Analysis of ATAC-seq and RNA-seq data combined with publicly available information on transcription factor DNA-binding motifs enabled comparison of individual gene regulatory networks activated by cell-surface or intracellular receptor-mediated immunity, or by both. These results and analyses reveal overlapping and conserved transcriptional regulatory mechanisms between the two immune systems."}],"day":"13","oa_version":"None","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0022-0957","1460-2431"]},"quality_controlled":"1","date_created":"2023-01-16T09:14:35Z","month":"08","volume":72,"article_processing_charge":"No","citation":{"short":"P. Ding, T. Sakai, R. Krishna Shrestha, N. Manosalva Perez, W. Guo, B.P.M. Ngou, S. He, C. Liu, X. Feng, R. Zhang, K. Vandepoele, D. MacLean, J.D.G. Jones, Journal of Experimental Botany 72 (2021) 7927–7941.","ista":"Ding P, Sakai T, Krishna Shrestha R, Manosalva Perez N, Guo W, Ngou BPM, He S, Liu C, Feng X, Zhang R, Vandepoele K, MacLean D, Jones JDG. 2021. Chromatin accessibility landscapes activated by cell-surface and intracellular immune receptors. Journal of Experimental Botany. 72(22), 7927–7941.","ama":"Ding P, Sakai T, Krishna Shrestha R, et al. Chromatin accessibility landscapes activated by cell-surface and intracellular immune receptors. <i>Journal of Experimental Botany</i>. 2021;72(22):7927-7941. doi:<a href=\"https://doi.org/10.1093/jxb/erab373\">10.1093/jxb/erab373</a>","chicago":"Ding, Pingtao, Toshiyuki Sakai, Ram Krishna Shrestha, Nicolas Manosalva Perez, Wenbin Guo, Bruno Pok Man Ngou, Shengbo He, et al. “Chromatin Accessibility Landscapes Activated by Cell-Surface and Intracellular Immune Receptors.” <i>Journal of Experimental Botany</i>. Oxford University Press, 2021. <a href=\"https://doi.org/10.1093/jxb/erab373\">https://doi.org/10.1093/jxb/erab373</a>.","ieee":"P. Ding <i>et al.</i>, “Chromatin accessibility landscapes activated by cell-surface and intracellular immune receptors,” <i>Journal of Experimental Botany</i>, vol. 72, no. 22. Oxford University Press, pp. 7927–7941, 2021.","mla":"Ding, Pingtao, et al. “Chromatin Accessibility Landscapes Activated by Cell-Surface and Intracellular Immune Receptors.” <i>Journal of Experimental Botany</i>, vol. 72, no. 22, Oxford University Press, 2021, pp. 7927–41, doi:<a href=\"https://doi.org/10.1093/jxb/erab373\">10.1093/jxb/erab373</a>.","apa":"Ding, P., Sakai, T., Krishna Shrestha, R., Manosalva Perez, N., Guo, W., Ngou, B. P. M., … Jones, J. D. G. (2021). Chromatin accessibility landscapes activated by cell-surface and intracellular immune receptors. <i>Journal of Experimental Botany</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/jxb/erab373\">https://doi.org/10.1093/jxb/erab373</a>"},"date_published":"2021-08-13T00:00:00Z","acknowledgement":"We thank the Gatsby Foundation (UK) for funding to the JDGJ laboratory. PD acknowledges support from the European Union’s Horizon 2020 Research and Innovation Program under Marie Skłodowska Curie Actions (grant agreement: 656243) and a Future Leader Fellowship from the Biotechnology and Biological Sciences Research Council (BBSRC) (grant agreement: BB/R012172/1). TS, RKS, DM, and JDGJ were supported by the Gatsby Foundation funding to the\r\nSainsbury Laboratory. NMP and KV were supported by a BOF grant from Ghent University (grant agreement: BOF24Y2019001901). WG and RZ were supported by the Scottish Government Rural and Environment Science and Analytical Services division (RESAS), and RZ also acknowledges the support from a BBSRC Bioinformatics and Biological Resources Fund (grant agreement: BB/S020160/1).BPMN was supported by the Norwich Research Park (NRP) Biosciences Doctoral Training Partnership (DTP) funded by the BBSRC (grant agreement: BB/M011216/1). SH and XF were supported by a BBSRC Responsive Mode grant (grant agreement: BB/S009620/1) and a European Research Council Starting grant ‘SexMeth’ (grant agreement: 804981). CL was supported by Deutsche Forschungsgemeinschaft (grant agreement: LI 2862/4). ","doi":"10.1093/jxb/erab373","date_updated":"2023-05-08T11:01:18Z","status":"public","keyword":["Plant Science","Physiology"],"type":"journal_article","publisher":"Oxford University Press","intvolume":"        72","article_type":"original","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12186","page":"7927-7941","year":"2021","pmid":1},{"doi":"10.1038/s41557-021-00752-9","date_updated":"2024-10-14T12:11:57Z","keyword":["General Chemical Engineering","General Chemistry"],"publisher":"Springer Nature","status":"public","type":"journal_article","intvolume":"        13","article_type":"original","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"13357","page":"940-949","year":"2021","pmid":1,"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1755-4349"],"issn":["1755-4330"]},"quality_controlled":"1","date_created":"2023-08-01T09:34:54Z","oa":1,"month":"10","article_processing_charge":"No","volume":13,"citation":{"ista":"Bian T, Gardin A, Gemen J, Houben L, Perego C, Lee B, Elad N, Chu Z, Pavan GM, Klajn R. 2021. Electrostatic co-assembly of nanoparticles with oppositely charged small molecules into static and dynamic superstructures. Nature Chemistry. 13(10), 940–949.","short":"T. Bian, A. Gardin, J. Gemen, L. Houben, C. Perego, B. Lee, N. Elad, Z. Chu, G.M. Pavan, R. Klajn, Nature Chemistry 13 (2021) 940–949.","ama":"Bian T, Gardin A, Gemen J, et al. Electrostatic co-assembly of nanoparticles with oppositely charged small molecules into static and dynamic superstructures. <i>Nature Chemistry</i>. 2021;13(10):940-949. doi:<a href=\"https://doi.org/10.1038/s41557-021-00752-9\">10.1038/s41557-021-00752-9</a>","chicago":"Bian, Tong, Andrea Gardin, Julius Gemen, Lothar Houben, Claudio Perego, Byeongdu Lee, Nadav Elad, Zonglin Chu, Giovanni M. Pavan, and Rafal Klajn. “Electrostatic Co-Assembly of Nanoparticles with Oppositely Charged Small Molecules into Static and Dynamic Superstructures.” <i>Nature Chemistry</i>. Springer Nature, 2021. <a href=\"https://doi.org/10.1038/s41557-021-00752-9\">https://doi.org/10.1038/s41557-021-00752-9</a>.","apa":"Bian, T., Gardin, A., Gemen, J., Houben, L., Perego, C., Lee, B., … Klajn, R. (2021). Electrostatic co-assembly of nanoparticles with oppositely charged small molecules into static and dynamic superstructures. <i>Nature Chemistry</i>. Springer Nature. <a href=\"https://doi.org/10.1038/s41557-021-00752-9\">https://doi.org/10.1038/s41557-021-00752-9</a>","ieee":"T. Bian <i>et al.</i>, “Electrostatic co-assembly of nanoparticles with oppositely charged small molecules into static and dynamic superstructures,” <i>Nature Chemistry</i>, vol. 13, no. 10. Springer Nature, pp. 940–949, 2021.","mla":"Bian, Tong, et al. “Electrostatic Co-Assembly of Nanoparticles with Oppositely Charged Small Molecules into Static and Dynamic Superstructures.” <i>Nature Chemistry</i>, vol. 13, no. 10, Springer Nature, 2021, pp. 940–49, doi:<a href=\"https://doi.org/10.1038/s41557-021-00752-9\">10.1038/s41557-021-00752-9</a>."},"date_published":"2021-10-01T00:00:00Z","extern":"1","publication_status":"published","scopus_import":"1","issue":"10","publication":"Nature Chemistry","abstract":[{"text":"Coulombic interactions can be used to assemble charged nanoparticles into higher-order structures, but the process requires oppositely charged partners that are similarly sized. The ability to mediate the assembly of such charged nanoparticles using structurally simple small molecules would greatly facilitate the fabrication of nanostructured materials and harnessing their applications in catalysis, sensing and photonics. Here we show that small molecules with as few as three electric charges can effectively induce attractive interactions between oppositely charged nanoparticles in water. These interactions can guide the assembly of charged nanoparticles into colloidal crystals of a quality previously only thought to result from their co-crystallization with oppositely charged nanoparticles of a similar size. Transient nanoparticle assemblies can be generated using positively charged nanoparticles and multiply charged anions that are enzymatically hydrolysed into mono- and/or dianions. Our findings demonstrate an approach for the facile fabrication, manipulation and further investigation of static and dynamic nanostructured materials in aqueous environments.","lang":"eng"}],"day":"01","oa_version":"Published Version","author":[{"first_name":"Tong","full_name":"Bian, Tong","last_name":"Bian"},{"first_name":"Andrea","full_name":"Gardin, Andrea","last_name":"Gardin"},{"full_name":"Gemen, Julius","last_name":"Gemen","first_name":"Julius"},{"last_name":"Houben","full_name":"Houben, Lothar","first_name":"Lothar"},{"full_name":"Perego, Claudio","last_name":"Perego","first_name":"Claudio"},{"last_name":"Lee","first_name":"Byeongdu","full_name":"Lee, Byeongdu"},{"full_name":"Elad, Nadav","last_name":"Elad","first_name":"Nadav"},{"last_name":"Chu","full_name":"Chu, Zonglin","first_name":"Zonglin"},{"first_name":"Giovanni M.","last_name":"Pavan","full_name":"Pavan, Giovanni M."},{"first_name":"Rafal","last_name":"Klajn","full_name":"Klajn, Rafal","id":"8e84690e-1e48-11ed-a02b-a1e6fb8bb53b"}],"external_id":{"pmid":["34489564"]},"main_file_link":[{"url":"https://doi.org/10.1038/s41557-021-00752-9","open_access":"1"}],"title":"Electrostatic co-assembly of nanoparticles with oppositely charged small molecules into static and dynamic superstructures"},{"intvolume":"        60","keyword":["General Chemistry","Catalysis"],"publisher":"Wiley","status":"public","type":"journal_article","date_updated":"2023-08-02T07:22:23Z","doi":"10.1002/anie.202014963","year":"2021","page":"5859-5863","_id":"13358","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_type":"original","date_created":"2023-08-01T09:35:06Z","quality_controlled":"1","publication_identifier":{"eissn":["1521-3773"],"issn":["1433-7851"]},"language":[{"iso":"eng"}],"date_published":"2021-03-08T00:00:00Z","citation":{"ista":"Ryssy J, Natarajan AK, Wang J, Lehtonen AJ, Nguyen M, Klajn R, Kuzyk A. 2021. Light‐responsive dynamic DNA‐origami‐based plasmonic assemblies. Angewandte Chemie International Edition. 60(11), 5859–5863.","short":"J. Ryssy, A.K. Natarajan, J. Wang, A.J. Lehtonen, M. Nguyen, R. Klajn, A. Kuzyk, Angewandte Chemie International Edition 60 (2021) 5859–5863.","apa":"Ryssy, J., Natarajan, A. K., Wang, J., Lehtonen, A. J., Nguyen, M., Klajn, R., &#38; Kuzyk, A. (2021). Light‐responsive dynamic DNA‐origami‐based plasmonic assemblies. <i>Angewandte Chemie International Edition</i>. Wiley. <a href=\"https://doi.org/10.1002/anie.202014963\">https://doi.org/10.1002/anie.202014963</a>","mla":"Ryssy, Joonas, et al. “Light‐responsive Dynamic DNA‐origami‐based Plasmonic Assemblies.” <i>Angewandte Chemie International Edition</i>, vol. 60, no. 11, Wiley, 2021, pp. 5859–63, doi:<a href=\"https://doi.org/10.1002/anie.202014963\">10.1002/anie.202014963</a>.","ieee":"J. Ryssy <i>et al.</i>, “Light‐responsive dynamic DNA‐origami‐based plasmonic assemblies,” <i>Angewandte Chemie International Edition</i>, vol. 60, no. 11. Wiley, pp. 5859–5863, 2021.","ama":"Ryssy J, Natarajan AK, Wang J, et al. Light‐responsive dynamic DNA‐origami‐based plasmonic assemblies. <i>Angewandte Chemie International Edition</i>. 2021;60(11):5859-5863. doi:<a href=\"https://doi.org/10.1002/anie.202014963\">10.1002/anie.202014963</a>","chicago":"Ryssy, Joonas, Ashwin K. Natarajan, Jinhua Wang, Arttu J. Lehtonen, Minh‐Kha Nguyen, Rafal Klajn, and Anton Kuzyk. “Light‐responsive Dynamic DNA‐origami‐based Plasmonic Assemblies.” <i>Angewandte Chemie International Edition</i>. Wiley, 2021. <a href=\"https://doi.org/10.1002/anie.202014963\">https://doi.org/10.1002/anie.202014963</a>."},"volume":60,"article_processing_charge":"No","month":"03","oa":1,"scopus_import":"1","publication_status":"published","extern":"1","related_material":{"link":[{"relation":"erratum","url":"https://doi.org/10.1002/anie.202210394"}]},"oa_version":"Published Version","abstract":[{"text":"DNA nanotechnology offers a versatile toolbox for precise spatial and temporal manipulation of matter on the nanoscale. However, rendering DNA-based systems responsive to light has remained challenging. Herein, we describe the remote manipulation of native (non-photoresponsive) chiral plasmonic molecules (CPMs) using light. Our strategy is based on the use of a photoresponsive medium comprising a merocyanine-based photoacid. Upon exposure to visible light, the medium decreases its pH, inducing the formation of DNA triplex links, leading to a spatial reconfiguration of the CPMs. The process can be reversed simply by turning the light off and it can be repeated for multiple cycles. The degree of the overall chirality change in an ensemble of CPMs depends on the CPM fraction undergoing reconfiguration, which, remarkably, depends on and can be tuned by the intensity of incident light. Such a dynamic, remotely controlled system could aid in further advancing DNA-based devices and nanomaterials.","lang":"eng"}],"day":"08","publication":"Angewandte Chemie International Edition","issue":"11","author":[{"full_name":"Ryssy, Joonas","first_name":"Joonas","last_name":"Ryssy"},{"first_name":"Ashwin K.","full_name":"Natarajan, Ashwin K.","last_name":"Natarajan"},{"full_name":"Wang, Jinhua","last_name":"Wang","first_name":"Jinhua"},{"last_name":"Lehtonen","full_name":"Lehtonen, Arttu J.","first_name":"Arttu J."},{"last_name":"Nguyen","full_name":"Nguyen, Minh‐Kha","first_name":"Minh‐Kha"},{"full_name":"Klajn, Rafal","last_name":"Klajn","first_name":"Rafal","id":"8e84690e-1e48-11ed-a02b-a1e6fb8bb53b"},{"first_name":"Anton","last_name":"Kuzyk","full_name":"Kuzyk, Anton"}],"title":"Light‐responsive dynamic DNA‐origami‐based plasmonic assemblies","main_file_link":[{"url":"https://doi.org/10.1002/anie.202014963","open_access":"1"}]}]