@inproceedings{11870, abstract = {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.}, author = {Henzinger, Monika H and Krinninger, Sebastian and Nanongkai, Danupon}, booktitle = {46th Annual ACM Symposium on Theory of Computing}, isbn = {978-145032710-7}, issn = {0737-8017}, location = {New York, NY, United States}, publisher = {Association for Computing Machinery}, title = {{Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs}}, doi = {10.1145/2591796.2591869}, year = {2014}, } @inproceedings{11876, abstract = {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.}, author = {Henzinger, Monika H and Krinninger, Sebastian and Nanongkai, Danupon}, booktitle = {25th Annual ACM-SIAM Symposium on Discrete Algorithms}, isbn = {978-1-61197-338-9}, location = {Portland, OR, United States}, pages = {1053--1072}, publisher = {Society for Industrial and Applied Mathematics}, title = {{A subquadratic-time algorithm for decremental single-source shortest paths}}, doi = {10.1137/1.9781611973402.79}, year = {2014}, } @inproceedings{11875, abstract = {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].}, author = {Bhattacharya, Sayan and Henzinger, Monika H and Italiano, Giuseppe F.}, booktitle = {26th Annual ACM-SIAM Symposium on Discrete Algorithms}, isbn = {978-1-61197-374-7}, location = {San Diego, CA, United States}, pages = {785--804}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Deterministic fully dynamic data structures for vertex cover and matching}}, doi = {10.1137/1.9781611973730.54}, year = {2014}, } @article{119, abstract = {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.}, author = {Waitukaitis, Scott R and Lee, Victor and Pierson, James and Forman, Steven and Jaeger, Heinrich}, journal = {APS Physics, Physical Review Letters}, number = {21}, publisher = {American Physical Society}, title = {{Size-dependent same-material tribocharging in insulating grains}}, doi = {10.1103/PhysRevLett.112.218001}, volume = {112}, year = {2014}, } @article{11968, abstract = {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.}, author = {Hofbauer, Harald F. and Schopf, Florian H. and Schleifer, Hannes and Knittelfelder, Oskar L. and Pieber, Bartholomäus and Rechberger, Gerald N. and Wolinski, Heimo and Gaspar, Maria L. and Kappe, C. Oliver and Stadlmann, Johannes and Mechtler, Karl and Zenz, Alexandra and Lohner, Karl and Tehlivets, Oksana and Henry, Susan A. and Kohlwein, Sepp D.}, issn = {1878-1551}, journal = {Developmental Cell}, number = {6}, pages = {P729--739}, publisher = {Elsevier}, title = {{Regulation of gene expression through a transcriptional repressor that senses acyl-chain length in membrane phospholipids}}, doi = {10.1016/j.devcel.2014.04.025}, volume = {29}, year = {2014}, } @article{11967, abstract = {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.}, author = {Moghaddam, Mojtaba Mirhosseini and Pieber, Bartholomäus and Glasnov, Toma and Kappe, C. Oliver}, issn = {1864-564X}, journal = {ChemSusChem}, number = {11}, pages = {3122--3131}, publisher = {Wiley}, title = {{Immobilized iron oxide nanoparticles as stable and reusable catalysts for hydrazine-mediated nitro reductions in continuous flow}}, doi = {10.1002/cssc.201402455}, volume = {7}, year = {2014}, } @article{11987, abstract = {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.}, author = {Pieber, Bartholomäus and Glasnov, Toma and Kappe, C. O.}, issn = {2046-2069}, journal = {RSC Advances}, number = {26}, publisher = {Royal Society of Chemistry}, title = {{Flash carboxylation: Fast lithiation–carboxylation sequence at room temperature in continuous flow}}, doi = {10.1039/c4ra01442a}, volume = {4}, year = {2014}, } @article{1309, abstract = {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.}, author = {Julian Fischer}, journal = {Nonlinear Differential Equations and Applications}, number = {1}, pages = {27 -- 50}, publisher = {Birkhäuser}, title = {{Infinite speed of support propagation for the Derrida-Lebowitz-Speer-Spohn equation and quantum drift-diffusion models}}, doi = {10.1007/s00030-013-0235-0}, volume = {21}, year = {2014}, } @article{1312, abstract = {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.}, author = {Julian Fischer}, journal = {Archive for Rational Mechanics and Analysis}, number = {3}, pages = {771 -- 818}, publisher = {Springer}, title = {{Upper bounds on waiting times for the Thin-film equation: The case of weak slippage}}, doi = {10.1007/s00205-013-0690-0}, volume = {211}, year = {2014}, } @article{1375, abstract = {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.}, author = {Chatterjee, Krishnendu and Henzinger, Monika H and Krinninger, Sebastian and Loitzenbauer, Veronika and Raskin, Michael}, journal = {Theoretical Computer Science}, number = {C}, pages = {104 -- 116}, publisher = {Elsevier}, title = {{Approximating the minimum cycle mean}}, doi = {10.1016/j.tcs.2014.06.031}, volume = {547}, year = {2014}, }