TY - CONF AB - In this paper, we study the problem of opening centers to cluster a set of clients in a metric space so as to minimize the sum of the costs of the centers and of the cluster radii, in a dynamic environment where clients arrive and depart, and the solution must be updated efficiently while remaining competitive with respect to the current optimal solution. We call this dynamic sum-of-radii clustering problem. We present a data structure that maintains a solution whose cost is within a constant factor of the cost of an optimal solution in metric spaces with bounded doubling dimension and whose worst-case update time is logarithmic in the parameters of the problem. AU - Henzinger, Monika H AU - Leniowski, Dariusz AU - Mathieu, Claire ID - 11832 SN - 1868-8969 T2 - 25th Annual European Symposium on Algorithms TI - Dynamic clustering to minimize the sum of radii VL - 87 ER - TY - CONF AB - We consider the problem of maintaining an approximately maximum (fractional) matching and an approximately minimum vertex cover in a dynamic graph. Starting with the seminal paper by Onak and Rubinfeld [STOC 2010], this problem has received significant attention in recent years. There remains, however, a polynomial gap between the best known worst case update time and the best known amortised update time for this problem, even after allowing for randomisation. Specifically, Bernstein and Stein [ICALP 2015, SODA 2016] have the best known worst case update time. They present a deterministic data structure with approximation ratio (3/2 + ∊) and worst case update time O(m1/4/ ∊2), where m is the number of edges in the graph. In recent past, Gupta and Peng [FOCS 2013] gave a deterministic data structure with approximation ratio (1+ ∊) and worst case update time No known randomised data structure beats the worst case update times of these two results. In contrast, the paper by Onak and Rubinfeld [STOC 2010] gave a randomised data structure with approximation ratio O(1) and amortised update time O(log2 n), where n is the number of nodes in the graph. This was later improved by Baswana, Gupta and Sen [FOCS 2011] and Solomon [FOCS 2016], leading to a randomised date structure with approximation ratio 2 and amortised update time O(1). We bridge the polynomial gap between the worst case and amortised update times for this problem, without using any randomisation. We present a deterministic data structure with approximation ratio (2 + ∊) and worst case update time O(log3 n), for all sufficiently small constants ∊. AU - Bhattacharya, Sayan AU - Henzinger, Monika H AU - Nanongkai, Danupon ID - 11874 T2 - 28th Annual ACM-SIAM Symposium on Discrete Algorithms TI - Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time ER - TY - CONF AB - We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic O(m log2 n log log2 n) time algorithm. This improves both on the best previously known deterministic running time of O(m log12 n) (Kawarabayashi and Thorup [12]) and the best previously known randomized running time of O(mlog3n) (Karger [11]) for this problem, though Karger's algorithm can be further applied to weighted graphs. Our approach is using the Kawarabayashi and Tho- rup graph compression technique, which repeatedly finds low-conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow- based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow and diffusion based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that is both local and produces low conductance cuts. Thus, it may be of independent interest. AU - Henzinger, Monika H AU - Rao, Satish AU - Wang, Di ID - 11873 T2 - 28th Annual ACM-SIAM Symposium on Discrete Algorithms TI - Local flow partitioning for faster edge connectivity ER - TY - CONF AB - Graph Sparsification aims at compressing large graphs into smaller ones while (approximately) preserving important characteristics of the input graph. In this work we study Vertex Sparsifiers, i.e., sparsifiers whose goal is to reduce the number of vertices. Given a weighted graph G=(V,E), and a terminal set K with |K|=k, a quality-q vertex cut sparsifier of G is a graph H with K contained in V_H that preserves the value of minimum cuts separating any bipartition of K, up to a factor of q. We show that planar graphs with all the k terminals lying on the same face admit quality-1 vertex cut sparsifier of size O(k^2) that are also planar. Our result extends to vertex flow and distance sparsifiers. It improves the previous best known bound of O(k^2 2^(2k)) for cut and flow sparsifiers by an exponential factor, and matches an Omega(k^2) lower-bound for this class of graphs. We also study vertex reachability sparsifiers for directed graphs. Given a digraph G=(V,E) and a terminal set K, a vertex reachability sparsifier of G is a digraph H=(V_H,E_H), K contained in V_H that preserves all reachability information among terminal pairs. We introduce the notion of reachability-preserving minors, i.e., we require H to be a minor of G. Among others, for general planar digraphs, we construct reachability-preserving minors of size O(k^2 log^2 k). We complement our upper-bound by showing that there exists an infinite family of acyclic planar digraphs such that any reachability-preserving minor must have Omega(k^2) vertices. AU - Goranci, Gramoz AU - Henzinger, Monika H AU - Peng, Pan ID - 11831 SN - 1868-8969 T2 - 25th Annual European Symposium on Algorithms TI - Improved guarantees for vertex sparsification in planar graphs VL - 87 ER - TY - JOUR AB - Online social networks allow the collection of large amounts of data about the influence between users connected by a friendship-like relationship. When distributing items among agents forming a social network, this information allows us to exploit network externalities that each agent receives from his neighbors that get the same item. In this paper we consider Friends-of-Friends (2-hop) network externalities, i.e., externalities that not only depend on the neighbors that get the same item but also on neighbors of neighbors. For these externalities we study a setting where multiple different items are assigned to unit-demand agents. Specifically, we study the problem of welfare maximization under different types of externality functions. Let n be the number of agents and m be the number of items. Our contributions are the following: (1) We show that welfare maximization is APX-hard; we show that even for step functions with 2-hop (and also with 1-hop) externalities it is NP-hard to approximate social welfare better than (1−1/e). (2) On the positive side we present (i) an 𝑂(𝑛√)-approximation algorithm for general concave externality functions, (ii) an O(log m)-approximation algorithm for linear externality functions, and (iii) a 518(1−1/𝑒)-approximation algorithm for 2-hop step function externalities. We also improve the result from [7] for 1-hop step function externalities by giving a 12(1−1/𝑒)-approximation algorithm. AU - Bhattacharya, Sayan AU - Dvořák, Wolfgang AU - Henzinger, Monika H AU - Starnberger, Martin ID - 11903 IS - 4 JF - Theory of Computing Systems SN - 1432-4350 TI - Welfare maximization with friends-of-friends network externalities VL - 61 ER - TY - JOUR AB - Variation in genotypes may be responsible for differences in dispersal rates, directional biases, and growth rates of individuals. These traits may favor certain genotypes and enhance their spatiotemporal spreading into areas occupied by the less advantageous genotypes. We study how these factors influence the speed of spreading in the case of two competing genotypes under the assumption that spatial variation of the total population is small compared to the spatial variation of the frequencies of the genotypes in the population. In that case, the dynamics of the frequency of one of the genotypes is approximately described by a generalized Fisher–Kolmogorov–Petrovskii–Piskunov (F–KPP) equation. This generalized F–KPP equation with (nonlinear) frequency-dependent diffusion and advection terms admits traveling wave solutions that characterize the invasion of the dominant genotype. Our existence results generalize the classical theory for traveling waves for the F–KPP with constant coefficients. Moreover, in the particular case of the quadratic (monostable) nonlinear growth–decay rate in the generalized F–KPP we study in detail the influence of the variance in diffusion and mean displacement rates of the two genotypes on the minimal wave propagation speed. AU - Kollár, Richard AU - Novak, Sebastian ID - 1191 IS - 3 JF - Bulletin of Mathematical Biology TI - Existence of traveling waves for the generalized F–KPP equation VL - 79 ER - TY - JOUR AB - The way organic multistep synthesis is performed is changing due to the adoption of flow chemical techniques, which has enabled the development of improved methods to make complex molecules. The modular nature of the technique provides not only access to target molecules via linear flow approaches but also for the targeting of structural cores with single systems. This perspective article summarizes the state of the art of continuous multistep synthesis and discusses the main challenges and opportunities in this area. AU - Pieber, Bartholomäus AU - Gilmore, Kerry AU - Seeberger, Peter H. ID - 11976 IS - 3-4 JF - Journal of Flow Chemistry SN - 2062-249X TI - Integrated flow processing - challenges in continuous multistep synthesis VL - 7 ER - TY - JOUR AB - Systems such as fluid flows in channels and pipes or the complex Ginzburg–Landau system, defined over periodic domains, exhibit both continuous symmetries, translational and rotational, as well as discrete symmetries under spatial reflections or complex conjugation. The simplest, and very common symmetry of this type is the equivariance of the defining equations under the orthogonal group O(2). We formulate a novel symmetry reduction scheme for such systems by combining the method of slices with invariant polynomial methods, and show how it works by applying it to the Kuramoto–Sivashinsky system in one spatial dimension. As an example, we track a relative periodic orbit through a sequence of bifurcations to the onset of chaos. Within the symmetry-reduced state space we are able to compute and visualize the unstable manifolds of relative periodic orbits, their torus bifurcations, a transition to chaos via torus breakdown, and heteroclinic connections between various relative periodic orbits. It would be very hard to carry through such analysis in the full state space, without a symmetry reduction such as the one we present here. AU - Budanur, Nazmi B AU - Cvitanović, Predrag ID - 1211 IS - 3-4 JF - Journal of Statistical Physics TI - Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system VL - 167 ER - TY - JOUR AB - The Leidenfrost effect occurs when an object near a hot surface vaporizes rapidly enough to lift itself up and hover. Although well understood for liquids and stiff sublimable solids, nothing is known about the effect with materials whose stiffness lies between these extremes. Here we introduce a new phenomenon that occurs with vaporizable soft solids - the elastic Leidenfrost effect. By dropping hydrogel spheres onto hot surfaces we find that, rather than hovering, they energetically bounce several times their diameter for minutes at a time. With high-speed video during a single impact, we uncover high-frequency microscopic gap dynamics at the sphere/substrate interface. We show how these otherwise-hidden agitations constitute work cycles that harvest mechanical energy from the vapour and sustain the bouncing. Our findings suggest a new strategy for injecting mechanical energy into a widely used class of soft materials, with potential relevance to fields such as active matter, soft robotics and microfluidics. AU - Waitukaitis, Scott R AU - Zuiderwijk, Antal AU - Souslov, Anton AU - Coulais, Corentin AU - Van Hecke, Martin ID - 123 IS - 11 JF - Nature Physics TI - Coupling the Leidenfrost effect and elastic deformations to power sustained bouncing VL - 13 ER - TY - CONF AB - We consider the problems of maintaining approximate maximum matching and minimum vertex cover in a dynamic graph. Starting with the seminal work of Onak and Rubinfeld [STOC 2010], this problem has received significant attention in recent years. Very recently, extending the framework of Baswana, Gupta and Sen [FOCS 2011], Solomon [FOCS 2016] gave a randomized 2-approximation dynamic algorithm for this problem that has amortized update time of O(1) with high probability. We consider the natural open question of derandomizing this result. We present a new deterministic fully dynamic algorithm that maintains a O(1)-approximate minimum vertex cover and maximum fractional matching, with an amortized update time of O(1). Previously, the best deterministic algorithm for this problem was due to Bhattacharya, Henzinger and Italiano [SODA 2015]; it had an approximation ratio of (2+ϵ) and an amortized update time of O(logn/ϵ2). Our result can be generalized to give a fully dynamic O(f3)-approximation algorithm with O(f2) amortized update time for the hypergraph vertex cover and fractional matching problems, where every hyperedge has at most f vertices. AU - Bhattacharya, Sayan AU - Chakrabarty, Deeparnab AU - Henzinger, Monika H ID - 12571 SN - 0302-9743 T2 - 19th International Conference on Integer Programming and Combinatorial Optimization TI - Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time VL - 10328 ER - TY - JOUR AB - A drawing of a graph G is radial if the vertices of G are placed on concentric circles C 1 , . . . , C k with common center c , and edges are drawn radially : every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Toth. AU - Fulek, Radoslav AU - Pelsmajer, Michael AU - Schaefer, Marcus ID - 1113 IS - 1 JF - Journal of Graph Algorithms and Applications TI - Hanani-Tutte for radial planarity VL - 21 ER - TY - JOUR AB - We show that a twisted variant of Linnik’s conjecture on sums of Kloosterman sums leads to an optimal covering exponent for S3. AU - Browning, Timothy D AU - Kumaraswamy, Vinay AU - Steiner, Rapael ID - 169 JF - International Mathematics Research Notices TI - Twisted Linnik implies optimal covering exponent for S3 ER - TY - JOUR AB - We study strong approximation for some algebraic varieties over ℚ which are defined using norm forms. This allows us to confirm a special case of a conjecture due to Harpaz and Wittenberg. AU - Browning, Timothy D AU - Schindler, Damaris ID - 172 JF - International Mathematics Research Notices TI - Strong approximation and a conjecture of Harpaz and Wittenberg ER - TY - JOUR AB - We use a three-pulse ultrafast optical spectroscopy to study the relaxation processes in a frustrated Mott insulator Na2IrO3. By being able to independently produce the out-of-equilibrium bound states (excitons) of doublons and holons with the first pulse and suppress the underlying antiferromagnetic order with the second one, we were able to elucidate the relaxation mechanism of quasiparticles in this system. By observing the difference in the exciton dynamics in the magnetically ordered and disordered phases we found that the mass of this quasiparticle is mostly determined by its interaction with the surrounding spins. AU - Alpichshev, Zhanybek AU - Sie, Edbert AU - Mahmood, Fahad AU - Cao, Gang AU - Gedik, Nuh ID - 393 IS - 23 JF - Physical Review B TI - Origin of the exciton mass in the frustrated Mott insulator Na2IrO3 VL - 96 ER - TY - JOUR AB - We used femtosecond optical pump-probe spectroscopy to study the photoinduced change in reflectivity of thin films of the electron-doped cuprate La2-xCexCuO4 (LCCO) with dopings of x=0.08 (underdoped) and x=0.11 (optimally doped). Above Tc, we observe fluence-dependent relaxation rates that begin at a temperature similar to the one where transport measurements first show signatures of antiferromagnetic correlations. Upon suppressing superconductivity with a magnetic field, it is found that the fluence and temperature dependence of relaxation rates are consistent with bimolecular recombination of electrons and holes across a gap (2ΔAF) originating from antiferromagnetic correlations which comprise the pseudogap in electron-doped cuprates. This can be used to learn about coupling between electrons and high-energy (ω>2ΔAF) excitations in these compounds and set limits on the time scales on which antiferromagnetic correlations are static. AU - Vishik, Inna AU - Mahmood, Fahad AU - Alpichshev, Zhanybek AU - Gedik, Nuh AU - Higgins, Joshu AU - Greene, Richard ID - 392 IS - 11 JF - Physical Review B TI - Ultrafast dynamics in the presence of antiferromagnetic correlations in electron doped cuprate La2 xCexCuO4±δ VL - 95 ER - TY - JOUR AB - Pancreatic cancer has a five-year survival rate of ~8%, with characteristic molecular heterogeneity and restricted treatment options. Targeting metabolism has emerged as a potentially effective therapeutic strategy for cancers such as pancreatic cancer, which are driven by genetic alterations that are not tractable drug targets. Although somatic mitochondrial genome (mtDNA) mutations have been observed in various tumors types, understanding of metabolic genotype-phenotype relationships is limited. AU - Hardie, Rae AU - Van Dam, Ellen AU - Cowley, Mark AU - Han, Ting AU - Balaban, Seher AU - Pajic, Marina AU - Pinese, Mark AU - Iconomou, Mary AU - Shearer, Robert AU - Mckenna, Jessie AU - Miller, David AU - Waddell, Nicola AU - Pearson, John AU - Grimmond, Sean AU - Sazanov, Leonid A AU - Biankin, Andrew AU - Villas Boas, Silas AU - Hoy, Andrew AU - Turner, Nigel AU - Saunders, Darren ID - 443 IS - 2 JF - Cancer & Metabolism TI - Mitochondrial mutations and metabolic adaptation in pancreatic cancer VL - 5 ER - TY - JOUR AB - The Loschmidt echo, defined as the overlap between quantum wave function evolved with different Hamiltonians, quantifies the sensitivity of quantum dynamics to perturbations and is often used as a probe of quantum chaos. In this work we consider the behavior of the Loschmidt echo in the many-body localized phase, which is characterized by emergent local integrals of motion and provides a generic example of nonergodic dynamics. We demonstrate that the fluctuations of the Loschmidt echo decay as a power law in time in the many-body localized phase, in contrast to the exponential decay in few-body ergodic systems. We consider the spin-echo generalization of the Loschmidt echo and argue that the corresponding correlation function saturates to a finite value in localized systems. Slow, power-law decay of fluctuations of such spin-echo-type overlap is related to the operator spreading and is present only in the many-body localized phase, but not in a noninteracting Anderson insulator. While most of the previously considered probes of dephasing dynamics could be understood by approximating physical spin operators with local integrals of motion, the Loschmidt echo and its generalizations crucially depend on the full expansion of the physical operators via local integrals of motion operators, as well as operators which flip local integrals of motion. Hence these probes allow one to get insights into the relation between physical operators and local integrals of motion and access the operator spreading in the many-body localized phase. AU - Maksym Serbyn AU - Abanin, Dimitry A ID - 445 IS - 1 JF - Physical Review B - Condensed Matter and Materials Physics TI - Loschmidt echo in many body localized phases VL - 96 ER - TY - JOUR AB - Most kinesin motors move in only one direction along microtubules. Members of the kinesin-5 subfamily were initially described as unidirectional plus-end-directed motors and shown to produce piconewton forces. However, some fungal kinesin-5 motors are bidirectional. The force production of a bidirectional kinesin-5 has not yet been measured. Therefore, it remains unknown whether the mechanism of the unconventional minus-end-directed motility differs fundamentally from that of plus-end-directed stepping. Using force spectroscopy, we have measured here the forces that ensembles of purified budding yeast kinesin-5 Cin8 produce in microtubule gliding assays in both plus- and minus-end direction. Correlation analysis of pause forces demonstrated that individual Cin8 molecules produce additive forces in both directions of movement. In ensembles, Cin8 motors were able to produce single-motor forces up to a magnitude of ∼1.5 pN. Hence, these properties appear to be conserved within the kinesin-5 subfamily. Force production was largely independent of the directionality of movement, indicating similarities between the motility mechanisms for both directions. These results provide constraints for the development of models for the bidirectional motility mechanism of fission yeast kinesin-5 and provide insight into the function of this mitotic motor. AU - Fallesen, Todd AU - Roostalu, Johanna AU - Düllberg, Christian F AU - Pruessner, Gunnar AU - Surrey, Thomas ID - 453 IS - 9 JF - Biophysical Journal TI - Ensembles of bidirectional kinesin Cin8 produce additive forces in both directions of movement VL - 113 ER - TY - JOUR AB - The computation of the winning set for parity objectives and for Streett objectives in graphs as well as in game graphs are central problems in computer-aided verification, with application to the verification of closed systems with strong fairness conditions, the verification of open systems, checking interface compatibility, well-formedness of specifications, and the synthesis of reactive systems. We show how to compute the winning set on n vertices for (1) parity-3 (aka one-pair Streett) objectives in game graphs in time O(n5/2) and for (2) k-pair Streett objectives in graphs in time O(n2+nklogn). For both problems this gives faster algorithms for dense graphs and represents the first improvement in asymptotic running time in 15 years. AU - Chatterjee, Krishnendu AU - Henzinger, Monika H AU - Loitzenbauer, Veronika ID - 464 IS - 3 JF - Logical Methods in Computer Science SN - 1860-5974 TI - Improved algorithms for parity and Streett objectives VL - 13 ER - TY - JOUR AB - This paper presents a method for simulating water surface waves as a displacement field on a 2D domain. Our method relies on Lagrangian particles that carry packets of water wave energy; each packet carries information about an entire group of wave trains, as opposed to only a single wave crest. Our approach is unconditionally stable and can simulate high resolution geometric details. This approach also presents a straightforward interface for artistic control, because it is essentially a particle system with intuitive parameters like wavelength and amplitude. Our implementation parallelizes well and runs in real time for moderately challenging scenarios. AU - Jeschke, Stefan AU - Wojtan, Christopher J ID - 470 IS - 4 JF - ACM Transactions on Graphics SN - 07300301 TI - Water wave packets VL - 36 ER -