@article{1013, abstract = {From microwave ovens to satellite television to the GPS and data services on our mobile phones, microwave technology is everywhere today. But one technology that has so far failed to prove its worth in this wavelength regime is quantum communication that uses the states of single photons as information carriers. This is because single microwave photons, as opposed to classical microwave signals, are extremely vulnerable to noise from thermal excitations in the channels through which they travel. Two new independent studies, one by Ze-Liang Xiang at Technische Universität Wien (Vienna), Austria, and colleagues [1] and another by Benoît Vermersch at the University of Innsbruck, also in Austria, and colleagues [2] now describe a theoretical protocol for microwave quantum communication that is resilient to thermal and other types of noise. Their approach could become a powerful technique to establish fast links between superconducting data processors in a future all-microwave quantum network.}, author = {Fink, Johannes M}, journal = {Physics}, number = {32}, publisher = {American Physical Society}, title = {{Viewpoint: Microwave quantum states beat the heat}}, doi = {10.1103/Physics.10.32}, volume = {10}, year = {2017}, } @article{10126, author = {Vahid Belarghou, Afshin and Šarić, Anđela and Idema, Timon}, issn = {0006-3495}, journal = {Biophysical Journal}, keywords = {biophysics}, number = {3}, publisher = {Elsevier }, title = {{Curvature mediated interactions in highly curved membranes}}, doi = {10.1016/j.bpj.2016.11.2123}, volume = {112}, year = {2017}, } @article{10175, abstract = {We study periodic homogenization by Γ-convergence of integral functionals with integrands W(x,ξ) having no polynomial growth and which are both not necessarily continuous with respect to the space variable and not necessarily convex with respect to the matrix variable. This allows to deal with homogenization of composite hyperelastic materials consisting of two or more periodic components whose the energy densities tend to infinity as the volume of matter tends to zero, i.e., W(x,ξ)=∑j∈J1Vj(x)Hj(ξ) where {Vj}j∈J is a finite family of open disjoint subsets of RN, with |∂Vj|=0 for all j∈J and ∣∣RN∖⋃j∈JVj|=0, and, for each j∈J, Hj(ξ)→∞ as detξ→0. In fact, our results apply to integrands of type W(x,ξ)=a(x)H(ξ) when H(ξ)→∞ as detξ→0 and a∈L∞(RN;[0,∞[) is 1-periodic and is either continuous almost everywhere or not continuous. When a is not continuous, we obtain a density homogenization formula which is a priori different from the classical one by Braides–Müller. Although applications to hyperelasticity are limited due to the fact that our framework is not consistent with the constraint of noninterpenetration of the matter, our results can be of technical interest to analysis of homogenization of integral functionals.}, author = {Anza Hafsa, Omar and Clozeau, Nicolas and Mandallena, Jean-Philippe}, issn = {2118-7436}, journal = {Annales mathématiques Blaise Pascal}, number = {2}, pages = {135--193}, publisher = {Université Clermont Auvergne}, title = {{Homogenization of nonconvex unbounded singular integrals}}, doi = {10.5802/ambp.367}, volume = {24}, year = {2017}, } @article{103, abstract = {We investigate effects of quasiparticle poisoning in a Majorana island with strong tunnel coupling to normal-metal leads. In addition to the main Coulomb blockade diamonds, "shadow" diamonds appear, shifted by 1e in gate voltage, consistent with transport through an excited (poisoned) state of the island. Comparison to a simple model yields an estimate of parity lifetime for the strongly coupled island (∼1 μs) and sets a bound for a weakly coupled island (>10 μs). Fluctuations in the gate-voltage spacing of Coulomb peaks at high field, reflecting Majorana hybridization, are enhanced by the reduced lever arm at strong coupling. When converted from gate voltage to energy units, fluctuations are consistent with previous measurements.}, author = {Albrecht, S M and Hansen, Esben and Higginbotham, Andrew P and Kuemmeth, Ferdinand and Jespersen, Thomas and Nygård, Jesper and Krogstrup, Peter and Danon, Jeroen and Flensberg, Karsten and Marcus, Charles}, journal = {APS Physics, Physical Review Letters}, number = {13}, publisher = {American Physical Society}, title = {{Transport signatures of quasiparticle poisoning in a majorana island}}, doi = {10.1103/PhysRevLett.118.137701}, volume = {118}, year = {2017}, } @article{10370, abstract = {Eukaryotic cells are densely packed with macromolecular complexes and intertwining organelles, continually transported and reshaped. Intriguingly, organelles avoid clashing and entangling with each other in such limited space. Mitochondria form extensive networks constantly remodeled by fission and fusion. Here, we show that mitochondrial fission is triggered by mechanical forces. Mechano-stimulation of mitochondria – via encounter with motile intracellular pathogens, via external pressure applied by an atomic force microscope, or via cell migration across uneven microsurfaces – results in the recruitment of the mitochondrial fission machinery, and subsequent division. We propose that MFF, owing to affinity for narrow mitochondria, acts as a membrane-bound force sensor to recruit the fission machinery to mechanically strained sites. Thus, mitochondria adapt to the environment by sensing and responding to biomechanical cues. Our findings that mechanical triggers can be coupled to biochemical responses in membrane dynamics may explain how organelles orderly cohabit in the crowded cytoplasm.}, author = {Helle, Sebastian Carsten Johannes and Feng, Qian and Aebersold, Mathias J and Hirt, Luca and Grüter, Raphael R and Vahid, Afshin and Sirianni, Andrea and Mostowy, Serge and Snedeker, Jess G and Šarić, Anđela and Idema, Timon and Zambelli, Tomaso and Kornmann, Benoît}, issn = {2050-084X}, journal = {eLife}, keywords = {general immunology and microbiology, general biochemistry, genetics and molecular biology, general medicine, general neuroscience}, publisher = {eLife Sciences Publications}, title = {{Mechanical force induces mitochondrial fission}}, doi = {10.7554/elife.30292}, volume = {6}, year = {2017}, } @article{10369, abstract = {Biological membranes have a central role in mediating the organization of membrane-curving proteins, a dynamic process that has proven to be challenging to probe experimentally. Using atomic force microscopy, we capture the hierarchically organized assemblies of Bin/amphiphysin/Rvs (BAR) proteins on supported lipid membranes. Their structure reveals distinct long linear aggregates of proteins, regularly spaced by up to 300 nm. Employing accurate free-energy calculations from large-scale coarse-grained computer simulations, we found that the membrane mediates the interaction among protein filaments as a combination of short- and long-ranged interactions. The long-ranged component acts at strikingly long distances, giving rise to a variety of micron-sized ordered patterns. This mechanism may contribute to the long-ranged spatiotemporal control of membrane remodeling by proteins in the cell.}, author = {Simunovic, Mijo and Šarić, Anđela and Henderson, J. Michael and Lee, Ka Yee C. and Voth, Gregory A.}, issn = {2374-7951}, journal = {ACS Central Science}, keywords = {general chemical engineering, general chemistry}, number = {12}, pages = {1246--1253}, publisher = {American Chemical Society}, title = {{Long-range organization of membrane-curving proteins}}, doi = {10.1021/acscentsci.7b00392}, volume = {3}, year = {2017}, } @article{10373, abstract = {Electric charges are conserved. The same would be expected to hold for magnetic charges, yet magnetic monopoles have never been observed. It is therefore surprising that the laws of nonequilibrium thermodynamics, combined with Maxwell’s equations, suggest that colloidal particles heated or cooled in certain polar or paramagnetic solvents may behave as if they carry an electric/magnetic charge. Here, we present numerical simulations that show that the field distribution around a pair of such heated/cooled colloidal particles agrees quantitatively with the theoretical predictions for a pair of oppositely charged electric or magnetic monopoles. However, in other respects, the nonequilibrium colloidal particles do not behave as monopoles: They cannot be moved by a homogeneous applied field. The numerical evidence for the monopole-like fields around heated/cooled colloidal particles is crucial because the experimental and numerical determination of forces between such colloidal particles would be complicated by the presence of other effects, such as thermophoresis.}, author = {Wirnsberger, Peter and Fijan, Domagoj and Lightwood, Roger A. and Šarić, Anđela and Dellago, Christoph and Frenkel, Daan}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, keywords = {multidisciplinary}, number = {19}, pages = {4911--4914}, publisher = {National Academy of Sciences}, title = {{Numerical evidence for thermally induced monopoles}}, doi = {10.1073/pnas.1621494114}, volume = {114}, year = {2017}, } @article{10374, abstract = {The formation of filaments from naturally occurring protein molecules is a process at the core of a range of functional and aberrant biological phenomena, such as the assembly of the cytoskeleton or the appearance of aggregates in Alzheimer's disease. The macroscopic behaviour associated with such processes is remarkably diverse, ranging from simple nucleated growth to highly cooperative processes with a well-defined lagtime. Thus, conventionally, different molecular mechanisms have been used to explain the self-assembly of different proteins. Here we show that this range of behaviour can be quantitatively captured by a single unifying Petri net that describes filamentous growth in terms of aggregate number and aggregate mass concentrations. By considering general features associated with a particular network connectivity, we are able to establish directly the rate-determining steps of the overall aggregation reaction from the system's scaling behaviour. We illustrate the power of this framework on a range of different experimental and simulated aggregating systems. The approach is general and will be applicable to any future extensions of the reaction network of filamentous self-assembly.}, author = {Meisl, Georg and Rajah, Luke and Cohen, Samuel A. I. and Pfammatter, Manuela and Šarić, Anđela and Hellstrand, Erik and Buell, Alexander K. and Aguzzi, Adriano and Linse, Sara and Vendruscolo, Michele and Dobson, Christopher M. and Knowles, Tuomas P. J.}, issn = {2041-6539}, journal = {Chemical Science}, keywords = {general chemistry}, number = {10}, pages = {7087--7097}, publisher = {Royal Society of Chemistry}, title = {{Scaling behaviour and rate-determining steps in filamentous self-assembly}}, doi = {10.1039/c7sc01965c}, volume = {8}, year = {2017}, } @article{10375, abstract = {Cellular membranes exhibit a large variety of shapes, strongly coupled to their function. Many biological processes involve dynamic reshaping of membranes, usually mediated by proteins. This interaction works both ways: while proteins influence the membrane shape, the membrane shape affects the interactions between the proteins. To study these membrane-mediated interactions on closed and anisotropically curved membranes, we use colloids adhered to ellipsoidal membrane vesicles as a model system. We find that two particles on a closed system always attract each other, and tend to align with the direction of largest curvature. Multiple particles form arcs, or, at large enough numbers, a complete ring surrounding the vesicle in its equatorial plane. The resulting vesicle shape resembles a snowman. Our results indicate that these physical interactions on membranes with anisotropic shapes can be exploited by cells to drive macromolecules to preferred regions of cellular or intracellular membranes, and utilized to initiate dynamic processes such as cell division. The same principle could be used to find the midplane of an artificial vesicle, as a first step towards dividing it into two equal parts.}, author = {Vahid, Afshin and Šarić, Anđela and Idema, Timon}, issn = {1744-6848}, journal = {Soft Matter}, keywords = {condensed matter physics, general chemistry}, number = {28}, pages = {4924--4930}, publisher = {Royal Society of Chemistry}, title = {{Curvature variation controls particle aggregation on fluid vesicles}}, doi = {10.1039/c7sm00433h}, volume = {13}, year = {2017}, } @article{10418, abstract = {We present a new proof rule for proving almost-sure termination of probabilistic programs, including those that contain demonic non-determinism. An important question for a probabilistic program is whether the probability mass of all its diverging runs is zero, that is that it terminates "almost surely". Proving that can be hard, and this paper presents a new method for doing so. It applies directly to the program's source code, even if the program contains demonic choice. Like others, we use variant functions (a.k.a. "super-martingales") that are real-valued and decrease randomly on each loop iteration; but our key innovation is that the amount as well as the probability of the decrease are parametric. We prove the soundness of the new rule, indicate where its applicability goes beyond existing rules, and explain its connection to classical results on denumerable (non-demonic) Markov chains.}, author = {Mciver, Annabelle and Morgan, Carroll and Kaminski, Benjamin Lucien and Katoen, Joost P}, issn = {2475-1421}, journal = {Proceedings of the ACM on Programming Languages}, location = {Los Angeles, CA, United States}, number = {POPL}, publisher = {Association for Computing Machinery}, title = {{A new proof rule for almost-sure termination}}, doi = {10.1145/3158121}, volume = {2}, year = {2017}, } @phdthesis{10663, abstract = {The superconducting state of matter enables one to observe quantum effects on the macroscopic scale and hosts many fascinating phenomena. Topological defects of the superconducting order parameter, such as vortices and fluxoid states in multiply connected structures, are often the key ingredients of these phenomena. This dissertation describes a new mode of magnetic force microscopy (Φ0-MFM) for investigating vortex and fluxoid sates in mesoscopic superconducting (SC) structures. The technique relies on the magneto-mechanical coupling of a MFM cantilever to the motion of fluxons. The novelty of the technique is that a magnetic particle attached to the cantilever is used not only to sense the state of a SC structure, but also as a primary source of the inhomogeneous magnetic field which induces that state. Φ0-MFM enables us to map the transitions between tip-induced states during a scan: at the positions of the tip, where the two lowest energy states become degenerate, small oscillations of the tip drive the transitions between these states, which causes a significant shift in the resonant frequency and dissipation of the cantilever. For narrow-wall aluminum rings, the mapped fluxoid transitions form concentric contours on a scan. We show that the changes in the cantilever resonant frequency and dissipation are well-described by a stochastic resonance (SR) of cantilever-driven thermally activated phase slips (TAPS). The SR model allows us to experimentally determine the rate of TAPS and compare it to the Langer-Ambegaokar-McCumber-Halperin (LAMH) theory for TAPS in 1D superconducting structures. Further, we use the SR model to qualitatively study the effects of a locally applied magnetic field on the phase slip rate in rings containing constrictions. The states with multiple vortices or winding numbers could be useful for the development of novel superconducting devices, or the study of vortex interactions and interference effects. Using Φ0-MFM allows us to induce, probe and control fluxoid states in thin wall structures comprised of multiple loops. We show that Φ0-MFM images of the fluxoid transitions allow us to identify the underlying states and to investigate their energetics and dynamics even in complicated structures.}, author = {Polshyn, Hryhoriy}, keywords = {physics, superconductivity, magnetic force microscopy, phase slips}, pages = {103}, publisher = {University of Illinois at Urbana-Champaign}, title = {{Magnetic force microscopy studies of mesoscopic superconducting structures}}, year = {2017}, } @inproceedings{10745, abstract = {New ways to investigate and manipulate fluxoid and vortex states of mesoscopic superconducting structures are of great interest. The states with multiple vortices or winding numbers could be useful for the study of vortex interactions and interference effects, the braiding of Majorana bound states by winding vortices, and the development of novel superconducting devices. We demonstrate a methodology based on magnetic force microscopy that allows us to induce, probe and control fluxoid states in thin wall structures comprised of multiple loops. By using micro-magnet as a source of inhomogeneous magnetic field, we can efficiently explore the configuration space of fluxoid states. Scanning over the structure reveals the energy crossing points of the lowest laying fluxoid states. This is due the strong interaction of cantilever with thermally activated fluxoid transitions at points of degeneracy. We show that measured patterns of fluxoid transitions allow to identify the states, investigate their energetics, and manipulate them. Further, we show that the dynamics of driven fluxoid transitions can be described by stochastic resonance model, which provides a unique way of measuring fluxoid transition rate and related energy barrier for chosen transitions even in complicated structures}, author = {Polshyn, Hryhoriy and Naibert, Tyler and Budakian, Raffi}, booktitle = {APS March Meeting 2017}, issn = {0003-0503}, location = {New Orleans, LA, United States}, number = {4}, publisher = {American Physical Society}, title = {{ Probing and controlling fluxoid states in multiply-connected mesoscopic superconducting structures}}, volume = {62}, year = {2017}, } @inbook{1075, author = {Wenzl, Bernhard}, booktitle = {Austria and America: 20th-Century Cross-Cultural Encounters}, editor = {Parker, Joshua and Poole, Ralph}, isbn = {978-3643908124}, pages = {73 -- 80}, publisher = {LIT Verlag Berlin-Münster-Wien-Zürich-London}, title = {{An American in Allied-occupied Austria: John Dos Passos Reports on "The Vienna Frontier"}}, volume = {15}, year = {2017}, } @article{11066, abstract = {Recent studies have shown that a subset of nucleoporins (Nups) can detach from the nuclear pore complex and move into the nuclear interior to regulate transcription. One such dynamic Nup, called Nup98, has been implicated in gene activation in healthy cells and has been shown to drive leukemogenesis when mutated in patients with acute myeloid leukemia (AML). Here we show that in hematopoietic cells, Nup98 binds predominantly to transcription start sites to recruit the Wdr82–Set1A/COMPASS (complex of proteins associated with Set1) complex, which is required for deposition of the histone 3 Lys4 trimethyl (H3K4me3)-activating mark. Depletion of Nup98 or Wdr82 abolishes Set1A recruitment to chromatin and subsequently ablates H3K4me3 at adjacent promoters. Furthermore, expression of a Nup98 fusion protein implicated in aggressive AML causes mislocalization of H3K4me3 at abnormal regions and up-regulation of associated genes. Our findings establish a function of Nup98 in hematopoietic gene activation and provide mechanistic insight into which Nup98 leukemic fusion proteins promote AML.}, author = {Franks, Tobias M. and McCloskey, Asako and Shokhirev, Maxim Nikolaievich and Benner, Chris and Rathore, Annie and HETZER, Martin W}, issn = {0890-9369}, journal = {Genes & Development}, keywords = {Developmental Biology, Genetics}, number = {22}, pages = {2222--2234}, publisher = {Cold Spring Harbor Laboratory}, title = {{Nup98 recruits the Wdr82–Set1A/COMPASS complex to promoters to regulate H3K4 trimethylation in hematopoietic progenitor cells}}, doi = {10.1101/gad.306753.117}, volume = {31}, year = {2017}, } @article{11067, abstract = {Neural progenitor cells (NeuPCs) possess a unique nuclear architecture that changes during differentiation. Nucleoporins are linked with cell-type-specific gene regulation, coupling physical changes in nuclear structure to transcriptional output; but, whether and how they coordinate with key fate-determining transcription factors is unclear. Here we show that the nucleoporin Nup153 interacts with Sox2 in adult NeuPCs, where it is indispensable for their maintenance and controls neuronal differentiation. Genome-wide analyses show that Nup153 and Sox2 bind and co-regulate hundreds of genes. Binding of Nup153 to gene promoters or transcriptional end sites correlates with increased or decreased gene expression, respectively, and inhibiting Nup153 expression alters open chromatin configurations at its target genes, disrupts genomic localization of Sox2, and promotes differentiation in vitro and a gliogenic fate switch in vivo. Together, these findings reveal that nuclear structural proteins may exert bimodal transcriptional effects to control cell fate.}, author = {Toda, Tomohisa and Hsu, Jonathan Y. and Linker, Sara B. and Hu, Lauren and Schafer, Simon T. and Mertens, Jerome and Jacinto, Filipe V. and HETZER, Martin W and Gage, Fred H.}, issn = {1934-5909}, journal = {Cell Stem Cell}, keywords = {Cell Biology, Genetics, Molecular Medicine}, number = {5}, pages = {618--634.e7}, publisher = {Elsevier}, title = {{Nup153 interacts with Sox2 to enable bimodal gene regulation and maintenance of neural progenitor cells}}, doi = {10.1016/j.stem.2017.08.012}, volume = {21}, year = {2017}, } @article{11065, abstract = {Premature aging disorders provide an opportunity to study the mechanisms that drive aging. In Hutchinson-Gilford progeria syndrome (HGPS), a mutant form of the nuclear scaffold protein lamin A distorts nuclei and sequesters nuclear proteins. We sought to investigate protein homeostasis in this disease. Here, we report a widespread increase in protein turnover in HGPS-derived cells compared to normal cells. We determine that global protein synthesis is elevated as a consequence of activated nucleoli and enhanced ribosome biogenesis in HGPS-derived fibroblasts. Depleting normal lamin A or inducing mutant lamin A expression are each sufficient to drive nucleolar expansion. We further show that nucleolar size correlates with donor age in primary fibroblasts derived from healthy individuals and that ribosomal RNA production increases with age, indicating that nucleolar size and activity can serve as aging biomarkers. While limiting ribosome biogenesis extends lifespan in several systems, we show that increased ribosome biogenesis and activity are a hallmark of premature aging.}, author = {Buchwalter, Abigail and HETZER, Martin W}, issn = {2041-1723}, journal = {Nature Communications}, keywords = {General Physics and Astronomy, General Biochemistry, Genetics and Molecular Biology, General Chemistry}, publisher = {Springer Nature}, title = {{Nucleolar expansion and elevated protein translation in premature aging}}, doi = {10.1038/s41467-017-00322-z}, volume = {8}, year = {2017}, } @inproceedings{1112, abstract = {There has been renewed interest in modelling the behaviour of evolutionary algorithms by more traditional mathematical objects, such as ordinary differential equations or Markov chains. The advantage is that the analysis becomes greatly facilitated due to the existence of well established methods. However, this typically comes at the cost of disregarding information about the process. Here, we introduce the use of stochastic differential equations (SDEs) for the study of EAs. SDEs can produce simple analytical results for the dynamics of stochastic processes, unlike Markov chains which can produce rigorous but unwieldy expressions about the dynamics. On the other hand, unlike ordinary differential equations (ODEs), they do not discard information about the stochasticity of the process. We show that these are especially suitable for the analysis of fixed budget scenarios and present analogs of the additive and multiplicative drift theorems for SDEs. We exemplify the use of these methods for two model algorithms ((1+1) EA and RLS) on two canonical problems(OneMax and LeadingOnes).}, author = {Paixao, Tiago and Pérez Heredia, Jorge}, booktitle = {Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms}, isbn = {978-145034651-1}, location = {Copenhagen, Denmark}, pages = {3 -- 11}, publisher = {ACM}, title = {{An application of stochastic differential equations to evolutionary algorithms}}, doi = {10.1145/3040718.3040729}, year = {2017}, } @article{11518, abstract = {We present spectroscopic follow-up observations of CR7 with ALMA, targeted at constraining the infrared (IR) continuum and [C II]158 mm line-emission at high spatial resolution matched to the HST/WFC3 imaging. CR7 is a luminous Lyα emitting galaxy at z = 6.6 that consists of three separated UV-continuum components. Our observations reveal several well-separated components of [C II] emission. The two most luminous components in [C II] coincide with the brightest UV components (A and B), blueshifted by »150 km s−1 with respect to the peak of Lyα emission. Other [C II] components are observed close to UV clumps B and C and are blueshifted by »300 and ≈80 km s−1 with respect to the systemic redshift. We do not detect FIR continuum emission due to dust with a 3σ limiting luminosity LIR T L d 35 K 3.1 10 = <´ 10 ( ) . This allows us to mitigate uncertainties in the dust-corrected SFR and derive SFRs for the three UV clumps A, B, and C of 28, 5, and 7 M yr−1. All clumps have [C II] luminosities consistent within the scatter observed in the local relation between SFR and L[ ] C II , implying that strong Lyα emission does not necessarily anti-correlate with [C II] luminosity. Combining our measurements with the literature, we show that galaxies with blue UV slopes have weaker [C II] emission at fixed SFR, potentially due to their lower metallicities and/or higher photoionization. Comparison with hydrodynamical simulations suggests that CR7ʼs clumps have metallicities of 0.1 Z Z 0.2 < < . The observed ISM structure of CR7 indicates that we are likely witnessing the build up of a central galaxy in the early universe through complex accretion of satellites.}, author = {Matthee, Jorryt J and Sobral, D. and Boone, F. and Röttgering, H. and Schaerer, D. and Girard, M. and Pallottini, A. and Vallini, L. and Ferrara, A. and Darvish, B. and Mobasher, B.}, issn = {1538-4357}, journal = {The Astrophysical Journal}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, dark ages, reionization, first stars – galaxies: formation – galaxies: high-redshift – galaxies: ISM – galaxies: kinematics and dynamics}, number = {2}, publisher = {IOP Publishing}, title = {{ALMA reveals metals yet no dust within multiple components in CR7}}, doi = {10.3847/1538-4357/aa9931}, volume = {851}, year = {2017}, } @article{11562, abstract = {We present the CAlibrating LYMan-α with Hα (CALYMHA) pilot survey and new results on Lyman α (Lyα) selected galaxies at z ∼ 2. We use a custom-built Lyα narrow-band filter at the Isaac Newton Telescope, designed to provide a matched volume coverage to the z = 2.23 Hα HiZELS survey. Here, we present the first results for the COSMOS and UDS fields. Our survey currently reaches a 3σ line flux limit of ∼4 × 10−17 erg s−1 cm−2, and a Lyα luminosity limit of ∼1042.3 erg s−1. We find 188 Lyα emitters over 7.3 × 105 Mpc3, but also find significant numbers of other line-emitting sources corresponding to He II, C III] and C IV emission lines. These sources are important contaminants, and we carefully remove them, unlike most previous studies. We find that the Lyα luminosity function at z = 2.23 is very well described by a Schechter function up to LLy α ≈ 1043 erg s−1 with L∗=1042.59+0.16−0.08 erg s−1, ϕ∗=10−3.09+0.14−0.34 Mpc−3 and α = −1.75 ± 0.25. Above LLy α ≈ 1043 erg s−1, the Lyα luminosity function becomes power-law like, driven by X-ray AGN. We find that Lyα-selected emitters have a high escape fraction of 37 ± 7 per cent, anticorrelated with Lyα luminosity and correlated with Lyα equivalent width. Lyα emitters have ubiquitous large (≈40 kpc) Lyα haloes, ∼2 times larger than their Hα extents. By directly comparing our Lyα and Hα luminosity functions, we find that the global/overall escape fraction of Lyα photons (within a 13 kpc radius) from the full population of star-forming galaxies is 5.1 ± 0.2 per cent at the peak of the star formation history. An extra 3.3 ± 0.3 per cent of Lyα photons likely still escape, but at larger radii.}, author = {Sobral, David and Matthee, Jorryt J and Best, Philip and Stroe, Andra and Röttgering, Huub and Oteo, Iván and Smail, Ian and Morabito, Leah and Paulino-Afonso, Ana}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: evolution, galaxies: haloes, galaxies: high-redshift, galaxies: luminosity function, mass function, galaxies: statistics, cosmology: observations}, number = {1}, pages = {1242--1258}, publisher = {Oxford University Press}, title = {{The CALYMHA survey: Lyα luminosity function and global escape fraction of Lyα photons at z = 2.23}}, doi = {10.1093/mnras/stw3090}, volume = {466}, year = {2017}, } @article{11566, abstract = {While traditionally associated with active galactic nuclei (AGN), the properties of the C II] (λ = 2326 Å), C III] (λ, λ = 1907, 1909 Å) and C IV (λ, λ = 1549, 1551 Å) emission lines are still uncertain as large, unbiased samples of sources are scarce. We present the first blind, statistical study of C II], C III] and C IV emitters at z ∼ 0.68, 1.05, 1.53, respectively, uniformly selected down to a flux limit of ∼4 × 10−17 erg s−1 cm−1 through a narrow-band survey covering an area of ∼1.4 deg2 over COSMOS and UDS. We detect 16 C II], 35 C III] and 17 C IV emitters, whose nature we investigate using optical colours as well as Hubble Space Telescope (HST), X-ray, radio and far-infrared data. We find that z ∼ 0.7 C II] emitters are consistent with a mixture of blue (UV slope β = −2.0 ± 0.4) star-forming (SF) galaxies with discy HST structure and AGN with Seyfert-like morphologies. Bright C II] emitters have individual X-ray detections as well as high average black hole accretion rates (BHARs) of ∼0.1 M⊙ yr−1. C III] emitters at z ∼ 1.05 trace a general population of SF galaxies, with β = −0.8 ± 1.1, a variety of optical morphologies, including isolated and interacting galaxies and low BHAR (<0.02 M⊙ yr−1). Our C IV emitters at z ∼ 1.5 are consistent with young, blue quasars (β ∼ −1.9) with point-like optical morphologies, bright X-ray counterparts and large BHAR (0.8  M⊙ yr−1). We also find some surprising C II], C III] and C IV emitters with rest-frame equivalent widths (EWs) that could be as large as 50–100 Å. AGN or spatial offsets between the UV continuum stellar disc and the line-emitting regions may explain the large EW. These bright C II], C III] and C IV emitters are ideal candidates for spectroscopic follow-up to fully unveil their nature.}, author = {Stroe, Andra and Sobral, David and Matthee, Jorryt J and Calhau, João and Oteo, Ivan}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: active, galaxies: high-redshift, quasars: emission lines, galaxies: star formation, cosmology: observations}, number = {3}, pages = {2558--2574}, publisher = {Oxford University Press}, title = {{A 1.4 deg2 blind survey for C II], C III] and C IV at z ∼ 0.7–1.5 – I. Nature, morphologies and equivalent widths }}, doi = {10.1093/mnras/stx1712}, volume = {471}, year = {2017}, } @article{11564, abstract = {We study the production rate of ionizing photons of a sample of 588 Hα emitters (HAEs) and 160 Lyman-α emitters (LAEs) at z = 2.2 in the COSMOS field in order to assess the implied emissivity from galaxies, based on their ultraviolet (UV) luminosity. By exploring the rest-frame Lyman Continuum (LyC) with GALEX/NUV data, we find fesc < 2.8 (6.4) per cent through median (mean) stacking. By combining the Hα luminosity density with intergalactic medium emissivity measurements from absorption studies, we find a globally averaged 〈fesc〉 of 5.9+14.5−4.2 per cent at z = 2.2 if we assume HAEs are the only source of ionizing photons. We find similarly low values of the global 〈fesc〉 at z ≈ 3–5, also ruling out a high 〈fesc〉 at z < 5. These low escape fractions allow us to measure ξion, the number of produced ionizing photons per unit UV luminosity, and investigate how this depends on galaxy properties. We find a typical ξion ≈ 1024.77 ± 0.04 Hz erg−1 for HAEs and ξion ≈ 1025.14 ± 0.09 Hz erg−1 for LAEs. LAEs and low-mass HAEs at z = 2.2 show similar values of ξion as typically assumed in the reionization era, while the typical HAE is three times less ionizing. Due to an increasing ξion with increasing EW(Hα), ξion likely increases with redshift. This evolution alone is fully in line with the observed evolution of ξion between z ≈ 2 and 5, indicating a typical value of ξion ≈ 1025.4 Hz erg−1 in the reionization era.}, author = {Matthee, Jorryt J and Sobral, David and Best, Philip and Khostovan, Ali Ahmad and Oteo, Iván and Bouwens, Rychard and Röttgering, Huub}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: evolution, galaxies: high-redshift, cosmology: observations, dark ages, reionization, first stars}, number = {3}, pages = {3637--3655}, publisher = {Oxford University Press}, title = {{The production and escape of Lyman-Continuum radiation from star-forming galaxies at z ∼ 2 and their redshift evolution}}, doi = {10.1093/mnras/stw2973}, volume = {465}, year = {2017}, } @article{11567, abstract = {Recently, the C III] and C IV emission lines have been observed in galaxies in the early Universe (z > 5), providing new ways to measure their redshift and study their stellar populations and active galactic nuclei (AGN). We explore the first blind C II], C III] and C IV survey (z ∼ 0.68, 1.05, 1.53, respectively) presented in Stroe et al. (2017). We derive luminosity functions (LF) and study properties of C II], C III] and C IV line emitters through comparisons to the LFs of H α and Ly α emitters, UV selected star-forming (SF) galaxies and quasars at similar redshifts. The C II] LF at z ∼ 0.68 is equally well described by a Schechter or a power-law LF, characteristic of a mixture of SF and AGN activity. The C III] LF (z ∼ 1.05) is consistent to a scaled down version of the Schechter H α and Ly α LF at their redshift, indicating a SF origin. In stark contrast, the C IV LF at z ∼ 1.53 is well fit by a power-law, quasar-like LF. We find that the brightest UV sources (MUV < −22) will universally have C III] and C IV emission. However, on average, C III] and C IV are not as abundant as H α or Ly α emitters at the same redshift, with cosmic average ratios of ∼0.02–0.06 to H α and ∼0.01–0.1 to intrinsic Ly α. We predict that the C III] and C IV lines can only be truly competitive in confirming high-redshift candidates when the hosts are intrinsically bright and the effective Ly α escape fraction is below 1 per cent. While C III] and C IV were proposed as good tracers of young, relatively low-metallicity galaxies typical of the early Universe, we find that, at least at z ∼ 1.5, C IV is exclusively hosted by AGN/quasars, especially at large line equivalent widths.}, author = {Stroe, Andra and Sobral, David and Matthee, Jorryt J and Calhau, João and Oteo, Ivan}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: active, galaxies: high redshift, galaxies: luminosity function, mass function, quasars: emission lines, star formation, cosmology: observations}, number = {3}, pages = {2575--2586}, publisher = {Oxford University Press}, title = {{A 1.4 deg2 blind survey for C II], C III] and C IV at z ∼ 0.7–1.5 – II. Luminosity functions and cosmic average line ratios}}, doi = {10.1093/mnras/stx1713}, volume = {471}, year = {2017}, } @article{11565, abstract = {We use the hydrodynamical EAGLE simulation to study the magnitude and origin of the scatter in the stellar mass–halo mass relation for central galaxies. We separate cause and effect by correlating stellar masses in the baryonic simulation with halo properties in a matched dark matter only (DMO) simulation. The scatter in stellar mass increases with redshift and decreases with halo mass. At z = 0.1, it declines from 0.25 dex at M200, DMO ≈ 1011 M⊙ to 0.12 dex at M200, DMO ≈ 1013 M⊙, but the trend is weak above 1012 M⊙. For M200, DMO < 1012.5 M⊙ up to 0.04 dex of the scatter is due to scatter in the halo concentration. At fixed halo mass, a larger stellar mass corresponds to a more concentrated halo. This is likely because higher concentrations imply earlier formation times and hence more time for accretion and star formation, and/or because feedback is less efficient in haloes with higher binding energies. The maximum circular velocity, Vmax, DMO, and binding energy are therefore more fundamental properties than halo mass, meaning that they are more accurate predictors of stellar mass, and we provide fitting formulae for their relations with stellar mass. However, concentration alone cannot explain the total scatter in the Mstar−M200,DMO relation, and it does not explain the scatter in Mstar–Vmax, DMO. Halo spin, sphericity, triaxiality, substructure and environment are also not responsible for the remaining scatter, which thus could be due to more complex halo properties or non-linear/stochastic baryonic effects.}, author = {Matthee, Jorryt J and Schaye, Joop and Crain, Robert A. and Schaller, Matthieu and Bower, Richard and Theuns, Tom}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: evolution, galaxies: formation, galaxies: haloes, cosmology: theory}, number = {2}, pages = {2381--2396}, publisher = {Oxford University Press}, title = {{The origin of scatter in the stellar mass–halo mass relation of central galaxies in the EAGLE simulation}}, doi = {10.1093/mnras/stw2884}, volume = {465}, year = {2017}, } @article{11561, abstract = {We present a sample of ∼1000 emission-line galaxies at z = 0.4–4.7 from the ∼0.7deg2 High-z Emission-Line Survey in the Boötes field identified with a suite of six narrow-band filters at ≈0.4–2.1 μm. These galaxies have been selected on their Ly α (73), [O II] (285), H β/[O III] (387) or H α (362) emission line, and have been classified with optical to near-infrared colours. A subsample of 98 sources have reliable redshifts from multiple narrow-band (e.g. [O II]–H α) detections and/or spectroscopy. In this survey paper, we present the observations, selection and catalogues of emitters. We measure number densities of Ly α, [O II], H β/[O III] and H α and confirm strong luminosity evolution in star-forming galaxies from z ∼ 0.4 to ∼5, in agreement with previous results. To demonstrate the usefulness of dual-line emitters, we use the sample of dual [O II]–H α emitters to measure the observed [O II]/H α ratio at z = 1.47. The observed [O II]/H α ratio increases significantly from 0.40 ± 0.01 at z = 0.1 to 0.52 ± 0.05 at z = 1.47, which we attribute to either decreasing dust attenuation with redshift, or due to a bias in the (typically) fibre measurements in the local Universe that only measure the central kpc regions. At the bright end, we find that both the H α and Ly α number densities at z ≈ 2.2 deviate significantly from a Schechter form, following a power law. We show that this is driven entirely by an increasing X-ray/active galactic nucleus fraction with line luminosity, which reaches ≈100 per cent at line luminosities L ≳ 3 × 1044 erg s−1.}, author = {Matthee, Jorryt J and Sobral, David and Best, Philip and Smail, Ian and Bian, Fuyan and Darvish, Behnam and Röttgering, Huub and Fan, Xiaohui}, issn = {0035-8711}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics galaxies, active, galaxies, evolution, galaxies, high-redshift, galaxies, luminosity function, mass function, galaxies: star formation}, number = {1}, pages = {629--649}, publisher = {Oxford University Press}, title = {{Boötes-HiZELS: An optical to near-infrared survey of emission-line galaxies at z = 0.4–4.7}}, doi = {10.1093/mnras/stx1569}, volume = {471}, year = {2017}, } @article{11572, abstract = {We present spectroscopic follow-up of candidate luminous Ly α emitters (LAEs) at z = 5.7–6.6 in the SA22 field with VLT/X-SHOOTER. We confirm two new luminous LAEs at z = 5.676 (SR6) and z = 6.532 (VR7), and also present HST follow-up of both sources. These sources have luminosities LLy α ≈ 3 × 1043 erg s−1, very high rest-frame equivalent widths of EW0 ≳ 200 Å and narrow Ly α lines (200–340 km s−1). VR7 is the most UV-luminous LAE at z > 6.5, with M1500 = −22.5, even brighter in the UV than CR7. Besides Ly α, we do not detect any other rest-frame UV lines in the spectra of SR6 and VR7, and argue that rest-frame UV lines are easier to observe in bright galaxies with low Ly α equivalent widths. We confirm that Ly α line widths increase with Ly α luminosity at z = 5.7, while there are indications that Ly α lines of faint LAEs become broader at z = 6.6, potentially due to reionization. We find a large spread of up to 3 dex in UV luminosity for >L⋆ LAEs, but find that the Ly α luminosity of the brightest LAEs is strongly related to UV luminosity at z = 6.6. Under basic assumptions, we find that several LAEs at z ≈ 6–7 have Ly α escape fractions ≳ 100  per cent, indicating bursty star formation histories, alternative Ly α production mechanisms, or dust attenuating Ly α emission differently than UV emission. Finally, we present a method to compute ξion, the production efficiency of ionizing photons, and find that LAEs at z ≈ 6–7 have high values of log10(ξion/Hz erg−1) ≈ 25.51 ± 0.09 that may alleviate the need for high Lyman-Continuum escape fractions required for reionization.}, author = {Matthee, Jorryt J and Sobral, David and Darvish, Behnam and Santos, Sérgio and Mobasher, Bahram and Paulino-Afonso, Ana and Röttgering, Huub and Alegre, Lara}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: evolution – galaxies: high-redshift, dark ages, reionization, first stars, cosmology: observations}, number = {1}, pages = {772--787}, publisher = {Oxford University Press}, title = {{Spectroscopic properties of luminous Ly α emitters at z ≈ 6–7 and comparison to the Lyman-break population}}, doi = {10.1093/mnras/stx2061}, volume = {472}, year = {2017}, } @article{11573, abstract = {We present dynamical measurements from the KMOS (K-band multi-object spectrograph) Deep Survey (KDS), which comprises 77 typical star-forming galaxies at z ≃ 3.5 in the mass range 9.0 < log (M⋆/M⊙) < 10.5. These measurements constrain the internal dynamics, the intrinsic velocity dispersions (σint) and rotation velocities (VC) of galaxies in the high-redshift Universe. The mean velocity dispersion of the galaxies in our sample is σint=70.8+3.3−3.1kms−1⁠, revealing that the increasing average σint with increasing redshift, reported for z ≲ 2, continues out to z ≃ 3.5. Only 36 ± 8 per cent of our galaxies are rotation-dominated (VC/σint > 1), with the sample average VC/σint value much smaller than at lower redshift. After carefully selecting comparable star-forming samples at multiple epochs, we find that the rotation-dominated fraction evolves with redshift with a z−0.2 dependence. The rotation-dominated KDS galaxies show no clear offset from the local rotation velocity–stellar mass (i.e. VC–M⋆) relation, although a smaller fraction of the galaxies are on the relation due to the increase in the dispersion-dominated fraction. These observations are consistent with a simple equilibrium model picture, in which random motions are boosted in high-redshift galaxies by a combination of the increasing gas fractions, accretion efficiency, specific star formation rate and stellar feedback and which may provide significant pressure support against gravity on the galactic disc scale.}, author = {Turner, O. J. and Cirasuolo, M. and Harrison, C. M. and McLure, R. J. and Dunlop, J. S. and Swinbank, A. M. and Johnson, H. L. and Sobral, D. and Matthee, Jorryt J and Sharples, R. M.}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: evolution, galaxies: high-redshift, galaxies: kinematics and dynamics}, number = {2}, pages = {1280--1320}, publisher = {Oxford University Press}, title = {{The KMOS Deep Survey (KDS) – I. Dynamical measurements of typical star-forming galaxies at z ≃ 3.5}}, doi = {10.1093/mnras/stx1366}, volume = {471}, year = {2017}, } @unpublished{11633, abstract = {Our understanding of stars through asteroseismic data analysis is limited by our ability to take advantage of the huge amount of observed stars provided by space missions such as CoRoT, Kepler , K2, and soon TESS and PLATO. Global seismic pipelines provide global stellar parameters such as mass and radius using the mean seismic parameters, as well as the effective temperature. These pipelines are commonly used automatically on thousands of stars observed by K2 for 3 months (and soon TESS for at least ∼ 1 month). However, pipelines are not immune from misidentifying noise peaks and stellar oscillations. Therefore, new validation techniques are required to assess the quality of these results. We present a new metric called FliPer (Flicker in Power), which takes into account the average variability at all measured time scales. The proper calibration of FliPer enables us to obtain good estimations of global stellar parameters such as surface gravity that are robust against the influence of noise peaks and hence are an excellent way to find faults in asteroseismic pipelines.}, author = {Bugnet, Lisa Annabelle and Garcia, R. A. and Davies, G. R. and Mathur, S. and Corsaro, E.}, booktitle = {arXiv}, keywords = {asteroseismology - methods, data analysis - stars, oscillations}, title = {{FliPer: Checking the reliability of global seismic parameters from automatic pipelines}}, doi = {10.48550/arXiv.1711.02890}, year = {2017}, } @inproceedings{11651, abstract = {Diffusions and related random walk procedures are of central importance in many areas of machine learning, data analysis, and applied mathematics. Because they spread mass agnostically at each step in an iterative manner, they can sometimes spread mass “too aggressively,” thereby failing to find the “right” clusters. We introduce a novel Capacity Releasing Diffusion (CRD) Process, which is both faster and stays more local than the classical spectral diffusion process. As an application, we use our CRD Process to develop an improved local algorithm for graph clustering. Our local graph clustering method can find local clusters in a model of clustering where one begins the CRD Process in a cluster whose vertices are connected better internally than externally by an O(log2n) factor, where n is the number of nodes in the cluster. Thus, our CRD Process is the first local graph clustering algorithm that is not subject to the well-known quadratic Cheeger barrier. Our result requires a certain smoothness condition, which we expect to be an artifact of our analysis. Our empirical evaluation demonstrates improved results, in particular for realistic social graphs where there are moderately good—but not very good—clusters.}, author = {Wang, Di and Fountoulakis, Kimon and Henzinger, Monika H and Mahoney, Michael W. and Rao , Satish}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, issn = {2640-3498}, location = {Sydney, Australia}, pages = {3598--3607}, publisher = {ML Research Press}, title = {{Capacity releasing diffusion for speed and locality}}, volume = {70}, year = {2017}, } @article{11665, abstract = {We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We present deterministic (1+ϵ)-approximation algorithms whose amortized time (over some number of link changes) is sublinear in D, the maximum diameter of the network. Our technique also leads to a deterministic (1+ϵ)-approximate incremental algorithm for single-source shortest paths in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic exact algorithm of Even and Shiloach (1981), which is optimal under some assumptions (Roditty and Zwick 2011; Henzinger et al. 2015). Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if some approximation is allowed.}, author = {Henzinger, Monika H and Krinninger, Sebastian and Nanongkai, Danupon}, issn = {1549-6333}, journal = {ACM Transactions on Algorithms}, number = {4}, publisher = {Association for Computing Machinery}, title = {{Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks}}, doi = {10.1145/3146550}, volume = {13}, year = {2017}, } @article{11676, abstract = {We study the problem of maximizing a monotone submodular function with viability constraints. This problem originates from computational biology, where we are given a phylogenetic tree over a set of species and a directed graph, the so-called food web, encoding viability constraints between these species. These food webs usually have constant depth. The goal is to select a subset of k species that satisfies the viability constraints and has maximal phylogenetic diversity. As this problem is known to be NP-hard, we investigate approximation algorithms. We present the first constant factor approximation algorithm if the depth is constant. Its approximation ratio is (1−1e√). This algorithm not only applies to phylogenetic trees with viability constraints but for arbitrary monotone submodular set functions with viability constraints. Second, we show that there is no (1−1/e+ϵ)-approximation algorithm for our problem setting (even for additive functions) and that there is no approximation algorithm for a slight extension of this setting.}, author = {Dvořák, Wolfgang and Henzinger, Monika H and Williamson, David P.}, issn = {1432-0541}, journal = {Algorithmica}, keywords = {Approximation algorithms, Submodular functions, Phylogenetic diversity, Viability constraints}, number = {1}, pages = {152--172}, publisher = {Springer Nature}, title = {{Maximizing a submodular function with viability constraints}}, doi = {10.1007/s00453-015-0066-y}, volume = {77}, year = {2017}, } @inproceedings{1175, abstract = {We study space complexity and time-space trade-offs with a focus not on peak memory usage but on overall memory consumption throughout the computation. Such a cumulative space measure was introduced for the computational model of parallel black pebbling by [Alwen and Serbinenko ’15] as a tool for obtaining results in cryptography. We consider instead the non- deterministic black-white pebble game and prove optimal cumulative space lower bounds and trade-offs, where in order to minimize pebbling time the space has to remain large during a significant fraction of the pebbling. We also initiate the study of cumulative space in proof complexity, an area where other space complexity measures have been extensively studied during the last 10–15 years. Using and extending the connection between proof complexity and pebble games in [Ben-Sasson and Nordström ’08, ’11] we obtain several strong cumulative space results for (even parallel versions of) the resolution proof system, and outline some possible future directions of study of this, in our opinion, natural and interesting space measure.}, author = {Alwen, Joel F and De Rezende, Susanna and Nordstrom, Jakob and Vinyals, Marc}, editor = {Papadimitriou, Christos}, issn = {18688969}, location = {Berkeley, CA, United States}, pages = {38:1--38--21}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Cumulative space in black-white pebbling and resolution}}, doi = {10.4230/LIPIcs.ITCS.2017.38}, volume = {67}, year = {2017}, } @inproceedings{11772, abstract = {A dynamic graph algorithm is a data structure that supports operations on dynamically changing graphs.}, author = {Henzinger, Monika H}, booktitle = {44th International Conference on Current Trends in Theory and Practice of Computer Science}, isbn = {9783319731162}, issn = {0302-9743}, location = {Krems, Austria}, pages = {40–44}, publisher = {Springer Nature}, title = {{The state of the art in dynamic graph algorithms}}, doi = {10.1007/978-3-319-73117-9_3}, volume = {10706}, year = {2017}, } @inproceedings{11829, abstract = {In recent years it has become popular to study dynamic problems in a sensitivity setting: Instead of allowing for an arbitrary sequence of updates, the sensitivity model only allows to apply batch updates of small size to the original input data. The sensitivity model is particularly appealing since recent strong conditional lower bounds ruled out fast algorithms for many dynamic problems, such as shortest paths, reachability, or subgraph connectivity. In this paper we prove conditional lower bounds for these and additional problems in a sensitivity setting. For example, we show that under the Boolean Matrix Multiplication (BMM) conjecture combinatorial algorithms cannot compute the (4/3-\varepsilon)-approximate diameter of an undirected unweighted dense graph with truly subcubic preprocessing time and truly subquadratic update/query time. This result is surprising since in the static setting it is not clear whether a reduction from BMM to diameter is possible. We further show under the BMM conjecture that many problems, such as reachability or approximate shortest paths, cannot be solved faster than by recomputation from scratch even after only one or two edge insertions. We extend our reduction from BMM to Diameter to give a reduction from All Pairs Shortest Paths to Diameter under one deletion in weighted graphs. This is intriguing, as in the static setting it is a big open problem whether Diameter is as hard as APSP. We further get a nearly tight lower bound for shortest paths after two edge deletions based on the APSP conjecture. We give more lower bounds under the Strong Exponential Time Hypothesis. Many of our lower bounds also hold for static oracle data structures where no sensitivity is required. Finally, we give the first algorithm for the (1+\varepsilon)-approximate radius, diameter, and eccentricity problems in directed or undirected unweighted graphs in case of single edges failures. The algorithm has a truly subcubic running time for graphs with a truly subquadratic number of edges; it is tight w.r.t. the conditional lower bounds we obtain.}, author = {Henzinger, Monika H and Lincoln, Andrea and Neumann, Stefan and Vassilevska Williams, Virginia}, booktitle = {8th Innovations in Theoretical Computer Science Conference}, isbn = {9783959770293}, issn = {1868-8969}, location = {Berkley, CA, United States}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Conditional hardness for sensitivity problems}}, doi = {10.4230/LIPICS.ITCS.2017.26}, volume = {67}, year = {2017}, } @inproceedings{11833, abstract = {We introduce a new algorithmic framework for designing dynamic graph algorithms in minor-free graphs, by exploiting the structure of such graphs and a tool called vertex sparsification, which is a way to compress large graphs into small ones that well preserve relevant properties among a subset of vertices and has previously mainly been used in the design of approximation algorithms. Using this framework, we obtain a Monte Carlo randomized fully dynamic algorithm for (1 + epsilon)-approximating the energy of electrical flows in n-vertex planar graphs with tilde{O}(r epsilon^{-2}) worst-case update time and tilde{O}((r + n / sqrt{r}) epsilon^{-2}) worst-case query time, for any r larger than some constant. For r=n^{2/3}, this gives tilde{O}(n^{2/3} epsilon^{-2}) update time and tilde{O}(n^{2/3} epsilon^{-2}) query time. We also extend this algorithm to work for minor-free graphs with similar approximation and running time guarantees. Furthermore, we illustrate our framework on the all-pairs max flow and shortest path problems by giving corresponding dynamic algorithms in minor-free graphs with both sublinear update and query times. To the best of our knowledge, our results are the first to systematically establish such a connection between dynamic graph algorithms and vertex sparsification. We also present both upper bound and lower bound for maintaining the energy of electrical flows in the incremental subgraph model, where updates consist of only vertex activations, which might be of independent interest.}, author = {Goranci, Gramoz and Henzinger, Monika H and Peng, Pan}, booktitle = {25th Annual European Symposium on Algorithms}, isbn = {978-3-95977-049-1}, issn = {1868-8969}, location = {Vienna, Austria}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{The power of vertex sparsifiers in dynamic graph algorithms}}, doi = {10.4230/LIPICS.ESA.2017.45}, volume = {87}, year = {2017}, } @inproceedings{11832, abstract = {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.}, author = {Henzinger, Monika H and Leniowski, Dariusz and Mathieu, Claire}, booktitle = {25th Annual European Symposium on Algorithms}, isbn = {978-3-95977-049-1}, issn = {1868-8969}, location = {Vienna, Austria}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Dynamic clustering to minimize the sum of radii}}, doi = {10.4230/LIPICS.ESA.2017.48}, volume = {87}, year = {2017}, } @inproceedings{11874, abstract = {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 ∊.}, author = {Bhattacharya, Sayan and Henzinger, Monika H and Nanongkai, Danupon}, booktitle = {28th Annual ACM-SIAM Symposium on Discrete Algorithms}, location = {Barcelona, Spain}, pages = {470 -- 489}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time}}, doi = {10.1137/1.9781611974782.30}, year = {2017}, } @inproceedings{11873, abstract = {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.}, author = {Henzinger, Monika H and Rao, Satish and Wang, Di}, booktitle = {28th Annual ACM-SIAM Symposium on Discrete Algorithms}, location = {Barcelona, Spain}, pages = {1919--1938}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Local flow partitioning for faster edge connectivity}}, doi = {10.1137/1.9781611974782.125}, year = {2017}, } @inproceedings{11831, abstract = {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.}, author = {Goranci, Gramoz and Henzinger, Monika H and Peng, Pan}, booktitle = {25th Annual European Symposium on Algorithms}, isbn = {978-3-95977-049-1}, issn = {1868-8969}, location = {Vienna, Austria}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Improved guarantees for vertex sparsification in planar graphs}}, doi = {10.4230/LIPICS.ESA.2017.44}, volume = {87}, year = {2017}, } @article{11903, abstract = {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.}, author = {Bhattacharya, Sayan and Dvořák, Wolfgang and Henzinger, Monika H and Starnberger, Martin}, issn = {1433-0490}, journal = {Theory of Computing Systems}, number = {4}, pages = {948--986}, publisher = {Springer Nature}, title = {{Welfare maximization with friends-of-friends network externalities}}, doi = {10.1007/s00224-017-9759-8}, volume = {61}, year = {2017}, } @article{1191, abstract = {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.}, author = {Kollár, Richard and Novak, Sebastian}, journal = {Bulletin of Mathematical Biology}, number = {3}, pages = {525--559}, publisher = {Springer}, title = {{Existence of traveling waves for the generalized F–KPP equation}}, doi = {10.1007/s11538-016-0244-3}, volume = {79}, year = {2017}, } @article{11961, abstract = {Flow chemistry involves the use of channels or tubing to conduct a reaction in a continuous stream rather than in a flask. Flow equipment provides chemists with unique control over reaction parameters enhancing reactivity or in some cases enabling new reactions. This relatively young technology has received a remarkable amount of attention in the past decade with many reports on what can be done in flow. Until recently, however, the question, “Should we do this in flow?” has merely been an afterthought. This review introduces readers to the basic principles and fundamentals of flow chemistry and critically discusses recent flow chemistry accounts.}, author = {Plutschack, Matthew B. and Pieber, Bartholomäus and Gilmore, Kerry and Seeberger, Peter H.}, issn = {1520-6890}, journal = {Chemical Reviews}, number = {18}, pages = {11796--11893}, publisher = {American Chemical Society}, title = {{The Hitchhiker’s Guide to flow chemistry}}, doi = {10.1021/acs.chemrev.7b00183}, volume = {117}, year = {2017}, } @article{11976, abstract = {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.}, author = {Pieber, Bartholomäus and Gilmore, Kerry and Seeberger, Peter H.}, issn = {2063-0212}, journal = {Journal of Flow Chemistry}, number = {3-4}, pages = {129--136}, publisher = {AKJournals}, title = {{Integrated flow processing - challenges in continuous multistep synthesis}}, doi = {10.1556/1846.2017.00016}, volume = {7}, year = {2017}, } @article{1211, abstract = {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.}, author = {Budanur, Nazmi B and Cvitanović, Predrag}, journal = {Journal of Statistical Physics}, number = {3-4}, pages = {636--655}, publisher = {Springer}, title = {{Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system}}, doi = {10.1007/s10955-016-1672-z}, volume = {167}, year = {2017}, } @article{123, abstract = {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.}, author = {Waitukaitis, Scott R and Zuiderwijk, Antal and Souslov, Anton and Coulais, Corentin and Van Hecke, Martin}, journal = {Nature Physics}, number = {11}, pages = {1095 -- 1099}, publisher = {Nature Publishing Group}, title = {{Coupling the Leidenfrost effect and elastic deformations to power sustained bouncing}}, doi = {10.1038/nphys4194}, volume = {13}, year = {2017}, } @inproceedings{12571, abstract = {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.}, author = {Bhattacharya, Sayan and Chakrabarty, Deeparnab and Henzinger, Monika H}, booktitle = {19th International Conference on Integer Programming and Combinatorial Optimization}, isbn = {9783319592497}, issn = {0302-9743}, location = {Waterloo, ON, Canada}, pages = {86--98}, publisher = {Springer Nature}, title = {{Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time}}, doi = {10.1007/978-3-319-59250-3_8}, volume = {10328}, year = {2017}, } @article{1113, abstract = {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.}, author = {Fulek, Radoslav and Pelsmajer, Michael and Schaefer, Marcus}, journal = {Journal of Graph Algorithms and Applications}, number = {1}, pages = {135 -- 154}, publisher = {Brown University}, title = {{Hanani-Tutte for radial planarity}}, doi = {10.7155/jgaa.00408}, volume = {21}, year = {2017}, } @article{169, abstract = {We show that a twisted variant of Linnik’s conjecture on sums of Kloosterman sums leads to an optimal covering exponent for S3.}, author = {Browning, Timothy D and Kumaraswamy, Vinay and Steiner, Rapael}, journal = {International Mathematics Research Notices}, publisher = {Oxford University Press}, title = {{Twisted Linnik implies optimal covering exponent for S3}}, doi = {10.1093/imrn/rnx116}, year = {2017}, } @article{172, abstract = {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.}, author = {Browning, Timothy D and Schindler, Damaris}, journal = {International Mathematics Research Notices}, publisher = {Oxford University Press}, title = {{Strong approximation and a conjecture of Harpaz and Wittenberg}}, doi = {10.1093/imrn/rnx252}, year = {2017}, } @article{391, abstract = {Three-dimensional topological insulators are bulk insulators with Z 2 topological electronic order that gives rise to conducting light-like surface states. These surface electrons are exceptionally resistant to localization by non-magnetic disorder, and have been adopted as the basis for a wide range of proposals to achieve new quasiparticle species and device functionality. Recent studies have yielded a surprise by showing that in spite of resisting localization, topological insulator surface electrons can be reshaped by defects into distinctive resonance states. Here we use numerical simulations and scanning tunnelling microscopy data to show that these resonance states have significance well beyond the localized regime usually associated with impurity bands. At native densities in the model Bi2X3 (X=Bi, Te) compounds, defect resonance states are predicted to generate a new quantum basis for an emergent electron gas that supports diffusive electrical transport. }, author = {Xu, Yishuai and Chiu, Janet and Miao, Lin and He, Haowei and Alpichshev, Zhanybek and Kapitulnik, Aharon and Biswas, Rudro and Wray, Lewis}, journal = {Nature Communications}, publisher = {Nature Publishing Group}, title = {{Disorder enabled band structure engineering of a topological insulator surface}}, doi = {10.1038/ncomms14081}, volume = {8}, year = {2017}, } @article{393, abstract = {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. }, author = {Alpichshev, Zhanybek and Sie, Edbert and Mahmood, Fahad and Cao, Gang and Gedik, Nuh}, journal = {Physical Review B}, number = {23}, publisher = {American Physical Society}, title = {{Origin of the exciton mass in the frustrated Mott insulator Na2IrO3}}, doi = {10.1103/PhysRevB.96.235141}, volume = {96}, year = {2017}, }