TY - CHAP AB - We introduce the notion of Witness Maps as a cryptographic notion of a proof system. A Unique Witness Map (UWM) deterministically maps all witnesses for an NP statement to a single representative witness, resulting in a computationally sound, deterministic-prover, non-interactive witness independent proof system. A relaxation of UWM, called Compact Witness Map (CWM), maps all the witnesses to a small number of witnesses, resulting in a “lossy” deterministic-prover, non-interactive proof-system. We also define a Dual Mode Witness Map (DMWM) which adds an “extractable” mode to a CWM. Our main construction is a DMWM for all NP relations, assuming sub-exponentially secure indistinguishability obfuscation ( iO ), along with standard cryptographic assumptions. The DMWM construction relies on a CWM and a new primitive called Cumulative All-Lossy-But-One Trapdoor Functions (C-ALBO-TDF), both of which are in turn instantiated based on iO and other primitives. Our instantiation of a CWM is in fact a UWM; in turn, we show that a UWM implies Witness Encryption. Along the way to constructing UWM and C-ALBO-TDF, we also construct, from standard assumptions, Puncturable Digital Signatures and a new primitive called Cumulative Lossy Trapdoor Functions (C-LTDF). The former improves up on a construction of Bellare et al. (Eurocrypt 2016), who relied on sub-exponentially secure iO and sub-exponentially secure OWF. As an application of our constructions, we show how to use a DMWM to construct the first leakage and tamper-resilient signatures with a deterministic signer, thereby solving a decade old open problem posed by Katz and Vaikunthanathan (Asiacrypt 2009), by Boyle, Segev and Wichs (Eurocrypt 2011), as well as by Faonio and Venturi (Asiacrypt 2016). Our construction achieves the optimal leakage rate of 1−o(1) . AU - Chakraborty, Suvradip AU - Prabhakaran, Manoj AU - Wichs, Daniel ED - Kiayias, A ID - 10865 SN - 0302-9743 T2 - Public-Key Cryptography TI - Witness maps and applications VL - 12110 ER - TY - JOUR AB - We consider a system of N bosons in the limit N→∞, interacting through singular potentials. For initial data exhibiting Bose–Einstein condensation, the many-body time evolution is well approximated through a quadratic fluctuation dynamics around a cubic nonlinear Schrödinger equation of the condensate wave function. We show that these fluctuations satisfy a (multi-variate) central limit theorem. AU - Rademacher, Simone Anna Elvira ID - 7611 JF - Letters in Mathematical Physics SN - 0377-9017 TI - Central limit theorem for Bose gases interacting through singular potentials VL - 110 ER - TY - JOUR AB - The biotic interactions hypothesis posits that biotic interactions are more important drivers of adaptation closer to the equator, evidenced by “stronger” contemporary interactions (e.g. greater interaction rates) and/or patterns of trait evolution consistent with a history of stronger interactions. Support for the hypothesis is mixed, but few studies span tropical and temperate regions while experimentally controlling for evolutionary history. Here, we integrate field observations and common garden experiments to quantify the relative importance of pollination and herbivory in a pair of tropical‐temperate congeneric perennial herbs. Phytolacca rivinoides and P. americana are pioneer species native to the Neotropics and the eastern USA, respectively. We compared plant‐pollinator and plant‐herbivore interactions between three tropical populations of P. rivinoides from Costa Rica and three temperate populations of P. americana from its northern range edge in Michigan and Ohio. For some metrics of interaction importance, we also included three subtropical populations of P. americana from its southern range edge in Florida. This approach confounds species and region but allows us, uniquely, to measure complementary proxies of interaction importance across a tropical‐temperate range in one system. To test the prediction that lower‐latitude plants are more reliant on insect pollinators, we quantified floral display and reward, insect visitation rates, and self‐pollination ability (autogamy). To test the prediction that lower‐latitude plants experience more herbivore pressure, we quantified herbivory rates, herbivore abundance, and leaf palatability. We found evidence supporting the biotic interactions hypothesis for most comparisons between P. rivinoides and north‐temperate P. americana (floral display, insect visitation, autogamy, herbivory, herbivore abundance, and young‐leaf palatability). Results for subtropical P. americana populations, however, were typically not intermediate between P. rivinoides and north‐temperate P. americana, as would be predicted by a linear latitudinal gradient in interaction importance. Subtropical young‐leaf palatability was intermediate, but subtropical mature leaves were the least palatable, and pollination‐related traits did not differ between temperate and subtropical regions. These nonlinear patterns of interaction importance suggest future work to relate interaction importance to climatic or biotic thresholds. In sum, we found that the biotic interactions hypothesis was more consistently supported at the larger spatial scale of our study. AU - Baskett, Carina AU - Schroeder, Lucy AU - Weber, Marjorie G. AU - Schemske, Douglas W. ID - 7236 IS - 1 JF - Ecological Monographs SN - 0012-9615 TI - Multiple metrics of latitudinal patterns in insect pollination and herbivory for a tropical‐temperate congener pair VL - 90 ER - TY - JOUR AB - * Morphogenesis and adaptive tropic growth in plants depend on gradients of the phytohormone auxin, mediated by the membrane‐based PIN‐FORMED (PIN) auxin transporters. PINs localize to a particular side of the plasma membrane (PM) or to the endoplasmic reticulum (ER) to directionally transport auxin and maintain intercellular and intracellular auxin homeostasis, respectively. However, the molecular cues that confer their diverse cellular localizations remain largely unknown. * In this study, we systematically swapped the domains between ER‐ and PM‐localized PIN proteins, as well as between apical and basal PM‐localized PINs from Arabidopsis thaliana , to shed light on why PIN family members with similar topological structures reside at different membrane compartments within cells. * Our results show that not only do the N‐ and C‐terminal transmembrane domains (TMDs) and central hydrophilic loop contribute to their differential subcellular localizations and cellular polarity, but that the pairwise‐matched N‐ and C‐terminal TMDs resulting from intramolecular domain–domain coevolution are also crucial for their divergent patterns of localization. * These findings illustrate the complexity of the evolutionary path of PIN proteins in acquiring their plethora of developmental functions and adaptive growth in plants. AU - Zhang, Yuzhou AU - Hartinger, Corinna AU - Wang, Xiaojuan AU - Friml, Jiří ID - 7697 IS - 5 JF - New Phytologist SN - 0028-646X TI - Directional auxin fluxes in plants by intramolecular domain‐domain co‐evolution of PIN auxin transporters VL - 227 ER - TY - JOUR AB - This paper introduces a simple method for simulating highly anisotropic elastoplastic material behaviors like the dissolution of fibrous phenomena (splintering wood, shredding bales of hay) and materials composed of large numbers of irregularly‐shaped bodies (piles of twigs, pencils, or cards). We introduce a simple transformation of the anisotropic problem into an equivalent isotropic one, and we solve this new “fictitious” isotropic problem using an existing simulator based on the material point method. Our approach results in minimal changes to existing simulators, and it allows us to re‐use popular isotropic plasticity models like the Drucker‐Prager yield criterion instead of inventing new anisotropic plasticity models for every phenomenon we wish to simulate. AU - Schreck, Camille AU - Wojtan, Christopher J ID - 8765 IS - 2 JF - Computer Graphics Forum KW - Computer Networks and Communications SN - 0167-7055 TI - A practical method for animating anisotropic elastoplastic materials VL - 39 ER - TY - JOUR AB - Water-in-salt electrolytes based on highly concentrated bis(trifluoromethyl)sulfonimide (TFSI) promise aqueous electrolytes with stabilities approaching 3 V. However, especially with an electrode approaching the cathodic (reductive) stability, cycling stability is insufficient. While stability critically relies on a solid electrolyte interphase (SEI), the mechanism behind the cathodic stability limit remains unclear. Here, we reveal two distinct reduction potentials for the chemical environments of ‘free’ and ‘bound’ water and that both contribute to SEI formation. Free-water is reduced ~1V above bound water in a hydrogen evolution reaction (HER) and responsible for SEI formation via reactive intermediates of the HER; concurrent LiTFSI precipitation/dissolution establishes a dynamic interface. The free-water population emerges, therefore, as the handle to extend the cathodic limit of aqueous electrolytes and the battery cycling stability. AU - Bouchal, Roza AU - Li, Zhujie AU - Bongu, Chandra AU - Le Vot, Steven AU - Berthelot, Romain AU - Rotenberg, Benjamin AU - Favier, Frederic AU - Freunberger, Stefan Alexander AU - Salanne, Mathieu AU - Fontaine, Olivier ID - 8057 IS - 37 JF - Angewandte Chemie SN - 0044-8249 TI - Competitive salt precipitation/dissolution during free‐water reduction in water‐in‐salt electrolyte VL - 132 ER - TY - JOUR AB - Coinfections with multiple pathogens can result in complex within‐host dynamics affecting virulence and transmission. While multiple infections are intensively studied in solitary hosts, it is so far unresolved how social host interactions interfere with pathogen competition, and if this depends on coinfection diversity. We studied how the collective disease defences of ants – their social immunity – influence pathogen competition in coinfections of same or different fungal pathogen species. Social immunity reduced virulence for all pathogen combinations, but interfered with spore production only in different‐species coinfections. Here, it decreased overall pathogen sporulation success while increasing co‐sporulation on individual cadavers and maintaining a higher pathogen diversity at the community level. Mathematical modelling revealed that host sanitary care alone can modulate competitive outcomes between pathogens, giving advantage to fast‐germinating, thus less grooming‐sensitive ones. Host social interactions can hence modulate infection dynamics in coinfected group members, thereby altering pathogen communities at the host level and population level. AU - Milutinovic, Barbara AU - Stock, Miriam AU - Grasse, Anna V AU - Naderlinger, Elisabeth AU - Hilbe, Christian AU - Cremer, Sylvia ID - 7343 IS - 3 JF - Ecology Letters SN - 1461-023X TI - Social immunity modulates competition between coinfecting pathogens VL - 23 ER - TY - JOUR AB - Sewall Wright developed FST for describing population differentiation and it has since been extended to many novel applications, including the detection of homomorphic sex chromosomes. However, there has been confusion regarding the expected estimate of FST for a fixed difference between the X‐ and Y‐chromosome when comparing males and females. Here, we attempt to resolve this confusion by contrasting two common FST estimators and explain why they yield different estimates when applied to the case of sex chromosomes. We show that this difference is true for many allele frequencies, but the situation characterized by fixed differences between the X‐ and Y‐chromosome is among the most extreme. To avoid additional confusion, we recommend that all authors using FST clearly state which estimator of FST their work uses. AU - Gammerdinger, William J AU - Toups, Melissa A AU - Vicoso, Beatriz ID - 8099 IS - 6 JF - Molecular Ecology Resources SN - 1755-098X TI - Disagreement in FST estimators: A case study from sex chromosomes VL - 20 ER - TY - JOUR AB - Water-in-salt electrolytes based on highly concentrated bis(trifluoromethyl)sulfonimide (TFSI) promise aqueous electrolytes with stabilities nearing 3 V. However, especially with an electrode approaching the cathodic (reductive) stability, cycling stability is insufficient. While stability critically relies on a solid electrolyte interphase (SEI), the mechanism behind the cathodic stability limit remains unclear. Here, we reveal two distinct reduction potentials for the chemical environments of 'free' and 'bound' water and that both contribute to SEI formation. Free-water is reduced ~1V above bound water in a hydrogen evolution reaction (HER) and responsible for SEI formation via reactive intermediates of the HER; concurrent LiTFSI precipitation/dissolution establishes a dynamic interface. The free-water population emerges, therefore, as the handle to extend the cathodic limit of aqueous electrolytes and the battery cycling stability. AU - Bouchal, Roza AU - Li, Zhujie AU - Bongu, Chandra AU - Le Vot, Steven AU - Berthelot, Romain AU - Rotenberg, Benjamin AU - Favier, Fréderic AU - Freunberger, Stefan Alexander AU - Salanne, Mathieu AU - Fontaine, Olivier ID - 7847 IS - 37 JF - Angewandte Chemie International Edition SN - 1433-7851 TI - Competitive salt precipitation/dissolution during free‐water reduction in water‐in‐salt electrolyte VL - 59 ER - TY - JOUR AB - Habitat loss is one of the key drivers of the ongoing decline of biodiversity. However, ecologists still argue about how fragmentation of habitat (independent of habitat loss) affects species richness. The recently proposed habitat amount hypothesis posits that species richness only depends on the total amount of habitat in a local landscape. In contrast, empirical studies report contrasting patterns: some find positive and others negative effects of fragmentation per se on species richness. To explain this apparent disparity, we devise a stochastic, spatially explicit model of competitive species communities in heterogeneous habitats. The model shows that habitat loss and fragmentation have complex effects on species diversity in competitive communities. When the total amount of habitat is large, fragmentation per se tends to increase species diversity, but if the total amount of habitat is small, the situation is reversed: fragmentation per se decreases species diversity. AU - Rybicki, Joel AU - Abrego, Nerea AU - Ovaskainen, Otso ID - 7224 IS - 3 JF - Ecology Letters SN - 1461-023X TI - Habitat fragmentation and species diversity in competitive communities VL - 23 ER - TY - JOUR AB - We show the synthesis of a redox‐active quinone, 2‐methoxy‐1,4‐hydroquinone (MHQ), from a bio‐based feedstock and its suitability as electrolyte in aqueous redox flow batteries. We identified semiquinone intermediates at insufficiently low pH and quinoid radicals as responsible for decomposition of MHQ under electrochemical conditions. Both can be avoided and/or stabilized, respectively, using H 3 PO 4 electrolyte, allowing for reversible cycling in a redox flow battery for hundreds of cycles. AU - Schlemmer, Werner AU - Nothdurft, Philipp AU - Petzold, Alina AU - Frühwirt, Philipp AU - Schmallegger, Max AU - Gescheidt-Demner, Georg AU - Fischer, Roland AU - Freunberger, Stefan Alexander AU - Kern, Wolfgang AU - Spirk, Stefan ID - 8329 IS - 51 JF - Angewandte Chemie International Edition SN - 1433-7851 TI - 2‐methoxyhydroquinone from vanillin for aqueous redox‐flow batteries VL - 59 ER - TY - GEN AB - Coinfections with multiple pathogens can result in complex within-host dynamics affecting virulence and transmission. Whilst multiple infections are intensively studied in solitary hosts, it is so far unresolved how social host interactions interfere with pathogen competition, and if this depends on coinfection diversity. We studied how the collective disease defenses of ants – their social immunity ­– influence pathogen competition in coinfections of same or different fungal pathogen species. Social immunity reduced virulence for all pathogen combinations, but interfered with spore production only in different-species coinfections. Here, it decreased overall pathogen sporulation success, whilst simultaneously increasing co-sporulation on individual cadavers and maintaining a higher pathogen diversity at the community-level. Mathematical modeling revealed that host sanitary care alone can modulate competitive outcomes between pathogens, giving advantage to fast-germinating, thus less grooming-sensitive ones. Host social interactions can hence modulate infection dynamics in coinfected group members, thereby altering pathogen communities at the host- and population-level. AU - Milutinovic, Barbara AU - Stock, Miriam AU - Grasse, Anna V AU - Naderlinger, Elisabeth AU - Hilbe, Christian AU - Cremer, Sylvia ID - 13060 TI - Social immunity modulates competition between coinfecting pathogens ER - TY - GEN AB - PADREV : 4,4'-dimethoxy[1,1'-biphenyl]-2,2',5,5'-tetrol Space Group: C 2 (5), Cell: a 24.488(16)Å b 5.981(4)Å c 3.911(3)Å, α 90° β 91.47(3)° γ 90° AU - Schlemmer, Werner AU - Nothdurft, Philipp AU - Petzold, Alina AU - Riess, Gisbert AU - Frühwirt, Philipp AU - Schmallegger, Max AU - Gescheidt-Demner, Georg AU - Fischer, Roland AU - Freunberger, Stefan Alexander AU - Kern, Wolfgang AU - Spirk, Stefan ID - 9780 TI - CCDC 1991959: Experimental Crystal Structure Determination ER - TY - JOUR AB - The hippocampus plays key roles in learning and memory and is a main target of Alzheimer's disease (AD), which causes progressive memory impairments. Despite numerous investigations about the processes required for the normal hippocampal functions, the neurotransmitter receptors involved in the synaptic deficits by which AD disables the hippocampus are not yet characterized. By combining histoblots, western blots, immunohistochemistry and high‐resolution immunoelectron microscopic methods for GABAB receptors, this study provides a quantitative description of the expression and the subcellular localization of GABAB1 in the hippocampus in a mouse model of AD at 1, 6 and 12 months of age. Western blots and histoblots showed that the total amount of protein and the laminar expression pattern of GABAB1 were similar in APP/PS1 mice and in age‐matched wild‐type mice. In contrast, immunoelectron microscopic techniques showed that the subcellular localization of GABAB1 subunit did not change significantly in APP/PS1 mice at 1 month of age, was significantly reduced in the stratum lacunosum‐moleculare of CA1 pyramidal cells at 6 months of age and significantly reduced at the membrane surface of CA1 pyramidal cells at 12 months of age. This reduction of plasma membrane GABAB1 was paralleled by a significant increase of the subunit at the intracellular sites. We further observed a decrease of membrane‐targeted GABAB receptors in axon terminals contacting CA1 pyramidal cells. Our data demonstrate compartment‐ and age‐dependent reduction of plasma membrane‐targeted GABAB receptors in the CA1 region of the hippocampus, suggesting that this decrease might be enough to alter the GABAB‐mediated synaptic transmission taking place in AD. AU - Martín-Belmonte, Alejandro AU - Aguado, Carolina AU - Alfaro-Ruíz, Rocío AU - Moreno-Martínez, Ana Esther AU - De La Ossa, Luis AU - Martínez-Hernández, José AU - Buisson, Alain AU - Früh, Simon AU - Bettler, Bernhard AU - Shigemoto, Ryuichi AU - Fukazawa, Yugo AU - Luján, Rafael ID - 7207 IS - 3 JF - Brain Pathology SN - 10156305 TI - Reduction in the neuronal surface of post and presynaptic GABA>B< receptors in the hippocampus in a mouse model of Alzheimer's disease VL - 30 ER - TY - JOUR AB - Genetic incompatibilities contribute to reproductive isolation between many diverging populations, but it is still unclear to what extent they play a role if divergence happens with gene flow. In contact zones between the "Crab" and "Wave" ecotypes of the snail Littorina saxatilis, divergent selection forms strong barriers to gene flow, while the role of post‐zygotic barriers due to selection against hybrids remains unclear. High embryo abortion rates in this species could indicate the presence of such barriers. Post‐zygotic barriers might include genetic incompatibilities (e.g. Dobzhansky–Muller incompatibilities) but also maladaptation, both expected to be most pronounced in contact zones. In addition, embryo abortion might reflect physiological stress on females and embryos independent of any genetic stress. We examined all embryos of >500 females sampled outside and inside contact zones of three populations in Sweden. Females' clutch size ranged from 0 to 1,011 embryos (mean 130 ± 123), and abortion rates varied between 0% and 100% (mean 12%). We described female genotypes by using a hybrid index based on hundreds of SNPs differentiated between ecotypes with which we characterized female genotypes. We also calculated female SNP heterozygosity and inversion karyotype. Clutch size did not vary with female hybrid index, and abortion rates were only weakly related to hybrid index in two sites but not at all in a third site. No additional variation in abortion rate was explained by female SNP heterozygosity, but increased female inversion heterozygosity added slightly to increased abortion. Our results show only weak and probably biologically insignificant post‐zygotic barriers contributing to ecotype divergence, and the high and variable abortion rates were marginally, if at all, explained by hybrid index of females. AU - Johannesson, Kerstin AU - Zagrodzka, Zuzanna AU - Faria, Rui AU - Westram, Anja M AU - Butlin, Roger K. ID - 7205 IS - 3 JF - Journal of Evolutionary Biology SN - 1010061X TI - Is embryo abortion a post-zygotic barrier to gene flow between Littorina ecotypes? VL - 33 ER - TY - JOUR AB - Previously, we reported that the allelic de-etiolated by zinc (dez) and trichome birefringence (tbr) mutants exhibit photomorphogenic development in the dark, which is enhanced by high Zn. TRICHOME BIREFRINGENCE-LIKE proteins had been implicated in transferring acetyl groups to various hemicelluloses. Pectin O-acetylation levels were lower in dark-grown dez seedlings than in the wild type. We observed Zn-enhanced photomorphogenesis in the dark also in the reduced wall acetylation 2 (rwa2-3) mutant, which exhibits lowered O-acetylation levels of cell wall macromolecules including pectins and xyloglucans, supporting a role for cell wall macromolecule O-acetylation in the photomorphogenic phenotypes of rwa2-3 and dez. Application of very short oligogalacturonides (vsOGs) restored skotomorphogenesis in dark-grown dez and rwa2-3. Here we demonstrate that in dez, O-acetylation of non-pectin cell wall components, notably of xyloglucan, is enhanced. Our results highlight the complexity of cell wall homeostasis and indicate against an influence of xyloglucan O-acetylation on light-dependent seedling development. AU - Sinclair, Scott A AU - Gille, S. AU - Pauly, M. AU - Krämer, U. ID - 7417 IS - 1 JF - Plant Signaling & Behavior SN - 1559-2324 TI - Regulation of acetylation of plant cell wall components is complex and responds to external stimuli VL - 15 ER - TY - JOUR AB - For complex Wigner-type matrices, i.e. Hermitian random matrices with independent, not necessarily identically distributed entries above the diagonal, we show that at any cusp singularity of the limiting eigenvalue distribution the local eigenvalue statistics are universal and form a Pearcey process. Since the density of states typically exhibits only square root or cubic root cusp singularities, our work complements previous results on the bulk and edge universality and it thus completes the resolution of the Wigner–Dyson–Mehta universality conjecture for the last remaining universality type in the complex Hermitian class. Our analysis holds not only for exact cusps, but approximate cusps as well, where an extended Pearcey process emerges. As a main technical ingredient we prove an optimal local law at the cusp for both symmetry classes. This result is also the key input in the companion paper (Cipolloni et al. in Pure Appl Anal, 2018. arXiv:1811.04055) where the cusp universality for real symmetric Wigner-type matrices is proven. The novel cusp fluctuation mechanism is also essential for the recent results on the spectral radius of non-Hermitian random matrices (Alt et al. in Spectral radius of random matrices with independent entries, 2019. arXiv:1907.13631), and the non-Hermitian edge universality (Cipolloni et al. in Edge universality for non-Hermitian random matrices, 2019. arXiv:1908.00969). AU - Erdös, László AU - Krüger, Torben H AU - Schröder, Dominik J ID - 6185 JF - Communications in Mathematical Physics SN - 0010-3616 TI - Cusp universality for random matrices I: Local law and the complex Hermitian case VL - 378 ER - TY - THES AB - This thesis is based on three main topics: In the first part, we study convergence of discrete gradient flow structures associated with regular finite-volume discretisations of Fokker-Planck equations. We show evolutionary I convergence of the discrete gradient flows to the L2-Wasserstein gradient flow corresponding to the solution of a Fokker-Planck equation in arbitrary dimension d >= 1. Along the argument, we prove Mosco- and I-convergence results for discrete energy functionals, which are of independent interest for convergence of equivalent gradient flow structures in Hilbert spaces. The second part investigates L2-Wasserstein flows on metric graph. The starting point is a Benamou-Brenier formula for the L2-Wasserstein distance, which is proved via a regularisation scheme for solutions of the continuity equation, adapted to the peculiar geometric structure of metric graphs. Based on those results, we show that the L2-Wasserstein space over a metric graph admits a gradient flow which may be identified as a solution of a Fokker-Planck equation. In the third part, we focus again on the discrete gradient flows, already encountered in the first part. We propose a variational structure which extends the gradient flow structure to Markov chains violating the detailed-balance conditions. Using this structure, we characterise contraction estimates for the discrete heat flow in terms of convexity of corresponding path-dependent energy functionals. In addition, we use this approach to derive several functional inequalities for said functionals. AU - Forkert, Dominik L ID - 7629 SN - 2663-337X TI - Gradient flows in spaces of probability measures for finite-volume schemes, metric graphs and non-reversible Markov chains ER - TY - THES AB - This thesis concerns itself with the interactions of evolutionary and ecological forces and the consequences on genetic diversity and the ultimate survival of populations. It is important to understand what signals processes leave on the genome and what we can infer from such data, which is usually abundant but noisy. Furthermore, understanding how and when populations adapt or go extinct is important for practical purposes, such as the genetic management of populations, as well as for theoretical questions, since local adaptation can be the first step toward speciation. In Chapter 2, we introduce the method of maximum entropy to approximate the demographic changes of a population in a simple setting, namely the logistic growth model with immigration. We show that this method is not only a powerful tool in physics but can be gainfully applied in an ecological framework. We investigate how well it approximates the real behavior of the system, and find that is does so, even in unexpected situations. Finally, we illustrate how it can model changing environments. In Chapter 3, we analyze the co-evolution of allele frequencies and population sizes in an infinite island model. We give conditions under which polygenic adaptation to a rare habitat is possible. The model we use is based on the diffusion approximation, considers eco-evolutionary feedback mechanisms (hard selection), and treats both drift and environmental fluctuations explicitly. We also look at limiting scenarios, for which we derive analytical expressions. In Chapter 4, we present a coalescent based simulation tool to obtain patterns of diversity in a spatially explicit subdivided population, in which the demographic history of each subpopulation can be specified. We compare the results to existing predictions, and explore the relative importance of time and space under a variety of spatial arrangements and demographic histories, such as expansion and extinction. In the last chapter, we give a brief outlook to further research. AU - Szep, Eniko ID - 8574 TI - Local adaptation in metapopulations ER - TY - THES AB - We study the interacting homogeneous Bose gas in two spatial dimensions in the thermodynamic limit at fixed density. We shall be concerned with some mathematical aspects of this complicated problem in many-body quantum mechanics. More specifically, we consider the dilute limit where the scattering length of the interaction potential, which is a measure for the effective range of the potential, is small compared to the average distance between the particles. We are interested in a setting with positive (i.e., non-zero) temperature. After giving a survey of the relevant literature in the field, we provide some facts and examples to set expectations for the two-dimensional system. The crucial difference to the three-dimensional system is that there is no Bose–Einstein condensate at positive temperature due to the Hohenberg–Mermin–Wagner theorem. However, it turns out that an asymptotic formula for the free energy holds similarly to the three-dimensional case. We motivate this formula by considering a toy model with δ interaction potential. By restricting this model Hamiltonian to certain trial states with a quasi-condensate we obtain an upper bound for the free energy that still has the quasi-condensate fraction as a free parameter. When minimizing over the quasi-condensate fraction, we obtain the Berezinskii–Kosterlitz–Thouless critical temperature for superfluidity, which plays an important role in our rigorous contribution. The mathematically rigorous result that we prove concerns the specific free energy in the dilute limit. We give upper and lower bounds on the free energy in terms of the free energy of the non-interacting system and a correction term coming from the interaction. Both bounds match and thus we obtain the leading term of an asymptotic approximation in the dilute limit, provided the thermal wavelength of the particles is of the same order (or larger) than the average distance between the particles. The remarkable feature of this result is its generality: the correction term depends on the interaction potential only through its scattering length and it holds for all nonnegative interaction potentials with finite scattering length that are measurable. In particular, this allows to model an interaction of hard disks. AU - Mayer, Simon ID - 7514 SN - 2663-337X TI - The free energy of a dilute two-dimensional Bose gas ER - TY - THES AB - Mrp (Multi resistance and pH adaptation) are broadly distributed secondary active antiporters that catalyze the transport of monovalent ions such as sodium and potassium outside of the cell coupled to the inward translocation of protons. Mrp antiporters are unique in a way that they are composed of seven subunits (MrpABCDEFG) encoded in a single operon, whereas other antiporters catalyzing the same reaction are mostly encoded by a single gene. Mrp exchangers are crucial for intracellular pH homeostasis and Na+ efflux, essential mechanisms for H+ uptake under alkaline environments and for reduction of the intracellular concentration of toxic cations. Mrp displays no homology to any other monovalent Na+(K+)/H+ antiporters but Mrp subunits have primary sequence similarity to essential redox-driven proton pumps, such as respiratory complex I and membrane-bound hydrogenases. This similarity reinforces the hypothesis that these present day redox-driven proton pumps are descended from the Mrp antiporter. The Mrp structure serves as a model to understand the yet obscure coupling mechanism between ion or electron transfer and proton translocation in this large group of proteins. In the thesis, I am presenting the purification, biochemical analysis, cryo-EM analysis and molecular structure of the Mrp complex from Anoxybacillus flavithermus solved by cryo-EM at 3.0 Å resolution. Numerous conditions were screened to purify Mrp to high homogeneity and to obtain an appropriate distribution of single particles on cryo-EM grids covered with a continuous layer of ultrathin carbon. A preferred particle orientation problem was solved by performing a tilted data collection. The activity assays showed the specific pH-dependent profile of secondary active antiporters. The molecular structure shows that Mrp is a dimer of seven-subunit protomers with 50 trans-membrane helices each. The dimer interface is built by many short and tilted transmembrane helices, probably causing a thinning of the bacterial membrane. The surface charge distribution shows an extraordinary asymmetry within each monomer, revealing presumable proton and sodium translocation pathways. The two largest and homologous Mrp subunits MrpA and MrpD probably translocate one proton each into the cell. The sodium ion is likely being translocated in the opposite direction within the small subunits along a ladder of charged and conserved residues. Based on the structure, we propose a mechanism were the antiport activity is accomplished via electrostatic interactions between the charged cations and key charged residues. The flexible key TM helices coordinate these electrostatic interactions, while the membrane thinning between the monomers enables the translocation of sodium across the charged membrane. The entire family of redox-driven proton pumps is likely to perform their mechanism in a likewise manner. AU - Steiner, Julia ID - 8353 SN - 2663-337X TI - Biochemical and structural investigation of the Mrp antiporter, an ancestor of complex I ER - TY - THES AB - The plant hormone auxin plays indispensable roles in plant growth and development. An essential level of regulation in auxin action is the directional auxin transport within cells. The establishment of auxin gradient in plant tissue has been attributed to local auxin biosynthesis and directional intercellular auxin transport, which both are controlled by various environmental and developmental signals. It is well established that asymmetric auxin distribution in cells is achieved by polarly localized PIN-FORMED (PIN) auxin efflux transporters. Despite the initial insights into cellular mechanisms of PIN polarization obtained from the last decades, the molecular mechanism and specific regulators mediating PIN polarization remains elusive. In this thesis, we aim to find novel players in PIN subcellular polarity regulation during Arabidopsis development. We first characterize the physiological effect of piperonylic acid (PA) on Arabidopsis hypocotyl gravitropic bending and PIN polarization. Secondly, we reveal the importance of SCFTIR1/AFB auxin signaling pathway in shoot gravitropism bending termination. In addition, we also explore the role of myosin XI complex, and actin cytoskeleton in auxin feedback regulation on PIN polarity. In Chapter 1, we give an overview of the current knowledge about PIN-mediated auxin fluxes in various plant tropic responses. In Chapter 2, we study the physiological effect of PA on shoot gravitropic bending. Our results show that PA treatment inhibits auxin-mediated PIN3 repolarization by interfering with PINOID and PIN3 phosphorylation status, ultimately leading to hyperbending hypocotyls. In Chapter 3, we provide evidence to show that the SCFTIR1/AFB nuclear auxin signaling pathway is crucial and required for auxin-mediated PIN3 repolarization and shoot gravitropic bending termination. In Chapter 4, we perform a phosphoproteomics approach and identify the motor protein Myosin XI and its binding protein, the MadB2 family, as an essential regulator of PIN polarity for auxin-canalization related developmental processes. In Chapter 5, we demonstrate the vital role of actin cytoskeleton in auxin feedback on PIN polarity by regulating PIN subcellular trafficking. Overall, the data presented in this PhD thesis brings novel insights into the PIN polar localization regulation that resulted in the (re)establishment of the polar auxin flow and gradient in response to environmental stimuli during plant development. AU - Han, Huibin ID - 8589 SN - 2663-337X TI - Novel insights into PIN polarity regulation during Arabidopsis development ER - TY - JOUR AB - Multiple resistance and pH adaptation (Mrp) antiporters are multi-subunit Na+ (or K+)/H+ exchangers representing an ancestor of many essential redox-driven proton pumps, such as respiratory complex I. The mechanism of coupling between ion or electron transfer and proton translocation in this large protein family is unknown. Here, we present the structure of the Mrp complex from Anoxybacillus flavithermus solved by cryo-EM at 3.0 Å resolution. It is a dimer of seven-subunit protomers with 50 trans-membrane helices each. Surface charge distribution within each monomer is remarkably asymmetric, revealing probable proton and sodium translocation pathways. On the basis of the structure we propose a mechanism where the coupling between sodium and proton translocation is facilitated by a series of electrostatic interactions between a cation and key charged residues. This mechanism is likely to be applicable to the entire family of redox proton pumps, where electron transfer to substrates replaces cation movements. AU - Steiner, Julia AU - Sazanov, Leonid A ID - 8284 JF - eLife TI - Structure and mechanism of the Mrp complex, an ancient cation/proton antiporter VL - 9 ER - TY - THES AB - In the thesis we focus on the interplay of the biophysics and evolution of gene regulation. We start by addressing how the type of prokaryotic gene regulation – activation and repression – affects spurious binding to DNA, also known as transcriptional crosstalk. We propose that regulatory interference caused by excess regulatory proteins in the dense cellular medium – global crosstalk – could be a factor in determining which type of gene regulatory network is evolutionarily preferred. Next,we use a normative approach in eukaryotic gene regulation to describe minimal non-equilibrium enhancer models that optimize so-called regulatory phenotypes. We find a class of models that differ from standard thermodynamic equilibrium models by a single parameter that notably increases the regulatory performance. Next chapter addresses the question of genotype-phenotype-fitness maps of higher dimensional phenotypes. We show that our biophysically realistic approach allows us to understand how the mechanisms of promoter function constrain genotypephenotype maps, and how they affect the evolutionary trajectories of promoters. In the last chapter we ask whether the intrinsic instability of gene duplication and amplification provides a generic alternative to canonical gene regulation. Using mathematical modeling, we show that amplifications can tune gene expression in many environments, including those where transcription factor-based schemes are hard to evolve or maintain. AU - Grah, Rok ID - 8155 SN - 2663-337X TI - Gene regulation across scales – how biophysical constraints shape evolution ER - TY - JOUR AU - Han, Huibin AU - Rakusova, Hana AU - Verstraeten, Inge AU - Zhang, Yuzhou AU - Friml, Jiří ID - 7643 IS - 5 JF - Plant Physiology SN - 0032-0889 TI - SCF TIR1/AFB auxin signaling for bending termination during shoot gravitropism VL - 183 ER - TY - GEN AB - In prokaryotes, thermodynamic models of gene regulation provide a highly quantitative mapping from promoter sequences to gene expression levels that is compatible with in vivo and in vitro bio-physical measurements. Such concordance has not been achieved for models of enhancer function in eukaryotes. In equilibrium models, it is difficult to reconcile the reported short transcription factor (TF) residence times on the DNA with the high specificity of regulation. In non-equilibrium models, progress is difficult due to an explosion in the number of parameters. Here, we navigate this complexity by looking for minimal non-equilibrium enhancer models that yield desired regulatory phenotypes: low TF residence time, high specificity and tunable cooperativity. We find that a single extra parameter, interpretable as the “linking rate” by which bound TFs interact with Mediator components, enables our models to escape equilibrium bounds and access optimal regulatory phenotypes, while remaining consistent with the reported phenomenology and simple enough to be inferred from upcoming experiments. We further find that high specificity in non-equilibrium models is in a tradeoff with gene expression noise, predicting bursty dynamics — an experimentally-observed hallmark of eukaryotic transcription. By drastically reducing the vast parameter space to a much smaller subspace that optimally realizes biological function prior to inference from data, our normative approach holds promise for mathematical models in systems biology. AU - Grah, Rok AU - Zoller, Benjamin AU - Tkačik, Gašper ID - 7675 T2 - bioRxiv TI - Normative models of enhancer function ER - TY - THES AB - Many methods for the reconstruction of shapes from sets of points produce ordered simplicial complexes, which are collections of vertices, edges, triangles, and their higher-dimensional analogues, called simplices, in which every simplex gets assigned a real value measuring its size. This thesis studies ordered simplicial complexes, with a focus on their topology, which reflects the connectedness of the represented shapes and the presence of holes. We are interested both in understanding better the structure of these complexes, as well as in developing algorithms for applications. For the Delaunay triangulation, the most popular measure for a simplex is the radius of the smallest empty circumsphere. Based on it, we revisit Alpha and Wrap complexes and experimentally determine their probabilistic properties for random data. Also, we prove the existence of tri-partitions, propose algorithms to open and close holes, and extend the concepts from Euclidean to Bregman geometries. AU - Ölsböck, Katharina ID - 7460 KW - shape reconstruction KW - hole manipulation KW - ordered complexes KW - Alpha complex KW - Wrap complex KW - computational topology KW - Bregman geometry SN - 2663-337X TI - The hole system of triangulated shapes ER - TY - THES AB - A search problem lies in the complexity class FNP if a solution to the given instance of the problem can be verified efficiently. The complexity class TFNP consists of all search problems in FNP that are total in the sense that a solution is guaranteed to exist. TFNP contains a host of interesting problems from fields such as algorithmic game theory, computational topology, number theory and combinatorics. Since TFNP is a semantic class, it is unlikely to have a complete problem. Instead, one studies its syntactic subclasses which are defined based on the combinatorial principle used to argue totality. Of particular interest is the subclass PPAD, which contains important problems like computing Nash equilibrium for bimatrix games and computational counterparts of several fixed-point theorems as complete. In the thesis, we undertake the study of averagecase hardness of TFNP, and in particular its subclass PPAD. Almost nothing was known about average-case hardness of PPAD before a series of recent results showed how to achieve it using a cryptographic primitive called program obfuscation. However, it is currently not known how to construct program obfuscation from standard cryptographic assumptions. Therefore, it is desirable to relax the assumption under which average-case hardness of PPAD can be shown. In the thesis we take a step in this direction. First, we show that assuming the (average-case) hardness of a numbertheoretic problem related to factoring of integers, which we call Iterated-Squaring, PPAD is hard-on-average in the random-oracle model. Then we strengthen this result to show that the average-case hardness of PPAD reduces to the (adaptive) soundness of the Fiat-Shamir Transform, a well-known technique used to compile a public-coin interactive protocol into a non-interactive one. As a corollary, we obtain average-case hardness for PPAD in the random-oracle model assuming the worst-case hardness of #SAT. Moreover, the above results can all be strengthened to obtain average-case hardness for the class CLS ⊆ PPAD. Our main technical contribution is constructing incrementally-verifiable procedures for computing Iterated-Squaring and #SAT. By incrementally-verifiable, we mean that every intermediate state of the computation includes a proof of its correctness, and the proof can be updated and verified in polynomial time. Previous constructions of such procedures relied on strong, non-standard assumptions. Instead, we introduce a technique called recursive proof-merging to obtain the same from weaker assumptions. AU - Kamath Hosdurg, Chethan ID - 7896 SN - 2663-337X TI - On the average-case hardness of total search problems ER - TY - CONF AB - State-of-the-art detection systems are generally evaluated on their ability to exhaustively retrieve objects densely distributed in the image, across a wide variety of appearances and semantic categories. Orthogonal to this, many real-life object detection applications, for example in remote sensing, instead require dealing with large images that contain only a few small objects of a single class, scattered heterogeneously across the space. In addition, they are often subject to strict computational constraints, such as limited battery capacity and computing power.To tackle these more practical scenarios, we propose a novel flexible detection scheme that efficiently adapts to variable object sizes and densities: We rely on a sequence of detection stages, each of which has the ability to predict groups of objects as well as individuals. Similar to a detection cascade, this multi-stage architecture spares computational effort by discarding large irrelevant regions of the image early during the detection process. The ability to group objects provides further computational and memory savings, as it allows working with lower image resolutions in early stages, where groups are more easily detected than individuals, as they are more salient. We report experimental results on two aerial image datasets, and show that the proposed method is as accurate yet computationally more efficient than standard single-shot detectors, consistently across three different backbone architectures. AU - Royer, Amélie AU - Lampert, Christoph ID - 7936 SN - 9781728165530 T2 - IEEE Winter Conference on Applications of Computer Vision TI - Localizing grouped instances for efficient detection in low-resource scenarios ER - TY - CONF AB - Fine-tuning is a popular way of exploiting knowledge contained in a pre-trained convolutional network for a new visual recognition task. However, the orthogonal setting of transferring knowledge from a pretrained network to a visually different yet semantically close source is rarely considered: This commonly happens with real-life data, which is not necessarily as clean as the training source (noise, geometric transformations, different modalities, etc.).To tackle such scenarios, we introduce a new, generalized form of fine-tuning, called flex-tuning, in which any individual unit (e.g. layer) of a network can be tuned, and the most promising one is chosen automatically. In order to make the method appealing for practical use, we propose two lightweight and faster selection procedures that prove to be good approximations in practice. We study these selection criteria empirically across a variety of domain shifts and data scarcity scenarios, and show that fine-tuning individual units, despite its simplicity, yields very good results as an adaptation technique. As it turns out, in contrast to common practice, rather than the last fully-connected unit it is best to tune an intermediate or early one in many domain- shift scenarios, which is accurately detected by flex-tuning. AU - Royer, Amélie AU - Lampert, Christoph ID - 7937 SN - 9781728165530 T2 - 2020 IEEE Winter Conference on Applications of Computer Vision TI - A flexible selection scheme for minimum-effort transfer learning ER - TY - CHAP AB - Image translation refers to the task of mapping images from a visual domain to another. Given two unpaired collections of images, we aim to learn a mapping between the corpus-level style of each collection, while preserving semantic content shared across the two domains. We introduce xgan, a dual adversarial auto-encoder, which captures a shared representation of the common domain semantic content in an unsupervised way, while jointly learning the domain-to-domain image translations in both directions. We exploit ideas from the domain adaptation literature and define a semantic consistency loss which encourages the learned embedding to preserve semantics shared across domains. We report promising qualitative results for the task of face-to-cartoon translation. The cartoon dataset we collected for this purpose, “CartoonSet”, is also publicly available as a new benchmark for semantic style transfer at https://google.github.io/cartoonset/index.html. AU - Royer, Amélie AU - Bousmalis, Konstantinos AU - Gouws, Stephan AU - Bertsch, Fred AU - Mosseri, Inbar AU - Cole, Forrester AU - Murphy, Kevin ED - Singh, Richa ED - Vatsa, Mayank ED - Patel, Vishal M. ED - Ratha, Nalini ID - 8092 SN - 9783030306717 T2 - Domain Adaptation for Visual Understanding TI - XGAN: Unsupervised image-to-image translation for many-to-many mappings ER - TY - THES AB - This thesis considers two examples of reconfiguration problems: flipping edges in edge-labelled triangulations of planar point sets and swapping labelled tokens placed on vertices of a graph. In both cases the studied structures – all the triangulations of a given point set or all token placements on a given graph – can be thought of as vertices of the so-called reconfiguration graph, in which two vertices are adjacent if the corresponding structures differ by a single elementary operation – by a flip of a diagonal in a triangulation or by a swap of tokens on adjacent vertices, respectively. We study the reconfiguration of one instance of a structure into another via (shortest) paths in the reconfiguration graph. For triangulations of point sets in which each edge has a unique label and a flip transfers the label from the removed edge to the new edge, we prove a polynomial-time testable condition, called the Orbit Theorem, that characterizes when two triangulations of the same point set lie in the same connected component of the reconfiguration graph. The condition was first conjectured by Bose, Lubiw, Pathak and Verdonschot. We additionally provide a polynomial time algorithm that computes a reconfiguring flip sequence, if it exists. Our proof of the Orbit Theorem uses topological properties of a certain high-dimensional cell complex that has the usual reconfiguration graph as its 1-skeleton. In the context of token swapping on a tree graph, we make partial progress on the problem of finding shortest reconfiguration sequences. We disprove the so-called Happy Leaf Conjecture and demonstrate the importance of swapping tokens that are already placed at the correct vertices. We also prove that a generalization of the problem to weighted coloured token swapping is NP-hard on trees but solvable in polynomial time on paths and stars. AU - Masárová, Zuzana ID - 7944 KW - reconfiguration KW - reconfiguration graph KW - triangulations KW - flip KW - constrained triangulations KW - shellability KW - piecewise-linear balls KW - token swapping KW - trees KW - coloured weighted token swapping SN - 2663-337X TI - Reconfiguration problems ER - TY - JOUR AB - Inspired by the possibility to experimentally manipulate and enhance chemical reactivity in helium nanodroplets, we investigate the effective interaction and the resulting correlations between two diatomic molecules immersed in a bath of bosons. By analogy with the bipolaron, we introduce the biangulon quasiparticle describing two rotating molecules that align with respect to each other due to the effective attractive interaction mediated by the excitations of the bath. We study this system in different parameter regimes and apply several theoretical approaches to describe its properties. Using a Born–Oppenheimer approximation, we investigate the dependence of the effective intermolecular interaction on the rotational state of the two molecules. In the strong-coupling regime, a product-state ansatz shows that the molecules tend to have a strong alignment in the ground state. To investigate the system in the weak-coupling regime, we apply a one-phonon excitation variational ansatz, which allows us to access the energy spectrum. In comparison to the angulon quasiparticle, the biangulon shows shifted angulon instabilities and an additional spectral instability, where resonant angular momentum transfer between the molecules and the bath takes place. These features are proposed as an experimentally observable signature for the formation of the biangulon quasiparticle. Finally, by using products of single angulon and bare impurity wave functions as basis states, we introduce a diagonalization scheme that allows us to describe the transition from two separated angulons to a biangulon as a function of the distance between the two molecules. AU - Li, Xiang AU - Yakaboylu, Enderalp AU - Bighin, Giacomo AU - Schmidt, Richard AU - Lemeshko, Mikhail AU - Deuchert, Andreas ID - 8587 IS - 16 JF - The Journal of Chemical Physics KW - Physical and Theoretical Chemistry KW - General Physics and Astronomy SN - 0021-9606 TI - Intermolecular forces and correlations mediated by a phonon bath VL - 152 ER - TY - THES AB - One of the most striking hallmarks of the eukaryotic cell is the presence of intracellular vesicles and organelles. Each of these membrane-enclosed compartments has a distinct composition of lipids and proteins, which is essential for accurate membrane traffic and homeostasis. Interestingly, their biochemical identities are achieved with the help of small GTPases of the Rab family, which cycle between GDP- and GTP-bound forms on the selected membrane surface. While this activity switch is well understood for an individual protein, how Rab GTPases collectively transition between states to generate decisive signal propagation in space and time is unclear. In my PhD thesis, I present in vitro reconstitution experiments with theoretical modeling to systematically study a minimal Rab5 activation network from bottom-up. We find that positive feedback based on known molecular interactions gives rise to bistable GTPase activity switching on system’s scale. Furthermore, we determine that collective transition near the critical point is intrinsically stochastic and provide evidence that the inactive Rab5 abundance on the membrane can shape the network response. Finally, we demonstrate that collective switching can spread on the lipid bilayer as a traveling activation wave, representing a possible emergent activity pattern in endosomal maturation. Together, our findings reveal new insights into the self-organization properties of signaling networks away from chemical equilibrium. Our work highlights the importance of systematic characterization of biochemical systems in well-defined physiological conditions. This way, we were able to answer long-standing open questions in the field and close the gap between regulatory processes on a molecular scale and emergent responses on system’s level. AU - Bezeljak, Urban ID - 8341 SN - 2663-337X TI - In vitro reconstitution of a Rab activation switch ER - TY - JOUR AB - The eukaryotic endomembrane system is controlled by small GTPases of the Rab family, which are activated at defined times and locations in a switch-like manner. While this switch is well understood for an individual protein, how regulatory networks produce intracellular activity patterns is currently not known. Here, we combine in vitro reconstitution experiments with computational modeling to study a minimal Rab5 activation network. We find that the molecular interactions in this system give rise to a positive feedback and bistable collective switching of Rab5. Furthermore, we find that switching near the critical point is intrinsically stochastic and provide evidence that controlling the inactive population of Rab5 on the membrane can shape the network response. Notably, we demonstrate that collective switching can spread on the membrane surface as a traveling wave of Rab5 activation. Together, our findings reveal how biochemical signaling networks control vesicle trafficking pathways and how their nonequilibrium properties define the spatiotemporal organization of the cell. AU - Bezeljak, Urban AU - Loya, Hrushikesh AU - Kaczmarek, Beata M AU - Saunders, Timothy E. AU - Loose, Martin ID - 7580 IS - 12 JF - Proceedings of the National Academy of Sciences SN - 0027-8424 TI - Stochastic activation and bistability in a Rab GTPase regulatory network VL - 117 ER - TY - THES AB - Algorithms in computational 3-manifold topology typically take a triangulation as an input and return topological information about the underlying 3-manifold. However, extracting the desired information from a triangulation (e.g., evaluating an invariant) is often computationally very expensive. In recent years this complexity barrier has been successfully tackled in some cases by importing ideas from the theory of parameterized algorithms into the realm of 3-manifolds. Various computationally hard problems were shown to be efficiently solvable for input triangulations that are sufficiently “tree-like.” In this thesis we focus on the key combinatorial parameter in the above context: we consider the treewidth of a compact, orientable 3-manifold, i.e., the smallest treewidth of the dual graph of any triangulation thereof. By building on the work of Scharlemann–Thompson and Scharlemann–Schultens–Saito on generalized Heegaard splittings, and on the work of Jaco–Rubinstein on layered triangulations, we establish quantitative relations between the treewidth and classical topological invariants of a 3-manifold. In particular, among other results, we show that the treewidth of a closed, orientable, irreducible, non-Haken 3-manifold is always within a constant factor of its Heegaard genus. AU - Huszár, Kristóf ID - 8032 SN - 2663-337X TI - Combinatorial width parameters for 3-dimensional manifolds ER - TY - CONF AB - This paper presents a foundation for refining concurrent programs with structured control flow. The verification problem is decomposed into subproblems that aid interactive program development, proof reuse, and automation. The formalization in this paper is the basis of a new design and implementation of the Civl verifier. AU - Kragl, Bernhard AU - Qadeer, Shaz AU - Henzinger, Thomas A ID - 8195 SN - 0302-9743 T2 - Computer Aided Verification TI - Refinement for structured concurrent programs VL - 12224 ER - TY - CONF AB - Asynchronous programs are notoriously difficult to reason about because they spawn computation tasks which take effect asynchronously in a nondeterministic way. Devising inductive invariants for such programs requires understanding and stating complex relationships between an unbounded number of computation tasks in arbitrarily long executions. In this paper, we introduce inductive sequentialization, a new proof rule that sidesteps this complexity via a sequential reduction, a sequential program that captures every behavior of the original program up to reordering of coarse-grained commutative actions. A sequential reduction of a concurrent program is easy to reason about since it corresponds to a simple execution of the program in an idealized synchronous environment, where processes act in a fixed order and at the same speed. We have implemented and integrated our proof rule in the CIVL verifier, allowing us to provably derive fine-grained implementations of asynchronous programs. We have successfully applied our proof rule to a diverse set of message-passing protocols, including leader election protocols, two-phase commit, and Paxos. AU - Kragl, Bernhard AU - Enea, Constantin AU - Henzinger, Thomas A AU - Mutluergil, Suha Orhun AU - Qadeer, Shaz ID - 8012 SN - 9781450376136 T2 - Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation TI - Inductive sequentialization of asynchronous programs ER - TY - THES AB - During bacterial cell division, the tubulin-homolog FtsZ forms a ring-like structure at the center of the cell. This so-called Z-ring acts as a scaffold recruiting several division-related proteins to mid-cell and plays a key role in distributing proteins at the division site, a feature driven by the treadmilling motion of FtsZ filaments around the septum. What regulates the architecture, dynamics and stability of the Z-ring is still poorly understood, but FtsZ-associated proteins (Zaps) are known to play an important role. Advances in fluorescence microscopy and in vitro reconstitution experiments have helped to shed light into some of the dynamic properties of these complex systems, but methods that allow to collect and analyze large quantitative data sets of the underlying polymer dynamics are still missing. Here, using an in vitro reconstitution approach, we studied how different Zaps affect FtsZ filament dynamics and organization into large-scale patterns, giving special emphasis to the role of the well-conserved protein ZapA. For this purpose, we use high-resolution fluorescence microscopy combined with novel image analysis workfows to study pattern organization and polymerization dynamics of active filaments. We quantified the influence of Zaps on FtsZ on three diferent spatial scales: the large-scale organization of the membrane-bound filament network, the underlying polymerization dynamics and the behavior of single molecules. We found that ZapA cooperatively increases the spatial order of the filament network, binds only transiently to FtsZ filaments and has no effect on filament length and treadmilling velocity. Our data provides a model for how FtsZ-associated proteins can increase the precision and stability of the bacterial cell division machinery in a switch-like manner, without compromising filament dynamics. Furthermore, we believe that our automated quantitative methods can be used to analyze a large variety of dynamic cytoskeletal systems, using standard time-lapse movies of homogeneously labeled proteins obtained from experiments in vitro or even inside the living cell. AU - Dos Santos Caldas, Paulo R ID - 8358 SN - 2663-337X TI - Organization and dynamics of treadmilling filaments in cytoskeletal networks of FtsZ and its crosslinkers ER - TY - CONF AB - Even though Delaunay originally introduced his famous triangulations in the case of infinite point sets with translational periodicity, a software that computes such triangulations in the general case is not yet available, to the best of our knowledge. Combining and generalizing previous work, we present a practical algorithm for computing such triangulations. The algorithm has been implemented and experiments show that its performance is as good as the one of the CGAL package, which is restricted to cubic periodicity. AU - Osang, Georg F AU - Rouxel-Labbé, Mael AU - Teillaud, Monique ID - 8703 SN - 18688969 T2 - 28th Annual European Symposium on Algorithms TI - Generalizing CGAL periodic Delaunay triangulations VL - 173 ER - TY - CONF AB - We address the following question: How redundant is the parameterisation of ReLU networks? Specifically, we consider transformations of the weight space which leave the function implemented by the network intact. Two such transformations are known for feed-forward architectures: permutation of neurons within a layer, and positive scaling of all incoming weights of a neuron coupled with inverse scaling of its outgoing weights. In this work, we show for architectures with non-increasing widths that permutation and scaling are in fact the only function-preserving weight transformations. For any eligible architecture we give an explicit construction of a neural network such that any other network that implements the same function can be obtained from the original one by the application of permutations and rescaling. The proof relies on a geometric understanding of boundaries between linear regions of ReLU networks, and we hope the developed mathematical tools are of independent interest. AU - Bui Thi Mai, Phuong AU - Lampert, Christoph ID - 7481 T2 - 8th International Conference on Learning Representations TI - Functional vs. parametric equivalence of ReLU networks ER - TY - JOUR AB - We consider the Pekar functional on a ball in ℝ3. We prove uniqueness of minimizers, and a quadratic lower bound in terms of the distance to the minimizer. The latter follows from nondegeneracy of the Hessian at the minimum. AU - Feliciangeli, Dario AU - Seiringer, Robert ID - 9781 IS - 1 JF - SIAM Journal on Mathematical Analysis KW - Applied Mathematics KW - Computational Mathematics KW - Analysis SN - 0036-1410 TI - Uniqueness and nondegeneracy of minimizers of the Pekar functional on a ball VL - 52 ER - TY - JOUR AB - In the present work, we consider the evolution of two fluids separated by a sharp interface in the presence of surface tension—like, for example, the evolution of oil bubbles in water. Our main result is a weak–strong uniqueness principle for the corresponding free boundary problem for the incompressible Navier–Stokes equation: as long as a strong solution exists, any varifold solution must coincide with it. In particular, in the absence of physical singularities, the concept of varifold solutions—whose global in time existence has been shown by Abels (Interfaces Free Bound 9(1):31–65, 2007) for general initial data—does not introduce a mechanism for non-uniqueness. The key ingredient of our approach is the construction of a relative entropy functional capable of controlling the interface error. If the viscosities of the two fluids do not coincide, even for classical (strong) solutions the gradient of the velocity field becomes discontinuous at the interface, introducing the need for a careful additional adaption of the relative entropy. AU - Fischer, Julian L AU - Hensel, Sebastian ID - 7489 JF - Archive for Rational Mechanics and Analysis SN - 00039527 TI - Weak–strong uniqueness for the Navier–Stokes equation for two fluids with surface tension VL - 236 ER - TY - GEN AB - We prove that in the absence of topological changes, the notion of BV solutions to planar multiphase mean curvature flow does not allow for a mechanism for (unphysical) non-uniqueness. Our approach is based on the local structure of the energy landscape near a classical evolution by mean curvature. Mean curvature flow being the gradient flow of the surface energy functional, we develop a gradient-flow analogue of the notion of calibrations. Just like the existence of a calibration guarantees that one has reached a global minimum in the energy landscape, the existence of a "gradient flow calibration" ensures that the route of steepest descent in the energy landscape is unique and stable. AU - Fischer, Julian L AU - Hensel, Sebastian AU - Laux, Tim AU - Simon, Thilo ID - 10012 T2 - arXiv TI - The local structure of the energy landscape in multiphase mean curvature flow: weak-strong uniqueness and stability of evolutions ER - TY - JOUR AB - The superconducting circuit community has recently discovered the promising potential of superinductors. These circuit elements have a characteristic impedance exceeding the resistance quantum RQ ≈ 6.45 kΩ which leads to a suppression of ground state charge fluctuations. Applications include the realization of hardware protected qubits for fault tolerant quantum computing, improved coupling to small dipole moment objects and defining a new quantum metrology standard for the ampere. In this work we refute the widespread notion that superinductors can only be implemented based on kinetic inductance, i.e. using disordered superconductors or Josephson junction arrays. We present modeling, fabrication and characterization of 104 planar aluminum coil resonators with a characteristic impedance up to 30.9 kΩ at 5.6 GHz and a capacitance down to ≤ 1 fF, with lowloss and a power handling reaching 108 intra-cavity photons. Geometric superinductors are free of uncontrolled tunneling events and offer high reproducibility, linearity and the ability to couple magnetically - properties that significantly broaden the scope of future quantum circuits. AU - Peruzzo, Matilda AU - Trioni, Andrea AU - Hassani, Farid AU - Zemlicka, Martin AU - Fink, Johannes M ID - 8755 IS - 4 JF - Physical Review Applied TI - Surpassing the resistance quantum with a geometric superinductor VL - 14 ER - TY - JOUR AB - This paper deals with dynamical optimal transport metrics defined by spatial discretisation of the Benamou–Benamou formula for the Kantorovich metric . Such metrics appear naturally in discretisations of -gradient flow formulations for dissipative PDE. However, it has recently been shown that these metrics do not in general converge to , unless strong geometric constraints are imposed on the discrete mesh. In this paper we prove that, in a 1-dimensional periodic setting, discrete transport metrics converge to a limiting transport metric with a non-trivial effective mobility. This mobility depends sensitively on the geometry of the mesh and on the non-local mobility at the discrete level. Our result quantifies to what extent discrete transport can make use of microstructure in the mesh to reduce the cost of transport. AU - Gladbach, Peter AU - Kopfer, Eva AU - Maas, Jan AU - Portinale, Lorenzo ID - 7573 IS - 7 JF - Journal de Mathematiques Pures et Appliquees SN - 00217824 TI - Homogenisation of one-dimensional discrete optimal transport VL - 139 ER - TY - GEN AB - We consider finite-volume approximations of Fokker-Planck equations on bounded convex domains in R^d and study the corresponding gradient flow structures. We reprove the convergence of the discrete to continuous Fokker-Planck equation via the method of Evolutionary Γ-convergence, i.e., we pass to the limit at the level of the gradient flow structures, generalising the one-dimensional result obtained by Disser and Liero. The proof is of variational nature and relies on a Mosco convergence result for functionals in the discrete-to-continuum limit that is of independent interest. Our results apply to arbitrary regular meshes, even though the associated discrete transport distances may fail to converge to the Wasserstein distance in this generality. AU - Forkert, Dominik L AU - Maas, Jan AU - Portinale, Lorenzo ID - 10022 T2 - arXiv TI - Evolutionary Γ-convergence of entropic gradient flow structures for Fokker-Planck equations in multiple dimensions ER - TY - CONF AB - We study the problem of learning from multiple untrusted data sources, a scenario of increasing practical relevance given the recent emergence of crowdsourcing and collaborative learning paradigms. Specifically, we analyze the situation in which a learning system obtains datasets from multiple sources, some of which might be biased or even adversarially perturbed. It is known that in the single-source case, an adversary with the power to corrupt a fixed fraction of the training data can prevent PAC-learnability, that is, even in the limit of infinitely much training data, no learning system can approach the optimal test error. In this work we show that, surprisingly, the same is not true in the multi-source setting, where the adversary can arbitrarily corrupt a fixed fraction of the data sources. Our main results are a generalization bound that provides finite-sample guarantees for this learning setting, as well as corresponding lower bounds. Besides establishing PAC-learnability our results also show that in a cooperative learning setting sharing data with other parties has provable benefits, even if some participants are malicious. AU - Konstantinov, Nikola H AU - Frantar, Elias AU - Alistarh, Dan-Adrian AU - Lampert, Christoph ID - 8724 SN - 2640-3498 T2 - Proceedings of the 37th International Conference on Machine Learning TI - On the sample complexity of adversarial multi-source PAC learning VL - 119 ER - TY - JOUR AB - Determining the phase diagram of systems consisting of smaller subsystems 'connected' via a tunable coupling is a challenging task relevant for a variety of physical settings. A general question is whether new phases, not present in the uncoupled limit, may arise. We use machine learning and a suitable quasidistance between different points of the phase diagram to study layered spin models, in which the spin variables constituting each of the uncoupled systems (to which we refer as layers) are coupled to each other via an interlayer coupling. In such systems, in general, composite order parameters involving spins of different layers may emerge as a consequence of the interlayer coupling. We focus on the layered Ising and Ashkin–Teller models as a paradigmatic case study, determining their phase diagram via the application of a machine learning algorithm to the Monte Carlo data. Remarkably our technique is able to correctly characterize all the system phases also in the case of hidden order parameters, i.e. order parameters whose expression in terms of the microscopic configurations would require additional preprocessing of the data fed to the algorithm. We correctly retrieve the three known phases of the Ashkin–Teller model with ferromagnetic couplings, including the phase described by a composite order parameter. For the bilayer and trilayer Ising models the phases we find are only the ferromagnetic and the paramagnetic ones. Within the approach we introduce, owing to the construction of convolutional neural networks, naturally suitable for layered image-like data with arbitrary number of layers, no preprocessing of the Monte Carlo data is needed, also with regard to its spatial structure. The physical meaning of our results is discussed and compared with analytical data, where available. Yet, the method can be used without any a priori knowledge of the phases one seeks to find and can be applied to other models and structures. AU - Rzadkowski, Wojciech AU - Defenu, N AU - Chiacchiera, S AU - Trombettoni, A AU - Bighin, Giacomo ID - 8644 IS - 9 JF - New Journal of Physics SN - 13672630 TI - Detecting composite orders in layered models via machine learning VL - 22 ER - TY - JOUR AB - We consider the quantum mechanical many-body problem of a single impurity particle immersed in a weakly interacting Bose gas. The impurity interacts with the bosons via a two-body potential. We study the Hamiltonian of this system in the mean-field limit and rigorously show that, at low energies, the problem is well described by the Fröhlich polaron model. AU - Mysliwy, Krzysztof AU - Seiringer, Robert ID - 8705 IS - 12 JF - Annales Henri Poincare SN - 1424-0637 TI - Microscopic derivation of the Fröhlich Hamiltonian for the Bose polaron in the mean-field limit VL - 21 ER -