TY - JOUR
AB - A process of restorative patterning in plant roots correctly replaces eliminated cells to heal local injuries despite the absence of cell migration, which underpins wound healing in animals.
Patterning in plants relies on oriented cell divisions and acquisition of specific cell identities. Plants regularly endure wounds caused by abiotic or biotic environmental stimuli and have developed extraordinary abilities to restore their tissues after injuries. Here, we provide insight into a mechanism of restorative patterning that repairs tissues after wounding. Laser-assisted elimination of different cells in Arabidopsis root combined with live-imaging tracking during vertical growth allowed analysis of the regeneration processes in vivo. Specifically, the cells adjacent to the inner side of the injury re-activated their stem cell transcriptional programs. They accelerated their progression through cell cycle, coordinately changed the cell division orientation, and ultimately acquired de novo the correct cell fates to replace missing cells. These observations highlight existence of unknown intercellular positional signaling and demonstrate the capability of specified cells to re-acquire stem cell programs as a crucial part of the plant-specific mechanism of wound healing.
AU - Marhavá, Petra
AU - Hörmayer, Lukas
AU - Yoshida, Saiko
AU - Marhavy, Peter
AU - Benková, Eva
AU - Friml, Jiří
ID - 6351
IS - 4
JF - Cell
SN - 00928674
TI - Re-activation of stem cell pathways for pattern restoration in plant wound healing
VL - 177
ER -
TY - JOUR
AB - Chronic overuse of common pharmaceuticals, e.g. acetaminophen (paracetamol), often leads to the development of acute liver failure (ALF). This study aimed to elucidate the effect of cultured mesenchymal stem cells (MSCs) proteome on the onset of liver damage and regeneration dynamics in animals with ALF induced by acetaminophen, to test the liver protective efficacy of MSCs proteome depending on the oxygen tension in cell culture, and to blueprint protein components responsible for the effect. Protein compositions prepared from MSCs cultured in mild hypoxic (5% and 10% O2) and normal (21% O2) conditions were used to treat ALF induced in mice by injection of acetaminophen. To test the effect of reduced oxygen tension in cell culture on resulting MSCs proteome content we applied a combination of high performance liquid chromatography and mass-spectrometry (LC–MS/MS) for the identification of proteins in lysates of MSCs cultured at different O2 levels. The treatment of acetaminophen-administered animals with proteins released from cultured MSCs resulted in the inhibition of inflammatory reactions in damaged liver; the area of hepatocyte necrosis being reduced in the first 24 h. Compositions obtained from MSCs cultured at lower O2 level were shown to be more potent than a composition prepared from normoxic cells. A comparative characterization of protein pattern and identification of individual components done by a cytokine assay and proteomics analysis of protein compositions revealed that even moderate hypoxia produces discrete changes in the expression of various subsets of proteins responsible for intracellular respiration and cell signaling. The application of proteins prepared from MSCs grown in vitro at reduced oxygen tension significantly accelerates healing process in damaged liver tissue. The proteomics data obtained for different preparations offer new information about the potential candidates in the MSCs protein repertoire sensitive to oxygen tension in culture medium, which can be involved in the generalized mechanisms the cells use to respond to acute liver failure.
AU - Temnov, Andrey Alexandrovich
AU - Rogov, Konstantin Arkadevich
AU - Sklifas, Alla Nikolaevna
AU - Klychnikova, Elena Valerievna
AU - Hartl, Markus
AU - Djinovic-Carugo, Kristina
AU - Charnagalov, Alexej
ID - 6352
JF - Molecular Biology Reports
SN - 03014851
TI - Protective properties of the cultured stem cell proteome studied in an animal model of acetaminophen-induced acute liver failure
ER -
TY - JOUR
AB - Plants have a remarkable capacity to adjust their growth and development to elevated ambient temperatures. Increased elongation growth of roots, hypocotyls and petioles in warm temperatures are hallmarks of seedling thermomorphogenesis. In the last decade, significant progress has been made to identify the molecular signaling components regulating these growth responses. Increased ambient temperature utilizes diverse components of the light sensing and signal transduction network to trigger growth adjustments. However, it remains unknown whether temperature sensing and responses are universal processes that occur uniformly in all plant organs. Alternatively, temperature sensing may be confined to specific tissues or organs, which would require a systemic signal that mediates responses in distal parts of the plant. Here we show that Arabidopsis (Arabidopsis thaliana) seedlings show organ-specific transcriptome responses to elevated temperatures, and that thermomorphogenesis involves both autonomous and organ-interdependent temperature sensing and signaling. Seedling roots can sense and respond to temperature in a shoot-independent manner, whereas shoot temperature responses require both local and systemic processes. The induction of cell elongation in hypocotyls requires temperature sensing in cotyledons, followed by generation of a mobile auxin signal. Subsequently, auxin travels to the hypocotyl where it triggers local brassinosteroid-induced cell elongation in seedling stems, which depends upon a distinct, permissive temperature sensor in the hypocotyl.
AU - Bellstaedt, Julia
AU - Trenner, Jana
AU - Lippmann, Rebecca
AU - Poeschl, Yvonne
AU - Zhang, Xixi
AU - Friml, Jiří
AU - Quint, Marcel
AU - Delker, Carolin
ID - 6366
IS - 2
JF - Plant Physiology
SN - 0032-0889
TI - A mobile auxin signal connects temperature sensing in cotyledons with growth responses in hypocotyls
VL - 180
ER -
TY - JOUR
AB - Clathrin-mediated endocytosis (CME) is a highly conserved and essential cellular process in eukaryotic cells, but its dynamic and vital nature makes it challenging to study using classical genetics tools. In contrast, although small molecules can acutely and reversibly perturb CME, the few chemical CME inhibitors that have been applied to plants are either ineffective or show undesirable side effects. Here, we identify the previously described endosidin9 (ES9) as an inhibitor of clathrin heavy chain (CHC) function in both Arabidopsis and human cells through affinity-based target isolation, in vitro binding studies and X-ray crystallography. Moreover, we present a chemically improved ES9 analog, ES9-17, which lacks the undesirable side effects of ES9 while retaining the ability to target CHC. ES9 and ES9-17 have expanded the chemical toolbox used to probe CHC function, and present chemical scaffolds for further design of more specific and potent CHC inhibitors across different systems.
AU - Dejonghe, Wim
AU - Sharma, Isha
AU - Denoo, Bram
AU - De Munck, Steven
AU - Lu, Qing
AU - Mishev, Kiril
AU - Bulut, Haydar
AU - Mylle, Evelien
AU - De Rycke, Riet
AU - Vasileva, Mina K
AU - Savatin, Daniel V.
AU - Nerinckx, Wim
AU - Staes, An
AU - Drozdzecki, Andrzej
AU - Audenaert, Dominique
AU - Yperman, Klaas
AU - Madder, Annemieke
AU - Friml, Jiří
AU - Van Damme, Daniël
AU - Gevaert, Kris
AU - Haucke, Volker
AU - Savvides, Savvas N.
AU - Winne, Johan
AU - Russinova, Eugenia
ID - 6377
IS - 6
JF - Nature Chemical Biology
SN - 15524450
TI - Disruption of endocytosis through chemical inhibition of clathrin heavy chain function
VL - 15
ER -
TY - JOUR
AB - Polycomb group (PcG) proteins play critical roles in the epigenetic inheritance of cell fate. The Polycomb Repressive Complexes PRC1 and PRC2 catalyse distinct chromatin modifications to enforce gene silencing, but how transcriptional repression is propagated through mitotic cell divisions remains a key unresolved question. Using reversible tethering of PcG proteins to ectopic sites in mouse embryonic stem cells, here we show that PRC1 can trigger transcriptional repression and Polycomb-dependent chromatin modifications. We find that canonical PRC1 (cPRC1), but not variant PRC1, maintains gene silencing through cell division upon reversal of tethering. Propagation of gene repression is sustained by cis-acting histone modifications, PRC2-mediated H3K27me3 and cPRC1-mediated H2AK119ub1, promoting a sequence-independent feedback mechanism for PcG protein recruitment. Thus, the distinct PRC1 complexes present in vertebrates can differentially regulate epigenetic maintenance of gene silencing, potentially enabling dynamic heritable responses to complex stimuli. Our findings reveal how PcG repression is potentially inherited in vertebrates.
AU - Moussa, Hagar F.
AU - Bsteh, Daniel
AU - Yelagandula, Ramesh
AU - Pribitzer, Carina
AU - Stecher, Karin
AU - Bartalska, Katarina
AU - Michetti, Luca
AU - Wang, Jingkui
AU - Zepeda-Martinez, Jorge A.
AU - Elling, Ulrich
AU - Stuckey, Jacob I.
AU - James, Lindsey I.
AU - Frye, Stephen V.
AU - Bell, Oliver
ID - 6412
IS - 1
JF - Nature Communications
TI - Canonical PRC1 controls sequence-independent propagation of Polycomb-mediated gene silencing
VL - 10
ER -
TY - JOUR
AB - Phase-field methods have long been used to model the flow of immiscible fluids. Their ability to naturally capture interface topological changes is widely recognized, but their accuracy in simulating flows of real fluids in practical geometries is not established. We here quantitatively investigate the convergence of the phase-field method to the sharp-interface limit with simulations of two-phase pipe flow. We focus on core-annular flows, in which a highly viscous fluid is lubricated by a less viscous fluid, and validate our simulations with an analytic laminar solution, a formal linear stability analysis and also in the fully nonlinear regime. We demonstrate the ability of the phase-field method to accurately deal with non-rectangular geometry, strong advection, unsteady fluctuations and large viscosity contrast. We argue that phase-field methods are very promising for quantitatively studying moderately turbulent flows, especially at high concentrations of the disperse phase.
AU - Song, Baofang
AU - Plana, Carlos
AU - Lopez Alonso, Jose M
AU - Avila, Marc
ID - 6413
JF - International Journal of Multiphase Flow
SN - 03019322
TI - Phase-field simulation of core-annular pipe flow
VL - 117
ER -
TY - JOUR
AB - Ant invasions are often harmful to native species communities. Their pathogens and host disease defense mechanisms may be one component of their devastating success. First, they can introduce harmful diseases to their competitors in the introduced range, to which they themselves are tolerant. Second, their supercolonial social structure of huge multi-queen nest networks means that they will harbor a broad pathogen spectrum and high pathogen load while remaining resilient, unlike the smaller, territorial colonies of the native species. Thus, it is likely that invasive ants act as a disease reservoir, promoting their competitive advantage and invasive success.
AU - Cremer, Sylvia
ID - 6415
JF - Current Opinion in Insect Science
SN - 22145745
TI - Pathogens and disease defense of invasive ants
VL - 33
ER -
TY - JOUR
AB - Males and females of Artemia franciscana, a crustacean commonly used in the aquarium trade, are highly dimorphic. Sex is determined by a pair of ZW chromosomes, but the nature and extent of differentiation of these chromosomes is unknown. Here, we characterize the Z chromosome by detecting genomic regions that show lower genomic coverage in female than in male samples, and regions that harbor an excess of female-specific SNPs. We detect many Z-specific genes, which no longer have homologs on the W, but also Z-linked genes that appear to have diverged very recently from their existing W-linked homolog. We assess patterns of male and female expression in two tissues with extensive morphological dimorphism, gonads, and heads. In agreement with their morphology, sex-biased expression is common in both tissues. Interestingly, the Z chromosome is not enriched for sex-biased genes, and seems to in fact have a mechanism of dosage compensation that leads to equal expression in males and in females. Both of these patterns are contrary to most ZW systems studied so far, making A. franciscana an excellent model for investigating the interplay between the evolution of sexual dimorphism and dosage compensation, as well as Z chromosome evolution in general.
AU - Huylmans, Ann K
AU - Toups, Melissa A
AU - Macon, Ariana
AU - Gammerdinger, William J
AU - Vicoso, Beatriz
ID - 6418
IS - 4
JF - Genome biology and evolution
TI - Sex-biased gene expression and dosage compensation on the Artemia franciscana Z-chromosome
VL - 11
ER -
TY - JOUR
AB - Characterizing the fitness landscape, a representation of fitness for a large set of genotypes, is key to understanding how genetic information is interpreted to create functional organisms. Here we determined the evolutionarily-relevant segment of the fitness landscape of His3, a gene coding for an enzyme in the histidine synthesis pathway, focusing on combinations of amino acid states found at orthologous sites of extant species. Just 15% of amino acids found in yeast His3 orthologues were always neutral while the impact on fitness of the remaining 85% depended on the genetic background. Furthermore, at 67% of sites, amino acid replacements were under sign epistasis, having both strongly positive and negative effect in different genetic backgrounds. 46% of sites were under reciprocal sign epistasis. The fitness impact of amino acid replacements was influenced by only a few genetic backgrounds but involved interaction of multiple sites, shaping a rugged fitness landscape in which many of the shortest paths between highly fit genotypes are inaccessible.
AU - Pokusaeva, Victoria
AU - Usmanova, Dinara R.
AU - Putintseva, Ekaterina V.
AU - Espinar, Lorena
AU - Sarkisyan, Karen
AU - Mishin, Alexander S.
AU - Bogatyreva, Natalya S.
AU - Ivankov, Dmitry
AU - Akopyan, Arseniy
AU - Avvakumov, Sergey
AU - Povolotskaya, Inna S.
AU - Filion, Guillaume J.
AU - Carey, Lucas B.
AU - Kondrashov, Fyodor
ID - 6419
IS - 4
JF - PLoS Genetics
TI - An experimental assay of the interactions of amino acids from orthologous sequences shaping a complex fitness landscape
VL - 15
ER -
TY - CONF
AB - Safety and security are major concerns in the development of Cyber-Physical Systems (CPS). Signal temporal logic (STL) was proposedas a language to specify and monitor the correctness of CPS relativeto formalized requirements. Incorporating STL into a developmentprocess enables designers to automatically monitor and diagnosetraces, compute robustness estimates based on requirements, andperform requirement falsification, leading to productivity gains inverification and validation activities; however, in its current formSTL is agnostic to the input/output classification of signals, andthis negatively impacts the relevance of the analysis results.In this paper we propose to make the interface explicit in theSTL language by introducing input/output signal declarations. Wethen define new measures of input vacuity and output robustnessthat better reflect the nature of the system and the specification in-tent. The resulting framework, which we call interface-aware signaltemporal logic (IA-STL), aids verification and validation activities.We demonstrate the benefits of IA-STL on several CPS analysisactivities: (1) robustness-driven sensitivity analysis, (2) falsificationand (3) fault localization. We describe an implementation of our en-hancement to STL and associated notions of robustness and vacuityin a prototype extension of Breach, a MATLAB®/Simulink®toolboxfor CPS verification and validation. We explore these methodologi-cal improvements and evaluate our results on two examples fromthe automotive domain: a benchmark powertrain control systemand a hydrogen fuel cell system.
AU - Ferrere, Thomas
AU - Nickovic, Dejan
AU - Donzé, Alexandre
AU - Ito, Hisahiro
AU - Kapinski, James
ID - 6428
SN - 9781450362825
T2 - Proceedings of the 2019 22nd ACM International Conference on Hybrid Systems: Computation and Control
TI - Interface-aware signal temporal logic
ER -
TY - CONF
AB - A proxy re-encryption (PRE) scheme is a public-key encryption scheme that allows the holder of a key pk to derive a re-encryption key for any other key 𝑝𝑘′. This re-encryption key lets anyone transform ciphertexts under pk into ciphertexts under 𝑝𝑘′ without having to know the underlying message, while transformations from 𝑝𝑘′ to pk should not be possible (unidirectional). Security is defined in a multi-user setting against an adversary that gets the users’ public keys and can ask for re-encryption keys and can corrupt users by requesting their secret keys. Any ciphertext that the adversary cannot trivially decrypt given the obtained secret and re-encryption keys should be secure.
All existing security proofs for PRE only show selective security, where the adversary must first declare the users it wants to corrupt. This can be lifted to more meaningful adaptive security by guessing the set of corrupted users among the n users, which loses a factor exponential in Open image in new window , rendering the result meaningless already for moderate Open image in new window .
Jafargholi et al. (CRYPTO’17) proposed a framework that in some cases allows to give adaptive security proofs for schemes which were previously only known to be selectively secure, while avoiding the exponential loss that results from guessing the adaptive choices made by an adversary. We apply their framework to PREs that satisfy some natural additional properties. Concretely, we give a more fine-grained reduction for several unidirectional PREs, proving adaptive security at a much smaller loss. The loss depends on the graph of users whose edges represent the re-encryption keys queried by the adversary. For trees and chains the loss is quasi-polynomial in the size and for general graphs it is exponential in their depth and indegree (instead of their size as for previous reductions). Fortunately, trees and low-depth graphs cover many, if not most, interesting applications.
Our results apply e.g. to the bilinear-map based PRE schemes by Ateniese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme (STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14).
AU - Fuchsbauer, Georg
AU - Kamath Hosdurg, Chethan
AU - Klein, Karen
AU - Pietrzak, Krzysztof Z
ID - 6430
SN - 03029743
TI - Adaptively secure proxy re-encryption
VL - 11443
ER -
TY - JOUR
AB - This paper investigates the use of fundamental solutions for animating detailed linear water surface waves. We first propose an analytical solution for efficiently animating circular ripples in closed form. We then show how to adapt the method of fundamental solutions (MFS) to create ambient waves interacting with complex obstacles. Subsequently, we present a novel wavelet-based discretization which outperforms the state of the art MFS approach for simulating time-varying water surface waves with moving obstacles. Our results feature high-resolution spatial details, interactions with complex boundaries, and large open ocean domains. Our method compares favorably with previous work as well as known analytical solutions. We also present comparisons between our method and real world examples.
AU - Schreck, Camille
AU - Hafner, Christian
AU - Wojtan, Christopher J
ID - 6442
IS - 4
JF - ACM Transactions on Graphics
TI - Fundamental solutions for water wave animation
VL - 38
ER -
TY - JOUR
AB - Epidermal growth factor receptor (EGFR) signaling controls skin development and homeostasis inmice and humans, and its deficiency causes severe skin inflammation, which might affect epidermalstem cell behavior. Here, we describe the inflammation-independent effects of EGFR deficiency dur-ing skin morphogenesis and in adult hair follicle stem cells. Expression and alternative splicing analysisof RNA sequencing data from interfollicular epidermis and outer root sheath indicate that EGFR con-trols genes involved in epidermal differentiation and also in centrosome function, DNA damage, cellcycle, and apoptosis. Genetic experiments employingp53deletion in EGFR-deficient epidermis revealthat EGFR signaling exhibitsp53-dependent functions in proliferative epidermal compartments, aswell asp53-independent functions in differentiated hair shaft keratinocytes. Loss of EGFR leads toabsence of LEF1 protein specifically in the innermost epithelial hair layers, resulting in disorganizationof medulla cells. Thus, our results uncover important spatial and temporal features of cell-autonomousEGFR functions in the epidermis.
AU - Amberg, Nicole
AU - Sotiropoulou, Panagiota A.
AU - Heller, Gerwin
AU - Lichtenberger, Beate M.
AU - Holcmann, Martin
AU - Camurdanoglu, Bahar
AU - Baykuscheva-Gentscheva, Temenuschka
AU - Blanpain, Cedric
AU - Sibilia, Maria
ID - 6451
JF - iScience
SN - 2589-0042
TI - EGFR controls hair shaft differentiation in a p53-independent manner
VL - 15
ER -
TY - JOUR
AB - Adult neural stem cells and multiciliated ependymalcells are glial cells essential for neurological func-tions. Together, they make up the adult neurogenicniche. Using both high-throughput clonal analysisand single-cell resolution of progenitor division pat-terns and fate, we show that these two componentsof the neurogenic niche are lineally related: adult neu-ral stem cells are sister cells to ependymal cells,whereas most ependymal cells arise from the termi-nal symmetric divisions of the lineage. Unexpectedly,we found that the antagonist regulators of DNA repli-cation, GemC1 and Geminin, can tune the proportionof neural stem cells and ependymal cells. Our find-ings reveal the controlled dynamic of the neurogenicniche ontogeny and identify the Geminin familymembers as key regulators of the initial pool of adultneural stem cells.
AU - Ortiz-Álvarez, G
AU - Daclin, M
AU - Shihavuddin, A
AU - Lansade, P
AU - Fortoul, A
AU - Faucourt, M
AU - Clavreul, S
AU - Lalioti, ME
AU - Taraviras, S
AU - Hippenmeyer, Simon
AU - Livet, J
AU - Meunier, A
AU - Genovesio, A
AU - Spassky, N
ID - 6454
IS - 1
JF - Neuron
SN - 0896-6273
TI - Adult neural stem cells and multiciliated ependymal cells share a common lineage regulated by the Geminin family members
VL - 102
ER -
TY - JOUR
AB - During corticogenesis, distinct subtypes of neurons are sequentially born from ventricular zone progenitors. How these cells are molecularly temporally patterned is poorly understood. We used single-cell RNA sequencing at high temporal resolution to trace the lineage of the molecular identities of successive generations of apical progenitors (APs) and their daughter neurons in mouse embryos. We identified a core set of evolutionarily conserved, temporally patterned genes that drive APs from internally driven to more exteroceptive states. We found that the Polycomb repressor complex 2 (PRC2) epigenetically regulates AP temporal progression. Embryonic age–dependent AP molecular states are transmitted to their progeny as successive ground states, onto which essentially conserved early postmitotic differentiation programs are applied, and are complemented by later-occurring environment-dependent signals. Thus, epigenetically regulated temporal molecular birthmarks present in progenitors act in their postmitotic progeny to seed adult neuronal diversity.
AU - Telley, L
AU - Agirman, G
AU - Prados, J
AU - Amberg, Nicole
AU - Fièvre, S
AU - Oberst, P
AU - Bartolini, G
AU - Vitali, I
AU - Cadilhac, C
AU - Hippenmeyer, Simon
AU - Nguyen, L
AU - Dayer, A
AU - Jabaudon, D
ID - 6455
IS - 6440
JF - Science
SN - 0036-8075
TI - Temporal patterning of apical progenitors and their daughter neurons in the developing neocortex
VL - 364
ER -
TY - CONF
AB - A controller is a device that interacts with a plant. At each time point,it reads the plant’s state and issues commands with the goal that the plant oper-ates optimally. Constructing optimal controllers is a fundamental and challengingproblem. Machine learning techniques have recently been successfully applied totrain controllers, yet they have limitations. Learned controllers are monolithic andhard to reason about. In particular, it is difficult to add features without retraining,to guarantee any level of performance, and to achieve acceptable performancewhen encountering untrained scenarios. These limitations can be addressed bydeploying quantitative run-timeshieldsthat serve as a proxy for the controller.At each time point, the shield reads the command issued by the controller andmay choose to alter it before passing it on to the plant. We show how optimalshields that interfere as little as possible while guaranteeing a desired level ofcontroller performance, can be generated systematically and automatically usingreactive synthesis. First, we abstract the plant by building a stochastic model.Second, we consider the learned controller to be a black box. Third, we mea-surecontroller performanceandshield interferenceby two quantitative run-timemeasures that are formally defined using weighted automata. Then, the problemof constructing a shield that guarantees maximal performance with minimal inter-ference is the problem of finding an optimal strategy in a stochastic2-player game“controller versus shield” played on the abstract state space of the plant with aquantitative objective obtained from combining the performance and interferencemeasures. We illustrate the effectiveness of our approach by automatically con-structing lightweight shields for learned traffic-light controllers in various roadnetworks. The shields we generate avoid liveness bugs, improve controller per-formance in untrained and changing traffic situations, and add features to learnedcontrollers, such as giving priority to emergency vehicles.
AU - Avni, Guy
AU - Bloem, Roderick
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Konighofer, Bettina
AU - Pranger, Stefan
ID - 6462
SN - 0302-9743
T2 - 31st International Conference on Computer-Aided Verification
TI - Run-time optimization for learned controllers through quantitative games
VL - 11561
ER -
TY - JOUR
AB - Tight control over protein degradation is a fundamental requirement for cells to respond rapidly to various stimuli and adapt to a fluctuating environment. Here we develop a versatile, easy-to-handle library of destabilizing tags (degrons) for the precise regulation of protein expression profiles in mammalian cells by modulating target protein half-lives in a predictable manner. Using the well-established tetracycline gene-regulation system as a model, we show that the dynamics of protein expression can be tuned by fusing appropriate degron tags to gene regulators. Next, we apply this degron library to tune a synthetic pulse-generating circuit in mammalian cells. With this toolbox we establish a set of pulse generators with tailored pulse lengths and magnitudes of protein expression. This methodology will prove useful in the functional roles of essential proteins, fine-tuning of gene-expression systems, and enabling a higher complexity in the design of synthetic biological systems in mammalian cells.
AU - Chassin, Hélène
AU - Müller, Marius
AU - Tigges, Marcel
AU - Scheller, Leo
AU - Lang, Moritz
AU - Fussenegger, Martin
ID - 6465
IS - 1
JF - Nature Communications
TI - A modular degron library for synthetic circuits in mammalian cells
VL - 10
ER -
TY - JOUR
AB - One of the most striking and consistent results in speciation genomics is the heterogeneous divergence observed across the genomes of closely related species. This pattern was initially attributed to different levels of gene exchange—with divergence preserved at loci generating a barrier to gene flow but homogenized at unlinked neutral loci. Although there is evidence to support this model, it is now recognized that interpreting patterns of divergence across genomes is not so straightforward. One
problem is that heterogenous divergence between populations can also be generated by other processes (e.g. recurrent selective sweeps or background selection) without any involvement of differential gene flow. Thus, integrated studies that identify which loci are likely subject to divergent selection are required to shed light on the interplay between selection and gene flow during the early phases of speciation. In this issue of Molecular Ecology, Rifkin et al. (2019) confront this challenge using a pair of sister morning glory species. They wisely design their sampling to take the geographic context of individuals into account, including geographically isolated (allopatric) and co‐occurring (sympatric) populations. This enabled them to show that individuals are phenotypically less differentiated in sympatry. They also found that the loci that resist introgression are enriched for those most differentiated in allopatry and loci that exhibit signals of divergent selection. One great strength of the
study is the combination of methods from population genetics and molecular evolution, including the development of a model to simultaneously infer admixture proportions and selfing rates.
AU - Field, David
AU - Fraisse, Christelle
ID - 6466
IS - 7
JF - Molecular ecology
TI - Breaking down barriers in morning glories
VL - 28
ER -
TY - JOUR
AB - Fitness interactions between mutations can influence a population’s evolution in many different ways. While epistatic effects are difficult to measure precisely, important information is captured by the mean and variance of log fitnesses for individuals carrying different numbers of mutations. We derive predictions for these quantities from a class of simple fitness landscapes, based on models of optimizing selection on quantitative traits. We also explore extensions to the models, including modular pleiotropy, variable effect sizes, mutational bias and maladaptation of the wild type. We illustrate our approach by reanalysing a large dataset of mutant effects in a yeast snoRNA (small nucleolar RNA). Though characterized by some large epistatic effects, these data give a good overall fit to the non-epistatic null model, suggesting that epistasis might have limited influence on the evolutionary dynamics in this system. We also show how the amount of epistasis depends on both the underlying fitness landscape and the distribution of mutations, and so is expected to vary in consistent ways between new mutations, standing variation and fixed mutations.
AU - Fraisse, Christelle
AU - Welch, John J.
ID - 6467
IS - 4
JF - Biology Letters
SN - 17449561
TI - The distribution of epistasis on simple fitness landscapes
VL - 15
ER -
TY - JOUR
AB - Investigating neuronal activity using genetically encoded Ca2+ indicators in behaving animals is hampered by inaccuracies in spike inference from fluorescent tracers. Here we combine two‐photon [Ca2+] imaging with cell‐attached recordings, followed by post hoc determination of the expression level of GCaMP6f, to explore how it affects the amplitude, kinetics and temporal summation of somatic [Ca2+] transients in mouse hippocampal pyramidal cells (PCs). The amplitude of unitary [Ca2+] transients (evoked by a single action potential) negatively correlates with GCaMP6f expression, but displays large variability even among PCs with similarly low expression levels. The summation of fluorescence signals is frequency‐dependent, supralinear and also shows remarkable cell‐to‐cell variability. We performed experimental data‐based simulations and found that spike inference error rates using MLspike depend strongly on unitary peak amplitudes and GCaMP6f expression levels. We provide simple methods for estimating the unitary [Ca2+] transients in individual weakly GCaMP6f‐expressing PCs, with which we achieve spike inference error rates of ∼5%.
AU - Éltes, Tímea
AU - Szoboszlay, Miklos
AU - Szigeti, Margit Katalin
AU - Nusser, Zoltan
ID - 6470
IS - 11
JF - Journal of Physiology
SN - 00223751
TI - Improved spike inference accuracy by estimating the peak amplitude of unitary [Ca2+] transients in weakly GCaMP6f-expressing hippocampal pyramidal cells
VL - 597
ER -
TY - THES
AB - Single cells are constantly interacting with their environment and each other, more importantly, the accurate perception of environmental cues is crucial for growth, survival, and reproduction. This communication between cells and their environment can be formalized in mathematical terms and be quantified as the information flow between them, as prescribed by information theory.
The recent availability of real–time dynamical patterns of signaling molecules in single cells has allowed us to identify encoding about the identity of the environment in the time–series. However, efficient estimation of the information transmitted by these signals has been a data–analysis challenge due to the high dimensionality of the trajectories and the limited number of samples. In the first part of this thesis, we develop and evaluate decoding–based estimation methods to lower bound the mutual information and derive model–based precise information estimates for biological reaction networks governed by the chemical master equation. This is followed by applying the decoding-based methods to study the intracellular representation of extracellular changes in budding yeast, by observing the transient dynamics of nuclear translocation of 10 transcription factors in response to 3 stress conditions. Additionally, we apply these estimators to previously published data on ERK and Ca2+ signaling and yeast stress response. We argue that this single cell decoding-based measure of information provides an unbiased, quantitative and interpretable measure for the fidelity of biological signaling processes.
Finally, in the last section, we deal with gene regulation which is primarily controlled by transcription factors (TFs) that bind to the DNA to activate gene expression. The possibility that non-cognate TFs activate transcription diminishes the accuracy of regulation with potentially disastrous effects for the cell. This ’crosstalk’ acts as a previously unexplored source of noise in biochemical networks and puts a strong constraint on their performance. To mitigate erroneous initiation we propose an out of equilibrium scheme that implements kinetic proofreading. We show that such architectures are favored over their equilibrium counterparts for complex organisms despite introducing noise in gene expression.
AU - Cepeda Humerez, Sarah A
ID - 6473
KW - Information estimation
KW - Time-series
KW - data analysis
SN - 2663-337X
TI - Estimating information flow in single cells
ER -
TY - JOUR
AB - Thermalizing quantum systems are conventionallydescribed by statistical mechanics at equilib-rium. However, not all systems fall into this category, with many-body localization providinga generic mechanism for thermalization to fail in strongly disordered systems. Many-bodylocalized (MBL) systems remain perfect insulators at nonzero temperature, which do notthermalize and therefore cannot be describedusing statistical mechanics. This Colloquiumreviews recent theoretical and experimental advances in studies of MBL systems, focusing onthe new perspective provided by entanglement and nonequilibrium experimental probes suchas quantum quenches. Theoretically, MBL systems exhibit a new kind of robust integrability: anextensive set of quasilocal integrals of motion emerges, which provides an intuitive explanationof the breakdown of thermalization. A description based on quasilocal integrals of motion isused to predict dynamical properties of MBL systems, such as the spreading of quantumentanglement, the behavior of local observables, and the response to external dissipativeprocesses. Furthermore, MBL systems can exhibit eigenstate transitions and quantum ordersforbidden in thermodynamic equilibrium. An outline isgiven of the current theoretical under-standing of the quantum-to-classical transitionbetween many-body localized and ergodic phasesand anomalous transport in the vicinity of that transition. Experimentally, synthetic quantumsystems, which are well isolated from an external thermal reservoir, provide natural platforms forrealizing the MBL phase. Recent experiments with ultracold atoms, trapped ions, superconductingqubits, and quantum materials, in which different signatures of many-body localization have beenobserved, are reviewed. This Colloquium concludes by listing outstanding challenges andpromising future research directions.
AU - Abanin, Dmitry A.
AU - Altman, Ehud
AU - Bloch, Immanuel
AU - Serbyn, Maksym
ID - 6477
IS - 2
JF - Reviews of Modern Physics
SN - 1539-0756
TI - Colloquium: Many-body localization, thermalization, and entanglement
VL - 91
ER -
TY - CONF
AB - Computer vision systems for automatic image categorization have become accurate and reliable enough that they can run continuously for days or even years as components of real-world commercial applications. A major open problem in this context, however, is quality control. Good classification performance can only be expected if systems run under the specific conditions, in particular data distributions, that they were trained for. Surprisingly, none of the currently used deep network architectures have a built-in functionality that could detect if a network operates on data from a distribution it was not trained for, such that potentially a warning to the human users could be triggered. In this work, we describe KS(conf), a procedure for detecting such outside of specifications (out-of-specs) operation, based on statistical testing of the network outputs. We show by extensive experiments using the ImageNet, AwA2 and DAVIS datasets on a variety of ConvNets architectures that KS(conf) reliably detects out-of-specs situations. It furthermore has a number of properties that make it a promising candidate for practical deployment: it is easy to implement, adds almost no overhead to the system, works with all networks, including pretrained ones, and requires no a priori knowledge of how the data distribution could change.
AU - Sun, Rémy
AU - Lampert, Christoph
ID - 6482
SN - 0302-9743
TI - KS(conf): A light-weight test if a ConvNet operates outside of Its specifications
VL - 11269
ER -
TY - GEN
AB - Traditional concurrent programming involves manipulating shared mutable state. Alternatives to this programming style are communicating sequential processes (CSP) [1] and actor [2] models, which share data via explicit communication. Rendezvous channelis the common abstraction for communication between several processes, where senders and receivers perform a rendezvous handshake as a part of their protocol (senders wait for receivers and vice versa). Additionally to this, channels support the select expression. In this work, we present the first efficient lock-free channel algorithm, and compare it against Go [3] and Kotlin [4] baseline implementations.
AU - Koval, Nikita
AU - Alistarh, Dan-Adrian
AU - Elizarov, Roman
ID - 6485
SN - 9781450362252
T2 - Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming
TI - Lock-free channels for programming via communicating sequential processes
ER -
TY - CONF
AB - We present two algorithmic approaches for synthesizing linear hybrid automata from experimental data. Unlike previous approaches, our algorithms work without a template and generate an automaton with nondeterministic guards and invariants, and with an arbitrary number and topology of modes. They thus construct a succinct model from the data and provide formal guarantees. In particular, (1) the generated automaton can reproduce the data up to a specified tolerance and (2) the automaton is tight, given the first guarantee. Our first approach encodes the synthesis problem as a logical formula in the theory of linear arithmetic, which can then be solved by an SMT solver. This approach minimizes the number of modes in the resulting model but is only feasible for limited data sets. To address scalability, we propose a second approach that does not enforce to find a minimal model. The algorithm constructs an initial automaton and then iteratively extends the automaton based on processing new data. Therefore the algorithm is well-suited for online and synthesis-in-the-loop applications. The core of the algorithm is a membership query that checks whether, within the specified tolerance, a given data set can result from the execution of a given automaton. We solve this membership problem for linear hybrid automata by repeated reachability computations. We demonstrate the effectiveness of the algorithm on synthetic data sets and on cardiac-cell measurements.
AU - Garcia Soto, Miriam
AU - Henzinger, Thomas A
AU - Schilling, Christian
AU - Zeleznik, Luka
ID - 6493
KW - Synthesis
KW - Linear hybrid automaton
KW - Membership
SN - 0302-9743
T2 - 31st International Conference on Computer-Aided Verification
TI - Membership-based synthesis of linear hybrid automata
VL - 11561
ER -
TY - JOUR
AB - We provide an entropy formulation for porous medium-type equations with a stochastic, non-linear, spatially inhomogeneous forcing. Well-posedness and L1-contraction is obtained in the class of entropy solutions. Our scope allows for porous medium operators Δ(|u|m−1u) for all m∈(1,∞), and Hölder continuous diffusion nonlinearity with exponent 1/2.
AU - Dareiotis, Konstantinos
AU - Gerencser, Mate
AU - Gess, Benjamin
ID - 65
IS - 6
JF - Journal of Differential Equations
TI - Entropy solutions for stochastic porous media equations
VL - 266
ER -
TY - JOUR
AB - Root gravitropism is one of the most important processes allowing plant adaptation to the land environment. Auxin plays a central role in mediating root gravitropism, but how auxin contributes to gravitational perception and the subsequent response is still unclear.
Here, we showed that the local auxin maximum/gradient within the root apex, which is generated by the PIN directional auxin transporters, regulates the expression of three key starch granule synthesis genes, SS4, PGM and ADG1, which in turn influence the accumulation of starch granules that serve as a statolith perceiving gravity.
Moreover, using the cvxIAA‐ccvTIR1 system, we also showed that TIR1‐mediated auxin signaling is required for starch granule formation and gravitropic response within root tips. In addition, axr3 mutants showed reduced auxin‐mediated starch granule accumulation and disruption of gravitropism within the root apex.
Our results indicate that auxin‐mediated statolith production relies on the TIR1/AFB‐AXR3‐mediated auxin signaling pathway. In summary, we propose a dual role for auxin in gravitropism: the regulation of both gravity perception and response.
AU - Zhang, Yuzhou
AU - He, P
AU - Ma, X
AU - Yang, Z
AU - Pang, C
AU - Yu, J
AU - Wang, G
AU - Friml, Jiří
AU - Xiao, G
ID - 6504
IS - 2
JF - New Phytologist
SN - 0028-646x
TI - Auxin-mediated statolith production for root gravitropism
VL - 224
ER -
TY - JOUR
AB - How does environmental complexity affect the evolution of single genes? Here, we measured the effects of a set of Bacillus subtilis glutamate dehydrogenase mutants across 19 different environments—from phenotypically homogeneous single-cell populations in liquid media to heterogeneous biofilms, plant roots and soil populations. The effects of individual gene mutations on organismal fitness were highly reproducible in liquid cultures. However, 84% of the tested alleles showed opposing fitness effects under different growth conditions (sign environmental pleiotropy). In colony biofilms and soil samples, different alleles dominated in parallel replica experiments. Accordingly, we found that in these heterogeneous cell populations the fate of mutations was dictated by a combination of selection and drift. The latter relates to programmed prophage excisions that occurred during biofilm development. Overall, for each condition, a wide range of glutamate dehydrogenase mutations persisted and sometimes fixated as a result of the combined action of selection, pleiotropy and chance. However, over longer periods and in multiple environments, nearly all of this diversity would be lost—across all the environments and conditions that we tested, the wild type was the fittest allele.
AU - Noda-García, Lianet
AU - Davidi, Dan
AU - Korenblum, Elisa
AU - Elazar, Assaf
AU - Putintseva, Ekaterina
AU - Aharoni, Asaph
AU - Tawfik, Dan S.
ID - 6506
IS - 7
JF - Nature Microbiology
SN - 2058-5276
TI - Chance and pleiotropy dominate genetic diversity in complex bacterial environments
VL - 4
ER -
TY - JOUR
AB - Segregation of maternal determinants within the oocyte constitutes the first step in embryo patterning. In zebrafish oocytes, extensive ooplasmic streaming leads to the segregation of ooplasm from yolk granules along the animal-vegetal axis of the oocyte. Here, we show that this process does not rely on cortical actin reorganization, as previously thought, but instead on a cell-cycle-dependent bulk actin polymerization wave traveling from the animal to the vegetal pole of the oocyte. This wave functions in segregation by both pulling ooplasm animally and pushing yolk granules vegetally. Using biophysical experimentation and theory, we show that ooplasm pulling is mediated by bulk actin network flows exerting friction forces on the ooplasm, while yolk granule pushing is achieved by a mechanism closely resembling actin comet formation on yolk granules. Our study defines a novel role of cell-cycle-controlled bulk actin polymerization waves in oocyte polarization via ooplasmic segregation.
AU - Shamipour, Shayan
AU - Kardos, Roland
AU - Xue, Shi-lei
AU - Hof, Björn
AU - Hannezo, Edouard B
AU - Heisenberg, Carl-Philipp J
ID - 6508
IS - 6
JF - Cell
SN - 00928674
TI - Bulk actin dynamics drive phase segregation in zebrafish oocytes
VL - 177
ER -
TY - JOUR
AB - Let U and V be two independent N by N random matrices that are distributed according to Haar measure on U(N). Let Σ be a nonnegative deterministic N by N matrix. The single ring theorem [Ann. of Math. (2) 174 (2011) 1189–1217] asserts that the empirical eigenvalue distribution of the matrix X:=UΣV∗ converges weakly, in the limit of large N, to a deterministic measure which is supported on a single ring centered at the origin in ℂ. Within the bulk regime, that is, in the interior of the single ring, we establish the convergence of the empirical eigenvalue distribution on the optimal local scale of order N−1/2+ε and establish the optimal convergence rate. The same results hold true when U and V are Haar distributed on O(N).
AU - Bao, Zhigang
AU - Erdös, László
AU - Schnelli, Kevin
ID - 6511
IS - 3
JF - Annals of Probability
SN - 00911798
TI - Local single ring theorem on optimal scale
VL - 47
ER -
TY - JOUR
AB - Adult intestinal stem cells are located at the bottom of crypts of Lieberkühn, where they express markers such as LGR5 1,2 and fuel the constant replenishment of the intestinal epithelium1. Although fetal LGR5-expressing cells can give rise to adult intestinal stem cells3,4, it remains unclear whether this population in the patterned epithelium represents unique intestinal stem-cell precursors. Here we show, using unbiased quantitative lineage-tracing approaches, biophysical modelling and intestinal transplantation, that all cells of the mouse intestinal epithelium—irrespective of their location and pattern of LGR5 expression in the fetal gut tube—contribute actively to the adult intestinal stem cell pool. Using 3D imaging, we find that during fetal development the villus undergoes gross remodelling and fission. This brings epithelial cells from the non-proliferative villus into the proliferative intervillus region, which enables them to contribute to the adult stem-cell niche. Our results demonstrate that large-scale remodelling of the intestinal wall and cell-fate specification are closely linked. Moreover, these findings provide a direct link between the observed plasticity and cellular reprogramming of differentiating cells in adult tissues following damage5,6,7,8,9, revealing that stem-cell identity is an induced rather than a hardwired property.
AU - Guiu, Jordi
AU - Hannezo, Edouard B
AU - Yui, Shiro
AU - Demharter, Samuel
AU - Ulyanchenko, Svetlana
AU - Maimets, Martti
AU - Jørgensen, Anne
AU - Perlman, Signe
AU - Lundvall, Lene
AU - Mamsen, Linn Salto
AU - Larsen, Agnete
AU - Olesen, Rasmus H.
AU - Andersen, Claus Yding
AU - Thuesen, Lea Langhoff
AU - Hare, Kristine Juul
AU - Pers, Tune H.
AU - Khodosevich, Konstantin
AU - Simons, Benjamin D.
AU - Jensen, Kim B.
ID - 6513
JF - Nature
SN - 00280836
TI - Tracing the origin of adult intestinal stem cells
VL - 570
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 - JOUR
AB - Microglia have emerged as a critical component of neurodegenerative diseases. Genetic manipulation of microglia can elucidate their functional impact in disease. In neuroscience, recombinant viruses such as lentiviruses and adeno-associated viruses (AAVs) have been successfully used to target various cell types in the brain, although effective transduction of microglia is rare. In this review, we provide a short background of lentiviruses and AAVs, and strategies for designing recombinant viral vectors. Then, we will summarize recent literature on successful microglial transductions in vitro and in vivo, and discuss the current challenges. Finally, we provide guidelines for reporting the efficiency and specificity of viral targeting in microglia, which will enable the microglial research community to assess and improve methodologies for future studies.
AU - Maes, Margaret E
AU - Colombo, Gloria
AU - Schulz, Rouven
AU - Siegert, Sandra
ID - 6521
JF - Neuroscience Letters
SN - 0304-3940
TI - Targeting microglia with lentivirus and AAV: Recent advances and remaining challenges
VL - 707
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 - JOUR
AB - When animals become sick, infected cells and an armada of activated immune cells attempt to eliminate the pathogen from the body. Once infectious particles have breached the body's physical barriers of the skin or gut lining, an initially local response quickly escalates into a systemic response, attracting mobile immune cells to the site of infection. These cells complement the initial, unspecific defense with a more specialized, targeted response. This can also provide long-term immune memory and protection against future infection. The cell-autonomous defenses of the infected cells are thus aided by the actions of recruited immune cells. These specialized cells are the most mobile cells in the body, constantly patrolling through the otherwise static tissue to detect incoming pathogens. Such constant immune surveillance means infections are noticed immediately and can be rapidly cleared from the body. Some immune cells also remove infected cells that have succumbed to infection. All this prevents pathogen replication and spread to healthy tissues. Although this may involve the sacrifice of some somatic tissue, this is typically replaced quickly. Particular care is, however, given to the reproductive organs, which should always remain disease free (immune privilege).
AU - Cremer, Sylvia
ID - 6552
IS - 11
JF - Current Biology
SN - 09609822
TI - Social immunity in insects
VL - 29
ER -
TY - JOUR
AB - Due to the importance of zero-shot learning, i.e. classifying images where there is a lack of labeled training data, the number of proposed approaches has recently increased steadily. We argue that it is time to take a step back and to analyze the status quo of the area. The purpose of this paper is three-fold. First, given the fact that there is no agreed upon zero-shot learning benchmark, we first define a new benchmark by unifying both the evaluation protocols and data splits of publicly available datasets used for this task. This is an important contribution as published results are often not comparable and sometimes even flawed due to, e.g. pre-training on zero-shot test classes. Moreover, we propose a new zero-shot learning dataset, the Animals with Attributes 2 (AWA2) dataset which we make publicly available both in terms of image features and the images themselves. Second, we compare and analyze a significant number of the state-of-the-art methods in depth, both in the classic zero-shot setting but also in the more realistic generalized zero-shot setting. Finally, we discuss in detail the limitations of the current status of the area which can be taken as a basis for advancing it.
AU - Xian, Yongqin
AU - Lampert, Christoph
AU - Schiele, Bernt
AU - Akata, Zeynep
ID - 6554
IS - 9
JF - IEEE Transactions on Pattern Analysis and Machine Intelligence
SN - 0162-8828
TI - Zero-shot learning - A comprehensive evaluation of the good, the bad and the ugly
VL - 41
ER -
TY - CONF
AB - Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined to be the minimum treewidth of the face pairing graph of any triangulation T of M. In this setting the relationship between the topology of a 3-manifold and its treewidth is of particular interest. First, as a corollary of work of Jaco and Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination with our earlier work with Wagner, this yields that for non-Haken manifolds the Heegaard genus and the treewidth are within a constant factor. Second, we characterize all 3-manifolds of treewidth one: These are precisely the lens spaces and a single other Seifert fibered space. Furthermore, we show that all remaining orientable Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth two. In particular, for every spherical 3-manifold we exhibit a triangulation of treewidth at most two. Our results further validate the parameter of treewidth (and other related parameters such as cutwidth or congestion) to be useful for topological computing, and also shed more light on the scope of existing FPT-algorithms in the field.
AU - Huszár, Kristóf
AU - Spreer, Jonathan
ID - 6556
KW - computational 3-manifold topology
KW - fixed-parameter tractability
KW - layered triangulations
KW - structural graph theory
KW - treewidth
KW - cutwidth
KW - Heegaard genus
SN - 1868-8969
T2 - 35th International Symposium on Computational Geometry
TI - 3-manifold triangulations with small treewidth
VL - 129
ER -
TY - JOUR
AB - Branching morphogenesis is a prototypical example of complex three-dimensional organ sculpting, required in multiple developmental settings to maximize the area of exchange surfaces. It requires, in particular, the coordinated growth of different cell types together with complex patterning to lead to robust macroscopic outputs. In recent years, novel multiscale quantitative biology approaches, together with biophysical modelling, have begun to shed new light of this topic. Here, we wish to review some of these recent developments, highlighting the generic design principles that can be abstracted across different branched organs, as well as the implications for the broader fields of stem cell, developmental and systems biology.
AU - Hannezo, Edouard B
AU - Simons, Benjamin D.
ID - 6559
JF - Current Opinion in Cell Biology
SN - 09550674
TI - Multiscale dynamics of branching morphogenesis
VL - 60
ER -
TY - JOUR
AB - Optogenetics enables the spatio-temporally precise control of cell and animal behavior. Many optogenetic tools are driven by light-controlled protein–protein interactions (PPIs) that are repurposed from natural light-sensitive domains (LSDs). Applying light-controlled PPIs to new target proteins is challenging because it is difficult to predict which of the many available LSDs, if any, will yield robust light regulation. As a consequence, fusion protein libraries need to be prepared and tested, but methods and platforms to facilitate this process are currently not available. Here, we developed a genetic engineering strategy and vector library for the rapid generation of light-controlled PPIs. The strategy permits fusing a target protein to multiple LSDs efficiently and in two orientations. The public and expandable library contains 29 vectors with blue, green or red light-responsive LSDs, many of which have been previously applied ex vivo and in vivo. We demonstrate the versatility of the approach and the necessity for sampling LSDs by generating light-activated caspase-9 (casp9) enzymes. Collectively, this work provides a new resource for optical regulation of a broad range of target proteins in cell and developmental biology.
AU - Tichy, Alexandra-Madelaine
AU - Gerrard, Elliot J.
AU - Legrand, Julien M.D.
AU - Hobbs, Robin M.
AU - Janovjak, Harald L
ID - 6564
IS - 17
JF - Journal of Molecular Biology
SN - 00222836
TI - Engineering strategy and vector library for the rapid generation of modular light-controlled protein–protein interactions
VL - 431
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 - JOUR
AB - Methodologies that involve the use of nanoparticles as “artificial atoms” to rationally build materials in a bottom-up fashion are particularly well-suited to control the matter at the nanoscale. Colloidal synthetic routes allow for an exquisite control over such “artificial atoms” in terms of size, shape, and crystal phase as well as core and surface compositions. We present here a bottom-up approach to produce Pb–Ag–K–S–Te nanocomposites, which is a highly promising system for thermoelectric energy conversion. First, we developed a high-yield and scalable colloidal synthesis route to uniform lead sulfide (PbS) nanorods, whose tips are made of silver sulfide (Ag2S). We then took advantage of the large surface-to-volume ratio to introduce a p-type dopant (K) by replacing native organic ligands with K2Te. Upon thermal consolidation, K2Te-surface modified PbS–Ag2S nanorods yield p-type doped nanocomposites with PbTe and PbS as major phases and Ag2S and Ag2Te as embedded nanoinclusions. Thermoelectric characterization of such consolidated nanosolids showed a high thermoelectric figure-of-merit of 1 at 620 K.
AU - Ibáñez, Maria
AU - Genç, Aziz
AU - Hasler, Roger
AU - Liu, Yu
AU - Dobrozhan, Oleksandr
AU - Nazarenko, Olga
AU - Mata, María de la
AU - Arbiol, Jordi
AU - Cabot, Andreu
AU - Kovalenko, Maksym V.
ID - 6566
IS - 6
JF - ACS Nano
KW - colloidal nanoparticles
KW - asymmetric nanoparticles
KW - inorganic ligands
KW - heterostructures
KW - catalyst assisted growth
KW - nanocomposites
KW - thermoelectrics
SN - 1936-0851
TI - Tuning transport properties in thermoelectric nanocomposites through inorganic ligands and heterostructured building blocks
VL - 13
ER -
TY - CONF
AB - Knowledge distillation, i.e. one classifier being trained on the outputs of another classifier, is an empirically very successful technique for knowledge transfer between classifiers. It has even been observed that classifiers learn much faster and more reliably if trained with the outputs of another classifier as soft labels, instead of from ground truth data. So far, however, there is no satisfactory theoretical explanation of this phenomenon. In this work, we provide the first insights into the working mechanisms of distillation by studying the special case of linear and deep linear classifiers. Specifically, we prove a generalization bound that establishes fast convergence of the expected risk of a distillation-trained linear classifier. From the bound and its proof we extract three keyfactors that determine the success of distillation: data geometry – geometric properties of the datadistribution, in particular class separation, has an immediate influence on the convergence speed of the risk; optimization bias– gradient descentoptimization finds a very favorable minimum of the distillation objective; and strong monotonicity– the expected risk of the student classifier always decreases when the size of the training set grows.
AU - Bui Thi Mai, Phuong
AU - Lampert, Christoph
ID - 6569
T2 - Proceedings of the 36th International Conference on Machine Learning
TI - Towards understanding knowledge distillation
VL - 97
ER -
TY - JOUR
AB - Motivated by recent experimental observations of coherent many-body revivals in a constrained Rydbergatom chain, we construct a weak quasilocal deformation of the Rydberg-blockaded Hamiltonian, whichmakes the revivals virtually perfect. Our analysis suggests the existence of an underlying nonintegrableHamiltonian which supports an emergent SU(2)-spin dynamics within a small subspace of the many-bodyHilbert space. We show that such perfect dynamics necessitates the existence of atypical, nonergodicenergy eigenstates—quantum many-body scars. Furthermore, using these insights, we construct a toymodel that hosts exact quantum many-body scars, providing an intuitive explanation of their origin. Ourresults offer specific routes to enhancing coherent many-body revivals and provide a step towardestablishing the stability of quantum many-body scars in the thermodynamic limit.
AU - Choi, Soonwon
AU - Turner, Christopher J.
AU - Pichler, Hannes
AU - Ho, Wen Wei
AU - Michailidis, Alexios
AU - Papić, Zlatko
AU - Serbyn, Maksym
AU - Lukin, Mikhail D.
AU - Abanin, Dmitry A.
ID - 6575
IS - 22
JF - Physical Review Letters
SN - 00319007
TI - Emergent SU(2) dynamics and perfect quantum many-body scars
VL - 122
ER -
TY - JOUR
AB - The bottom-up assembly of colloidal nanocrystals is a versatile methodology to produce composite nanomaterials with precisely tuned electronic properties. Beyond the synthetic control over crystal domain size, shape, crystal phase, and composition, solution-processed nanocrystals allow exquisite surface engineering. This provides additional means to modulate the nanomaterial characteristics and particularly its electronic transport properties. For instance, inorganic surface ligands can be used to tune the type and concentration of majority carriers or to modify the electronic band structure. Herein, we report the thermoelectric properties of SnTe nanocomposites obtained from the consolidation of surface-engineered SnTe nanocrystals into macroscopic pellets. A CdSe-based ligand is selected to (i) converge the light and heavy bands through partial Cd alloying and (ii) generate CdSe nanoinclusions as a secondary phase within the SnTe matrix, thereby reducing the thermal conductivity. These SnTe-CdSe nanocomposites possess thermoelectric figures of merit of up to 1.3 at 850 K, which is, to the best of our knowledge, the highest thermoelectric figure of merit reported for solution-processed SnTe.
AU - Ibáñez, Maria
AU - Hasler, Roger
AU - Genç, Aziz
AU - Liu, Yu
AU - Kuster, Beatrice
AU - Schuster, Maximilian
AU - Dobrozhan, Oleksandr
AU - Cadavid, Doris
AU - Arbiol, Jordi
AU - Cabot, Andreu
AU - Kovalenko, Maksym V.
ID - 6586
IS - 20
JF - Journal of the American Chemical Society
SN - 0002-7863
TI - Ligand-mediated band engineering in bottom-up assembled SnTe nanocomposites for thermoelectric energy conversion
VL - 141
ER -
TY - CONF
AB - Modern machine learning methods often require more data for training than a single expert can provide. Therefore, it has become a standard procedure to collect data from external sources, e.g. via crowdsourcing. Unfortunately, the quality of these sources is not always guaranteed. As additional complications, the data might be stored in a distributed way, or might even have to remain private. In this work, we address the question of how to learn robustly in such scenarios. Studying the problem through the lens of statistical learning theory, we derive a procedure that allows for learning from all available sources, yet automatically suppresses irrelevant or corrupted data. We show by extensive experiments that our method provides significant improvements over alternative approaches from robust statistics and distributed optimization.
AU - Konstantinov, Nikola H
AU - Lampert, Christoph
ID - 6590
T2 - Proceedings of the 36th International Conference on Machine Learning
TI - Robust learning from untrusted sources
VL - 97
ER -
TY - JOUR
AB - It is well known that many problems in image recovery, signal processing, and machine learning can be modeled as finding zeros of the sum of maximal monotone and Lipschitz continuous monotone operators. Many papers have studied forward-backward splitting methods for finding zeros of the sum of two monotone operators in Hilbert spaces. Most of the proposed splitting methods in the literature have been proposed for the sum of maximal monotone and inverse-strongly monotone operators in Hilbert spaces. In this paper, we consider splitting methods for finding zeros of the sum of maximal monotone operators and Lipschitz continuous monotone operators in Banach spaces. We obtain weak and strong convergence results for the zeros of the sum of maximal monotone and Lipschitz continuous monotone operators in Banach spaces. Many already studied problems in the literature can be considered as special cases of this paper.
AU - Shehu, Yekini
ID - 6596
IS - 4
JF - Results in Mathematics
SN - 1422-6383
TI - Convergence results of forward-backward algorithms for sum of monotone operators in Banach spaces
VL - 74
ER -
TY - JOUR
AB - There is increasing evidence that both mechanical and biochemical signals play important roles in development and disease. The development of complex organisms, in particular, has been proposed to rely on the feedback between mechanical and biochemical patterning events. This feedback occurs at the molecular level via mechanosensation but can also arise as an emergent property of the system at the cellular and tissue level. In recent years, dynamic changes in tissue geometry, flow, rheology, and cell fate specification have emerged as key platforms of mechanochemical feedback loops in multiple processes. Here, we review recent experimental and theoretical advances in understanding how these feedbacks function in development and disease.
AU - Hannezo, Edouard B
AU - Heisenberg, Carl-Philipp J
ID - 6601
IS - 1
JF - Cell
SN - 00928674
TI - Mechanochemical feedback loops in development and disease
VL - 178
ER -
TY - JOUR
AB - Acute myeloid leukemia (AML) is a heterogeneous disease with respect to its genetic and molecular basis and to patients´ outcome. Clinical, cytogenetic, and mutational data are used to classify patients into risk groups with different survival, however, within-group heterogeneity is still an issue. Here, we used a robust likelihood-based survival modeling approach and publicly available gene expression data to identify a minimal number of genes whose combined expression values were prognostic of overall survival. The resulting gene expression signature (4-GES) consisted of 4 genes (SOCS2, IL2RA, NPDC1, PHGDH), predicted patient survival as an independent prognostic parameter in several cohorts of AML patients (total, 1272 patients), and further refined prognostication based on the European Leukemia Net classification. An oncogenic role of the top scoring gene in this signature, SOCS2, was investigated using MLL-AF9 and Flt3-ITD/NPM1c driven mouse models of AML. SOCS2 promoted leukemogenesis as well as the abundance, quiescence, and activity of AML stem cells. Overall, the 4-GES represents a highly discriminating prognostic parameter in AML, whose clinical applicability is greatly enhanced by its small number of genes. The newly established role of SOCS2 in leukemia aggressiveness and stemness raises the possibility that the signature might even be exploitable therapeutically.
AU - Nguyen, Chi Huu
AU - Glüxam, Tobias
AU - Schlerka, Angela
AU - Bauer, Katharina
AU - Grandits, Alexander M.
AU - Hackl, Hubert
AU - Dovey, Oliver
AU - Zöchbauer-Müller, Sabine
AU - Cooper, Jonathan L.
AU - Vassiliou, George S.
AU - Stoiber, Dagmar
AU - Wieser, Rotraud
AU - Heller, Gerwin
ID - 6607
IS - 1
JF - Scientific Reports
TI - SOCS2 is part of a highly prognostic 4-gene signature in AML and promotes disease aggressiveness
VL - 9
ER -
TY - JOUR
AB - We use the canonical bases produced by the tri-partition algorithm in (Edelsbrunner and Ölsböck, 2018) to open and close holes in a polyhedral complex, K. In a concrete application, we consider the Delaunay mosaic of a finite set, we let K be an Alpha complex, and we use the persistence diagram of the distance function to guide the hole opening and closing operations. The dependences between the holes define a partial order on the cells in K that characterizes what can and what cannot be constructed using the operations. The relations in this partial order reveal structural information about the underlying filtration of complexes beyond what is expressed by the persistence diagram.
AU - Edelsbrunner, Herbert
AU - Ölsböck, Katharina
ID - 6608
JF - Computer Aided Geometric Design
TI - Holes and dependences in an ordered complex
VL - 73
ER -
TY - JOUR
AB - Mechanical systems facilitate the development of a hybrid quantum technology comprising electrical, optical, atomic and acoustic degrees of freedom1, and entanglement is essential to realize quantum-enabled devices. Continuous-variable entangled fields—known as Einstein–Podolsky–Rosen (EPR) states—are spatially separated two-mode squeezed states that can be used for quantum teleportation and quantum communication2. In the optical domain, EPR states are typically generated using nondegenerate optical amplifiers3, and at microwave frequencies Josephson circuits can serve as a nonlinear medium4,5,6. An outstanding goal is to deterministically generate and distribute entangled states with a mechanical oscillator, which requires a carefully arranged balance between excitation, cooling and dissipation in an ultralow noise environment. Here we observe stationary emission of path-entangled microwave radiation from a parametrically driven 30-micrometre-long silicon nanostring oscillator, squeezing the joint field operators of two thermal modes by 3.40 decibels below the vacuum level. The motion of this micromechanical system correlates up to 50 photons per second per hertz, giving rise to a quantum discord that is robust with respect to microwave noise7. Such generalized quantum correlations of separable states are important for quantum-enhanced detection8 and provide direct evidence of the non-classical nature of the mechanical oscillator without directly measuring its state9. This noninvasive measurement scheme allows to infer information about otherwise inaccessible objects, with potential implications for sensing, open-system dynamics and fundamental tests of quantum gravity. In the future, similar on-chip devices could be used to entangle subsystems on very different energy scales, such as microwave and optical photons.
AU - Barzanjeh, Shabir
AU - Redchenko, Elena
AU - Peruzzo, Matilda
AU - Wulf, Matthias
AU - Lewis, Dylan
AU - Arnold, Georg M
AU - Fink, Johannes M
ID - 6609
JF - Nature
TI - Stationary entangled radiation from micromechanical motion
VL - 570
ER -
TY - JOUR
AB - Cell polarity is crucial for the coordinated development of all multicellular organisms. In plants, this is exemplified by the PIN-FORMED (PIN) efflux carriers of the phytohormone auxin: The polar subcellular localization of the PINs is instructive to the directional intercellular auxin transport, and thus to a plethora of auxin-regulated growth and developmental processes. Despite its importance, the regulation of PIN polar subcellular localization remains poorly understood. Here, we have employed advanced live-cell imaging techniques to study the roles of microtubules and actin microfilaments in the establishment of apical polar localization of PIN2 in the epidermis of the Arabidopsis root meristem. We report that apical PIN2 polarity requires neither intact actin microfilaments nor microtubules, suggesting that the primary spatial cue for polar PIN distribution is likely independent of cytoskeleton-guided endomembrane trafficking.
AU - Glanc, Matous
AU - Fendrych, Matyas
AU - Friml, Jiří
ID - 6611
IS - 6
JF - Biomolecules
TI - PIN2 polarity establishment in arabidopsis in the absence of an intact cytoskeleton
VL - 9
ER -
TY - JOUR
AB - The effective large-scale properties of materials with random heterogeneities on a small scale are typically determined by the method of representative volumes: a sample of the random material is chosen—the representative volume—and its effective properties are computed by the cell formula. Intuitively, for a fixed sample size it should be possible to increase the accuracy of the method by choosing a material sample which captures the statistical properties of the material particularly well; for example, for a composite material consisting of two constituents, one would select a representative volume in which the volume fraction of the constituents matches closely with their volume fraction in the overall material. Inspired by similar attempts in materials science, Le Bris, Legoll and Minvielle have designed a selection approach for representative volumes which performs remarkably well in numerical examples of linear materials with moderate contrast. In the present work, we provide a rigorous analysis of this selection approach for representative volumes in the context of stochastic homogenization of linear elliptic equations. In particular, we prove that the method essentially never performs worse than a random selection of the material sample and may perform much better if the selection criterion for the material samples is chosen suitably.
AU - Fischer, Julian L
ID - 6617
IS - 2
JF - Archive for Rational Mechanics and Analysis
SN - 0003-9527
TI - The choice of representative volumes in the approximation of effective properties of random materials
VL - 234
ER -
TY - JOUR
AB - This paper establishes an asymptotic formula with a power-saving error term for the number of rational points of bounded height on the singular cubic surface of ℙ3ℚ given by the following equation 𝑥0(𝑥21+𝑥22)−𝑥33=0 in agreement with the Manin-Peyre conjectures.
AU - De La Bretèche, Régis
AU - Destagnol, Kevin N
AU - Liu, Jianya
AU - Wu, Jie
AU - Zhao, Yongqiang
ID - 6620
IS - 12
JF - Science China Mathematics
SN - 16747283
TI - On a certain non-split cubic surface
VL - 62
ER -
TY - JOUR
AB - We read with great interest the recent work in PNAS by Bergero et al. (1) describing differences in male and female recombination patterns on the guppy (Poecilia reticulata) sex chromosome. We fully agree that recombination in males is largely confined to the ends of the sex chromosome. Bergero et al. interpret these results to suggest that our previous findings of population-level variation in the degree of sex chromosome differentiation in this species (2) are incorrect. However, we suggest that their results are entirely consistent with our previous report, and that their interpretation presents a false controversy.
AU - Wright, Alison E.
AU - Darolti, Iulia
AU - Bloch, Natasha I.
AU - Oostra, Vicencio
AU - Sandkam, Benjamin A.
AU - Buechel, Séverine D.
AU - Kolm, Niclas
AU - Breden, Felix
AU - Vicoso, Beatriz
AU - Mank, Judith E.
ID - 6621
IS - 26
JF - Proceedings of the National Academy of Sciences of the United States of America
TI - On the power to detect rare recombination events
VL - 116
ER -
TY - JOUR
AB - Cortical microtubule arrays in elongating epidermal cells in both the root and stem of plants have the propensity of dynamic reorientations that are correlated with the activation or inhibition of growth. Factors regulating plant growth, among them the hormone auxin, have been recognized as regulators of microtubule array orientations. Some previous work in the field has aimed at elucidating the causal relationship between cell growth, the signaling of auxin or other growth-regulating factors, and microtubule array reorientations, with various conclusions. Here, we revisit this problem of causality with a comprehensive set of experiments in Arabidopsis thaliana, using the now available pharmacological and genetic tools. We use isolated, auxin-depleted hypocotyls, an experimental system allowing for full control of both growth and auxin signaling. We demonstrate that reorientation of microtubules is not directly triggered by an auxin signal during growth activation. Instead, reorientation is triggered by the activation of the growth process itself and is auxin-independent in its nature. We discuss these findings in the context of previous relevant work, including that on the mechanical regulation of microtubule array orientation.
AU - Adamowski, Maciek
AU - Li, Lanxin
AU - Friml, Jiří
ID - 6627
IS - 13
JF - International Journal of Molecular Sciences
TI - Reorientation of cortical microtubule arrays in the hypocotyl of arabidopsis thaliana is induced by the cell growth process and independent of auxin signaling
VL - 20
ER -
TY - 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 - JOUR
AB - The spatiotemporal organization of cell divisions constitutes an integral part in the development of multicellular organisms, and mis-regulation of cell divisions can lead to severe developmental defects. Cell divisions have an important morphogenetic function in development by regulating growth and shape acquisition of developing tissues, and, conversely, tissue morphogenesis is known to affect both the rate and orientation of cell divisions. Moreover, cell divisions are associated with an extensive reorganization of the cytoskeleton and adhesion apparatus in the dividing cells that in turn can affect large-scale tissue rheological properties. Thus, the interplay between cell divisions and tissue morphogenesis plays a key role in embryo and tissue morphogenesis.
AU - Godard, Benoit G
AU - Heisenberg, Carl-Philipp J
ID - 6631
JF - Current Opinion in Cell Biology
SN - 0955-0674
TI - Cell division and tissue mechanics
VL - 60
ER -
TY - JOUR
AB - We consider a two-component Bose gas in two dimensions at a low temperature with short-range repulsive interaction. In the coexistence phase where both components are superfluid, interspecies interactions induce a nondissipative drag between the two superfluid flows (Andreev-Bashkin effect). We show that this behavior leads to a modification of the usual Berezinskii-Kosterlitz-Thouless (BKT) transition in two dimensions. We extend the renormalization of the superfluid densities at finite temperature using the renormalization-group approach and find that the vortices of one component have a large influence on the superfluid properties of the other, mediated by the nondissipative drag. The extended BKT flow equations indicate that the occurrence of the vortex unbinding transition in one of the components can induce the breakdown of superfluidity also in the other, leading to a locking phenomenon for the critical temperatures of the two gases.
AU - Karle, Volker
AU - Defenu, Nicolò
AU - Enss, Tilman
ID - 6632
IS - 6
JF - Physical Review A
SN - 24699926
TI - Coupled superfluidity of binary Bose mixtures in two dimensions
VL - 99
ER -
TY - JOUR
AB - In this paper we prove several new results around Gromov's waist theorem. We give a simple proof of Vaaler's theorem on sections of the unit cube using the Borsuk-Ulam-Crofton technique, consider waists of real and complex projective spaces, flat tori, convex bodies in Euclidean space; and establish waist-type results in terms of the Hausdorff measure.
AU - Akopyan, Arseniy
AU - Hubard, Alfredo
AU - Karasev, Roman
ID - 6634
IS - 2
JF - Topological Methods in Nonlinear Analysis
TI - Lower and upper bounds for the waists of different spaces
VL - 53
ER -
TY - JOUR
AB - The environment changes constantly at various time scales and, in order to survive, species need to keep adapting. Whether these species succeed in avoiding extinction is a major evolutionary question. Using a multilocus evolutionary model of a mutation‐limited population adapting under strong selection, we investigate the effects of the frequency of environmental fluctuations on adaptation. Our results rely on an “adaptive‐walk” approximation and use mathematical methods from evolutionary computation theory to investigate the interplay between fluctuation frequency, the similarity of environments, and the number of loci contributing to adaptation. First, we assume a linear additive fitness function, but later generalize our results to include several types of epistasis. We show that frequent environmental changes prevent populations from reaching a fitness peak, but they may also prevent the large fitness loss that occurs after a single environmental change. Thus, the population can survive, although not thrive, in a wide range of conditions. Furthermore, we show that in a frequently changing environment, the similarity of threats that a population faces affects the level of adaptation that it is able to achieve. We check and supplement our analytical results with simulations.
AU - Trubenova, Barbora
AU - Krejca, Martin
AU - Lehre, Per Kristian
AU - Kötzing, Timo
ID - 6637
IS - 7
JF - Evolution
TI - Surfing on the seascape: Adaptation in a changing environment
VL - 73
ER -
TY - JOUR
AB - The crossing number of a graph G is the least number of crossings over all possible drawings of G. We present a structural characterization of graphs with crossing number one.
AU - Silva, André
AU - Arroyo Guevara, Alan M
AU - Richter, Bruce
AU - Lee, Orlando
ID - 6638
IS - 11
JF - Discrete Mathematics
SN - 0012-365X
TI - Graphs with at most one crossing
VL - 342
ER -
TY - CONF
AB - We present a thermodynamically based approach to the design of models for viscoelastic fluids with stress diffusion effect. In particular, we show how to add a stress diffusion term to some standard viscoelastic rate-type models (Giesekus, FENE-P, Johnson–Segalman, Phan-Thien–Tanner and Bautista–Manero–Puig) so that the resulting models with the added stress diffusion term are thermodynamically consistent in the sense that they obey the first and the second law of thermodynamics. We point out the potential applications of the provided thermodynamical background in the study of flows of fluids described by the proposed models.
AU - Dostalík, Mark
AU - Pruša, Vít
AU - Skrivan, Tomas
ID - 6642
T2 - AIP Conference Proceedings
TI - On diffusive variants of some classical viscoelastic rate-type models
VL - 2107
ER -
TY - CONF
AB - We demonstrate robust retention of valley coherence and its control via polariton pseudospin precession through the optical TE-TM splitting in bilayer WS2 microcavity exciton polaritons at room temperature.
AU - Khatoniar, Mandeep
AU - Yama, Nicholas
AU - Ghazaryan, Areg
AU - Guddala, Sriram
AU - Ghaemi, Pouyan
AU - Menon, Vinod
ID - 6646
SN - 9781943580576
T2 - CLEO: Applications and Technology
TI - Room temperature control of valley coherence in bilayer WS2 exciton polaritons
ER -
TY - CONF
AB - The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r-1)+1 points in R^d, one can find a partition X=X_1 cup ... cup X_r of X, such that the convex hulls of the X_i, i=1,...,r, all share a common point. In this paper, we prove a strengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span floor[n/3] vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Alvarez-Rebollar et al. guarantees floor[n/6] pairwise crossing triangles. Our result generalizes to a result about simplices in R^d,d >=2.
AU - Fulek, Radoslav
AU - Gärtner, Bernd
AU - Kupavskii, Andrey
AU - Valtr, Pavel
AU - Wagner, Uli
ID - 6647
SN - 1868-8969
T2 - 35th International Symposium on Computational Geometry
TI - The crossing Tverberg theorem
VL - 129
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 - We propose a novel technique for the automatic design of molds to cast highly complex shapes. The technique generates composite, two-piece molds. Each mold piece is made up of a hard plastic shell and a flexible silicone part. Thanks to the thin, soft, and smartly shaped silicone part, which is kept in place by a hard plastic shell, we can cast objects of unprecedented complexity. An innovative algorithm based on a volumetric analysis defines the layout of the internal cuts in the silicone mold part. Our approach can robustly handle thin protruding features and intertwined topologies that have caused previous methods to fail. We compare our results with state of the art techniques, and we demonstrate the casting of shapes with extremely complex geometry.
AU - Alderighi, Thomas
AU - Malomo, Luigi
AU - Giorgi, Daniela
AU - Bickel, Bernd
AU - Cignoni, Paolo
AU - Pietroni, Nico
ID - 6650
IS - 4
JF - ACM Transactions on Graphics
SN - 0730-0301
TI - Volume-aware design of composite molds
VL - 38
ER -
TY - JOUR
AB - In this article a model is described how Open Access definitions can be formed on the basis of objective criteria. The common Open Access definitions such as "gold" and "green" are not exactly defined. This becomes a problem as soon as one begins to measure Open Access, for example if the development of the Open Access share should be monitored. This was discussed in the working group on Open Access Monitoring of the AT2OA project and the present model was developed, which is based on 5 critics with 4 characteristics: location, licence, version, embargo and conditions of the Open Access publication are taken into account. In the meantime, the model has also been tested in practice using R scripts, and the initial results are quite promising.
AU - Danowski, Patrick
ID - 6657
IS - 1
JF - VOEB-Mitteilungen
TI - An Austrian proposal for the classification of Open Access Tuples (COAT) - distinguish different open access types beyond colors
VL - 72
ER -
TY - JOUR
AB - New genes are a major source of novelties, and a disproportionate amount of them are known to show testis expression in later phases of male gametogenesis in different groups such as mammals and plants. Here, we propose that this enhanced expression is a consequence of haploid selection during the latter stages of male gametogenesis. Because emerging adaptive mutations will be fixed faster if their phenotypes are expressed by haploid rather than diploid genotypes, new genes with advantageous functions arising during this unique stage of development have a better chance to become fixed. To test this hypothesis, expression levels of genes of differing evolutionary age were examined at various stages of Drosophila spermatogenesis. We found, consistent with a model based on haploid selection, that new Drosophila genes are both expressed in later haploid phases of spermatogenesis and harbor a significant enrichment of adaptive mutations. Additionally, the observed overexpression of new genes in the latter phases of spermatogenesis was limited to the autosomes. Because all male cells exhibit hemizygous expression for X-linked genes (and therefore effectively haploid), there is no expectation that selection acting on late spermatogenesis will have a different effect on X-linked genes in comparison to initial diploid phases. Together, our proposed hypothesis and the analyzed data suggest that natural selection in haploid cells elucidates several aspects of the origin of new genes by explaining the general prevalence of their testis expression, and a parsimonious solution for new alleles to avoid being lost by genetic drift or pseudogenization.
AU - Raices, Julia
AU - Otto, Paulo
AU - Vibranovski, Maria
ID - 6658
IS - 7
JF - Genome Research
TI - Haploid selection drives new gene male germline expression
VL - 29
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 - Commercially available full-color 3D printing allows for detailed control of material deposition in a volume, but an exact reproduction of a target surface appearance is hampered by the strong subsurface scattering that causes nontrivial volumetric cross-talk at the print surface. Previous work showed how an iterative optimization scheme based on accumulating absorptive materials at the surface can be used to find a volumetric distribution of print materials that closely approximates a given target appearance.
In this work, we first revisit the assumption that pushing the absorptive materials to the surface results in minimal volumetric cross-talk. We design a full-fledged optimization on a small domain for this task and confirm this previously reported heuristic. Then, we extend the above approach that is critically limited to color reproduction on planar surfaces, to arbitrary 3D shapes. Our method enables high-fidelity color texture reproduction on 3D prints by effectively compensating for internal light scattering within arbitrarily shaped objects. In addition, we propose a content-aware gamut mapping that significantly improves color reproduction for the pathological case of thin geometric features. Using a wide range of sample objects with complex textures and geometries, we demonstrate color reproduction whose fidelity is superior to state-of-the-art drivers for color 3D printers.
AU - Sumin, Denis
AU - Weyrich, Tim
AU - Rittig, Tobias
AU - Babaei, Vahid
AU - Nindel, Thomas
AU - Wilkie, Alexander
AU - Didyk, Piotr
AU - Bickel, Bernd
AU - Křivánek, Jaroslav
AU - Myszkowski, Karol
ID - 6660
IS - 4
JF - ACM Transactions on Graphics
SN - 0730-0301
TI - Geometry-aware scattering compensation for 3D printing
VL - 38
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 - 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 - JOUR
AB - In this paper we discuss three results. The first two concern general sets of positive reach: we first characterize the reach of a closed set by means of a bound on the metric distortion between the distance measured in the ambient Euclidean space and the shortest path distance measured in the set. Secondly, we prove that the intersection of a ball with radius less than the reach with the set is geodesically convex, meaning that the shortest path between any two points in the intersection lies itself in the intersection. For our third result we focus on manifolds with positive reach and give a bound on the angle between tangent spaces at two different points in terms of the reach and the distance between the two points.
AU - Boissonnat, Jean-Daniel
AU - Lieutier, André
AU - Wintraecken, Mathijs
ID - 6671
IS - 1-2
JF - Journal of Applied and Computational Topology
SN - 2367-1726
TI - The reach, metric distortion, geodesic convexity and the variation of tangent spaces
VL - 3
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 - Several classic problems in graph processing and computational geometry are solved via incremental algorithms, which split computation into a series of small tasks acting on shared state, which gets updated progressively. While the sequential variant of such algorithms usually specifies a fixed (but sometimes random) order in which the tasks should be performed, a standard approach to parallelizing such algorithms is to relax this constraint to allow for out-of-order parallel execution. This is the case for parallel implementations of Dijkstra's single-source shortest-paths (SSSP) algorithm, and for parallel Delaunay mesh triangulation. While many software frameworks parallelize incremental computation in this way, it is still not well understood whether this relaxed ordering approach can still provide any complexity guarantees. In this paper, we address this problem, and analyze the efficiency guarantees provided by a range of incremental algorithms when parallelized via relaxed schedulers. We show that, for algorithms such as Delaunay mesh triangulation and sorting by insertion, schedulers with a maximum relaxation factor of k in terms of the maximum priority inversion allowed will introduce a maximum amount of wasted work of O(łog n poly(k)), where n is the number of tasks to be executed. For SSSP, we show that the additional work is O(poly(k), dmax / wmin), where dmax is the maximum distance between two nodes, and wmin is the minimum such distance. In practical settings where n >> k, this suggests that the overheads of relaxation will be outweighed by the improved scalability of the relaxed scheduler. On the negative side, we provide lower bounds showing that certain algorithms will inherently incur a non-trivial amount of wasted work due to scheduler relaxation, even for relatively benign relaxed schedulers.
AU - Alistarh, Dan-Adrian
AU - Nadiradze, Giorgi
AU - Koval, Nikita
ID - 6673
SN - 9781450361842
T2 - 31st ACM Symposium on Parallelism in Algorithms and Architectures
TI - Efficiency guarantees for parallel incremental algorithms under relaxed schedulers
ER -
TY - CONF
AB - It is impossible to deterministically solve wait-free consensus in an asynchronous system. The classic proof uses a valency argument, which constructs an infinite execution by repeatedly extending a finite execution. We introduce extension-based proofs, a class of impossibility proofs that are modelled as an interaction between a prover and a protocol and that include valency arguments.
Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k ≥ 2 processes in a wait-free manner. However, it was unknown whether proofs based on simpler techniques were possible. We show that this impossibility result cannot be obtained by an extension-based proof and, hence, extension-based proofs are limited in power.
AU - Alistarh, Dan-Adrian
AU - Aspnes, James
AU - Ellen, Faith
AU - Gelashvili, Rati
AU - Zhu, Leqi
ID - 6676
SN - 9781450367059
T2 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
TI - Why extension-based proofs fail
ER -
TY - CONF
AB - The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.
We show that solving the END−OF−METERED−LINE problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD. Our result opens up the possibility of sampling moderately-sized games for which it is hard to find a Nash equilibrium, by reducing the inversion of appropriately chosen one-way functions to #SAT.
Our main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n).
AU - Choudhuri, Arka Rai
AU - Hubáček, Pavel
AU - Kamath Hosdurg, Chethan
AU - Pietrzak, Krzysztof Z
AU - Rosen, Alon
AU - Rothblum, Guy N.
ID - 6677
SN - 9781450367059
T2 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019
TI - Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
ER -
TY - JOUR
AB - This paper analyzes how partial selfing in a large source population influences its ability to colonize a new habitat via the introduction of a few founder individuals. Founders experience inbreeding depression due to partially recessive deleterious alleles as well as maladaptation to the new environment due to selection on a large number of additive loci. I first introduce a simplified version of the Inbreeding History Model (Kelly, 2007) in order to characterize mutation‐selection balance in a large, partially selfing source population under selection involving multiple non‐identical loci. I then use individual‐based simulations to study the eco‐evolutionary dynamics of founders establishing in the new habitat under a model of hard selection. The study explores how selfing rate shapes establishment probabilities of founders via effects on both inbreeding depression and adaptability to the new environment, and also distinguishes the effects of selfing on the initial fitness of founders from its effects on the long‐term adaptive response of the populations they found. A high rate of (but not complete) selfing is found to aid establishment over a wide range of parameters, even in the absence of mate limitation. The sensitivity of the results to assumptions about the nature of polygenic selection are discussed.
AU - Sachdeva, Himani
ID - 6680
IS - 9
JF - Evolution
SN - 0014-3820
TI - Effect of partial selfing and polygenic selection on establishment in a new habitat
VL - 73
ER -
TY - THES
AB - The first part of the thesis considers the computational aspects of the homotopy groups πd(X) of a topological space X. It is well known that there is no algorithm to decide whether the fundamental group π1(X) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute the higher homotopy group πd(X) for any given d ≥ 2.
However, these algorithms come with a caveat: They compute the isomorphism type of πd(X), d ≥ 2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πd(X). We present an algorithm that, given a simply connected space X, computes πd(X) and represents its elements as simplicial maps from suitable triangulations of the d-sphere Sd to X. For fixed d, the algorithm runs in time exponential in size(X), the number of simplices of X. Moreover, we prove that this is optimal: For every fixed d ≥ 2,
we construct a family of simply connected spaces X such that for any simplicial map representing a generator of πd(X), the size of the triangulation of S d on which the map is defined, is exponential in size(X).
In the second part of the thesis, we prove that the following question is algorithmically undecidable for d < ⌊3(k+1)/2⌋, k ≥ 5 and (k, d) ̸= (5, 7), which covers essentially everything outside the meta-stable range: Given a finite simplicial complex K of dimension k, decide whether there exists a piecewise-linear (i.e., linear on an arbitrarily fine subdivision of K) embedding f : K ↪→ Rd of K into a d-dimensional Euclidean space.
AU - Zhechev, Stephan Y
ID - 6681
SN - 2663-337X
TI - Algorithmic aspects of homotopy theory and embeddability
ER -
TY - JOUR
AB - Sexual dimorphism in morphology, physiology or life history traits is common in dioecious plants at reproductive maturity, but it is typically inconspicuous or absent in juveniles. Although plants of different sexes probably begin to diverge in gene expression both before their reproduction commences and before dimorphism becomes readily apparent, to our knowledge transcriptome-wide differential gene expression has yet to be demonstrated for any angiosperm species.
AU - Cossard, Guillaume
AU - Toups, Melissa A
AU - Pannell, John
ID - 6710
IS - 7
JF - Annals of botany
TI - Sexual dimorphism and rapid turnover in gene expression in pre-reproductive seedlings of a dioecious herb
VL - 123
ER -
TY - JOUR
AB - Evolutionary studies are often limited by missing data that are critical to understanding the history of selection. Selection experiments, which reproduce rapid evolution under controlled conditions, are excellent tools to study how genomes evolve under selection. Here we present a genomic dissection of the Longshanks selection experiment, in which mice were selectively bred over 20 generations for longer tibiae relative to body mass, resulting in 13% longer tibiae in two replicates. We synthesized evolutionary theory, genome sequences and molecular genetics to understand the selection response and found that it involved both polygenic adaptation and discrete loci of major effect, with the strongest loci tending to be selected in parallel between replicates. We show that selection may favor de-repression of bone growth through inactivating two limb enhancers of an inhibitor, Nkx3-2. Our integrative genomic analyses thus show that it is possible to connect individual base-pair changes to the overall selection response.
AU - Castro, João Pl
AU - Yancoskie, Michelle N.
AU - Marchini, Marta
AU - Belohlavy, Stefanie
AU - Hiramatsu, Layla
AU - Kučka, Marek
AU - Beluch, William H.
AU - Naumann, Ronald
AU - Skuplik, Isabella
AU - Cobb, John
AU - Barton, Nicholas H
AU - Rolian, Campbell
AU - Chan, Yingguang Frank
ID - 6713
JF - eLife
TI - An integrative genomic analysis of the Longshanks selection experiment for longer limbs in mice
VL - 8
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 - 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 - Two-player games on graphs are widely studied in formal methods, as they model the interaction between a system and its environment. The game is played by moving a token throughout a graph to produce an infinite path. There are several common modes to determine how the players move the token through the graph; e.g., in turn-based games the players alternate turns in moving the token. We study the bidding mode of moving the token, which, to the best of our knowledge, has never been studied in infinite-duration games. The following bidding rule was previously defined and called Richman bidding. Both players have separate budgets, which sum up to 1. In each turn, a bidding takes place: Both players submit bids simultaneously, where a bid is legal if it does not exceed the available budget, and the higher bidder pays his bid to the other player and moves the token. The central question studied in bidding games is a necessary and sufficient initial budget for winning the game: a threshold budget in a vertex is a value t ∈ [0, 1] such that if Player 1’s budget exceeds t, he can win the game; and if Player 2’s budget exceeds 1 − t, he can win the game. Threshold budgets were previously shown to exist in every vertex of a reachability game, which have an interesting connection with random-turn games—a sub-class of simple stochastic games in which the player who moves is chosen randomly. We show the existence of threshold budgets for a qualitative class of infinite-duration games, namely parity games, and a quantitative class, namely mean-payoff games. The key component of the proof is a quantitative solution to strongly connected mean-payoff bidding games in which we extend the connection with random-turn games to these games, and construct explicit optimal strategies for both players.
AU - Avni, Guy
AU - Henzinger, Thomas A
AU - Chonev, Ventsislav K
ID - 6752
IS - 4
JF - Journal of the ACM
SN - 00045411
TI - Infinite-duration bidding games
VL - 66
ER -
TY - JOUR
AB - Differentiated sex chromosomes are accompanied by a difference in gene dose between X/Z-specific and autosomal genes. At the transcriptomic level, these sex-linked genes can lead to expression imbalance, or gene dosage can be compensated by epigenetic mechanisms and results into expression level equalization. Schistosoma mansoni has been previously described as a ZW species (i.e., female heterogamety, in opposition to XY male heterogametic species) with a partial dosage compensation, but underlying mechanisms are still unexplored. Here, we combine transcriptomic (RNA-Seq) and epigenetic data (ChIP-Seq against H3K4me3, H3K27me3,andH4K20me1histonemarks) in free larval cercariae and intravertebrate parasitic stages. For the first time, we describe differences in dosage compensation status in ZW females, depending on the parasitic status: free cercariae display global dosage compensation, whereas intravertebrate stages show a partial dosage compensation. We also highlight regional differences of gene expression along the Z chromosome in cercariae, but not in the intravertebrate stages. Finally, we feature a consistent permissive chromatin landscape of the Z chromosome in both sexes and stages. We argue that dosage compensation in schistosomes is characterized by chromatin remodeling mechanisms in the Z-specific region.
AU - Picard, Marion A L
AU - Vicoso, Beatriz
AU - Roquis, David
AU - Bulla, Ingo
AU - Augusto, Ronaldo C.
AU - Arancibia, Nathalie
AU - Grunau, Christoph
AU - Boissier, Jérôme
AU - Cosseau, Céline
ID - 6755
IS - 7
JF - Genome biology and evolution
TI - Dosage compensation throughout the Schistosoma mansoni lifecycle: Specific chromatin landscape of the Z chromosome
VL - 11
ER -
TY - JOUR
AB - We study the topology generated by the temperature fluctuations of the cosmic microwave background (CMB) radiation, as quantified by the number of components and holes, formally given by the Betti numbers, in the growing excursion sets. We compare CMB maps observed by the Planck satellite with a thousand simulated maps generated according to the ΛCDM paradigm with Gaussian distributed fluctuations. The comparison is multi-scale, being performed on a sequence of degraded maps with mean pixel separation ranging from 0.05 to 7.33°. The survey of the CMB over 𝕊2 is incomplete due to obfuscation effects by bright point sources and other extended foreground objects like our own galaxy. To deal with such situations, where analysis in the presence of “masks” is of importance, we introduce the concept of relative homology. The parametric χ2-test shows differences between observations and simulations, yielding p-values at percent to less than permil levels roughly between 2 and 7°, with the difference in the number of components and holes peaking at more than 3σ sporadically at these scales. The highest observed deviation between the observations and simulations for b0 and b1 is approximately between 3σ and 4σ at scales of 3–7°. There are reports of mildly unusual behaviour of the Euler characteristic at 3.66° in the literature, computed from independent measurements of the CMB temperature fluctuations by Planck’s predecessor, the Wilkinson Microwave Anisotropy Probe (WMAP) satellite. The mildly anomalous behaviour of the Euler characteristic is phenomenologically related to the strongly anomalous behaviour of components and holes, or the zeroth and first Betti numbers, respectively. Further, since these topological descriptors show consistent anomalous behaviour over independent measurements of Planck and WMAP, instrumental and systematic errors may be an unlikely source. These are also the scales at which the observed maps exhibit low variance compared to the simulations, and approximately the range of scales at which the power spectrum exhibits a dip with respect to the theoretical model. Non-parametric tests show even stronger differences at almost all scales. Crucially, Gaussian simulations based on power-spectrum matching the characteristics of the observed dipped power spectrum are not able to resolve the anomaly. Understanding the origin of the anomalies in the CMB, whether cosmological in nature or arising due to late-time effects, is an extremely challenging task. Regardless, beyond the trivial possibility that this may still be a manifestation of an extreme Gaussian case, these observations, along with the super-horizon scales involved, may motivate the study of primordial non-Gaussianity. Alternative scenarios worth exploring may be models with non-trivial topology, including topological defect models.
AU - Pranav, Pratyush
AU - Adler, Robert J.
AU - Buchert, Thomas
AU - Edelsbrunner, Herbert
AU - Jones, Bernard J.T.
AU - Schwartzman, Armin
AU - Wagner, Hubert
AU - Van De Weygaert, Rien
ID - 6756
JF - Astronomy and Astrophysics
SN - 00046361
TI - Unexpected topology of the temperature fluctuations in the cosmic microwave background
VL - 627
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 - JOUR
AB - We present and study novel optimal control problems motivated by the search for photovoltaic materials with high power-conversion efficiency. The material must perform the first step: convert light (photons) into electronic excitations. We formulate various desirable properties of the excitations as mathematical control goals at the Kohn-Sham-DFT level
of theory, with the control being given by the nuclear charge distribution. We prove that nuclear distributions exist which give rise to optimal HOMO-LUMO excitations, and present illustrative numerical simulations for 1D finite nanocrystals. We observe pronounced goal-dependent features such as large electron-hole separation, and a hierarchy of length scales: internal HOMO and LUMO wavelengths < atomic spacings < (irregular) fluctuations of the doping profiles < system size.
AU - Friesecke, Gero
AU - Kniely, Michael
ID - 6762
IS - 3
JF - Multiscale Modeling and Simulation
SN - 15403459
TI - New optimal control problems in density functional theory motivated by photovoltaics
VL - 17
ER -
TY - JOUR
AB - When grape-sized aqueous dimers are irradiated in a microwave oven, an intense electromagnetic hotspot forms at their point of contact, often igniting a plasma. Here we show that this irradiation can result in the injection of mechanical energy. By examining irradiated hydrogel dimers through high-speed imaging, we find that they repeatedly bounce off of each other while irradiated. We determine that an average of 1 lJ of mechanical energy is injected into the pair during each collision. Furthermore, a characteristic high-pitched audio signal is found to accompany each collision.
We show that both the audio signal and the energy injection arise via an interplay between vaporization and elastic deformations in the region of contact, the so-called ‘elastic Liedenfrost effect’. Our results establish a novel, non-contact method of injecting mechanical energy into soft matter systems, suggesting application in fields such as soft robotics.
AU - Khattak, Hamza K.
AU - Waitukaitis, Scott R
AU - Slepkov, Aaron D.
ID - 6763
IS - 29
JF - Soft Matter
SN - 1744683X
TI - Microwave induced mechanical activation of hydrogel dimers
VL - 15
ER -
TY - JOUR
AB - An important adaptation during colonization of land by plants is gravitropic growth of roots, which enabled roots to reach water and nutrients, and firmly anchor plants in the ground. Here we provide insights into the evolution of an efficient root gravitropic mechanism in the seed plants. Architectural innovation, with gravity perception constrained in the root tips
along with a shootward transport route for the phytohormone auxin, appeared only upon the emergence of seed plants. Interspecies complementation and protein domain swapping revealed functional innovations within the PIN family of auxin transporters leading to the evolution of gravitropism-specific PINs. The unique apical/shootward subcellular localization of PIN proteins is the major evolutionary innovation that connected the anatomically separated sites of gravity perception and growth response via the mobile auxin signal. We conclude that the crucial anatomical and functional components emerged hand-in-hand to facilitate the evolution of fast gravitropic response, which is one of the major adaptations of seed plants to dry land.
AU - Zhang, Yuzhou
AU - Xiao, G
AU - Wang, X
AU - Zhang, Xixi
AU - Friml, Jiří
ID - 6778
JF - Nature Communications
SN - 2041-1723
TI - Evolution of fast root gravitropism in seed plants
VL - 10
ER -
TY - JOUR
AB - Recent studies suggest that unstable recurrent solutions of the Navier-Stokes equation provide new insights
into dynamics of turbulent flows. In this study, we compute an extensive network of dynamical connections
between such solutions in a weakly turbulent quasi-two-dimensional Kolmogorov flow that lies in the inversion symmetric subspace. In particular, we find numerous isolated heteroclinic connections between different
types of solutions—equilibria, periodic, and quasiperiodic orbits—as well as continua of connections forming
higher-dimensional connecting manifolds. We also compute a homoclinic connection of a periodic orbit and
provide strong evidence that the associated homoclinic tangle forms the chaotic repeller that underpins transient
turbulence in the symmetric subspace.
AU - Suri, Balachandra
AU - Pallantla, Ravi Kumar
AU - Schatz, Michael F.
AU - Grigoriev, Roman O.
ID - 6779
IS - 1
JF - Physical Review E
SN - 2470-0045
TI - Heteroclinic and homoclinic connections in a Kolmogorov-like flow
VL - 100
ER -
TY - JOUR
AB - Mathematical models have been used successfully at diverse scales of biological organization, ranging from ecology and population dynamics to stochastic reaction events occurring between individual molecules in single cells. Generally, many biological processes unfold across multiple scales, with mutations being the best studied example of how stochasticity at the molecular scale can influence outcomes at the population scale. In many other contexts, however, an analogous link between micro- and macro-scale remains elusive, primarily due to the challenges involved in setting up and analyzing multi-scale models. Here, we employ such a model to investigate how stochasticity propagates from individual biochemical reaction events in the bacterial innate immune system to the ecology of bacteria and bacterial viruses. We show analytically how the dynamics of bacterial populations are shaped by the activities of immunity-conferring enzymes in single cells and how the ecological consequences imply optimal bacterial defense strategies against viruses. Our results suggest that bacterial populations in the presence of viruses can either optimize their initial growth rate or their population size, with the first strategy favoring simple immunity featuring a single restriction modification system and the second strategy favoring complex bacterial innate immunity featuring several simultaneously active restriction modification systems.
AU - Ruess, Jakob
AU - Pleska, Maros
AU - Guet, Calin C
AU - Tkačik, Gašper
ID - 6784
IS - 7
JF - PLoS Computational Biology
TI - Molecular noise of innate immunity shapes bacteria-phage ecologies
VL - 15
ER -
TY - JOUR
AB - Dipolar coupling plays a fundamental role in the interaction between electrically or magnetically polarized species such as magnetic atoms and dipolar molecules in a gas or dipolar excitons in the solid state. Unlike Coulomb or contactlike interactions found in many atomic, molecular, and condensed-matter systems, this interaction is long-ranged and highly anisotropic, as it changes from repulsive to attractive depending on the relative positions and orientation of the dipoles. Because of this unique property, many exotic, symmetry-breaking collective states have been recently predicted for cold dipolar gases, but only a few have been experimentally detected and only in dilute atomic dipolar Bose-Einstein condensates. Here, we report on the first observation of attractive dipolar coupling between excitonic dipoles using a new design of stacked semiconductor bilayers. We show that the presence of a dipolar exciton fluid in one bilayer modifies the spatial distribution and increases the binding energy of excitonic dipoles in a vertically remote layer. The binding energy changes are explained using a many-body polaron model describing the deformation of the exciton cloud due to its interaction with a remote dipolar exciton. The surprising nonmonotonic dependence on the cloud density indicates the important role of dipolar correlations, which is unique to dense, strongly interacting dipolar solid-state systems. Our concept provides a route for the realization of dipolar lattices with strong anisotropic interactions in semiconductor systems, which open the way for the observation of theoretically predicted new and exotic collective phases, as well as for engineering and sensing their collective excitations.
AU - Hubert, Colin
AU - Baruchi, Yifat
AU - Mazuz-Harpaz, Yotam
AU - Cohen, Kobi
AU - Biermann, Klaus
AU - Lemeshko, Mikhail
AU - West, Ken
AU - Pfeiffer, Loren
AU - Rapaport, Ronen
AU - Santos, Paulo
ID - 6786
IS - 2
JF - Physical Review X
TI - Attractive dipolar coupling between stacked exciton fluids
VL - 9
ER -
TY - JOUR
AB - We consider the Nelson model with ultraviolet cutoff, which describes the interaction between non-relativistic particles and a positive or zero mass quantized scalar field. We take the non-relativistic particles to obey Fermi statistics and discuss the time evolution in a mean-field limit of many fermions. In this case, the limit is known to be also a semiclassical limit. We prove convergence in terms of reduced density matrices of the many-body state to a tensor product of a Slater determinant with semiclassical structure and a coherent state, which evolve according to a fermionic version of the Schrödinger–Klein–Gordon equations.
AU - Leopold, Nikolai K
AU - Petrat, Sören P
ID - 6788
IS - 10
JF - Annales Henri Poincare
SN - 1424-0637
TI - Mean-field dynamics for the Nelson model with fermions
VL - 20
ER -
TY - JOUR
AB - The Regge symmetry is a set of remarkable relations between two tetrahedra whose edge lengths are related in a simple fashion. It was first discovered as a consequence of an asymptotic formula in mathematical physics. Here, we give a simple geometric proof of Regge symmetries in Euclidean, spherical, and hyperbolic geometry.
AU - Akopyan, Arseniy
AU - Izmestiev, Ivan
ID - 6793
IS - 5
JF - Bulletin of the London Mathematical Society
SN - 00246093
TI - The Regge symmetry, confocal conics, and the Schläfli formula
VL - 51
ER -
TY - JOUR
AB - The green‐beard effect is one proposed mechanism predicted to underpin the evolu‐tion of altruistic behavior. It relies on the recognition and the selective help of altruists to each other in order to promote and sustain altruistic behavior. However, this mechanism has often been dismissed as unlikely or uncommon, as it is assumed that both the signaling trait and altruistic trait need to be encoded by the same gene or through tightly linked genes. Here, we use models of indirect genetic effects (IGEs) to find the minimum correlation between the signaling and altruistic trait required for the evolution of the latter. We show that this correlation threshold depends on the strength of the interaction (influence of the green beard on the expression of the altruistic trait), as well as the costs and benefits of the altruistic behavior. We further show that this correlation does not necessarily have to be high and support our analytical results by simulations.
AU - Trubenova, Barbora
AU - Hager, Reinmar
ID - 6795
IS - 17
JF - Ecology and Evolution
TI - Green beards in the light of indirect genetic effects
VL - 9
ER -
TY - JOUR
AB - Indigoidine is a blue natural pigment, which can be efficiently synthetized in E. coli. In addition to its antioxidant and antimicrobial activities indigoidine due to its stability and deep blue color can find an application as an industrial, environmentally friendly dye. Moreover, similarly to its counterpart regular indigo dye, due to its molecular structure, indigoidine is an organic semiconductor. Fully conjugated aromatic moiety and intermolecular hydrogen bonding of indigoidine result in an unusually narrow bandgap for such a small molecule. This, in its turn, result is tight molecular packing in the solid state and opens a path for a wide range of application in organic and bio-electronics, such as electrochemical and field effect transistors, organic solar cells, light and bio-sensors etc.
AU - Yumusak, Cigdem
AU - Prochazkova, Anna Jancik
AU - Apaydin, Dogukan H
AU - Seelajaroen, Hathaichanok
AU - Sariciftci, Niyazi Serdar
AU - Weiter, Martin
AU - Krajcovic, Jozef
AU - Qin, Yong
AU - Zhang, Wei
AU - Zhan, Jixun
AU - Kovalenko, Alexander
ID - 6818
JF - Dyes and Pigments
SN - 0143-7208
TI - Indigoidine - Biosynthesized organic semiconductor
VL - 171
ER -
TY - JOUR
AB - Glyphosate (N-phosphonomethyl glycine) and its commercial herbicide formulations have been shown to exert toxicity via various mechanisms. It has been asserted that glyphosate substitutes for glycine in polypeptide chains leading to protein misfolding and toxicity. However, as no direct evidence exists for glycine to glyphosate substitution in proteins, including in mammalian organisms, we tested this claim by conducting a proteomics analysis of MDA-MB-231 human breast cancer cells grown in the presence of 100 mg/L glyphosate for 6 days. Protein extracts from three treated and three untreated cell cultures were analysed as one TMT-6plex labelled sample, to highlight a specific pattern (+/+/+/−/−/−) of reporter intensities for peptides bearing true glyphosate treatment induced-post translational modifications as well as allowing an investigation of the total proteome.
AU - Antoniou, Michael N.
AU - Nicolas, Armel
AU - Mesnage, Robin
AU - Biserni, Martina
AU - Rao, Francesco V.
AU - Martin, Cristina Vazquez
ID - 6819
JF - BMC Research Notes
TI - Glyphosate does not substitute for glycine in proteins of actively dividing mammalian cells
VL - 12
ER -