TY - JOUR AB - Partially filled Landau levels host competing electronic orders. For example, electron solids may prevail close to integer filling of the Landau levels before giving way to fractional quantum Hall liquids at higher carrier density1,2. Here, we report the observation of an electron solid with non-collinear spin texture in monolayer graphene, consistent with solidification of skyrmions3—topological spin textures characterized by quantized electrical charge4,5. We probe the spin texture of the solids using a modified Corbino geometry that allows ferromagnetic magnons to be launched and detected6,7. We find that magnon transport is highly efficient when one Landau level is filled (ν=1), consistent with quantum Hall ferromagnetic spin polarization. However, even minimal doping immediately quenches the magnon signal while leaving the vanishing low-temperature charge conductivity unchanged. Our results can be understood by the formation of a solid of charged skyrmions near ν=1, whose non-collinear spin texture leads to rapid magnon decay. Data near fractional fillings show evidence of several fractional skyrmion solids, suggesting that graphene hosts a highly tunable landscape of coupled spin and charge orders. AU - Zhou, H. AU - Polshyn, Hryhoriy AU - Taniguchi, T. AU - Watanabe, K. AU - Young, A. F. ID - 10620 IS - 2 JF - Nature Physics KW - General Physics and Astronomy SN - 1745-2473 TI - Solids of quantum Hall skyrmions in graphene VL - 16 ER - TY - JOUR AB - Since the discovery of correlated insulators and superconductivity in magic-angle twisted bilayer graphene (tBLG) ([1, 2], JCCM April 2018), theorists have been excitedly pursuing the alluring mix of band topology, symmetry breaking, Mott insulators and superconductivity at play, as well as the potential relation (if any) to high-Tc physics. Now a new stream of experimental work is arriving which further enriches the story. To briefly recap Episodes 1 and 2 (JCCM April and November 2018), when two graphene layers are stacked with a small rotational mismatch θ, the resulting long-wavelength moire pattern leads to a superlattice potential which reconstructs the low energy band structure. When θ approaches the “magic-angle” θM ∼ 1 ◦, the band structure features eight nearly-flat bands which fill when the electron number per moire unit cell, n/n0, lies between −4 < n/n0 < 4. The bands can be counted as 8 = 2 × 2 × 2: for each spin (2×) and valley (2×) characteristic of monolayergraphene, tBLG has has 2× flat bands which cross at mini-Dirac points. AU - Yankowitz, Mathew AU - Chen, Shaowen AU - Polshyn, Hryhoriy AU - Watanabe, K. AU - Taniguchi, T. AU - Graf, David AU - Young, Andrea F. AU - Dean, Cory R. AU - Sharpe, Aaron L. AU - Fox, E.J. AU - Barnard, A.W. AU - Finney, Joe ID - 10664 JF - Journal Club for Condensed Matter Physics TI - New correlated phenomena in magic-angle twisted bilayer graphene/s VL - 03 ER - TY - JOUR AB - The quantum anomalous Hall (QAH) effect combines topology and magnetism to produce precisely quantized Hall resistance at zero magnetic field. We report the observation of a QAH effect in twisted bilayer graphene aligned to hexagonal boron nitride. The effect is driven by intrinsic strong interactions, which polarize the electrons into a single spin- and valley-resolved moiré miniband with Chern number C = 1. In contrast to magnetically doped systems, the measured transport energy gap is larger than the Curie temperature for magnetic ordering, and quantization to within 0.1% of the von Klitzing constant persists to temperatures of several kelvin at zero magnetic field. Electrical currents as small as 1 nanoampere controllably switch the magnetic order between states of opposite polarization, forming an electrically rewritable magnetic memory. AU - Serlin, M. AU - Tschirhart, C. L. AU - Polshyn, Hryhoriy AU - Zhang, Y. AU - Zhu, J. AU - Watanabe, K. AU - Taniguchi, T. AU - Balents, L. AU - Young, A. F. ID - 10619 IS - 6480 JF - Science KW - multidisciplinary SN - 0036-8075 TI - Intrinsic quantized anomalous Hall effect in a moiré heterostructure VL - 367 ER - TY - CONF AB - Twisted bilayer graphene (tBLG) near the flat band condition is a versatile new platform for the study of correlated physics in 2D. Resistive states have been observed at several commensurate fillings of the flat miniband, along with superconducting states near half filling. To better understand the electronic structure of this system, we study electronic transport of graphite gated superconducting tBLG devices in the normal regime. At high magnetic fields, we observe full lifting of the spin and valley degeneracy. The transitions in the splitting of this four-fold degeneracy as a function of carrier density indicate Landau level (LL) crossings, which tilted field measurements show occur between LLs with different valley polarization. Similar LL structure measured in two devices, one with twist angle θ=1.08° at ambient pressure and one at θ=1.27° and 1.33GPa, suggests that the dimensionless combination of twist angle and interlayer coupling controls the relevant details of the band structure. In addition, we find that the temperature dependence of the resistance at B=0 shows linear growth at several hundred Ohm/K in a broad range of temperatures. We discuss the implications for modeling the scattering processes in this system. AU - Polshyn, Hryhoriy AU - Zhang, Yuxuan AU - Yankowitz, Matthew AU - Chen, Shaowen AU - Taniguchi, Takashi AU - Watanabe, Kenji AU - Graf, David E. AU - Dean, Cory R. AU - Young, Andrea ID - 10724 IS - 2 SN - 0003-0503 T2 - APS March Meeting 2019 TI - Normal state transport in superconducting twisted bilayer graphene VL - 64 ER - TY - CONF AB - Bilayer graphene, rotationally faulted to ~1.1 degree misalignment, has recently been shown to host superconducting and resistive states associated with the formation of a flat electronic band. While numerous theories exist for the origins of both states, direct validation of these theories remains an outstanding experimental problem. Here, we focus on the resistive states occurring at commensurate filling (1/2, 1/4, and 3/4) of the two lowest superlattice bands. We test theoretical proposals that these states arise due to broken spin—and/or valley—symmetry by performing direct magnetic imaging with nanoscale SQUID-on-tip microscopy. This technique provides single-spin resolved magnetometry on sub-100nm length scales. I will present imaging data from our 4.2K nSOT microscope on graphite-gated twisted bilayers near the flat band condition and discuss the implications for the physics of the commensurate resistive states. AU - Serlin, Marec AU - Tschirhart, Charles AU - Polshyn, Hryhoriy AU - Zhu, Jiacheng AU - Huber, Martin E. AU - Young, Andrea ID - 10722 IS - 2 SN - 0003-0503 T2 - APS March Meeting 2019 TI - Direct Imaging of magnetic structure in twisted bilayer graphene with scanning nanoSQUID-On-Tip microscopy VL - 64 ER - TY - CONF AB - Bilayer graphene with ~ 1.1 degrees twist mismatch between the layers hosts a low energy flat band in which the Coulomb interaction is large relative to the bandwidth, promoting correlated insulating states at half band filling, and superconducting (SC) phases with dome-like structure neighboring correlated insulating states. Here we show measurements of a dual-graphite-gated twisted bilayer graphene device, which minimizes charge inhomogeneity. We observe new correlated phases, including for the first time a SC pocket near half-filling of the electron-doped band and resistive states at quarter-filling of both bands that emerge in a magnetic field. Changing the layer polarization with vertical electric field reveals an unexpected competition between SC and correlated insulator phases, which we interpret to result from differences in disorder of each graphene layer and underscores the spatial inhomogeneity like twist angle as a significant source of disorder in these devices [1]. AU - Chen, Shaowen AU - Yankowitz, Matthew AU - Polshyn, Hryhoriy AU - Watanabe, Kenji AU - Taniguchi, Takashi AU - Graf, David E. AU - Young, Andrea AU - Dean, Cory R. ID - 10725 IS - 2 SN - 0003-0503 T2 - APS March Meeting 2019 TI - Correlated insulating and superconducting phases in twisted bilayer graphene VL - 64 ER - TY - CONF AB - In monolayer graphene, the interplay of electronic correlations with the internal spin- and valley- degrees of freedom leads to a complex phase diagram of isospin symmetry breaking at high magnetic fields. Recently, Wei et al. (Science (2018)) demonstrated that spin waves can be electrically generated and detected in graphene heterojunctions, allowing direct experiment access to the spin degree of freedom. Here, we apply this technique to high quality graphite-gated graphene devices showing robust fractional quantum Hall phases and isospin phase transitions. We use an edgeless Corbino geometry to eliminate the contributions of edge states to the spin-wave mediated nonlocal voltage, allowing unambiguous identification of spin wave transport signatures. Our data reveal two phases within the ν = 1 plateau. For exactly ν=1, charge is localized but spin waves propagate freely while small carrier doping completely quenches the low-energy spin-wave transport, even as those charges remain localized. We identify this new phase as a spin textured electron solid. We also find that spin-wave transport is modulated by phase transitions in the valley order that preserve spin polarization, suggesting that this technique is sensitive to both spin and valley order. AU - Zhou, Haoxin AU - Polshyn, Hryhoriy AU - Tanaguchi, Takashi AU - Watanabe, Kenji AU - Young, Andrea ID - 10723 IS - 2 SN - 0003-0503 T2 - APS March Meeting 2019 TI - Spin wave transport through electron solids and fractional quantum Hall liquids in graphene VL - 64 ER - TY - CONF AB - This report presents the results of a friendly competition for formal verification of continuous and hybrid systems with piecewise constant dynamics. The friendly competition took place as part of the workshop Applied Verification for Continuous and Hybrid Systems (ARCH) in 2019. In this third edition, six tools have been applied to solve five different benchmark problems in the category for piecewise constant dynamics: BACH, Lyse, Hy- COMP, PHAVer/SX, PHAVerLite, and VeriSiMPL. Compared to last year, a new tool has participated (HyCOMP) and PHAVerLite has replaced PHAVer-lite. The result is a snap- shot of the current landscape of tools and the types of benchmarks they are particularly suited for. Due to the diversity of problems, we are not ranking tools, yet the presented results probably provide the most complete assessment of tools for the safety verification of continuous and hybrid systems with piecewise constant dynamics up to this date. AU - Frehse, Goran AU - Abate, Alessandro AU - Adzkiya, Dieky AU - Becchi, Anna AU - Bu, Lei AU - Cimatti, Alessandro AU - Giacobbe, Mirco AU - Griggio, Alberto AU - Mover, Sergio AU - Mufid, Muhammad Syifa'ul AU - Riouak, Idriss AU - Tonetta, Stefano AU - Zaffanella, Enea ED - Frehse, Goran ED - Althoff, Matthias ID - 10877 SN - 2398-7340 T2 - ARCH19. 6th International Workshop on Applied Verification of Continuous and Hybrid Systems TI - ARCH-COMP19 Category Report: Hybrid systems with piecewise constant dynamics VL - 61 ER - TY - JOUR AB - Many adult tissues contain postmitotic cells as old as the host organism. The only organelle that does not turn over in these cells is the nucleus, and its maintenance represents a formidable challenge, as it harbors regulatory proteins that persist throughout adulthood. Here we developed strategies to visualize two classes of such long-lived proteins, histones and nucleoporins, to understand the function of protein longevity in nuclear maintenance. Genome-wide mapping of histones revealed specific enrichment of long-lived variants at silent gene loci. Interestingly, nuclear pores are maintained by piecemeal replacement of subunits, resulting in mosaic complexes composed of polypeptides with vastly different ages. In contrast, nondividing quiescent cells remove old nuclear pores in an ESCRT-dependent manner. Our findings reveal distinct molecular strategies of nuclear maintenance, linking lifelong protein persistence to gene regulation and nuclear integrity. AU - Toyama, Brandon H. AU - Arrojo e Drigo, Rafael AU - Lev-Ram, Varda AU - Ramachandra, Ranjan AU - Deerinck, Thomas J. AU - Lechene, Claude AU - Ellisman, Mark H. AU - HETZER, Martin W ID - 11061 IS - 2 JF - Journal of Cell Biology KW - Cell Biology SN - 0021-9525 TI - Visualization of long-lived proteins reveals age mosaicism within nuclei of postmitotic cells VL - 218 ER - TY - JOUR AB - Most neurons are not replaced during an animal’s lifetime. This nondividing state is characterized by extreme longevity and age-dependent decline of key regulatory proteins. To study the lifespans of cells and proteins in adult tissues, we combined isotope labeling of mice with a hybrid imaging method (MIMS-EM). Using 15N mapping, we show that liver and pancreas are composed of cells with vastly different ages, many as old as the animal. Strikingly, we also found that a subset of fibroblasts and endothelial cells, both known for their replicative potential, are characterized by the absence of cell division during adulthood. In addition, we show that the primary cilia of beta cells and neurons contains different structural regions with vastly different lifespans. Based on these results, we propose that age mosaicism across multiple scales is a fundamental principle of adult tissue, cell, and protein complex organization. AU - Arrojo e Drigo, Rafael AU - Lev-Ram, Varda AU - Tyagi, Swati AU - Ramachandra, Ranjan AU - Deerinck, Thomas AU - Bushong, Eric AU - Phan, Sebastien AU - Orphan, Victoria AU - Lechene, Claude AU - Ellisman, Mark H. AU - HETZER, Martin W ID - 11062 IS - 2 JF - Cell Metabolism KW - Cell Biology KW - Molecular Biology KW - Physiology SN - 1550-4131 TI - Age mosaicism across multiple scales in adult tissues VL - 30 ER - TY - JOUR AB - The genome is packaged and organized nonrandomly within the 3D space of the nucleus to promote efficient gene expression and to faithfully maintain silencing of heterochromatin. The genome is enclosed within the nucleus by the nuclear envelope membrane, which contains a set of proteins that actively participate in chromatin organization and gene regulation. Technological advances are providing views of genome organization at unprecedented resolution and are beginning to reveal the ways that cells co-opt the structures of the nuclear periphery for nuclear organization and gene regulation. These genome regulatory roles of proteins of the nuclear periphery have important influences on development, disease and ageing. AU - Buchwalter, Abigail AU - Kaneshiro, Jeanae M. AU - HETZER, Martin W ID - 11059 IS - 1 JF - Nature Reviews Genetics KW - Genetics (clinical) KW - Genetics KW - Molecular Biology SN - 1471-0056 TI - Coaching from the sidelines: The nuclear periphery in genome regulation VL - 20 ER - TY - JOUR AB - Deep optical spectroscopic surveys of galaxies provide a unique opportunity to investigate rest-frame ultra-violet (UV) emission line properties of galaxies at z ∼ 2 − 4.5. Here we combine VLT/MUSE Guaranteed Time Observations of the Hubble Deep Field South, Ultra Deep Field, COSMOS, and several quasar fields with other publicly available data from VLT/VIMOS and VLT/FORS2 to construct a catalogue of He II λ1640 emitters at z ≳ 2. The deepest areas of our MUSE pointings reach a 3σ line flux limit of 3.1 × 10−19 erg s−1 cm−2. After discarding broad-line active galactic nuclei, we find 13 He II λ1640 detections from MUSE with a median MUV = −20.1 and 21 tentative He II λ1640 detections from other public surveys. Excluding Lyα, all except two galaxies in our sample show at least one other rest-UV emission line, with C III] λ1907, λ1909 being the most prominent. We use multi-wavelength data available in the Hubble legacy fields to derive basic galaxy properties of our sample through spectral energy distribution fitting techniques. Taking advantage of the high-quality spectra obtained by MUSE (∼10 − 30 h of exposure time per pointing), we use photo-ionisation models to study the rest-UV emission line diagnostics of the He II λ1640 emitters. Line ratios of our sample can be reproduced by moderately sub-solar photo-ionisation models, however, we find that including effects of binary stars lead to degeneracies in most free parameters. Even after considering extra ionising photons produced by extreme sub-solar metallicity binary stellar models, photo-ionisation models are unable to reproduce rest-frame He II λ1640 equivalent widths (∼0.2 − 10 Å), thus additional mechanisms are necessary in models to match the observed He II λ1640 properties. AU - Nanayakkara, Themiya AU - Brinchmann, Jarle AU - Boogaard, Leindert AU - Bouwens, Rychard AU - Cantalupo, Sebastiano AU - Feltre, Anna AU - Kollatschny, Wolfram AU - Marino, Raffaella Anna AU - Maseda, Michael AU - Matthee, Jorryt J AU - Paalvast, Mieke AU - Richard, Johan AU - Verhamme, Anne ID - 11499 JF - Astronomy & Astrophysics KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: ISM / galaxies: star formation / galaxies: evolution / galaxies: high-redshift SN - 0004-6361 TI - Exploring He II λ1640 emission line properties at z ∼2−4 VL - 648 ER - TY - JOUR AB - Contact. This paper presents the results obtained with the Multi-Unit Spectroscopic Explorer (MUSE) at the ESO Very Large Telescope on the faint end of the Lyman-alpha luminosity function (LF) based on deep observations of four lensing clusters. The goal of our project is to set strong constraints on the relative contribution of the Lyman-alpha emitter (LAE) population to cosmic reionization. Aims. The precise aim of the present study is to further constrain the abundance of LAEs by taking advantage of the magnification provided by lensing clusters to build a blindly selected sample of galaxies which is less biased than current blank field samples in redshift and luminosity. By construction, this sample of LAEs is complementary to those built from deep blank fields, whether observed by MUSE or by other facilities, and makes it possible to determine the shape of the LF at fainter levels, as well as its evolution with redshift. Methods. We selected a sample of 156 LAEs with redshifts between 2.9 ≤ z ≤ 6.7 and magnification-corrected luminosities in the range 39 ≲ log LLyα [erg s−1] ≲43. To properly take into account the individual differences in detection conditions between the LAEs when computing the LF, including lensing configurations, and spatial and spectral morphologies, the non-parametric 1/Vmax method was adopted. The price to pay to benefit from magnification is a reduction of the effective volume of the survey, together with a more complex analysis procedure to properly determine the effective volume Vmax for each galaxy. In this paper we present a complete procedure for the determination of the LF based on IFU detections in lensing clusters. This procedure, including some new methods for masking, effective volume integration and (individual) completeness determinations, has been fully automated when possible, and it can be easily generalized to the analysis of IFU observations in blank fields. Results. As a result of this analysis, the Lyman-alpha LF has been obtained in four different redshift bins: 2.9 <  z <  6, 7, 2.9 <  z <  4.0, 4.0 <  z <  5.0, and 5.0 <  z <  6.7 with constraints down to log LLyα = 40.5. From our data only, no significant evolution of LF mean slope can be found. When performing a Schechter analysis also including data from the literature to complete the present sample towards the brightest luminosities, a steep faint end slope was measured varying from α = −1.69−0.08+0.08 to α = −1.87−0.12+0.12 between the lowest and the highest redshift bins. Conclusions. The contribution of the LAE population to the star formation rate density at z ∼ 6 is ≲50% depending on the luminosity limit considered, which is of the same order as the Lyman-break galaxy (LBG) contribution. The evolution of the LAE contribution with redshift depends on the assumed escape fraction of Lyman-alpha photons, and appears to slightly increase with increasing redshift when this fraction is conservatively set to one. Depending on the intersection between the LAE/LBG populations, the contribution of the observed galaxies to the ionizing flux may suffice to keep the universe ionized at z ∼ 6. AU - de La Vieuville, G. AU - Bina, D. AU - Pello, R. AU - Mahler, G. AU - Richard, J. AU - Drake, A. B. AU - Herenz, E. C. AU - Bauer, F. E. AU - Clément, B. AU - Lagattuta, D. AU - Laporte, N. AU - Martinez, J. AU - Patrício, V. AU - Wisotzki, L. AU - Zabl, J. AU - Bouwens, R. J. AU - Contini, T. AU - Garel, T. AU - Guiderdoni, B. AU - Marino, R. A. AU - Maseda, M. V. AU - Matthee, Jorryt J AU - Schaye, J. AU - Soucail, G. ID - 11505 JF - Astronomy & Astrophysics KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - gravitational lensing: strong / galaxies: high-redshift / dark ages KW - reionization KW - first stars / galaxies: clusters: general / galaxies: luminosity function KW - mass function SN - 0004-6361 TI - Faint end of the z ∼ 3–7 luminosity function of Lyman-alpha emitters behind lensing clusters observed with MUSE VL - 628 ER - TY - JOUR AB - Lyman-α (Lyα) is intrinsically the brightest line emitted from active galaxies. While it originates from many physical processes, for star-forming galaxies the intrinsic Lyα luminosity is a direct tracer of the Lyman-continuum (LyC) radiation produced by the most massive O- and early-type B-stars (M⋆ ≳ 10 M⊙) with lifetimes of a few Myrs. As such, Lyα luminosity should be an excellent instantaneous star formation rate (SFR) indicator. However, its resonant nature and susceptibility to dust as a rest-frame UV photon makes Lyα very hard to interpret due to the uncertain Lyα escape fraction, fesc, Lyα. Here we explore results from the CAlibrating LYMan-α with Hα (CALYMHA) survey at z = 2.2, follow-up of Lyα emitters (LAEs) at z = 2.2 − 2.6 and a z ∼ 0−0.3 compilation of LAEs to directly measure fesc, Lyα with Hα. We derive a simple empirical relation that robustly retrieves fesc, Lyα as a function of Lyα rest-frame EW (EW0): fesc,Lyα = 0.0048 EW0[Å] ± 0.05 and we show that it constrains a well-defined anti-correlation between ionisation efficiency (ξion) and dust extinction in LAEs. Observed Lyα luminosities and EW0 are easy measurable quantities at high redshift, thus making our relation a practical tool to estimate intrinsic Lyα and LyC luminosities under well controlled and simple assumptions. Our results allow observed Lyα luminosities to be used to compute SFRs for LAEs at z ∼ 0−2.6 within ±0.2 dex of the Hα dust corrected SFRs. We apply our empirical SFR(Lyα,EW0) calibration to several sources at z ≥ 2.6 to find that star-forming LAEs have SFRs typically ranging from 0.1 to 20 M⊙ yr−1 and that our calibration might be even applicable for the most luminous LAEs within the epoch of re-ionisation. Our results imply high ionisation efficiencies (log10[ξion/Hz erg−1] = 25.4−25.6) and low dust content in LAEs across cosmic time, and will be easily tested with future observations with JWST which can obtain Hα and Hβ measurements for high-redshift LAEs. AU - Sobral, David AU - Matthee, Jorryt J ID - 11507 JF - Astronomy & Astrophysics KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: high-redshift / galaxies: star formation / galaxies: statistics / galaxies: evolution / galaxies: formation / galaxies: ISM SN - 0004-6361 TI - Predicting Lyα escape fractions with a simple observable: Lyα in emission as an empirically calibrated star formation rate indicator VL - 623 ER - TY - JOUR AB - We discuss the nature and physical properties of gas-mass selected galaxies in the ALMA spectroscopic survey (ASPECS) of the Hubble Ultra Deep Field (HUDF). We capitalize on the deep optical integral-field spectroscopy from the Multi Unit Spectroscopic Explorer (MUSE) HUDF Survey and multiwavelength data to uniquely associate all 16 line emitters, detected in the ALMA data without preselection, with rotational transitions of carbon monoxide (CO). We identify 10 as CO(2–1) at 1 < z < 2, 5 as CO(3–2) at 2 < z < 3, and 1 as CO(4–3) at z = 3.6. Using the MUSE data as a prior, we identify two additional CO(2–1) emitters, increasing the total sample size to 18. We infer metallicities consistent with (super-)solar for the CO-detected galaxies at z ≤ 1.5, motivating our choice of a Galactic conversion factor between CO luminosity and molecular gas mass for these galaxies. Using deep Chandra imaging of the HUDF, we determine an X-ray AGN fraction of 20% and 60% among the CO emitters at z ∼ 1.4 and z ∼ 2.6, respectively. Being a CO-flux-limited survey, ASPECS-LP detects molecular gas in galaxies on, above, and below the main sequence (MS) at z ∼ 1.4. For stellar masses ≥1010 (1010.5) ${M}_{\odot }$, we detect about 40% (50%) of all galaxies in the HUDF at 1 < z < 2 (2 < z < 3). The combination of ALMA and MUSE integral-field spectroscopy thus enables an unprecedented view of MS galaxies during the peak of galaxy formation. AU - Boogaard, Leindert A. AU - Decarli, Roberto AU - González-López, Jorge AU - van der Werf, Paul AU - Walter, Fabian AU - Bouwens, Rychard AU - Aravena, Manuel AU - Carilli, Chris AU - Bauer, Franz Erik AU - Brinchmann, Jarle AU - Contini, Thierry AU - Cox, Pierre AU - da Cunha, Elisabete AU - Daddi, Emanuele AU - Díaz-Santos, Tanio AU - Hodge, Jacqueline AU - Inami, Hanae AU - Ivison, Rob AU - Maseda, Michael AU - Matthee, Jorryt J AU - Oesch, Pascal AU - Popping, Gergö AU - Riechers, Dominik AU - Schaye, Joop AU - Schouws, Sander AU - Smail, Ian AU - Weiss, Axel AU - Wisotzki, Lutz AU - Bacon, Roland AU - Cortes, Paulo C. AU - Rix, Hans-Walter AU - Somerville, Rachel S. AU - Swinbank, Mark AU - Wagg, Jeff ID - 11514 IS - 2 JF - The Astrophysical Journal KW - Space and Planetary Science KW - Astronomy and Astrophysics SN - 0004-637X TI - The ALMA spectroscopic survey in the HUDF: Nature and physical properties of gas-mass selected galaxies using MUSE spectroscopy VL - 882 ER - TY - JOUR AB - The well-known quasar SDSS J095253.83+011421.9 (J0952+0114) at z = 3.02 has one of the most peculiar spectra discovered so far, showing the presence of narrow Lyα and broad metal emission lines. Although recent studies have suggested that a proximate damped Lyα absorption (PDLA) system causes this peculiar spectrum, the origin of the gas associated with the PDLA is unknown. Here we report the results of observations with the Multi Unit Spectroscopic Explorer (MUSE) that reveal a new giant (≈100 physical kpc) Lyα nebula. The detailed analysis of the Lyα velocity, velocity dispersion, and surface brightness profiles suggests that the J0952+0114 Lyα nebula shares similar properties with other QSO nebulae previously detected with MUSE, implying that the PDLA in J0952+0144 is covering only a small fraction of the solid angle of the QSO emission. We also detected bright and spectrally narrow C iv λ1550 and He ii λ1640 extended emission around J0952+0114 with velocity centroids similar to the peak of the extended and central narrow Lyα emission. The presence of a peculiarly bright, unresolved, and relatively broad He ii λ1640 emission in the central region at exactly the same PDLA redshift hints at the possibility that the PDLA originates in a clumpy outflow with a bulk velocity of about 500 km s−1. The smaller velocity dispersion of the large-scale Lyα emission suggests that the high-speed outflow is confined to the central region. Lastly, the derived spatially resolved He ii/Lyα and C iv/Lyα maps show a positive gradient with the distance to the QSO, hinting at a non-homogeneous distribution of the ionization parameter. AU - Marino, Raffaella Anna AU - Cantalupo, Sebastiano AU - Pezzulli, Gabriele AU - Lilly, Simon J. AU - Gallego, Sofia AU - Mackenzie, Ruari AU - Matthee, Jorryt J AU - Brinchmann, Jarle AU - Bouché, Nicolas AU - Feltre, Anna AU - Muzahid, Sowgat AU - Schroetter, Ilane AU - Johnson, Sean D. AU - Nanayakkara, Themiya ID - 11516 IS - 1 JF - The Astrophysical Journal KW - Space and Planetary Science KW - Astronomy and Astrophysics SN - 0004-637X TI - A giant Lyα nebula and a small-scale clumpy outflow in the system of the exotic quasar J0952+0114 unveiled by MUSE VL - 880 ER - TY - JOUR AB - We present new deep ALMA and Hubble Space Telescope (HST)/WFC3 observations of MASOSA and VR7, two luminous Lyα emitters (LAEs) at z = 6.5, for which the UV continuum levels differ by a factor of four. No IR dust continuum emission is detected in either, indicating little amounts of obscured star formation and/or high dust temperatures. MASOSA, with a UV luminosity M1500 = −20.9, compact size, and very high Lyα ${\mathrm{EW}}_{0}\approx 145\,\mathring{\rm A} $, is undetected in [C ii] to a limit of L[C ii] < 2.2 × 107 L⊙, implying a metallicity Z ≲ 0.07 Z⊙. Intriguingly, our HST data indicate a red UV slope β = −1.1 ± 0.7, at odds with the low dust content. VR7, which is a bright (M1500 = −22.4) galaxy with moderate color (β = −1.4 ± 0.3) and Lyα EW0 = 34 Å, is clearly detected in [C ii] emission (S/N = 15). VR7's rest-frame UV morphology can be described by two components separated by ≈1.5 kpc and is globally more compact than the [C ii] emission. The global [C ii]/UV ratio indicates Z ≈ 0.2 Z⊙, but there are large variations in the UV/[C ii] ratio on kiloparsec scales. We also identify diffuse, possibly outflowing, [C ii]-emitting gas at ≈100 km s−1 with respect to the peak. VR7 appears to be assembling its components at a slightly more evolved stage than other luminous LAEs, with outflows already shaping its direct environment at z ∼ 7. Our results further indicate that the global [C ii]−UV relation steepens at SFR < 30 M⊙ yr−1, naturally explaining why the [C ii]/UV ratio is anticorrelated with Lyα EW in many, but not all, observed LAEs. AU - Matthee, Jorryt J AU - Sobral, D. AU - Boogaard, L. A. AU - Röttgering, H. AU - Vallini, L. AU - Ferrara, A. AU - Paulino-Afonso, A. AU - Boone, F. AU - Schaerer, D. AU - Mobasher, B. ID - 11515 IS - 2 JF - The Astrophysical Journal KW - Space and Planetary Science KW - Astronomy and Astrophysics SN - 0004-637X TI - Resolved UV and [C ii] structures of luminous galaxies within the epoch of reionization VL - 881 ER - TY - JOUR AB - To understand star formation in galaxies, we investigate the star formation rate (SFR) surface density (ΣSFR) profiles for galaxies, based on a well-defined sample of 976 star-forming MaNGA galaxies. We find that the typical ΣSFR profiles within 1.5Re of normal SF galaxies can be well described by an exponential function for different stellar mass intervals, while the sSFR profile shows positive gradients, especially for more massive SF galaxies. This is due to the more pronounced central cores or bulges rather than the onset of a `quenching' process. While galaxies that lie significantly above (or below) the star formation main sequence (SFMS) show overall an elevation (or suppression) of ΣSFR at all radii, this central elevation (or suppression) is more pronounced in more massive galaxies. The degree of central enhancement and suppression is quite symmetric, suggesting that both the elevation and suppression of star formation are following the same physical processes. Furthermore, we find that the dispersion in ΣSFR within and across the population is found to be tightly correlated with the inferred gas depletion time, whether based on the stellar surface mass density or the orbital dynamical time. This suggests that we are seeing the response of a simple gas-regulator system to variations in the accretion rate. This is explored using a heuristic model that can quantitatively explain the dependence of σ(ΣSFR) on gas depletion timescale. Variations in accretion rate are progressively more damped out in regions of low star-formation efficiency leading to a reduced amplitude of variations in star-formation. AU - Wang, Enci AU - Lilly, Simon J. AU - Pezzulli, Gabriele AU - Matthee, Jorryt J ID - 11517 IS - 2 JF - The Astrophysical Journal KW - Space and Planetary Science KW - Astronomy and Astrophysics SN - 0004-637X TI - On the elevation and suppression of star formation within galaxies VL - 877 ER - TY - JOUR AB - We investigate the clustering and halo properties of ∼5000 Ly α-selected emission-line galaxies (LAEs) from the Slicing COSMOS 4K (SC4K) and from archival NB497 imaging of SA22 split in 15 discrete redshift slices between z ∼ 2.5 and 6. We measure clustering lengths of r0 ∼ 3–6 h−1 Mpc and typical halo masses of ∼1011 M⊙ for our narrowband-selected LAEs with typical LLy α ∼ 1042–43 erg s−1. The intermediate-band-selected LAEs are observed to have r0 ∼ 3.5–15 h−1 Mpc with typical halo masses of ∼1011–12 M⊙ and typical LLy α ∼ 1043–43.6 erg s−1. We find a strong, redshift-independent correlation between halo mass and Ly α luminosity normalized by the characteristic Ly α luminosity, L⋆(z). The faintest LAEs (L ∼ 0.1 L⋆(z)) typically identified by deep narrowband surveys are found in 1010 M⊙ haloes and the brightest LAEs (L ∼ 7 L⋆(z)) are found in ∼5 × 1012 M⊙ haloes. A dependency on the rest-frame 1500 Å UV luminosity, MUV, is also observed where the halo masses increase from 1011 to 1013 M⊙ for MUV ∼ −19 to −23.5 mag. Halo mass is also observed to increase from 109.8 to 1012 M⊙ for dust-corrected UV star formation rates from ∼0.6 to 10 M⊙ yr−1 and continues to increase up to 1013 M⊙ in halo mass, where the majority of those sources are active galactic nuclei. All the trends we observe are found to be redshift independent. Our results reveal that LAEs are the likely progenitors of a wide range of galaxies depending on their luminosity, from dwarf-like, to Milky Way-type, to bright cluster galaxies. LAEs therefore provide unique insight into the early formation and evolution of the galaxies we observe in the local Universe. AU - Khostovan, A A AU - Sobral, D AU - Mobasher, B AU - Matthee, Jorryt J AU - Cochrane, R K AU - Chartab, N AU - Jafariyazani, M AU - Paulino-Afonso, A AU - Santos, S AU - Calhau, J ID - 11535 IS - 1 JF - Monthly Notices of the Royal Astronomical Society KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - galaxies: evolution KW - galaxies: haloes KW - galaxies: high-redshift KW - galaxies: star formation KW - cosmology: observations KW - large-scale structure of Universe SN - 0035-8711 TI - The clustering of typical Ly α emitters from z ∼ 2.5–6: Host halo masses depend on Ly α and UV luminosities VL - 489 ER - TY - JOUR AB - We present new Hubble Space Telescope (HST)/WFC3 observations and re-analyse VLT data to unveil the continuum, variability, and rest-frame ultraviolet (UV) lines of the multiple UV clumps of the most luminous Lyα emitter at z = 6.6, CR7 (COSMOS Redshift 7). Our re-reduced, flux-calibrated X-SHOOTER spectra of CR7 reveal an He II emission line in observations obtained along the major axis of Lyα emission with the best seeing conditions. He II is spatially offset by ≈+0.8 arcsec from the peak of Lyα emission, and it is found towards clump B. Our WFC3 grism spectra detects the UV continuum of CR7’s clump A, yielding a power law with β=−2.5+0.6−0.7 and MUV=−21.87+0.25−0.20⁠. No significant variability is found for any of the UV clumps on their own, but there is tentative (≈2.2 σ) brightening of CR7 in F110W as a whole from 2012 to 2017. HST grism data fail to robustly detect rest-frame UV lines in any of the clumps, implying fluxes ≲2×10−17 erg s−1 cm−2 (3σ). We perform CLOUDY modelling to constrain the metallicity and the ionizing nature of CR7. CR7 seems to be actively forming stars without any clear active galactic nucleus activity in clump A, consistent with a metallicity of ∼0.05–0.2 Z⊙. Component C or an interclump component between B and C may host a high ionization source. Our results highlight the need for spatially resolved information to study the formation and assembly of early galaxies. AU - Sobral, David AU - Matthee, Jorryt J AU - Brammer, Gabriel AU - Ferrara, Andrea AU - Alegre, Lara AU - Röttgering, Huub AU - Schaerer, Daniel AU - Mobasher, Bahram AU - Darvish, Behnam ID - 11541 IS - 2 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 - cosmology: observations KW - dark ages KW - reionization KW - first stars KW - early Universe SN - 0035-8711 TI - On the nature and physical conditions of the luminous Ly α emitter CR7 and its rest-frame UV components VL - 482 ER - TY - JOUR AB - Observations have revealed that the star formation rate (SFR) and stellar mass (Mstar) of star-forming galaxies follow a tight relation known as the galaxy main sequence. However, what physical information is encoded in this relation is under debate. Here, we use the EAGLE cosmological hydrodynamical simulation to study the mass dependence, evolution, and origin of scatter in the SFR–Mstar relation. At z = 0, we find that the scatter decreases slightly with stellar mass from 0.35 dex at Mstar ≈ 109 M⊙ to 0.30 dex at Mstar ≳ 1010.5 M⊙. The scatter decreases from z = 0 to z = 5 by 0.05 dex at Mstar ≳ 1010 M⊙ and by 0.15 dex for lower masses. We show that the scatter at z = 0.1 originates from a combination of fluctuations on short time-scales (ranging from 0.2–2 Gyr) that are presumably associated with self-regulation from cooling, star formation, and outflows, but is dominated by long time-scale (∼10 Gyr) variations related to differences in halo formation times. Shorter time-scale fluctuations are relatively more important for lower mass galaxies. At high masses, differences in black hole formation efficiency cause additional scatter, but also diminish the scatter caused by different halo formation times. While individual galaxies cross the main sequence multiple times during their evolution, they fluctuate around tracks associated with their halo properties, i.e. galaxies above/below the main sequence at z = 0.1 tend to have been above/below the main sequence for ≫1 Gyr. AU - Matthee, Jorryt J AU - Schaye, Joop ID - 11540 IS - 1 JF - Monthly Notices of the Royal Astronomical Society KW - Space and Planetary Science KW - Astronomy and Astrophysics : galaxies: evolution KW - galaxies: formation KW - galaxies: star formation KW - cosmology: theory SN - 0035-8711 TI - The origin of scatter in the star formation rate–stellar mass relation VL - 484 ER - TY - JOUR AB - We present the discovery of HD 221416 b, the first transiting planet identified by the Transiting Exoplanet Survey Satellite (TESS) for which asteroseismology of the host star is possible. HD 221416 b (HIP 116158, TOI-197) is a bright (V = 8.2 mag), spectroscopically classified subgiant that oscillates with an average frequency of about 430 μHz and displays a clear signature of mixed modes. The oscillation amplitude confirms that the redder TESS bandpass compared to Kepler has a small effect on the oscillations, supporting the expected yield of thousands of solar-like oscillators with TESS 2 minute cadence observations. Asteroseismic modeling yields a robust determination of the host star radius (R⋆ = 2.943 ± 0.064 R⊙), mass (M⋆ = 1.212 ± 0.074 M⊙), and age (4.9 ± 1.1 Gyr), and demonstrates that it has just started ascending the red-giant branch. Combining asteroseismology with transit modeling and radial-velocity observations, we show that the planet is a "hot Saturn" (Rp = 9.17 ± 0.33 R⊕) with an orbital period of ∼14.3 days, irradiance of F = 343 ± 24 F⊕, and moderate mass (Mp = 60.5 ± 5.7 M⊕) and density (ρp = 0.431 ± 0.062 g cm−3). The properties of HD 221416 b show that the host-star metallicity–planet mass correlation found in sub-Saturns (4–8 R⊕) does not extend to larger radii, indicating that planets in the transition between sub-Saturns and Jupiters follow a relatively narrow range of densities. With a density measured to ∼15%, HD 221416 b is one of the best characterized Saturn-size planets to date, augmenting the small number of known transiting planets around evolved stars and demonstrating the power of TESS to characterize exoplanets and their host stars using asteroseismology. AU - Huber, Daniel AU - Chaplin, William J. AU - Chontos, Ashley AU - Kjeldsen, Hans AU - Christensen-Dalsgaard, Jørgen AU - Bedding, Timothy R. AU - Ball, Warrick AU - Brahm, Rafael AU - Espinoza, Nestor AU - Henning, Thomas AU - Jordán, Andrés AU - Sarkis, Paula AU - Knudstrup, Emil AU - Albrecht, Simon AU - Grundahl, Frank AU - Andersen, Mads Fredslund AU - Pallé, Pere L. AU - Crossfield, Ian AU - Fulton, Benjamin AU - Howard, Andrew W. AU - Isaacson, Howard T. AU - Weiss, Lauren M. AU - Handberg, Rasmus AU - Lund, Mikkel N. AU - Serenelli, Aldo M. AU - Rørsted Mosumgaard, Jakob AU - Stokholm, Amalie AU - Bieryla, Allyson AU - Buchhave, Lars A. AU - Latham, David W. AU - Quinn, Samuel N. AU - Gaidos, Eric AU - Hirano, Teruyuki AU - Ricker, George R. AU - Vanderspek, Roland K. AU - Seager, Sara AU - Jenkins, Jon M. AU - Winn, Joshua N. AU - Antia, H. M. AU - Appourchaux, Thierry AU - Basu, Sarbani AU - Bell, Keaton J. AU - Benomar, Othman AU - Bonanno, Alfio AU - Buzasi, Derek L. AU - Campante, Tiago L. AU - Çelik Orhan, Z. AU - Corsaro, Enrico AU - Cunha, Margarida S. AU - Davies, Guy R. AU - Deheuvels, Sebastien AU - Grunblatt, Samuel K. AU - Hasanzadeh, Amir AU - Di Mauro, Maria Pia AU - A. García, Rafael AU - Gaulme, Patrick AU - Girardi, Léo AU - Guzik, Joyce A. AU - Hon, Marc AU - Jiang, Chen AU - Kallinger, Thomas AU - Kawaler, Steven D. AU - Kuszlewicz, James S. AU - Lebreton, Yveline AU - Li, Tanda AU - Lucas, Miles AU - Lundkvist, Mia S. AU - Mann, Andrew W. AU - Mathis, Stéphane AU - Mathur, Savita AU - Mazumdar, Anwesh AU - Metcalfe, Travis S. AU - Miglio, Andrea AU - F. G. Monteiro, Mário J. P. AU - Mosser, Benoit AU - Noll, Anthony AU - Nsamba, Benard AU - Joel Ong, Jia Mian AU - Örtel, S. AU - Pereira, Filipe AU - Ranadive, Pritesh AU - Régulo, Clara AU - Rodrigues, Thaíse S. AU - Roxburgh, Ian W. AU - Aguirre, Victor Silva AU - Smalley, Barry AU - Schofield, Mathew AU - Sousa, Sérgio G. AU - Stassun, Keivan G. AU - Stello, Dennis AU - Tayar, Jamie AU - White, Timothy R. AU - Verma, Kuldeep AU - Vrard, Mathieu AU - Yıldız, M. AU - Baker, David AU - Bazot, Michaël AU - Beichmann, Charles AU - Bergmann, Christoph AU - Bugnet, Lisa Annabelle AU - Cale, Bryson AU - Carlino, Roberto AU - Cartwright, Scott M. AU - Christiansen, Jessie L. AU - Ciardi, David R. AU - Creevey, Orlagh AU - Dittmann, Jason A. AU - Nascimento, Jose-Dias Do AU - Eylen, Vincent Van AU - Fürész, Gabor AU - Gagné, Jonathan AU - Gao, Peter AU - Gazeas, Kosmas AU - Giddens, Frank AU - Hall, Oliver J. AU - Hekker, Saskia AU - Ireland, Michael J. AU - Latouf, Natasha AU - LeBrun, Danny AU - Levine, Alan M. AU - Matzko, William AU - Natinsky, Eva AU - Page, Emma AU - Plavchan, Peter AU - Mansouri-Samani, Masoud AU - McCauliff, Sean AU - Mullally, Susan E. AU - Orenstein, Brendan AU - Soto, Aylin Garcia AU - Paegert, Martin AU - van Saders, Jennifer L. AU - Schnaible, Chloe AU - Soderblom, David R. AU - Szabó, Róbert AU - Tanner, Angelle AU - Tinney, C. G. AU - Teske, Johanna AU - Thomas, Alexandra AU - Trampedach, Regner AU - Wright, Duncan AU - Yuan, Thomas T. AU - Zohrabi, Farzaneh ID - 11616 IS - 6 JF - The Astronomical Journal KW - Space and Planetary Science KW - Astronomy and Astrophysics SN - 0004-6256 TI - A hot Saturn orbiting an oscillating late subgiant discovered by TESS VL - 157 ER - TY - JOUR AB - Over 2,000 stars were observed for 1 month with a high enough cadence in order to look for acoustic modes during the survey phase of the Kepler mission. Solar-like oscillations have been detected in about 540 stars. The question of why no oscillations were detected in the remaining stars is still open. Previous works explained the non-detection of modes with the high level of magnetic activity of the stars. However, the sample of stars studied contained some classical pulsators and red giants that could have biased the results. In this work, we revisit this analysis on a cleaner sample of main-sequence solar-like stars that consists of 1,014 stars. First we compute the predicted amplitude of the modes of that sample and for the stars with detected oscillation and compare it to the noise at high frequency in the power spectrum. We find that the stars with detected modes have an amplitude to noise ratio larger than 0.94. We measure reliable rotation periods and the associated photometric magnetic index for 684 stars out of the full sample and in particular for 323 stars where the amplitude of the modes is predicted to be high enough to be detected. We find that among these 323 stars 32% of them have a level of magnetic activity larger than the Sun during its maximum activity, explaining the non-detection of acoustic modes. Interestingly, magnetic activity cannot be the primary reason responsible for the absence of detectable modes in the remaining 68% of the stars without acoustic modes detected and with reliable rotation periods. Thus, we investigate metallicity, inclination angle of the rotation axis, and binarity as possible causes of low mode amplitudes. Using spectroscopic observations for a subsample, we find that a low metallicity could be the reason for suppressed modes. No clear correlation with binarity nor inclination is found. We also derive the lower limit for our photometric activity index (of 20–30 ppm) below which rotation and magnetic activity are not detected. Finally, with our analysis we conclude that stars with a photometric activity index larger than 2,000 ppm have 98.3% probability of not having oscillations detected. AU - Mathur, Savita AU - García, Rafael A. AU - Bugnet, Lisa Annabelle AU - Santos, Ângela R.G. AU - Santiago, Netsha AU - Beck, Paul G. ID - 11613 JF - Frontiers in Astronomy and Space Sciences KW - Astronomy and Astrophysics TI - Revisiting the impact of stellar magnetic activity on the detectability of solar-like oscillations by Kepler VL - 6 ER - TY - JOUR AB - The recently published Kepler mission Data Release 25 (DR25) reported on ∼197 000 targets observed during the mission. Despite this, no wide search for red giants showing solar-like oscillations have been made across all stars observed in Kepler’s long-cadence mode. In this work, we perform this task using custom apertures on the Kepler pixel files and detect oscillations in 21 914 stars, representing the largest sample of solar-like oscillating stars to date. We measure their frequency at maximum power, νmax, down to νmax≃4μHz and obtain log (g) estimates with a typical uncertainty below 0.05 dex, which is superior to typical measurements from spectroscopy. Additionally, the νmax distribution of our detections show good agreement with results from a simulated model of the Milky Way, with a ratio of observed to predicted stars of 0.992 for stars with 10<νmax<270μHz. Among our red giant detections, we find 909 to be dwarf/subgiant stars whose flux signal is polluted by a neighbouring giant as a result of using larger photometric apertures than those used by the NASA Kepler science processing pipeline. We further find that only 293 of the polluting giants are known Kepler targets. The remainder comprises over 600 newly identified oscillating red giants, with many expected to belong to the Galactic halo, serendipitously falling within the Kepler pixel files of targeted stars. AU - Hon, Marc AU - Stello, Dennis AU - García, Rafael A AU - Mathur, Savita AU - Sharma, Sanjib AU - Colman, Isabel L AU - Bugnet, Lisa Annabelle ID - 11615 IS - 4 JF - Monthly Notices of the Royal Astronomical Society KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - asteroseismology KW - methods: data analysis KW - techniques: image processing KW - stars: oscillations KW - stars: statistics SN - 0035-8711 TI - A search for red giant solar-like oscillations in all Kepler data VL - 485 ER - TY - JOUR AB - The NASA Transiting Exoplanet Survey Satellite (TESS) is about to provide full-frame images of almost the entire sky. The amount of stellar data to be analysed represents hundreds of millions stars, which is several orders of magnitude more than the number of stars observed by the Convection, Rotation and planetary Transits satellite (CoRoT), and NASA Kepler and K2 missions. We aim at automatically classifying the newly observed stars with near real-time algorithms to better guide the subsequent detailed studies. In this paper, we present a classification algorithm built to recognise solar-like pulsators among classical pulsators. This algorithm relies on the global amount of power contained in the power spectral density (PSD), also known as the flicker in spectral power density (FliPer). Because each type of pulsating star has a characteristic background or pulsation pattern, the shape of the PSD at different frequencies can be used to characterise the type of pulsating star. The FliPer classifier (FliPerClass) uses different FliPer parameters along with the effective temperature as input parameters to feed a ML algorithm in order to automatically classify the pulsating stars observed by TESS. Using noisy TESS-simulated data from the TESS Asteroseismic Science Consortium (TASC), we classify pulsators with a 98% accuracy. Among them, solar-like pulsating stars are recognised with a 99% accuracy, which is of great interest for a further seismic analysis of these stars, which are like our Sun. Similar results are obtained when we trained our classifier and applied it to 27-day subsets of real Kepler data. FliPerClass is part of the large TASC classification pipeline developed by the TESS Data for Asteroseismology (T’DA) classification working group. AU - Bugnet, Lisa Annabelle AU - García, R. A. AU - Mathur, S. AU - Davies, G. R. AU - Hall, O. J. AU - Lund, M. N. AU - Rendle, B. M. ID - 11614 JF - Astronomy & Astrophysics KW - Space and Planetary Science KW - Astronomy and Astrophysics SN - 0004-6361 TI - FliPerClass: In search of solar-like pulsators among TESS targets VL - 624 ER - TY - JOUR AB - Brightness variations due to dark spots on the stellar surface encode information about stellar surface rotation and magnetic activity. In this work, we analyze the Kepler long-cadence data of 26,521 main-sequence stars of spectral types M and K in order to measure their surface rotation and photometric activity level. Rotation-period estimates are obtained by the combination of a wavelet analysis and autocorrelation function of the light curves. Reliable rotation estimates are determined by comparing the results from the different rotation diagnostics and four data sets. We also measure the photometric activity proxy Sph using the amplitude of the flux variations on an appropriate timescale. We report rotation periods and photometric activity proxies for about 60% of the sample, including 4431 targets for which McQuillan et al. did not report a rotation period. For the common targets with rotation estimates in this study and in McQuillan et al., our rotation periods agree within 99%. In this work, we also identify potential polluters, such as misclassified red giants and classical pulsator candidates. Within the parameter range we study, there is a mild tendency for hotter stars to have shorter rotation periods. The photometric activity proxy spans a wider range of values with increasing effective temperature. The rotation period and photometric activity proxy are also related, with Sph being larger for fast rotators. Similar to McQuillan et al., we find a bimodal distribution of rotation periods. AU - Santos, A. R. G. AU - García, R. A. AU - Mathur, S. AU - Bugnet, Lisa Annabelle AU - van Saders, J. L. AU - Metcalfe, T. S. AU - Simonian, G. V. A. AU - Pinsonneault, M. H. ID - 11623 IS - 1 JF - The Astrophysical Journal Supplement Series KW - Space and Planetary Science KW - Astronomy and Astrophysics KW - methods: data analysis KW - stars: activity KW - stars: low-mass KW - stars: rotation KW - starspots KW - techniques: photometric SN - 0067-0049 TI - Surface rotation and photometric activity for Kepler targets. I. M and K main-sequence stars VL - 244 ER - TY - GEN AB - For a solar-like star, the surface rotation evolves with time, allowing in principle to estimate the age of a star from its surface rotation period. Here we are interested in measuring surface rotation periods of solar-like stars observed by the NASA mission Kepler. Different methods have been developed to track rotation signals in Kepler photometric light curves: time-frequency analysis based on wavelet techniques, autocorrelation and composite spectrum. We use the learning abilities of random forest classifiers to take decisions during two crucial steps of the analysis. First, given some input parameters, we discriminate the considered Kepler targets between rotating MS stars, non-rotating MS stars, red giants, binaries and pulsators. We then use a second classifier only on the MS rotating targets to decide the best data analysis treatment. AU - Breton, S. N. AU - Bugnet, Lisa Annabelle AU - Santos, A. R. G. AU - Saux, A. Le AU - Mathur, S. AU - Palle, P. L. AU - Garcia, R. A. ID - 11627 KW - asteroseismology KW - rotation KW - solar-like stars KW - kepler KW - machine learning KW - random forest T2 - arXiv TI - Determining surface rotation periods of solar-like stars observed by the Kepler mission using machine learning techniques ER - TY - GEN AB - The second mission of NASA’s Kepler satellite, K2, has collected hundreds of thousands of lightcurves for stars close to the ecliptic plane. This new sample could increase the number of known pulsating stars and then improve our understanding of those stars. For the moment only a few stars have been properly classified and published. In this work, we present a method to automaticly classify K2 pulsating stars using a Machine Learning technique called Random Forest. The objective is to sort out the stars in four classes: red giant (RG), main-sequence Solar-like stars (SL), classical pulsators (PULS) and Other. To do this we use the effective temperatures and the luminosities of the stars as well as the FliPer features, that measures the amount of power contained in the power spectral density. The classifier now retrieves the right classification for more than 80% of the stars. AU - Saux, A. Le AU - Bugnet, Lisa Annabelle AU - Mathur, S. AU - Breton, S. N. AU - Garcia, R. A. ID - 11630 KW - asteroseismology - methods KW - data analysis - thecniques KW - machine learning - stars KW - oscillations T2 - arXiv TI - Automatic classification of K2 pulsating stars using machine learning techniques ER - TY - CONF AB - The diameter, radius and eccentricities are natural graph parameters. While these problems have been studied extensively, there are no known dynamic algorithms for them beyond the ones that follow from trivial recomputation after each update or from solving dynamic All-Pairs Shortest Paths (APSP), which is very computationally intensive. This is the situation for dynamic approximation algorithms as well, and even if only edge insertions or edge deletions need to be supported. This paper provides a comprehensive study of the dynamic approximation of Diameter, Radius and Eccentricities, providing both conditional lower bounds, and new algorithms whose bounds are optimal under popular hypotheses in fine-grained complexity. Some of the highlights include: - Under popular hardness hypotheses, there can be no significantly better fully dynamic approximation algorithms than recomputing the answer after each update, or maintaining full APSP. - Nearly optimal partially dynamic (incremental/decremental) algorithms can be achieved via efficient reductions to (incremental/decremental) maintenance of Single-Source Shortest Paths. For instance, a nearly (3/2+epsilon)-approximation to Diameter in directed or undirected n-vertex, m-edge graphs can be maintained decrementally in total time m^{1+o(1)}sqrt{n}/epsilon^2. This nearly matches the static 3/2-approximation algorithm for the problem that is known to be conditionally optimal. AU - Ancona, Bertie AU - Henzinger, Monika H AU - Roditty, Liam AU - Williams, Virginia Vassilevska AU - Wein, Nicole ID - 11826 SN - 1868-8969 T2 - 46th International Colloquium on Automata, Languages, and Programming TI - Algorithms and hardness for diameter in dynamic graphs VL - 132 ER - TY - CONF AB - Modern networked systems are increasingly reconfigurable, enabling demand-aware infrastructures whose resources can be adjusted according to the workload they currently serve. Such dynamic adjustments can be exploited to improve network utilization and hence performance, by moving frequently interacting communication partners closer, e.g., collocating them in the same server or datacenter. However, dynamically changing the embedding of workloads is algorithmically challenging: communication patterns are often not known ahead of time, but must be learned. During the learning process, overheads related to unnecessary moves (i.e., re-embeddings) should be minimized. This paper studies a fundamental model which captures the tradeoff between the benefits and costs of dynamically collocating communication partners on l servers, in an online manner. Our main contribution is a distributed online algorithm which is asymptotically almost optimal, i.e., almost matches the lower bound (also derived in this paper) on the competitive ratio of any (distributed or centralized) online algorithm. AU - Henzinger, Monika H AU - Neumann, Stefan AU - Schmid, Stefan ID - 11850 SN - 978-1-4503-6678-6 T2 - SIGMETRICS'19: International Conference on Measurement and Modeling of Computer Systems TI - Efficient distributed workload (re-)embedding ER - TY - CHAP AB - This paper serves as a user guide to the Vienna graph clustering framework. We review our general memetic algorithm, VieClus, to tackle the graph clustering problem. 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. After giving a description of the algorithms employed, we establish the connection of the graph clustering problem to protein–protein interaction networks and moreover give a description on how the software can be used, what file formats are expected, and how this can be used to find functional groups in protein–protein interaction networks. AU - Biedermann, Sonja AU - Henzinger, Monika H AU - Schulz, Christian AU - Schuster, Bernhard ED - Canzar, Stefan ED - Rojas Ringeling, Francisca ID - 11847 SN - 1064-3745 T2 - Protein-Protein Interaction Networks TI - Vienna Graph Clustering VL - 2074 ER - TY - CONF AB - We present a deterministic dynamic algorithm for maintaining a (1+ε)f-approximate minimum cost set cover with O(f log(Cn)/ε^2) amortized update time, when the input set system is undergoing element insertions and deletions. Here, n denotes the number of elements, each element appears in at most f sets, and the cost of each set lies in the range [1/C, 1]. Our result, together with that of Gupta~et~al.~[STOC'17], implies that there is a deterministic algorithm for this problem with O(f log(Cn)) amortized update time and O(min(log n, f)) -approximation ratio, which nearly matches the polynomial-time hardness of approximation for minimum set cover in the static setting. Our update time is only O(log (Cn)) away from a trivial lower bound. Prior to our work, the previous best approximation ratio guaranteed by deterministic algorithms was O(f^2), which was due to Bhattacharya~et~al.~[ICALP`15]. In contrast, the only result that guaranteed O(f) -approximation was obtained very recently by Abboud~et~al.~[STOC`19], who designed a dynamic algorithm with (1+ε)f-approximation ratio and O(f^2 log n/ε) amortized update time. Besides the extra O(f) factor in the update time compared to our and Gupta~et~al.'s results, the Abboud~et~al.~algorithm is randomized, and works only when the adversary is oblivious and the sets are unweighted (each set has the same cost). We achieve our result via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. This approach was pursued previously by Bhattacharya~et~al.~and Gupta~et~al., but not in the recent paper by Abboud~et~al. Unlike previous primal-dual algorithms that try to satisfy some local constraints for individual sets at all time, our algorithm basically waits until the dual solution changes significantly globally, and fixes the solution only where the fix is needed. AU - Bhattacharya, Sayan AU - Henzinger, Monika H AU - Nanongkai, Danupon ID - 11853 SN - 2575-8454 T2 - 60th Annual Symposium on Foundations of Computer Science TI - A new deterministic algorithm for dynamic set cover 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 weighted sum of the cut edges. In this paper, we engineer the fastest known exact algorithm for the problem. State-of-the-art algorithms like the algorithm of Padberg and Rinaldi or the algorithm of Nagamochi, Ono and Ibaraki identify edges that can be contracted to reduce the graph size such that at least one minimum cut is maintained in the contracted graph. Our algorithm achieves improvements in running time over these algorithms by a multitude of techniques. First, we use a recently developed fast and parallel inexact minimum cut algorithm to obtain a better bound for the problem. Afterwards, we use reductions that depend on this bound to reduce the size of the graph much faster than previously possible. We use improved data structures to further lower the running time of our algorithm. Additionally, we parallelize the contraction routines of Nagamochi et al. . Overall, we arrive at a system that significantly outperforms the fastest state-of-the-art solvers for the exact minimum cut problem. AU - Henzinger, Monika H AU - Noe, Alexander AU - Schulz, Christian ID - 11851 SN - 978-1-7281-1247-3 T2 - 33rd International Parallel and Distributed Processing Symposium TI - Shared-memory exact minimum cuts ER - TY - CONF AB - We present the first sublinear-time algorithm that can compute the edge connectivity λ of a network exactly on distributed message-passing networks (the CONGEST model), as long as the network contains no multi-edge. We present the first sublinear-time algorithm for a distributed message-passing network sto compute its edge connectivity λ exactly in the CONGEST model, as long as there are no parallel edges. Our algorithm takes Õ(n1−1/353D1/353+n1−1/706) time to compute λ and a cut of cardinality λ with high probability, where n and D are the number of nodes and the diameter of the network, respectively, and Õ hides polylogarithmic factors. This running time is sublinear in n (i.e. Õ(n1−є)) whenever D is. Previous sublinear-time distributed algorithms can solve this problem either (i) exactly only when λ=O(n1/8−є) [Thurimella PODC’95; Pritchard, Thurimella, ACM Trans. Algorithms’11; Nanongkai, Su, DISC’14] or (ii) approximately [Ghaffari, Kuhn, DISC’13; Nanongkai, Su, DISC’14]. To achieve this we develop and combine several new techniques. First, we design the first distributed algorithm that can compute a k-edge connectivity certificate for any k=O(n1−є) in time Õ(√nk+D). The previous sublinear-time algorithm can do so only when k=o(√n) [Thurimella PODC’95]. In fact, our algorithm can be turned into the first parallel algorithm with polylogarithmic depth and near-linear work. Previous near-linear work algorithms are essentially sequential and previous polylogarithmic-depth algorithms require Ω(mk) work in the worst case (e.g. [Karger, Motwani, STOC’93]). Second, we show that by combining the recent distributed expander decomposition technique of [Chang, Pettie, Zhang, SODA’19] with techniques from the sequential deterministic edge connectivity algorithm of [Kawarabayashi, Thorup, STOC’15], we can decompose the network into a sublinear number of clusters with small average diameter and without any mincut separating a cluster (except the “trivial” ones). This leads to a simplification of the Kawarabayashi-Thorup framework (except that we are randomized while they are deterministic). This might make this framework more useful in other models of computation. Finally, by extending the tree packing technique from [Karger STOC’96], we can find the minimum cut in time proportional to the number of components. As a byproduct of this technique, we obtain an Õ(n)-time algorithm for computing exact minimum cut for weighted graphs. AU - Daga, Mohit AU - Henzinger, Monika H AU - Nanongkai, Danupon AU - Saranurak, Thatchaphol ID - 11865 SN - 0737-8017 T2 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing TI - Distributed edge connectivity in sublinear time ER - TY - CONF AB - Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, where each individual operation has to be executed quickly. For this reason, there exist many recent randomized results that aim to provide a guarantee stronger than amortized expected. The strongest possible guarantee for a randomized algorithm is that it is always correct (Las Vegas), and has high-probability worst-case update time, which gives a bound on the time for each individual operation that holds with high probability. In this paper we present the first polylogarithmic high-probability worst-case time bounds for the dynamic spanner and the dynamic maximal matching problem. 1. For dynamic spanner, the only known o(n) worst-case bounds were O(n3/4) high-probability worst-case update time for maintaining a 3-spanner, and O(n5/9) for maintaining a 5-spanner. We give a O(1)k log3(n) high-probability worst-case time bound for maintaining a (2k – 1)-spanner, which yields the first worst-case polylog update time for all constant k. (All the results above maintain the optimal tradeoff of stretch 2k – 1 and Õ(n1+1/k) edges.) 2. For dynamic maximal matching, or dynamic 2-approximate maximum matching, no algorithm with o(n) worst-case time bound was known and we present an algorithm with O(log5 (n)) high-probability worst-case time; similar worst-case bounds existed only for maintaining a matching that was (2 + ∊)-approximate, and hence not maximal. Our results are achieved using a new approach for converting amortized guarantees to worst-case ones for randomized data structures by going through a third type of guarantee, which is a middle ground between the two above: an algorithm is said to have worst-case expected update time α if for every update σ, the expected time to process σ is at most α. Although stronger than amortized expected, the worst-case expected guarantee does not resolve the fundamental problem of amortization: a worst-case expected update time of O(1) still allows for the possibility that every 1/f(n) updates requires Θ(f(n)) time to process, for arbitrarily high f(n). In this paper we present a black-box reduction that converts any data structure with worst-case expected update time into one with a high-probability worst-case update time: the query time remains the same, while the update time increases by a factor of O(log2(n)). Thus we achieve our results in two steps: (1) First we show how to convert existing dynamic graph algorithms with amortized expected polylogarithmic running times into algorithms with worst-case expected polylogarithmic running times. (2) Then we use our black-box reduction to achieve the polylogarithmic high-probability worst-case time bound. All our algorithms are Las-Vegas-type algorithms. AU - Bernstein, Aaron AU - Forster, Sebastian AU - Henzinger, Monika H ID - 11871 T2 - 30th Annual ACM-SIAM Symposium on Discrete Algorithms TI - A deamortization approach for dynamic spanner and dynamic maximal matching ER - TY - JOUR AB - We build upon the recent papers by Weinstein and Yu (FOCS'16), Larsen (FOCS'12), and Clifford et al. (FOCS'15) to present a general framework that gives amortized lower bounds on the update and query times of dynamic data structures. Using our framework, we present two concrete results. (1) For the dynamic polynomial evaluation problem, where the polynomial is defined over a finite field of size n1+Ω(1) and has degree n, any dynamic data structure must either have an amortized update time of Ω((lgn/lglgn)2) or an amortized query time of Ω((lgn/lglgn)2). (2) For the dynamic online matrix vector multiplication problem, where we get an n×n matrix whose entires are drawn from a finite field of size nΘ(1), any dynamic data structure must either have an amortized update time of Ω((lgn/lglgn)2) or an amortized query time of Ω(n⋅(lgn/lglgn)2). For these two problems, the previous works by Larsen (FOCS'12) and Clifford et al. (FOCS'15) gave the same lower bounds, but only for worst case update and query times. Our bounds match the highest unconditional lower bounds known till date for any dynamic problem in the cell-probe model. AU - Bhattacharya, Sayan AU - Henzinger, Monika H AU - Neumann, Stefan ID - 11898 JF - Theoretical Computer Science SN - 0304-3975 TI - New amortized cell-probe lower bounds for dynamic problems VL - 779 ER - TY - JOUR AB - Cross-coupling reactions mediated by dual nickel/photocatalysis are synthetically attractive but rely mainly on expensive, non-recyclable noble-metal complexes as photocatalysts. Heterogeneous semiconductors, which are commonly used for artificial photosynthesis and wastewater treatment, are a sustainable alternative. Graphitic carbon nitrides, a class of metal-free polymers that can be easily prepared from bulk chemicals, are heterogeneous semiconductors with high potential for photocatalytic organic transformations. Here, we demonstrate that graphitic carbon nitrides in combination with nickel catalysis can induce selective C−O cross-couplings of carboxylic acids with aryl halides, yielding the respective aryl esters in excellent yield and selectivity. The heterogeneous organic photocatalyst exhibits a broad substrate scope, is able to harvest green light, and can be recycled multiple times. In situ FTIR was used to track the reaction progress to study this transformation at different irradiation wavelengths and reaction scales. AU - Pieber, Bartholomäus AU - Malik, Jamal A. AU - Cavedon, Cristian AU - Gisbertz, Sebastian AU - Savateev, Aleksandr AU - Cruz, Daniel AU - Heil, Tobias AU - Zhang, Guigang AU - Seeberger, Peter H. ID - 11957 IS - 28 JF - Angewandte Chemie International Edition SN - 1433-7851 TI - Semi‐heterogeneous dual nickel/photocatalysis using carbon nitrides: Esterification of carboxylic acids with aryl halides VL - 58 ER - TY - JOUR AB - Differentially protected galactosamine building blocks are key components for the synthesis of human and bacterial oligosaccharides. The azidophenylselenylation of 3,4,6-tri-O-acetyl-d-galactal provides straightforward access to the corresponding 2-nitrogenated glycoside. Poor reproducibility and the use of azides that lead to the formation of potentially explosive and toxic species limit the scalability of this reaction and render it a bottleneck for carbohydrate synthesis. Here, we present a method for the safe, efficient, and reliable azidophenylselenylation of 3,4,6-tri-O-acetyl-d-galactal at room temperature, using continuous flow chemistry. Careful analysis of the transformation resulted in reaction conditions that produce minimal side products while the reaction time was reduced drastically when compared to batch reactions. The flow setup is readily scalable to process 5 mmol of galactal in 3 h, producing 1.2 mmol/h of product. AU - Guberman, Mónica AU - Pieber, Bartholomäus AU - Seeberger, Peter H. ID - 11984 IS - 12 JF - Organic Process Research and Development SN - 1083-6160 TI - Safe and scalable continuous flow azidophenylselenylation of galactal to prepare galactosamine building blocks VL - 23 ER - TY - JOUR AB - A carbon nitride material can be combined with homogeneous nickel catalysts for light-mediated cross-couplings of aryl bromides with alcohols under mild conditions. The metal-free heterogeneous semiconductor is fully recyclable and couples a broad range of electron-poor aryl bromides with primary and secondary alcohols as well as water. The application for intramolecular reactions and the synthesis of active pharmaceutical ingredients was demonstrated. The catalytic protocol is applicable for the coupling of aryl iodides with thiols as well. AU - Cavedon, Cristian AU - Madani, Amiera AU - Seeberger, Peter H. AU - Pieber, Bartholomäus ID - 11982 IS - 13 JF - Organic Letters SN - 1523-7060 TI - Semiheterogeneous dual nickel/photocatalytic (thio)etherification using carbon nitrides VL - 21 ER - TY - JOUR AB - Upper and lower bounds, of the expected order of magnitude, are obtained for the number of rational points of bounded height on any quartic del Pezzo surface over ℚ that contains a conic defined over ℚ . AU - Browning, Timothy D AU - Sofos, Efthymios ID - 170 IS - 3-4 JF - Mathematische Annalen TI - Counting rational points on quartic del Pezzo surfaces with a rational conic VL - 373 ER - TY - JOUR AU - Kalinin, Nikita AU - Shkolnikov, Mikhail ID - 441 IS - 3 JF - European Journal of Mathematics SN - 2199-675X TI - Tropical formulae for summation over a part of SL(2,Z) VL - 5 ER - TY - CHAP AB - The transcription coactivator, Yes-associated protein (YAP), which is a nuclear effector of the Hippo signaling pathway, has been shown to be a mechano-transducer. By using mutant fish and human 3D spheroids, we have recently demonstrated that YAP is also a mechano-effector. YAP functions in three-dimensional (3D) morphogenesis of organ and global body shape by controlling actomyosin-mediated tissue tension. In this chapter, we present a platform that links the findings in fish embryos with human cells. The protocols for analyzing tissue tension-mediated global body shape/organ morphogenesis in vivo and ex vivo using medaka fish embryos and in vitro using human cell spheroids represent useful tools for unraveling the molecular mechanisms by which YAP functions in regulating global body/organ morphogenesis. AU - Asaoka, Yoichi AU - Morita, Hitoshi AU - Furumoto, Hiroko AU - Heisenberg, Carl-Philipp J AU - Furutani-Seiki, Makoto ED - Hergovich, Alexander ID - 5793 SN - 978-1-4939-8909-6 T2 - The hippo pathway TI - Studying YAP-mediated 3D morphogenesis using fish embryos and human spheroids VL - 1893 ER - TY - JOUR AB - Cryptographic security is usually defined as a guarantee that holds except when a bad event with negligible probability occurs, and nothing is guaranteed in that bad case. However, in settings where such failure can happen with substantial probability, one needs to provide guarantees even for the bad case. A typical example is where a (possibly weak) password is used instead of a secure cryptographic key to protect a session, the bad event being that the adversary correctly guesses the password. In a situation with multiple such sessions, a per-session guarantee is desired: any session for which the password has not been guessed remains secure, independently of whether other sessions have been compromised. A new formalism for stating such gracefully degrading security guarantees is introduced and applied to analyze the examples of password-based message authentication and password-based encryption. While a natural per-message guarantee is achieved for authentication, the situation of password-based encryption is more delicate: a per-session confidentiality guarantee only holds against attackers for which the distribution of password-guessing effort over the sessions is known in advance. In contrast, for more general attackers without such a restriction, a strong, composable notion of security cannot be achieved. AU - Demay, Gregory AU - Gazi, Peter AU - Maurer, Ueli AU - Tackmann, Bjorn ID - 5887 IS - 1 JF - Journal of Computer Security SN - 0926227X TI - Per-session security: Password-based cryptography revisited VL - 27 ER - TY - CONF AB - We propose a new non-orthogonal basis to express the 3D Euclidean space in terms of a regular grid. Every grid point, each represented by integer 3-coordinates, corresponds to rhombic dodecahedron centroid. Rhombic dodecahedron is a space filling polyhedron which represents the close packing of spheres in 3D space and the Voronoi structures of the face centered cubic (FCC) lattice. In order to illustrate the interest of the new coordinate system, we propose the characterization of 3D digital plane with its topological features, such as the interrelation between the thickness of the digital plane and the separability constraint we aim to obtain. A characterization of a 3D digital sphere with relevant topological features is proposed as well with the help of a 48 symmetry that comes with the new coordinate system. AU - Biswas, Ranita AU - Largeteau-Skapin, Gaëlle AU - Zrour, Rita AU - Andres, Eric ID - 6163 SN - 0302-9743 T2 - 21st IAPR International Conference on Discrete Geometry for Computer Imagery TI - Rhombic dodecahedron grid—coordinate system and 3D digital object definitions VL - 11414 ER - TY - JOUR AB - We give non-degeneracy criteria for Riemannian simplices based on simplices in spaces of constant sectional curvature. It extends previous work on Riemannian simplices, where we developed Riemannian simplices with respect to Euclidean reference simplices. The criteria we give in this article are in terms of quality measures for spaces of constant curvature that we develop here. We see that simplices in spaces that have nearly constant curvature, are already non-degenerate under very weak quality demands. This is of importance because it allows for sampling of Riemannian manifolds based on anisotropy of the manifold and not (absolute) curvature. AU - Dyer, Ramsay AU - Vegter, Gert AU - Wintraecken, Mathijs ID - 6515 IS - 1 JF - Journal of Computational Geometry SN - 1920-180X TI - Simplices modelled on spaces of constant curvature VL - 10 ER - TY - CONF AB - We construct a verifiable delay function (VDF) by showing how the Rivest-Shamir-Wagner time-lock puzzle can be made publicly verifiable. Concretely, we give a statistically sound public-coin protocol to prove that a tuple (N,x,T,y) satisfies y=x2T (mod N) where the prover doesn’t know the factorization of N and its running time is dominated by solving the puzzle, that is, compute x2T, which is conjectured to require T sequential squarings. To get a VDF we make this protocol non-interactive using the Fiat-Shamir heuristic.The motivation for this work comes from the Chia blockchain design, which uses a VDF as akey ingredient. For typical parameters (T≤2 40, N= 2048), our proofs are of size around 10K B, verification cost around three RSA exponentiations and computing the proof is 8000 times faster than solving the puzzle even without any parallelism. AU - Pietrzak, Krzysztof Z ID - 6528 SN - 1868-8969 T2 - 10th Innovations in Theoretical Computer Science Conference TI - Simple verifiable delay functions VL - 124 ER - TY - CONF AB - In this paper, we address the problem of synthesizing periodic switching controllers for stabilizing a family of linear systems. Our broad approach consists of constructing a finite game graph based on the family of linear systems such that every winning strategy on the game graph corresponds to a stabilizing switching controller for the family of linear systems. The construction of a (finite) game graph, the synthesis of a winning strategy and the extraction of a stabilizing controller are all computationally feasible. We illustrate our method on an example. AU - Kundu, Atreyee AU - Garcia Soto, Miriam AU - Prabhakar, Pavithra ID - 6565 SN - 978-153866246-5 T2 - 5th Indian Control Conference Proceedings TI - Formal synthesis of stabilizing controllers for periodically controlled linear switched systems ER - TY - CONF AB - Fejes Tóth [5] and Schneider [9] studied approximations of smooth convex hypersurfaces in Euclidean space by piecewise flat triangular meshes with a given number of vertices on the hypersurface that are optimal with respect to Hausdorff distance. They proved that this Hausdorff distance decreases inversely proportional with m 2/(d−1), where m is the number of vertices and d is the dimension of Euclidean space. Moreover the pro-portionality constant can be expressed in terms of the Gaussian curvature, an intrinsic quantity. In this short note, we prove the extrinsic nature of this constant for manifolds of sufficiently high codimension. We do so by constructing an family of isometric embeddings of the flat torus in Euclidean space. AU - Vegter, Gert AU - Wintraecken, Mathijs ID - 6628 T2 - The 31st Canadian Conference in Computational Geometry TI - The extrinsic nature of the Hausdorff distance of optimal triangulations of manifolds ER - TY - CONF AB - Various kinds of data are routinely represented as discrete probability distributions. Examples include text documents summarized by histograms of word occurrences and images represented as histograms of oriented gradients. Viewing a discrete probability distribution as a point in the standard simplex of the appropriate dimension, we can understand collections of such objects in geometric and topological terms. Importantly, instead of using the standard Euclidean distance, we look into dissimilarity measures with information-theoretic justification, and we develop the theory needed for applying topological data analysis in this setting. In doing so, we emphasize constructions that enable the usage of existing computational topology software in this context. AU - Edelsbrunner, Herbert AU - Virk, Ziga AU - Wagner, Hubert ID - 6648 SN - 9783959771047 T2 - 35th International Symposium on Computational Geometry TI - Topological data analysis in information space VL - 129 ER - TY - JOUR AB - Chemical labeling of proteins with synthetic molecular probes offers the possibility to probe the functions of proteins of interest in living cells. However, the methods for covalently labeling targeted proteins using complementary peptide tag-probe pairs are still limited, irrespective of the versatility of such pairs in biological research. Herein, we report the new CysHis tag-Ni(II) probe pair for the specific covalent labeling of proteins. A broad-range evaluation of the reactivity profiles of the probe and the CysHis peptide tag afforded a tag-probe pair with an optimized and high labeling selectivity and reactivity. In particular, the labeling specificity of this pair was notably improved compared to the previously reported one. This pair was successfully utilized for the fluorescence imaging of membrane proteins on the surfaces of living cells, demonstrating its potential utility in biological research. AU - Zenmyo, Naoki AU - Tokumaru, Hiroki AU - Uchinomiya, Shohei AU - Fuchida, Hirokazu AU - Tabata, Shigekazu AU - Hamachi, Itaru AU - Shigemoto, Ryuichi AU - Ojida, Akio ID - 6659 IS - 5 JF - Bulletin of the Chemical Society of Japan SN - 00092673 TI - Optimized reaction pair of the CysHis tag and Ni(II)-NTA probe for highly selective chemical labeling of membrane proteins VL - 92 ER - TY - JOUR AB - In phase retrieval, we want to recover an unknown signal 𝑥∈ℂ𝑑 from n quadratic measurements of the form 𝑦𝑖=|⟨𝑎𝑖,𝑥⟩|2+𝑤𝑖, where 𝑎𝑖∈ℂ𝑑 are known sensing vectors and 𝑤𝑖 is measurement noise. We ask the following weak recovery question: What is the minimum number of measurements n needed to produce an estimator 𝑥^(𝑦) that is positively correlated with the signal 𝑥? We consider the case of Gaussian vectors 𝑎𝑎𝑖. We prove that—in the high-dimensional limit—a sharp phase transition takes place, and we locate the threshold in the regime of vanishingly small noise. For 𝑛≤𝑑−𝑜(𝑑), no estimator can do significantly better than random and achieve a strictly positive correlation. For 𝑛≥𝑑+𝑜(𝑑), a simple spectral estimator achieves a positive correlation. Surprisingly, numerical simulations with the same spectral estimator demonstrate promising performance with realistic sensing matrices. Spectral methods are used to initialize non-convex optimization algorithms in phase retrieval, and our approach can boost the performance in this setting as well. Our impossibility result is based on classical information-theoretic arguments. The spectral algorithm computes the leading eigenvector of a weighted empirical covariance matrix. We obtain a sharp characterization of the spectral properties of this random matrix using tools from free probability and generalizing a recent result by Lu and Li. Both the upper bound and lower bound generalize beyond phase retrieval to measurements 𝑦𝑖 produced according to a generalized linear model. As a by-product of our analysis, we compare the threshold of the proposed spectral method with that of a message passing algorithm. AU - Mondelli, Marco AU - Montanari, Andrea ID - 6662 IS - 3 JF - Foundations of Computational Mathematics TI - Fundamental limits of weak recovery with applications to phase retrieval VL - 19 ER - TY - JOUR AB - The construction of anisotropic triangulations is desirable for various applications, such as the numerical solving of partial differential equations and the representation of surfaces in graphics. To solve this notoriously difficult problem in a practical way, we introduce the discrete Riemannian Voronoi diagram, a discrete structure that approximates the Riemannian Voronoi diagram. This structure has been implemented and was shown to lead to good triangulations in $\mathbb{R}^2$ and on surfaces embedded in $\mathbb{R}^3$ as detailed in our experimental companion paper. In this paper, we study theoretical aspects of our structure. Given a finite set of points $\mathcal{P}$ in a domain $\Omega$ equipped with a Riemannian metric, we compare the discrete Riemannian Voronoi diagram of $\mathcal{P}$ to its Riemannian Voronoi diagram. Both diagrams have dual structures called the discrete Riemannian Delaunay and the Riemannian Delaunay complex. We provide conditions that guarantee that these dual structures are identical. It then follows from previous results that the discrete Riemannian Delaunay complex can be embedded in $\Omega$ under sufficient conditions, leading to an anisotropic triangulation with curved simplices. Furthermore, we show that, under similar conditions, the simplices of this triangulation can be straightened. AU - Boissonnat, Jean-Daniel AU - Rouxel-Labbé, Mael AU - Wintraecken, Mathijs ID - 6672 IS - 3 JF - SIAM Journal on Computing SN - 0097-5397 TI - Anisotropic triangulations via discrete Riemannian Voronoi diagrams VL - 48 ER - TY - CONF AB - A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that can express a wide range of discrete optimization problems. A VCSP instance is given by a finite set of variables, a finite domain of labels, and an objective function to be minimized. This function is represented as a sum of terms where each term depends on a subset of the variables. To obtain different classes of optimization problems, one can restrict all terms to come from a fixed set Γ of cost functions, called a language. Recent breakthrough results have established a complete complexity classification of such classes with respect to language Γ: if all cost functions in Γ satisfy a certain algebraic condition then all Γ-instances can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately, testing this condition for a given language Γ is known to be NP-hard. We thus study exponential algorithms for this meta-problem. We show that the tractability condition of a finite-valued language Γ can be tested in O(3‾√3|D|⋅poly(size(Γ))) time, where D is the domain of Γ and poly(⋅) is some fixed polynomial. We also obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH). More precisely, we prove that for any constant δ<1 there is no O(3‾√3δ|D|) algorithm, assuming that SETH holds. AU - Kolmogorov, Vladimir ID - 6725 SN - 1868-8969 T2 - 46th International Colloquium on Automata, Languages and Programming TI - Testing the complexity of a valued CSP language VL - 132 ER - TY - CHAP AB - Randomness is an essential part of any secure cryptosystem, but many constructions rely on distributions that are not uniform. This is particularly true for lattice based cryptosystems, which more often than not make use of discrete Gaussian distributions over the integers. For practical purposes it is crucial to evaluate the impact that approximation errors have on the security of a scheme to provide the best possible trade-off between security and performance. Recent years have seen surprising results allowing to use relatively low precision while maintaining high levels of security. A key insight in these results is that sampling a distribution with low relative error can provide very strong security guarantees. Since floating point numbers provide guarantees on the relative approximation error, they seem a suitable tool in this setting, but it is not obvious which sampling algorithms can actually profit from them. While previous works have shown that inversion sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES 2014; Prest, ASIACRYPT 2017), other works have called into question if this is possible for other sampling techniques (Zheng et al., Eprint report 2018/309). In this work, we consider all sampling algorithms that are popular in the cryptographic setting and analyze the relationship of floating point precision and the resulting relative error. We show that all of the algorithms either natively achieve a low relative error or can be adapted to do so. AU - Walter, Michael ED - Buchmann, J ED - Nitaj, A ED - Rachidi, T ID - 6726 SN - 0302-9743 T2 - Progress in Cryptology – AFRICACRYPT 2019 TI - Sampling the integers with low relative error VL - 11627 ER - TY - JOUR AB - Consider the problem of constructing a polar code of block length N for a given transmission channel W. Previous approaches require one to compute the reliability of the N synthetic channels and then use only those that are sufficiently reliable. However, we know from two independent works by Schürch and by Bardet et al. that the synthetic channels are partially ordered with respect to degradation. Hence, it is natural to ask whether the partial order can be exploited to reduce the computational burden of the construction problem. We show that, if we take advantage of the partial order, we can construct a polar code by computing the reliability of roughly a fraction 1/ log 3/2 N of the synthetic channels. In particular, we prove that N/ log 3/2 N is a lower bound on the number of synthetic channels to be considered and such a bound is tight up to a multiplicative factor log log N. This set of roughly N/ log 3/2 N synthetic channels is universal, in the sense that it allows one to construct polar codes for any W, and it can be identified by solving a maximum matching problem on a bipartite graph. Our proof technique consists of reducing the construction problem to the problem of computing the maximum cardinality of an antichain for a suitable partially ordered set. As such, this method is general, and it can be used to further improve the complexity of the construction problem, in case a refined partial order on the synthetic channels of polar codes is discovered. AU - Mondelli, Marco AU - Hassani, Hamed AU - Urbanke, Rudiger ID - 6663 IS - 5 JF - IEEE TI - Construction of polar codes with sublinear complexity VL - 65 ER - TY - CONF AB - We establish connections between the problem of learning a two-layer neural network and tensor decomposition. We consider a model with feature vectors x∈ℝd, r hidden units with weights {wi}1≤i≤r and output y∈ℝ, i.e., y=∑ri=1σ(w𝖳ix), with activation functions given by low-degree polynomials. In particular, if σ(x)=a0+a1x+a3x3, we prove that no polynomial-time learning algorithm can outperform the trivial predictor that assigns to each example the response variable 𝔼(y), when d3/2≪r≪d2. Our conclusion holds for a `natural data distribution', namely standard Gaussian feature vectors x, and output distributed according to a two-layer neural network with random isotropic weights, and under a certain complexity-theoretic assumption on tensor decomposition. Roughly speaking, we assume that no polynomial-time algorithm can substantially outperform current methods for tensor decomposition based on the sum-of-squares hierarchy. We also prove generalizations of this statement for higher degree polynomial activations, and non-random weight vectors. Remarkably, several existing algorithms for learning two-layer networks with rigorous guarantees are based on tensor decomposition. Our results support the idea that this is indeed the core computational difficulty in learning such networks, under the stated generative model for the data. As a side result, we show that under this model learning the network requires accurate learning of its weights, a property that does not hold in a more general setting. AU - Mondelli, Marco AU - Montanari, Andrea ID - 6747 T2 - Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics TI - On the connection between learning two-layers neural networks and tensor decomposition VL - 89 ER - TY - JOUR AB - Polar codes have gained extensive attention during the past few years and recently they have been selected for the next generation of wireless communications standards (5G). Successive-cancellation-based (SC-based) decoders, such as SC list (SCL) and SC flip (SCF), provide a reasonable error performance for polar codes at the cost of low decoding speed. Fast SC-based decoders, such as Fast-SSC, Fast-SSCL, and Fast-SSCF, identify the special constituent codes in a polar code graph off-line, produce a list of operations, store the list in memory, and feed the list to the decoder to decode the constituent codes in order efficiently, thus increasing the decoding speed. However, the list of operations is dependent on the code rate and as the rate changes, a new list is produced, making fast SC-based decoders not rate-flexible. In this paper, we propose a completely rate-flexible fast SC-based decoder by creating the list of operations directly in hardware, with low implementation complexity. We further propose a hardware architecture implementing the proposed method and show that the area occupation of the rate-flexible fast SC-based decoder in this paper is only 38% of the total area of the memory-based base-line decoder when 5G code rates are supported. AU - Hashemi, Seyyed Ali AU - Condo, Carlo AU - Mondelli, Marco AU - Gross, Warren J ID - 6750 IS - 22 JF - IEEE Transactions on Signal Processing SN - 1053587X TI - Rate-flexible fast polar decoders VL - 67 ER - TY - JOUR AB - We consider the graph class Grounded-L corresponding to graphs that admit an intersection representation by L-shaped curves, where additionally the topmost points of each curve are assumed to belong to a common horizontal line. We prove that Grounded-L graphs admit an equivalent characterisation in terms of vertex ordering with forbidden patterns. We also compare this class to related intersection classes, such as the grounded segment graphs, the monotone L-graphs (a.k.a. max point-tolerance graphs), or the outer-1-string graphs. We give constructions showing that these classes are all distinct and satisfy only trivial or previously known inclusions. AU - Jelínek, Vít AU - Töpfer, Martin ID - 6759 IS - 3 JF - Electronic Journal of Combinatorics TI - On grounded L-graphs and their relatives VL - 26 ER - TY - CONF AB - In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the qualitative winner or quantitative payoff of the game. In bidding games, in each turn, we hold an auction between the two players to determine which player moves the token. Bidding games have largely been studied with concrete bidding mechanisms that are variants of a first-price auction: in each turn both players simultaneously submit bids, the higher bidder moves the token, and pays his bid to the lower bidder in Richman bidding, to the bank in poorman bidding, and in taxman bidding, the bid is split between the other player and the bank according to a predefined constant factor. Bidding games are deterministic games. They have an intriguing connection with a fragment of stochastic games called randomturn games. We study, for the first time, a combination of bidding games with probabilistic behavior; namely, we study bidding games that are played on Markov decision processes, where the players bid for the right to choose the next action, which determines the probability distribution according to which the next vertex is chosen. We study parity and meanpayoff bidding games on MDPs and extend results from the deterministic bidding setting to the probabilistic one. AU - Avni, Guy AU - Henzinger, Thomas A AU - Ibsen-Jensen, Rasmus AU - Novotny, Petr ID - 6822 SN - 0302-9743 T2 - Proceedings of the 13th International Conference of Reachability Problems TI - Bidding games on Markov decision processes VL - 11674 ER - TY - CONF AB - The fundamental model-checking problem, given as input a model and a specification, asks for the algorithmic verification of whether the model satisfies the specification. Two classical models for reactive systems are graphs and Markov decision processes (MDPs). A basic specification formalism in the verification of reactive systems is the strong fairness (aka Streett) objective, where given different types of requests and corresponding grants, the requirement is that for each type, if the request event happens infinitely often, then the corresponding grant event must also happen infinitely often. All omega-regular objectives can be expressed as Streett objectives and hence they are canonical in verification. Consider graphs/MDPs with n vertices, m edges, and a Streett objectives with k pairs, and let b denote the size of the description of the Streett objective for the sets of requests and grants. The current best-known algorithm for the problem requires time O(min(n^2, m sqrt{m log n}) + b log n). In this work we present randomized near-linear time algorithms, with expected running time O~(m + b), where the O~ notation hides poly-log factors. Our randomized algorithms are near-linear in the size of the input, and hence optimal up to poly-log factors. AU - Chatterjee, Krishnendu AU - Dvorák, Wolfgang AU - Henzinger, Monika H AU - Svozil, Alexander ID - 6887 T2 - Leibniz International Proceedings in Informatics TI - Near-linear time algorithms for Streett objectives in graphs and MDPs VL - 140 ER - TY - CONF AB - In this paper, we design novel liquid time-constant recurrent neural networks for robotic control, inspired by the brain of the nematode, C. elegans. In the worm's nervous system, neurons communicate through nonlinear time-varying synaptic links established amongst them by their particular wiring structure. This property enables neurons to express liquid time-constants dynamics and therefore allows the network to originate complex behaviors with a small number of neurons. We identify neuron-pair communication motifs as design operators and use them to configure compact neuronal network structures to govern sequential robotic tasks. The networks are systematically designed to map the environmental observations to motor actions, by their hierarchical topology from sensory neurons, through recurrently-wired interneurons, to motor neurons. The networks are then parametrized in a supervised-learning scheme by a search-based algorithm. We demonstrate that obtained networks realize interpretable dynamics. We evaluate their performance in controlling mobile and arm robots, and compare their attributes to other artificial neural network-based control agents. Finally, we experimentally show their superior resilience to environmental noise, compared to the existing machine learning-based methods. AU - Lechner, Mathias AU - Hasani, Ramin AU - Zimmer, Manuel AU - Henzinger, Thomas A AU - Grosu, Radu ID - 6888 SN - 9781538660270 T2 - Proceedings - IEEE International Conference on Robotics and Automation TI - Designing worm-inspired neural networks for interpretable robotic control VL - 2019-May ER - TY - CONF AB - In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the winner of the game. Such games are central in formal methods since they model the interaction between a non-terminating system and its environment. In bidding games the players bid for the right to move the token: in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. Bidding games are known to have a clean and elegant mathematical structure that relies on the ability of the players to submit arbitrarily small bids. Many applications, however, require a fixed granularity for the bids, which can represent, for example, the monetary value expressed in cents. We study, for the first time, the combination of discrete-bidding and infinite-duration games. Our most important result proves that these games form a large determined subclass of concurrent games, where determinacy is the strong property that there always exists exactly one player who can guarantee winning the game. In particular, we show that, in contrast to non-discrete bidding games, the mechanism with which tied bids are resolved plays an important role in discrete-bidding games. We study several natural tie-breaking mechanisms and show that, while some do not admit determinacy, most natural mechanisms imply determinacy for every pair of initial budgets. AU - Aghajohari, Milad AU - Avni, Guy AU - Henzinger, Thomas A ID - 6886 TI - Determinacy in discrete-bidding infinite-duration games VL - 140 ER - TY - CONF AB - A vector addition system with states (VASS) consists of a finite set of states and counters. A configuration is a state and a value for each counter; a transition changes the state and each counter is incremented, decremented, or left unchanged. While qualitative properties such as state and configuration reachability have been studied for VASS, we consider the long-run average cost of infinite computations of VASS. The cost of a configuration is for each state, a linear combination of the counter values. In the special case of uniform cost functions, the linear combination is the same for all states. The (regular) long-run emptiness problem is, given a VASS, a cost function, and a threshold value, if there is a (lasso-shaped) computation such that the long-run average value of the cost function does not exceed the threshold. For uniform cost functions, we show that the regular long-run emptiness problem is (a) decidable in polynomial time for integer-valued VASS, and (b) decidable but nonelementarily hard for natural-valued VASS (i.e., nonnegative counters). For general cost functions, we show that the problem is (c) NP-complete for integer-valued VASS, and (d) undecidable for natural-valued VASS. Our most interesting result is for (c) integer-valued VASS with general cost functions, where we establish a connection between the regular long-run emptiness problem and quadratic Diophantine inequalities. The general (nonregular) long-run emptiness problem is equally hard as the regular problem in all cases except (c), where it remains open. AU - Chatterjee, Krishnendu AU - Henzinger, Thomas A AU - Otop, Jan ID - 6885 TI - Long-run average behavior of vector addition systems with states VL - 140 ER - TY - CONF AB - We study Markov decision processes and turn-based stochastic games with parity conditions. There are three qualitative winning criteria, namely, sure winning, which requires all paths to satisfy the condition, almost-sure winning, which requires the condition to be satisfied with probability 1, and limit-sure winning, which requires the condition to be satisfied with probability arbitrarily close to 1. We study the combination of two of these criteria for parity conditions, e.g., there are two parity conditions one of which must be won surely, and the other almost-surely. The problem has been studied recently by Berthon et al. for MDPs with combination of sure and almost-sure winning, under infinite-memory strategies, and the problem has been established to be in NP cap co-NP. Even in MDPs there is a difference between finite-memory and infinite-memory strategies. Our main results for combination of sure and almost-sure winning are as follows: (a) we show that for MDPs with finite-memory strategies the problem is in NP cap co-NP; (b) we show that for turn-based stochastic games the problem is co-NP-complete, both for finite-memory and infinite-memory strategies; and (c) we present algorithmic results for the finite-memory case, both for MDPs and turn-based stochastic games, by reduction to non-stochastic parity games. In addition we show that all the above complexity results also carry over to combination of sure and limit-sure winning, and results for all other combinations can be derived from existing results in the literature. Thus we present a complete picture for the study of combinations of two qualitative winning criteria for parity conditions in MDPs and turn-based stochastic games. AU - Chatterjee, Krishnendu AU - Piterman, Nir ID - 6889 TI - Combinations of Qualitative Winning for Stochastic Parity Games VL - 140 ER - TY - CONF AB - Consider a distributed system with n processors out of which f can be Byzantine faulty. In the approximate agreement task, each processor i receives an input value xi and has to decide on an output value yi such that 1. the output values are in the convex hull of the non-faulty processors’ input values, 2. the output values are within distance d of each other. Classically, the values are assumed to be from an m-dimensional Euclidean space, where m ≥ 1. In this work, we study the task in a discrete setting, where input values with some structure expressible as a graph. Namely, the input values are vertices of a finite graph G and the goal is to output vertices that are within distance d of each other in G, but still remain in the graph-induced convex hull of the input values. For d = 0, the task reduces to consensus and cannot be solved with a deterministic algorithm in an asynchronous system even with a single crash fault. For any d ≥ 1, we show that the task is solvable in asynchronous systems when G is chordal and n > (ω + 1)f, where ω is the clique number of G. In addition, we give the first Byzantine-tolerant algorithm for a variant of lattice agreement. For synchronous systems, we show tight resilience bounds for the exact variants of these and related tasks over a large class of combinatorial structures. AU - Nowak, Thomas AU - Rybicki, Joel ID - 6931 KW - consensus KW - approximate agreement KW - Byzantine faults KW - chordal graphs KW - lattice agreement T2 - 33rd International Symposium on Distributed Computing TI - Byzantine approximate agreement on graphs VL - 146 ER - TY - CONF AB - In this paper, we introduce a novel method to interpret recurrent neural networks (RNNs), particularly long short-term memory networks (LSTMs) at the cellular level. We propose a systematic pipeline for interpreting individual hidden state dynamics within the network using response characterization methods. The ranked contribution of individual cells to the network's output is computed by analyzing a set of interpretable metrics of their decoupled step and sinusoidal responses. As a result, our method is able to uniquely identify neurons with insightful dynamics, quantify relationships between dynamical properties and test accuracy through ablation analysis, and interpret the impact of network capacity on a network's dynamical distribution. Finally, we demonstrate the generalizability and scalability of our method by evaluating a series of different benchmark sequential datasets. AU - Hasani, Ramin AU - Amini, Alexander AU - Lechner, Mathias AU - Naser, Felix AU - Grosu, Radu AU - Rus, Daniela ID - 6985 SN - 9781728119854 T2 - Proceedings of the International Joint Conference on Neural Networks TI - Response characterization for auditing cell dynamics in long short-term memory networks ER - TY - JOUR AB - We consider the primitive relay channel, where the source sends a message to the relay and to the destination, and the relay helps the communication by transmitting an additional message to the destination via a separate channel. Two well-known coding techniques have been introduced for this setting: decode-and-forward and compress-and-forward. In decode-and-forward, the relay completely decodes the message and sends some information to the destination; in compress-and-forward, the relay does not decode, and it sends a compressed version of the received signal to the destination using Wyner–Ziv coding. In this paper, we present a novel coding paradigm that provides an improved achievable rate for the primitive relay channel. The idea is to combine compress-and-forward and decode-and-forward via a chaining construction. We transmit over pairs of blocks: in the first block, we use compress-and-forward; and, in the second block, we use decode-and-forward. More specifically, in the first block, the relay does not decode, it compresses the received signal via Wyner–Ziv, and it sends only part of the compression to the destination. In the second block, the relay completely decodes the message, it sends some information to the destination, and it also sends the remaining part of the compression coming from the first block. By doing so, we are able to strictly outperform both compress-and-forward and decode-and-forward. Note that the proposed coding scheme can be implemented with polar codes. As such, it has the typical attractive properties of polar coding schemes, namely, quasi-linear encoding and decoding complexity, and error probability that decays at super-polynomial speed. As a running example, we take into account the special case of the erasure relay channel, and we provide a comparison between the rates achievable by our proposed scheme and the existing upper and lower bounds. AU - Mondelli, Marco AU - Hassani, S. Hamed AU - Urbanke, Rüdiger ID - 7007 IS - 10 JF - Algorithms SN - 1999-4893 TI - A new coding paradigm for the primitive relay channel VL - 12 ER - TY - CONF AB - The aim of this short note is to expound one particular issue that was discussed during the talk [10] given at the symposium ”Researches on isometries as preserver problems and related topics” at Kyoto RIMS. That is, the role of Dirac masses by describing the isometry group of various metric spaces of probability measures. This article is of survey character, and it does not contain any essentially new results.From an isometric point of view, in some cases, metric spaces of measures are similar to C(K)-type function spaces. Similarity means here that their isometries are driven by some nice transformations of the underlying space. Of course, it depends on the particular choice of the metric how nice these transformations should be. Sometimes, as we will see, being a homeomorphism is enough to generate an isometry. But sometimes we need more: the transformation must preserve the underlying distance as well. Statements claiming that isometries in questions are necessarily induced by homeomorphisms are called Banach-Stone-type results, while results asserting that the underlying transformation is necessarily an isometry are termed as isometric rigidity results.As Dirac masses can be considered as building bricks of the set of all Borel measures, a natural question arises:Is it enough to understand how an isometry acts on the set of Dirac masses? Does this action extend uniquely to all measures?In what follows, we will thoroughly investigate this question. AU - Geher, Gyorgy Pal AU - Titkos, Tamas AU - Virosztek, Daniel ID - 7035 T2 - Kyoto RIMS Kôkyûroku TI - Dirac masses and isometric rigidity VL - 2125 ER - TY - JOUR AB - A recent class of topological nodal-line semimetals with the general formula MSiX (M = Zr, Hf and X = S, Se, Te) has attracted much experimental and theoretical interest due to their properties, particularly their large magnetoresistances and high carrier mobilities. The plateletlike nature of the MSiX crystals and their extremely low residual resistivities make measurements of the resistivity along the [001] direction extremely challenging. To accomplish such measurements, microstructures of single crystals were prepared using focused ion beam techniques. Microstructures prepared in this manner have very well-defined geometries and maintain their high crystal quality, verified by the observations of quantum oscillations. We present magnetoresistance and quantum oscillation data for currents applied along both [001] and [100] in ZrSiS and ZrSiSe, which are consistent with the nontrivial topology of the Dirac line-node, as determined by a measured π Berry phase. Surprisingly, we find that, despite the three dimensional nature of both the Fermi surfaces of ZrSiS and ZrSiSe, both the resistivity anisotropy under applied magnetic fields and the in-plane angular dependent magnetoresistance differ considerably between the two compounds. Finally, we discuss the role microstructuring can play in the study of these materials and our ability to make these microstructures free-standing. AU - Shirer, Kent R. AU - Modic, Kimberly A AU - Zimmerling, Tino AU - Bachmann, Maja D. AU - König, Markus AU - Moll, Philip J. W. AU - Schoop, Leslie AU - Mackenzie, Andrew P. ID - 7055 IS - 10 JF - APL Materials SN - 2166-532X TI - Out-of-plane transport in ZrSiS and ZrSiSe microstructures VL - 7 ER - TY - JOUR AB - We present a high magnetic field study of NbP—a member of the monopnictide Weyl semimetal (WSM) family. While the monoarsenides (NbAs and TaAs) have topologically distinct left and right-handed Weyl fermi surfaces, NbP is argued to be “topologically trivial” due to the fact that all pairs of Weyl nodes are encompassed by a single Fermi surface. We use torque magnetometry to measure the magnetic response of NbP up to 60 tesla and uncover a Berry paramagnetic response, characteristic of the topological Weyl nodes, across the entire field range. At the quantum limit B* (≈32 T), τ/B experiences a change in slope when the chemical potential enters the last Landau level. Our calculations confirm that this magnetic response arises from band topology of the Weyl pocket, even though the Fermi surface encompasses both Weyl nodes at zero magnetic field. We also find that the magnetic field pulls the chemical potential to the chiral n = 0 Landau level in the quantum limit, providing a disorder-free way of accessing chiral Weyl fermions in systems that are “not quite” WSMs in zero magnetic field. AU - Modic, Kimberly A AU - Meng, Tobias AU - Ronning, Filip AU - Bauer, Eric D. AU - Moll, Philip J. W. AU - Ramshaw, B. J. ID - 7057 IS - 1 JF - Scientific Reports SN - 2045-2322 TI - Thermodynamic signatures of Weyl fermions in NbP VL - 9 ER - TY - JOUR AB - In the Ca1−x La x FeAs2 (1 1 2) family of pnictide superconductors, we have investigated a highly overdoped composition (x  =  0.56), prepared by a high-pressure, high-temperature synthesis. Magnetic measurements show an antiferromagnetic transition at T N  =  120 K, well above the one at lower doping (0.15  <  x  <  0.27). Below the onset of long-range magnetic order at T N, the electrical resistivity is strongly reduced and is dominated by electron–electron interactions, as evident from its temperature dependence. The Seebeck coefficient shows a clear metallic behavior as in narrow band conductors. The temperature dependence of the Hall coefficient and the violation of Kohler's rule agree with the multiband character of the material. No superconductivity was observed down to 1.8 K. The success of the high-pressure synthesis encourages further investigations of the so far only partially explored phase diagram in this family of Iron-based high temperature superconductors. AU - Martino, Edoardo AU - Bachmann, Maja D AU - Rossi, Lidia AU - Modic, Kimberly A AU - Zivkovic, Ivica AU - Rønnow, Henrik M AU - Moll, Philip J W AU - Akrap, Ana AU - Forró, László AU - Katrych, Sergiy ID - 7056 IS - 48 JF - Journal of Physics: Condensed Matter SN - 0953-8984 TI - Persistent antiferromagnetic order in heavily overdoped Ca1−x La x FeAs2 VL - 31 ER - TY - JOUR AB - Although crystals of strongly correlated metals exhibit a diverse set of electronic ground states, few approaches exist for spatially modulating their properties. In this study, we demonstrate disorder-free control, on the micrometer scale, over the superconducting state in samples of the heavy-fermion superconductor CeIrIn5. We pattern crystals by focused ion beam milling to tailor the boundary conditions for the elastic deformation upon thermal contraction during cooling. The resulting nonuniform strain fields induce complex patterns of superconductivity, owing to the strong dependence of the transition temperature on the strength and direction of strain. These results showcase a generic approach to manipulating electronic order on micrometer length scales in strongly correlated matter without compromising the cleanliness, stoichiometry, or mean free path. AU - Bachmann, Maja D. AU - Ferguson, G. M. AU - Theuss, Florian AU - Meng, Tobias AU - Putzke, Carsten AU - Helm, Toni AU - Shirer, K. R. AU - Li, You-Sheng AU - Modic, Kimberly A AU - Nicklas, Michael AU - König, Markus AU - Low, D. AU - Ghosh, Sayak AU - Mackenzie, Andrew P. AU - Arnold, Frank AU - Hassinger, Elena AU - McDonald, Ross D. AU - Winter, Laurel E. AU - Bauer, Eric D. AU - Ronning, Filip AU - Ramshaw, B. J. AU - Nowack, Katja C. AU - Moll, Philip J. W. ID - 7082 IS - 6462 JF - Science SN - 0036-8075 TI - Spatial control of heavy-fermion superconductivity in CeIrIn5 VL - 366 ER - TY - JOUR AB - Loss of functional cardiomyocytes is a major determinant of heart failure after myocardial infarction. Previous high throughput screening studies have identified a few microRNAs (miRNAs) that can induce cardiomyocyte proliferation and stimulate cardiac regeneration in mice. Here, we show that all of the most effective of these miRNAs activate nuclear localization of the master transcriptional cofactor Yes-associated protein (YAP) and induce expression of YAP-responsive genes. In particular, miR-199a-3p directly targets two mRNAs coding for proteins impinging on the Hippo pathway, the upstream YAP inhibitory kinase TAOK1, and the E3 ubiquitin ligase β-TrCP, which leads to YAP degradation. Several of the pro-proliferative miRNAs (including miR-199a-3p) also inhibit filamentous actin depolymerization by targeting Cofilin2, a process that by itself activates YAP nuclear translocation. Thus, activation of YAP and modulation of the actin cytoskeleton are major components of the pro-proliferative action of miR-199a-3p and other miRNAs that induce cardiomyocyte proliferation. AU - Torrini, Consuelo AU - Cubero, Ryan J AU - Dirkx, Ellen AU - Braga, Luca AU - Ali, Hashim AU - Prosdocimo, Giulia AU - Gutierrez, Maria Ines AU - Collesi, Chiara AU - Licastro, Danilo AU - Zentilin, Lorena AU - Mano, Miguel AU - Zacchigna, Serena AU - Vendruscolo, Michele AU - Marsili, Matteo AU - Samal, Areejit AU - Giacca, Mauro ID - 7128 IS - 9 JF - Cell Reports KW - cardiomyocyte KW - cell cycle KW - Cofilin2 KW - cytoskeleton KW - Hippo KW - microRNA KW - regeneration KW - YAP SN - 2211-1247 TI - Common regulatory pathways mediate activity of microRNAs inducing cardiomyocyte proliferation VL - 27 ER - TY - JOUR AB - We show that statistical criticality, i.e. the occurrence of power law frequency distributions, arises in samples that are maximally informative about the underlying generating process. In order to reach this conclusion, we first identify the frequency with which different outcomes occur in a sample, as the variable carrying useful information on the generative process. The entropy of the frequency, that we call relevance, provides an upper bound to the number of informative bits. This differs from the entropy of the data, that we take as a measure of resolution. Samples that maximise relevance at a given resolution—that we call maximally informative samples—exhibit statistical criticality. In particular, Zipf's law arises at the optimal trade-off between resolution (i.e. compression) and relevance. As a byproduct, we derive a bound of the maximal number of parameters that can be estimated from a dataset, in the absence of prior knowledge on the generative model. Furthermore, we relate criticality to the statistical properties of the representation of the data generating process. We show that, as a consequence of the concentration property of the asymptotic equipartition property, representations that are maximally informative about the data generating process are characterised by an exponential distribution of energy levels. This arises from a principle of minimal entropy, that is conjugate of the maximum entropy principle in statistical mechanics. This explains why statistical criticality requires no parameter fine tuning in maximally informative samples. AU - Cubero, Ryan J AU - Jo, Junghyo AU - Marsili, Matteo AU - Roudi, Yasser AU - Song, Juyong ID - 7130 IS - 6 JF - Journal of Statistical Mechanics: Theory and Experiment KW - optimization under uncertainty KW - source coding KW - large deviation SN - 1742-5468 TI - Statistical criticality arises in most informative representations VL - 2019 ER - TY - JOUR AB - In this work, we use algebraic methods for studying distance computation and subgraph detection tasks in the congested clique model. Specifically, we adapt parallel matrix multiplication implementations to the congested clique, obtaining an O(n1−2/ω) round matrix multiplication algorithm, where ω<2.3728639 is the exponent of matrix multiplication. In conjunction with known techniques from centralised algorithmics, this gives significant improvements over previous best upper bounds in the congested clique model. The highlight results include: 1. triangle and 4-cycle counting in O(n0.158) rounds, improving upon the O(n1/3) algorithm of Dolev et al. [DISC 2012], 2. a (1+o(1))-approximation of all-pairs shortest paths in O(n0.158) rounds, improving upon the O~(n1/2)-round (2+o(1))-approximation algorithm given by Nanongkai [STOC 2014], and 3. computing the girth in O(n0.158) rounds, which is the first non-trivial solution in this model. In addition, we present a novel constant-round combinatorial algorithm for detecting 4-cycles. AU - Censor-Hillel, Keren AU - Kaski, Petteri AU - Korhonen, Janne AU - Lenzen, Christoph AU - Paz, Ami AU - Suomela, Jukka ID - 7150 IS - 6 JF - Distributed Computing SN - 0178-2770 TI - Algebraic methods in the congested clique VL - 32 ER - TY - BOOK AB - Wissen Sie, was sich hinter künstlicher Intelligenz und maschinellem Lernen verbirgt? Dieses Sachbuch erklärt Ihnen leicht verständlich und ohne komplizierte Formeln die grundlegenden Methoden und Vorgehensweisen des maschinellen Lernens. Mathematisches Vorwissen ist dafür nicht nötig. Kurzweilig und informativ illustriert Lisa, die Protagonistin des Buches, diese anhand von Alltagssituationen. Ein Buch für alle, die in Diskussionen über Chancen und Risiken der aktuellen Entwicklung der künstlichen Intelligenz und des maschinellen Lernens mit Faktenwissen punkten möchten. Auch für Schülerinnen und Schüler geeignet! ED - Kersting, Kristian ED - Lampert, Christoph ED - Rothkopf, Constantin ID - 7171 SN - 978-3-658-26762-9 TI - Wie Maschinen Lernen: Künstliche Intelligenz Verständlich Erklärt ER - TY - JOUR AB - Aprotic alkali metal–oxygen batteries require reversible formation of metal superoxide or peroxide on cycling. Severe parasitic reactions cause poor rechargeability, efficiency, and cycle life and have been shown to be caused by singlet oxygen (1O2) that forms at all stages of cycling. However, its formation mechanism remains unclear. We show that disproportionation of superoxide, the product or intermediate on discharge and charge, to peroxide and oxygen is responsible for 1O2 formation. While the overall reaction is driven by the stability of peroxide and thus favored by stronger Lewis acidic cations such as Li+, the 1O2 fraction is enhanced by weak Lewis acids such as organic cations. Concurrently, the metal peroxide yield drops with increasing 1O2. The results explain a major parasitic pathway during cell cycling and the growing severity in K–, Na–, and Li–O2 cells based on the growing propensity for disproportionation. High capacities and rates with peroxides are now realized to require solution processes, which form peroxide or release O2via disproportionation. The results therefore establish the central dilemma that disproportionation is required for high capacity but also responsible for irreversible reactions. Highly reversible cell operation requires hence finding reaction routes that avoid disproportionation. AU - Mourad, Eléonore AU - Petit, Yann K. AU - Spezia, Riccardo AU - Samojlov, Aleksej AU - Summa, Francesco F. AU - Prehal, Christian AU - Leypold, Christian AU - Mahne, Nika AU - Slugovc, Christian AU - Fontaine, Olivier AU - Brutti, Sergio AU - Freunberger, Stefan Alexander ID - 7275 IS - 8 JF - Energy & Environmental Science SN - 1754-5692 TI - Singlet oxygen from cation driven superoxide disproportionation and consequences for aprotic metal–O2 batteries VL - 12 ER - TY - JOUR AB - Non-aqueous lithium-oxygen batteries cycle by forming lithium peroxide during discharge and oxidizing it during recharge. The significant problem of oxidizing the solid insulating lithium peroxide can greatly be facilitated by incorporating redox mediators that shuttle electron-holes between the porous substrate and lithium peroxide. Redox mediator stability is thus key for energy efficiency, reversibility, and cycle life. However, the gradual deactivation of redox mediators during repeated cycling has not conclusively been explained. Here, we show that organic redox mediators are predominantly decomposed by singlet oxygen that forms during cycling. Their reaction with superoxide, previously assumed to mainly trigger their degradation, peroxide, and dioxygen, is orders of magnitude slower in comparison. The reduced form of the mediator is markedly more reactive towards singlet oxygen than the oxidized form, from which we derive reaction mechanisms supported by density functional theory calculations. Redox mediators must thus be designed for stability against singlet oxygen. AU - Kwak, Won-Jin AU - Kim, Hun AU - Petit, Yann K. AU - Leypold, Christian AU - Nguyen, Trung Thien AU - Mahne, Nika AU - Redfern, Paul AU - Curtiss, Larry A. AU - Jung, Hun-Gi AU - Borisov, Sergey M. AU - Freunberger, Stefan Alexander AU - Sun, Yang-Kook ID - 7280 JF - Nature Communications SN - 2041-1723 TI - Deactivation of redox mediators in lithium-oxygen batteries by singlet oxygen VL - 10 ER - TY - JOUR AB - Singlet oxygen (1O2) causes a major fraction of the parasitic chemistry during the cycling of non‐aqueous alkali metal‐O2 batteries and also contributes to interfacial reactivity of transition‐metal oxide intercalation compounds. We introduce DABCOnium, the mono alkylated form of 1,4‐diazabicyclo[2.2.2]octane (DABCO), as an efficient 1O2 quencher with an unusually high oxidative stability of ca. 4.2 V vs. Li/Li+. Previous quenchers are strongly Lewis basic amines with too low oxidative stability. DABCOnium is an ionic liquid, non‐volatile, highly soluble in the electrolyte, stable against superoxide and peroxide, and compatible with lithium metal. The electrochemical stability covers the required range for metal–O2 batteries and greatly reduces 1O2 related parasitic chemistry as demonstrated for the Li–O2 cell. AU - Petit, Yann K. AU - Leypold, Christian AU - Mahne, Nika AU - Mourad, Eléonore AU - Schafzahl, Lukas AU - Slugovc, Christian AU - Borisov, Sergey M. AU - Freunberger, Stefan Alexander ID - 7276 IS - 20 JF - Angewandte Chemie International Edition SN - 1433-7851 TI - DABCOnium: An efficient and high-voltage stable singlet oxygen quencher for metal-O2 cells VL - 58 ER - TY - JOUR AB - Li–O2 batteries are plagued by side reactions that cause poor rechargeability and efficiency. These reactions were recently revealed to be predominantly caused by singlet oxygen, which can be neutralized by chemical traps or physical quenchers. However, traps are irreversibly consumed and thus only active for a limited time, and so far identified quenchers lack oxidative stability to be suitable for typically required recharge potentials. Thus, reducing the charge potential within the stability limit of the quencher and/or finding more stable quenchers is required. Here, we show that dimethylphenazine as a redox mediator decreases the charge potential well within the stability limit of the quencher 1,4-diazabicyclo[2.2.2]octane. The quencher can thus mitigate the parasitic reactions without being oxidatively decomposed. At the same time the quencher protects the redox mediator from singlet oxygen attack. The mutual conservation of the redox mediator and the quencher is rational for stable and effective Li–O2 batteries. AU - Kwak, Won-Jin AU - Freunberger, Stefan Alexander AU - Kim, Hun AU - Park, Jiwon AU - Nguyen, Trung Thien AU - Jung, Hun-Gi AU - Byon, Hye Ryung AU - Sun, Yang-Kook ID - 7281 IS - 11 JF - ACS Catalysis SN - 2155-5435 TI - Mutual conservation of redox mediator and singlet oxygen quencher in Lithium–Oxygen batteries VL - 9 ER - TY - JOUR AB - Interphases that form on the anode surface of lithium-ion batteries are critical for performance and lifetime, but are poorly understood. Now, a decade-old misconception regarding a main component of the interphase has been revealed, which could potentially lead to improved devices. AU - Freunberger, Stefan Alexander ID - 7282 IS - 9 JF - Nature Chemistry SN - 1755-4330 TI - Interphase identity crisis VL - 11 ER - TY - JOUR AB - Potassium–air batteries, which suffer from oxygen cathode and potassium metal anode degradation, can be cycled thousands of times when an organic anode replaces the metal. AU - Petit, Yann K. AU - Freunberger, Stefan Alexander ID - 7283 IS - 4 JF - Nature Materials SN - 1476-1122 TI - Thousands of cycles VL - 18 ER - TY - JOUR AB - In this issue of Joule, Dongmin Im and coworkers from Samsung in South Korea describe a prototype lithium-O2 battery that reaches ∼700 Wh kg–1 and ∼600 Wh L–1 on the cell level. They cut all components to the minimum to reach this value. Difficulties filling the pores with discharge product and inhomogeneous cell utilization turn out to limit the achievable energy. Their work underlines the importance of reporting performance with respect to full cell weight and volume. AU - Prehal, Christian AU - Freunberger, Stefan Alexander ID - 7284 IS - 2 JF - Joule SN - 2542-4351 TI - Li-O2 cell-scale energy densities VL - 3 ER - TY - GEN AB - Telencephalic organoids generated from human pluripotent stem cells (hPSCs) are emerging as an effective system to study the distinct features of the developing human brain and the underlying causes of many neurological disorders. While progress in organoid technology has been steadily advancing, many challenges remain including rampant batch-to-batch and cell line-to-cell line variability and irreproducibility. Here, we demonstrate that a major contributor to successful cortical organoid production is the manner in which hPSCs are maintained prior to differentiation. Optimal results were achieved using fibroblast-feeder-supported hPSCs compared to feeder-independent cells, related to differences in their transcriptomic states. Feeder-supported hPSCs display elevated activation of diverse TGFβ superfamily signaling pathways and increased expression of genes associated with naïve pluripotency. We further identify combinations of TGFβ-related growth factors that are necessary and together sufficient to impart broad telencephalic organoid competency to feeder-free hPSCs and enable reproducible formation of brain structures suitable for disease modeling. AU - Watanabe, Momoko AU - Haney, Jillian R. AU - Vishlaghi, Neda AU - Turcios, Felix AU - Buth, Jessie E. AU - Gu, Wen AU - Collier, Amanda J. AU - Miranda, Osvaldo AU - Chen, Di AU - Sabri, Shan AU - Clark, Amander T. AU - Plath, Kathrin AU - Christofk, Heather R. AU - Gandal, Michael J. AU - Novitch, Bennett G. ID - 7358 T2 - bioRxiv TI - TGFβ superfamily signaling regulates the state of human stem cell pluripotency and competency to create telencephalic organoids ER - TY - CONF AB - The genus g(G) of a graph G is the minimum g such that G has an embedding on the orientable surface M_g of genus g. A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z_2-genus of a graph G, denoted by g_0(G), is the minimum g such that G has an independently even drawing on M_g. By a result of Battle, Harary, Kodama and Youngs from 1962, the graph genus is additive over 2-connected blocks. In 2013, Schaefer and Stefankovic proved that the Z_2-genus of a graph is additive over 2-connected blocks as well, and asked whether this result can be extended to so-called 2-amalgamations, as an analogue of results by Decker, Glover, Huneke, and Stahl for the genus. We give the following partial answer. If G=G_1 cup G_2, G_1 and G_2 intersect in two vertices u and v, and G-u-v has k connected components (among which we count the edge uv if present), then |g_0(G)-(g_0(G_1)+g_0(G_2))|<=k+1. For complete bipartite graphs K_{m,n}, with n >= m >= 3, we prove that g_0(K_{m,n})/g(K_{m,n})=1-O(1/n). Similar results are proved also for the Euler Z_2-genus. We express the Z_2-genus of a graph using the minimum rank of partial symmetric matrices over Z_2; a problem that might be of independent interest. AU - Fulek, Radoslav AU - Kyncl, Jan ID - 7401 SN - 1868-8969 T2 - 35th International Symposium on Computational Geometry (SoCG 2019) TI - Z_2-Genus of graphs and minimum rank of partial symmetric matrices VL - 129 ER - TY - CHAP AB - We illustrate the ingredients of the state-of-the-art of model-based approach for the formal design and verification of cyber-physical systems. To capture the interaction between a discrete controller and its continuously evolving environment, we use the formal models of timed and hybrid automata. We explain the steps of modeling and verification in the tools Uppaal and SpaceEx using a case study based on a dual-chamber implantable pacemaker monitoring a human heart. We show how to design a model as a composition of components, how to construct models at varying levels of detail, how to establish that one model is an abstraction of another, how to specify correctness requirements using temporal logic, and how to verify that a model satisfies a logical requirement. AU - Alur, Rajeev AU - Giacobbe, Mirco AU - Henzinger, Thomas A AU - Larsen, Kim G. AU - Mikučionis, Marius ED - Steffen, Bernhard ED - Woeginger, Gerhard ID - 7453 SN - 1611-3349 T2 - Computing and Software Science TI - Continuous-time models for system design and analysis VL - 10000 ER - TY - JOUR AB - We report the fabrication of BaTiO3-Ni magnetoelectric nanocomposites comprising of BaTiO3 nanotubes surrounded by Ni matrix. BaTiO3 nanotubes obtained from the hydrothermal transformation of TiO2 have both inner and outer surfaces, which facilitates greater magnetoelectric coupling with the surrounding Ni matrix. The magnetoelectric coupling was studied by measuring the piezoelectric behavior in the presence of an in-plane direct magnetic field. A higher magnetoelectric voltage coefficient of 110 mV/cm·Oe was obtained, because of better coupling between Ni and BaTiO3 through the walls of the nanotubes. Such nanocomposite developed directly on Ti substrate may lead to efficient fabrication of magnetoelectric devices. AU - Vadla, Samba Siva AU - Costanzo, Tommaso AU - John, Subish AU - Caruntu, Gabriel AU - Roy, Somnath C. ID - 7459 JF - Scripta Materialia SN - 1359-6462 TI - Local probing of magnetoelectric coupling in BaTiO3-Ni 1–3 composites VL - 159 ER - TY - JOUR AB - The sebaceous gland (SG) is an essential component of the skin, and SG dysfunction is debilitating1,2. Yet, the cellular bases for its origin, development and subsequent maintenance remain poorly understood. Here, we apply large-scale quantitative fate mapping to define the patterns of cell fate behaviour during SG development and maintenance. We show that the SG develops from a defined number of lineage-restricted progenitors that undergo a programme of independent and stochastic cell fate decisions. Following an expansion phase, equipotent progenitors transition into a phase of homeostatic turnover, which is correlated with changes in the mechanical properties of the stroma and spatial restrictions on gland size. Expression of the oncogene KrasG12D results in a release from these constraints and unbridled gland expansion. Quantitative clonal fate analysis reveals that, during this phase, the primary effect of the Kras oncogene is to drive a constant fate bias with little effect on cell division rates. These findings provide insight into the developmental programme of the SG, as well as the mechanisms that drive tumour progression and gland dysfunction. AU - Andersen, Marianne Stemann AU - Hannezo, Edouard B AU - Ulyanchenko, Svetlana AU - Estrach, Soline AU - Antoku, Yasuko AU - Pisano, Sabrina AU - Boonekamp, Kim E. AU - Sendrup, Sarah AU - Maimets, Martti AU - Pedersen, Marianne Terndrup AU - Johansen, Jens V. AU - Clement, Ditte L. AU - Feral, Chloe C. AU - Simons, Benjamin D. AU - Jensen, Kim B. ID - 7476 IS - 8 JF - Nature Cell Biology SN - 1465-7392 TI - Tracing the cellular dynamics of sebaceous gland development in normal and perturbed states VL - 21 ER - TY - JOUR AB - Although the aggregation of the amyloid-β peptide (Aβ) into amyloid fibrils is a well-established hallmark of Alzheimer’s disease, the complex mechanisms linking this process to neurodegeneration are still incompletely understood. The nematode worm C. elegans is a valuable model organism through which to study these mechanisms because of its simple nervous system and its relatively short lifespan. Standard Aβ-based C. elegans models of Alzheimer’s disease are designed to study the toxic effects of the overexpression of Aβ in the muscle or nervous systems. However, the wide variety of effects associated with the tissue-level overexpression of Aβ makes it difficult to single out and study specific cellular mechanisms related to the onset of Alzheimer’s disease. Here, to better understand how to investigate the early events affecting neuronal signalling, we created a C. elegans model expressing Aβ42, the 42-residue form of Aβ, from a single-copy gene insertion in just one pair of glutamatergic sensory neurons, the BAG neurons. In behavioural assays, we found that the Aβ42-expressing animals displayed a subtle modulation of the response to CO2, compared to controls. Ca2+ imaging revealed that the BAG neurons in young Aβ42-expressing nematodes were activated more strongly than in control animals, and that neuronal activation remained intact until old age. Taken together, our results suggest that Aβ42-expression in this very subtle model of AD is sufficient to modulate the behavioural response but not strong enough to generate significant neurotoxicity, suggesting that slightly more aggressive perturbations will enable effectively studies of the links between the modulation of a physiological response and its associated neurotoxicity. AU - Sinnige, Tessa AU - Ciryam, Prashanth AU - Casford, Samuel AU - Dobson, Christopher M. AU - de Bono, Mario AU - Vendruscolo, Michele ID - 7548 IS - 5 JF - PLOS ONE SN - 1932-6203 TI - Expression of the amyloid-β peptide in a single pair of C. elegans sensory neurons modulates the associated behavioural response VL - 14 ER - TY - JOUR AB - The BH3-only family of proteins is key for initiating apoptosis in a variety of contexts, and may also contribute to non-apoptotic cellular processes. Historically, the nematode Caenorhabditis elegans has provided a powerful system for studying and identifying conserved regulators of BH3-only proteins. In C. elegans, the BH3-only protein egl-1 is expressed during development to cell-autonomously trigger most developmental cell deaths. Here we provide evidence that egl-1 is also transcribed after development in the sensory neuron pair URX without inducing apoptosis. We used genetic screening and epistasis analysis to determine that its transcription is regulated in URX by neuronal activity and/or in parallel by orthologs of Protein Kinase G and the Salt-Inducible Kinase family. Because several BH3-only family proteins are also expressed in the adult nervous system of mammals, we suggest that studying egl-1 expression in URX may shed light on mechanisms that regulate conserved family members in higher organisms. AU - Cohn, Jesse AU - Dwivedi, Vivek AU - Valperga, Giulio AU - Zarate, Nicole AU - de Bono, Mario AU - Horvitz, H. Robert AU - Pierce, Jonathan T. ID - 7547 IS - 11 JF - G3: Genes, Genomes, Genetics SN - 2160-1836 TI - Activity-dependent regulation of the proapoptotic BH3-only gene egl-1 in a living neuron pair in Caenorhabditis elegans VL - 9 ER - TY - JOUR AB - We consider an optimal control problem for an abstract nonlinear dissipative evolution equation. The differential constraint is penalized by augmenting the target functional by a nonnegative global-in-time functional which is null-minimized in the evolution equation is satisfied. Different variational settings are presented, leading to the convergence of the penalization method for gradient flows, noncyclic and semimonotone flows, doubly nonlinear evolutions, and GENERIC systems. AU - Portinale, Lorenzo AU - Stefanelli, Ulisse ID - 7550 IS - 2 JF - Advances in Mathematical Sciences and Applications SN - 1343-4373 TI - Penalization via global functionals of optimal-control problems for dissipative evolution VL - 28 ER - TY - GEN AB - There is increasing evidence that protein binding to specific sites along DNA can activate the reading out of genetic information without coming into direct physical contact with the gene. There also is evidence that these distant but interacting sites are embedded in a liquid droplet of proteins which condenses out of the surrounding solution. We argue that droplet-mediated interactions can account for crucial features of gene regulation only if the droplet is poised at a non-generic point in its phase diagram. We explore a minimal model that embodies this idea, show that this model has a natural mechanism for self-tuning, and suggest direct experimental tests. AU - Bialek, William AU - Gregor, Thomas AU - Tkačik, Gašper ID - 7552 T2 - arXiv:1912.08579 TI - Action at a distance in transcriptional regulation ER - TY - CONF AB - We present the results of a friendly competition for formal verification of continuous and hybrid systems with nonlinear continuous dynamics. The friendly competition took place as part of the workshop Applied Verification for Continuous and Hybrid Systems (ARCH) in 2019. In this year, 6 tools Ariadne, CORA, DynIbex, Flow*, Isabelle/HOL, and JuliaReach (in alphabetic order) participated. They are applied to solve reachability analysis problems on four benchmark problems, one of them with hybrid dynamics. We do not rank the tools based on the results, but show the current status and discover the potential advantages of different tools. AU - Immler, Fabian AU - Althoff, Matthias AU - Benet, Luis AU - Chapoutot, Alexandre AU - Chen, Xin AU - Forets, Marcelo AU - Geretti, Luca AU - Kochdumper, Niklas AU - Sanders, David P. AU - Schilling, Christian ID - 7576 T2 - EPiC Series in Computing TI - ARCH-COMP19 Category Report: Continuous and hybrid systems with nonlinear dynamics VL - 61 ER - TY - GEN AB - Electrodepositing insulating and insoluble Li2O2 is the key process during discharge of aprotic Li-O2 batteries and determines rate, capacity, and reversibility. Current understanding states that the partition between surface adsorbed and solvated LiO2 governs whether Li2O2 grows as surface film, leading to low capacity even at low rates, or in solution, leading to particles and high capacities. Here we show that Li2O2 forms to the widest extent as particles via solution mediated LiO2 disproportionation. We describe a unified Li2O2 growth model that conclusively explains capacity limitations across the whole range of electrolytes. Deciding for particle morphology, achievable rate and capacities are species mobilities, electrode specific surface area (determining true areal rate) and the concentration distribution of associated LiO2 in solution. Provided that species mobilities and surface are high, high, capacities are possible even with low-donor-number electrolytes, previously considered prototypical for low capacity via surface growth. The tools for these insights are microscopy, hydrodynamic voltammetry, a numerical reaction model, and in situ small/wide angle X-ray scattering (SAXS/WAXS). Combined with sophisticated data analysis, SAXS allows retrieving rich quantitative information from complex multi-phase systems. On a wider perspective, this SAXS method is a powerful in situ metrology with atomic to sub-micron resolution to study mechanisms in complex electrochemical systems and beyond. AU - Prehal, Christian AU - Samojlov, Aleksej AU - Nachtnebel, Manfred AU - Kriechbaum, Manfred AU - Amenitsch, Heinz AU - Freunberger, Stefan Alexander ID - 7627 TI - A revised O2 reduction model in Li-O2 batteries as revealed by in situ small angle X-ray scattering ER - TY - JOUR AB - The number of human genomes being genotyped or sequenced increases exponentially and efficient haplotype estimation methods able to handle this amount of data are now required. Here we present a method, SHAPEIT4, which substantially improves upon other methods to process large genotype and high coverage sequencing datasets. It notably exhibits sub-linear running times with sample size, provides highly accurate haplotypes and allows integrating external phasing information such as large reference panels of haplotypes, collections of pre-phased variants and long sequencing reads. We provide SHAPEIT4 in an open source format and demonstrate its performance in terms of accuracy and running times on two gold standard datasets: the UK Biobank data and the Genome In A Bottle. AU - Delaneau, Olivier AU - Zagury, Jean-François AU - Robinson, Matthew Richard AU - Marchini, Jonathan L. AU - Dermitzakis, Emmanouil T. ID - 7710 JF - Nature Communications SN - 2041-1723 TI - Accurate, scalable and integrative haplotype estimation VL - 10 ER - TY - JOUR AB - The nature and extent of mitochondrial DNA variation in a population and how it affects traits is poorly understood. Here we resequence the mitochondrial genomes of 169 Drosophila Genetic Reference Panel lines, identifying 231 variants that stratify along 12 mitochondrial haplotypes. We identify 1,845 cases of mitonuclear allelic imbalances, thus implying that mitochondrial haplotypes are reflected in the nuclear genome. However, no major fitness effects are associated with mitonuclear imbalance, suggesting that such imbalances reflect population structure at the mitochondrial level rather than genomic incompatibilities. Although mitochondrial haplotypes have no direct impact on mitochondrial respiration, some haplotypes are associated with stress- and metabolism-related phenotypes, including food intake in males. Finally, through reciprocal swapping of mitochondrial genomes, we demonstrate that a mitochondrial haplotype associated with high food intake can rescue a low food intake phenotype. Together, our findings provide new insight into population structure at the mitochondrial level and point to the importance of incorporating mitochondrial haplotypes in genotype–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 - 7711 IS - 12 JF - Nature Metabolism SN - 2522-5812 TI - Mitochondrial haplotypes affect metabolic phenotypes in the Drosophila Genetic Reference Panel VL - 1 ER - TY - GEN AB - As genome-wide association studies (GWAS) increased in size, numerous gene-environment interactions (GxE) have been discovered, many of which however explore only one environment at a time and may suffer from statistical artefacts leading to biased interaction estimates. Here we propose a maximum likelihood method to estimate the contribution of GxE to complex traits taking into account all interacting environmental variables at the same time, without the need to measure any. This is possible because GxE induces fluctuations in the conditional trait variance, the extent of which depends on the strength of GxE. The approach can be applied to continuous outcomes and for single SNPs or genetic risk scores (GRS). Extensive simulations demonstrated that our method yields unbiased interaction estimates and excellent confidence interval coverage. We also offer a strategy to distinguish specific GxE from general heteroscedasticity (scale effects). Applying our method to 32 complex traits in the UK Biobank reveals that for body mass index (BMI) the GRSxE explains an additional 1.9% variance on top of the 5.2% GRS contribution. However, this interaction is not specific to the GRS and holds for any variable similarly correlated with BMI. On the contrary, the GRSxE interaction effect for leg impedance Embedded Image is significantly (P < 10−56) larger than it would be expected for a similarly correlated variable Embedded Image. We showed that our method could robustly detect the global contribution of GxE to complex traits, which turned out to be substantial for certain obesity measures. AU - Sulc, Jonathan AU - Mounier, Ninon AU - Günther, Felix AU - Winkler, Thomas AU - Wood, Andrew R. AU - Frayling, Timothy M. AU - Heid, Iris M. AU - Robinson, Matthew Richard AU - Kutalik, Zoltán ID - 7782 T2 - bioRxiv TI - Maximum likelihood method quantifies the overall contribution of gene-environment interaction to continuous traits: An application to complex traits in the UK Biobank ER - TY - JOUR AU - Currin, Christopher B. AU - Khoza, Phumlani N. AU - Antrobus, Alexander D. AU - Latham, Peter E. AU - Vogels, Tim P AU - Raimondo, Joseph V. ID - 8013 IS - 7 JF - PLOS Computational Biology SN - 1553-7358 TI - Think: Theory for Africa VL - 15 ER - TY - JOUR AB - Working memory, the ability to keep recently accessed information available for immediate manipulation, has been proposed to rely on two mechanisms that appear difficult to reconcile: self-sustained neural firing, or the opposite—activity-silent synaptic traces. Here we review and contrast models of these two mechanisms, and then show that both phenomena can co-exist within a unified system in which neurons hold information in both activity and synapses. Rapid plasticity in flexibly-coding neurons allows features to be bound together into objects, with an important emergent property being the focus of attention. One memory item is held by persistent activity in an attended or “focused” state, and is thus remembered better than other items. Other, previously attended items can remain in memory but in the background, encoded in activity-silent synaptic traces. This dual functional architecture provides a unified common mechanism accounting for a diversity of perplexing attention and memory effects that have been hitherto difficult to explain in a single theoretical framework. AU - Manohar, Sanjay G. AU - Zokaei, Nahid AU - Fallon, Sean J. AU - Vogels, Tim P AU - Husain, Masud ID - 8014 JF - Neuroscience and Biobehavioral Reviews SN - 0149-7634 TI - Neural mechanisms of attending to items in working memory VL - 101 ER - TY - CONF AB - We study edge asymptotics of poissonized Plancherel-type measures on skew Young diagrams (integer partitions). These measures can be seen as generalizations of those studied by Baik--Deift--Johansson and Baik--Rains in resolving Ulam's problem on longest increasing subsequences of random permutations and the last passage percolation (corner growth) discrete versions thereof. Moreover they interpolate between said measures and the uniform measure on partitions. In the new KPZ-like 1/3 exponent edge scaling limit with logarithmic corrections, we find new probability distributions generalizing the classical Tracy--Widom GUE, GOE and GSE distributions from the theory of random matrices. AU - Betea, Dan AU - Bouttier, Jérémie AU - Nejjar, Peter AU - Vuletíc, Mirjana ID - 8175 T2 - Proceedings on the 31st International Conference on Formal Power Series and Algebraic Combinatorics TI - New edge asymptotics of skew Young diagrams via free boundaries ER -