TY - CONF AB - We consider dynamic algorithms for maintaining Single-Source Reachability (SSR) and approximate Single-Source Shortest Paths (SSSP) on n-node m-edge directed graphs under edge deletions (decremental algorithms). The previous fastest algorithm for SSR and SSSP goes back three decades to Even and Shiloach (JACM 1981); it has O(1) query time and O(mn) total update time (i.e., linear amortized update time if all edges are deleted). This algorithm serves as a building block for several other dynamic algorithms. The question whether its total update time can be improved is a major, long standing, open problem. In this paper, we answer this question affirmatively. We obtain a randomized algorithm which, in a simplified form, achieves an Õ(mn0.984) expected total update time for SSR and (1 + ε)-approximate SSSP, where Õ(·) hides poly log n. We also extend our algorithm to achieve roughly the same running time for Strongly Connected Components (SCC), improving the algorithm of Roditty and Zwick (FOCS 2002), and an algorithm that improves the Õ (mn log W)-time algorithm of Bernstein (STOC 2013) for approximating SSSP on weighted directed graphs, where the edge weights are integers from 1 to W. All our algorithms have constant query time in the worst case. AU - Henzinger, Monika H AU - Krinninger, Sebastian AU - Nanongkai, Danupon ID - 11870 SN - 0737-8017 T2 - 46th Annual ACM Symposium on Theory of Computing TI - Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs ER - TY - CONF AB - We study dynamic (1 + ∊)-approximation algorithms for the single-source shortest paths problem in an unweighted undirected n-node m-edge graph under edge deletions. The fastest algorithm for this problem is an algorithm with O(n2+o(1)) total update time and constant query time by Bernstein and Roditty (SODA 2011). In this paper, we improve the total update time to O(n1.8+o(1) + m1+o(1)) while keeping the query time constant. This running time is essentially tight when m = Ω(n1.8) since we need Ω(m) time even in the static setting. For smaller values of m, the running time of our algorithm is subquadratic, and is the first that breaks through the quadratic time barrier. In obtaining this result, we develop a fast algorithm for what we call center cover data structure. We also make non-trivial extensions to our previous techniques called lazy-update and monotone Even-Shiloach trees (ICALP 2013 and FOCS 2013). As by-products of our new techniques, we obtain two new results for the decremental all-pairs shortest-paths problem. Our first result is the first approximation algorithm whose total update time is faster than Õ(mn) for all values of m. Our second result is a new trade-off between the total update time and the additive approximation guarantee. AU - Henzinger, Monika H AU - Krinninger, Sebastian AU - Nanongkai, Danupon ID - 11876 SN - 978-1-61197-338-9 T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms TI - A subquadratic-time algorithm for decremental single-source shortest paths ER - TY - CONF AB - We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph in time per update. In particular, for minimum vertex cover we provide deterministic data structures for maintaining a (2 + ε) approximation in O(log n/ε2) amortized time per update. For maximum matching, we show how to maintain a (3 + e) approximation in O(m1/3/ε2) amortized time per update, and a (4 + ε) approximation in O(m1/3/ε2) worst-case time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld [13]. AU - Bhattacharya, Sayan AU - Henzinger, Monika H AU - Italiano, Giuseppe F. ID - 11875 SN - 978-1-61197-374-7 T2 - 26th Annual ACM-SIAM Symposium on Discrete Algorithms TI - Deterministic fully dynamic data structures for vertex cover and matching ER - TY - JOUR AB - Observations of flowing granular matter have suggested that same-material tribocharging depends on particle size, typically rendering large grains positive and small ones negative. Models assuming the transfer of trapped electrons can account for this trend, but have not been validated. Tracking individual grains in an electric field, we show quantitatively that charge is transferred based on size between materially identical grains. However, the surface density of trapped electrons, measured independently by thermoluminescence techniques, is orders of magnitude too small to account for the scale of charge transferred. This reveals that trapped electrons are not a necessary ingredient for same-material tribocharging. AU - Waitukaitis, Scott R AU - Lee, Victor AU - Pierson, James AU - Forman, Steven AU - Jaeger, Heinrich ID - 119 IS - 21 JF - APS Physics, Physical Review Letters TI - Size-dependent same-material tribocharging in insulating grains VL - 112 ER - TY - JOUR AB - Membrane phospholipids typically contain fatty acids (FAs) of 16 and 18 carbon atoms. This particular chain length is evolutionarily highly conserved and presumably provides maximum stability and dynamic properties to biological membranes in response to nutritional or environmental cues. Here, we show that the relative proportion of C16 versus C18 FAs is regulated by the activity of acetyl-CoA carboxylase (Acc1), the first and rate-limiting enzyme of FA de novo synthesis. Acc1 activity is attenuated by AMPK/Snf1-dependent phosphorylation, which is required to maintain an appropriate acyl-chain length distribution. Moreover, we find that the transcriptional repressor Opi1 preferentially binds to C16 over C18 phosphatidic acid (PA) species: thus, C16-chain containing PA sequesters Opi1 more effectively to the ER, enabling AMPK/Snf1 control of PA acyl-chain length to determine the degree of derepression of Opi1 target genes. These findings reveal an unexpected regulatory link between the major energy-sensing kinase, membrane lipid composition, and transcription. AU - Hofbauer, Harald F. AU - Schopf, Florian H. AU - Schleifer, Hannes AU - Knittelfelder, Oskar L. AU - Pieber, Bartholomäus AU - Rechberger, Gerald N. AU - Wolinski, Heimo AU - Gaspar, Maria L. AU - Kappe, C. Oliver AU - Stadlmann, Johannes AU - Mechtler, Karl AU - Zenz, Alexandra AU - Lohner, Karl AU - Tehlivets, Oksana AU - Henry, Susan A. AU - Kohlwein, Sepp D. ID - 11968 IS - 6 JF - Developmental Cell SN - 1534-5807 TI - Regulation of gene expression through a transcriptional repressor that senses acyl-chain length in membrane phospholipids VL - 29 ER - TY - JOUR AB - An experimentally easy to perform method for the generation of alumina-supported Fe3O4 nanoparticles [(6±1) nm size, 0.67 wt %]and the use of this material in hydrazine-mediated heterogeneously catalyzed reductions of nitroarenes to anilines under batch and continuous-flow conditions is presented. The bench-stable, reusable nano-Fe3O4@Al2O3 catalyst can selectively reduce functionalized nitroarenes at 1 mol % catalyst loading by using a 20 mol % excess of hydrazine hydrate in an elevated temperature regime (150 °C, reaction time 2–6 min in batch). For continuous-flow processing, the catalyst material is packed into dedicated cartridges and used in a commercially available high-temperature/-pressure flow device. In continuous mode, reaction times can be reduced to less than 1 min at 150 °C (30 bar back pressure) in a highly intensified process. The nano-Fe3O4@Al2O3 catalyst demonstrated stable reduction of nitrobenzene (0.5 M in MeOH) for more than 10 h on stream at a productivity of 30 mmol h−1 (0.72 mol per day). Importantly, virtually no leaching of the catalytically active material could be observed by inductively coupled plasma MS monitoring. AU - Moghaddam, Mojtaba Mirhosseini AU - Pieber, Bartholomäus AU - Glasnov, Toma AU - Kappe, C. Oliver ID - 11967 IS - 11 JF - ChemSusChem SN - 1864-5631 TI - Immobilized iron oxide nanoparticles as stable and reusable catalysts for hydrazine-mediated nitro reductions in continuous flow VL - 7 ER - TY - JOUR AB - A method for the direct lithiation of terminal alkynes and heterocycles with subsequent carboxylation in a continuous flow format was developed. This method provides carboxylic acids at ambient conditions within less than five seconds with only little excess of the organometallic base and CO2. AU - Pieber, Bartholomäus AU - Glasnov, Toma AU - Kappe, C. O. ID - 11987 IS - 26 JF - RSC Advances TI - Flash carboxylation: Fast lithiation–carboxylation sequence at room temperature in continuous flow VL - 4 ER - TY - JOUR AB - We show that weak solutions of the Derrida-Lebowitz-Speer-Spohn (DLSS) equation display infinite speed of support propagation. We apply our method to the case of the quantum drift-diffusion equation which augments the DLSS equation with a drift term and possibly a second-order diffusion term. The proof is accomplished using weighted entropy estimates, Hardy's inequality and a family of singular weight functions to derive a differential inequality; the differential inequality shows exponential growth of the weighted entropy, with the growth constant blowing up very fast as the singularity of the weight becomes sharper. To the best of our knowledge, this is the first example of a nonnegativity-preserving higher-order parabolic equation displaying infinite speed of support propagation. AU - Julian Fischer ID - 1309 IS - 1 JF - Nonlinear Differential Equations and Applications TI - Infinite speed of support propagation for the Derrida-Lebowitz-Speer-Spohn equation and quantum drift-diffusion models VL - 21 ER - TY - JOUR AB - We derive upper bounds on the waiting time of solutions to the thin-film equation in the regime of weak slippage n ∈ [2, 32\11). In particular, we give sufficient conditions on the initial data for instantaneous forward motion of the free boundary. For n ∈ (2, 32\11), our estimates are sharp, for n = 2, they are sharp up to a logarithmic correction term. Note that the case n = 2 corresponds-with a grain of salt-to the assumption of the Navier slip condition at the fluid-solid interface. We also obtain results in the regime of strong slippage n ∈ (1,2); however, in this regime we expect them not to be optimal. Our method is based on weighted backward entropy estimates, Hardy's inequality and singular weight functions; we deduce a differential inequality which would enforce blowup of the weighted entropy if the contact line were to remain stationary for too long. AU - Julian Fischer ID - 1312 IS - 3 JF - Archive for Rational Mechanics and Analysis TI - Upper bounds on waiting times for the Thin-film equation: The case of weak slippage VL - 211 ER - TY - JOUR AB - We consider directed graphs where each edge is labeled with an integer weight and study the fundamental algorithmic question of computing the value of a cycle with minimum mean weight. Our contributions are twofold: (1) First we show that the algorithmic question is reducible to the problem of a logarithmic number of min-plus matrix multiplications of n×n-matrices, where n is the number of vertices of the graph. (2) Second, when the weights are nonnegative, we present the first (1+ε)-approximation algorithm for the problem and the running time of our algorithm is Õ(nωlog3(nW/ε)/ε),1 where O(nω) is the time required for the classic n×n-matrix multiplication and W is the maximum value of the weights. With an additional O(log(nW/ε)) factor in space a cycle with approximately optimal weight can be computed within the same time bound. AU - Chatterjee, Krishnendu AU - Henzinger, Monika H AU - Krinninger, Sebastian AU - Loitzenbauer, Veronika AU - Raskin, Michael ID - 1375 IS - C JF - Theoretical Computer Science TI - Approximating the minimum cycle mean VL - 547 ER -