TY - JOUR
AB - Bow-tie or hourglass structure is a common architectural feature found in many biological systems. A bow-tie in a multi-layered structure occurs when intermediate layers have much fewer components than the input and output layers. Examples include metabolism where a handful of building blocks mediate between multiple input nutrients and multiple output biomass components, and signaling networks where information from numerous receptor types passes through a small set of signaling pathways to regulate multiple output genes. Little is known, however, about how bow-tie architectures evolve. Here, we address the evolution of bow-tie architectures using simulations of multi-layered systems evolving to fulfill a given input-output goal. We find that bow-ties spontaneously evolve when the information in the evolutionary goal can be compressed. Mathematically speaking, bow-ties evolve when the rank of the input-output matrix describing the evolutionary goal is deficient. The maximal compression possible (the rank of the goal) determines the size of the narrowest part of the network—that is the bow-tie. A further requirement is that a process is active to reduce the number of links in the network, such as product-rule mutations, otherwise a non-bow-tie solution is found in the evolutionary simulations. This offers a mechanism to understand a common architectural principle of biological systems, and a way to quantitate the effective rank of the goals under which they evolved.
AU - Friedlander, Tamar
AU - Mayo, Avraham
AU - Tlusty, Tsvi
AU - Alon, Uri
ID - 1827
IS - 3
JF - PLoS Computational Biology
TI - Evolution of bow-tie architectures in biology
VL - 11
ER -
TY - JOUR
AB - We construct a non-linear Markov process connected with a biological model of a bacterial genome recombination. The description of invariant measures of this process gives us the solution of one problem in elementary probability theory.
AU - Akopyan, Arseniy
AU - Pirogov, Sergey
AU - Rybko, Aleksandr
ID - 1828
IS - 1
JF - Journal of Statistical Physics
TI - Invariant measures of genetic recombination process
VL - 160
ER -
TY - JOUR
AB - To prevent epidemics, insect societies have evolved collective disease defences that are highly effective at curing exposed individuals and limiting disease transmission to healthy group members. Grooming is an important sanitary behaviour—either performed towards oneself (self-grooming) or towards others (allogrooming)—to remove infectious agents from the body surface of exposed individuals, but at the risk of disease contraction by the groomer. We use garden ants (Lasius neglectus) and the fungal pathogen Metarhizium as a model system to study how pathogen presence affects self-grooming and allogrooming between exposed and healthy individuals. We develop an epidemiological SIS model to explore how experimentally observed grooming patterns affect disease spread within the colony, thereby providing a direct link between the expression and direction of sanitary behaviours, and their effects on colony-level epidemiology. We find that fungus-exposed ants increase self-grooming, while simultaneously decreasing allogrooming. This behavioural modulation seems universally adaptive and is predicted to contain disease spread in a great variety of host–pathogen systems. In contrast, allogrooming directed towards pathogen-exposed individuals might both increase and decrease disease risk. Our model reveals that the effect of allogrooming depends on the balance between pathogen infectiousness and efficiency of social host defences, which are likely to vary across host–pathogen systems.
AU - Theis, Fabian
AU - Ugelvig, Line V
AU - Marr, Carsten
AU - Cremer, Sylvia
ID - 1830
IS - 1669
JF - Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences
TI - Opposing effects of allogrooming on disease transmission in ant societies
VL - 370
ER -
TY - JOUR
AB - This paper introduces a theme issue presenting the latest developments in research on the impacts of sociality on health and fitness. The articles that follow cover research on societies ranging from insects to humans. Variation in measures of fitness (i.e. survival and reproduction) has been linked to various aspects of sociality in humans and animals alike, and variability in individual health and condition has been recognized as a key mediator of these relationships. Viewed from a broad evolutionary perspective, the evolutionary transitions from a solitary lifestyle to group living have resulted in several new health-related costs and benefits of sociality. Social transmission of parasites within groups represents a major cost of group living, but some behavioural mechanisms, such as grooming, have evolved repeatedly to reduce this cost. Group living also has created novel costs in terms of altered susceptibility to infectious and non-infectious disease as a result of the unavoidable physiological consequences of social competition and integration, which are partly alleviated by social buffering in some vertebrates. Here, we define the relevant aspects of sociality, summarize their health-related costs and benefits, and discuss possible fitness measures in different study systems. Given the pervasive effects of social factors on health and fitness, we propose a synthesis of existing conceptual approaches in disease ecology, ecological immunology and behavioural neurosciences by adding sociality as a key factor, with the goal to generate a broader framework for organismal integration of health-related research.
AU - Kappeler, Peter
AU - Cremer, Sylvia
AU - Nunn, Charles
ID - 1831
IS - 1669
JF - Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences
TI - Sociality and health: Impacts of sociality on disease susceptibility and transmission in animal and human societies
VL - 370
ER -
TY - JOUR
AB - Linearizability of concurrent data structures is usually proved by monolithic simulation arguments relying on the identification of the so-called linearization points. Regrettably, such proofs, whether manual or automatic, are often complicated and scale poorly to advanced non-blocking concurrency patterns, such as helping and optimistic updates. In response, we propose a more modular way of checking linearizability of concurrent queue algorithms that does not involve identifying linearization points. We reduce the task of proving linearizability with respect to the queue specification to establishing four basic properties, each of which can be proved independently by simpler arguments. As a demonstration of our approach, we verify the Herlihy and Wing queue, an algorithm that is challenging to verify by a simulation proof.
AU - Chakraborty, Soham
AU - Henzinger, Thomas A
AU - Sezgin, Ali
AU - Vafeiadis, Viktor
ID - 1832
IS - 1
JF - Logical Methods in Computer Science
TI - Aspect-oriented linearizability proofs
VL - 11
ER -
TY - JOUR
AB - Huge body of evidences demonstrated that volatile anesthetics affect the hippocampal neurogenesis and neurocognitive functions, and most of them showed impairment at anesthetic dose. Here, we investigated the effect of low dose (1.8%) sevoflurane on hippocampal neurogenesis and dentate gyrus-dependent learning. Neonatal rats at postnatal day 4 to 6 (P4-6) were treated with 1.8% sevoflurane for 6 hours. Neurogenesis was quantified by bromodeoxyuridine labeling and electrophysiology recording. Four and seven weeks after treatment, the Morris water maze and contextual-fear discrimination learning tests were performed to determine the influence on spatial learning and pattern separation. A 6-hour treatment with 1.8% sevoflurane promoted hippocampal neurogenesis and increased the survival of newborn cells and the proportion of immature granular cells in the dentate gyrus of neonatal rats. Sevoflurane-treated rats performed better during the training days of the Morris water maze test and in contextual-fear discrimination learning test. These results suggest that a subanesthetic dose of sevoflurane promotes hippocampal neurogenesis in neonatal rats and facilitates their performance in dentate gyrus-dependent learning tasks.
AU - Chen, Chong
AU - Wang, Chao
AU - Zhao, Xuan
AU - Zhou, Tao
AU - Xu, Dao
AU - Wang, Zhi
AU - Wang, Ying
ID - 1834
IS - 2
JF - ASN Neuro
TI - Low-dose sevoflurane promoteshippocampal neurogenesis and facilitates the development of dentate gyrus-dependent learning in neonatal rats
VL - 7
ER -
TY - CONF
AB - The behaviour of gene regulatory networks (GRNs) is typically analysed using simulation-based statistical testing-like methods. In this paper, we demonstrate that we can replace this approach by a formal verification-like method that gives higher assurance and scalability. We focus on Wagner’s weighted GRN model with varying weights, which is used in evolutionary biology. In the model, weight parameters represent the gene interaction strength that may change due to genetic mutations. For a property of interest, we synthesise the constraints over the parameter space that represent the set of GRNs satisfying the property. We experimentally show that our parameter synthesis procedure computes the mutational robustness of GRNs –an important problem of interest in evolutionary biology– more efficiently than the classical simulation method. We specify the property in linear temporal logics. We employ symbolic bounded model checking and SMT solving to compute the space of GRNs that satisfy the property, which amounts to synthesizing a set of linear constraints on the weights.
AU - Giacobbe, Mirco
AU - Guet, Calin C
AU - Gupta, Ashutosh
AU - Henzinger, Thomas A
AU - Paixao, Tiago
AU - Petrov, Tatjana
ID - 1835
TI - Model checking gene regulatory networks
VL - 9035
ER -
TY - JOUR
AB - Transition to turbulence in straight pipes occurs in spite of the linear stability of the laminar Hagen-Poiseuille flow if both the amplitude of flow perturbations and the Reynolds number Re exceed a minimum threshold (subcritical transition). As the pipe curvature increases, centrifugal effects become important, modifying the basic flow as well as the most unstable linear modes. If the curvature (tube-to-coiling diameter d/D) is sufficiently large, a Hopf bifurcation (supercritical instability) is encountered before turbulence can be excited (subcritical instability). We trace the instability thresholds in the Re - d/D parameter space in the range 0.01 ≤ d/D\ ≤ 0.1 by means of laser-Doppler velocimetry and determine the point where the subcritical and supercritical instabilities meet. Two different experimental set-ups are used: a closed system where the pipe forms an axisymmetric torus and an open system employing a helical pipe. Implications for the measurement of friction factors in curved pipes are discussed.
AU - Kühnen, Jakob
AU - Braunshier, P
AU - Schwegel, M
AU - Kuhlmann, Hendrik
AU - Hof, Björn
ID - 1837
IS - 5
JF - Journal of Fluid Mechanics
TI - Subcritical versus supercritical transition to turbulence in curved pipes
VL - 770
ER -
TY - CONF
AB - Synthesis of program parts is particularly useful for concurrent systems. However, most approaches do not support common design tasks, like modifying a single process without having to re-synthesize or verify the whole system. Assume-guarantee synthesis (AGS) provides robustness against modifications of system parts, but thus far has been limited to the perfect information setting. This means that local variables cannot be hidden from other processes, which renders synthesis results cumbersome or even impossible to realize.We resolve this shortcoming by defining AGS under partial information. We analyze the complexity and decidability in different settings, showing that the problem has a high worstcase complexity and is undecidable in many interesting cases. Based on these observations, we present a pragmatic algorithm based on bounded synthesis, and demonstrate its practical applicability on several examples.
AU - Bloem, Roderick
AU - Chatterjee, Krishnendu
AU - Jacobs, Swen
AU - Könighofer, Robert
ID - 1838
TI - Assume-guarantee synthesis for concurrent reactive programs with partial information
VL - 9035
ER -
TY - CONF
AB - We present MultiGain, a tool to synthesize strategies for Markov decision processes (MDPs) with multiple mean-payoff objectives. Our models are described in PRISM, and our tool uses the existing interface and simulator of PRISM. Our tool extends PRISM by adding novel algorithms for multiple mean-payoff objectives, and also provides features such as (i) generating strategies and exploring them for simulation, and checking them with respect to other properties; and (ii) generating an approximate Pareto curve for two mean-payoff objectives. In addition, we present a new practical algorithm for the analysis of MDPs with multiple mean-payoff objectives under memoryless strategies.
AU - Brázdil, Tomáš
AU - Chatterjee, Krishnendu
AU - Forejt, Vojtěch
AU - Kučera, Antonín
ID - 1839
TI - Multigain: A controller synthesis tool for MDPs with multiple mean-payoff objectives
VL - 9035
ER -
TY - JOUR
AB - In this paper, we present a method for reducing a regular, discrete-time Markov chain (DTMC) to another DTMC with a given, typically much smaller number of states. The cost of reduction is defined as the Kullback-Leibler divergence rate between a projection of the original process through a partition function and a DTMC on the correspondingly partitioned state space. Finding the reduced model with minimal cost is computationally expensive, as it requires an exhaustive search among all state space partitions, and an exact evaluation of the reduction cost for each candidate partition. Our approach deals with the latter problem by minimizing an upper bound on the reduction cost instead of minimizing the exact cost. The proposed upper bound is easy to compute and it is tight if the original chain is lumpable with respect to the partition. Then, we express the problem in the form of information bottleneck optimization, and propose using the agglomerative information bottleneck algorithm for searching a suboptimal partition greedily, rather than exhaustively. The theory is illustrated with examples and one application scenario in the context of modeling bio-molecular interactions.
AU - Geiger, Bernhard
AU - Petrov, Tatjana
AU - Kubin, Gernot
AU - Koeppl, Heinz
ID - 1840
IS - 4
JF - IEEE Transactions on Automatic Control
SN - 0018-9286
TI - Optimal Kullback-Leibler aggregation via information bottleneck
VL - 60
ER -
TY - JOUR
AB - We propose a new family of message passing techniques for MAP estimation in graphical models which we call Sequential Reweighted Message Passing (SRMP). Special cases include well-known techniques such as Min-Sum Diffusion (MSD) and a faster Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation is simpler than the original derivation of TRW-S, and does not involve a decomposition into trees. This allows easy generalizations. The new family of algorithms can be viewed as a generalization of TRW-S from pairwise to higher-order graphical models. We test SRMP on several real-world problems with promising results.
AU - Kolmogorov, Vladimir
ID - 1841
IS - 5
JF - IEEE Transactions on Pattern Analysis and Machine Intelligence
TI - A new look at reweighted message passing
VL - 37
ER -
TY - JOUR
AB - Based on extrapolation from excitatory synapses, it is often assumed that depletion of the releasable pool of synaptic vesicles is the main factor underlying depression at inhibitory synapses. In this issue of Neuron, using subcellular patch-clamp recording from inhibitory presynaptic terminals, Kawaguchi and Sakaba (2015) show that at Purkinje cell-deep cerebellar nuclei neuron synapses, changes in presynaptic action potential waveform substantially contribute to synaptic depression. Based on extrapolation from excitatory synapses, it is often assumed that depletion of the releasable pool of synaptic vesicles is the main factor underlying depression at inhibitory synapses. In this issue of Neuron, using subcellular patch-clamp recording from inhibitory presynaptic terminals, Kawaguchi and Sakaba (2015) show that at Purkinje cell-deep cerebellar nuclei neuron synapses, changes in presynaptic action potential waveform substantially contribute to synaptic depression.
AU - Vandael, David H
AU - Espinoza Martinez, Claudia M
AU - Jonas, Peter M
ID - 1845
IS - 6
JF - Neuron
TI - Excitement about inhibitory presynaptic terminals
VL - 85
ER -
TY - JOUR
AB - Modal transition systems (MTS) is a well-studied specification formalism of reactive systems supporting a step-wise refinement methodology. Despite its many advantages, the formalism as well as its currently known extensions are incapable of expressing some practically needed aspects in the refinement process like exclusive, conditional and persistent choices. We introduce a new model called parametric modal transition systems (PMTS) together with a general modal refinement notion that overcomes many of the limitations. We investigate the computational complexity of modal and thorough refinement checking on PMTS and its subclasses and provide a direct encoding of the modal refinement problem into quantified Boolean formulae, allowing us to employ state-of-the-art QBF solvers for modal refinement checking. The experiments we report on show that the feasibility of refinement checking is more influenced by the degree of nondeterminism rather than by the syntactic restrictions on the types of formulae allowed in the description of the PMTS.
AU - Beneš, Nikola
AU - Kretinsky, Jan
AU - Larsen, Kim
AU - Möller, Mikael
AU - Sickert, Salomon
AU - Srba, Jiří
ID - 1846
IS - 2-3
JF - Acta Informatica
TI - Refinement checking on parametric modal transition systems
VL - 52
ER -
TY - JOUR
AB - The ability to escape apoptosis is a hallmark of cancer-initiating cells and a key factor of resistance to oncolytic therapy. Here, we identify FAM96A as a ubiquitous, evolutionarily conserved apoptosome-activating protein and investigate its potential pro-apoptotic tumor suppressor function in gastrointestinal stromal tumors (GISTs). Interaction between FAM96A and apoptotic peptidase activating factor 1 (APAF1) was identified in yeast two-hybrid screen and further studied by deletion mutants, glutathione-S-transferase pull-down, co-immunoprecipitation and immunofluorescence. Effects of FAM96A overexpression and knock-down on apoptosis sensitivity were examined in cancer cells and zebrafish embryos. Expression of FAM96A in GISTs and histogenetically related cells including interstitial cells of Cajal (ICCs), “fibroblast-like cells” (FLCs) and ICC stem cells (ICC-SCs) was investigated by Northern blotting, reverse transcription—polymerase chain reaction, immunohistochemistry and Western immunoblotting. Tumorigenicity of GIST cells and transformed murine ICC-SCs stably transduced to re-express FAM96A was studied by xeno- and allografting into immunocompromised mice. FAM96A was found to bind APAF1 and to enhance the induction of mitochondrial apoptosis. FAM96A protein or mRNA was dramatically reduced or lost in 106 of 108 GIST samples representing three independent patient cohorts. Whereas ICCs, ICC-SCs and FLCs, the presumed normal counterparts of GIST, were found to robustly express FAM96A protein and mRNA, FAM96A expression was much reduced in tumorigenic ICC-SCs. Re-expression of FAM96A in GIST cells and transformed ICC-SCs increased apoptosis sensitivity and diminished tumorigenicity. Our data suggest FAM96A is a novel pro-apoptotic tumor suppressor that is lost during GIST tumorigenesis.
AU - Schwamb, Bettina
AU - Pick, Robert
AU - Fernández, Sara
AU - Völp, Kirsten
AU - Heering, Jan
AU - Dötsch, Volker
AU - Bösser, Susanne
AU - Jung, Jennifer
AU - Beinoravičiute Kellner, Rasa
AU - Wesely, Josephine
AU - Zörnig, Inka
AU - Hammerschmidt, Matthias
AU - Nowak, Matthias
AU - Penzel, Roland
AU - Zatloukal, Kurt
AU - Joos, Stefan
AU - Rieker, Ralf
AU - Agaimy, Abbas
AU - Söder, Stephan
AU - Reid Lombardo, Kmarie
AU - Kendrick, Michael
AU - Bardsley, Michael
AU - Hayashi, Yujiro
AU - Asuzu, David
AU - Syed, Sabriya
AU - Ördög, Tamás
AU - Zörnig, Martin
ID - 1848
IS - 6
JF - International Journal of Cancer
TI - FAM96A is a novel pro-apoptotic tumor suppressor in gastrointestinal stromal tumors
VL - 137
ER -
TY - JOUR
AB - Entomopathogenic fungi are potent biocontrol agents that are widely used against insect pests, many of which are social insects. Nevertheless, theoretical investigations of their particular life history are scarce. We develop a model that takes into account the main distinguishing features between traditionally studied diseases and obligate killing pathogens, like the (biocontrol-relevant) insect-pathogenic fungi Metarhizium and Beauveria. First, obligate killing entomopathogenic fungi produce new infectious particles (conidiospores) only after host death and not yet on the living host. Second, the killing rates of entomopathogenic fungi depend strongly on the initial exposure dosage, thus we explicitly consider the pathogen load of individual hosts. Further, we make the model applicable not only to solitary host species, but also to group living species by incorporating social interactions between hosts, like the collective disease defences of insect societies. Our results identify the optimal killing rate for the pathogen that minimises its invasion threshold. Furthermore, we find that the rate of contact between hosts has an ambivalent effect: dense interaction networks between individuals are considered to facilitate disease outbreaks because of increased pathogen transmission. In social insects, this is compensated by their collective disease defences, i.e., social immunity. For the type of pathogens considered here, we show that even without social immunity, high contact rates between live individuals dilute the pathogen in the host colony and hence can reduce individual pathogen loads below disease-causing levels.
AU - Novak, Sebastian
AU - Cremer, Sylvia
ID - 1850
IS - 5
JF - Journal of Theoretical Biology
TI - Fungal disease dynamics in insect societies: Optimal killing rates and the ambivalent effect of high social interaction rates
VL - 372
ER -
TY - JOUR
AB - We consider mating strategies for females who search for males sequentially during a season of limited length. We show that the best strategy rejects a given male type if encountered before a time-threshold but accepts him after. For frequency-independent benefits, we obtain the optimal time-thresholds explicitly for both discrete and continuous distributions of males, and allow for mistakes being made in assessing the correct male type. When the benefits are indirect (genes for the offspring) and the population is under frequency-dependent ecological selection, the benefits depend on the mating strategy of other females as well. This case is particularly relevant to speciation models that seek to explore the stability of reproductive isolation by assortative mating under frequency-dependent ecological selection. We show that the indirect benefits are to be quantified by the reproductive values of couples, and describe how the evolutionarily stable time-thresholds can be found. We conclude with an example based on the Levene model, in which we analyze the evolutionarily stable assortative mating strategies and the strength of reproductive isolation provided by them.
AU - Priklopil, Tadeas
AU - Kisdi, Eva
AU - Gyllenberg, Mats
ID - 1851
IS - 4
JF - Evolution
TI - Evolutionarily stable mating decisions for sequentially searching females and the stability of reproductive isolation by assortative mating
VL - 69
ER -
TY - JOUR
AB - Summary: Declining populations of bee pollinators are a cause of concern, with major repercussions for biodiversity loss and food security. RNA viruses associated with honeybees represent a potential threat to other insect pollinators, but the extent of this threat is poorly understood. This study aims to attain a detailed understanding of the current and ongoing risk of emerging infectious disease (EID) transmission between managed and wild pollinator species across a wide range of RNA viruses. Within a structured large-scale national survey across 26 independent sites, we quantify the prevalence and pathogen loads of multiple RNA viruses in co-occurring managed honeybee (Apis mellifera) and wild bumblebee (Bombus spp.) populations. We then construct models that compare virus prevalence between wild and managed pollinators. Multiple RNA viruses associated with honeybees are widespread in sympatric wild bumblebee populations. Virus prevalence in honeybees is a significant predictor of virus prevalence in bumblebees, but we remain cautious in speculating over the principle direction of pathogen transmission. We demonstrate species-specific differences in prevalence, indicating significant variation in disease susceptibility or tolerance. Pathogen loads within individual bumblebees may be high and in the case of at least one RNA virus, prevalence is higher in wild bumblebees than in managed honeybee populations. Our findings indicate widespread transmission of RNA viruses between managed and wild bee pollinators, pointing to an interconnected network of potential disease pressures within and among pollinator species. In the context of the biodiversity crisis, our study emphasizes the importance of targeting a wide range of pathogens and defining host associations when considering potential drivers of population decline.
AU - Mcmahon, Dino
AU - Fürst, Matthias
AU - Caspar, Jesicca
AU - Theodorou, Panagiotis
AU - Brown, Mark
AU - Paxton, Robert
ID - 1855
IS - 3
JF - Journal of Animal Ecology
TI - A sting in the spit: Widespread cross-infection of multiple RNA viruses across wild and managed bees
VL - 84
ER -
TY - JOUR
AB - The traditional synthesis question given a specification asks for the automatic construction of a system that satisfies the specification, whereas often there exists a preference order among the different systems that satisfy the given specification. Under a probabilistic assumption about the possible inputs, such a preference order is naturally expressed by a weighted automaton, which assigns to each word a value, such that a system is preferred if it generates a higher expected value. We solve the following optimal synthesis problem: given an omega-regular specification, a Markov chain that describes the distribution of inputs, and a weighted automaton that measures how well a system satisfies the given specification under the input assumption, synthesize a system that optimizes the measured value. For safety specifications and quantitative measures that are defined by mean-payoff automata, the optimal synthesis problem reduces to finding a strategy in a Markov decision process (MDP) that is optimal for a long-run average reward objective, which can be achieved in polynomial time. For general omega-regular specifications along with mean-payoff automata, the solution rests on a new, polynomial-time algorithm for computing optimal strategies in MDPs with mean-payoff parity objectives. Our algorithm constructs optimal strategies that consist of two memoryless strategies and a counter. The counter is in general not bounded. To obtain a finite-state system, we show how to construct an ε-optimal strategy with a bounded counter, for all ε > 0. Furthermore, we show how to decide in polynomial time if it is possible to construct an optimal finite-state system (i.e., a system without a counter) for a given specification. We have implemented our approach and the underlying algorithms in a tool that takes qualitative and quantitative specifications and automatically constructs a system that satisfies the qualitative specification and optimizes the quantitative specification, if such a system exists. We present some experimental results showing optimal systems that were automatically generated in this way.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Jobstmann, Barbara
AU - Singh, Rohit
ID - 1856
IS - 1
JF - Journal of the ACM
TI - Measuring and synthesizing systems in probabilistic environments
VL - 62
ER -
TY - CONF
AB - Sharing information between multiple tasks enables algorithms to achieve good generalization performance even from small amounts of training data. However, in a realistic scenario of multi-task learning not all tasks are equally related to each other, hence it could be advantageous to transfer information only between the most related tasks. In this work we propose an approach that processes multiple tasks in a sequence with sharing between subsequent tasks instead of solving all tasks jointly. Subsequently, we address the question of curriculum learning of tasks, i.e. finding the best order of tasks to be learned. Our approach is based on a generalization bound criterion for choosing the task order that optimizes the average expected classification performance over all tasks. Our experimental results show that learning multiple related tasks sequentially can be more effective than learning them jointly, the order in which tasks are being solved affects the overall performance, and that our model is able to automatically discover the favourable order of tasks.
AU - Pentina, Anastasia
AU - Sharmanska, Viktoriia
AU - Lampert, Christoph
ID - 1857
TI - Curriculum learning of multiple tasks
ER -
TY - CONF
AB - We study the problem of predicting the future, though only in the probabilistic sense of estimating a future state of a time-varying probability distribution. This is not only an interesting academic problem, but solving this extrapolation problem also has many practical application, e.g. for training classifiers that have to operate under time-varying conditions. Our main contribution is a method for predicting the next step of the time-varying distribution from a given sequence of sample sets from earlier time steps. For this we rely on two recent machine learning techniques: embedding probability distributions into a reproducing kernel Hilbert space, and learning operators by vector-valued regression. We illustrate the working principles and the practical usefulness of our method by experiments on synthetic and real data. We also highlight an exemplary application: training a classifier in a domain adaptation setting without having access to examples from the test time distribution at training time.
AU - Lampert, Christoph
ID - 1858
TI - Predicting the future behavior of a time-varying probability distribution
ER -
TY - CONF
AB - Structural support vector machines (SSVMs) are amongst the best performing models for structured computer vision tasks, such as semantic image segmentation or human pose estimation. Training SSVMs, however, is computationally costly, because it requires repeated calls to a structured prediction subroutine (called \emph{max-oracle}), which has to solve an optimization problem itself, e.g. a graph cut.
In this work, we introduce a new algorithm for SSVM training that is more efficient than earlier techniques when the max-oracle is computationally expensive, as it is frequently the case in computer vision tasks. The main idea is to (i) combine the recent stochastic Block-Coordinate Frank-Wolfe algorithm with efficient hyperplane caching, and (ii) use an automatic selection rule for deciding whether to call the exact max-oracle or to rely on an approximate one based on the cached hyperplanes.
We show experimentally that this strategy leads to faster convergence to the optimum with respect to the number of requires oracle calls, and that this translates into faster convergence with respect to the total runtime when the max-oracle is slow compared to the other steps of the algorithm.
AU - Shah, Neel
AU - Kolmogorov, Vladimir
AU - Lampert, Christoph
ID - 1859
TI - A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle
ER -
TY - CONF
AB - Classifiers for object categorization are usually evaluated by their accuracy on a set of i.i.d. test examples. This provides us with an estimate of the expected error when applying the classifiers to a single new image. In real application, however, classifiers are rarely only used for a single image and then discarded. Instead, they are applied sequentially to many images, and these are typically not i.i.d. samples from a fixed data distribution, but they carry dependencies and their class distribution varies over time. In this work, we argue that the phenomenon of correlated data at prediction time is not a nuisance, but a blessing in disguise. We describe a probabilistic method for adapting classifiers at prediction time without having to retrain them. We also introduce a framework for creating realistically distributed image sequences, which offers a way to benchmark classifier adaptation methods, such as the one we propose. Experiments on the ILSVRC2010 and ILSVRC2012 datasets show that adapting object classification systems at prediction time can significantly reduce their error rate, even with no additional human feedback.
AU - Royer, Amélie
AU - Lampert, Christoph
ID - 1860
TI - Classifier adaptation at prediction time
ER -
TY - JOUR
AB - The Altshuler–Shklovskii formulas (Altshuler and Shklovskii, BZh Eksp Teor Fiz 91:200, 1986) predict, for any disordered quantum system in the diffusive regime, a universal power law behaviour for the correlation functions of the mesoscopic eigenvalue density. In this paper and its companion (Erdős and Knowles, The Altshuler–Shklovskii formulas for random band matrices I: the unimodular case, 2013), we prove these formulas for random band matrices. In (Erdős and Knowles, The Altshuler–Shklovskii formulas for random band matrices I: the unimodular case, 2013) we introduced a diagrammatic approach and presented robust estimates on general diagrams under certain simplifying assumptions. In this paper, we remove these assumptions by giving a general estimate of the subleading diagrams. We also give a precise analysis of the leading diagrams which give rise to the Altschuler–Shklovskii power laws. Moreover, we introduce a family of general random band matrices which interpolates between real symmetric (β = 1) and complex Hermitian (β = 2) models, and track the transition for the mesoscopic density–density correlation. Finally, we address the higher-order correlation functions by proving that they behave asymptotically according to a Gaussian process whose covariance is given by the Altshuler–Shklovskii formulas.
AU - Erdös, László
AU - Knowles, Antti
ID - 1864
IS - 3
JF - Annales Henri Poincare
TI - The Altshuler–Shklovskii formulas for random band matrices II: The general case
VL - 16
ER -
TY - JOUR
AB - The plant hormone auxin is a key regulator of plant growth and development. Differences in auxin distribution within tissues are mediated by the polar auxin transport machinery, and cellular auxin responses occur depending on changes in cellular auxin levels. Multiple receptor systems at the cell surface and in the interior operate to sense and interpret fluctuations in auxin distribution that occur during plant development. Until now, three proteins or protein complexes that can bind auxin have been identified. SCFTIR1 [a SKP1-cullin-1-F-box complex that contains transport inhibitor response 1 (TIR1) as the F-box protein] and S-phase-kinaseassociated protein 2 (SKP2) localize to the nucleus, whereas auxinbinding protein 1 (ABP1), predominantly associates with the endoplasmic reticulum and cell surface. In this Cell Science at a Glance article, we summarize recent discoveries in the field of auxin transport and signaling that have led to the identification of new components of these pathways, as well as their mutual interaction.
AU - Grones, Peter
AU - Friml, Jirí
ID - 1871
IS - 1
JF - Journal of Cell Science
TI - Auxin transporters and binding proteins at a glance
VL - 128
ER -
TY - JOUR
AB - We consider partially observable Markov decision processes (POMDPs) with limit-average payoff, where a reward value in the interval [0,1] is associated with every transition, and the payoff of an infinite path is the long-run average of the rewards. We consider two types of path constraints: (i) a quantitative constraint defines the set of paths where the payoff is at least a given threshold λ1ε(0,1]; and (ii) a qualitative constraint which is a special case of the quantitative constraint with λ1=1. We consider the computation of the almost-sure winning set, where the controller needs to ensure that the path constraint is satisfied with probability 1. Our main results for qualitative path constraints are as follows: (i) the problem of deciding the existence of a finite-memory controller is EXPTIME-complete; and (ii) the problem of deciding the existence of an infinite-memory controller is undecidable. For quantitative path constraints we show that the problem of deciding the existence of a finite-memory controller is undecidable. We also present a prototype implementation of our EXPTIME algorithm and experimental results on several examples.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
ID - 1873
JF - Artificial Intelligence
TI - POMDPs under probabilistic semantics
VL - 221
ER -
TY - JOUR
AB - When electron microscopy (EM) was introduced in the 1930s it gave scientists their first look into the nanoworld of cells. Over the last 80 years EM has vastly increased our understanding of the complex cellular structures that underlie the diverse functions that cells need to maintain life. One drawback that has been difficult to overcome was the inherent lack of volume information, mainly due to the limit on the thickness of sections that could be viewed in a transmission electron microscope (TEM). For many years scientists struggled to achieve three-dimensional (3D) EM using serial section reconstructions, TEM tomography, and scanning EM (SEM) techniques such as freeze-fracture. Although each technique yielded some special information, they required a significant amount of time and specialist expertise to obtain even a very small 3D EM dataset. Almost 20 years ago scientists began to exploit SEMs to image blocks of embedded tissues and perform serial sectioning of these tissues inside the SEM chamber. Using first focused ion beams (FIB) and subsequently robotic ultramicrotomes (serial block-face, SBF-SEM) microscopists were able to collect large volumes of 3D EM information at resolutions that could address many important biological questions, and do so in an efficient manner. We present here some examples of 3D EM taken from the many diverse specimens that have been imaged in our core facility. We propose that the next major step forward will be to efficiently correlate functional information obtained using light microscopy (LM) with 3D EM datasets to more completely investigate the important links between cell structures and their functions.
AU - Kremer, A
AU - Lippens, Stefaan
AU - Bartunkova, Sonia
AU - Asselbergh, Bob
AU - Blanpain, Cendric
AU - Fendrych, Matyas
AU - Goossens, A
AU - Holt, Matthew
AU - Janssens, Sophie
AU - Krols, Michiel
AU - Larsimont, Jean
AU - Mc Guire, Conor
AU - Nowack, Moritz
AU - Saelens, Xavier
AU - Schertel, Andreas
AU - Schepens, B
AU - Slezak, M
AU - Timmerman, Vincent
AU - Theunis, Clara
AU - Van Brempt, Ronald
AU - Visser, Y
AU - Guérin, Christophe
ID - 1879
IS - 2
JF - Journal of Microscopy
TI - Developing 3D SEM in a broad biological context
VL - 259
ER -
TY - JOUR
AB - We investigate the relation between Bose-Einstein condensation (BEC) and superfluidity in the ground state of a one-dimensional model of interacting bosons in a strong random potential. We prove rigorously that in a certain parameter regime the superfluid fraction can be arbitrarily small while complete BEC prevails. In another regime there is both complete BEC and complete superfluidity, despite the strong disorder
AU - Könenberg, Martin
AU - Moser, Thomas
AU - Seiringer, Robert
AU - Yngvason, Jakob
ID - 1880
JF - New Journal of Physics
TI - Superfluid behavior of a Bose-Einstein condensate in a random potential
VL - 17
ER -
TY - CONF
AB - We provide a framework for compositional and iterative design and verification of systems with quantitative information, such as rewards, time or energy. It is based on disjunctive modal transition systems where we allow actions to bear various types of quantitative information. Throughout the design process the actions can be further refined and the information made more precise. We show how to compute the results of standard operations on the systems, including the quotient (residual), which has not been previously considered for quantitative non-deterministic systems. Our quantitative framework has close connections to the modal nu-calculus and is compositional with respect to general notions of distances between systems and the standard operations.
AU - Fahrenberg, Uli
AU - Kretinsky, Jan
AU - Legay, Axel
AU - Traonouez, Louis
ID - 1882
TI - Compositionality for quantitative specifications
VL - 8997
ER -
TY - JOUR
AB - We introduce a one-parametric family of tree growth models, in which branching probabilities decrease with branch age τ as τ-α. Depending on the exponent α, the scaling of tree depth with tree size n displays a transition between the logarithmic scaling of random trees and an algebraic growth. At the transition (α=1) tree depth grows as (logn)2. This anomalous scaling is in good agreement with the trend observed in evolution of biological species, thus providing a theoretical support for age-dependent speciation and associating it to the occurrence of a critical point.
AU - Keller-Schmidt, Stephanie
AU - Tugrul, Murat
AU - Eguíluz, Víctor
AU - Hernandez Garcia, Emilio
AU - Klemm, Konstantin
ID - 1883
IS - 2
JF - Physical Review E Statistical Nonlinear and Soft Matter Physics
TI - Anomalous scaling in an age-dependent branching model
VL - 91
ER -
TY - JOUR
AB - The concept of positional information is central to our understanding of how cells determine their location in a multicellular structure and thereby their developmental fates. Nevertheless, positional information has neither been defined mathematically nor quantified in a principled way. Here we provide an information-theoretic definition in the context of developmental gene expression patterns and examine the features of expression patterns that affect positional information quantitatively. We connect positional information with the concept of positional error and develop tools to directly measure information and error from experimental data. We illustrate our framework for the case of gap gene expression patterns in the early Drosophila embryo and show how information that is distributed among only four genes is sufficient to determine developmental fates with nearly single-cell resolution. Our approach can be generalized to a variety of different model systems; procedures and examples are discussed in detail.
AU - Tkacik, Gasper
AU - Dubuis, Julien
AU - Petkova, Mariela
AU - Gregor, Thomas
ID - 1885
IS - 1
JF - Genetics
TI - Positional information, positional error, and readout precision in morphogenesis: A mathematical framework
VL - 199
ER -
TY - JOUR
AB - We typically think of cells as responding to external signals independently by regulating their gene expression levels, yet they often locally exchange information and coordinate. Can such spatial coupling be of benefit for conveying signals subject to gene regulatory noise? Here we extend our information-theoretic framework for gene regulation to spatially extended systems. As an example, we consider a lattice of nuclei responding to a concentration field of a transcriptional regulator (the "input") by expressing a single diffusible target gene. When input concentrations are low, diffusive coupling markedly improves information transmission; optimal gene activation functions also systematically change. A qualitatively new regulatory strategy emerges where individual cells respond to the input in a nearly step-like fashion that is subsequently averaged out by strong diffusion. While motivated by early patterning events in the Drosophila embryo, our framework is generically applicable to spatially coupled stochastic gene expression models.
AU - Sokolowski, Thomas R
AU - Tkacik, Gasper
ID - 1940
IS - 6
JF - Physical Review E Statistical Nonlinear and Soft Matter Physics
TI - Optimizing information flow in small genetic networks. IV. Spatial coupling
VL - 91
ER -
TY - CONF
AB - We present a method and a tool for generating succinct representations of sets of concurrent traces. We focus on trace sets that contain all correct or all incorrect permutations of events from a given trace. We represent trace sets as HB-Formulas that are Boolean combinations of happens-before constraints between events. To generate a representation of incorrect interleavings, our method iteratively explores interleavings that violate the specification and gathers generalizations of the discovered interleavings into an HB-Formula; its complement yields a representation of correct interleavings.
We claim that our trace set representations can drive diverse verification, fault localization, repair, and synthesis techniques for concurrent programs. We demonstrate this by using our tool in three case studies involving synchronization synthesis, bug summarization, and abstraction refinement based verification. In each case study, our initial experimental results have been promising.
In the first case study, we present an algorithm for inferring missing synchronization from an HB-Formula representing correct interleavings of a given trace. The algorithm applies rules to rewrite specific patterns in the HB-Formula into locks, barriers, and wait-notify constructs. In the second case study, we use an HB-Formula representing incorrect interleavings for bug summarization. While the HB-Formula itself is a concise counterexample summary, we present additional inference rules to help identify specific concurrency bugs such as data races, define-use order violations, and two-stage access bugs. In the final case study, we present a novel predicate learning procedure that uses HB-Formulas representing abstract counterexamples to accelerate counterexample-guided abstraction refinement (CEGAR). In each iteration of the CEGAR loop, the procedure refines the abstraction to eliminate multiple spurious abstract counterexamples drawn from the HB-Formula.
AU - Gupta, Ashutosh
AU - Henzinger, Thomas A
AU - Radhakrishna, Arjun
AU - Samanta, Roopsha
AU - Tarrach, Thorsten
ID - 1992
SN - 978-1-4503-3300-9
TI - Succinct representation of concurrent trace sets
ER -
TY - JOUR
AB - The fitness effects of symbionts on their hosts can be context-dependent, with usually benign symbionts causing detrimental effects when their hosts are stressed, or typically parasitic symbionts providing protection towards their hosts (e.g. against pathogen infection). Here, we studied the novel association between the invasive garden ant Lasius neglectus and its fungal ectosymbiont Laboulbenia formicarum for potential costs and benefits. We tested ants with different Laboulbenia levels for their survival and immunity under resource limitation and exposure to the obligate killing entomopathogen Metarhizium brunneum. While survival of L. neglectus workers under starvation was significantly decreased with increasing Laboulbenia levels, host survival under Metarhizium exposure increased with higher levels of the ectosymbiont, suggesting a symbiont-mediated anti-pathogen protection, which seems to be driven mechanistically by both improved sanitary behaviours and an upregulated immune system. Ants with high Laboulbenia levels showed significantly longer self-grooming and elevated expression of immune genes relevant for wound repair and antifungal responses (β-1,3-glucan binding protein, Prophenoloxidase), compared with ants carrying low Laboulbenia levels. This suggests that the ectosymbiont Laboulbenia formicarum weakens its ant host by either direct resource exploitation or the costs of an upregulated behavioural and immunological response, which, however, provides a prophylactic protection upon later exposure to pathogens.
AU - Konrad, Matthias
AU - Grasse, Anna V
AU - Tragust, Simon
AU - Cremer, Sylvia
ID - 1993
IS - 1799
JF - Proceedings of the Royal Society of London Series B Biological Sciences
TI - Anti-pathogen protection versus survival costs mediated by an ectosymbiont in an ant host
VL - 282
ER -
TY - JOUR
AB - We prove that the three-state toric homogeneous Markov chain model has Markov degree two. In algebraic terminology this means, that a certain class of toric ideals is generated by quadratic binomials. This was conjectured by Haws, Martin del Campo, Takemura and Yoshida, who proved that they are generated by degree six binomials.
AU - Noren, Patrik
ID - 1997
IS - May-June
JF - Journal of Symbolic Computation
TI - The three-state toric homogeneous Markov chain model has Markov degree two
VL - 68/Part 2
ER -
TY - JOUR
AB - The monotone secant conjecture posits a rich class of polynomial systems, all of whose solutions are real. These systems come from the Schubert calculus on flag manifolds, and the monotone secant conjecture is a compelling generalization of the Shapiro conjecture for Grassmannians (Theorem of Mukhin, Tarasov, and Varchenko). We present some theoretical evidence for this conjecture, as well as computational evidence obtained by 1.9 teraHertz-years of computing, and we discuss some of the phenomena we observed in our data.
AU - Hein, Nicolas
AU - Hillar, Christopher
AU - Martin Del Campo Sanchez, Abraham
AU - Sottile, Frank
AU - Teitler, Zach
ID - 2006
IS - 3
JF - Experimental Mathematics
TI - The monotone secant conjecture in the real Schubert calculus
VL - 24
ER -
TY - JOUR
AB - The paper describes a generalized iterative proportional fitting procedure that can be used for maximum likelihood estimation in a special class of the general log-linear model. The models in this class, called relational, apply to multivariate discrete sample spaces that do not necessarily have a Cartesian product structure and may not contain an overall effect. When applied to the cell probabilities, the models without the overall effect are curved exponential families and the values of the sufficient statistics are reproduced by the MLE only up to a constant of proportionality. The paper shows that Iterative Proportional Fitting, Generalized Iterative Scaling, and Improved Iterative Scaling fail to work for such models. The algorithm proposed here is based on iterated Bregman projections. As a by-product, estimates of the multiplicative parameters are also obtained. An implementation of the algorithm is available as an R-package.
AU - Klimova, Anna
AU - Rudas, Tamás
ID - 2008
IS - 3
JF - Scandinavian Journal of Statistics
TI - Iterative scaling in curved exponential families
VL - 42
ER -
TY - JOUR
AB - The concepts of faithfulness and strong-faithfulness are important for statistical learning of graphical models. Graphs are not sufficient for describing the association structure of a discrete distribution. Hypergraphs representing hierarchical log-linear models are considered instead, and the concept of parametric (strong-) faithfulness with respect to a hypergraph is introduced. Strong-faithfulness ensures the existence of uniformly consistent parameter estimators and enables building uniformly consistent procedures for a hypergraph search. The strength of association in a discrete distribution can be quantified with various measures, leading to different concepts of strong-faithfulness. Lower and upper bounds for the proportions of distributions that do not satisfy strong-faithfulness are computed for different parameterizations and measures of association.
AU - Klimova, Anna
AU - Uhler, Caroline
AU - Rudas, Tamás
ID - 2014
IS - 7
JF - Computational Statistics & Data Analysis
TI - Faithfulness and learning hypergraphs from discrete distributions
VL - 87
ER -
TY - JOUR
AB - Small GTP-binding proteins of the Ras superfamily play diverse roles in intracellular trafficking. Among them, the Rab, Arf, and Rho families function in successive steps of vesicle transport, in forming vesicles from donor membranes, directing vesicle trafficking toward target membranes and docking vesicles onto target membranes. These proteins act as molecular switches that are controlled by a cycle of GTP binding and hydrolysis regulated by guanine nucleotide exchange factors (GEFs) and GTPase-activating proteins (GAPs). In this study we explored the role of GAPs in the regulation of the endocytic pathway using fluorescently labeled yeast mating pheromone α-factor. Among 25 non-essential GAP mutants, we found that deletion of the GLO3 gene, encoding Arf-GAP protein, caused defective internalization of fluorescently labeled α-factor. Quantitative analysis revealed that glo3Δ cells show defective α-factor binding to the cell surface. Interestingly, Ste2p, the α-factor receptor, was mis-localized from the plasma membrane to the vacuole in glo3Δ cells. Domain deletion mutants of Glo3p revealed that a GAP-independent function, as well as the GAP activity, of Glo3p is important for both α-factor binding and Ste2p localization at the cell surface. Additionally, we found that deletion of the GLO3 gene affects the size and number of Arf1p-residing Golgi compartments and causes a defect in transport from the TGN to the plasma membrane. Furthermore, we demonstrated that glo3Δ cells were defective in the late endosome-to-TGN transport pathway, but not in the early endosome-to-TGN transport pathway. These findings suggest novel roles for Arf-GAP Glo3p in endocytic recycling of cell surface proteins.
AU - Kawada, Daiki
AU - Kobayashi, Hiromu
AU - Tomita, Tsuyoshi
AU - Nakata, Eisuke
AU - Nagano, Makoto
AU - Siekhaus, Daria E
AU - Toshima, Junko
AU - Toshimaa, Jiro
ID - 2025
IS - 1
JF - Biochimica et Biophysica Acta - Molecular Cell Research
TI - The yeast Arf-GAP Glo3p is required for the endocytic recycling of cell surface proteins
VL - 1853
ER -
TY - JOUR
AB - A hybrid-parallel direct-numerical-simulation method with application to turbulent Taylor-Couette flow is presented. The Navier-Stokes equations are discretized in cylindrical coordinates with the spectral Fourier-Galerkin method in the axial and azimuthal directions, and high-order finite differences in the radial direction. Time is advanced by a second-order, semi-implicit projection scheme, which requires the solution of five Helmholtz/Poisson equations, avoids staggered grids and renders very small slip velocities. Nonlinear terms are evaluated with the pseudospectral method. The code is parallelized using a hybrid MPI-OpenMP strategy, which, compared with a flat MPI parallelization, is simpler to implement, allows to reduce inter-node communications and MPI overhead that become relevant at high processor-core counts, and helps to contain the memory footprint. A strong scaling study shows that the hybrid code maintains scalability up to more than 20,000 processor cores and thus allows to perform simulations at higher resolutions than previously feasible. In particular, it opens up the possibility to simulate turbulent Taylor-Couette flows at Reynolds numbers up to O(105). This enables to probe hydrodynamic turbulence in Keplerian flows in experimentally relevant regimes.
AU - Shi, Liang
AU - Rampp, Markus
AU - Hof, Björn
AU - Avila, Marc
ID - 2030
IS - 1
JF - Computers and Fluids
TI - A hybrid MPI-OpenMP parallel implementation for pseudospectral simulations with application to Taylor-Couette flow
VL - 106
ER -
TY - JOUR
AB - Opacity is a generic security property, that has been defined on (non-probabilistic) transition systems and later on Markov chains with labels. For a secret predicate, given as a subset of runs, and a function describing the view of an external observer, the value of interest for opacity is a measure of the set of runs disclosing the secret. We extend this definition to the richer framework of Markov decision processes, where non-deterministicchoice is combined with probabilistic transitions, and we study related decidability problems with partial or complete observation hypotheses for the schedulers. We prove that all questions are decidable with complete observation and ω-regular secrets. With partial observation, we prove that all quantitative questions are undecidable but the question whether a system is almost surely non-opaquebecomes decidable for a restricted class of ω-regular secrets, as well as for all ω-regular secrets under finite-memory schedulers.
AU - Bérard, Béatrice
AU - Chatterjee, Krishnendu
AU - Sznajder, Nathalie
ID - 2034
IS - 1
JF - Information Processing Letters
TI - Probabilistic opacity for Markov decision processes
VL - 115
ER -
TY - JOUR
AB - Considering a continuous self-map and the induced endomorphism on homology, we study the eigenvalues and eigenspaces of the latter. Taking a filtration of representations, we define the persistence of the eigenspaces, effectively introducing a hierarchical organization of the map. The algorithm that computes this information for a finite sample is proved to be stable, and to give the correct answer for a sufficiently dense sample. Results computed with an implementation of the algorithm provide evidence of its practical utility.
AU - Edelsbrunner, Herbert
AU - Jablonski, Grzegorz
AU - Mrozek, Marian
ID - 2035
IS - 5
JF - Foundations of Computational Mathematics
TI - The persistent homology of a self-map
VL - 15
ER -
TY - JOUR
AB - We study the spectrum of a large system of N identical bosons interacting via a two-body potential with strength 1/N. In this mean-field regime, Bogoliubov's theory predicts that the spectrum of the N-particle Hamiltonian can be approximated by that of an effective quadratic Hamiltonian acting on Fock space, which describes the fluctuations around a condensed state. Recently, Bogoliubov's theory has been justified rigorously in the case that the low-energy eigenvectors of the N-particle Hamiltonian display complete condensation in the unique minimizer of the corresponding Hartree functional. In this paper, we shall justify Bogoliubov's theory for the high-energy part of the spectrum of the N-particle Hamiltonian corresponding to (non-linear) excited states of the Hartree functional. Moreover, we shall extend the existing results on the excitation spectrum to the case of non-uniqueness and/or degeneracy of the Hartree minimizer. In particular, the latter covers the case of rotating Bose gases, when the rotation speed is large enough to break the symmetry and to produce multiple quantized vortices in the Hartree minimizer.
AU - Nam, Phan
AU - Seiringer, Robert
ID - 2085
IS - 2
JF - Archive for Rational Mechanics and Analysis
TI - Collective excitations of Bose gases in the mean-field regime
VL - 215
ER -
TY - JOUR
AB - We consider the spectral statistics of large random band matrices on mesoscopic energy scales. We show that the correlation function of the local eigenvalue density exhibits a universal power law behaviour that differs from the Wigner-Dyson- Mehta statistics. This law had been predicted in the physics literature by Altshuler and Shklovskii in (Zh Eksp Teor Fiz (Sov Phys JETP) 91(64):220(127), 1986); it describes the correlations of the eigenvalue density in general metallic sampleswith weak disorder. Our result rigorously establishes the Altshuler-Shklovskii formulas for band matrices. In two dimensions, where the leading term vanishes owing to an algebraic cancellation, we identify the first non-vanishing term and show that it differs substantially from the prediction of Kravtsov and Lerner in (Phys Rev Lett 74:2563-2566, 1995). The proof is given in the current paper and its companion (Ann. H. Poincaré. arXiv:1309.5107, 2014).
AU - Erdös, László
AU - Knowles, Antti
ID - 2166
IS - 3
JF - Communications in Mathematical Physics
TI - The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case
VL - 333
ER -
TY - JOUR
AB - Currently, there is much debate on the genetic architecture of quantitative traits in wild populations. Is trait variation influenced by many genes of small effect or by a few genes of major effect? Where is additive genetic variation located in the genome? Do the same loci cause similar phenotypic variation in different populations? Great tits (Parus major) have been studied extensively in long‐term studies across Europe and consequently are considered an ecological ‘model organism’. Recently, genomic resources have been developed for the great tit, including a custom SNP chip and genetic linkage map. In this study, we used a suite of approaches to investigate the genetic architecture of eight quantitative traits in two long‐term study populations of great tits—one in the Netherlands and the other in the United Kingdom. Overall, we found little evidence for the presence of genes of large effects in either population. Instead, traits appeared to be influenced by many genes of small effect, with conservative estimates of the number of contributing loci ranging from 31 to 310. Despite concordance between population‐specific heritabilities, we found no evidence for the presence of loci having similar effects in both populations. While population‐specific genetic architectures are possible, an undetected shared architecture cannot be rejected because of limited power to map loci of small and moderate effects. This study is one of few examples of genetic architecture analysis in replicated wild populations and highlights some of the challenges and limitations researchers will face when attempting similar molecular quantitative genetic studies in free‐living populations.
AU - Santure, Anna W.
AU - Poissant, Jocelyn
AU - De Cauwer, Isabelle
AU - van Oers, Kees
AU - Robinson, Matthew Richard
AU - Quinn, John L.
AU - Groenen, Martien A. M.
AU - Visser, Marcel E.
AU - Sheldon, Ben C.
AU - Slate, Jon
ID - 7739
JF - Molecular Ecology
SN - 0962-1083
TI - Replicated analysis of the genetic architecture of quantitative traits in two wild great tit populations
VL - 24
ER -
TY - JOUR
AB - Phenotypes expressed in a social context are not only a function of the individual, but can also be shaped by the phenotypes of social partners. These social effects may play a major role in the evolution of cooperative breeding if social partners differ in the quality of care they provide and if individual carers adjust their effort in relation to that of other carers. When applying social effects models to wild study systems, it is also important to explore sources of individual plasticity that could masquerade as social effects. We studied offspring provisioning rates of parents and helpers in a wild population of long-tailed tits Aegithalos caudatus using a quantitative genetic framework to identify these social effects and partition them into genetic, permanent environment and current environment components. Controlling for other effects, individuals were consistent in their provisioning effort at a given nest, but adjusted their effort based on who was in their social group, indicating the presence of social effects. However, these social effects differed between years and social contexts, indicating a current environment effect, rather than indicating a genetic or permanent environment effect. While this study reveals the importance of examining environmental and genetic sources of social effects, the framework we present is entirely general, enabling a greater understanding of potentially important social effects within any ecological population.
AU - Adams, Mark James
AU - Robinson, Matthew Richard
AU - Mannarelli, Maria-Elena
AU - Hatchwell, Ben J.
ID - 7741
IS - 1810
JF - Proceedings of the Royal Society B: Biological Sciences
SN - 0962-8452
TI - Social genetic and social environment effects on parental and helper care in a cooperatively breeding bird
VL - 282
ER -
TY - GEN
AB - The fact that a disordered material is not constrained in its properties in
the same way as a crystal presents significant and yet largely untapped
potential for novel material design. However, unlike their crystalline
counterparts, disordered solids are not well understood. One of the primary
obstacles is the lack of a theoretical framework for thinking about disorder
and its relation to mechanical properties. To this end, we study an idealized
system of frictionless athermal soft spheres that, when compressed, undergoes a
jamming phase transition with diverging length scales and clean power-law
signatures. This critical point is the cornerstone of a much larger "jamming
scenario" that has the potential to provide the essential theoretical
foundation necessary for a unified understanding of the mechanics of disordered
solids. We begin by showing that jammed sphere packings have a valid linear
regime despite the presence of "contact nonlinearities." We then investigate
the critical nature of the transition, focusing on diverging length scales and
finite-size effects. Next, we argue that jamming plays the same role for
disordered solids as the perfect crystal plays for crystalline solids. Not only
can it be considered an idealized starting point for understanding disordered
materials, but it can even influence systems that have a relatively high amount
of crystalline order. The behavior of solids can thus be thought of as existing
on a spectrum, with the perfect crystal and the jamming transition at opposing
ends. Finally, we introduce a new principle wherein the contribution of an
individual bond to one global property is independent of its contribution to
another. This principle allows the different global responses of a disordered
system to be manipulated independently and provides a great deal of flexibility
in designing materials with unique, textured and tunable properties.
AU - Goodrich, Carl Peter
ID - 7779
T2 - arXiv:1510.08820
TI - Unearthing the anticrystal: Criticality in the linear response of disordered solids
ER -
TY - CONF
AB - Several Hybrid Transactional Memory (HyTM) schemes have recently been proposed to complement the fast, but best-effort nature of Hardware Transactional Memory (HTM) with a slow, reliable software backup. However, the costs of providing concurrency between hardware and software transactions in HyTM are still not well understood. In this paper, we propose a general model for HyTM implementations, which captures the ability of hardware transactions to buffer memory accesses. The model allows us to formally quantify and analyze the amount of overhead (instrumentation) caused by the potential presence of software transactions.We prove that (1) it is impossible to build a strictly serializable HyTM implementation that has both uninstrumented reads and writes, even for very weak progress guarantees, and (2) the instrumentation cost incurred by a hardware transaction in any progressive opaque HyTM is linear in the size of the transaction’s data set.We further describe two implementations which exhibit optimal instrumentation costs for two different progress conditions. In sum, this paper proposes the first formal HyTM model and captures for the first time the trade-off between the degree of hardware-software TM concurrency and the amount of instrumentation overhead.
AU - Alistarh, Dan-Adrian
AU - Kopinsky, Justin
AU - Kuznetsov, Petr
AU - Ravi, Srivatsan
AU - Shavit, Nir
ID - 778
TI - Inherent limitations of hybrid transactional memory
VL - 9363
ER -
TY - CONF
AB - Population protocols are networks of finite-state agents, interacting randomly, and updating their states using simple rules. Despite their extreme simplicity, these systems have been shown to cooperatively perform complex computational tasks, such as simulating register machines to compute standard arithmetic functions. The election of a unique leader agent is a key requirement in such computational constructions. Yet, the fastest currently known population protocol for electing a leader only has linear convergence time, and it has recently been shown that no population protocol using a constant number of states per node may overcome this linear bound. In this paper, we give the first population protocol for leader election with polylogarithmic convergence time, using polylogarithmic memory states per node. The protocol structure is quite simple: each node has an associated value, and is either a leader (still in contention) or a minion (following some leader). A leader keeps incrementing its value and “defeats” other leaders in one-to-one interactions, and will drop from contention and become a minion if it meets a leader with higher value. Importantly, a leader also drops out if it meets a minion with higher absolute value. While these rules are quite simple, the proof that this algorithm achieves polylogarithmic convergence time is non-trivial. In particular, the argument combines careful use of concentration inequalities with anti-concentration bounds, showing that the leaders’ values become spread apart as the execution progresses, which in turn implies that straggling leaders get quickly eliminated. We complement our analysis with empirical results, showing that our protocol converges extremely fast, even for large network sizes.
AU - Alistarh, Dan-Adrian
AU - Gelashvili, Rati
ID - 780
TI - Polylogarithmic-time leader election in population protocols
VL - 9135
ER -
TY - CONF
AB - The problem of electing a leader from among n contenders is one of the fundamental questions in distributed computing. In its simplest formulation, the task is as follows: given n processors, all participants must eventually return a win or lose indication, such that a single contender may win. Despite a considerable amount of work on leader election, the following question is still open: can we elect a leader in an asynchronous fault-prone system faster than just running a Θ(log n)-time tournament, against a strong adaptive adversary? In this paper, we answer this question in the affirmative, improving on a decades-old upper bound. We introduce two new algorithmic ideas to reduce the time complexity of electing a leader to O(log∗ n), using O(n2) point-to-point messages. A non-trivial application of our algorithm is a new upper bound for the tight renaming problem, assigning n items to the n participants in expected O(log2 n) time and O(n2) messages. We complement our results with lower bound of Ω(n2) messages for solving these two problems, closing the question of their message complexity.
AU - Alistarh, Dan-Adrian
AU - Gelashvili, Rati
AU - Vladu, Adrian
ID - 783
TI - How to elect a leader faster than a tournament
VL - 2015-July
ER -