@inproceedings{11919, abstract = {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. Under 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. As 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. Our 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. Finally, 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.}, author = {Bergamaschi, Thiago and Henzinger, Monika H and Gutenberg, Maximilian Probst and Williams, Virginia Vassilevska and Wein, Nicole}, booktitle = {32nd Annual ACM-SIAM Symposium on Discrete Algorithms}, location = {Alexandria, VA, United States}, pages = {1836--1855}, publisher = {Society for Industrial and Applied Mathematics}, title = {{New techniques and fine-grained hardness for dynamic near-additive spanners}}, doi = {10.1137/1.9781611976465.110}, year = {2021}, } @inproceedings{11920, abstract = {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.}, author = {Bhattacharya, Sayan and Henzinger, Monika H and Nanongkai, Danupon and Wu, Xiaowei}, booktitle = {32nd Annual ACM-SIAM Symposium on Discrete Algorithms}, location = {Alexandria, VA, United States}, pages = {2537--2549}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Dynamic set cover: Improved amortized and worst-case update time}}, doi = {10.1137/1.9781611976465.150}, year = {2021}, } @inproceedings{11923, abstract = {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. The 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. Our 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. Our 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.}, author = {Henzinger, Monika H and Neumann, Stefan and Räcke, Harald and Schmid, Stefan}, booktitle = {32nd Annual ACM-SIAM Symposium on Discrete Algorithms}, location = {Alexandria, VA, United States}, pages = {2799--2818}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Tight bounds for online graph partitioning}}, doi = {10.1137/1.9781611976465.166}, year = {2021}, } @inproceedings{11931, abstract = {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.}, author = {Goranci, Gramoz and Henzinger, Monika H and Leniowski, Dariusz and Schulz, Christian and Svozil, Alexander}, booktitle = {2021 Proceedings of the Workshop on Algorithm Engineering and Experiments}, issn = {2164-0300}, location = {Alexandria, VA, United States}, pages = {143 --153}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Fully dynamic k-center clustering in low dimensional metrics}}, doi = {10.1137/1.9781611976472.11}, year = {2021}, } @article{11956, abstract = {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).}, author = {Schmermund, Luca and Reischauer, Susanne and Bierbaumer, Sarah and Winkler, Christoph K. and Diaz‐Rodriguez, Alba and Edwards, Lee J. and Kara, Selin and Mielke, Tamara and Cartwright, Jared and Grogan, Gideon and Pieber, Bartholomäus and Kroutil, Wolfgang}, issn = {1521-3773}, journal = {Angewandte Chemie International Edition}, number = {13}, pages = {6965--6969}, publisher = {Wiley}, title = {{Chromoselective photocatalysis enables stereocomplementary biocatalytic pathways}}, doi = {10.1002/anie.202100164}, volume = {60}, year = {2021}, } @article{11965, abstract = {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 %.}, author = {Reischauer, Susanne and Pieber, Bartholomäus}, issn = {2367-0932}, journal = {ChemPhotoChem}, number = {8}, pages = {716--720}, publisher = {Wiley}, title = {{Recyclable, bifunctional metallaphotocatalysts for C−S cross‐coupling reactions}}, doi = {10.1002/cptc.202100062}, volume = {5}, year = {2021}, } @article{11972, abstract = {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.}, author = {Zhao, Zhouxiang and Reischauer, Susanne and Pieber, Bartholomäus and Delbianco, Martina}, issn = {1463-9270}, journal = {Green Chemistry}, number = {12}, pages = {4524--4530}, publisher = {Royal Society of Chemistry}, title = {{Carbon dot/TiO₂ nanocomposites as photocatalysts for metallaphotocatalytic carbon-heteroatom cross-couplings}}, doi = {10.1039/d1gc01284c}, volume = {23}, year = {2021}, } @article{11974, abstract = {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.}, author = {Reischauer, Susanne and Pieber, Bartholomäus}, issn = {2589-0042}, journal = {iScience}, number = {3}, publisher = {Elsevier}, title = {{Emerging concepts in photocatalytic organic synthesis}}, doi = {10.1016/j.isci.2021.102209}, volume = {24}, year = {2021}, } @article{11981, abstract = {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.}, author = {Cavedon, Cristian and Sletten, Eric T. and Madani, Amiera and Niemeyer, Olaf and Seeberger, Peter H. and Pieber, Bartholomäus}, issn = {1523-7052}, journal = {Organic Letters}, number = {2}, pages = {514--518}, publisher = {American Chemical Society}, title = {{Visible-light-mediated oxidative debenzylation enables the use of benzyl ethers as temporary protecting groups}}, doi = {10.1021/acs.orglett.0c04026}, volume = {23}, year = {2021}, } @unpublished{12068, abstract = {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.}, author = {Cavedon, Cristian and Gisbertz, Sebastian and Vogl, Sarah and Richter, Noah and Schrottke, Stefanie and Teutloff, Christian and Seeberger, Peter H. and Thomas, Arne and Pieber, Bartholomäus}, publisher = {ChemRxiv}, title = {{Photocatalyst-free, visible-light-mediated nickel catalyzed carbon–heteroatom cross-couplings}}, doi = {10.26434/chemrxiv-2021-kt2wr}, year = {2021}, } @unpublished{12070, abstract = {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).}, author = {Schmermund, Luca and Reischauer, Susanne and Bierbaumer, Sarah and Winkler, Christoph and Diaz-Rodriguez, Alba and Edwards, Lee J. and Kara, Selin and Mielke, Tamara and Cartwright, Jared and Grogan, Gideon and Pieber, Bartholomäus and Kroutil, Wolfgang}, publisher = {ChemRxiv}, title = {{Switching between enantiomers by combining chromoselective photocatalysis and biocatalysis}}, doi = {10.26434/chemrxiv.13521527}, year = {2021}, } @article{12071, abstract = {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.}, author = {Sun, Zhixiang and Guevara, Jose M. and Sykora, Steffen and Paerschke, Ekaterina and Manna, Kaustuv and Maljuk, Andrey and Wurmehl, Sabine and van den Brink, Jeroen and Büchner, Bernd and Hess, Christian}, issn = {2643-1564}, journal = {Physical Review Research}, number = {2}, publisher = {American Physical Society}, title = {{Evidence for a percolative Mott insulator-metal transition in doped Sr₂IrO₄}}, doi = {10.1103/physrevresearch.3.023075}, volume = {3}, year = {2021}, } @unpublished{12076, abstract = {We find an asymptotic formula for the number of primitive vectors $(z_1,\ldots,z_4)\in (\mathbb{Z}_{\neq 0})^4$ such that $z_1,\ldots, z_4$ are all squareful and bounded by $B$, and $z_1+\cdots + z_4 = 0$. Our result agrees in the power of $B$ and $\log B$ with the Campana-Manin conjecture of Pieropan, Smeets, Tanimoto and V\'{a}rilly-Alvarado.}, author = {Shute, Alec L}, booktitle = {arXiv}, title = {{Sums of four squareful numbers}}, doi = {10.48550/arXiv.2104.06966}, year = {2021}, } @unpublished{12077, abstract = {We compare the Manin-type conjecture for Campana points recently formulated by Pieropan, Smeets, Tanimoto and V\'{a}rilly-Alvarado with an alternative prediction of Browning and Van Valckenborgh in the special case of the orbifold $(\mathbb{P}^1,D)$, where $D =\frac{1}{2}[0]+\frac{1}{2}[1]+\frac{1}{2}[\infty]$. We find that the two predicted leading constants do not agree, and we discuss whether thin sets could explain this discrepancy. Motivated by this, we provide a counterexample to the Manin-type conjecture for Campana points, by considering orbifolds corresponding to squareful values of binary quadratic forms.}, author = {Shute, Alec L}, booktitle = {arXiv}, title = {{On the leading constant in the Manin-type conjecture for Campana points}}, doi = {10.48550/arXiv.2104.14946}, year = {2021}, }