TY - JOUR
AB - The solid electrolyte interphase (SEI) in Li and Na ion batteries forms when highly reducing or oxidizing electrode materials come into contact with a liquid organic electrolyte. Its ability to form a mechanically robust, ion-conducting, and electron-insulating layer critically determines performance, cycle life, and safety. Li or Na alkyl carbonates (LiAC and NaAC, respectively) are lead SEI components in state-of-the-art carbonate based electrolytes, and our fundamental understanding of their charge transport and mechanical properties may hold the key to designing electrolytes forming an improved SEI. We synthesized a homologous series of LiACs and NaACs from methyl to octyl analogues and characterized them with respect to structure, ionic conductivity, and stiffness. The compounds assume layered structures except for the lithium methyl carbonate. Room-temperature conductivities were found to be ∼10–9 S cm–1 for lithium methyl carbonate, <10–12 S cm–1 for the other LiACs, and <10–12 S cm–1 for the NaACs with ion transport mostly attributed to grain boundaries. While LiACs show stiffnesses of ∼1 GPa, NaACs become significantly softer with increasing chain lengths. These findings will help to more precisely interpret the complex results from charge transport and mechanical characterization of real SEIs and can give a rationale for influencing the SEI’s mechanical properties via the electrolyte.
AU - Schafzahl, Lukas
AU - Ehmann, Heike
AU - Kriechbaum, Manfred
AU - Sattelkow, Jürgen
AU - Ganner, Thomas
AU - Plank, Harald
AU - Wilkening, Martin
AU - Freunberger, Stefan Alexander
ID - 7286
IS - 10
JF - Chemistry of Materials
SN - 0897-4756
TI - Long-chain Li and Na alkyl carbonates as solid electrolyte interphase components: Structure, ion transport, and mechanical properties
VL - 30
ER -
TY - JOUR
AB - Passivation layers on electrode materials are ubiquitous in nonaqueous battery chemistries and strongly govern performance and lifetime. They comprise breakdown products of the electrolyte including carbonate, alkyl carbonates, alkoxides, carboxylates, and polymers. Parasitic chemistry in metal–O2 batteries forms similar products and is tied to the deviation of the O2 balance from the ideal stoichiometry during formation/decomposition of alkaline peroxides or superoxides. Accurate and integral quantification of carbonaceous species and peroxides or superoxides in battery electrodes remains, however, elusive. We present a refined procedure to quantify them accurately and sensitively by pointing out and rectifying pitfalls of previous procedures. Carbonaceous compounds are differentiated into inorganic and organic ones. We combine mass and UV–vis spectrometry to quantify evolved O2 and complexed peroxide and CO2 evolved from carbonaceous compounds by acid treatment and Fenton’s reaction. The capabilities of the method are exemplified by means of Li–O2 and Na–O2 cathodes, graphite anodes, and LiNi0.8Co0.15Al0.05O2 cathodes.
AU - Schafzahl, Bettina
AU - Mourad, Eléonore
AU - Schafzahl, Lukas
AU - Petit, Yann K.
AU - Raju, Anjana R.
AU - Thotiyl, Musthafa Ottakam
AU - Wilkening, Martin
AU - Slugovc, Christian
AU - Freunberger, Stefan Alexander
ID - 7287
IS - 1
JF - ACS Energy Letters
SN - 2380-8195
TI - Quantifying total superoxide, peroxide, and carbonaceous compounds in metal–O2 batteries and the solid electrolyte interphase
VL - 3
ER -
TY - JOUR
AB - This paper is devoted to automatic competitive analysis of real-time scheduling algorithms for firm-deadline tasksets, where only completed tasks con- tribute some utility to the system. Given such a taskset T , the competitive ratio of an on-line scheduling algorithm A for T is the worst-case utility ratio of A over the utility achieved by a clairvoyant algorithm. We leverage the theory of quantitative graph games to address the competitive analysis and competitive synthesis problems. For the competitive analysis case, given any taskset T and any finite-memory on- line scheduling algorithm A , we show that the competitive ratio of A in T can be computed in polynomial time in the size of the state space of A . Our approach is flexible as it also provides ways to model meaningful constraints on the released task sequences that determine the competitive ratio. We provide an experimental study of many well-known on-line scheduling algorithms, which demonstrates the feasibility of our competitive analysis approach that effectively replaces human ingenuity (required Preliminary versions of this paper have appeared in Chatterjee et al. ( 2013 , 2014 ). B Andreas Pavlogiannis pavlogiannis@ist.ac.at Krishnendu Chatterjee krish.chat@ist.ac.at Alexander Kößler koe@ecs.tuwien.ac.at Ulrich Schmid s@ecs.tuwien.ac.at 1 IST Austria (Institute of Science and Technology Austria), Am Campus 1, 3400 Klosterneuburg, Austria 2 Embedded Computing Systems Group, Vienna University of Technology, Treitlstrasse 3, 1040 Vienna, Austria 123 Real-Time Syst for finding worst-case scenarios) by computing power. For the competitive synthesis case, we are just given a taskset T , and the goal is to automatically synthesize an opti- mal on-line scheduling algorithm A , i.e., one that guarantees the largest competitive ratio possible for T . We show how the competitive synthesis problem can be reduced to a two-player graph game with partial information, and establish that the compu- tational complexity of solving this game is Np -complete. The competitive synthesis problem is hence in Np in the size of the state space of the non-deterministic labeled transition system encoding the taskset. Overall, the proposed framework assists in the selection of suitable scheduling algorithms for a given taskset, which is in fact the most common situation in real-time systems design.
AU - Chatterjee, Krishnendu
AU - Pavlogiannis, Andreas
AU - Kößler, Alexander
AU - Schmid, Ulrich
ID - 738
IS - 1
JF - Real-Time Systems
TI - Automated competitive analysis of real time scheduling with graph games
VL - 54
ER -
TY - CONF
AB - Proofs of space (PoS) [Dziembowski et al., CRYPTO'15] are proof systems where a prover can convince a verifier that he "wastes" disk space. PoS were introduced as a more ecological and economical replacement for proofs of work which are currently used to secure blockchains like Bitcoin. In this work we investigate extensions of PoS which allow the prover to embed useful data into the dedicated space, which later can be recovered. Our first contribution is a security proof for the original PoS from CRYPTO'15 in the random oracle model (the original proof only applied to a restricted class of adversaries which can store a subset of the data an honest prover would store). When this PoS is instantiated with recent constructions of maximally depth robust graphs, our proof implies basically optimal security. As a second contribution we show three different extensions of this PoS where useful data can be embedded into the space required by the prover. Our security proof for the PoS extends (non-trivially) to these constructions. We discuss how some of these variants can be used as proofs of catalytic space (PoCS), a notion we put forward in this work, and which basically is a PoS where most of the space required by the prover can be used to backup useful data. Finally we discuss how one of the extensions is a candidate construction for a proof of replication (PoR), a proof system recently suggested in the Filecoin whitepaper.
AU - Pietrzak, Krzysztof Z
ID - 7407
SN - 1868-8969
T2 - 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
TI - Proofs of catalytic space
VL - 124
ER -
TY - JOUR
AB - We give a detailed and easily accessible proof of Gromov’s Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map (Formula presented.) there exists a point (Formula presented.) that is contained in the images of a positive fraction (Formula presented.) of the d-cells of X. More generally, the conclusion holds if (Formula presented.) is replaced by any d-dimensional piecewise-linear manifold M, with a constant (Formula presented.) that depends only on d and on the expansion properties of X, but not on M.
AU - Dotterrer, Dominic
AU - Kaufman, Tali
AU - Wagner, Uli
ID - 742
IS - 1
JF - Geometriae Dedicata
TI - On expansion and topological overlap
VL - 195
ER -
TY - JOUR
AB - The coupling between magnetic and electric subsystems in composites of ferromagnetic and ferroelectric phases is a product property that is facilitated by mechanical strain that arises due to magnetostriction and the piezoelectric effect in the constituent phases. Such multiferroic composites are of immense interests for studies on the physics of electromagnetic coupling and for use in a variety of applications. Here, we focus on magneto-electric (ME) coupling in nanocomposites. Particular emphasis is on core-shell particles and coaxial fibers, thin film heterostructures, and planar structures with a variety of mechanical connectivity. A brief review of models that predict strong ME effects in nanostructures is followed by synthesis and characterization. Core-shell particulate composites can be prepared by hydrothermal processes and chemical or deoxyribonucleic acid-assisted assembly. Electrospinning techniques have been utilized to prepare defect free core-shell nanofibers. Core-shell particles and fibers can be assembled into superstructures with the aid of magnetic and electric fields and characterized for possible use in advanced technologies. Chemical-vapor deposition techniques have been shown to be effective for the preparation of heterostructures of ferrites and ferroelectrics. Exotic planar multiferroic structures with potential for enhancing ME coupling strengths are also considered. Scanning probe microscopy techniques are ideal for probing the nature of direct- and converse-ME coupling in individual nanostructures. Magnetoelectric characterization of assemblies of nanocomposites can be done by ME voltage coefficient, magnetic field induced polarization, and magneto-dielectric effects. We conclude with a brief discussion on possible avenues for strengthening the product properties in the nanocomposites.
AU - Viehland, Dwight
AU - Li, Jie Fang
AU - Yang, Yaodong
AU - Costanzo, Tommaso
AU - Yourdkhani, Amin
AU - Caruntu, Gabriel
AU - Zhou, Peng
AU - Zhang, Tianjin
AU - Li, Tianqian
AU - Gupta, Arunava
AU - Popov, Maksym
AU - Srinivasan, Gopalan
ID - 7458
IS - 6
JF - Journal of Applied Physics
SN - 0021-8979
TI - Tutorial: Product properties in multiferroic nanocomposites
VL - 124
ER -
TY - GEN
AB - We prove that any convex body in the plane can be partitioned into m convex parts of equal areas and perimeters for any integer m≥2; this result was previously known for prime powers m=pk. We also give a higher-dimensional generalization.
AU - Akopyan, Arseniy
AU - Avvakumov, Sergey
AU - Karasev, Roman
ID - 75
TI - Convex fair partitions into arbitrary number of pieces
ER -
TY - JOUR
AB - Consider a fully-connected synchronous distributed system consisting of n nodes, where up to f nodes may be faulty and every node starts in an arbitrary initial state. In the synchronous C-counting problem, all nodes need to eventually agree on a counter that is increased by one modulo C in each round for given C>1. In the self-stabilising firing squad problem, the task is to eventually guarantee that all non-faulty nodes have simultaneous responses to external inputs: if a subset of the correct nodes receive an external “go” signal as input, then all correct nodes should agree on a round (in the not-too-distant future) in which to jointly output a “fire” signal. Moreover, no node should generate a “fire” signal without some correct node having previously received a “go” signal as input. We present a framework reducing both tasks to binary consensus at very small cost. For example, we obtain a deterministic algorithm for self-stabilising Byzantine firing squads with optimal resilience f<n/3, asymptotically optimal stabilisation and response time O(f), and message size O(log f). As our framework does not restrict the type of consensus routines used, we also obtain efficient randomised solutions.
AU - Lenzen, Christoph
AU - Rybicki, Joel
ID - 76
JF - Distributed Computing
TI - Near-optimal self-stabilising counting and firing squads
ER -
TY - JOUR
AB - Motor output varies along the rostro-caudal axis of the tetrapod spinal cord. At limb levels, ∼60 motor pools control the alternation of flexor and extensor muscles about each joint, whereas at thoracic levels as few as 10 motor pools supply muscle groups that support posture, inspiration, and expiration. Whether such differences in motor neuron identity and muscle number are associated with segmental distinctions in interneuron diversity has not been resolved. We show that select combinations of nineteen transcription factors that specify lumbar V1 inhibitory interneurons generate subpopulations enriched at limb and thoracic levels. Specification of limb and thoracic V1 interneurons involves the Hox gene Hoxc9 independently of motor neurons. Thus, early Hox patterning of the spinal cord determines the identity of V1 interneurons and motor neurons. These studies reveal a developmental program of V1 interneuron diversity, providing insight into the organization of inhibitory interneurons associated with differential motor output.
AU - Sweeney, Lora Beatrice Jaeger
AU - Bikoff, Jay B.
AU - Gabitto, Mariano I.
AU - Brenner-Morton, Susan
AU - Baek, Myungin
AU - Yang, Jerry H.
AU - Tabak, Esteban G.
AU - Dasen, Jeremy S.
AU - Kintner, Christopher R.
AU - Jessell, Thomas M.
ID - 7698
IS - 2
JF - Neuron
SN - 0896-6273
TI - Origin and segmental diversity of spinal inhibitory interneurons
VL - 97
ER -
TY - JOUR
AB - Holes confined in quantum dots have gained considerable interest in the past few years due to their potential as spin qubits. Here we demonstrate two-axis control of a spin 3/2 qubit in natural Ge. The qubit is formed in a hut wire double quantum dot device. The Pauli spin blockade principle allowed us to demonstrate electric dipole spin resonance by applying a radio frequency electric field to one of the electrodes defining the double quantum dot. Coherent hole spin oscillations with Rabi frequencies reaching 140 MHz are demonstrated and dephasing times of 130 ns are measured. The reported results emphasize the potential of Ge as a platform for fast and electrically tunable hole spin qubit devices.
AU - Watzinger, Hannes
AU - Kukucka, Josip
AU - Vukusic, Lada
AU - Gao, Fei
AU - Wang, Ting
AU - Schäffler, Friedrich
AU - Zhang, Jian
AU - Katsaros, Georgios
ID - 77
IS - 3902
JF - Nature Communications
TI - A germanium hole spin qubit
VL - 9
ER -
TY - JOUR
AB - Male pattern baldness (MPB) is a sex-limited, age-related, complex trait. We study MPB genetics in 205,327 European males from the UK Biobank. Here we show that MPB is strongly heritable and polygenic, with pedigree-heritability of 0.62 (SE = 0.03) estimated from close relatives, and SNP-heritability of 0.39 (SE = 0.01) from conventionally-unrelated males. We detect 624 near-independent genome-wide loci, contributing SNP-heritability of 0.25 (SE = 0.01), of which 26 X-chromosome loci explain 11.6%. Autosomal genetic variance is enriched for common variants and regions of lower linkage disequilibrium. We identify plausible genetic correlations between MPB and multiple sex-limited markers of earlier puberty, increased bone mineral density (rg = 0.15) and pancreatic β-cell function (rg = 0.12). Correlations with reproductive traits imply an effect on fitness, consistent with an estimated linear selection gradient of -0.018 per MPB standard deviation. Overall, we provide genetic insights into MPB: a phenotype of interest in its own right, with value as a model sex-limited, complex trait.
AU - Yap, Chloe X.
AU - Sidorenko, Julia
AU - Wu, Yang
AU - Kemper, Kathryn E.
AU - Yang, Jian
AU - Wray, Naomi R.
AU - Robinson, Matthew Richard
AU - Visscher, Peter M.
ID - 7712
JF - Nature Communications
SN - 2041-1723
TI - Dissection of genetic variation and evidence for pleiotropy in male pattern baldness
VL - 9
ER -
TY - JOUR
AB - There are mean differences in complex traits among global human populations. We hypothesize that part of the phenotypic differentiation is due to natural selection. To address this hypothesis, we assess the differentiation in allele frequencies of trait-associated SNPs among African, Eastern Asian, and European populations for ten complex traits using data of large sample size (up to ~405,000). We show that SNPs associated with height (P=2.46×10−5), waist-to-hip ratio (P=2.77×10−4), and schizophrenia (P=3.96×10−5) are significantly more differentiated among populations than matched “control” SNPs, suggesting that these trait-associated SNPs have undergone natural selection. We further find that SNPs associated with height (P=2.01×10−6) and schizophrenia (P=5.16×10−18) show significantly higher variance in linkage disequilibrium (LD) scores across populations than control SNPs. Our results support the hypothesis that natural selection has shaped the genetic differentiation of complex traits, such as height and schizophrenia, among worldwide populations.
AU - Guo, Jing
AU - Wu, Yang
AU - Zhu, Zhihong
AU - Zheng, Zhili
AU - Trzaskowski, Maciej
AU - Zeng, Jian
AU - Robinson, Matthew Richard
AU - Visscher, Peter M.
AU - Yang, Jian
ID - 7713
JF - Nature Communications
SN - 2041-1723
TI - Global genetic differentiation of complex traits shaped by natural selection in humans
VL - 9
ER -
TY - JOUR
AB - Health risk factors such as body mass index (BMI) and serum cholesterol are associated with many common diseases. It often remains unclear whether the risk factors are cause or consequence of disease, or whether the associations are the result of confounding. We develop and apply a method (called GSMR) that performs a multi-SNP Mendelian randomization analysis using summary-level data from genome-wide association studies to test the causal associations of BMI, waist-to-hip ratio, serum cholesterols, blood pressures, height, and years of schooling (EduYears) with common diseases (sample sizes of up to 405,072). We identify a number of causal associations including a protective effect of LDL-cholesterol against type-2 diabetes (T2D) that might explain the side effects of statins on T2D, a protective effect of EduYears against Alzheimer’s disease, and bidirectional associations with opposite effects (e.g., higher BMI increases the risk of T2D but the effect of T2D on BMI is negative).
AU - Zhu, Zhihong
AU - Zheng, Zhili
AU - Zhang, Futao
AU - Wu, Yang
AU - Trzaskowski, Maciej
AU - Maier, Robert
AU - Robinson, Matthew Richard
AU - McGrath, John J.
AU - Visscher, Peter M.
AU - Wray, Naomi R.
AU - Yang, Jian
ID - 7714
JF - Nature Communications
SN - 2041-1723
TI - Causal associations between risk factors and common diseases inferred from GWAS summary data
VL - 9
ER -
TY - JOUR
AB - Preference for mates with similar phenotypes; that is, assortative mating, is widely observed in humans1,2,3,4,5 and has evolutionary consequences6,7,8. Under Fisher's classical theory6, assortative mating is predicted to induce a signature in the genome at trait-associated loci that can be detected and quantified. Here, we develop and apply a method to quantify assortative mating on a specific trait by estimating the correlation (θ) between genetic predictors of the trait from single nucleotide polymorphisms on odd- versus even-numbered chromosomes. We show by theory and simulation that the effect of assortative mating can be quantified in the presence of population stratification. We applied this approach to 32 complex traits and diseases using single nucleotide polymorphism data from ~400,000 unrelated individuals of European ancestry. We found significant evidence of assortative mating for height (θ = 3.2%) and educational attainment (θ = 2.7%), both of which were consistent with theoretical predictions. Overall, our results imply that assortative mating involves multiple traits and affects the genomic architecture of loci that are associated with these traits, and that the consequence of mate choice can be detected from a random sample of genomes.
AU - Yengo, Loic
AU - Robinson, Matthew Richard
AU - Keller, Matthew C.
AU - Kemper, Kathryn E.
AU - Yang, Yuanhao
AU - Trzaskowski, Maciej
AU - Gratten, Jacob
AU - Turley, Patrick
AU - Cesarini, David
AU - Benjamin, Daniel J.
AU - Wray, Naomi R.
AU - Goddard, Michael E.
AU - Yang, Jian
AU - Visscher, Peter M.
ID - 7715
IS - 12
JF - Nature Human Behaviour
SN - 2397-3374
TI - Imprint of assortative mating on the human genome
VL - 2
ER -
TY - JOUR
AB - Genomic prediction has the potential to contribute to precision medicine. However, to date, the utility of such predictors is limited due to low accuracy for most traits. Here theory and simulation study are used to demonstrate that widespread pleiotropy among phenotypes can be utilised to improve genomic risk prediction. We show how a genetic predictor can be created as a weighted index that combines published genome-wide association study (GWAS) summary statistics across many different traits. We apply this framework to predict risk of schizophrenia and bipolar disorder in the Psychiatric Genomics consortium data, finding substantial heterogeneity in prediction accuracy increases across cohorts. For six additional phenotypes in the UK Biobank data, we find increases in prediction accuracy ranging from 0.7% for height to 47% for type 2 diabetes, when using a multi-trait predictor that combines published summary statistics from multiple traits, as compared to a predictor based only on one trait.
AU - Maier, Robert M.
AU - Zhu, Zhihong
AU - Lee, Sang Hong
AU - Trzaskowski, Maciej
AU - Ruderfer, Douglas M.
AU - Stahl, Eli A.
AU - Ripke, Stephan
AU - Wray, Naomi R.
AU - Yang, Jian
AU - Visscher, Peter M.
AU - Robinson, Matthew Richard
ID - 7716
JF - Nature Communications
SN - 2041-1723
TI - Improving genetic prediction by leveraging genetic correlations among human diseases and traits
VL - 9
ER -
TY - JOUR
AB - Background: DNA methylation levels change along with age, but few studies have examined the variation in the rate of such changes between individuals.
Methods: We performed a longitudinal analysis to quantify the variation in the rate of change of DNA methylation between individuals using whole blood DNA methylation array profiles collected at 2–4 time points (N = 2894) in 954 individuals (67–90 years).
Results: After stringent quality control, we identified 1507 DNA methylation CpG sites (rsCpGs) with statistically significant variation in the rate of change (random slope) of DNA methylation among individuals in a mixed linear model analysis. Genes in the vicinity of these rsCpGs were found to be enriched in Homeobox transcription factors and the Wnt signalling pathway, both of which are related to ageing processes. Furthermore, we investigated the SNP effect on the random slope. We found that 4 out of 1507 rsCpGs had one significant (P < 5 × 10−8/1507) SNP effect and 343 rsCpGs had at least one SNP effect (436 SNP-probe pairs) reaching genome-wide significance (P < 5 × 10−8). Ninety-five percent of the significant (P < 5 × 10−8) SNPs are on different chromosomes from their corresponding probes.
Conclusions: We identified CpG sites that have variability in the rate of change of DNA methylation between individuals, and our results suggest a genetic basis of this variation. Genes around these CpG sites have been reported to be involved in the ageing process.
AU - Zhang, Qian
AU - Marioni, Riccardo E
AU - Robinson, Matthew Richard
AU - Higham, Jon
AU - Sproul, Duncan
AU - Wray, Naomi R
AU - Deary, Ian J
AU - McRae, Allan F
AU - Visscher, Peter M
ID - 7717
IS - 1
JF - Genome Medicine
SN - 1756-994X
TI - Genotype effects contribute to variation in longitudinal methylome patterns in older people
VL - 10
ER -
TY - JOUR
AB - Flores Island, Indonesia, was inhabited by the small-bodied hominin species Homo floresiensis, which has an unknown evolutionary relationship to modern humans. This island is also home to an extant human pygmy population. Here we describe genome-scale single-nucleotide polymorphism data and whole-genome sequences from a contemporary human pygmy population living on Flores near the cave where H. floresiensis was found. The genomes of Flores pygmies reveal a complex history of admixture with Denisovans and Neanderthals but no evidence for gene flow with other archaic hominins. Modern individuals bear the signatures of recent positive selection encompassing the FADS (fatty acid desaturase) gene cluster, likely related to diet, and polygenic selection acting on standing variation that contributed to their short-stature phenotype. Thus, multiple independent instances of hominin insular dwarfism occurred on Flores.
AU - Tucci, Serena
AU - Vohr, Samuel H.
AU - McCoy, Rajiv C.
AU - Vernot, Benjamin
AU - Robinson, Matthew Richard
AU - Barbieri, Chiara
AU - Nelson, Brad J.
AU - Fu, Wenqing
AU - Purnomo, Gludhug A.
AU - Sudoyo, Herawati
AU - Eichler, Evan E.
AU - Barbujani, Guido
AU - Visscher, Peter M.
AU - Akey, Joshua M.
AU - Green, Richard E.
ID - 7718
IS - 6401
JF - Science
SN - 0036-8075
TI - Evolutionary history and adaptation of a human pygmy population of Flores Island, Indonesia
VL - 361
ER -
TY - JOUR
AB - The availability of genome-wide genetic data on hundreds of thousands of people has led to an equally rapid growth in methodologies available to analyse these data. While the motivation for undertaking genome-wide association studies (GWAS) is identification of genetic markers associated with complex traits, once generated these data can be used for many other analyses. GWAS have demonstrated that complex traits exhibit a highly polygenic genetic architecture, often with shared genetic risk factors across traits. New methods to analyse data from GWAS are increasingly being used to address a diverse set of questions about the aetiology of complex traits and diseases, including psychiatric disorders. Here, we give an overview of some of these methods and present examples of how they have contributed to our understanding of psychiatric disorders. We consider: (i) estimation of the extent of genetic influence on traits, (ii) uncovering of shared genetic control between traits, (iii) predictions of genetic risk for individuals, (iv) uncovering of causal relationships between traits, (v) identifying causal single-nucleotide polymorphisms and genes or (vi) the detection of genetic heterogeneity. This classification helps organise the large number of recently developed methods, although some could be placed in more than one category. While some methods require GWAS data on individual people, others simply use GWAS summary statistics data, allowing novel well-powered analyses to be conducted at a low computational burden.
AU - Maier, R. M.
AU - Visscher, P. M.
AU - Robinson, Matthew Richard
AU - Wray, N. R.
ID - 7721
IS - 7
JF - Psychological Medicine
SN - 0033-2917
TI - Embracing polygenicity: A review of methods and tools for psychiatric genetics research
VL - 48
ER -
TY - JOUR
AB - We develop a Bayesian mixed linear model that simultaneously estimates single-nucleotide polymorphism (SNP)-based heritability, polygenicity (proportion of SNPs with nonzero effects), and the relationship between SNP effect size and minor allele frequency for complex traits in conventionally unrelated individuals using genome-wide SNP data. We apply the method to 28 complex traits in the UK Biobank data (N = 126,752) and show that on average, 6% of SNPs have nonzero effects, which in total explain 22% of phenotypic variance. We detect significant (P < 0.05/28) signatures of natural selection in the genetic architecture of 23 traits, including reproductive, cardiovascular, and anthropometric traits, as well as educational attainment. The significant estimates of the relationship between effect size and minor allele frequency in complex traits are consistent with a model of negative (or purifying) selection, as confirmed by forward simulation. We conclude that negative selection acts pervasively on the genetic variants associated with human complex traits.
AU - Zeng, Jian
AU - de Vlaming, Ronald
AU - Wu, Yang
AU - Robinson, Matthew Richard
AU - Lloyd-Jones, Luke R.
AU - Yengo, Loic
AU - Yap, Chloe X.
AU - Xue, Angli
AU - Sidorenko, Julia
AU - McRae, Allan F.
AU - Powell, Joseph E.
AU - Montgomery, Grant W.
AU - Metspalu, Andres
AU - Esko, Tonu
AU - Gibson, Greg
AU - Wray, Naomi R.
AU - Visscher, Peter M.
AU - Yang, Jian
ID - 7722
IS - 5
JF - Nature Genetics
SN - 1061-4036
TI - Signatures of negative selection in the genetic architecture of human complex traits
VL - 50
ER -
TY - JOUR
AB - Genome-wide association studies (GWAS) have identified thousands of loci that are robustly associated with complex diseases. The use of linear mixed model (LMM) methodology for GWAS is becoming more prevalent due to its ability to control for population structure and cryptic relatedness and to increase power. The odds ratio (OR) is a common measure of the association of a disease with an exposure (e.g., a genetic variant) and is readably available from logistic regression. However, when the LMM is applied to all-or-none traits it provides estimates of genetic effects on the observed 0–1 scale, a different scale to that in logistic regression. This limits the comparability of results across studies, for example in a meta-analysis, and makes the interpretation of the magnitude of an effect from an LMM GWAS difficult. In this study, we derived transformations from the genetic effects estimated under the LMM to the OR that only rely on summary statistics. To test the proposed transformations, we used real genotypes from two large, publicly available data sets to simulate all-or-none phenotypes for a set of scenarios that differ in underlying model, disease prevalence, and heritability. Furthermore, we applied these transformations to GWAS summary statistics for type 2 diabetes generated from 108,042 individuals in the UK Biobank. In both simulation and real-data application, we observed very high concordance between the transformed OR from the LMM and either the simulated truth or estimates from logistic regression. The transformations derived and validated in this study improve the comparability of results from prospective and already performed LMM GWAS on complex diseases by providing a reliable transformation to a common comparative scale for the genetic effects.
AU - Lloyd-Jones, Luke R.
AU - Robinson, Matthew Richard
AU - Yang, Jian
AU - Visscher, Peter M.
ID - 7723
IS - 4
JF - Genetics
SN - 0016-6731
TI - Transformation of summary statistics from linear mixed model association on all-or-none traits to odds ratio
VL - 208
ER -
TY - JOUR
AB - Modern molecular genetic datasets, primarily collected to study the biology of human health and disease, can be used to directly measure the action of natural selection and reveal important features of contemporary human evolution. Here we leverage the UK Biobank data to test for the presence of linear and nonlinear natural selection in a contemporary population of the United Kingdom. We obtain phenotypic and genetic evidence consistent with the action of linear/directional selection. Phenotypic evidence suggests that stabilizing selection, which acts to reduce variance in the population without necessarily modifying the population mean, is widespread and relatively weak in comparison with estimates from other species.
AU - Sanjak, Jaleal S.
AU - Sidorenko, Julia
AU - Robinson, Matthew Richard
AU - Thornton, Kevin R.
AU - Visscher, Peter M.
ID - 7724
IS - 1
JF - Proceedings of the National Academy of Sciences
SN - 0027-8424
TI - Evidence of directional and stabilizing selection in contemporary humans
VL - 115
ER -
TY - JOUR
AB - Creating a selective gel that filters particles based on their interactions is a major goal of nanotechnology, with far-reaching implications from drug delivery to controlling assembly pathways. However, this is particularly difficult when the particles are larger than the gel’s characteristic mesh size because such particles cannot passively pass through the gel. Thus, filtering requires the interacting particles to transiently reorganize the gel’s internal structure. While significant advances, e.g., in DNA engineering, have enabled the design of nano-materials with programmable interactions, it is not clear what physical principles such a designer gel could exploit to achieve selective permeability. We present an equilibrium mechanism where crosslink binding dynamics are affected by interacting particles such that particle diffusion is enhanced. In addition to revealing specific design rules for manufacturing selective gels, our results have the potential to explain the origin of selective permeability in certain biological materials, including the nuclear pore complex.
AU - Goodrich, Carl Peter
AU - Brenner, Michael P.
AU - Ribbeck, Katharina
ID - 7754
JF - Nature Communications
SN - 2041-1723
TI - Enhanced diffusion by binding to the crosslinks of a polymer gel
VL - 9
ER -
TY - JOUR
AB - The goal of this article is to introduce the reader to the theory of intrinsic geometry of convex surfaces. We illustrate the power of the tools by proving a theorem on convex surfaces containing an arbitrarily long closed simple geodesic. Let us remind ourselves that a curve in a surface is called geodesic if every sufficiently short arc of the curve is length minimizing; if, in addition, it has no self-intersections, we call it simple geodesic. A tetrahedron with equal opposite edges is called isosceles. The axiomatic method of Alexandrov geometry allows us to work with the metrics of convex surfaces directly, without approximating it first by a smooth or polyhedral metric. Such approximations destroy the closed geodesics on the surface; therefore it is difficult (if at all possible) to apply approximations in the proof of our theorem. On the other hand, a proof in the smooth or polyhedral case usually admits a translation into Alexandrov’s language; such translation makes the result more general. In fact, our proof resembles a translation of the proof given by Protasov. Note that the main theorem implies in particular that a smooth convex surface does not have arbitrarily long simple closed geodesics. However we do not know a proof of this corollary that is essentially simpler than the one presented below.
AU - Akopyan, Arseniy
AU - Petrunin, Anton
ID - 106
IS - 3
JF - Mathematical Intelligencer
TI - Long geodesics on convex surfaces
VL - 40
ER -
TY - JOUR
AB - Owing to their wide tunability, multiple internal degrees of freedom, and low disorder, graphene heterostructures are emerging as a promising experimental platform for fractional quantum Hall (FQH) studies. Here, we report FQH thermal activation gap measurements in dual graphite-gated monolayer graphene devices fabricated in an edgeless Corbino geometry. In devices with substrate-induced sublattice splitting, we find a tunable crossover between single- and multicomponent FQH states in the zero energy Landau level. Activation gaps in the single-component regime show excellent agreement with numerical calculations using a single broadening parameter
Γ≈7.2K. In the first excited Landau level, in contrast, FQH gaps are strongly influenced by Landau level mixing, and we observe an unexpected valley-ordered state at integer filling ν=−4.
AU - Polshyn, Hryhoriy
AU - Zhou, H.
AU - Spanton, E. M.
AU - Taniguchi, T.
AU - Watanabe, K.
AU - Young, A. F.
ID - 10626
IS - 22
JF - Physical Review Letters
KW - general physics and astronomy
SN - 0031-9007
TI - Quantitative transport measurements of fractional quantum Hall energy gaps in edgeless graphene devices
VL - 121
ER -
TY - JOUR
AB - We present a scanning probe technique for measuring the dynamics of individual fluxoid transitions in multiply connected superconducting structures. In these measurements, a small magnetic particle attached to the tip of a silicon cantilever is scanned over a micron-size superconducting ring fabricated from a thin aluminum film. We find that near the superconducting transition temperature of the aluminum, the dissipation and frequency of the cantilever changes significantly at particular locations where the tip-induced magnetic flux penetrating the ring causes the two lowest-energy fluxoid states to become nearly degenerate. In this regime, we show that changes in the cantilever frequency and dissipation are well-described by a stochastic resonance (SR) process, wherein small oscillations of the cantilever in the presence of thermally activated phase slips (TAPS) in the ring give rise to a dynamical force that modifies the mechanical properties of the cantilever. Using the SR model, we calculate the average fluctuation rate of the TAPS as a function of temperature over a 32-dB range in frequency, and we compare it to the Langer-Ambegaokar-McCumber-Halperin theory for TAPS in one-dimensional superconducting structures.
AU - Polshyn, Hryhoriy
AU - Naibert, Tyler R.
AU - Budakian, Raffi
ID - 10627
IS - 18
JF - Physical Review B
SN - 2469-9950
TI - Imaging phase slip dynamics in micron-size superconducting rings
VL - 97
ER -
TY - JOUR
AB - In 1945, A.W. Goodman and R.E. Goodman proved the following conjecture by P. Erdős: Given a family of (round) disks of radii r1, … , rn in the plane, it is always possible to cover them by a disk of radius R= ∑ ri, provided they cannot be separated into two subfamilies by a straight line disjoint from the disks. In this note we show that essentially the same idea may work for different analogues and generalizations of their result. In particular, we prove the following: Given a family of positive homothetic copies of a fixed convex body K⊂ Rd with homothety coefficients τ1, … , τn> 0 , it is always possible to cover them by a translate of d+12(∑τi)K, provided they cannot be separated into two subfamilies by a hyperplane disjoint from the homothets.
AU - Akopyan, Arseniy
AU - Balitskiy, Alexey
AU - Grigorev, Mikhail
ID - 1064
IS - 4
JF - Discrete & Computational Geometry
SN - 01795376
TI - On the circle covering theorem by A.W. Goodman and R.E. Goodman
VL - 59
ER -
TY - JOUR
AB - We introduce the notion of “non-malleable codes” which relaxes the notion of error correction and error detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. In contrast to error correction and error detection, non-malleability can be achieved for very rich classes of modifications. We construct an efficient code that is non-malleable with respect to modifications that affect each bit of the codeword arbitrarily (i.e., leave it untouched, flip it, or set it to either 0 or 1), but independently of the value of the other bits of the codeword. Using the probabilistic method, we also show a very strong and general statement: there exists a non-malleable code for every “small enough” family F of functions via which codewords can be modified. Although this probabilistic method argument does not directly yield efficient constructions, it gives us efficient non-malleable codes in the random-oracle model for very general classes of tampering functions—e.g., functions where every bit in the tampered codeword can depend arbitrarily on any 99% of the bits in the original codeword. As an application of non-malleable codes, we show that they provide an elegant algorithmic solution to the task of protecting functionalities implemented in hardware (e.g., signature cards) against “tampering attacks.” In such attacks, the secret state of a physical system is tampered, in the hopes that future interaction with the modified system will reveal some secret information. This problem was previously studied in the work of Gennaro et al. in 2004 under the name “algorithmic tamper proof security” (ATP). We show that non-malleable codes can be used to achieve important improvements over the prior work. In particular, we show that any functionality can be made secure against a large class of tampering attacks, simply by encoding the secret state with a non-malleable code while it is stored in memory.
AU - Dziembowski, Stefan
AU - Pietrzak, Krzysztof Z
AU - Wichs, Daniel
ID - 107
IS - 4
JF - Journal of the ACM
TI - Non-malleable codes
VL - 65
ER -
TY - CONF
AB - Universal hashing found a lot of applications in computer science. In cryptography the most important fact about universal families is the so called Leftover Hash Lemma, proved by Impagliazzo, Levin and Luby. In the language of modern cryptography it states that almost universal families are good extractors. In this work we provide a somewhat surprising characterization in the opposite direction. Namely, every extractor with sufficiently good parameters yields a universal family on a noticeable fraction of its inputs. Our proof technique is based on tools from extremal graph theory applied to the \'collision graph\' induced by the extractor, and may be of independent interest. We discuss possible applications to the theory of randomness extractors and non-malleable codes.
AU - Obremski, Marciej
AU - Skorski, Maciej
ID - 108
TI - Inverted leftover hash lemma
VL - 2018
ER -
TY - CHAP
AB - We prove that every congruence distributive variety has directed Jónsson terms, and every congruence modular variety has directed Gumm terms. The directed terms we construct witness every case of absorption witnessed by the original Jónsson or Gumm terms. This result is equivalent to a pair of claims about absorption for admissible preorders in congruence distributive and congruence modular varieties, respectively. For finite algebras, these absorption theorems have already seen significant applications, but until now, it was not clear if the theorems hold for general algebras as well. Our method also yields a novel proof of a result by P. Lipparini about the existence of a chain of terms (which we call Pixley terms) in varieties that are at the same time congruence distributive and k-permutable for some k.
AU - Kazda, Alexandr
AU - Kozik, Marcin
AU - McKenzie, Ralph
AU - Moore, Matthew
ED - Czelakowski, J
ID - 10864
SN - 2211-2758
T2 - Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science
TI - Absorption and directed Jónsson terms
VL - 16
ER -
TY - JOUR
AB - Acquisition of evolutionary novelties is a fundamental process for adapting to the external environment and invading new niches and results in the diversification of life, which we can see in the world today. How such novel phenotypic traits are acquired in the course of evolution and are built up in developing embryos has been a central question in biology. Whole-genome duplication (WGD) is a process of genome doubling that supplies raw genetic materials and increases genome complexity. Recently, it has been gradually revealed that WGD and subsequent fate changes of duplicated genes can facilitate phenotypic evolution. Here, we review the current understanding of the relationship between WGD and the acquisition of evolutionary novelties. We show some examples of this link and discuss how WGD and subsequent duplicated genes can facilitate phenotypic evolution as well as when such genomic doubling can be advantageous for adaptation.
AU - Yuuta, Moriyama
AU - Koshiba-Takeuchi, Kazuko
ID - 10880
IS - 5
JF - Briefings in Functional Genomics
KW - Genetics
KW - Molecular Biology
KW - Biochemistry
KW - General Medicine
SN - 2041-2649
TI - Significance of whole-genome duplications on the emergence of evolutionary novelties
VL - 17
ER -
TY - JOUR
AB - Strigolactones (SLs) are a relatively recent addition to the list of plant hormones that control different aspects of plant development. SL signalling is perceived by an α/β hydrolase, DWARF 14 (D14). A close homolog of D14, KARRIKIN INSENSTIVE2 (KAI2), is involved in perception of an uncharacterized molecule called karrikin (KAR). Recent studies in Arabidopsis identified the SUPPRESSOR OF MAX2 1 (SMAX1) and SMAX1-LIKE 7 (SMXL7) to be potential SCF–MAX2 complex-mediated proteasome targets of KAI2 and D14, respectively. Genetic studies on SMXL7 and SMAX1 demonstrated distinct developmental roles for each, but very little is known about these repressors in terms of their sequence features. In this study, we performed an extensive comparative analysis of SMXLs and determined their phylogenetic and evolutionary history in the plant lineage. Our results show that SMXL family members can be sub-divided into four distinct phylogenetic clades/classes, with an ancient SMAX1. Further, we identified the clade-specific motifs that have evolved and that might act as determinants of SL-KAR signalling specificity. These specificities resulted from functional diversities among the clades. Our results suggest that a gradual co-evolution of SMXL members with their upstream receptors D14/KAI2 provided an increased specificity to both the SL perception and response in land plants.
AU - Moturu, Taraka Ramji
AU - Thula, Sravankumar
AU - Singh, Ravi Kumar
AU - Nodzyński, Tomasz
AU - Vařeková, Radka Svobodová
AU - Friml, Jiří
AU - Simon, Sibu
ID - 10881
IS - 9
JF - Journal of Experimental Botany
KW - Plant Science
KW - Physiology
SN - 0022-0957
TI - Molecular evolution and diversification of the SMXL gene family
VL - 69
ER -
TY - JOUR
AB - A graphical model encodes conditional independence relations via the Markov properties. For an undirected graph these conditional independence relations can be represented by a simple polytope known as the graph associahedron, which can be constructed as a Minkowski sum of standard simplices. We show that there is an analogous polytope for conditional independence relations coming from a regular Gaussian model, and it can be defined using multiinformation or relative entropy. For directed acyclic graphical models we give a construction of this polytope as a Minkowski sum of matroid polytopes. Finally, we apply this geometric insight to construct a new ordering-based search algorithm for causal inference via directed acyclic graphical models.
AU - Mohammadi, Fatemeh
AU - Uhler, Caroline
AU - Wang, Charles
AU - Yu, Josephine
ID - 1092
IS - 1
JF - SIAM Journal on Discrete Mathematics
TI - Generalized permutohedra from probabilistic graphical models
VL - 32
ER -
TY - CONF
AB - We report on a novel strategy to derive mean-field limits of quantum mechanical systems in which a large number of particles weakly couple to a second-quantized radiation field. The technique combines the method of counting and the coherent state approach to study the growth of the correlations among the particles and in the radiation field. As an instructional example, we derive the Schrödinger–Klein–Gordon system of equations from the Nelson model with ultraviolet cutoff and possibly massless scalar field. In particular, we prove the convergence of the reduced density matrices (of the nonrelativistic particles and the field bosons) associated with the exact time evolution to the projectors onto the solutions of the Schrödinger–Klein–Gordon equations in trace norm. Furthermore, we derive explicit bounds on the rate of convergence of the one-particle reduced density matrix of the nonrelativistic particles in Sobolev norm.
AU - Leopold, Nikolai K
AU - Pickl, Peter
ID - 11
TI - Mean-field limits of particles in interaction with quantised radiation fields
VL - 270
ER -
TY - JOUR
AB - We give a lower bound on the ground state energy of a system of two fermions of one species interacting with two fermions of another species via point interactions. We show that there is a critical mass ratio m2 ≈ 0.58 such that the system is stable, i.e., the energy is bounded from below, for m∈[m2,m2−1]. So far it was not known whether this 2 + 2 system exhibits a stable region at all or whether the formation of four-body bound states causes an unbounded spectrum for all mass ratios, similar to the Thomas effect. Our result gives further evidence for the stability of the more general N + M system.
AU - Moser, Thomas
AU - Seiringer, Robert
ID - 154
IS - 3
JF - Mathematical Physics Analysis and Geometry
SN - 13850172
TI - Stability of the 2+2 fermionic system with point interactions
VL - 21
ER -
TY - CONF
AB - There is currently significant interest in operating devices in the quantum regime, where their behaviour cannot be explained through classical mechanics. Quantum states, including entangled states, are fragile and easily disturbed by excessive thermal noise. Here we address the question of whether it is possible to create non-reciprocal devices that encourage the flow of thermal noise towards or away from a particular quantum device in a network. Our work makes use of the cascaded systems formalism to answer this question in the affirmative, showing how a three-port device can be used as an effective thermal transistor, and illustrates how this formalism maps onto an experimentally-realisable optomechanical system. Our results pave the way to more resilient quantum devices and to the use of thermal noise as a resource.
AU - Xuereb, André
AU - Aquilina, Matteo
AU - Barzanjeh, Shabir
ED - Andrews, D L
ED - Ostendorf, A
ED - Bain, A J
ED - Nunzi, J M
ID - 155
TI - Routing thermal noise through quantum networks
VL - 10672
ER -
TY - CONF
AB - Imprecision in timing can sometimes be beneficial: Metric interval temporal logic (MITL), disabling the expression of punctuality constraints, was shown to translate to timed automata, yielding an elementary decision procedure. We show how this principle extends to other forms of dense-time specification using regular expressions. By providing a clean, automaton-based formal framework for non-punctual languages, we are able to recover and extend several results in timed systems. Metric interval regular expressions (MIRE) are introduced, providing regular expressions with non-singular duration constraints. We obtain that MIRE are expressively complete relative to a class of one-clock timed automata, which can be determinized using additional clocks. Metric interval dynamic logic (MIDL) is then defined using MIRE as temporal modalities. We show that MIDL generalizes known extensions of MITL, while translating to timed automata at comparable cost.
AU - Ferrere, Thomas
ID - 156
TI - The compound interest in relaxing punctuality
VL - 10951
ER -
TY - JOUR
AB - Social dilemmas occur when incentives for individuals are misaligned with group interests 1-7 . According to the 'tragedy of the commons', these misalignments can lead to overexploitation and collapse of public resources. The resulting behaviours can be analysed with the tools of game theory 8 . The theory of direct reciprocity 9-15 suggests that repeated interactions can alleviate such dilemmas, but previous work has assumed that the public resource remains constant over time. Here we introduce the idea that the public resource is instead changeable and depends on the strategic choices of individuals. An intuitive scenario is that cooperation increases the public resource, whereas defection decreases it. Thus, cooperation allows the possibility of playing a more valuable game with higher payoffs, whereas defection leads to a less valuable game. We analyse this idea using the theory of stochastic games 16-19 and evolutionary game theory. We find that the dependence of the public resource on previous interactions can greatly enhance the propensity for cooperation. For these results, the interaction between reciprocity and payoff feedback is crucial: neither repeated interactions in a constant environment nor single interactions in a changing environment yield similar cooperation rates. Our framework shows which feedbacks between exploitation and environment - either naturally occurring or designed - help to overcome social dilemmas.
AU - Hilbe, Christian
AU - Šimsa, Štepán
AU - Chatterjee, Krishnendu
AU - Nowak, Martin
ID - 157
IS - 7713
JF - Nature
TI - Evolution of cooperation in stochastic games
VL - 559
ER -
TY - JOUR
AB - The angiosperm seed is composed of three genetically distinct tissues: the diploid embryo that originates from the fertilized egg cell, the triploid endosperm that is produced from the fertilized central cell, and the maternal sporophytic integuments that develop into the seed coat1. At the onset of embryo development in Arabidopsis thaliana, the zygote divides asymmetrically, producing a small apical embryonic cell and a larger basal cell that connects the embryo to the maternal tissue2. The coordinated and synchronous development of the embryo and the surrounding integuments, and the alignment of their growth axes, suggest communication between maternal tissues and the embryo. In contrast to animals, however, where a network of maternal factors that direct embryo patterning have been identified3,4, only a few maternal mutations have been described to affect embryo development in plants5–7. Early embryo patterning in Arabidopsis requires accumulation of the phytohormone auxin in the apical cell by directed transport from the suspensor8–10. However, the origin of this auxin has remained obscure. Here we investigate the source of auxin for early embryogenesis and provide evidence that the mother plant coordinates seed development by supplying auxin to the early embryo from the integuments of the ovule. We show that auxin response increases in ovules after fertilization, due to upregulated auxin biosynthesis in the integuments, and this maternally produced auxin is required for correct embryo development.
AU - Robert, Hélène
AU - Park, Chulmin
AU - Gutièrrez, Carla
AU - Wójcikowska, Barbara
AU - Pěnčík, Aleš
AU - Novák, Ondřej
AU - Chen, Junyi
AU - Grunewald, Wim
AU - Dresselhaus, Thomas
AU - Friml, Jirí
AU - Laux, Thomas
ID - 158
IS - 8
JF - Nature Plants
TI - Maternal auxin supply contributes to early embryo patterning in Arabidopsis
VL - 4
ER -
TY - JOUR
AB - L-type Ca2+ channels (LTCCs) play a crucial role in excitation-contraction coupling and release of hormones from secretory cells. They are targets of antihypertensive and antiarrhythmic drugs such as diltiazem. Here, we present a photoswitchable diltiazem, FHU-779, which can be used to reversibly block endogenous LTCCs by light. FHU-779 is as potent as diltiazem and can be used to place pancreatic β-cell function and cardiac activity under optical control.
AU - Fehrentz, Timm
AU - Huber, Florian
AU - Hartrampf, Nina
AU - Bruegmann, Tobias
AU - Frank, James
AU - Fine, Nicholas
AU - Malan, Daniela
AU - Danzl, Johann G
AU - Tikhonov, Denis
AU - Sumser, Maritn
AU - Sasse, Philipp
AU - Hodson, David
AU - Zhorov, Boris
AU - Klocker, Nikolaj
AU - Trauner, Dirk
ID - 159
IS - 8
JF - Nature Chemical Biology
TI - Optical control of L-type Ca2+ channels using a diltiazem photoswitch
VL - 14
ER -
TY - JOUR
AB - We report quantitative evidence of mixing-layer elastic instability in a viscoelastic fluid flow between two widely spaced obstacles hindering a channel flow at Re 1 and Wi 1. Two mixing layers with nonuniform shear velocity profiles are formed in the region between the obstacles. The mixing-layer instability arises in the vicinity of an inflection point on the shear velocity profile with a steep variation in the elastic stress. The instability results in an intermittent appearance of small vortices in the mixing layers and an amplification of spatiotemporal averaged vorticity in the elastic turbulence regime. The latter is characterized through scaling of friction factor with Wi and both pressure and velocity spectra. Furthermore, the observations reported provide improved understanding of the stability of the mixing layer in a viscoelastic fluid at large elasticity, i.e., Wi 1 and Re 1 and oppose the current view of suppression of vorticity solely by polymer additives.
AU - Varshney, Atul
AU - Steinberg, Victor
ID - 16
IS - 10
JF - Physical Review Fluids
TI - Mixing layer instability and vorticity amplification in a creeping viscoelastic flow
VL - 3
ER -
TY - CONF
AB - We present layered concurrent programs, a compact and expressive notation for specifying refinement proofs of concurrent programs. A layered concurrent program specifies a sequence of connected concurrent programs, from most concrete to most abstract, such that common parts of different programs are written exactly once. These programs are expressed in the ordinary syntax of imperative concurrent programs using gated atomic actions, sequencing, choice, and (recursive) procedure calls. Each concurrent program is automatically extracted from the layered program. We reduce refinement to the safety of a sequence of concurrent checker programs, one each to justify the connection between every two consecutive concurrent programs. These checker programs are also automatically extracted from the layered program. Layered concurrent programs have been implemented in the CIVL verifier which has been successfully used for the verification of several complex concurrent programs.
AU - Kragl, Bernhard
AU - Qadeer, Shaz
ID - 160
TI - Layered Concurrent Programs
VL - 10981
ER -
TY - JOUR
AB - Which properties of metabolic networks can be derived solely from stoichiometry? Predictive results have been obtained by flux balance analysis (FBA), by postulating that cells set metabolic fluxes to maximize growth rate. Here we consider a generalization of FBA to single-cell level using maximum entropy modeling, which we extend and test experimentally. Specifically, we define for Escherichia coli metabolism a flux distribution that yields the experimental growth rate: the model, containing FBA as a limit, provides a better match to measured fluxes and it makes a wide range of predictions: on flux variability, regulation, and correlations; on the relative importance of stoichiometry vs. optimization; on scaling relations for growth rate distributions. We validate the latter here with single-cell data at different sub-inhibitory antibiotic concentrations. The model quantifies growth optimization as emerging from the interplay of competitive dynamics in the population and regulation of metabolism at the level of single cells.
AU - De Martino, Daniele
AU - Mc, Andersson Anna
AU - Bergmiller, Tobias
AU - Guet, Calin C
AU - Tkacik, Gasper
ID - 161
IS - 1
JF - Nature Communications
TI - Statistical mechanics for metabolic networks during steady state growth
VL - 9
ER -
TY - JOUR
AB - For ultrafast fixation of biological samples to avoid artifacts, high-pressure freezing (HPF) followed by freeze substitution (FS) is preferred over chemical fixation at room temperature. After HPF, samples are maintained at low temperature during dehydration and fixation, while avoiding damaging recrystallization. This is a notoriously slow process. McDonald and Webb demonstrated, in 2011, that sample agitation during FS dramatically reduces the necessary time. Then, in 2015, we (H.G. and S.R.) introduced an agitation module into the cryochamber of an automated FS unit and demonstrated that the preparation of algae could be shortened from days to a couple of hours. We argued that variability in the processing, reproducibility, and safety issues are better addressed using automated FS units. For dissemination, we started low-cost manufacturing of agitation modules for two of the most widely used FS units, the Automatic Freeze Substitution Systems, AFS(1) and AFS2, from Leica Microsystems, using three dimensional (3D)-printing of the major components. To test them, several labs independently used the modules on a wide variety of specimens that had previously been processed by manual agitation, or without agitation. We demonstrate that automated processing with sample agitation saves time, increases flexibility with respect to sample requirements and protocols, and produces data of at least as good quality as other approaches.
AU - Reipert, Siegfried
AU - Goldammer, Helmuth
AU - Richardson, Christine
AU - Goldberg, Martin
AU - Hawkins, Timothy
AU - Hollergschwandtner, Elena
AU - Kaufmann, Walter
AU - Antreich, Sebastian
AU - Stierhof, York
ID - 163
IS - 12
JF - Journal of Histochemistry and Cytochemistry
TI - Agitation modules: Flexible means to accelerate automated freeze substitution
VL - 66
ER -
TY - JOUR
AB - Creeping flow of polymeric fluid without inertia exhibits elastic instabilities and elastic turbulence accompanied by drag enhancement due to elastic stress produced by flow-stretched polymers. However, in inertia-dominated flow at high Re and low fluid elasticity El, a reduction in turbulent frictional drag is caused by an intricate competition between inertial and elastic stresses. Here we explore the effect of inertia on the stability of viscoelastic flow in a broad range of control parameters El and (Re,Wi). We present the stability diagram of observed flow regimes in Wi-Re coordinates and find that the instabilities' onsets show an unexpectedly nonmonotonic dependence on El. Further, three distinct regions in the diagram are identified based on El. Strikingly, for high-elasticity fluids we discover a complete relaminarization of flow at Reynolds number in the range of 1 to 10, different from a well-known turbulent drag reduction. These counterintuitive effects may be explained by a finite polymer extensibility and a suppression of vorticity at high Wi. Our results call for further theoretical and numerical development to uncover the role of inertial effect on elastic turbulence in a viscoelastic flow.
AU - Varshney, Atul
AU - Steinberg, Victor
ID - 17
IS - 10
JF - Physical Review Fluids
TI - Drag enhancement and drag reduction in viscoelastic flow
VL - 3
ER -
TY - CONF
AB - We survey recent efforts to quantify failures of the Hasse principle in families of rationally connected varieties.
AU - Browning, Timothy D
ID - 174
IS - 2
TI - How often does the Hasse principle hold?
VL - 97
ER -
TY - JOUR
AB - For a general class of non-negative functions defined on integral ideals of number fields, upper bounds are established for their average over the values of certain principal ideals that are associated to irreducible binary forms with integer coefficients.
AU - Browning, Timothy D
AU - Sofos, Efthymios
ID - 176
IS - 3
JF - International Journal of Nuber Theory
TI - Averages of arithmetic functions over principal ideals
VL - 15
ER -
TY - JOUR
AB - An N-superconcentrator is a directed, acyclic graph with N input nodes and N output nodes such that every subset of the inputs and every subset of the outputs of same cardinality can be connected by node-disjoint paths. It is known that linear-size and bounded-degree superconcentrators exist. We prove the existence of such superconcentrators with asymptotic density 25.3 (where the density is the number of edges divided by N). The previously best known densities were 28 [12] and 27.4136 [17].
AU - Kolmogorov, Vladimir
AU - Rolinek, Michal
ID - 18
IS - 10
JF - Ars Combinatoria
SN - 0381-7032
TI - Superconcentrators of density 25.3
VL - 141
ER -
TY - JOUR
AB - In this paper we define and study the classical Uniform Electron Gas (UEG), a system of infinitely many electrons whose density is constant everywhere in space. The UEG is defined differently from Jellium, which has a positive constant background but no constraint on the density. We prove that the UEG arises in Density Functional Theory in the limit of a slowly varying density, minimizing the indirect Coulomb energy. We also construct the quantum UEG and compare it to the classical UEG at low density.
AU - Lewi, Mathieu
AU - Lieb, Élliott
AU - Seiringer, Robert
ID - 180
JF - Journal de l'Ecole Polytechnique - Mathematiques
TI - Statistical mechanics of the uniform electron gas
VL - 5
ER -
TY - JOUR
AB - We consider large random matrices X with centered, independent entries but possibly di erent variances. We compute the normalized trace of f(X)g(X∗) for f, g functions analytic on the spectrum of X. We use these results to compute the long time asymptotics for systems of coupled di erential equations with random coe cients. We show that when the coupling is critical, the norm squared of the solution decays like t−1/2.
AU - Erdös, László
AU - Krüger, Torben H
AU - Renfrew, David T
ID - 181
IS - 3
JF - SIAM Journal on Mathematical Analysis
TI - Power law decay for systems of randomly coupled differential equations
VL - 50
ER -
TY - CONF
AB - We describe a new algorithm for the parametric identification problem for signal temporal logic (STL), stated as follows. Given a densetime real-valued signal w and a parameterized temporal logic formula φ, compute the subset of the parameter space that renders the formula satisfied by the signal. Unlike previous solutions, which were based on search in the parameter space or quantifier elimination, our procedure works recursively on φ and computes the evolution over time of the set of valid parameter assignments. This procedure is similar to that of monitoring or computing the robustness of φ relative to w. Our implementation and experiments demonstrate that this approach can work well in practice.
AU - Bakhirkin, Alexey
AU - Ferrere, Thomas
AU - Maler, Oded
ID - 182
SN - 978-1-4503-5642-8
T2 - Proceedings of the 21st International Conference on Hybrid Systems
TI - Efficient parametric identification for STL
ER -
TY - CONF
AB - Fault-localization is considered to be a very tedious and time-consuming activity in the design of complex Cyber-Physical Systems (CPS). This laborious task essentially requires expert knowledge of the system in order to discover the cause of the fault. In this context, we propose a new procedure that AIDS designers in debugging Simulink/Stateflow hybrid system models, guided by Signal Temporal Logic (STL) specifications. The proposed method relies on three main ingredients: (1) a monitoring and a trace diagnostics procedure that checks whether a tested behavior satisfies or violates an STL specification, localizes time segments and interfaces variables contributing to the property violations; (2) a slicing procedure that maps these observable behavior segments to the internal states and transitions of the Simulink model; and (3) a spectrum-based fault-localization method that combines the previous analysis from multiple tests to identify the internal states and/or transitions that are the most likely to explain the fault. We demonstrate the applicability of our approach on two Simulink models from the automotive and the avionics domain.
AU - Bartocci, Ezio
AU - Ferrere, Thomas
AU - Manjunath, Niveditha
AU - Nickovic, Dejan
ID - 183
TI - Localizing faults in simulink/stateflow models with STL
ER -
TY - CONF
AB - We prove that for every d ≥ 2, deciding if a pure, d-dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k ≥ 0, deciding if a pure, d-dimensional, simplicial complex is k-decomposable is NP-hard. For d ≥ 3, both problems remain NP-hard when restricted to contractible pure d-dimensional complexes.
AU - Goaoc, Xavier
AU - Paták, Pavel
AU - Patakova, Zuzana
AU - Tancer, Martin
AU - Wagner, Uli
ID - 184
TI - Shellability is NP-complete
VL - 99
ER -
TY - CONF
AB - We resolve in the affirmative conjectures of A. Skopenkov and Repovš (1998), and M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the setting of approximating maps of graphs on 2-dimensional surfaces by embeddings. Our proof of this result is constructive and almost immediately implies an efficient algorithm for testing whether a given piecewise linear map of a graph in a surface is approximable by an embedding. More precisely, an instance of this problem consists of (i) a graph G whose vertices are partitioned into clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a region R of a 2-dimensional compact surface M given as the union of a set of pairwise disjoint discs corresponding to the clusters and a set of pairwise disjoint "pipes" corresponding to the bundles, connecting certain pairs of these discs. We are to decide whether G can be embedded inside M so that the vertices in every cluster are drawn in the corresponding disc, the edges in every bundle pass only through its corresponding pipe, and every edge crosses the boundary of each disc at most once.
AU - Fulek, Radoslav
AU - Kynčl, Jan
ID - 185
SN - 978-3-95977-066-8
TI - Hanani-Tutte for approximating maps of graphs
VL - 99
ER -
TY - CONF
AB - Given a locally finite X ⊆ ℝd and a radius r ≥ 0, the k-fold cover of X and r consists of all points in ℝd that have k or more points of X within distance r. We consider two filtrations - one in scale obtained by fixing k and increasing r, and the other in depth obtained by fixing r and decreasing k - and we compute the persistence diagrams of both. While standard methods suffice for the filtration in scale, we need novel geometric and topological concepts for the filtration in depth. In particular, we introduce a rhomboid tiling in ℝd+1 whose horizontal integer slices are the order-k Delaunay mosaics of X, and construct a zigzag module from Delaunay mosaics that is isomorphic to the persistence module of the multi-covers.
AU - Edelsbrunner, Herbert
AU - Osang, Georg F
ID - 187
TI - The multi-cover persistence of Euclidean balls
VL - 99
ER -
TY - CONF
AB - Smallest enclosing spheres of finite point sets are central to methods in topological data analysis. Focusing on Bregman divergences to measure dissimilarity, we prove bounds on the location of the center of a smallest enclosing sphere. These bounds depend on the range of radii for which Bregman balls are convex.
AU - Edelsbrunner, Herbert
AU - Virk, Ziga
AU - Wagner, Hubert
ID - 188
TI - Smallest enclosing spheres and Chernoff points in Bregman geometry
VL - 99
ER -
TY - JOUR
AB - Bacteria regulate genes to survive antibiotic stress, but regulation can be far from perfect. When regulation is not optimal, mutations that change gene expression can contribute to antibiotic resistance. It is not systematically understood to what extent natural gene regulation is or is not optimal for distinct antibiotics, and how changes in expression of specific genes quantitatively affect antibiotic resistance. Here we discover a simple quantitative relation between fitness, gene expression, and antibiotic potency, which rationalizes our observation that a multitude of genes and even innate antibiotic defense mechanisms have expression that is critically nonoptimal under antibiotic treatment. First, we developed a pooled-strain drug-diffusion assay and screened Escherichia coli overexpression and knockout libraries, finding that resistance to a range of 31 antibiotics could result from changing expression of a large and functionally diverse set of genes, in a primarily but not exclusively drug-specific manner. Second, by synthetically controlling the expression of single-drug and multidrug resistance genes, we observed that their fitness-expression functions changed dramatically under antibiotic treatment in accordance with a log-sensitivity relation. Thus, because many genes are nonoptimally expressed under antibiotic treatment, many regulatory mutations can contribute to resistance by altering expression and by activating latent defenses.
AU - Palmer, Adam
AU - Chait, Remy P
AU - Kishony, Roy
ID - 19
IS - 11
JF - Molecular Biology and Evolution
TI - Nonoptimal gene expression creates latent potential for antibiotic resistance
VL - 35
ER -
TY - JOUR
AB - The German cockroach, Blattella germanica, is a worldwide pest that infests buildings, including homes, restaurants, and hospitals, often living in unsanitary conditions. As a disease vector and producer of allergens, this species has major health and economic impacts on humans. Factors contributing to the success of the German cockroach include its resistance to a broad range of insecticides, immunity to many pathogens, and its ability, as an extreme generalist omnivore, to survive on most food sources. The recently published genome shows that B. germanica has an exceptionally high number of protein coding genes. In this study, we investigate the functions of the 93 significantly expanded gene families with the aim to better understand the success of B. germanica as a major pest despite such inhospitable conditions. We find major expansions in gene families with functions related to the detoxification of insecticides and allelochemicals, defense against pathogens, digestion, sensory perception, and gene regulation. These expansions might have allowed B. germanica to develop multiple resistance mechanisms to insecticides and pathogens, and enabled a broad, flexible diet, thus explaining its success in unsanitary conditions and under recurrent chemical control. The findings and resources presented here provide insights for better understanding molecular mechanisms that will facilitate more effective cockroach control.
AU - Harrison, Mark
AU - Arning, Nicolas
AU - Kremer, Lucas
AU - Ylla, Guillem
AU - Belles, Xavier
AU - Bornberg Bauer, Erich
AU - Huylmans, Ann K
AU - Jongepier, Evelien
AU - Puilachs, Maria
AU - Richards, Stephen
AU - Schal, Coby
ID - 190
JF - Journal of Experimental Zoology Part B: Molecular and Developmental Evolution
TI - Expansions of key protein families in the German cockroach highlight the molecular basis of its remarkable success as a global indoor pest
VL - 330
ER -
TY - JOUR
AB - The phytohormone auxin is the information carrier in a plethora of developmental and physiological processes in plants(1). It has been firmly established that canonical, nuclear auxin signalling acts through regulation of gene transcription(2). Here, we combined microfluidics, live imaging, genetic engineering and computational modelling to reanalyse the classical case of root growth inhibition(3) by auxin. We show that Arabidopsis roots react to addition and removal of auxin by extremely rapid adaptation of growth rate. This process requires intracellular auxin perception but not transcriptional reprogramming. The formation of the canonical TIR1/AFB-Aux/IAA co-receptor complex is required for the growth regulation, hinting to a novel, non-transcriptional branch of this signalling pathway. Our results challenge the current understanding of root growth regulation by auxin and suggest another, presumably non-transcriptional, signalling output of the canonical auxin pathway.
AU - Fendrych, Matyas
AU - Akhmanova, Maria
AU - Merrin, Jack
AU - Glanc, Matous
AU - Hagihara, Shinya
AU - Takahashi, Koji
AU - Uchida, Naoyuki
AU - Torii, Keiko U
AU - Friml, Jirí
ID - 192
IS - 7
JF - Nature Plants
TI - Rapid and reversible root growth inhibition by TIR1 auxin signalling
VL - 4
ER -
TY - CONF
AB - We show attacks on five data-independent memory-hard functions (iMHF) that were submitted to the password hashing competition (PHC). Informally, an MHF is a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly lower hardware and/or energy cost than evaluating a single instance on a standard single-core architecture. Data-independent means the memory access pattern of the function is independent of the input; this makes iMHFs harder to construct than data-dependent ones, but the latter can be attacked by various side-channel attacks. Following [Alwen-Blocki'16], we capture the evaluation of an iMHF as a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of this DAG is a measure for the hardware cost of evaluating the iMHF on an ASIC. Ideally, one would like the complexity of a DAG underlying an iMHF to be as close to quadratic in the number of nodes of the graph as possible. Instead, we show that (the DAGs underlying) the following iMHFs are far from this bound: Rig.v2, TwoCats and Gambit each having an exponent no more than 1.75. Moreover, we show that the complexity of the iMHF modes of the PHC finalists Pomelo and Lyra2 have exponents at most 1.83 and 1.67 respectively. To show this we investigate a combinatorial property of each underlying DAG (called its depth-robustness. By establishing upper bounds on this property we are then able to apply the general technique of [Alwen-Block'16] for analyzing the hardware costs of an iMHF.
AU - Alwen, Joel F
AU - Gazi, Peter
AU - Kamath Hosdurg, Chethan
AU - Klein, Karen
AU - Osang, Georg F
AU - Pietrzak, Krzysztof Z
AU - Reyzin, Lenoid
AU - Rolinek, Michal
AU - Rybar, Michal
ID - 193
T2 - Proceedings of the 2018 on Asia Conference on Computer and Communication Security
TI - On the memory hardness of data independent password hashing functions
ER -
TY - JOUR
AB - Ants are emerging model systems to study cellular signaling because distinct castes possess different physiologic phenotypes within the same colony. Here we studied the functionality of inotocin signaling, an insect ortholog of mammalian oxytocin (OT), which was recently discovered in ants. In Lasius ants, we determined that specialization within the colony, seasonal factors, and physiologic conditions down-regulated the expression of the OT-like signaling system. Given this natural variation, we interrogated its function using RNAi knockdowns. Next-generation RNA sequencing of OT-like precursor knock-down ants highlighted its role in the regulation of genes involved in metabolism. Knock-down ants exhibited higher walking activity and increased self-grooming in the brood chamber. We propose that OT-like signaling in ants is important for regulating metabolic processes and locomotion.
AU - Liutkeviciute, Zita
AU - Gil Mansilla, Esther
AU - Eder, Thomas
AU - Casillas Perez, Barbara E
AU - Giulia Di Giglio, Maria
AU - Muratspahić, Edin
AU - Grebien, Florian
AU - Rattei, Thomas
AU - Muttenthaler, Markus
AU - Cremer, Sylvia
AU - Gruber, Christian
ID - 194
IS - 12
JF - The FASEB Journal
SN - 08926638
TI - Oxytocin-like signaling in ants influences metabolic gene expression and locomotor activity
VL - 32
ER -
TY - JOUR
AB - We demonstrate that identical impurities immersed in a two-dimensional many-particle bath can be viewed as flux-tube-charged-particle composites described by fractional statistics. In particular, we find that the bath manifests itself as an external magnetic flux tube with respect to the impurities, and hence the time-reversal symmetry is broken for the effective Hamiltonian describing the impurities. The emerging flux tube acts as a statistical gauge field after a certain critical coupling. This critical coupling corresponds to the intersection point between the quasiparticle state and the phonon wing, where the angular momentum is transferred from the impurity to the bath. This amounts to a novel configuration with emerging anyons. The proposed setup paves the way to realizing anyons using electrons interacting with superfluid helium or lattice phonons, as well as using atomic impurities in ultracold gases.
AU - Yakaboylu, Enderalp
AU - Lemeshko, Mikhail
ID - 195
IS - 4
JF - Physical Review B - Condensed Matter and Materials Physics
TI - Anyonic statistics of quantum impurities in two dimensions
VL - 98
ER -
TY - THES
AB - Modern computer vision systems heavily rely on statistical machine learning models, which typically require large amounts of labeled data to be learned reliably. Moreover, very recently computer vision research widely adopted techniques for representation learning, which further increase the demand for labeled data. However, for many important practical problems there is relatively small amount of labeled data available, so it is problematic to leverage full potential of the representation learning methods. One way to overcome this obstacle is to invest substantial resources into producing large labelled datasets. Unfortunately, this can be prohibitively expensive in practice. In this thesis we focus on the alternative way of tackling the aforementioned issue. We concentrate on methods, which make use of weakly-labeled or even unlabeled data. Specifically, the first half of the thesis is dedicated to the semantic image segmentation task. We develop a technique, which achieves competitive segmentation performance and only requires annotations in a form of global image-level labels instead of dense segmentation masks. Subsequently, we present a new methodology, which further improves segmentation performance by leveraging tiny additional feedback from a human annotator. By using our methods practitioners can greatly reduce the amount of data annotation effort, which is required to learn modern image segmentation models. In the second half of the thesis we focus on methods for learning from unlabeled visual data. We study a family of autoregressive models for modeling structure of natural images and discuss potential applications of these models. Moreover, we conduct in-depth study of one of these applications, where we develop the state-of-the-art model for the probabilistic image colorization task.
AU - Kolesnikov, Alexander
ID - 197
TI - Weakly-Supervised Segmentation and Unsupervised Modeling of Natural Images
ER -
TY - JOUR
AB - Synthesis is the automated construction of a system from its specification. In real life, hardware and software systems are rarely constructed from scratch. Rather, a system is typically constructed from a library of components. Lustig and Vardi formalized this intuition and studied LTL synthesis from component libraries. In real life, designers seek optimal systems. In this paper we add optimality considerations to the setting. We distinguish between quality considerations (for example, size - the smaller a system is, the better it is), and pricing (for example, the payment to the company who manufactured the component). We study the problem of designing systems with minimal quality-cost and price. A key point is that while the quality cost is individual - the choices of a designer are independent of choices made by other designers that use the same library, pricing gives rise to a resource-allocation game - designers that use the same component share its price, with the share being proportional to the number of uses (a component can be used several times in a design). We study both closed and open settings, and in both we solve the problem of finding an optimal design. In a setting with multiple designers, we also study the game-theoretic problems of the induced resource-allocation game.
AU - Avni, Guy
AU - Kupferman, Orna
ID - 608
JF - Theoretical Computer Science
TI - Synthesis from component libraries with costs
VL - 712
ER -
TY - CHAP
AB - We prove that there is no strongly regular graph (SRG) with parameters (460; 153; 32; 60). The proof is based on a recent lower bound on the number of 4-cliques in a SRG and some applications of Euclidean representation of SRGs.
AU - Bondarenko, Andriy
AU - Mellit, Anton
AU - Prymak, Andriy
AU - Radchenko, Danylo
AU - Viazovska, Maryna
ID - 61
T2 - Contemporary Computational Mathematics
TI - There is no strongly regular graph with parameters (460; 153; 32; 60)
ER -
TY - JOUR
AB - Neuropeptides are ubiquitous modulators of behavior and physiology. They are packaged in specialized secretory organelles called dense core vesicles (DCVs) that are released upon neural stimulation. Unlike synaptic vesicles, which can be recycled and refilled close to release sites, DCVs must be replenished by de novo synthesis in the cell body. Here, we dissect DCV cell biology in vivo in a Caenorhabditis elegans sensory neuron whose tonic activity we can control using a natural stimulus. We express fluorescently tagged neuropeptides in the neuron and define parameters that describe their subcellular distribution. We measure these parameters at high and low neural activity in 187 mutants defective in proteins implicated in membrane traffic, neuroendocrine secretion, and neuronal or synaptic activity. Using unsupervised hierarchical clustering methods, we analyze these data and identify 62 groups of genes with similar mutant phenotypes. We explore the function of a subset of these groups. We recapitulate many previous findings, validating our paradigm. We uncover a large battery of proteins involved in recycling DCV membrane proteins, something hitherto poorly explored. We show that the unfolded protein response promotes DCV production, which may contribute to intertissue communication of stress. We also find evidence that different mechanisms of priming and exocytosis may operate at high and low neural activity. Our work provides a defined framework to study DCV biology at different neural activity levels.
AU - Laurent, Patrick
AU - Ch’ng, QueeLim
AU - Jospin, Maëlle
AU - Chen, Changchun
AU - Lorenzo, Ramiro
AU - de Bono, Mario
ID - 6109
IS - 29
JF - Proceedings of the National Academy of Sciences
SN - 0027-8424
TI - Genetic dissection of neuropeptide cell biology at high and low activity in a defined sensory neuron
VL - 115
ER -
TY - JOUR
AB - Neurons develop elaborate morphologies that provide a model for understanding cellular architecture. By studying C. elegans sensory dendrites, we previously identified genes that act to promote the extension of ciliated sensory dendrites during embryogenesis. Interestingly, the nonciliated dendrite of the oxygen-sensing neuron URX is not affected by these genes, suggesting it develops through a distinct mechanism. Here, we use a visual forward genetic screen to identify mutants that affect URX dendrite morphogenesis. We find that disruption of the MAP kinase MAPK-15 or the βH-spectrin SMA-1 causes a phenotype opposite to what we had seen before: dendrites extend normally during embryogenesis but begin to overgrow as the animals reach adulthood, ultimately extending up to 150% of their normal length. SMA-1 is broadly expressed and acts non-cell-autonomously, while MAPK-15 is expressed in many sensory neurons including URX and acts cell-autonomously. MAPK-15 acts at the time of overgrowth, localizes at the dendrite ending, and requires its kinase activity, suggesting it acts locally in time and space to constrain dendrite growth. Finally, we find that the oxygen-sensing guanylate cyclase GCY-35, which normally localizes at the dendrite ending, is localized throughout the overgrown region, and that overgrowth can be suppressed by overexpressing GCY-35 or by genetically mimicking elevated cGMP signaling. These results suggest that overgrowth may correspond to expansion of a sensory compartment at the dendrite ending, reminiscent of the remodeling of sensory cilia or dendritic spines. Thus, in contrast to established pathways that promote dendrite growth during early development, our results reveal a distinct mechanism that constrains dendrite growth throughout the life of the animal, possibly by controlling the size of a sensory compartment at the dendrite ending.
AU - McLachlan, Ian G.
AU - Beets, Isabel
AU - de Bono, Mario
AU - Heiman, Maxwell G.
ID - 6111
IS - 6
JF - PLOS Genetics
SN - 1553-7404
TI - A neuronal MAP kinase constrains growth of a Caenorhabditis elegans sensory dendrite throughout the life of the organism
VL - 14
ER -
TY - JOUR
AB - Social insects protect their colonies from infectious disease through collective defences that result in social immunity. In ants, workers first try to prevent infection of colony members. Here, we show that if this fails and a pathogen establishes an infection, ants employ an efficient multicomponent behaviour − "destructive disinfection" − to prevent further spread of disease through the colony. Ants specifically target infected pupae during the pathogen's non-contagious incubation period, relying on chemical 'sickness cues' emitted by pupae. They then remove the pupal cocoon, perforate its cuticle and administer antimicrobial poison, which enters the body and prevents pathogen replication from the inside out. Like the immune system of a body that specifically targets and eliminates infected cells, this social immunity measure sacrifices infected brood to stop the pathogen completing its lifecycle, thus protecting the rest of the colony. Hence, the same principles of disease defence apply at different levels of biological organisation.
AU - Pull, Christopher
AU - Ugelvig, Line V
AU - Wiesenhofer, Florian
AU - Grasse, Anna V
AU - Tragust, Simon
AU - Schmitt, Thomas
AU - Brown, Mark
AU - Cremer, Sylvia
ID - 616
JF - eLife
TI - Destructive disinfection of infected brood prevents systemic disease spread in ant colonies
VL - 7
ER -
TY - CONF
AB - In this paper, we propose an algorithm to build discrete spherical shell having integer center and real-valued inner and outer radii on the face-centered cubic (FCC) grid. We address the problem by mapping it to a 2D scenario and building the shell layer by layer on hexagonal grids with additive manufacturing in mind. The layered hexagonal grids get shifted according to need as we move from one layer to another and forms the FCC grid in 3D. However, we restrict our computation strictly to 2D in order to utilize symmetry and simplicity.
AU - Koshti, Girish
AU - Biswas, Ranita
AU - Largeteau-Skapin, Gaëlle
AU - Zrour, Rita
AU - Andres, Eric
AU - Bhowmick, Partha
ID - 6164
SN - 0302-9743
T2 - 19th International Workshop
TI - Sphere construction on the FCC grid interpreted as layered hexagonal grids in 3D
VL - 11255
ER -
TY - GEN
AB - We study the unique solution $m$ of the Dyson equation \[ -m(z)^{-1} = z - a
+ S[m(z)] \] on a von Neumann algebra $\mathcal{A}$ with the constraint
$\mathrm{Im}\,m\geq 0$. Here, $z$ lies in the complex upper half-plane, $a$ is
a self-adjoint element of $\mathcal{A}$ and $S$ is a positivity-preserving
linear operator on $\mathcal{A}$. We show that $m$ is the Stieltjes transform
of a compactly supported $\mathcal{A}$-valued measure on $\mathbb{R}$. Under
suitable assumptions, we establish that this measure has a uniformly
$1/3$-H\"{o}lder continuous density with respect to the Lebesgue measure, which
is supported on finitely many intervals, called bands. In fact, the density is
analytic inside the bands with a square-root growth at the edges and internal
cubic root cusps whenever the gap between two bands vanishes. The shape of
these singularities is universal and no other singularity may occur. We give a
precise asymptotic description of $m$ near the singular points. These
asymptotics generalize the analysis at the regular edges given in the companion
paper on the Tracy-Widom universality for the edge eigenvalue statistics for
correlated random matrices [arXiv:1804.07744] and they play a key role in the
proof of the Pearcey universality at the cusp for Wigner-type matrices
[arXiv:1809.03971,arXiv:1811.04055]. We also extend the finite dimensional band
mass formula from [arXiv:1804.07744] to the von Neumann algebra setting by
showing that the spectral mass of the bands is topologically rigid under
deformations and we conclude that these masses are quantized in some important
cases.
AU - Alt, Johannes
AU - Erdös, László
AU - Krüger, Torben H
ID - 6183
T2 - arXiv
TI - The Dyson equation with linear self-energy: Spectral bands, edges and cusps
ER -
TY - CONF
AB - In the context of robotic manipulation and grasping, the shift from a view that is static (force closure of a single posture) and contact-deprived (only contact for force closure is allowed, everything else is obstacle) towards a view that is dynamic and contact-rich (soft manipulation) has led to an increased interest in soft hands. These hands can easily exploit environmental constraints and object surfaces without risk, and safely interact with humans, but present also some challenges. Designing them is difficult, as well as predicting, modelling, and “programming” their interactions with the objects and the environment. This paper tackles the problem of simulating them in a fast and effective way, leveraging on novel and existing simulation technologies. We present a triple-layered simulation framework where dynamic properties such as stiffness are determined from slow but accurate FEM simulation data once, and then condensed into a lumped parameter model that can be used to fast simulate soft fingers and soft hands. We apply our approach to the simulation of soft pneumatic fingers.
AU - Pozzi, Maria
AU - Miguel Villalba, Eder
AU - Deimel, Raphael
AU - Malvezzi, Monica
AU - Bickel, Bernd
AU - Brock, Oliver
AU - Prattichizzo, Domenico
ID - 6195
SN - 9781538630815
TI - Efficient FEM-based simulation of soft robots modeled as kinematic chains
ER -
TY - JOUR
AB - Imaging is a dominant strategy for data collection in neuroscience, yielding stacks of images that often scale to gigabytes of data for a single experiment. Machine learning algorithms from computer vision can serve as a pair of virtual eyes that tirelessly processes these images, automatically detecting and identifying microstructures. Unlike learning methods, our Flexible Learning-free Reconstruction of Imaged Neural volumes (FLoRIN) pipeline exploits structure-specific contextual clues and requires no training. This approach generalizes across different modalities, including serially-sectioned scanning electron microscopy (sSEM) of genetically labeled and contrast enhanced processes, spectral confocal reflectance (SCoRe) microscopy, and high-energy synchrotron X-ray microtomography (μCT) of large tissue volumes. We deploy the FLoRIN pipeline on newly published and novel mouse datasets, demonstrating the high biological fidelity of the pipeline’s reconstructions. FLoRIN reconstructions are of sufficient quality for preliminary biological study, for example examining the distribution and morphology of cells or extracting single axons from functional data. Compared to existing supervised learning methods, FLoRIN is one to two orders of magnitude faster and produces high-quality reconstructions that are tolerant to noise and artifacts, as is shown qualitatively and quantitatively.
AU - Shabazi, Ali
AU - Kinnison, Jeffery
AU - Vescovi, Rafael
AU - Du, Ming
AU - Hill, Robert
AU - Jösch, Maximilian A
AU - Takeno, Marc
AU - Zeng, Hongkui
AU - Da Costa, Nuno
AU - Grutzendler, Jaime
AU - Kasthuri, Narayanan
AU - Scheirer, Walter
ID - 62
IS - 1
JF - Scientific Reports
TI - Flexible learning-free segmentation and reconstruction of neural volumes
VL - 8
ER -
TY - JOUR
AB - Clathrin-mediated endocytosis requires the coordinated assembly of various endocytic proteins and lipids at the plasma membrane. Accumulating evidence demonstrates a crucial role for phosphatidylinositol-4,5-bisphosphate (PtdIns(4,5)P2) in endocytosis, but specific roles for PtdIns(4)P other than as the biosynthetic precursor of PtdIns(4,5)P2 have not been clarified. In this study we investigated the role of PtdIns(4)P or PtdIns(4,5)P2 in receptor-mediated endocytosis through the construction of temperature-sensitive (ts) mutants for the PI 4-kinases Stt4p and Pik1p and the PtdIns(4) 5-kinase Mss4p. Quantitative analyses of endocytosis revealed that both the stt4(ts)pik1(ts) and mss4(ts) mutants have a severe defect in endocytic internalization. Live-cell imaging of endocytic protein dynamics in stt4(ts)pik1(ts) and mss4(ts) mutants revealed that PtdIns(4)P is required for the recruitment of the alpha-factor receptor Ste2p to clathrin-coated pits whereas PtdIns(4,5)P2 is required for membrane internalization. We also found that the localization to endocytic sites of the ENTH/ANTH domain-bearing clathrin adaptors, Ent1p/Ent2p and Yap1801p/Yap1802p, is significantly impaired in the stt4(ts)pik1(ts) mutant, but not in the mss4(ts) mutant. These results suggest distinct roles in successive steps for PtdIns(4)P and PtdIns(4,5)P2 during receptor-mediated endocytosis.
AU - Yamamoto, Wataru
AU - Wada, Suguru
AU - Nagano, Makoto
AU - Aoshima, Kaito
AU - Siekhaus, Daria E
AU - Toshima, Junko
AU - Toshima, Jiro
ID - 620
IS - 1
JF - Journal of Cell Science
TI - Distinct roles for plasma membrane PtdIns 4 P and PtdIns 4 5 P2 during yeast receptor mediated endocytosis
VL - 131
ER -
TY - JOUR
AB - African cichlids display a remarkable assortment of jaw morphologies, pigmentation patterns, and mating behaviors. In addition to this previously documented diversity, recent studies have documented a rich diversity of sex chromosomes within these fishes. Here we review the known sex-determination network within vertebrates, and the extraordinary number of sex chromosomes systems segregating in African cichlids. We also propose a model for understanding the unusual number of sex chromosome systems within this clade.
AU - Gammerdinger, William J
AU - Kocher, Thomas
ID - 63
IS - 10
JF - Genes
TI - Unusual diversity of sex chromosomes in African cichlid fishes
VL - 9
ER -
TY - JOUR
AB - We introduce a diagrammatic Monte Carlo approach to angular momentum properties of quantum many-particle systems possessing a macroscopic number of degrees of freedom. The treatment is based on a diagrammatic expansion that merges the usual Feynman diagrams with the angular momentum diagrams known from atomic and nuclear structure theory, thereby incorporating the non-Abelian algebra inherent to quantum rotations. Our approach is applicable at arbitrary coupling, is free of systematic errors and of finite-size effects, and naturally provides access to the impurity Green function. We exemplify the technique by obtaining an all-coupling solution of the angulon model; however, the method is quite general and can be applied to a broad variety of systems in which particles exchange quantum angular momentum with their many-body environment.
AU - Bighin, Giacomo
AU - Tscherbul, Timur
AU - Lemeshko, Mikhail
ID - 6339
IS - 16
JF - Physical Review Letters
TI - Diagrammatic Monte Carlo approach to angular momentum in quantum many-particle systems
VL - 121
ER -
TY - JOUR
AB - Blood platelets are critical for hemostasis and thrombosis, but also play diverse roles during immune responses. We have recently reported that platelets migrate at sites of infection in vitro and in vivo. Importantly, platelets use their ability to migrate to collect and bundle fibrin (ogen)-bound bacteria accomplishing efficient intravascular bacterial trapping. Here, we describe a method that allows analyzing platelet migration in vitro, focusing on their ability to collect bacteria and trap bacteria under flow.
AU - Fan, Shuxia
AU - Lorenz, Michael
AU - Massberg, Steffen
AU - Gärtner, Florian R
ID - 6354
IS - 18
JF - Bio-Protocol
KW - Platelets
KW - Cell migration
KW - Bacteria
KW - Shear flow
KW - Fibrinogen
KW - E. coli
SN - 2331-8325
TI - Platelet migration and bacterial trapping assay under flow
VL - 8
ER -
TY - JOUR
AB - We prove that any cyclic quadrilateral can be inscribed in any closed convex C1-curve. The smoothness condition is not required if the quadrilateral is a rectangle.
AU - Akopyan, Arseniy
AU - Avvakumov, Sergey
ID - 6355
JF - Forum of Mathematics, Sigma
SN - 2050-5094
TI - Any cyclic quadrilateral can be inscribed in any closed convex smooth curve
VL - 6
ER -
TY - JOUR
AB - An optical network of superconducting quantum bits (qubits) is an appealing platform for quantum communication and distributed quantum computing, but developing a quantum-compatible link between the microwave and optical domains remains an outstanding challenge. Operating at T < 100 mK temperatures, as required for quantum electrical circuits, we demonstrate a mechanically mediated microwave–optical converter with 47% conversion efficiency, and use a classical feed-forward protocol to reduce added noise to 38 photons. The feed-forward protocol harnesses our discovery that noise emitted from the two converter output ports is strongly correlated because both outputs record thermal motion of the same mechanical mode. We also discuss a quantum feed-forward protocol that, given high system efficiencies, would allow quantum information to be transferred even when thermal phonons enter the mechanical element faster than the electro-optic conversion rate.
AU - Higginbotham, Andrew P
AU - Burns, P. S.
AU - Urmey, M. D.
AU - Peterson, R. W.
AU - Kampel, N. S.
AU - Brubaker, B. M.
AU - Smith, G.
AU - Lehnert, K. W.
AU - Regal, C. A.
ID - 6368
IS - 10
JF - Nature Physics
SN - 1745-2473
TI - Harnessing electro-optic correlations in an efficient mechanical converter
VL - 14
ER -
TY - JOUR
AB - We construct a metamaterial from radio-frequency harmonic oscillators, and find two topologically distinct phases resulting from dissipation engineered into the system. These phases are distinguished by a quantized value of bulk energy transport. The impulse response of our circuit is measured and used to reconstruct the band structure and winding number of circuit eigenfunctions around a dark mode. Our results demonstrate that dissipative topological transport can occur in a wider class of physical systems than considered before.
AU - Rosenthal, Eric I.
AU - Ehrlich, Nicole K.
AU - Rudner, Mark S.
AU - Higginbotham, Andrew P
AU - Lehnert, K. W.
ID - 6369
IS - 22
JF - Physical Review B
SN - 2469-9950
TI - Topological phase transition measured in a dissipative metamaterial
VL - 97
ER -
TY - JOUR
AB - Tropical geometry, an established field in pure mathematics, is a place where string theory, mirror symmetry, computational algebra, auction theory, and so forth meet and influence one another. In this paper, we report on our discovery of a tropical model with self-organized criticality (SOC) behavior. Our model is continuous, in contrast to all known models of SOC, and is a certain scaling limit of the sandpile model, the first and archetypical model of SOC. We describe how our model is related to pattern formation and proportional growth phenomena and discuss the dichotomy between continuous and discrete models in several contexts. Our aim in this context is to present an idealized tropical toy model (cf. Turing reaction-diffusion model), requiring further investigation.
AU - Kalinin, Nikita
AU - Guzmán Sáenz, Aldo
AU - Prieto, Y
AU - Shkolnikov, Mikhail
AU - Kalinina, V
AU - Lupercio, Ernesto
ID - 64
IS - 35
JF - PNAS: Proceedings of the National Academy of Sciences of the United States of America
SN - 00278424
TI - Self-organized criticality and pattern emergence through the lens of tropical geometry
VL - 115
ER -
TY - GEN
AU - Petritsch, Barbara
ID - 6459
KW - Open Access
KW - Publication Analysis
TI - Open Access at IST Austria 2009-2017
ER -
TY - JOUR
AB - T cells are actively scanning pMHC-presenting cells in lymphoid organs and nonlymphoid tissues (NLTs) with divergent topologies and confinement. How the T cell actomyosin cytoskeleton facilitates this task in distinct environments is incompletely understood. Here, we show that lack of Myosin IXb (Myo9b), a negative regulator of the small GTPase Rho, led to increased Rho-GTP levels and cell surface stiffness in primary T cells. Nonetheless, intravital imaging revealed robust motility of Myo9b−/− CD8+ T cells in lymphoid tissue and similar expansion and differentiation during immune responses. In contrast, accumulation of Myo9b−/− CD8+ T cells in NLTs was strongly impaired. Specifically, Myo9b was required for T cell crossing of basement membranes, such as those which are present between dermis and epidermis. As consequence, Myo9b−/− CD8+ T cells showed impaired control of skin infections. In sum, we show that Myo9b is critical for the CD8+ T cell adaptation from lymphoid to NLT surveillance and the establishment of protective tissue–resident T cell populations.
AU - Moalli, Federica
AU - Ficht, Xenia
AU - Germann, Philipp
AU - Vladymyrov, Mykhailo
AU - Stolp, Bettina
AU - de Vries, Ingrid
AU - Lyck, Ruth
AU - Balmer, Jasmin
AU - Fiocchi, Amleto
AU - Kreutzfeldt, Mario
AU - Merkler, Doron
AU - Iannacone, Matteo
AU - Ariga, Akitaka
AU - Stoffel, Michael H.
AU - Sharpe, James
AU - Bähler, Martin
AU - Sixt, Michael K
AU - Diz-Muñoz, Alba
AU - Stein, Jens V.
ID - 6497
IS - 7
JF - The Journal of Experimental Medicine
SN - 0022-1007
TI - The Rho regulator Myosin IXb enables nonlymphoid tissue seeding of protective CD8+T cells
VL - 2015
ER -
TY - JOUR
AB - Expansion microscopy is a recently introduced imaging technique that achieves super‐resolution through physically expanding the specimen by ~4×, after embedding into a swellable gel. The resolution attained is, correspondingly, approximately fourfold better than the diffraction limit, or ~70 nm. This is a major improvement over conventional microscopy, but still lags behind modern STED or STORM setups, whose resolution can reach 20–30 nm. We addressed this issue here by introducing an improved gel recipe that enables an expansion factor of ~10× in each dimension, which corresponds to an expansion of the sample volume by more than 1,000‐fold. Our protocol, which we termed X10 microscopy, achieves a resolution of 25–30 nm on conventional epifluorescence microscopes. X10 provides multi‐color images similar or even superior to those produced with more challenging methods, such as STED, STORM, and iterative expansion microscopy (iExM). X10 is therefore the cheapest and easiest option for high‐quality super‐resolution imaging currently available. X10 should be usable in any laboratory, irrespective of the machinery owned or of the technical knowledge.
AU - Truckenbrodt, Sven M
AU - Maidorn, Manuel
AU - Crzan, Dagmar
AU - Wildhagen, Hanna
AU - Kabatas, Selda
AU - Rizzoli, Silvio O
ID - 6499
IS - 9
JF - EMBO reports
SN - 1469-221X
TI - X10 expansion microscopy enables 25‐nm resolution on conventional microscopes
VL - 19
ER -
TY - CHAP
AB - This chapter finds an agreement of equivariant indices of semi-classical homomorphisms between pairwise mirror branes in the GL2 Higgs moduli space on a Riemann surface. On one side of the agreement, components of the Lagrangian brane of U(1,1) Higgs bundles, whose mirror was proposed by Hitchin to be certain even exterior powers of the hyperholomorphic Dirac bundle on the SL2 Higgs moduli space, are present. The agreement arises from a mysterious functional equation. This gives strong computational evidence for Hitchin’s proposal.
AU - Hausel, Tamás
AU - Mellit, Anton
AU - Pei, Du
ID - 6525
SN - 9780198802013
T2 - Geometry and Physics: Volume I
TI - Mirror symmetry with branes by equivariant verlinde formulas
ER -
TY - CONF
AB - This paper studies the problem of distributed stochastic optimization in an adversarial setting where, out of m machines which allegedly compute stochastic gradients every iteration, an α-fraction are Byzantine, and may behave adversarially. Our main result is a variant of stochastic gradient descent (SGD) which finds ε-approximate minimizers of convex functions in T=O~(1/ε²m+α²/ε²) iterations. In contrast, traditional mini-batch SGD needs T=O(1/ε²m) iterations, but cannot tolerate Byzantine failures. Further, we provide a lower bound showing that, up to logarithmic factors, our algorithm is information-theoretically optimal both in terms of sample complexity and time complexity.
AU - Alistarh, Dan-Adrian
AU - Allen-Zhu, Zeyuan
AU - Li, Jerry
ED - Bengio, S.
ED - Wallach, H.
ED - Larochelle, H.
ED - Grauman, K.
ED - Cesa-Bianchi, N.
ED - Garnett, R.
ID - 6558
T2 - Advances in Neural Information Processing Systems
TI - Byzantine Stochastic Gradient Descent
VL - Volume 2018
ER -
TY - CONF
AB - Distributed training of massive machine learning models, in particular deep neural networks, via Stochastic Gradient Descent (SGD) is becoming commonplace. Several families of communication-reduction methods, such as quantization, large-batch methods, and gradient sparsification, have been proposed. To date, gradient sparsification methods--where each node sorts gradients by magnitude, and only communicates a subset of the components, accumulating the rest locally--are known to yield some of the largest practical gains. Such methods can reduce the amount of communication per step by up to \emph{three orders of magnitude}, while preserving model accuracy. Yet, this family of methods currently has no theoretical justification. This is the question we address in this paper. We prove that, under analytic assumptions, sparsifying gradients by magnitude with local error correction provides convergence guarantees, for both convex and non-convex smooth objectives, for data-parallel SGD. The main insight is that sparsification methods implicitly maintain bounds on the maximum impact of stale updates, thanks to selection by magnitude. Our analysis and empirical validation also reveal that these methods do require analytical conditions to converge well, justifying existing heuristics.
AU - Alistarh, Dan-Adrian
AU - Hoefler, Torsten
AU - Johansson, Mikael
AU - Konstantinov, Nikola H
AU - Khirirat, Sarit
AU - Renggli, Cedric
ID - 6589
T2 - Advances in Neural Information Processing Systems 31
TI - The convergence of sparsified gradient methods
VL - Volume 2018
ER -
TY - CONF
AB - Reed-Muller (RM) and polar codes are a class of capacity-achieving channel coding schemes with the same factor graph representation. Low-complexity decoding algorithms fall short in providing a good error-correction performance for RM and polar codes. Using the symmetric group of RM and polar codes, the specific decoding algorithm can be carried out on multiple permutations of the factor graph to boost the error-correction performance. However, this approach results in high decoding complexity. In this paper, we first derive the total number of factor graph permutations on which the decoding can be performed. We further propose a successive permutation (SP) scheme which finds the permutations on the fly, thus the decoding always progresses on a single factor graph permutation. We show that SP can be used to improve the error-correction performance of RM and polar codes under successive-cancellation (SC) and SC list (SCL) decoding, while keeping the memory requirements of the decoders unaltered. Our results for RM and polar codes of length 128 and rate 0.5 show that when SP is used and at a target frame error rate of 10 -4 , up to 0.5 dB and 0.1 dB improvement can be achieved for RM and polar codes respectively.
AU - Hashemi, Seyyed Ali
AU - Doan, Nghia
AU - Mondelli, Marco
AU - Gross, Warren
ID - 6664
T2 - 2018 IEEE 10th International Symposium on Turbo Codes & Iterative Information Processing
TI - Decoding Reed-Muller and polar codes by successive factor graph permutations
ER -
TY - CONF
AB - We prove that, at least for the binary erasure channel, the polar-coding paradigm gives rise to codes that not only approach the Shannon limit but, in fact, do so under the best possible scaling of their block length as a function of the gap to capacity. This result exhibits the first known family of binary codes that attain both optimal scaling and quasi-linear complexity of encoding and decoding. Specifically, for any fixed δ > 0, we exhibit binary linear codes that ensure reliable communication at rates within ε > 0 of capacity with block length n = O(1/ε 2+δ ), construction complexity Θ(n), and encoding/decoding complexity Θ(n log n).
AU - Fazeli, Arman
AU - Hassani, Hamed
AU - Mondelli, Marco
AU - Vardy, Alexander
ID - 6665
T2 - 2018 IEEE Information Theory Workshop
TI - Binary linear codes with optimal scaling: Polar codes with large kernels
ER -
TY - JOUR
AB - Polar codes represent one of the major recent breakthroughs in coding theory and, because of their attractive features, they have been selected for the incoming 5G standard. As such, a lot of attention has been devoted to the development of decoding algorithms with good error performance and efficient hardware implementation. One of the leading candidates in this regard is represented by successive-cancellation list (SCL) decoding. However, its hardware implementation requires a large amount of memory. Recently, a partitioned SCL (PSCL) decoder has been proposed to significantly reduce the memory consumption. In this paper, we consider the paradigm of PSCL decoding from a practical standpoint, and we provide several improvements. First, by changing the target signal-to-noise ratio and consequently modifying the construction of the code, we are able to improve the performance at no additional computational, latency, or memory cost. Second, we bridge the performance gap between SCL and PSCL decoding by introducing a generalized PSCL decoder and a layered PSCL decoder. In this way, we obtain almost the same performance of the SCL decoder with a significantly lower memory requirement, as testified by hardware implementation results. Third, we present an optimal scheme to allocate cyclic redundancy checks. Finally, we provide a lower bound on the list size that guarantees optimal maximum a posteriori performance for the binary erasure channel.
AU - Hashemi, Seyyed Ali
AU - Mondelli, Marco
AU - Hassani, S. Hamed
AU - Condo, Carlo
AU - Urbanke, Rudiger L.
AU - Gross, Warren J.
ID - 6674
IS - 9
JF - IEEE Transactions on Communications
TI - Decoder partitioning: Towards practical list decoding of polar codes
VL - 66
ER -
TY - CONF
AB - We present a coding paradigm that provides a new achievable rate for the primitive relay channel by combining compress-and-forward and decode-and-forward with a chaining construction. In the primitive relay channel model, the source broadcasts a message to the relay and to the destination; and the relay facilitates this communication by sending an additional message to the destination through a separate channel. Two well-known coding approaches for this setting are decode-and-forward and compress-and-forward: in the former, the relay decodes the message and sends some of the information to the destination; in the latter, the relay does not attempt to decode, but it sends a compressed description of the received sequence to the destination via Wyner-Ziv coding. In our scheme, we transmit over pairs of blocks and we use compress-and-forward for the first block and decode-and-forward for the second. In particular, in the first block, the relay does not attempt to decode and it sends only a part of the compressed description of the received sequence; in the second block, the relay decodes the message and sends this information plus the remaining part of the compressed sequence relative to the first block. As a result, we strictly outperform both compress-and- forward and decode-and-forward. Furthermore, this paradigm can be implemented with a low-complexity polar coding scheme that has the typical attractive features of polar codes, i.e., quasi-linear encoding/decoding complexity and super-polynomial decay of the error probability. Throughout the paper we consider as a running example the special case of the erasure relay channel and we compare the rates achievable by our proposed scheme with the existing upper and lower bounds.
AU - Mondelli, Marco
AU - Hassani, Hamed
AU - Urbanke, Rudiger
ID - 6675
T2 - 2018 IEEE International Symposium on Information Theory
TI - A new coding paradigm for the primitive relay channel
ER -
TY - JOUR
AB - We survey coding techniques that enable reliable transmission at rates that approach the capacity of an arbitrary discrete memoryless channel. In particular, we take the point of view of modern coding theory and discuss how recent advances in coding for symmetric channels help provide more efficient solutions for the asymmetric case. We consider, in more detail, three basic coding paradigms. The first one is Gallager's scheme that consists of concatenating a linear code with a non-linear mapping so that the input distribution can be appropriately shaped. We explicitly show that both polar codes and spatially coupled codes can be employed in this scenario. Furthermore, we derive a scaling law between the gap to capacity, the cardinality of the input and output alphabets, and the required size of the mapper. The second one is an integrated scheme in which the code is used both for source coding, in order to create codewords distributed according to the capacity-achieving input distribution, and for channel coding, in order to provide error protection. Such a technique has been recently introduced by Honda and Yamamoto in the context of polar codes, and we show how to apply it also to the design of sparse graph codes. The third paradigm is based on an idea of Böcherer and Mathar, and separates the two tasks of source coding and channel coding by a chaining construction that binds together several codewords. We present conditions for the source code and the channel code, and we describe how to combine any source code with any channel code that fulfill those conditions, in order to provide capacity-achieving schemes for asymmetric channels. In particular, we show that polar codes, spatially coupled codes, and homophonic codes are suitable as basic building blocks of the proposed coding strategy. Rather than focusing on the exact details of the schemes, the purpose of this tutorial is to present different coding techniques that can then be implemented with many variants. There is no absolute winner and, in order to understand the most suitable technique for a specific application scenario, we provide a detailed comparison that takes into account several performance metrics.
AU - Mondelli, Marco
AU - Hassani, Hamed
AU - Urbanke, Rudiger
ID - 6678
IS - 5
JF - IEEE Transactions on Information Theory
SN - 0018-9448
TI - How to achieve the capacity of asymmetric channels
VL - 64
ER -
TY - CONF
AB - Polar codes are a channel coding scheme for the next generation of wireless communications standard (5G). The belief propagation (BP) decoder allows for parallel decoding of polar codes, making it suitable for high throughput applications. However, the error-correction performance of polar codes under BP decoding is far from the requirements of 5G. It has been shown that the error-correction performance of BP can be improved if the decoding is performed on multiple permuted factor graphs of polar codes. However, a different BP decoding scheduling is required for each factor graph permutation which results in the design of a different decoder for each permutation. Moreover, the selection of the different factor graph permutations is at random, which prevents the decoder to achieve a desirable error correction performance with a small number of permutations. In this paper, we first show that the permutations on the factor graph can be mapped into suitable permutations on the codeword positions. As a result, we can make use of a single decoder for all the permutations. In addition, we introduce a method to construct a set of predetermined permutations which can provide the correct codeword if the decoding fails on the original permutation. We show that for the 5G polar code of length 1024, the error-correction performance of the proposed decoder is more than 0.25 dB better than that of the BP decoder with the same number of random permutations at the frame error rate of 10 -4 .
AU - Doan, Nghia
AU - Hashemi, Seyyed Ali
AU - Mondelli, Marco
AU - Gross, Warren J.
ID - 6728
SN - 9781538647271
T2 - 2018 IEEE Global Communications Conference
TI - On the decoding of polar codes on permuted factor graphs
ER -
TY - JOUR
AB - A central problem of algebraic topology is to understand the homotopy groups 𝜋𝑑(𝑋) of a topological space X. For the computational version of the problem, it is well known that there is no algorithm to decide whether the fundamental group 𝜋1(𝑋) 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(𝑋) trivial), compute the higher homotopy group 𝜋𝑑(𝑋) for any given 𝑑≥2 . However, these algorithms come with a caveat: They compute the isomorphism type of 𝜋𝑑(𝑋) , 𝑑≥2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of 𝜋𝑑(𝑋) . Converting elements of this abstract group into explicit geometric maps from the d-dimensional sphere 𝑆𝑑 to X has been one of the main unsolved problems in the emerging field of computational homotopy theory. Here we present an algorithm that, given a simply connected space X, computes 𝜋𝑑(𝑋) and represents its elements as simplicial maps from a suitable triangulation of the d-sphere 𝑆𝑑 to X. For fixed d, the algorithm runs in time exponential in size(𝑋) , the number of simplices of X. Moreover, we prove that this is optimal: For every fixed 𝑑≥2 , we construct a family of simply connected spaces X such that for any simplicial map representing a generator of 𝜋𝑑(𝑋) , the size of the triangulation of 𝑆𝑑 on which the map is defined, is exponential in size(𝑋) .
AU - Filakovský, Marek
AU - Franek, Peter
AU - Wagner, Uli
AU - Zhechev, Stephan Y
ID - 6774
IS - 3-4
JF - Journal of Applied and Computational Topology
SN - 2367-1726
TI - Computing simplicial representatives of homotopy group elements
VL - 2
ER -
TY - THES
AB - The most common assumption made in statistical learning theory is the assumption of the independent and identically distributed (i.i.d.) data. While being very convenient mathematically, it is often very clearly violated in practice. This disparity between the machine learning theory and applications underlies a growing demand in the development of algorithms that learn from dependent data and theory that can provide generalization guarantees similar to the independent situations. This thesis is dedicated to two variants of dependencies that can arise in practice. One is a dependence on the level of samples in a single learning task. Another dependency type arises in the multi-task setting when the tasks are dependent on each other even though the data for them can be i.i.d. In both cases we model the data (samples or tasks) as stochastic processes and introduce new algorithms for both settings that take into account and exploit the resulting dependencies. We prove the theoretical guarantees on the performance of the introduced algorithms under different evaluation criteria and, in addition, we compliment the theoretical study by the empirical one, where we evaluate some of the algorithms on two real world datasets to highlight their practical applicability.
AU - Zimin, Alexander
ID - 68
TI - Learning from dependent data
ER -
TY - JOUR
AB - We consider spectral properties and the edge universality of sparse random matrices, the class of random matrices that includes the adjacency matrices of the Erdős–Rényi graph model G(N, p). We prove a local law for the eigenvalue density up to the spectral edges. Under a suitable condition on the sparsity, we also prove that the rescaled extremal eigenvalues exhibit GOE Tracy–Widom fluctuations if a deterministic shift of the spectral edge due to the sparsity is included. For the adjacency matrix of the Erdős–Rényi graph this establishes the Tracy–Widom fluctuations of the second largest eigenvalue when p is much larger than N−2/3 with a deterministic shift of order (Np)−1.
AU - Lee, Jii
AU - Schnelli, Kevin
ID - 690
IS - 1-2
JF - Probability Theory and Related Fields
TI - Local law and Tracy–Widom limit for sparse random matrices
VL - 171
ER -
TY - JOUR
AB - Background: Transport protein particle (TRAPP) is a multisubunit complex that regulates membrane trafficking through the Golgi apparatus. The clinical phenotype associated with mutations in various TRAPP subunits has allowed elucidation of their functions in specific tissues. The role of some subunits in human disease, however, has not been fully established, and their functions remain uncertain.
Objective: We aimed to expand the range of neurodevelopmental disorders associated with mutations in TRAPP subunits by exome sequencing of consanguineous families.
Methods: Linkage and homozygosity mapping and candidate gene analysis were used to identify homozygous mutations in families. Patient fibroblasts were used to study splicing defect and zebrafish to model the disease.
Results: We identified six individuals from three unrelated families with a founder homozygous splice mutation in TRAPPC6B, encoding a core subunit of the complex TRAPP I. Patients manifested a neurodevelopmental disorder characterised by microcephaly, epilepsy and autistic features, and showed splicing defect. Zebrafish trappc6b morphants replicated the human phenotype, displaying decreased head size and neuronal hyperexcitability, leading to a lower seizure threshold.
Conclusion: This study provides clinical and functional evidence of the role of TRAPPC6B in brain development and function.
AU - Marin Valencia, Isaac
AU - Novarino, Gaia
AU - Johansen, Anide
AU - Rosti, Başak
AU - Issa, Mahmoud
AU - Musaev, Damir
AU - Bhat, Gifty
AU - Scott, Eric
AU - Silhavy, Jennifer
AU - Stanley, Valentina
AU - Rosti, Rasim
AU - Gleeson, Jeremy
AU - Imam, Farhad
AU - Zaki, Maha
AU - Gleeson, Joseph
ID - 691
IS - 1
JF - Journal of Medical Genetics
TI - A homozygous founder mutation in TRAPPC6B associates with a neurodevelopmental disorder characterised by microcephaly epilepsy and autistic features
VL - 55
ER -
TY - JOUR
AB - We consider families of confocal conics and two pencils of Apollonian circles having the same foci. We will show that these families of curves generate trivial 3-webs and find the exact formulas describing them.
AU - Akopyan, Arseniy
ID - 692
IS - 1
JF - Geometriae Dedicata
TI - 3-Webs generated by confocal conics and circles
VL - 194
ER -
TY - CONF
AB - Bitcoin has become the most successful cryptocurrency ever deployed, and its most distinctive feature is that it is decentralized. Its underlying protocol (Nakamoto consensus) achieves this by using proof of work, which has the drawback that it causes the consumption of vast amounts of energy to maintain the ledger. Moreover, Bitcoin mining dynamics have become less distributed over time.
Towards addressing these issues, we propose SpaceMint, a cryptocurrency based on proofs of space instead of proofs of work. Miners in SpaceMint dedicate disk space rather than computation. We argue that SpaceMint’s design solves or alleviates several of Bitcoin’s issues: most notably, its large energy consumption. SpaceMint also rewards smaller miners fairly according to their contribution to the network, thus incentivizing more distributed participation.
This paper adapts proof of space to enable its use in cryptocurrency, studies the attacks that can arise against a Bitcoin-like blockchain that uses proof of space, and proposes a new blockchain format and transaction types to address these attacks. Our prototype shows that initializing 1 TB for mining takes about a day (a one-off setup cost), and miners spend on average just a fraction of a second per block mined. Finally, we provide a game-theoretic analysis modeling SpaceMint as an extensive game (the canonical game-theoretic notion for games that take place over time) and show that this stylized game satisfies a strong equilibrium notion, thereby arguing for SpaceMint ’s stability and consensus.
AU - Park, Sunoo
AU - Kwon, Albert
AU - Fuchsbauer, Georg
AU - Gazi, Peter
AU - Alwen, Joel F
AU - Pietrzak, Krzysztof Z
ID - 6941
SN - 0302-9743
T2 - 22nd International Conference on Financial Cryptography and Data Security
TI - SpaceMint: A cryptocurrency based on proofs of space
VL - 10957
ER -
TY - JOUR
AB - Using the geodesic distance on the n-dimensional sphere, we study the expected radius function of the Delaunay mosaic of a random set of points. Specifically, we consider the partition of the mosaic into intervals of the radius function and determine the expected number of intervals whose radii are less than or equal to a given threshold. We find that the expectations are essentially the same as for the Poisson–Delaunay mosaic in n-dimensional Euclidean space. Assuming the points are not contained in a hemisphere, the Delaunay mosaic is isomorphic to the boundary complex of the convex hull in Rn+1, so we also get the expected number of faces of a random inscribed polytope. As proved in Antonelli et al. [Adv. in Appl. Probab. 9–12 (1977–1980)], an orthant section of the n-sphere is isometric to the standard n-simplex equipped with the Fisher information metric. It follows that the latter space has similar stochastic properties as the n-dimensional Euclidean space. Our results are therefore relevant in information geometry and in population genetics.
AU - Edelsbrunner, Herbert
AU - Nikitenko, Anton
ID - 87
IS - 5
JF - Annals of Applied Probability
TI - Random inscribed polytopes have similar radius functions as Poisson-Delaunay mosaics
VL - 28
ER -
TY - JOUR
AB - The development of strategies to assemble microscopic machines from dissipative building blocks are essential on the route to novel active materials. We recently demonstrated the hierarchical self-assembly of phoretic microswimmers into self-spinning microgears and their synchronization by diffusiophoretic interactions [Aubret et al., Nat. Phys., 2018]. In this paper, we adopt a pedagogical approach and expose our strategy to control self-assembly and build machines using phoretic phenomena. We notably introduce Highly Inclined Laminated Optical sheets microscopy (HILO) to image and characterize anisotropic and dynamic diffusiophoretic interactions, which cannot be performed by conventional fluorescence microscopy. The dynamics of a (haematite) photocatalytic material immersed in (hydrogen peroxide) fuel under various illumination patterns is first described and quantitatively rationalized by a model of diffusiophoresis, the migration of a colloidal particle in a concentration gradient. It is further exploited to design phototactic microswimmers that direct towards the high intensity of light, as a result of the reorientation of the haematite in a light gradient. We finally show the assembly of self-spinning microgears from colloidal microswimmers and carefully characterize the interactions using HILO techniques. The results are compared with analytical and numerical predictions and agree quantitatively, stressing the important role played by concentration gradients induced by chemical activity to control and design interactions. Because the approach described hereby is generic, this works paves the way for the rational design of machines by controlling phoretic phenomena.
AU - Aubret, Antoine
AU - Palacci, Jérémie A
ID - 9053
IS - 47
JF - Soft Matter
KW - General Chemistry
KW - Condensed Matter Physics
SN - 1744-683X
TI - Diffusiophoretic design of self-spinning microgears from colloidal microswimmers
VL - 14
ER -
TY - JOUR
AB - Self-assembly is the autonomous organization of components into patterns or structures: an essential ingredient of biology and a desired route to complex organization1. At equilibrium, the structure is encoded through specific interactions2,3,4,5,6,7,8, at an unfavourable entropic cost for the system. An alternative approach, widely used by nature, uses energy input to bypass the entropy bottleneck and develop features otherwise impossible at equilibrium9. Dissipative building blocks that inject energy locally were made available by recent advances in colloidal science10,11 but have not been used to control self-assembly. Here we show the targeted formation of self-powered microgears from active particles and their autonomous synchronization into dynamical superstructures. We use a photoactive component that consumes fuel, haematite, to devise phototactic microswimmers that form self-spinning microgears following spatiotemporal light patterns. The gears are coupled via their chemical clouds by diffusiophoresis12 and constitute the elementary bricks of synchronized superstructures, which autonomously regulate their dynamics. The results are quantitatively rationalized on the basis of a stochastic description of diffusio-phoretic oscillators dynamically coupled by chemical gradients. Our findings harness non-equilibrium phoretic phenomena to program interactions and direct self-assembly with fidelity and specificity. It lays the groundwork for the autonomous construction of dynamical architectures and functional micro-machinery.
AU - Aubret, Antoine
AU - Youssef, Mena
AU - Sacanna, Stefano
AU - Palacci, Jérémie A
ID - 9062
IS - 11
JF - Nature Physics
SN - 1745-2473
TI - Targeted assembly and synchronization of self-spinning microgears
VL - 14
ER -