TY - JOUR AB - During metazoan development, immune surveillance and cancer dissemination, cells migrate in complex three-dimensional microenvironments1,2,3. These spaces are crowded by cells and extracellular matrix, generating mazes with differently sized gaps that are typically smaller than the diameter of the migrating cell4,5. Most mesenchymal and epithelial cells and some—but not all—cancer cells actively generate their migratory path using pericellular tissue proteolysis6. By contrast, amoeboid cells such as leukocytes use non-destructive strategies of locomotion7, raising the question how these extremely fast cells navigate through dense tissues. Here we reveal that leukocytes sample their immediate vicinity for large pore sizes, and are thereby able to choose the path of least resistance. This allows them to circumnavigate local obstacles while effectively following global directional cues such as chemotactic gradients. Pore-size discrimination is facilitated by frontward positioning of the nucleus, which enables the cells to use their bulkiest compartment as a mechanical gauge. Once the nucleus and the closely associated microtubule organizing centre pass the largest pore, cytoplasmic protrusions still lingering in smaller pores are retracted. These retractions are coordinated by dynamic microtubules; when microtubules are disrupted, migrating cells lose coherence and frequently fragment into migratory cytoplasmic pieces. As nuclear positioning in front of the microtubule organizing centre is a typical feature of amoeboid migration, our findings link the fundamental organization of cellular polarity to the strategy of locomotion. AU - Renkawitz, Jörg AU - Kopf, Aglaja AU - Stopp, Julian A AU - de Vries, Ingrid AU - Driscoll, Meghan K. AU - Merrin, Jack AU - Hauschild, Robert AU - Welf, Erik S. AU - Danuser, Gaudenz AU - Fiolka, Reto AU - Sixt, Michael K ID - 6328 JF - Nature TI - Nuclear positioning facilitates amoeboid migration along the path of least resistance VL - 568 ER - TY - JOUR AU - Contreras, Ximena AU - Hippenmeyer, Simon ID - 6830 IS - 5 JF - Neuron SN - 08966273 TI - Memo1 tiles the radial glial cell grid VL - 103 ER - TY - JOUR AB - Cortical microtubule arrays in elongating epidermal cells in both the root and stem of plants have the propensity of dynamic reorientations that are correlated with the activation or inhibition of growth. Factors regulating plant growth, among them the hormone auxin, have been recognized as regulators of microtubule array orientations. Some previous work in the field has aimed at elucidating the causal relationship between cell growth, the signaling of auxin or other growth-regulating factors, and microtubule array reorientations, with various conclusions. Here, we revisit this problem of causality with a comprehensive set of experiments in Arabidopsis thaliana, using the now available pharmacological and genetic tools. We use isolated, auxin-depleted hypocotyls, an experimental system allowing for full control of both growth and auxin signaling. We demonstrate that reorientation of microtubules is not directly triggered by an auxin signal during growth activation. Instead, reorientation is triggered by the activation of the growth process itself and is auxin-independent in its nature. We discuss these findings in the context of previous relevant work, including that on the mechanical regulation of microtubule array orientation. AU - Adamowski, Maciek AU - Li, Lanxin AU - Friml, Jiří ID - 6627 IS - 13 JF - International Journal of Molecular Sciences TI - Reorientation of cortical microtubule arrays in the hypocotyl of arabidopsis thaliana is induced by the cell growth process and independent of auxin signaling VL - 20 ER - TY - JOUR AB - We propose a novel generic shape optimization method for CAD models based on the eXtended Finite Element Method (XFEM). Our method works directly on the intersection between the model and a regular simulation grid, without the need to mesh or remesh, thus removing a bottleneck of classical shape optimization strategies. This is made possible by a novel hierarchical integration scheme that accurately integrates finite element quantities with sub-element precision. For optimization, we efficiently compute analytical shape derivatives of the entire framework, from model intersection to integration rule generation and XFEM simulation. Moreover, we describe a differentiable projection of shape parameters onto a constraint manifold spanned by user-specified shape preservation, consistency, and manufacturability constraints. We demonstrate the utility of our approach by optimizing mass distribution, strength-to-weight ratio, and inverse elastic shape design objectives directly on parameterized 3D CAD models. AU - Hafner, Christian AU - Schumacher, Christian AU - Knoop, Espen AU - Auzinger, Thomas AU - Bickel, Bernd AU - Bächer, Moritz ID - 7117 IS - 6 JF - ACM Transactions on Graphics SN - 0730-0301 TI - X-CAD: Optimizing CAD Models with Extended Finite Elements VL - 38 ER - TY - JOUR AB - Suspended particles can alter the properties of fluids and in particular also affect the transition fromlaminar to turbulent flow. An earlier study [Mataset al.,Phys. Rev. Lett.90, 014501 (2003)] reported howthe subcritical (i.e., hysteretic) transition to turbulent puffs is affected by the addition of particles. Here weshow that in addition to this known transition, with increasing concentration a supercritical (i.e.,continuous) transition to a globally fluctuating state is found. At the same time the Newtonian-typetransition to puffs is delayed to larger Reynolds numbers. At even higher concentration only the globallyfluctuating state is found. The dynamics of particle laden flows are hence determined by two competinginstabilities that give rise to three flow regimes: Newtonian-type turbulence at low, a particle inducedglobally fluctuating state at high, and a coexistence state at intermediate concentrations. AU - Agrawal, Nishchal AU - Choueiri, George H AU - Hof, Björn ID - 6189 IS - 11 JF - Physical Review Letters SN - 00319007 TI - Transition to turbulence in particle laden flows VL - 122 ER - TY - THES AB - Decades of studies have revealed the mechanisms of gene regulation in molecular detail. We make use of such well-described regulatory systems to explore how the molecular mechanisms of protein-protein and protein-DNA interactions shape the dynamics and evolution of gene regulation. i) We uncover how the biophysics of protein-DNA binding determines the potential of regulatory networks to evolve and adapt, which can be captured using a simple mathematical model. ii) The evolution of regulatory connections can lead to a significant amount of crosstalk between binding proteins. We explore the effect of crosstalk on gene expression from a target promoter, which seems to be modulated through binding competition at non-specific DNA sites. iii) We investigate how the very same biophysical characteristics as in i) can generate significant fitness costs for cells through global crosstalk, meaning non-specific DNA binding across the genomic background. iv) Binding competition between proteins at a target promoter is a prevailing regulatory feature due to the prevalence of co-regulation at bacterial promoters. However, the dynamics of these systems are not always straightforward to determine even if the molecular mechanisms of regulation are known. A detailed model of the biophysical interactions reveals that interference between the regulatory proteins can constitute a new, generic form of system memory that records the history of the input signals at the promoter. We demonstrate how the biophysics of protein-DNA binding can be harnessed to investigate the principles that shape and ultimately limit cellular gene regulation. These results provide a basis for studies of higher-level functionality, which arises from the underlying regulation. AU - Igler, Claudia ID - 6371 KW - gene regulation KW - biophysics KW - transcription factor binding KW - bacteria SN - 2663-337X TI - On the nature of gene regulatory design - The biophysics of transcription factor binding shapes gene regulation ER - TY - JOUR AB - In this paper, we evaluate clock signals generated in ring oscillators and self-timed rings and the way their jitter can be transformed into random numbers. We show that counting the periods of the jittery clock signal produces random numbers of significantly better quality than the methods in which the jittery signal is simply sampled (the case in almost all current methods). Moreover, we use the counter values to characterize and continuously monitor the source of randomness. However, instead of using the widely used statistical variance, we propose to use Allan variance to do so. There are two main advantages: Allan variance is insensitive to low frequency noises such as flicker noise that are known to be autocorrelated and significantly less circuitry is required for its computation than that used to compute commonly used variance. We also show that it is essential to use a differential principle of randomness extraction from the jitter based on the use of two identical oscillators to avoid autocorrelations originating from external and internal global jitter sources and that this fact is valid for both kinds of rings. Last but not least, we propose a method of statistical testing based on high order Markov model to show the reduced dependencies when the proposed randomness extraction is applied. AU - Allini, Elie Noumon AU - Skórski, Maciej AU - Petura, Oto AU - Bernard, Florent AU - Laban, Marek AU - Fischer, Viktor ID - 10286 IS - 3 JF - IACR Transactions on Cryptographic Hardware and Embedded Systems TI - Evaluation and monitoring of free running oscillators serving as source of randomness VL - 2018 ER - TY - JOUR AB - Biological membranes typically contain a large number of different components dispersed in small concentrations in the main membrane phase, including proteins, sugars, and lipids of varying geometrical properties. Most of these components do not bind the cargo. Here, we show that such “inert” components can be crucial for the precise control of cross-membrane trafficking. Using a statistical mechanics model and molecular dynamics simulations, we demonstrate that the presence of inert membrane components of small isotropic curvatures dramatically influences cargo endocytosis, even if the total spontaneous curvature of such a membrane remains unchanged. Curved lipids, such as cholesterol, as well as asymmetrically included proteins and tethered sugars can, therefore, actively participate in the control of the membrane trafficking of nanoscopic cargo. We find that even a low-level expression of curved inert membrane components can determine the membrane selectivity toward the cargo size and can be used to selectively target membranes of certain compositions. Our results suggest a robust and general method of controlling cargo trafficking by adjusting the membrane composition without needing to alter the concentration of receptors or the average membrane curvature. This study indicates that cells can prepare for any trafficking event by incorporating curved inert components in either of the membrane leaflets. AU - Curk, Tine AU - Wirnsberger, Peter AU - Dobnikar, Jure AU - Frenkel, Daan AU - Šarić, Anđela ID - 10359 IS - 9 JF - Nano Letters KW - mechanical engineering KW - condensed matter physics SN - 1530-6984 TI - Controlling cargo trafficking in multicomponent membranes VL - 18 ER - TY - JOUR AB - Probing reaction mechanisms of supramolecular processes in soft and biological matter, such as protein aggregation, is inherently challenging. This is because these processes involve multiple molecular mechanisms that are associated with the rearrangement of large numbers of weak bonds, resulting in complex free energy landscapes with many kinetic barriers. Reaction rate measurements at different temperatures can offer unprecedented insights into the underlying molecular mechanisms. However, to be able to interpret such measurements, a key challenge is to establish which properties of the complex free energy landscapes are probed by the reaction rate. Here, we present a reaction rate theory for supramolecular kinetics based on Kramers theory of diffusive reactions over multiple kinetic barriers. We find that reaction rates for protein aggregation are of the Arrhenius–Eyring type and that the associated activation energies probe only one relevant barrier along the respective free energy landscapes. We apply this advancement to interpret, in experiments and in coarse-grained computer simulations, reaction rates of amyloid aggregation in terms of molecular mechanisms and associated thermodynamic signatures. These results suggest a practical extension of the concept of rate-determining steps for complex supramolecular processes and establish a general platform for probing the underlying energy landscape using kinetic measurements. AU - Michaels, Thomas C. T. AU - Liu, Lucie X. AU - Curk, Samo AU - Bolhuis, Peter G. AU - Šarić, Anđela AU - Knowles, Tuomas P. J. ID - 10358 IS - 21-22 JF - Molecular Physics KW - physical chemistry SN - 0026-8976 TI - Reaction rate theory for supramolecular kinetics: application to protein aggregation VL - 116 ER - TY - JOUR AB - Owing to their wide tunability, multiple internal degrees of freedom, and low disorder, graphene heterostructures are emerging as a promising experimental platform for fractional quantum Hall (FQH) studies. Here, we report FQH thermal activation gap measurements in dual graphite-gated monolayer graphene devices fabricated in an edgeless Corbino geometry. In devices with substrate-induced sublattice splitting, we find a tunable crossover between single- and multicomponent FQH states in the zero energy Landau level. Activation gaps in the single-component regime show excellent agreement with numerical calculations using a single broadening parameter Γ≈7.2K. In the first excited Landau level, in contrast, FQH gaps are strongly influenced by Landau level mixing, and we observe an unexpected valley-ordered state at integer filling ν=−4. AU - Polshyn, Hryhoriy AU - Zhou, H. AU - Spanton, E. M. AU - Taniguchi, T. AU - Watanabe, K. AU - Young, A. F. ID - 10626 IS - 22 JF - Physical Review Letters KW - general physics and astronomy SN - 0031-9007 TI - Quantitative transport measurements of fractional quantum Hall energy gaps in edgeless graphene devices VL - 121 ER - TY - JOUR AB - We present a scanning probe technique for measuring the dynamics of individual fluxoid transitions in multiply connected superconducting structures. In these measurements, a small magnetic particle attached to the tip of a silicon cantilever is scanned over a micron-size superconducting ring fabricated from a thin aluminum film. We find that near the superconducting transition temperature of the aluminum, the dissipation and frequency of the cantilever changes significantly at particular locations where the tip-induced magnetic flux penetrating the ring causes the two lowest-energy fluxoid states to become nearly degenerate. In this regime, we show that changes in the cantilever frequency and dissipation are well-described by a stochastic resonance (SR) process, wherein small oscillations of the cantilever in the presence of thermally activated phase slips (TAPS) in the ring give rise to a dynamical force that modifies the mechanical properties of the cantilever. Using the SR model, we calculate the average fluctuation rate of the TAPS as a function of temperature over a 32-dB range in frequency, and we compare it to the Langer-Ambegaokar-McCumber-Halperin theory for TAPS in one-dimensional superconducting structures. AU - Polshyn, Hryhoriy AU - Naibert, Tyler R. AU - Budakian, Raffi ID - 10627 IS - 18 JF - Physical Review B SN - 2469-9950 TI - Imaging phase slip dynamics in micron-size superconducting rings VL - 97 ER - TY - CONF AB - Solving parity games, which are equivalent to modal μ-calculus model checking, is a central algorithmic problem in formal methods, with applications in reactive synthesis, program repair, verification of branching-time properties, etc. Besides the standard compu- tation model with the explicit representation of games, another important theoretical model of computation is that of set-based symbolic algorithms. Set-based symbolic algorithms use basic set operations and one-step predecessor operations on the implicit description of games, rather than the explicit representation. The significance of symbolic algorithms is that they provide scalable algorithms for large finite-state systems, as well as for infinite-state systems with finite quotient. Consider parity games on graphs with n vertices and parity conditions with d priorities. While there is a rich literature of explicit algorithms for parity games, the main results for set-based symbolic algorithms are as follows: (a) the basic algorithm that requires O(nd) symbolic operations and O(d) symbolic space; and (b) an improved algorithm that requires O(nd/3+1) symbolic operations and O(n) symbolic space. In this work, our contributions are as follows: (1) We present a black-box set-based symbolic algorithm based on the explicit progress measure algorithm. Two important consequences of our algorithm are as follows: (a) a set-based symbolic algorithm for parity games that requires quasi-polynomially many symbolic operations and O(n) symbolic space; and (b) any future improvement in progress measure based explicit algorithms immediately imply an efficiency improvement in our set-based symbolic algorithm for parity games. (2) We present a set-based symbolic algorithm that requires quasi-polynomially many symbolic operations and O(d · log n) symbolic space. Moreover, for the important special case of d ≤ log n, our algorithm requires only polynomially many symbolic operations and poly-logarithmic symbolic space. AU - Chatterjee, Krishnendu AU - Dvořák, Wolfgang AU - Henzinger, Monika H AU - Svozil, Alexander ID - 10883 SN - 2398-7340 T2 - 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning TI - Quasipolynomial set-based symbolic algorithms for parity games VL - 57 ER - TY - JOUR AB - A graphical model encodes conditional independence relations via the Markov properties. For an undirected graph these conditional independence relations can be represented by a simple polytope known as the graph associahedron, which can be constructed as a Minkowski sum of standard simplices. We show that there is an analogous polytope for conditional independence relations coming from a regular Gaussian model, and it can be defined using multiinformation or relative entropy. For directed acyclic graphical models we give a construction of this polytope as a Minkowski sum of matroid polytopes. Finally, we apply this geometric insight to construct a new ordering-based search algorithm for causal inference via directed acyclic graphical models. AU - Mohammadi, Fatemeh AU - Uhler, Caroline AU - Wang, Charles AU - Yu, Josephine ID - 1092 IS - 1 JF - SIAM Journal on Discrete Mathematics TI - Generalized permutohedra from probabilistic graphical models VL - 32 ER - TY - CONF AB - We report on a novel strategy to derive mean-field limits of quantum mechanical systems in which a large number of particles weakly couple to a second-quantized radiation field. The technique combines the method of counting and the coherent state approach to study the growth of the correlations among the particles and in the radiation field. As an instructional example, we derive the Schrödinger–Klein–Gordon system of equations from the Nelson model with ultraviolet cutoff and possibly massless scalar field. In particular, we prove the convergence of the reduced density matrices (of the nonrelativistic particles and the field bosons) associated with the exact time evolution to the projectors onto the solutions of the Schrödinger–Klein–Gordon equations in trace norm. Furthermore, we derive explicit bounds on the rate of convergence of the one-particle reduced density matrix of the nonrelativistic particles in Sobolev norm. AU - Leopold, Nikolai K AU - Pickl, Peter ID - 11 TI - Mean-field limits of particles in interaction with quantised radiation fields VL - 270 ER - TY - JOUR AB - The total number of nuclear pore complexes (NPCs) per nucleus varies greatly between different cell types and is known to change during cell differentiation and cell transformation. However, the underlying mechanisms that control how many nuclear transport channels are assembled into a given nuclear envelope remain unclear. Here, we report that depletion of the NPC basket protein Tpr, but not Nup153, dramatically increases the total NPC number in various cell types. This negative regulation of Tpr occurs via a phosphorylation cascade of extracellular signal-regulated kinase (ERK), the central kinase of the mitogen-activated protein kinase (MAPK) pathway. Tpr serves as a scaffold for ERK to phosphorylate the nucleoporin (Nup) Nup153, which is critical for early stages of NPC biogenesis. Our results reveal a critical role of the Nup Tpr in coordinating signal transduction pathways during cell proliferation and the dynamic organization of the nucleus. AU - McCloskey, Asako AU - Ibarra, Arkaitz AU - HETZER, Martin W ID - 11063 IS - 19-20 JF - Genes & Development KW - Developmental Biology KW - Genetics SN - 0890-9369 TI - Tpr regulates the total number of nuclear pore complexes per cell nucleus VL - 32 ER - TY - JOUR AB - Biomarkers of aging can be used to assess the health of individuals and to study aging and age-related diseases. We generate a large dataset of genome-wide RNA-seq profiles of human dermal fibroblasts from 133 people aged 1 to 94 years old to test whether signatures of aging are encoded within the transcriptome. We develop an ensemble machine learning method that predicts age to a median error of 4 years, outperforming previous methods used to predict age. The ensemble was further validated by testing it on ten progeria patients, and our method is the only one that predicts accelerated aging in these patients. AU - Fleischer, Jason G. AU - Schulte, Roberta AU - Tsai, Hsiao H. AU - Tyagi, Swati AU - Ibarra, Arkaitz AU - Shokhirev, Maxim N. AU - Huang, Ling AU - HETZER, Martin W AU - Navlakha, Saket ID - 11064 JF - Genome Biology SN - 1474-760X TI - Predicting age from the transcriptome of human dermal fibroblasts VL - 19 ER - TY - JOUR AB - Distant luminous Lyman-α emitters (LAEs) are excellent targets for spectroscopic observations of galaxies in the epoch of reionisation (EoR). We present deep high-resolution (R = 5000) VLT/X-shooter observations, along with an extensive collection of photometric data of COLA1, a proposed double peaked LAE at z = 6.6. We rule out the possibility that COLA1’s emission line is an [OII] doublet at z = 1.475 on the basis of i) the asymmetric red line-profile and flux ratio of the peaks (blue/red=0.31 ± 0.03) and ii) an unphysical [OII]/Hα ratio ([OII]/Hα >  22). We show that COLA1’s observed B-band flux is explained by a faint extended foreground LAE, for which we detect Lyα and [OIII] at z = 2.142. We thus conclude that COLA1 is a real double-peaked LAE at z = 6.593, the first discovered at z >  6. COLA1 is UV luminous (M1500 = −21.6 ± 0.3), has a high equivalent width (EW0,Lyα = 120−40+50 Å) and very compact Lyα emission (r50,Lyα = 0.33−0.04+0.07 kpc). Relatively weak inferred Hβ+[OIII] line-emission from Spitzer/IRAC indicates an extremely low metallicity of Z <  1/20 Z⊙ or reduced strength of nebular lines due to high escape of ionising photons. The small Lyα peak separation of 220 ± 20 km s−1 implies a low HI column density and an ionising photon escape fraction of ≈15 − 30%, providing the first direct evidence that such galaxies contribute actively to the reionisation of the Universe at z >  6. Based on simple estimates, we find that COLA1 could have provided just enough photons to reionise its own ≈0.3 pMpc (2.3 cMpc) bubble, allowing the blue Lyα line to be observed. However, we also discuss alternative scenarios explaining the detected double peaked nature of COLA1. Our results show that future high-resolution observations of statistical samples of double peaked LAEs at z >  5 are a promising probe of the occurrence of ionised regions around galaxies in the EoR. AU - Matthee, Jorryt J AU - Sobral, David AU - Gronke, Max AU - Paulino-Afonso, Ana AU - Stefanon, Mauro AU - Röttgering, Huub ID - 11508 JF - Astronomy & Astrophysics KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: high-redshift / galaxies: formation / dark ages / reionization / first stars / techniques: spectroscopic / intergalactic medium SN - 0004-6361 TI - Confirmation of double peaked Lyα emission at z = 6.593: Witnessing a galaxy directly contributing to the reionisation of the universe VL - 619 ER - TY - JOUR AB - Deep narrow-band surveys have revealed a large population of faint Ly α emitters (LAEs) in the distant Universe, but relatively little is known about the most luminous sources (⁠LLyα≳1042.7 erg s−1; LLyα≳L∗Lyα⁠). Here we present the spectroscopic follow-up of 21 luminous LAEs at z ∼ 2–3 found with panoramic narrow-band surveys over five independent extragalactic fields (≈4 × 106 Mpc3 surveyed at z ∼ 2.2 and z ∼ 3.1). We use WHT/ISIS, Keck/DEIMOS, and VLT/X-SHOOTER to study these sources using high ionization UV lines. Luminous LAEs at z ∼ 2–3 have blue UV slopes (⁠β=−2.0+0.3−0.1⁠) and high Ly α escape fractions (⁠50+20−15 per cent) and span five orders of magnitude in UV luminosity (MUV ≈ −19 to −24). Many (70 per cent) show at least one high ionization rest-frame UV line such as C IV, N V, C III], He II or O III], typically blue-shifted by ≈100–200 km s−1 relative to Ly α. Their Ly α profiles reveal a wide variety of shapes, including significant blue-shifted components and widths from 200 to 4000 km s−1. Overall, 60 ± 11  per cent appear to be active galactic nucleus (AGN) dominated, and at LLyα > 1043.3 erg s−1 and/or MUV < −21.5 virtually all LAEs are AGNs with high ionization parameters (log U = 0.6 ± 0.5) and with metallicities of ≈0.5 − 1 Z⊙. Those lacking signatures of AGNs (40 ± 11  per cent) have lower ionization parameters (⁠logU=−3.0+1.6−0.9 and log ξion = 25.4 ± 0.2) and are apparently metal-poor sources likely powered by young, dust-poor ‘maximal’ starbursts. Our results show that luminous LAEs at z ∼ 2–3 are a diverse population and that 2×L∗Lyα and 2×M∗UV mark a sharp transition in the nature of LAEs, from star formation dominated to AGN dominated. AU - Sobral, David AU - Matthee, Jorryt J AU - Darvish, Behnam AU - Smail, Ian AU - Best, Philip N AU - Alegre, Lara AU - Röttgering, Huub AU - Mobasher, Bahram AU - Paulino-Afonso, Ana AU - Stroe, Andra AU - Oteo, Iván ID - 11557 IS - 2 JF - Monthly Notices of the Royal Astronomical Society KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: active KW - galaxies: evolution KW - galaxies: high-redshift KW - galaxies: ISM KW - galaxies: starburst KW - cosmology: observations SN - 0035-8711 TI - The nature of luminous Ly α emitters at z ∼ 2–3: Maximal dust-poor starbursts and highly ionizing AGN VL - 477 ER - TY - JOUR AB - We present and explore deep narrow- and medium-band data obtained with the Subaru and the Isaac Newton Telescopes in the ∼2 deg2 COSMOS field. We use these data as an extremely wide, low-resolution (R ∼ 20–80) Integral Field Unit survey to slice through the COSMOS field and obtain a large sample of ∼4000 Ly α emitters (LAEs) from z ∼ 2 to 6 in 16 redshift slices (SC4K). We present new Ly α luminosity functions (LFs) covering a comoving volume of ∼108 Mpc3. SC4K extensively complements ultradeep surveys, jointly covering over 4 dex in Ly α luminosity and revealing a global (2.5 < z < 6) synergy LF with α=−1.93+0.12−0.12⁠, log10Φ∗Lyα=−3.45+0.22−0.29 Mpc−3, and log10L∗Lyα=42.93+0.15−0.11 erg s−1. The Schechter component of the Ly α LF reveals a factor ∼5 rise in L∗Lyα and a ∼7 × decline in Φ∗Lyα from z ∼ 2 to 6. The data reveal an extra power-law (or Schechter) component above LLy α ≈ 1043.3 erg s−1 at z ∼ 2.2–3.5 and we show that it is partially driven by X-ray and radio active galactic nucleus (AGN), as their Ly α LF resembles the excess. The power-law component vanishes and/or is below our detection limits above z > 3.5, likely linked with the evolution of the AGN population. The Ly α luminosity density rises by a factor ∼2 from z ∼ 2 to 3 but is then found to be roughly constant (⁠1.1+0.2−0.2×1040 erg s−1 Mpc−3) to z ∼ 6, despite the ∼0.7 dex drop in ultraviolet (UV) luminosity density. The Ly α/UV luminosity density ratio rises from 4 ± 1 per cent to 30 ± 6 per cent from z ∼ 2.2 to 6. Our results imply a rise of a factor of ≈2 in the global ionization efficiency (ξion) and a factor ≈4 ± 1 in the Ly α escape fraction from z ∼ 2 to 6, hinting for evolution in both the typical burstiness/stellar populations and even more so in the typical interstellar medium conditions allowing Ly α photons to escape. AU - Sobral, David AU - Santos, Sérgio AU - Matthee, Jorryt J AU - Paulino-Afonso, Ana AU - Ribeiro, Bruno AU - Calhau, João AU - Khostovan, Ali A ID - 11558 IS - 4 JF - Monthly Notices of the Royal Astronomical Society KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: evolution KW - galaxies: formation KW - galaxies: high-redshift KW - galaxies: luminosity function KW - mass function KW - galaxies: statistics SN - 0035-8711 TI - Slicing COSMOS with SC4K: The evolution of typical Ly α emitters and the Ly α escape fraction from z ∼ 2 to 6 VL - 476 ER - TY - JOUR AB - We investigate the morphology of the [C II] emission in a sample of ‘normal’ star-forming galaxies at 5 < z < 7.2 in relation to their UV (rest-frame) counterpart. We use new Atacama Large Millimetre/submillimetre Array (ALMA) observations of galaxies at z ∼ 6–7, as well as a careful re-analysis of archival ALMA data. In total 29 galaxies were analysed, 21 of which are detected in [C II]. For several of the latter the [C II] emission breaks into multiple components. Only a fraction of these [C II] components, if any, is associated with the primary UV systems, while the bulk of the [C II] emission is associated either with fainter UV components, or not associated with any UV counterpart at the current limits. By taking into account the presence of all these components, we find that the L[CII]–SFR (star formation rate) relation at early epochs is fully consistent with the local relation, but it has a dispersion of 0.48 ± 0.07 dex, which is about two times larger than observed locally. We also find that the deviation from the local L[CII]–SFR relation has a weak anticorrelation with the EW(Ly α). The morphological analysis also reveals that [C II] emission is generally much more extended than the UV emission. As a consequence, these primordial galaxies are characterized by a [C II] surface brightness generally much lower than expected from the local Σ[CII]−ΣSFR relation. These properties are likely a consequence of a combination of different effects, namely gas metallicity, [C II] emission from obscured star-forming regions, strong variations of the ionization parameter, and circumgalactic gas in accretion or ejected by these primeval galaxies. AU - Carniani, S AU - Maiolino, R AU - Amorin, R AU - Pentericci, L AU - Pallottini, A AU - Ferrara, A AU - Willott, C J AU - Smit, R AU - Matthee, Jorryt J AU - Sobral, D AU - Santini, P AU - Castellano, M AU - De Barros, S AU - Fontana, A AU - Grazian, A AU - Guaita, L ID - 11555 IS - 1 JF - Monthly Notices of the Royal Astronomical Society KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: evolution KW - galaxies: high-redshift KW - galaxies: ISM KW - galaxies: formation SN - 0035-8711 TI - Kiloparsec-scale gaseous clumps and star formation at z = 5–7 VL - 478 ER - TY - JOUR AB - Observations show that star-forming galaxies reside on a tight 3D plane between mass, gas-phase metallicity, and star formation rate (SFR), which can be explained by the interplay between metal-poor gas inflows, SFR and outflows. However, different metals are released on different time-scales, which may affect the slope of this relation. Here, we use central, star-forming galaxies with Mstar = 109.0–10.5 M⊙ from the EAGLE hydrodynamical simulation to examine 3D relations between mass, SFR, and chemical enrichment using absolute and relative C, N, O, and Fe abundances. We show that the scatter is smaller when gas-phase α-enhancement is used rather than metallicity. A similar plane also exists for stellar α-enhancement, implying that present-day specific SFRs are correlated with long time-scale star formation histories. Between z = 0 and 1, the α-enhancement plane is even more insensitive to redshift than the plane using metallicity. However, it evolves at z > 1 due to lagging iron yields. At fixed mass, galaxies with higher SFRs have star formation histories shifted towards late times, are more α-enhanced, and this α-enhancement increases with redshift as observed. These findings suggest that relations between physical properties inferred from observations may be affected by systematic variations in α-enhancements. AU - Matthee, Jorryt J AU - Schaye, Joop ID - 11584 IS - 1 JF - Monthly Notices of the Royal Astronomical Society: Letters KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: abundances KW - galaxies: evolution KW - galaxies: formation KW - galaxies: star formation SN - 1745-3925 TI - Star-forming galaxies are predicted to lie on a fundamental plane of mass, star formation rate, and α-enhancement VL - 479 ER - TY - JOUR AB - We report on the confirmation and mass determination of π Men c, the first transiting planet discovered by NASA’s TESS space mission. π Men is a naked-eye (V = 5.65 mag), quiet G0 V star that was previously known to host a sub-stellar companion (π Men b) on a longperiod (Porb = 2091 days), eccentric (e = 0.64) orbit. Using TESS time-series photometry, combined with Gaia data, published UCLES at AAT Doppler measurements, and archival HARPS at ESO-3.6m radial velocities, we found that π Men c is a close-in planet with an orbital period of Porb = 6.27 days, a mass of Mc = 4.52 ± 0.81 M⊕, and a radius of Rc = 2.06 ± 0.03 R⊕. Based on the planet’s orbital period and size, π Men c is a super-Earth located at, or close to, the radius gap, while its mass and bulk density suggest it may have held on to a significant atmosphere. Because of the brightness of the host star, this system is highly suitable for a wide range of further studies to characterize the planetary atmosphere and dynamical properties. We also performed an asteroseismic analysis of the TESS data and detected a hint of power excess consistent with the seismic values expected for this star, although this result depends on the photometric aperture used to extract the light curve. This marginal detection is expected from pre-launch simulations hinting at the asteroseismic potential of the TESS mission for longer, multi-sector observations and/or for more evolved bright stars. AU - Gandolfi, D. AU - Barragán, O. AU - Livingston, J. H. AU - Fridlund, M. AU - Justesen, A. B. AU - Redfield, S. AU - Fossati, L. AU - Mathur, S. AU - Grziwa, S. AU - Cabrera, J. AU - García, R. A. AU - Persson, C. M. AU - Van Eylen, V. AU - Hatzes, A. P. AU - Hidalgo, D. AU - Albrecht, S. AU - Bugnet, Lisa Annabelle AU - Cochran, W. D. AU - Csizmadia, Sz. AU - Deeg, H. AU - Eigmüller, Ph. AU - Endl, M. AU - Erikson, A. AU - Esposito, M. AU - Guenther, E. AU - Korth, J. AU - Luque, R. AU - Montañes Rodríguez, P. AU - Nespral, D. AU - Nowak, G. AU - Pätzold, M. AU - Prieto-Arranz, J. ID - 11619 JF - Astronomy & Astrophysics KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - planetary systems / planets and satellites KW - detection / planets and satellites KW - fundamental parameters / planets and satellites KW - terrestrial planets / stars KW - fundamental parameters SN - 0004-6361 TI - TESS’s first planet: A super-Earth transiting the naked-eye star π Mensae VL - 619 ER - TY - JOUR AB - Asteroseismology provides global stellar parameters such as masses, radii, or surface gravities using mean global seismic parameters and effective temperature for thousands of low-mass stars (0.8 M⊙ < M < 3 M⊙). This methodology has been successfully applied to stars in which acoustic modes excited by turbulent convection are measured. Other methods such as the Flicker technique can also be used to determine stellar surface gravities, but only works for log g above 2.5 dex. In this work, we present a new metric called FliPer (Flicker in spectral power density, in opposition to the standard Flicker measurement which is computed in the time domain); it is able to extend the range for which reliable surface gravities can be obtained (0.1 < log g < 4.6 dex) without performing any seismic analysis for stars brighter than Kp < 14. FliPer takes into account the average variability of a star measured in the power density spectrum in a given range of frequencies. However, FliPer values calculated on several ranges of frequency are required to better characterize a star. Using a large set of asteroseismic targets it is possible to calibrate the behavior of surface gravity with FliPer through machine learning. This calibration made with a random forest regressor covers a wide range of surface gravities from main-sequence stars to subgiants and red giants, with very small uncertainties from 0.04 to 0.1 dex. FliPer values can be inserted in automatic global seismic pipelines to either give an estimation of the stellar surface gravity or to assess the quality of the seismic results by detecting any outliers in the obtained νmax values. FliPer also constrains the surface gravities of main-sequence dwarfs using only long-cadence data for which the Nyquist frequency is too low to measure the acoustic-mode properties. AU - Bugnet, Lisa Annabelle AU - García, R. A. AU - Davies, G. R. AU - Mathur, S. AU - Corsaro, E. AU - Hall, O. J. AU - Rendle, B. M. ID - 11618 JF - Astronomy & Astrophysics KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - asteroseismology / methods KW - data analysis / stars KW - oscillations SN - 0004-6361 TI - FliPer: A global measure of power density to estimate surface gravities of main-sequence solar-like stars and red giants VL - 620 ER - TY - JOUR AB - We report the discovery and characterization of HD 89345b (K2-234b; EPIC 248777106b), a Saturn-sized planet orbiting a slightly evolved star. HD 89345 is a bright star (V = 9.3 mag) observed by the K2 mission with 1 min time sampling. It exhibits solar-like oscillations. We conducted asteroseismology to determine the parameters of the star, finding the mass and radius to be 1.12+0.04−0.01M⊙ and 1.657+0.020−0.004R⊙⁠, respectively. The star appears to have recently left the main sequence, based on the inferred age, 9.4+0.4−1.3Gyr⁠, and the non-detection of mixed modes. The star hosts a ‘warm Saturn’ (P = 11.8 d, Rp = 6.86 ± 0.14 R⊕). Radial-velocity follow-up observations performed with the FIbre-fed Echelle Spectrograph, HARPS, and HARPS-N spectrographs show that the planet has a mass of 35.7 ± 3.3 M⊕. The data also show that the planet’s orbit is eccentric (e ≈ 0.2). An investigation of the rotational splitting of the oscillation frequencies of the star yields no conclusive evidence on the stellar inclination angle. We further obtained Rossiter–McLaughlin observations, which result in a broad posterior of the stellar obliquity. The planet seems to confirm to the same patterns that have been observed for other sub-Saturns regarding planet mass and multiplicity, orbital eccentricity, and stellar metallicity. AU - Van Eylen, V AU - Dai, F AU - Mathur, S AU - Gandolfi, D AU - Albrecht, S AU - Fridlund, M AU - García, R A AU - Guenther, E AU - Hjorth, M AU - Justesen, A B AU - Livingston, J AU - Lund, M N AU - Pérez Hernández, F AU - Prieto-Arranz, J AU - Regulo, C AU - Bugnet, Lisa Annabelle AU - Everett, M E AU - Hirano, T AU - Nespral, D AU - Nowak, G AU - Palle, E AU - Silva Aguirre, V AU - Trifonov, T AU - Winn, J N AU - Barragán, O AU - Beck, P G AU - Chaplin, W J AU - Cochran, W D AU - Csizmadia, S AU - Deeg, H AU - Endl, M AU - Heeren, P AU - Grziwa, S AU - Hatzes, A P AU - Hidalgo, D AU - Korth, J AU - Mathis, S AU - Montañes Rodriguez, P AU - Narita, N AU - Patzold, M AU - Persson, C M AU - Rodler, F AU - Smith, A M S ID - 11620 IS - 4 JF - Monthly Notices of the Royal Astronomical Society KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - asteroseismology KW - planets and satellites: composition KW - planets and satellites: formation KW - planets and satellites: fundamental parameters SN - 0035-8711 TI - HD 89345: A bright oscillating star hosting a transiting warm Saturn-sized planet observed by K2 VL - 478 ER - TY - GEN AB - The recently launched NASA Transiting Exoplanet Survey Satellite (TESS) mission is going to collect lightcurves for a few hundred million of stars and we expect to increase the number of pulsating stars to analyze compared to the few thousand stars observed by the CoRoT, Kepler and K2 missions. However, most of the TESS targets have not yet been properly classified and characterized. In order to improve the analysis of the TESS data, it is crucial to determine the type of stellar pulsations in a timely manner. We propose an automatic method to classify stars attending to their pulsation properties, in particular, to identify solar-like pulsators among all TESS targets. It relies on the use of the global amount of power contained in the power spectrum (already known as the FliPer method) as a key parameter, along with the effective temperature, to feed into a machine learning classifier. Our study, based on TESS simulated datasets, shows that we are able to classify pulsators with a 98% accuracy. AU - Bugnet, Lisa Annabelle AU - García, R. A. AU - Davies, G. R. AU - Mathur, S. AU - Hall, O. J. AU - Rendle, B. M. ID - 11631 KW - asteroseismology - methods KW - data analysis - stars KW - oscillations T2 - arXiv TI - FliPer: Classifying TESS pulsating stars ER - TY - JOUR AB - The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi’s contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art exact algorithms, and our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm runs a factor 7.5× faster on average when using 32 threads. To further speed up computations, we also give a version of our algorithm that performs random edge contractions as preprocessing. This version achieves a lower running time and better parallel scalability at the expense of a higher error rate. AU - Henzinger, Monika H AU - Noe, Alexander AU - Schulz, Christian AU - Strash, Darren ID - 11657 JF - ACM Journal of Experimental Algorithmics KW - Theoretical Computer Science SN - 1084-6654 TI - Practical minimum cut algorithms VL - 23 ER - TY - JOUR AB - The focus of classic mechanism design has been on truthful direct-revelation mechanisms. In the context of combinatorial auctions, the truthful direct-revelation mechanism that maximizes social welfare is the Vickrey-Clarke-Groves mechanism. For many valuation spaces, computing the allocation and payments of the VCG mechanism, however, is a computationally hard problem. We thus study the performance of the VCG mechanism when bidders are forced to choose bids from a subspace of the valuation space for which the VCG outcome can be computed efficiently. We prove improved upper bounds on the welfare loss for restrictions to additive bids and upper and lower bounds for restrictions to non-additive bids. These bounds show that increased expressiveness can give rise to additional equilibria of poorer efficiency. AU - Dütting, Paul AU - Henzinger, Monika H AU - Starnberger, Martin ID - 11667 IS - 2 JF - ACM Transactions on Economics and Computation KW - Theory of computation KW - Algorithmic game theory and mechanism design KW - Applied computing KW - Economics KW - Simplified mechanisms KW - Combinatorial auctions with item bidding KW - Price of anarchy SN - 2167-8375 TI - Valuation compressions in VCG-based combinatorial auctions VL - 6 ER - TY - JOUR AB - We present a deterministic incremental algorithm for exactly maintaining the size of a minimum cut with O(log3 n log log2 n) amortized time per edge insertion and O(1) query time. This result partially answers an open question posed by Thorup (2007). It also stays in sharp contrast to a polynomial conditional lower bound for the fully dynamic weighted minimum cut problem. Our algorithm is obtained by combining a sparsification technique of Kawarabayashi and Thorup (2015) or its recent improvement by Henzinger, Rao, and Wang (2017), and an exact incremental algorithm of Henzinger (1997). We also study space-efficient incremental algorithms for the minimum cut problem. Concretely, we show that there exists an O(nlog n/ε2) space Monte Carlo algorithm that can process a stream of edge insertions starting from an empty graph, and with high probability, the algorithm maintains a (1+ε)-approximation to the minimum cut. The algorithm has O((α (n) log3 n)/ε 2) amortized update time and constant query time, where α (n) stands for the inverse of Ackermann function. AU - Goranci, Gramoz AU - Henzinger, Monika H AU - Thorup, Mikkel ID - 11664 IS - 2 JF - ACM Transactions on Algorithms SN - 1549-6325 TI - Incremental exact min-cut in polylogarithmic amortized update time VL - 14 ER - TY - JOUR AB - We develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an O ( f 2)-approximately optimal solution in O ( f · log(m + n)) amortized update time, where f is the maximum “frequency” of an element, n is the number of sets, and m is the maximum number of elements in the universe at any point in time. (2) For the dynamic b-matching problem, we maintain an O (1)-approximately optimal solution in O (log3 n) amortized update time, where n is the number of nodes in the graph. AU - Bhattacharya, Sayan AU - Henzinger, Monika H AU - Italiano, Giuseppe ID - 11757 IS - 08 JF - Information and Computation SN - 0890-5401 TI - Dynamic algorithms via the primal-dual method VL - 261 ER - TY - CONF AB - We consider the problem of dynamically maintaining (approximate) all-pairs effective resistances in separable graphs, which are those that admit an n^{c}-separator theorem for some c<1. We give a fully dynamic algorithm that maintains (1+epsilon)-approximations of the all-pairs effective resistances of an n-vertex graph G undergoing edge insertions and deletions with O~(sqrt{n}/epsilon^2) worst-case update time and O~(sqrt{n}/epsilon^2) worst-case query time, if G is guaranteed to be sqrt{n}-separable (i.e., it is taken from a class satisfying a sqrt{n}-separator theorem) and its separator can be computed in O~(n) time. Our algorithm is built upon a dynamic algorithm for maintaining approximate Schur complement that approximately preserves pairwise effective resistances among a set of terminals for separable graphs, which might be of independent interest. We complement our result by proving that for any two fixed vertices s and t, no incremental or decremental algorithm can maintain the s-t effective resistance for sqrt{n}-separable graphs with worst-case update time O(n^{1/2-delta}) and query time O(n^{1-delta}) for any delta>0, unless the Online Matrix Vector Multiplication (OMv) conjecture is false. We further show that for general graphs, no incremental or decremental algorithm can maintain the s-t effective resistance problem with worst-case update time O(n^{1-delta}) and query-time O(n^{2-delta}) for any delta >0, unless the OMv conjecture is false. AU - Goranci, Gramoz AU - Henzinger, Monika H AU - Peng, Pan ID - 11828 SN - 1868-8969 T2 - 26th Annual European Symposium on Algorithms TI - Dynamic effective resistances and approximate schur complement on separable graphs VL - 112 ER - TY - CONF AB - We study the metric facility location problem with client insertions and deletions. This setting differs from the classic dynamic facility location problem, where the set of clients remains the same, but the metric space can change over time. We show a deterministic algorithm that maintains a constant factor approximation to the optimal solution in worst-case time O~(2^{O(kappa^2)}) per client insertion or deletion in metric spaces while answering queries about the cost in O(1) time, where kappa denotes the doubling dimension of the metric. For metric spaces with bounded doubling dimension, the update time is polylogarithmic in the parameters of the problem. AU - Goranci, Gramoz AU - Henzinger, Monika H AU - Leniowski, Dariusz ID - 11827 SN - 1868-8969 T2 - 26th Annual European Symposium on Algorithms TI - A tree structure for dynamic facility location VL - 112 ER - TY - JOUR AB - In the decremental single-source shortest paths (SSSP) problem, we want to maintain the distances between a given source node s and every other node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach [16] has been the fastest known algorithm for three decades. At the cost of a (1+ϵ)-approximation factor, the running time was recently improved to n2+o(1) by Bernstein and Roditty [9]. In this article, we bring the running time down to near-linear: We give a (1+ϵ)-approximation algorithm with m1+o(1) expected total update time, thus obtaining near-linear time. Moreover, we obtain m1+o(1) log W time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn) time is the mn0.9 + o(1)-time algorithm by Henzinger et al. [18, 19], which works for directed graphs with quasi-polynomial edge weights. The expected running time bound of our algorithm holds against an oblivious adversary. In contrast to the previous results, which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (h, ϵ)-hop set introduced by Cohen [12] in the PRAM literature. An (h, ϵ)-hop set of a graph G=(V, E) is a set F of weighted edges such that the distance between any pair of nodes in G can be (1+ϵ)-approximated by their h-hop distance (given by a path containing at most h edges) on G′=(V, E ∪ F). Our algorithm can maintain an (no(1), ϵ)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain approximate distances using this hop set, we extend the monotone Even-Shiloach tree of Henzinger et al. [20] and combine it with the bounded-hop SSSP technique of Bernstein [4, 5] and Mądry [27]. These two new tools might be of independent interest. AU - Henzinger, Monika H AU - Krinninger, Sebastian AU - Nanongkai, Danupon ID - 11768 IS - 6 JF - Journal of the ACM SN - 0004-5411 TI - Decremental single-source shortest paths on undirected graphs in near-linear total update time VL - 65 ER - TY - CONF AB - We design fast dynamic algorithms for proper vertex and edge colorings in a graph undergoing edge insertions and deletions. In the static setting, there are simple linear time algorithms for (Δ + 1)- vertex coloring and (2Δ – 1)-edge coloring in a graph with maximum degree Δ. It is natural to ask if we can efficiently maintain such colorings in the dynamic setting as well. We get the following three results. (1) We present a randomized algorithm which maintains a (Δ + 1)-vertex coloring with O(log Δ) expected amortized update time. (2) We present a deterministic algorithm which maintains a (1 + o(1)Δ-vertex coloring with O(polylog Δ) amortized update time. (3) We present a simple, deterministic algorithm which maintains a (2Δ – 1)-edge coloring with O(log Δ) worst-case update time. This improves the recent O(Δ)-edge coloring algorithm with worst-case update time [4]. AU - Bhattacharya, Sayan AU - Chakrabarty, Deeparnab AU - Henzinger, Monika H AU - Nanongkai, Danupon ID - 11872 T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms TI - Dynamic algorithms for graph coloring ER - TY - CONF AB - The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi's contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art exact algorithms, and our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm shows good scalability. AU - Henzinger, Monika H AU - Noe, Alexander AU - Schulz, Christian AU - Strash, Darren ID - 11882 T2 - 20th Workshop on Algorithm Engineering and Experiments TI - Practical minimum cut algorithms ER - TY - JOUR AB - We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph 𝐺=(𝑉,𝐸), with |𝑉|=𝑛 and |𝐸|=𝑚, in 𝑜(𝑚‾‾√) time per update. In particular, for minimum vertex cover, we provide deterministic data structures for maintaining a (2+𝜖) approximation in 𝑂(log𝑛/𝜖2) amortized time per update. For maximum matching, we show how to maintain a (3+𝜖) approximation in 𝑂(min(𝑛√/𝜖,𝑚1/3/𝜖2) amortized time per update and a (4+𝜖) approximation in 𝑂(𝑚1/3/𝜖2) worst-case time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld [in 42nd ACM Symposium on Theory of Computing, Cambridge, MA, ACM, 2010, pp. 457--464]. AU - Bhattacharya, Sayan AU - Henzinger, Monika H AU - Italiano, Giuseppe F. ID - 11890 IS - 3 JF - SIAM Journal on Computing SN - 0097-5397 TI - Deterministic fully dynamic data structures for vertex cover and matching VL - 47 ER - TY - CONF AB - It is common knowledge that there is no single best strategy for graph clustering, which justifies a plethora of existing approaches. In this paper, we present a general memetic algorithm, VieClus, to tackle the graph clustering problem. This algorithm can be adapted to optimize different objective functions. A key component of our contribution are natural recombine operators that employ ensemble clusterings as well as multi-level techniques. Lastly, we combine these techniques with a scalable communication protocol, producing a system that is able to compute high-quality solutions in a short amount of time. We instantiate our scheme with local search for modularity and show that our algorithm successfully improves or reproduces all entries of the 10th DIMACS implementation challenge under consideration using a small amount of time. AU - Biedermann, Sonja AU - Henzinger, Monika H AU - Schulz, Christian AU - Schuster, Bernhard ID - 11911 SN - 1868-8969 T2 - 17th International Symposium on Experimental Algorithms TI - Memetic graph clustering VL - 103 ER - TY - JOUR AB - Two generalizations of Itô formula to infinite-dimensional spaces are given. The first one, in Hilbert spaces, extends the classical one by taking advantage of cancellations when they occur in examples and it is applied to the case of a group generator. The second one, based on the previous one and a limit procedure, is an Itô formula in a special class of Banach spaces having a product structure with the noise in a Hilbert component; again the key point is the extension due to a cancellation. This extension to Banach spaces and in particular the specific cancellation are motivated by path-dependent Itô calculus. AU - Flandoli, Franco AU - Russo, Francesco AU - Zanco, Giovanni A ID - 1215 IS - 2 JF - Journal of Theoretical Probability TI - Infinite-dimensional calculus under weak spatial regularity of the processes VL - 31 ER - TY - JOUR AB - For a general class of non-negative functions defined on integral ideals of number fields, upper bounds are established for their average over the values of certain principal ideals that are associated to irreducible binary forms with integer coefficients. AU - Browning, Timothy D AU - Sofos, Efthymios ID - 176 IS - 3 JF - International Journal of Nuber Theory TI - Averages of arithmetic functions over principal ideals VL - 15 ER - TY - JOUR AB - We give an upper bound for the number of rational points of height at most B, lying on a surface defined by a quadratic form Q. The bound shows an explicit dependence on Q. It is optimal with respect to B, and is also optimal for typical forms Q. AU - Browning, Timothy D AU - Heath-Brown, Roger ID - 178 JF - Discrete Analysis TI - Counting rational points on quadric surfaces VL - 15 ER - TY - CONF AB - We resolve in the affirmative conjectures of A. Skopenkov and Repovš (1998), and M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the setting of approximating maps of graphs on 2-dimensional surfaces by embeddings. Our proof of this result is constructive and almost immediately implies an efficient algorithm for testing whether a given piecewise linear map of a graph in a surface is approximable by an embedding. More precisely, an instance of this problem consists of (i) a graph G whose vertices are partitioned into clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a region R of a 2-dimensional compact surface M given as the union of a set of pairwise disjoint discs corresponding to the clusters and a set of pairwise disjoint "pipes" corresponding to the bundles, connecting certain pairs of these discs. We are to decide whether G can be embedded inside M so that the vertices in every cluster are drawn in the corresponding disc, the edges in every bundle pass only through its corresponding pipe, and every edge crosses the boundary of each disc at most once. AU - Fulek, Radoslav AU - Kynčl, Jan ID - 185 SN - 978-3-95977-066-8 TI - Hanani-Tutte for approximating maps of graphs VL - 99 ER - TY - CONF AB - Smallest enclosing spheres of finite point sets are central to methods in topological data analysis. Focusing on Bregman divergences to measure dissimilarity, we prove bounds on the location of the center of a smallest enclosing sphere. These bounds depend on the range of radii for which Bregman balls are convex. AU - Edelsbrunner, Herbert AU - Virk, Ziga AU - Wagner, Hubert ID - 188 TI - Smallest enclosing spheres and Chernoff points in Bregman geometry VL - 99 ER - TY - JOUR AB - We consider the problem of learning a Bayesian network or directed acyclic graph model from observational data. A number of constraint‐based, score‐based and hybrid algorithms have been developed for this purpose. Statistical consistency guarantees of these algorithms rely on the faithfulness assumption, which has been shown to be restrictive especially for graphs with cycles in the skeleton. We here propose the sparsest permutation (SP) algorithm, showing that learning Bayesian networks is possible under strictly weaker assumptions than faithfulness. This comes at a computational price, thereby indicating a statistical‐computational trade‐off for causal inference algorithms. In the Gaussian noiseless setting, we prove that the SP algorithm boils down to finding the permutation of the variables with the sparsest Cholesky decomposition of the inverse covariance matrix, which is equivalent to ℓ0‐penalized maximum likelihood estimation. We end with a simulation study showing that in line with the proven stronger consistency guarantees, and the SP algorithm compares favourably to standard causal inference algorithms in terms of accuracy for a given sample size. AU - Raskutti, Garvesh AU - Uhler, Caroline ID - 2015 IS - 1 JF - STAT TI - Learning directed acyclic graphs based on sparsest permutations VL - 7 ER - TY - JOUR AB - A cornerstone of statistical inference, the maximum entropy framework is being increasingly applied to construct descriptive and predictive models of biological systems, especially complex biological networks, from large experimental data sets. Both its broad applicability and the success it obtained in different contexts hinge upon its conceptual simplicity and mathematical soundness. Here we try to concisely review the basic elements of the maximum entropy principle, starting from the notion of ‘entropy’, and describe its usefulness for the analysis of biological systems. As examples, we focus specifically on the problem of reconstructing gene interaction networks from expression data and on recent work attempting to expand our system-level understanding of bacterial metabolism. Finally, we highlight some extensions and potential limitations of the maximum entropy approach, and point to more recent developments that are likely to play a key role in the upcoming challenges of extracting structures and information from increasingly rich, high-throughput biological data. AU - De Martino, Andrea AU - De Martino, Daniele ID - 306 IS - 4 JF - Heliyon TI - An introduction to the maximum entropy approach and its application to inference problems in biology VL - 4 ER - TY - CHAP AB - Developmental processes are inherently dynamic and understanding them requires quantitative measurements of gene and protein expression levels in space and time. While live imaging is a powerful approach for obtaining such data, it is still a challenge to apply it over long periods of time to large tissues, such as the embryonic spinal cord in mouse and chick. Nevertheless, dynamics of gene expression and signaling activity patterns in this organ can be studied by collecting tissue sections at different developmental stages. In combination with immunohistochemistry, this allows for measuring the levels of multiple developmental regulators in a quantitative manner with high spatiotemporal resolution. The mean protein expression levels over time, as well as embryo-to-embryo variability can be analyzed. A key aspect of the approach is the ability to compare protein levels across different samples. This requires a number of considerations in sample preparation, imaging and data analysis. Here we present a protocol for obtaining time course data of dorsoventral expression patterns from mouse and chick neural tube in the first 3 days of neural tube development. The described workflow starts from embryo dissection and ends with a processed dataset. Software scripts for data analysis are included. The protocol is adaptable and instructions that allow the user to modify different steps are provided. Thus, the procedure can be altered for analysis of time-lapse images and applied to systems other than the neural tube. AU - Zagórski, Marcin P AU - Kicheva, Anna ID - 37 SN - 1064-3745 T2 - Morphogen Gradients TI - Measuring dorsoventral pattern and morphogen signaling profiles in the growing neural tube VL - 1863 ER - TY - CONF AB - Probabilistic programs extend classical imperative programs with real-valued random variables and random branching. The most basic liveness property for such programs is the termination property. The qualitative (aka almost-sure) termination problem asks whether a given program program terminates with probability 1. While ranking functions provide a sound and complete method for non-probabilistic programs, the extension of them to probabilistic programs is achieved via ranking supermartingales (RSMs). Although deep theoretical results have been established about RSMs, their application to probabilistic programs with nondeterminism has been limited only to programs of restricted control-flow structure. For non-probabilistic programs, lexicographic ranking functions provide a compositional and practical approach for termination analysis of real-world programs. In this work we introduce lexicographic RSMs and show that they present a sound method for almost-sure termination of probabilistic programs with nondeterminism. We show that lexicographic RSMs provide a tool for compositional reasoning about almost-sure termination, and for probabilistic programs with linear arithmetic they can be synthesized efficiently (in polynomial time). We also show that with additional restrictions even asymptotic bounds on expected termination time can be obtained through lexicographic RSMs. Finally, we present experimental results on benchmarks adapted from previous work to demonstrate the effectiveness of our approach. AU - Agrawal, Sheshansh AU - Chatterjee, Krishnendu AU - Novotny, Petr ID - 325 IS - POPL TI - Lexicographic ranking supermartingales: an efficient approach to termination of probabilistic programs VL - 2 ER - TY - JOUR AB - The valley pseudospin in monolayer transition metal dichalcogenides (TMDs) has been proposed as a new way to manipulate information in various optoelectronic devices. This relies on a large valley polarization that remains stable over long time scales (hundreds of nanoseconds). However, time-resolved measurements report valley lifetimes of only a few picoseconds. This has been attributed to mechanisms such as phonon-mediated intervalley scattering and a precession of the valley pseudospin through electron-hole exchange. Here we use transient spin grating to directly measure the valley depolarization lifetime in monolayer MoSe2. We find a fast valley decay rate that scales linearly with the excitation density at different temperatures. This establishes the presence of strong exciton-exciton Coulomb exchange interactions enhancing the valley depolarization. Our work highlights the microscopic processes inhibiting the efficient use of the exciton valley pseudospin in monolayer TMDs. AU - Mahmood, Fahad AU - Alpichshev, Zhanybek AU - Lee, Yi AU - Kong, Jing AU - Gedik, Nuh ID - 394 IS - 1 JF - Nano Letters TI - Observation of exciton-exciton interaction mediated valley Depolarization in Monolayer MoSe2 VL - 18 ER - TY - JOUR AB - In 2013, a publication repository was implemented at IST Austria and 2015 after a thorough preparation phase a data repository was implemented - both based on the Open Source Software EPrints. In this text, designed as field report, we will reflect on our experiences with Open Source Software in general and specifically with EPrints regarding technical aspects but also regarding their characteristics of the user community. The second part is a pleading for including the end users in the process of implementation, adaption and evaluation. AU - Petritsch, Barbara AU - Porsche, Jana ID - 53 IS - 1 JF - VÖB Mitteilungen TI - IST PubRep and IST DataRep: the institutional repositories at IST Austria VL - 71 ER - TY - JOUR AB - We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary. We describe a new randomized consensus protocol with expected message complexity O(n2log2n) when fewer than n / 2 processes may fail by crashing. This is an almost-linear improvement over the best previously known protocol, and within logarithmic factors of a known Ω(n2) message lower bound. The protocol further ensures that no process sends more than O(nlog3n) messages in expectation, which is again within logarithmic factors of optimal. We also present a generalization of the algorithm to an arbitrary number of failures t, which uses expected O(nt+t2log2t) total messages. Our approach is to build a message-efficient, resilient mechanism for aggregating individual processor votes, implementing the message-passing equivalent of a weak shared coin. Roughly, in our protocol, a processor first announces its votes to small groups, then propagates them to increasingly larger groups as it generates more and more votes. To bound the number of messages that an individual process might have to send or receive, the protocol progressively increases the weight of generated votes. The main technical challenge is bounding the impact of votes that are still “in flight” (generated, but not fully propagated) on the final outcome of the shared coin, especially since such votes might have different weights. We achieve this by leveraging the structure of the algorithm, and a technical argument based on martingale concentration bounds. Overall, we show that it is possible to build an efficient message-passing implementation of a shared coin, and in the process (almost-optimally) solve the classic consensus problem in the asynchronous message-passing model. AU - Alistarh, Dan-Adrian AU - Aspnes, James AU - King, Valerie AU - Saia, Jared ID - 536 IS - 6 JF - Distributed Computing SN - 01782770 TI - Communication-efficient randomized consensus VL - 31 ER - TY - JOUR AB - We analyse the canonical Bogoliubov free energy functional in three dimensions at low temperatures in the dilute limit. We prove existence of a first-order phase transition and, in the limit (Formula presented.), we determine the critical temperature to be (Formula presented.) to leading order. Here, (Formula presented.) is the critical temperature of the free Bose gas, ρ is the density of the gas and a is the scattering length of the pair-interaction potential V. We also prove asymptotic expansions for the free energy. In particular, we recover the Lee–Huang–Yang formula in the limit (Formula presented.). AU - Napiórkowski, Marcin M AU - Reuvers, Robin AU - Solovej, Jan ID - 554 IS - 1 JF - Communications in Mathematical Physics SN - 00103616 TI - The Bogoliubov free energy functional II: The dilute Limit VL - 360 ER - TY - CHAP AB - Primary neuronal cell culture preparations are widely used to investigate synaptic functions. This chapter describes a detailed protocol for the preparation of a neuronal cell culture in which giant calyx-type synaptic terminals are formed. This chapter also presents detailed protocols for utilizing the main technical advantages provided by such a preparation, namely, labeling and imaging of synaptic organelles and electrophysiological recordings directly from presynaptic terminals. AU - Dimitrov, Dimitar AU - Guillaud, Laurent AU - Eguchi, Kohgaku AU - Takahashi, Tomoyuki ED - Skaper, Stephen D. ID - 562 T2 - Neurotrophic Factors TI - Culture of mouse giant central nervous system synapses and application for imaging and electrophysiological analyses VL - 1727 ER - TY - CHAP AB - We prove that there is no strongly regular graph (SRG) with parameters (460; 153; 32; 60). The proof is based on a recent lower bound on the number of 4-cliques in a SRG and some applications of Euclidean representation of SRGs. AU - Bondarenko, Andriy AU - Mellit, Anton AU - Prymak, Andriy AU - Radchenko, Danylo AU - Viazovska, Maryna ID - 61 T2 - Contemporary Computational Mathematics TI - There is no strongly regular graph with parameters (460; 153; 32; 60) ER - TY - JOUR AB - Neurons develop elaborate morphologies that provide a model for understanding cellular architecture. By studying C. elegans sensory dendrites, we previously identified genes that act to promote the extension of ciliated sensory dendrites during embryogenesis. Interestingly, the nonciliated dendrite of the oxygen-sensing neuron URX is not affected by these genes, suggesting it develops through a distinct mechanism. Here, we use a visual forward genetic screen to identify mutants that affect URX dendrite morphogenesis. We find that disruption of the MAP kinase MAPK-15 or the βH-spectrin SMA-1 causes a phenotype opposite to what we had seen before: dendrites extend normally during embryogenesis but begin to overgrow as the animals reach adulthood, ultimately extending up to 150% of their normal length. SMA-1 is broadly expressed and acts non-cell-autonomously, while MAPK-15 is expressed in many sensory neurons including URX and acts cell-autonomously. MAPK-15 acts at the time of overgrowth, localizes at the dendrite ending, and requires its kinase activity, suggesting it acts locally in time and space to constrain dendrite growth. Finally, we find that the oxygen-sensing guanylate cyclase GCY-35, which normally localizes at the dendrite ending, is localized throughout the overgrown region, and that overgrowth can be suppressed by overexpressing GCY-35 or by genetically mimicking elevated cGMP signaling. These results suggest that overgrowth may correspond to expansion of a sensory compartment at the dendrite ending, reminiscent of the remodeling of sensory cilia or dendritic spines. Thus, in contrast to established pathways that promote dendrite growth during early development, our results reveal a distinct mechanism that constrains dendrite growth throughout the life of the animal, possibly by controlling the size of a sensory compartment at the dendrite ending. AU - McLachlan, Ian G. AU - Beets, Isabel AU - de Bono, Mario AU - Heiman, Maxwell G. ID - 6111 IS - 6 JF - PLOS Genetics SN - 1553-7404 TI - A neuronal MAP kinase constrains growth of a Caenorhabditis elegans sensory dendrite throughout the life of the organism VL - 14 ER - TY - JOUR AB - Neuropeptides are ubiquitous modulators of behavior and physiology. They are packaged in specialized secretory organelles called dense core vesicles (DCVs) that are released upon neural stimulation. Unlike synaptic vesicles, which can be recycled and refilled close to release sites, DCVs must be replenished by de novo synthesis in the cell body. Here, we dissect DCV cell biology in vivo in a Caenorhabditis elegans sensory neuron whose tonic activity we can control using a natural stimulus. We express fluorescently tagged neuropeptides in the neuron and define parameters that describe their subcellular distribution. We measure these parameters at high and low neural activity in 187 mutants defective in proteins implicated in membrane traffic, neuroendocrine secretion, and neuronal or synaptic activity. Using unsupervised hierarchical clustering methods, we analyze these data and identify 62 groups of genes with similar mutant phenotypes. We explore the function of a subset of these groups. We recapitulate many previous findings, validating our paradigm. We uncover a large battery of proteins involved in recycling DCV membrane proteins, something hitherto poorly explored. We show that the unfolded protein response promotes DCV production, which may contribute to intertissue communication of stress. We also find evidence that different mechanisms of priming and exocytosis may operate at high and low neural activity. Our work provides a defined framework to study DCV biology at different neural activity levels. AU - Laurent, Patrick AU - Ch’ng, QueeLim AU - Jospin, Maëlle AU - Chen, Changchun AU - Lorenzo, Ramiro AU - de Bono, Mario ID - 6109 IS - 29 JF - Proceedings of the National Academy of Sciences SN - 0027-8424 TI - Genetic dissection of neuropeptide cell biology at high and low activity in a defined sensory neuron VL - 115 ER - TY - JOUR AB - Blood platelets are critical for hemostasis and thrombosis, but also play diverse roles during immune responses. We have recently reported that platelets migrate at sites of infection in vitro and in vivo. Importantly, platelets use their ability to migrate to collect and bundle fibrin (ogen)-bound bacteria accomplishing efficient intravascular bacterial trapping. Here, we describe a method that allows analyzing platelet migration in vitro, focusing on their ability to collect bacteria and trap bacteria under flow. AU - Fan, Shuxia AU - Lorenz, Michael AU - Massberg, Steffen AU - Gärtner, Florian R ID - 6354 IS - 18 JF - Bio-Protocol KW - Platelets KW - Cell migration KW - Bacteria KW - Shear flow KW - Fibrinogen KW - E. coli SN - 2331-8325 TI - Platelet migration and bacterial trapping assay under flow VL - 8 ER - TY - JOUR AB - An optical network of superconducting quantum bits (qubits) is an appealing platform for quantum communication and distributed quantum computing, but developing a quantum-compatible link between the microwave and optical domains remains an outstanding challenge. Operating at T < 100 mK temperatures, as required for quantum electrical circuits, we demonstrate a mechanically mediated microwave–optical converter with 47% conversion efficiency, and use a classical feed-forward protocol to reduce added noise to 38 photons. The feed-forward protocol harnesses our discovery that noise emitted from the two converter output ports is strongly correlated because both outputs record thermal motion of the same mechanical mode. We also discuss a quantum feed-forward protocol that, given high system efficiencies, would allow quantum information to be transferred even when thermal phonons enter the mechanical element faster than the electro-optic conversion rate. AU - Higginbotham, Andrew P AU - Burns, P. S. AU - Urmey, M. D. AU - Peterson, R. W. AU - Kampel, N. S. AU - Brubaker, B. M. AU - Smith, G. AU - Lehnert, K. W. AU - Regal, C. A. ID - 6368 IS - 10 JF - Nature Physics SN - 1745-2473 TI - Harnessing electro-optic correlations in an efficient mechanical converter VL - 14 ER - TY - JOUR AB - We construct a metamaterial from radio-frequency harmonic oscillators, and find two topologically distinct phases resulting from dissipation engineered into the system. These phases are distinguished by a quantized value of bulk energy transport. The impulse response of our circuit is measured and used to reconstruct the band structure and winding number of circuit eigenfunctions around a dark mode. Our results demonstrate that dissipative topological transport can occur in a wider class of physical systems than considered before. AU - Rosenthal, Eric I. AU - Ehrlich, Nicole K. AU - Rudner, Mark S. AU - Higginbotham, Andrew P AU - Lehnert, K. W. ID - 6369 IS - 22 JF - Physical Review B SN - 2469-9950 TI - Topological phase transition measured in a dissipative metamaterial VL - 97 ER - TY - GEN AU - Petritsch, Barbara ID - 6459 KW - Open Access KW - Publication Analysis TI - Open Access at IST Austria 2009-2017 ER - TY - CONF AB - Reed-Muller (RM) and polar codes are a class of capacity-achieving channel coding schemes with the same factor graph representation. Low-complexity decoding algorithms fall short in providing a good error-correction performance for RM and polar codes. Using the symmetric group of RM and polar codes, the specific decoding algorithm can be carried out on multiple permutations of the factor graph to boost the error-correction performance. However, this approach results in high decoding complexity. In this paper, we first derive the total number of factor graph permutations on which the decoding can be performed. We further propose a successive permutation (SP) scheme which finds the permutations on the fly, thus the decoding always progresses on a single factor graph permutation. We show that SP can be used to improve the error-correction performance of RM and polar codes under successive-cancellation (SC) and SC list (SCL) decoding, while keeping the memory requirements of the decoders unaltered. Our results for RM and polar codes of length 128 and rate 0.5 show that when SP is used and at a target frame error rate of 10 -4 , up to 0.5 dB and 0.1 dB improvement can be achieved for RM and polar codes respectively. AU - Hashemi, Seyyed Ali AU - Doan, Nghia AU - Mondelli, Marco AU - Gross, Warren ID - 6664 T2 - 2018 IEEE 10th International Symposium on Turbo Codes & Iterative Information Processing TI - Decoding Reed-Muller and polar codes by successive factor graph permutations ER - TY - CONF AB - Polar codes are a channel coding scheme for the next generation of wireless communications standard (5G). The belief propagation (BP) decoder allows for parallel decoding of polar codes, making it suitable for high throughput applications. However, the error-correction performance of polar codes under BP decoding is far from the requirements of 5G. It has been shown that the error-correction performance of BP can be improved if the decoding is performed on multiple permuted factor graphs of polar codes. However, a different BP decoding scheduling is required for each factor graph permutation which results in the design of a different decoder for each permutation. Moreover, the selection of the different factor graph permutations is at random, which prevents the decoder to achieve a desirable error correction performance with a small number of permutations. In this paper, we first show that the permutations on the factor graph can be mapped into suitable permutations on the codeword positions. As a result, we can make use of a single decoder for all the permutations. In addition, we introduce a method to construct a set of predetermined permutations which can provide the correct codeword if the decoding fails on the original permutation. We show that for the 5G polar code of length 1024, the error-correction performance of the proposed decoder is more than 0.25 dB better than that of the BP decoder with the same number of random permutations at the frame error rate of 10 -4 . AU - Doan, Nghia AU - Hashemi, Seyyed Ali AU - Mondelli, Marco AU - Gross, Warren J. ID - 6728 SN - 9781538647271 T2 - 2018 IEEE Global Communications Conference TI - On the decoding of polar codes on permuted factor graphs ER - TY - JOUR AB - We survey coding techniques that enable reliable transmission at rates that approach the capacity of an arbitrary discrete memoryless channel. In particular, we take the point of view of modern coding theory and discuss how recent advances in coding for symmetric channels help provide more efficient solutions for the asymmetric case. We consider, in more detail, three basic coding paradigms. The first one is Gallager's scheme that consists of concatenating a linear code with a non-linear mapping so that the input distribution can be appropriately shaped. We explicitly show that both polar codes and spatially coupled codes can be employed in this scenario. Furthermore, we derive a scaling law between the gap to capacity, the cardinality of the input and output alphabets, and the required size of the mapper. The second one is an integrated scheme in which the code is used both for source coding, in order to create codewords distributed according to the capacity-achieving input distribution, and for channel coding, in order to provide error protection. Such a technique has been recently introduced by Honda and Yamamoto in the context of polar codes, and we show how to apply it also to the design of sparse graph codes. The third paradigm is based on an idea of Böcherer and Mathar, and separates the two tasks of source coding and channel coding by a chaining construction that binds together several codewords. We present conditions for the source code and the channel code, and we describe how to combine any source code with any channel code that fulfill those conditions, in order to provide capacity-achieving schemes for asymmetric channels. In particular, we show that polar codes, spatially coupled codes, and homophonic codes are suitable as basic building blocks of the proposed coding strategy. Rather than focusing on the exact details of the schemes, the purpose of this tutorial is to present different coding techniques that can then be implemented with many variants. There is no absolute winner and, in order to understand the most suitable technique for a specific application scenario, we provide a detailed comparison that takes into account several performance metrics. AU - Mondelli, Marco AU - Hassani, Hamed AU - Urbanke, Rudiger ID - 6678 IS - 5 JF - IEEE Transactions on Information Theory SN - 0018-9448 TI - How to achieve the capacity of asymmetric channels VL - 64 ER - TY - JOUR AB - We consider spectral properties and the edge universality of sparse random matrices, the class of random matrices that includes the adjacency matrices of the Erdős–Rényi graph model G(N, p). We prove a local law for the eigenvalue density up to the spectral edges. Under a suitable condition on the sparsity, we also prove that the rescaled extremal eigenvalues exhibit GOE Tracy–Widom fluctuations if a deterministic shift of the spectral edge due to the sparsity is included. For the adjacency matrix of the Erdős–Rényi graph this establishes the Tracy–Widom fluctuations of the second largest eigenvalue when p is much larger than N−2/3 with a deterministic shift of order (Np)−1. AU - Lee, Jii AU - Schnelli, Kevin ID - 690 IS - 1-2 JF - Probability Theory and Related Fields TI - Local law and Tracy–Widom limit for sparse random matrices VL - 171 ER - TY - CONF AB - We present a coding paradigm that provides a new achievable rate for the primitive relay channel by combining compress-and-forward and decode-and-forward with a chaining construction. In the primitive relay channel model, the source broadcasts a message to the relay and to the destination; and the relay facilitates this communication by sending an additional message to the destination through a separate channel. Two well-known coding approaches for this setting are decode-and-forward and compress-and-forward: in the former, the relay decodes the message and sends some of the information to the destination; in the latter, the relay does not attempt to decode, but it sends a compressed description of the received sequence to the destination via Wyner-Ziv coding. In our scheme, we transmit over pairs of blocks and we use compress-and-forward for the first block and decode-and-forward for the second. In particular, in the first block, the relay does not attempt to decode and it sends only a part of the compressed description of the received sequence; in the second block, the relay decodes the message and sends this information plus the remaining part of the compressed sequence relative to the first block. As a result, we strictly outperform both compress-and- forward and decode-and-forward. Furthermore, this paradigm can be implemented with a low-complexity polar coding scheme that has the typical attractive features of polar codes, i.e., quasi-linear encoding/decoding complexity and super-polynomial decay of the error probability. Throughout the paper we consider as a running example the special case of the erasure relay channel and we compare the rates achievable by our proposed scheme with the existing upper and lower bounds. AU - Mondelli, Marco AU - Hassani, Hamed AU - Urbanke, Rudiger ID - 6675 T2 - 2018 IEEE International Symposium on Information Theory TI - A new coding paradigm for the primitive relay channel ER - TY - JOUR AB - We consider the NP-hard problem of MAP-inference for undirected discrete graphical models. We propose a polynomial time and practically efficient algorithm for finding a part of its optimal solution. Specifically, our algorithm marks some labels of the considered graphical model either as (i) optimal, meaning that they belong to all optimal solutions of the inference problem; (ii) non-optimal if they provably do not belong to any solution. With access to an exact solver of a linear programming relaxation to the MAP-inference problem, our algorithm marks the maximal possible (in a specified sense) number of labels. We also present a version of the algorithm, which has access to a suboptimal dual solver only and still can ensure the (non-)optimality for the marked labels, although the overall number of the marked labels may decrease. We propose an efficient implementation, which runs in time comparable to a single run of a suboptimal dual solver. Our method is well-scalable and shows state-of-the-art results on computational benchmarks from machine learning and computer vision. AU - Shekhovtsov, Alexander AU - Swoboda, Paul AU - Savchynskyy, Bogdan ID - 703 IS - 7 JF - IEEE Transactions on Pattern Analysis and Machine Intelligence SN - 01628828 TI - Maximum persistency via iterative relaxed inference with graphical models VL - 40 ER - TY - JOUR AB - The high-pressure synthesis and incommensurately modulated structure are reported for the new compound Sr2Pt8−xAs, with x = 0.715 (5). The structure consists of Sr2Pt3As layers alternating with Pt-only corrugated grids. Ab initio calculations predict a metallic character with a dominant role of the Pt d electrons. The electrical resistivity (ρ) and Seebeck coefficient confirm the metallic character, but surprisingly, ρ showed a near-flat temperature dependence. This observation fits the description of the Mooij correlation for electrical resistivity in disordered metals, originally developed for statistically distributed point defects. The discussed material has a long-range crystallographic order, but the high concentration of Pt vacancies, incommensurately ordered, strongly influences the electronic conduction properties. This result extends the range of validity of the Mooij correlation to long-range ordered incommensurately modulated vacancies. Motivated by the layered structure, the resistivity anisotropy was measured in a focused-ion-beam micro-fabricated well oriented single crystal. A low resistivity anisotropy indicates that the layers are electrically coupled and conduction channels along different directions are intermixed. AU - Martino, Edoardo AU - Arakcheeva, Alla AU - Autès, Gabriel AU - Pisoni, Andrea AU - Bachmann, Maja D. AU - Modic, Kimberly A AU - Helm, Toni AU - Yazyev, Oleg V. AU - Moll, Philip J. W. AU - Forró, László AU - Katrych, Sergiy ID - 7063 IS - 4 JF - IUCrJ TI - Sr2Pt8−xAs: A layered incommensurately modulated metal with saturated resistivity VL - 5 ER - TY - JOUR AB - Weyl fermions are a recently discovered ingredient for correlated states of electronic matter. A key difficulty has been that real materials also contain non-Weyl quasiparticles, and disentangling the experimental signatures has proven challenging. Here we use magnetic fields up to 95 T to drive the Weyl semimetal TaAs far into its quantum limit, where only the purely chiral 0th Landau levels of the Weyl fermions are occupied. We find the electrical resistivity to be nearly independent of magnetic field up to 50 T: unusual for conventional metals but consistent with the chiral anomaly for Weyl fermions. Above 50 T we observe a two-order-of-magnitude increase in resistivity, indicating that a gap opens in the chiral Landau levels. Above 80 T we observe strong ultrasonic attenuation below 2 K, suggesting a mesoscopically textured state of matter. These results point the way to inducing new correlated states of matter in the quantum limit of Weyl semimetals. AU - Ramshaw, B. J. AU - Modic, Kimberly A AU - Shekhter, Arkady AU - Zhang, Yi AU - Kim, Eun-Ah AU - Moll, Philip J. W. AU - Bachmann, Maja D. AU - Chan, M. K. AU - Betts, J. B. AU - Balakirev, F. AU - Migliori, A. AU - Ghimire, N. J. AU - Bauer, E. D. AU - Ronning, F. AU - McDonald, R. D. ID - 7062 IS - 1 JF - Nature Communications SN - 2041-1723 TI - Quantum limit transport and destruction of the Weyl nodes in TaAs VL - 9 ER - TY - JOUR AB - Unusual behavior in quantum materials commonly arises from their effective low-dimensional physics, reflecting the underlying anisotropy in the spin and charge degrees of freedom. Here we introduce the magnetotropic coefficient k = ∂2F/∂θ2, the second derivative of the free energy F with respect to the magnetic field orientation θ in the crystal. We show that the magnetotropic coefficient can be quantitatively determined from a shift in the resonant frequency of a commercially available atomic force microscopy cantilever under magnetic field. This detection method enables part per 100 million sensitivity and the ability to measure magnetic anisotropy in nanogram-scale samples, as demonstrated on the Weyl semimetal NbP. Measurement of the magnetotropic coefficient in the spin-liquid candidate RuCl3 highlights its sensitivity to anisotropic phase transitions and allows a quantitative comparison to other thermodynamic coefficients via the Ehrenfest relations. AU - Modic, Kimberly A AU - Bachmann, Maja D. AU - Ramshaw, B. J. AU - Arnold, F. AU - Shirer, K. R. AU - Estry, Amelia AU - Betts, J. B. AU - Ghimire, Nirmal J. AU - Bauer, E. D. AU - Schmidt, Marcus AU - Baenitz, Michael AU - Svanidze, E. AU - McDonald, Ross D. AU - Shekhter, Arkady AU - Moll, Philip J. W. ID - 7059 IS - 1 JF - Nature Communications SN - 2041-1723 TI - Resonant torsion magnetometry in anisotropic quantum materials VL - 9 ER - TY - JOUR AB - We examine recent magnetic torque measurements in two compounds, γ−Li2IrO3 and RuCl3, which have been discussed as possible realizations of the Kitaev model. The analysis of the reported discontinuity in torque, as an external magnetic field is rotated across the c axis in both crystals, suggests that they have a translationally invariant chiral spin order of the form ⟨Si⋅(Sj×Sk)⟩≠0 in the ground state and persisting over a very wide range of magnetic field and temperature. An extraordinary |B|B2 dependence of the torque for small fields, beside the usual B2 part, is predicted by the chiral spin order. Data for small fields are available for γ−Li2IrO3 and are found to be consistent with the prediction upon further analysis. Other experiments such as inelastic scattering and thermal Hall effect and several questions raised by the discovery of chiral spin order, including its topological consequences, are discussed. AU - Modic, Kimberly A AU - Ramshaw, B. J. AU - Shekhter, A. AU - Varma, C. M. ID - 7058 IS - 20 JF - Physical Review B SN - 2469-9950 TI - Chiral spin order in some purported Kitaev spin-liquid compounds VL - 98 ER - TY - CONF AB - Training deep learning models has received tremendous research interest recently. In particular, there has been intensive research on reducing the communication cost of training when using multiple computational devices, through reducing the precision of the underlying data representation. Naturally, such methods induce system trade-offs—lowering communication precision could de-crease communication overheads and improve scalability; but, on the other hand, it can also reduce the accuracy of training. In this paper, we study this trade-off space, and ask:Can low-precision communication consistently improve the end-to-end performance of training modern neural networks, with no accuracy loss?From the performance point of view, the answer to this question may appear deceptively easy: compressing communication through low precision should help when the ratio between communication and computation is high. However, this answer is less straightforward when we try to generalize this principle across various neural network architectures (e.g., AlexNet vs. ResNet),number of GPUs (e.g., 2 vs. 8 GPUs), machine configurations(e.g., EC2 instances vs. NVIDIA DGX-1), communication primitives (e.g., MPI vs. NCCL), and even different GPU architectures(e.g., Kepler vs. Pascal). Currently, it is not clear how a realistic realization of all these factors maps to the speed up provided by low-precision communication. In this paper, we conduct an empirical study to answer this question and report the insights. AU - Grubic, Demjan AU - Tam, Leo AU - Alistarh, Dan-Adrian AU - Zhang, Ce ID - 7116 SN - 2367-2005 T2 - Proceedings of the 21st International Conference on Extending Database Technology TI - Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study ER - TY - JOUR AB - In the Minimum Description Length (MDL) principle, learning from the data is equivalent to an optimal coding problem. We show that the codes that achieve optimal compression in MDL are critical in a very precise sense. First, when they are taken as generative models of samples, they generate samples with broad empirical distributions and with a high value of the relevance, defined as the entropy of the empirical frequencies. These results are derived for different statistical models (Dirichlet model, independent and pairwise dependent spin models, and restricted Boltzmann machines). Second, MDL codes sit precisely at a second order phase transition point where the symmetry between the sampled outcomes is spontaneously broken. The order parameter controlling the phase transition is the coding cost of the samples. The phase transition is a manifestation of the optimality of MDL codes, and it arises because codes that achieve a higher compression do not exist. These results suggest a clear interpretation of the widespread occurrence of statistical criticality as a characterization of samples which are maximally informative on the underlying generative process. AU - Cubero, Ryan J AU - Marsili, Matteo AU - Roudi, Yasser ID - 7126 IS - 10 JF - Entropy KW - Minimum Description Length KW - normalized maximum likelihood KW - statistical criticality KW - phase transitions KW - large deviations SN - 1099-4300 TI - Minimum description length codes are critical VL - 20 ER - TY - JOUR AB - Solid alkali metal carbonates are universal passivation layer components of intercalation battery materials and common side products in metal‐O2 batteries, and are believed to form and decompose reversibly in metal‐O2/CO2 cells. In these cathodes, Li2CO3 decomposes to CO2 when exposed to potentials above 3.8 V vs. Li/Li+. However, O2 evolution, as would be expected according to the decomposition reaction 2 Li2CO3→4 Li++4 e−+2 CO2+O2, is not detected. O atoms are thus unaccounted for, which was previously ascribed to unidentified parasitic reactions. Here, we show that highly reactive singlet oxygen (1O2) forms upon oxidizing Li2CO3 in an aprotic electrolyte and therefore does not evolve as O2. These results have substantial implications for the long‐term cyclability of batteries: they underpin the importance of avoiding 1O2 in metal‐O2 batteries, question the possibility of a reversible metal‐O2/CO2 battery based on a carbonate discharge product, and help explain the interfacial reactivity of transition‐metal cathodes with residual Li2CO3. AU - Mahne, Nika AU - Renfrew, Sara E. AU - McCloskey, Bryan D. AU - Freunberger, Stefan Alexander ID - 7277 IS - 19 JF - Angewandte Chemie International Edition SN - 1433-7851 TI - Electrochemical oxidation of Lithium Carbonate generates singlet oxygen VL - 57 ER - TY - JOUR AB - Passivation layers on electrode materials are ubiquitous in nonaqueous battery chemistries and strongly govern performance and lifetime. They comprise breakdown products of the electrolyte including carbonate, alkyl carbonates, alkoxides, carboxylates, and polymers. Parasitic chemistry in metal–O2 batteries forms similar products and is tied to the deviation of the O2 balance from the ideal stoichiometry during formation/decomposition of alkaline peroxides or superoxides. Accurate and integral quantification of carbonaceous species and peroxides or superoxides in battery electrodes remains, however, elusive. We present a refined procedure to quantify them accurately and sensitively by pointing out and rectifying pitfalls of previous procedures. Carbonaceous compounds are differentiated into inorganic and organic ones. We combine mass and UV–vis spectrometry to quantify evolved O2 and complexed peroxide and CO2 evolved from carbonaceous compounds by acid treatment and Fenton’s reaction. The capabilities of the method are exemplified by means of Li–O2 and Na–O2 cathodes, graphite anodes, and LiNi0.8Co0.15Al0.05O2 cathodes. AU - Schafzahl, Bettina AU - Mourad, Eléonore AU - Schafzahl, Lukas AU - Petit, Yann K. AU - Raju, Anjana R. AU - Thotiyl, Musthafa Ottakam AU - Wilkening, Martin AU - Slugovc, Christian AU - Freunberger, Stefan Alexander ID - 7287 IS - 1 JF - ACS Energy Letters SN - 2380-8195 TI - Quantifying total superoxide, peroxide, and carbonaceous compounds in metal–O2 batteries and the solid electrolyte interphase VL - 3 ER - TY - JOUR AB - Hydrogelation, the self-assembly of molecules into soft, water-loaded networks, is one way to bridge the structural gap between single molecules and functional materials. The potential of hydrogels, such as those based on perylene bisimides, lies in their chemical, physical, optical, and electronic properties, which are governed by the supramolecular structure of the gel. However, the structural motifs and their precise role for long-range conductivity are yet to be explored. Here, we present a comprehensive structural picture of a perylene bisimide hydrogel, suggesting that its long-range conductivity is limited by charge transfer between electronic backbones. We reveal nanocrystalline ribbon-like structures as the electronic and structural backbone units between which charge transfer is mediated by polar solvent bridges. We exemplify this effect with sensing, where exposure to polar vapor enhances conductivity by 5 orders of magnitude, emphasizing the crucial role of the interplay between structural motif and surrounding medium for the rational design of devices based on nanocrystalline hydrogels. AU - Burian, Max AU - Rigodanza, Francesco AU - Demitri, Nicola AU - D̵ord̵ević, Luka AU - Marchesan, Silvia AU - Steinhartova, Tereza AU - Letofsky-Papst, Ilse AU - Khalakhan, Ivan AU - Mourad, Eléonore AU - Freunberger, Stefan Alexander AU - Amenitsch, Heinz AU - Prato, Maurizio AU - Syrgiannis, Zois ID - 7285 IS - 6 JF - ACS Nano SN - 1936-0851 TI - Inter-backbone charge transfer as prerequisite for long-range conductivity in perylene bisimide hydrogels VL - 12 ER - TY - CONF AB - Proofs of space (PoS) [Dziembowski et al., CRYPTO'15] are proof systems where a prover can convince a verifier that he "wastes" disk space. PoS were introduced as a more ecological and economical replacement for proofs of work which are currently used to secure blockchains like Bitcoin. In this work we investigate extensions of PoS which allow the prover to embed useful data into the dedicated space, which later can be recovered. Our first contribution is a security proof for the original PoS from CRYPTO'15 in the random oracle model (the original proof only applied to a restricted class of adversaries which can store a subset of the data an honest prover would store). When this PoS is instantiated with recent constructions of maximally depth robust graphs, our proof implies basically optimal security. As a second contribution we show three different extensions of this PoS where useful data can be embedded into the space required by the prover. Our security proof for the PoS extends (non-trivially) to these constructions. We discuss how some of these variants can be used as proofs of catalytic space (PoCS), a notion we put forward in this work, and which basically is a PoS where most of the space required by the prover can be used to backup useful data. Finally we discuss how one of the extensions is a candidate construction for a proof of replication (PoR), a proof system recently suggested in the Filecoin whitepaper. AU - Pietrzak, Krzysztof Z ID - 7407 SN - 1868-8969 T2 - 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) TI - Proofs of catalytic space VL - 124 ER - TY - JOUR AB - Background: DNA methylation levels change along with age, but few studies have examined the variation in the rate of such changes between individuals. Methods: We performed a longitudinal analysis to quantify the variation in the rate of change of DNA methylation between individuals using whole blood DNA methylation array profiles collected at 2–4 time points (N = 2894) in 954 individuals (67–90 years). Results: After stringent quality control, we identified 1507 DNA methylation CpG sites (rsCpGs) with statistically significant variation in the rate of change (random slope) of DNA methylation among individuals in a mixed linear model analysis. Genes in the vicinity of these rsCpGs were found to be enriched in Homeobox transcription factors and the Wnt signalling pathway, both of which are related to ageing processes. Furthermore, we investigated the SNP effect on the random slope. We found that 4 out of 1507 rsCpGs had one significant (P < 5 × 10−8/1507) SNP effect and 343 rsCpGs had at least one SNP effect (436 SNP-probe pairs) reaching genome-wide significance (P < 5 × 10−8). Ninety-five percent of the significant (P < 5 × 10−8) SNPs are on different chromosomes from their corresponding probes. Conclusions: We identified CpG sites that have variability in the rate of change of DNA methylation between individuals, and our results suggest a genetic basis of this variation. Genes around these CpG sites have been reported to be involved in the ageing process. AU - Zhang, Qian AU - Marioni, Riccardo E AU - Robinson, Matthew Richard AU - Higham, Jon AU - Sproul, Duncan AU - Wray, Naomi R AU - Deary, Ian J AU - McRae, Allan F AU - Visscher, Peter M ID - 7717 IS - 1 JF - Genome Medicine SN - 1756-994X TI - Genotype effects contribute to variation in longitudinal methylome patterns in older people VL - 10 ER - TY - JOUR AB - Male pattern baldness (MPB) is a sex-limited, age-related, complex trait. We study MPB genetics in 205,327 European males from the UK Biobank. Here we show that MPB is strongly heritable and polygenic, with pedigree-heritability of 0.62 (SE = 0.03) estimated from close relatives, and SNP-heritability of 0.39 (SE = 0.01) from conventionally-unrelated males. We detect 624 near-independent genome-wide loci, contributing SNP-heritability of 0.25 (SE = 0.01), of which 26 X-chromosome loci explain 11.6%. Autosomal genetic variance is enriched for common variants and regions of lower linkage disequilibrium. We identify plausible genetic correlations between MPB and multiple sex-limited markers of earlier puberty, increased bone mineral density (rg = 0.15) and pancreatic β-cell function (rg = 0.12). Correlations with reproductive traits imply an effect on fitness, consistent with an estimated linear selection gradient of -0.018 per MPB standard deviation. Overall, we provide genetic insights into MPB: a phenotype of interest in its own right, with value as a model sex-limited, complex trait. AU - Yap, Chloe X. AU - Sidorenko, Julia AU - Wu, Yang AU - Kemper, Kathryn E. AU - Yang, Jian AU - Wray, Naomi R. AU - Robinson, Matthew Richard AU - Visscher, Peter M. ID - 7712 JF - Nature Communications SN - 2041-1723 TI - Dissection of genetic variation and evidence for pleiotropy in male pattern baldness VL - 9 ER - TY - JOUR AB - Genomic prediction has the potential to contribute to precision medicine. However, to date, the utility of such predictors is limited due to low accuracy for most traits. Here theory and simulation study are used to demonstrate that widespread pleiotropy among phenotypes can be utilised to improve genomic risk prediction. We show how a genetic predictor can be created as a weighted index that combines published genome-wide association study (GWAS) summary statistics across many different traits. We apply this framework to predict risk of schizophrenia and bipolar disorder in the Psychiatric Genomics consortium data, finding substantial heterogeneity in prediction accuracy increases across cohorts. For six additional phenotypes in the UK Biobank data, we find increases in prediction accuracy ranging from 0.7% for height to 47% for type 2 diabetes, when using a multi-trait predictor that combines published summary statistics from multiple traits, as compared to a predictor based only on one trait. AU - Maier, Robert M. AU - Zhu, Zhihong AU - Lee, Sang Hong AU - Trzaskowski, Maciej AU - Ruderfer, Douglas M. AU - Stahl, Eli A. AU - Ripke, Stephan AU - Wray, Naomi R. AU - Yang, Jian AU - Visscher, Peter M. AU - Robinson, Matthew Richard ID - 7716 JF - Nature Communications SN - 2041-1723 TI - Improving genetic prediction by leveraging genetic correlations among human diseases and traits VL - 9 ER - TY - JOUR AB - Health risk factors such as body mass index (BMI) and serum cholesterol are associated with many common diseases. It often remains unclear whether the risk factors are cause or consequence of disease, or whether the associations are the result of confounding. We develop and apply a method (called GSMR) that performs a multi-SNP Mendelian randomization analysis using summary-level data from genome-wide association studies to test the causal associations of BMI, waist-to-hip ratio, serum cholesterols, blood pressures, height, and years of schooling (EduYears) with common diseases (sample sizes of up to 405,072). We identify a number of causal associations including a protective effect of LDL-cholesterol against type-2 diabetes (T2D) that might explain the side effects of statins on T2D, a protective effect of EduYears against Alzheimer’s disease, and bidirectional associations with opposite effects (e.g., higher BMI increases the risk of T2D but the effect of T2D on BMI is negative). AU - Zhu, Zhihong AU - Zheng, Zhili AU - Zhang, Futao AU - Wu, Yang AU - Trzaskowski, Maciej AU - Maier, Robert AU - Robinson, Matthew Richard AU - McGrath, John J. AU - Visscher, Peter M. AU - Wray, Naomi R. AU - Yang, Jian ID - 7714 JF - Nature Communications SN - 2041-1723 TI - Causal associations between risk factors and common diseases inferred from GWAS summary data VL - 9 ER - TY - JOUR AB - There are mean differences in complex traits among global human populations. We hypothesize that part of the phenotypic differentiation is due to natural selection. To address this hypothesis, we assess the differentiation in allele frequencies of trait-associated SNPs among African, Eastern Asian, and European populations for ten complex traits using data of large sample size (up to ~405,000). We show that SNPs associated with height (P=2.46×10−5), waist-to-hip ratio (P=2.77×10−4), and schizophrenia (P=3.96×10−5) are significantly more differentiated among populations than matched “control” SNPs, suggesting that these trait-associated SNPs have undergone natural selection. We further find that SNPs associated with height (P=2.01×10−6) and schizophrenia (P=5.16×10−18) show significantly higher variance in linkage disequilibrium (LD) scores across populations than control SNPs. Our results support the hypothesis that natural selection has shaped the genetic differentiation of complex traits, such as height and schizophrenia, among worldwide populations. AU - Guo, Jing AU - Wu, Yang AU - Zhu, Zhihong AU - Zheng, Zhili AU - Trzaskowski, Maciej AU - Zeng, Jian AU - Robinson, Matthew Richard AU - Visscher, Peter M. AU - Yang, Jian ID - 7713 JF - Nature Communications SN - 2041-1723 TI - Global genetic differentiation of complex traits shaped by natural selection in humans VL - 9 ER - TY - JOUR AB - The availability of genome-wide genetic data on hundreds of thousands of people has led to an equally rapid growth in methodologies available to analyse these data. While the motivation for undertaking genome-wide association studies (GWAS) is identification of genetic markers associated with complex traits, once generated these data can be used for many other analyses. GWAS have demonstrated that complex traits exhibit a highly polygenic genetic architecture, often with shared genetic risk factors across traits. New methods to analyse data from GWAS are increasingly being used to address a diverse set of questions about the aetiology of complex traits and diseases, including psychiatric disorders. Here, we give an overview of some of these methods and present examples of how they have contributed to our understanding of psychiatric disorders. We consider: (i) estimation of the extent of genetic influence on traits, (ii) uncovering of shared genetic control between traits, (iii) predictions of genetic risk for individuals, (iv) uncovering of causal relationships between traits, (v) identifying causal single-nucleotide polymorphisms and genes or (vi) the detection of genetic heterogeneity. This classification helps organise the large number of recently developed methods, although some could be placed in more than one category. While some methods require GWAS data on individual people, others simply use GWAS summary statistics data, allowing novel well-powered analyses to be conducted at a low computational burden. AU - Maier, R. M. AU - Visscher, P. M. AU - Robinson, Matthew Richard AU - Wray, N. R. ID - 7721 IS - 7 JF - Psychological Medicine SN - 0033-2917 TI - Embracing polygenicity: A review of methods and tools for psychiatric genetics research VL - 48 ER - TY - JOUR AB - Creating a selective gel that filters particles based on their interactions is a major goal of nanotechnology, with far-reaching implications from drug delivery to controlling assembly pathways. However, this is particularly difficult when the particles are larger than the gel’s characteristic mesh size because such particles cannot passively pass through the gel. Thus, filtering requires the interacting particles to transiently reorganize the gel’s internal structure. While significant advances, e.g., in DNA engineering, have enabled the design of nano-materials with programmable interactions, it is not clear what physical principles such a designer gel could exploit to achieve selective permeability. We present an equilibrium mechanism where crosslink binding dynamics are affected by interacting particles such that particle diffusion is enhanced. In addition to revealing specific design rules for manufacturing selective gels, our results have the potential to explain the origin of selective permeability in certain biological materials, including the nuclear pore complex. AU - Goodrich, Carl Peter AU - Brenner, Michael P. AU - Ribbeck, Katharina ID - 7754 JF - Nature Communications SN - 2041-1723 TI - Enhanced diffusion by binding to the crosslinks of a polymer gel VL - 9 ER - TY - GEN AB - The Drosophila Genetic Reference Panel (DGRP) serves as a valuable resource to better understand the genetic landscapes underlying quantitative traits. However, such DGRP studies have so far only focused on nuclear genetic variants. To address this, we sequenced the mitochondrial genomes of >170 DGRP lines, identifying 229 variants including 21 indels and 7 frameshifts. We used our mitochondrial variation data to identify 12 genetically distinct mitochondrial haplotypes, thus revealing important population structure at the mitochondrial level. We further examined whether this population structure was reflected on the nuclear genome by screening for the presence of potential mito-nuclear genetic incompatibilities in the form of significant genotype ratio distortions (GRDs) between mitochondrial and nuclear variants. In total, we detected a remarkable 1,845 mito-nuclear GRDs, with the highest enrichment observed in a 40 kb region around the gene Sex-lethal (Sxl). Intriguingly, downstream phenotypic analyses did not uncover major fitness effects associated with these GRDs, suggesting that a large number of mito-nuclear GRDs may reflect population structure at the mitochondrial level rather than actual genomic incompatibilities. This is further supported by the GRD landscape showing particular large genomic regions associated with a single mitochondrial haplotype. Next, we explored the functional relevance of the detected mitochondrial haplotypes through an association analysis on a set of 259 assembled, non-correlating DGRP phenotypes. We found multiple significant associations with stress- and metabolism-related phenotypes, including food intake in males. We validated the latter observation by reciprocal swapping of mitochondrial genomes from high food intake DGRP lines to low food intake ones. In conclusion, our study uncovered important mitochondrial population structure and haplotype-specific metabolic variation in the DGRP, thus demonstrating the significance of incorporating mitochondrial haplotypes in geno-phenotype relationship studies. AU - Bevers, Roel P.J. AU - Litovchenko, Maria AU - Kapopoulou, Adamandia AU - Braman, Virginie S. AU - Robinson, Matthew Richard AU - Auwerx, Johan AU - Hollis, Brian AU - Deplancke, Bart ID - 7783 T2 - bioRxiv TI - Extensive mitochondrial population structure and haplotype-specific phenotypic variation in the Drosophila Genetic Reference Panel ER - TY - CONF AB - Deep neural networks (DNNs) continue to make significant advances, solving tasks from image classification to translation or reinforcement learning. One aspect of the field receiving considerable attention is efficiently executing deep models in resource-constrained environments, such as mobile or embedded devices. This paper focuses on this problem, and proposes two new compression methods, which jointly leverage weight quantization and distillation of larger teacher networks into smaller student networks. The first method we propose is called quantized distillation and leverages distillation during the training process, by incorporating distillation loss, expressed with respect to the teacher, into the training of a student network whose weights are quantized to a limited set of levels. The second method, differentiable quantization, optimizes the location of quantization points through stochastic gradient descent, to better fit the behavior of the teacher model. We validate both methods through experiments on convolutional and recurrent architectures. We show that quantized shallow students can reach similar accuracy levels to full-precision teacher models, while providing order of magnitude compression, and inference speedup that is linear in the depth reduction. In sum, our results enable DNNs for resource-constrained environments to leverage architecture and accuracy advances developed on more powerful devices. AU - Polino, Antonio AU - Pascanu, Razvan AU - Alistarh, Dan-Adrian ID - 7812 T2 - 6th International Conference on Learning Representations TI - Model compression via distillation and quantization ER - TY - JOUR AB - Feste Alkalicarbonate sind universelle Bestandteile von Passivierungsschichten an Materialien für Interkalationsbatterien, übliche Nebenprodukte in Metall‐O2‐Batterien, und es wird angenommen, dass sie sich reversibel in Metall‐O2 /CO2‐Zellen bilden und zersetzen. In all diesen Kathoden zersetzt sich Li2CO3 zu CO2, sobald es Spannungen >3.8 V vs. Li/Li+ ausgesetzt wird. Beachtenswert ist, dass keine O2‐Entwicklung detektiert wird, wie gemäß der Zersetzungsreaktion 2 Li2CO3 → 4 Li+ + 4 e− + 2 CO2 + O2 zu erwarten wäre. Deswegen war der Verbleib eines der O‐Atome ungeklärt und wurde nicht identifizierten parasitären Reaktionen zugerechnet. Hier zeigen wir, dass hochreaktiver Singulett‐Sauerstoff (1O2) bei der Oxidation von Li2CO3 in einem aprotischen Elektrolyten gebildet und daher nicht als O2 freigesetzt wird. Diese Ergebnisse haben weitreichende Auswirkungen auf die langfristige Zyklisierbarkeit von Batterien: sie untermauern die Wichtigkeit, 1O2 in Metall‐O2‐Batterien zu verhindern, stellen die Möglichkeit einer reversiblen Metall‐O2 /CO2‐Batterie basierend auf einem Carbonat‐Entladeprodukt in Frage und helfen, Grenzflächenreaktivität von Übergangsmetallkathoden mit Li2CO3‐Resten zu erklären. AU - Mahne, Nika AU - Renfrew, Sara E. AU - McCloskey, Bryan D. AU - Freunberger, Stefan Alexander ID - 7983 IS - 19 JF - Angewandte Chemie SN - 0044-8249 TI - Elektrochemische Oxidation von Lithiumcarbonat generiert Singulett-Sauerstoff VL - 130 ER - TY - JOUR AB - The neural code of cortical processing remains uncracked; however, it must necessarily rely on faithful signal propagation between cortical areas. In this issue of Neuron, Joglekar et al. (2018) show that strong inter-areal excitation balanced by local inhibition can enable reliable signal propagation in data-constrained network models of macaque cortex. AU - Stroud, Jake P. AU - Vogels, Tim P ID - 8015 IS - 1 JF - Neuron SN - 0896-6273 TI - Cortical signal propagation: Balance, amplify, transmit VL - 98 ER - TY - JOUR AB - Motor cortex (M1) exhibits a rich repertoire of neuronal activities to support the generation of complex movements. Although recent neuronal-network models capture many qualitative aspects of M1 dynamics, they can generate only a few distinct movements. Additionally, it is unclear how M1 efficiently controls movements over a wide range of shapes and speeds. We demonstrate that modulation of neuronal input–output gains in recurrent neuronal-network models with a fixed architecture can dramatically reorganize neuronal activity and thus downstream muscle outputs. Consistent with the observation of diffuse neuromodulatory projections to M1, a relatively small number of modulatory control units provide sufficient flexibility to adjust high-dimensional network activity using a simple reward-based learning rule. Furthermore, it is possible to assemble novel movements from previously learned primitives, and one can separately change movement speed while preserving movement shape. Our results provide a new perspective on the role of modulatory systems in controlling recurrent cortical activity. AU - Stroud, Jake P. AU - Porter, Mason A. AU - Hennequin, Guillaume AU - Vogels, Tim P ID - 8073 IS - 12 JF - Nature Neuroscience SN - 1097-6256 TI - Motor primitives in space and time via targeted gain modulation in cortical networks VL - 21 ER - TY - JOUR AU - Fazekas-Singer, Judit AU - Singer, Josef AU - Ilieva, Kristina M. AU - Matz, Miroslawa AU - Herrmann, Ina AU - Spillner, Edzard AU - Karagiannis, Sophia N. AU - Jensen-Jarolim, Erika ID - 8231 IS - 3 JF - Journal of Allergy and Clinical Immunology SN - 0091-6749 TI - AllergoOncology: Generating a canine anticancer IgE against the epidermal growth factor receptor VL - 142 ER - TY - JOUR AB - Molecular imaging probes such as PET-tracers have the potential to improve the accuracy of tumor characterization by directly visualizing the biochemical situation. Thus, molecular changes can be detected early before morphological manifestation. The A3 adenosine receptor (A3AR) is described to be highly expressed in colon cancer cell lines and human colorectal cancer (CRC), suggesting this receptor as a tumor marker. The aim of this preclinical study was the evaluation of FE@SUPPY as a PET-tracer for CRC using in vitro imaging and in vivo PET imaging. First, affinity and selectivity of FE@SUPPY and its metabolites were determined, proving the favorable binding profile of FE@SUPPY. The human adenocarcinoma cell line HT-29 was characterized regarding its hA3AR expression and was subsequently chosen as tumor graft. Promising results regarding the potential of FE@SUPPY as a PET-tracer for CRC imaging were obtained by autoradiography as ≥2.3-fold higher accumulation of FE@SUPPY was found in CRC tissue compared to adjacent healthy colon tissue from the same patient. Nevertheless, first in vivo studies using HT-29 xenografts showed insufficient tumor uptake due to (1) poor conservation of target expression in xenografts and (2) unfavorable pharmacokinetics of FE@SUPPY in mice. We therefore conclude that HT-29 xenografts are not adequate to visualize hA3ARs using FE@SUPPY. AU - Balber, T. AU - Singer, Judit AU - Berroterán-Infante, N. AU - Dumanic, M. AU - Fetty, L. AU - Fazekas-Singer, J. AU - Vraka, C. AU - Nics, L. AU - Bergmann, M. AU - Pallitsch, K. AU - Spreitzer, H. AU - Wadsak, W. AU - Hacker, M. AU - Jensen-Jarolim, E. AU - Viernstein, H. AU - Mitterhauser, M. ID - 8234 JF - Contrast Media & Molecular Imaging SN - 1555-4309 TI - Preclinical in vitro and in vivo evaluation of [18F]FE@SUPPY for cancer PET imaging: Limitations of a xenograft model for colorectal cancer VL - 2018 ER - TY - JOUR AB - Anti-epidermal growth factor receptor (EGFR) antibody therapy is used in EGFR expressing cancers including lung, colon, head and neck, and bladder cancers, however results have been modest. Near infrared photoimmunotherapy (NIR-PIT) is a highly selective tumor treatment that employs an antibody-photo-absorber conjugate which is activated by NIR light. NIR-PIT is in clinical trials in patients with recurrent head and neck cancers using cetuximab-IR700 as the conjugate. However, its use has otherwise been restricted to mouse models. This is an effort to explore larger animal models with NIR-PIT. We describe the use of a recombinant canine anti-EGFR monoclonal antibody (mAb), can225IgG, conjugated to the photo-absorber, IR700DX, in three EGFR expressing canine transitional cell carcinoma (TCC) cell lines as a prelude to possible canine clinical studies. Can225-IR700 conjugate showed specific binding and cell-specific killing after NIR-PIT on EGFR expressing cells in vitro. In the in vivo study, can225-IR700 conjugate demonstrated accumulation of the fluorescent conjugate with high tumor-to-background ratio. Tumor-bearing mice were separated into 4 groups: (1) no treatment; (2) 100 μg of can225-IR700 i.v. only; (3) NIR light exposure only; (4) 100 μg of can225-IR700 i.v., NIR light exposure. Tumor growth was significantly inhibited by NIR-PIT treatment compared with the other groups (p < 0.001), and significantly prolonged survival was achieved (p < 0.001 vs. other groups) in the treatment groups. In conclusion, NIR-PIT with can225-IR700 is a promising treatment for canine EGFR-expressing cancers, including invasive transitional cell carcinoma in pet dogs, that could provide a pathway to translation to humans. AU - Nagaya, Tadanobu AU - Okuyama, Shuhei AU - Ogata, Fusa AU - Maruoka, Yasuhiro AU - Knapp, Deborah W. AU - Karagiannis, Sophia N. AU - Fazekas-Singer, Judit AU - Choyke, Peter L. AU - LeBlanc, Amy K. AU - Jensen-Jarolim, Erika AU - Kobayashi, Hisataka ID - 8232 JF - Oncotarget TI - Near infrared photoimmunotherapy targeting bladder cancer with a canine anti-epidermal growth factor receptor (EGFR) antibody VL - 9 ER - TY - JOUR AB - The M2a subtype of macrophages plays an important role in human immunoglobulin E (IgE-mediated allergies) and other Th2 type immune reactions. In contrast, very little is known about these cells in the dog. Here we describe an in vitro method to activate canine histiocytic DH82 cells and primary canine monocyte-derived macrophages (MDMs) toward the M2a macrophages using human cytokines. For a side-by-side comparison, we compared the canine cells to human MDMs, and the human monocytic cell line U937 activated towards M1 and M2a cells on the cellular and molecular level. In analogy to activated human M2a cells, canine M2a, differentiated from both DH82 and MDMs, showed an increase in CD206 surface receptor expression compared to M1. Interestingly, canine M2a, but not M1 derived from MDM, upregulated the high-affinity IgE receptor (FcεRI). Transcription levels of M2a-associated genes (IL10, CCL22, TGFβ, CD163) showed a diverse pattern between the human and dog species, whereas M1 genes (IDO1, CXCL11, IL6, TNF-α) were similarly upregulated in canine and human M1 cells (cell lines and MDMs). We suggest that our novel in vitro method will be suitable in comparative allergology studies focussing on macrophages. AU - Herrmann, Ina AU - Gotovina, Jelena AU - Fazekas-Singer, Judit AU - Fischer, Michael B. AU - Hufnagl, Karin AU - Bianchini, Rodolfo AU - Jensen-Jarolim, Erika ID - 8233 IS - 5 JF - Developmental & Comparative Immunology SN - 0145-305X TI - Canine macrophages can like human macrophages be in vitro activated toward the M2a subtype relevant in allergy VL - 82 ER - TY - JOUR AB - Background: The genus Burkholderia consists of species that occupy remarkably diverse ecological niches. Its best known members are important pathogens, B. mallei and B. pseudomallei, which cause glanders and melioidosis, respectively. Burkholderia genomes are unusual due to their multichromosomal organization, generally comprised of 2-3 chromosomes. Results: We performed integrated genomic analysis of 127 Burkholderia strains. The pan-genome is open with the saturation to be reached between 86,000 and 88,000 genes. The reconstructed rearrangements indicate a strong avoidance of intra-replichore inversions that is likely caused by selection against the transfer of large groups of genes between the leading and the lagging strands. Translocated genes also tend to retain their position in the leading or the lagging strand, and this selection is stronger for large syntenies. Integrated reconstruction of chromosome rearrangements in the context of strains phylogeny reveals parallel rearrangements that may indicate inversion-based phase variation and integration of new genomic islands. In particular, we detected parallel inversions in the second chromosomes of B. pseudomallei with breakpoints formed by genes encoding membrane components of multidrug resistance complex, that may be linked to a phase variation mechanism. Two genomic islands, spreading horizontally between chromosomes, were detected in the B. cepacia group. Conclusions: This study demonstrates the power of integrated analysis of pan-genomes, chromosome rearrangements, and selection regimes. Non-random inversion patterns indicate selective pressure, inversions are particularly frequent in a recent pathogen B. mallei, and, together with periods of positive selection at other branches, may indicate adaptation to new niches. One such adaptation could be a possible phase variation mechanism in B. pseudomallei. AU - Bochkareva, Olga AU - Moroz, Elena V. AU - Davydov, Iakov I. AU - Gelfand, Mikhail S. ID - 8262 JF - BMC Genomics SN - 1471-2164 TI - Genome rearrangements and selection in multi-chromosome bacteria Burkholderia spp. VL - 19 ER - TY - JOUR AB - Genome rearrangements have played an important role in the evolution of Yersinia pestis from its progenitor Yersinia pseudotuberculosis. Traditional phylogenetic trees for Y. pestis based on sequence comparison have short internal branches and low bootstrap supports as only a small number of nucleotide substitutions have occurred. On the other hand, even a small number of genome rearrangements may resolve topological ambiguities in a phylogenetic tree. We reconstructed phylogenetic trees based on genome rearrangements using several popular approaches such as Maximum likelihood for Gene Order and the Bayesian model of genome rearrangements by inversions. We also reconciled phylogenetic trees for each of the three CRISPR loci to obtain an integrated scenario of the CRISPR cassette evolution. Analysis of contradictions between the obtained evolutionary trees yielded numerous parallel inversions and gain/loss events. Our data indicate that an integrated analysis of sequence-based and inversion-based trees enhances the resolution of phylogenetic reconstruction. In contrast, reconstructions of strain relationships based on solely CRISPR loci may not be reliable, as the history is obscured by large deletions, obliterating the order of spacer gains. Similarly, numerous parallel gene losses preclude reconstruction of phylogeny based on gene content. AU - Bochkareva, Olga AU - Dranenko, Natalia O. AU - Ocheredko, Elena S. AU - Kanevsky, German M. AU - Lozinsky, Yaroslav N. AU - Khalaycheva, Vera A. AU - Artamonova, Irena I. AU - Gelfand, Mikhail S. ID - 8265 JF - PeerJ SN - 2167-8359 TI - Genome rearrangements and phylogeny reconstruction in Yersinia pestis VL - 6 ER - TY - CONF AB - Designing a secure permissionless distributed ledger (blockchain) that performs on par with centralized payment processors, such as Visa, is a challenging task. Most existing distributed ledgers are unable to scale-out, i.e., to grow their totalprocessing capacity with the number of validators; and those that do, compromise security or decentralization. We present OmniLedger, a novel scale-out distributed ledger that preserves longterm security under permissionless operation. It ensures security and correctness by using a bias-resistant public-randomness protocol for choosing large, statistically representative shards that process transactions, and by introducing an efficient crossshard commit protocol that atomically handles transactions affecting multiple shards. OmniLedger also optimizes performance via parallel intra-shard transaction processing, ledger pruning via collectively-signed state blocks, and low-latency “trust-butverify” validation for low-value transactions. An evaluation ofour experimental prototype shows that OmniLedger’s throughput scales linearly in the number of active validators, supporting Visa-level workloads and beyond, while confirming typical transactions in under two seconds. AU - Kokoris Kogias, Eleftherios AU - Jovanovic, Philipp AU - Gasser, Linus AU - Gailly, Nicolas AU - Syta, Ewa AU - Ford, Bryan ID - 8297 SN - 2375-1207 T2 - 2018 IEEE Symposium on Security and Privacy TI - OmniLedger: A secure, scale-out, decentralized ledger via sharding ER - TY - GEN AB - The cerebral cortex contains multiple hierarchically organized areas with distinctive cytoarchitectonical patterns, but the cellular mechanisms underlying the emergence of this diversity remain unclear. Here, we have quantitatively investigated the neuronal output of individual progenitor cells in the ventricular zone of the developing mouse neocortex using a combination of methods that together circumvent the biases and limitations of individual approaches. We found that individual cortical progenitor cells show a high degree of stochasticity and generate pyramidal cell lineages that adopt a wide range of laminar configurations. Mathematical modelling these lineage data suggests that a small number of progenitor cell populations, each generating pyramidal cells following different stochastic developmental programs, suffice to generate the heterogenous complement of pyramidal cell lineages that collectively build the complex cytoarchitecture of the neocortex. AU - Llorca, Alfredo AU - Ciceri, Gabriele AU - Beattie, Robert J AU - Wong, Fong K. AU - Diana, Giovanni AU - Serafeimidou, Eleni AU - Fernández-Otero, Marian AU - Streicher, Carmen AU - Arnold, Sebastian J. AU - Meyer, Martin AU - Hippenmeyer, Simon AU - Maravall, Miguel AU - Marín, Oscar ID - 8547 T2 - bioRxiv TI - Heterogeneous progenitor cell behaviors underlie the assembly of neocortical cytoarchitecture ER - TY - CHAP AB - Responsiveness—the requirement that every request to a system be eventually handled—is one of the fundamental liveness properties of a reactive system. Average response time is a quantitative measure for the responsiveness requirement used commonly in performance evaluation. We show how average response time can be computed on state-transition graphs, on Markov chains, and on game graphs. In all three cases, we give polynomial-time algorithms. AU - Chatterjee, Krishnendu AU - Henzinger, Thomas A AU - Otop, Jan ED - Lohstroh, Marten ED - Derler, Patricia ED - Sirjani, Marjan ID - 86 T2 - Principles of Modeling TI - Computing average response time VL - 10760 ER - TY - JOUR AB - Self-assembly is the autonomous organization of components into patterns or structures: an essential ingredient of biology and a desired route to complex organization1. At equilibrium, the structure is encoded through specific interactions2,3,4,5,6,7,8, at an unfavourable entropic cost for the system. An alternative approach, widely used by nature, uses energy input to bypass the entropy bottleneck and develop features otherwise impossible at equilibrium9. Dissipative building blocks that inject energy locally were made available by recent advances in colloidal science10,11 but have not been used to control self-assembly. Here we show the targeted formation of self-powered microgears from active particles and their autonomous synchronization into dynamical superstructures. We use a photoactive component that consumes fuel, haematite, to devise phototactic microswimmers that form self-spinning microgears following spatiotemporal light patterns. The gears are coupled via their chemical clouds by diffusiophoresis12 and constitute the elementary bricks of synchronized superstructures, which autonomously regulate their dynamics. The results are quantitatively rationalized on the basis of a stochastic description of diffusio-phoretic oscillators dynamically coupled by chemical gradients. Our findings harness non-equilibrium phoretic phenomena to program interactions and direct self-assembly with fidelity and specificity. It lays the groundwork for the autonomous construction of dynamical architectures and functional micro-machinery. AU - Aubret, Antoine AU - Youssef, Mena AU - Sacanna, Stefano AU - Palacci, Jérémie A ID - 9062 IS - 11 JF - Nature Physics SN - 1745-2473 TI - Targeted assembly and synchronization of self-spinning microgears VL - 14 ER - TY - JOUR AU - Danzl, Johann G ID - 9229 IS - S1 JF - Opera Medica et Physiologica SN - 2500-2287 TI - Diffraction-unlimited optical imaging for synaptic physiology VL - 4 ER - TY - CONF AB - Network games are widely used as a model for selfish resource-allocation problems. In the classicalmodel, each player selects a path connecting her source and target vertices. The cost of traversingan edge depends on theload; namely, number of players that traverse it. Thus, it abstracts the factthat different users may use a resource at different times and for different durations, which playsan important role in determining the costs of the users in reality. For example, when transmittingpackets in a communication network, routing traffic in a road network, or processing a task in aproduction system, actual sharing and congestion of resources crucially depends on time.In [13], we introducedtimed network games, which add a time component to network games.Each vertexvin the network is associated with a cost function, mapping the load onvto theprice that a player pays for staying invfor one time unit with this load. Each edge in thenetwork is guarded by the time intervals in which it can be traversed, which forces the players tospend time in the vertices. In this work we significantly extend the way time can be referred toin timed network games. In the model we study, the network is equipped withclocks, and, as intimed automata, edges are guarded by constraints on the values of the clocks, and their traversalmay involve a reset of some clocks. We argue that the stronger model captures many realisticnetworks. The addition of clocks breaks the techniques we developed in [13] and we developnew techniques in order to show that positive results on classic network games carry over to thestronger timed setting. AU - Avni, Guy AU - Guha, Shibashis AU - Kupferman, Orna ID - 6005 SN - 1868-8969 TI - Timed network games with clocks VL - 117 ER - TY - JOUR AB - Estimating the homogeneous ice nucleation rate from undercooled liquid water is crucial for understanding many important physical phenomena and technological applications, and challenging for both experiments and theory. From a theoretical point of view, difficulties arise due to the long time scales required, as well as the numerous nucleation pathways involved to form ice nuclei with different stacking disorders. We computed the homogeneous ice nucleation rate at a physically relevant undercooling for a single-site water model, taking into account the diffuse nature of ice–water interfaces, stacking disorders in ice nuclei, and the addition rate of particles to the critical nucleus. We disentangled and investigated the relative importance of all the terms, including interfacial free energy, entropic contributions and the kinetic prefactor, that contribute to the overall nucleation rate. Breaking down the problem into pieces not only provides physical insights into ice nucleation, but also sheds light on the long-standing discrepancy between different theoretical predictions, as well as between theoretical and experimental determinations of the nucleation rate. Moreover, we pinpoint the main shortcomings and suggest strategies to systematically improve the existing simulation methods. AU - Cheng, Bingqing AU - Dellago, Christoph AU - Ceriotti, Michele ID - 9668 IS - 45 JF - Physical Chemistry Chemical Physics SN - 1463-9076 TI - Theoretical prediction of the homogeneous ice nucleation rate: Disentangling thermodynamics and kinetics VL - 20 ER - TY - JOUR AB - The Gibbs free energy is the fundamental thermodynamic potential underlying the relative stability of different states of matter under constant-pressure conditions. However, computing this quantity from atomic-scale simulations is far from trivial, so the potential energy of a system is often used as a proxy. In this paper, we use a combination of thermodynamic integration methods to accurately evaluate the Gibbs free energies associated with defects in crystals, including the vacancy formation energy in bcc iron, and the stacking fault energy in fcc nickel, iron, and cobalt. We quantify the importance of entropic and anharmonic effects in determining the free energies of defects at high temperatures, and show that the potential energy approximation as well as the harmonic approximation may produce inaccurate or even qualitatively wrong results. Our calculations manifest the necessity to employ accurate free energy methods such as thermodynamic integration to estimate the stability of crystallographic defects at high temperatures. AU - Cheng, Bingqing AU - Ceriotti, Michele ID - 9687 IS - 5 JF - Physical Review B SN - 2469-9950 TI - Computing the absolute Gibbs free energy in atomistic simulations: Applications to defects in solids VL - 97 ER - TY - JOUR AB - More than 100 years after Grigg’s influential analysis of species’ borders, the causes of limits to species’ ranges still represent a puzzle that has never been understood with clarity. The topic has become especially important recently as many scientists have become interested in the potential for species’ ranges to shift in response to climate change—and yet nearly all of those studies fail to recognise or incorporate evolutionary genetics in a way that relates to theoretical developments. I show that range margins can be understood based on just two measurable parameters: (i) the fitness cost of dispersal—a measure of environmental heterogeneity—and (ii) the strength of genetic drift, which reduces genetic diversity. Together, these two parameters define an ‘expansion threshold’: adaptation fails when genetic drift reduces genetic diversity below that required for adaptation to a heterogeneous environment. When the key parameters drop below this expansion threshold locally, a sharp range margin forms. When they drop below this threshold throughout the species’ range, adaptation collapses everywhere, resulting in either extinction or formation of a fragmented metapopulation. Because the effects of dispersal differ fundamentally with dimension, the second parameter—the strength of genetic drift—is qualitatively different compared to a linear habitat. In two-dimensional habitats, genetic drift becomes effectively independent of selection. It decreases with ‘neighbourhood size’—the number of individuals accessible by dispersal within one generation. Moreover, in contrast to earlier predictions, which neglected evolution of genetic variance and/or stochasticity in two dimensions, dispersal into small marginal populations aids adaptation. This is because the reduction of both genetic and demographic stochasticity has a stronger effect than the cost of dispersal through increased maladaptation. The expansion threshold thus provides a novel, theoretically justified, and testable prediction for formation of the range margin and collapse of the species’ range. AU - Polechova, Jitka ID - 315 IS - 6 JF - PLoS Biology SN - 15449173 TI - Is the sky the limit? On the expansion threshold of a species’ range VL - 16 ER -