@inproceedings{2319, abstract = {In a recent paper [7] we give the first rigorous derivation of the celebrated Ginzburg-Landau (GL)theory, starting from the microscopic Bardeen- Cooper-Schrieffer (BCS)model. Here we present our results in the simplified case of a one-dimensional system of particles interacting via a δ-potential.}, author = {Frank, Rupert L and Hainzl, Christian and Robert Seiringer and Solovej, Jan P}, pages = {57 -- 88}, publisher = {Springer}, title = {{ Derivation of Ginzburg-Landau theory for a one-dimensional system with contact interaction}}, doi = {10.1007/978-3-0348-0531-5_3}, year = {2013}, } @inproceedings{2327, abstract = {We define the model-measuring problem: given a model M and specification φ, what is the maximal distance ρ such that all models M′ within distance ρ from M satisfy (or violate) φ. The model measuring problem presupposes a distance function on models. We concentrate on automatic distance functions, which are defined by weighted automata. The model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, quantitative model-checking problems that measure the degree of satisfaction of a specification, and robustness problems that measure how much a model can be perturbed without violating the specification. We show that for automatic distance functions, and ω-regular linear-time and branching-time specifications, the model-measuring problem can be solved. We use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for standard word and tree automata by the optimal-weight question for the weighted versions of these automata. We consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging. We give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications.}, author = {Henzinger, Thomas A and Otop, Jan}, location = {Buenos Aires, Argentina}, pages = {273 -- 287}, publisher = {Springer}, title = {{From model checking to model measuring}}, doi = {10.1007/978-3-642-40184-8_20}, volume = {8052}, year = {2013}, } @inproceedings{2328, abstract = {Linearizability of concurrent data structures is usually proved by monolithic simulation arguments relying on identifying 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.}, author = {Henzinger, Thomas A and Sezgin, Ali and Vafeiadis, Viktor}, location = {Buenos Aires, Argentina}, pages = {242 -- 256}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Aspect-oriented linearizability proofs}}, doi = {10.1007/978-3-642-40184-8_18}, volume = {8052}, year = {2013}, } @inproceedings{2329, abstract = {Two-player games on graphs are central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work, we consider both finite-state game graphs, and recursive game graphs (or pushdown game graphs) that model the control flow of sequential programs with recursion. The objectives we study are multidimensional mean-payoff objectives, where the goal of player 1 is to ensure that the mean-payoff is non-negative in all dimensions. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation. Our main contributions are as follows: (1) We show that finite-state multidimensional mean-payoff games can be solved in polynomial time if the number of dimensions and the maximal absolute value of the weights are fixed; whereas if the number of dimensions is arbitrary, then the problem is known to be coNP-complete. (2) We show that pushdown graphs with multidimensional mean-payoff objectives can be solved in polynomial time. For both (1) and (2) our algorithms are based on hyperplane separation technique. (3) For pushdown games under global strategies both one and multidimensional mean-payoff objectives problems are known to be undecidable, and we show that under modular strategies the multidimensional problem is also undecidable; under modular strategies the one-dimensional problem is NP-complete. We show that if the number of modules, the number of exits, and the maximal absolute value of the weights are fixed, then pushdown games under modular strategies with one-dimensional mean-payoff objectives can be solved in polynomial time, and if either the number of exits or the number of modules is unbounded, then the problem is NP-hard. (4) Finally we show that a fixed parameter tractable algorithm for finite-state multidimensional mean-payoff games or pushdown games under modular strategies with one-dimensional mean-payoff objectives would imply the fixed parameter tractability of parity games.}, author = {Chatterjee, Krishnendu and Velner, Yaron}, location = {Buenos Aires, Argentinia}, pages = {500 -- 515}, publisher = {Springer}, title = {{Hyperplane separation technique for multidimensional mean-payoff games}}, doi = {10.1007/978-3-642-40184-8_35}, volume = {8052}, year = {2013}, } @article{2404, abstract = {The Lieb-Thirring inequalities give a bound on the negative eigenvalues of a Schrödinger operator in terms of an Lp-norm of the potential. These are dual to bounds on the H1-norms of a system of orthonormal functions. Here we extend these bounds to analogous inequalities for perturbations of the Fermi sea of noninteracting particles (i.e., for perturbations of the continuous spectrum of the Laplacian by local potentials).}, author = {Frank, Rupert L and Lewin, Mathieu and Lieb, Élliott H and Robert Seiringer}, journal = {Duke Mathematical Journal}, number = {3}, pages = {435 -- 495}, publisher = {Duke University Press}, title = {{A positive density analogue of the Lieb-Thirring inequality}}, doi = {10.1215/00127094-2019477}, volume = {162}, year = {2013}, } @article{2405, abstract = {We consider the bipolaron in the Pekar-Tomasevich approximation and address the question whether the ground state is spherically symmetric or not. Numerical analysis has, so far, not completely settled the question. Our contribution is to prove rigorously that the ground state remains spherical for small values of the electron-electron Coulomb repulsion.}, author = {Frank, Rupert L and Lieb, Élliott H and Robert Seiringer}, journal = {Communications in Mathematical Physics}, number = {2}, pages = {557 -- 573}, publisher = {Springer}, title = {{Symmetry of bipolaron bound states for small Coulomb repulsion}}, doi = {10.1007/s00220-012-1604-y}, volume = {319}, year = {2013}, } @article{2406, abstract = {We study the effects of random scatterers on the ground state of the one-dimensional Lieb-Liniger model of interacting bosons on the unit interval. We prove that, in the Gross-Pitaevskii limit, Bose Einstein condensation takes place in the whole parameter range considered. The character of the wave function of the condensate, however, depends in an essential way on the interplay between randomness and the strength of the two-body interaction. For low density of scatterers or strong interactions the wave function extends over the whole interval. High density of scatterers and weak interaction, on the other hand, leads to localization of the wave function in a fragmented subset of the unit interval.}, author = {Robert Seiringer and Yngvason, Jakob and Zagrebnov, Valentin A}, journal = {European Physical Journal: Special Topics}, number = {1}, pages = {103 -- 107}, publisher = {Springer}, title = {{Condensation of interacting bosons in a random potential}}, doi = {10.1140/epjst/e2013-01759-5}, volume = {217}, year = {2013}, } @article{2408, abstract = {We investigate the low-energy excitation spectrum of a Bose gas confined in a trap, with weak long-range repulsive interactions. In particular, we prove that the spectrum can be described in terms of the eigenvalues of an effective one-particle operator, as predicted by the Bogoliubov approximation.}, author = {Grech, Philip and Robert Seiringer}, journal = {Communications in Mathematical Physics}, number = {2}, pages = {559 -- 591}, publisher = {Springer}, title = {{The excitation spectrum for weakly interacting Bosons in a trap}}, doi = {10.1007/s00220-013-1736-8}, volume = {322}, year = {2013}, } @article{2410, abstract = {Here, we describe a novel virulent bacteriophage that infects Bacillus weihenstephanensis, isolated from soil in Austria. It is the first phage to be discovered that infects this species. Here, we present the complete genome sequence of this podovirus. }, author = {Fernandes Redondo, Rodrigo A and Kupczok, Anne and Stift, Gertraud and Bollback, Jonathan P}, journal = {Genome Announcements}, number = {3}, publisher = {American Society for Microbiology}, title = {{Complete genome sequence of the novel phage MG-B1 infecting bacillus weihenstephanensis}}, doi = {10.1128/genomeA.00216-13}, volume = {1}, year = {2013}, } @article{2412, abstract = {Background: The CRISPR/Cas system is known to act as an adaptive and heritable immune system in Eubacteria and Archaea. Immunity is encoded in an array of spacer sequences. Each spacer can provide specific immunity to invasive elements that carry the same or a similar sequence. Even in closely related strains, spacer content is very dynamic and evolves quickly. Standard models of nucleotide evolutioncannot be applied to quantify its rate of change since processes other than single nucleotide changes determine its evolution.Methods We present probabilistic models that are specific for spacer content evolution. They account for the different processes of insertion and deletion. Insertions can be constrained to occur on one end only or are allowed to occur throughout the array. One deletion event can affect one spacer or a whole fragment of adjacent spacers. Parameters of the underlying models are estimated for a pair of arrays by maximum likelihood using explicit ancestor enumeration.Results Simulations show that parameters are well estimated on average under the models presented here. There is a bias in the rate estimation when including fragment deletions. The models also estimate times between pairs of strains. But with increasing time, spacer overlap goes to zero, and thus there is an upper bound on the distance that can be estimated. Spacer content similarities are displayed in a distance based phylogeny using the estimated times.We use the presented models to analyze different Yersinia pestis data sets and find that the results among them are largely congruent. The models also capture the variation in diversity of spacers among the data sets. A comparison of spacer-based phylogenies and Cas gene phylogenies shows that they resolve very different time scales for this data set.Conclusions The simulations and data analyses show that the presented models are useful for quantifying spacer content evolution and for displaying spacer content similarities of closely related strains in a phylogeny. This allows for comparisons of different CRISPR arrays or for comparisons between CRISPR arrays and nucleotide substitution rates.}, author = {Kupczok, Anne and Bollback, Jonathan P}, journal = {BMC Evolutionary Biology}, number = {1}, pages = {54 -- 54}, publisher = {BioMed Central}, title = {{Probabilistic models for CRISPR spacer content evolution }}, doi = {10.1186/1471-2148-13-54}, volume = {13}, year = {2013}, } @inbook{2413, abstract = {Progress in understanding the global brain dynamics has remained slow to date in large part because of the highly multiscale nature of brain activity. Indeed, normal brain dynamics is characterized by complex interactions between multiple levels: from the microscopic scale of single neurons to the mesoscopic level of local groups of neurons, and finally to the macroscopic level of the whole brain. Among the most difficult tasks are those of identifying which scales are significant for a given particular function and describing how the scales affect each other. It is important to realize that the scales of time and space are linked together, or even intertwined, and that causal inference is far more ambiguous between than within levels. We approach this problem from the perspective of our recent work on simultaneous recording from micro- and macroelectrodes in the human brain. We propose a physiological description of these multilevel interactions, based on phase–amplitude coupling of neuronal oscillations that operate at multiple frequencies and on different spatial scales. Specifically, the amplitude of the oscillations on a particular spatial scale is modulated by phasic variations in neuronal excitability induced by lower frequency oscillations that emerge on a larger spatial scale. Following this general principle, it is possible to scale up or scale down the multiscale brain dynamics. It is expected that large-scale network oscillations in the low-frequency range, mediating downward effects, may play an important role in attention and consciousness.}, author = {Valderrama, Mario and Botella Soler, Vicente and Le Van Quyen, Michel}, booktitle = {Multiscale Analysis and Nonlinear Dynamics: From Genes to the Brain}, editor = {Meyer, Misha and Pesenson, Z.}, isbn = {9783527411986 }, publisher = {Wiley-VCH}, title = {{Neuronal oscillations scale up and scale down the brain dynamics }}, doi = {10.1002/9783527671632.ch08}, year = {2013}, } @article{6768, abstract = {The paper presents an algorithm that applies a stack filter simulating the Mean Curvature Motion equation via a finite difference scheme.}, author = {Mondelli, Marco}, issn = {2105-1232}, journal = {Image Processing On Line}, pages = {68--111}, publisher = {Image Processing On Line}, title = {{A finite difference scheme for the stack filter simulating the MCM}}, doi = {10.5201/ipol.2013.53}, volume = {3}, year = {2013}, } @article{7306, abstract = {Rechargeable lithium–air (O2) batteries are receiving intense interest because their high theoretical specific energy exceeds that of lithium-ion batteries. If the Li–O2 battery is ever to succeed, highly reversible formation/decomposition of Li2O2 must take place at the cathode on cycling. However, carbon, used ubiquitously as the basis of the cathode, decomposes during Li2O2 oxidation on charge and actively promotes electrolyte decomposition on cycling. Replacing carbon with a nanoporous gold cathode, when in contact with a dimethyl sulphoxide-based electrolyte, does seem to demonstrate better stability. However, nanoporous gold is not a suitable cathode; its high mass destroys the key advantage of Li–O2 over Li ion (specific energy), it is too expensive and too difficult to fabricate. Identifying a suitable cathode material for the Li–O2 cell is one of the greatest challenges at present. Here we show that a TiC-based cathode reduces greatly side reactions (arising from the electrolyte and electrode degradation) compared with carbon and exhibits better reversible formation/decomposition of Li2O2 even than nanoporous gold (>98% capacity retention after 100 cycles, compared with 95% for nanoporous gold); it is also four times lighter, of lower cost and easier to fabricate. The stability may originate from the presence of TiO2 (along with some TiOC) on the surface of TiC. In contrast to carbon or nanoporous gold, TiC seems to represent a more viable, stable, cathode for aprotic Li–O2 cells.}, author = {Ottakam Thotiyl, Muhammed M. and Freunberger, Stefan Alexander and Peng, Zhangquan and Chen, Yuhui and Liu, Zheng and Bruce, Peter G.}, issn = {1476-1122}, journal = {Nature Materials}, number = {11}, pages = {1050--1056}, publisher = {Springer Nature}, title = {{A stable cathode for the aprotic Li–O2 battery}}, doi = {10.1038/nmat3737}, volume = {12}, year = {2013}, } @article{7307, abstract = {The non-aqueous Li–air (O2) battery is receiving intense interest because its theoretical specific energy exceeds that of Li-ion batteries. Recharging the Li–O2 battery depends on oxidizing solid lithium peroxide (Li2O2), which is formed on discharge within the porous cathode. However, transporting charge between Li2O2 particles and the solid electrode surface is at best very difficult and leads to voltage polarization on charging, even at modest rates. This is a significant problem facing the non-aqueous Li–O2 battery. Here we show that incorporation of a redox mediator, tetrathiafulvalene (TTF), enables recharging at rates that are impossible for the cell in the absence of the mediator. On charging, TTF is oxidized to TTF+ at the cathode surface; TTF+ in turn oxidizes the solid Li2O2, which results in the regeneration of TTF. The mediator acts as an electron–hole transfer agent that permits efficient oxidation of solid Li2O2. The cell with the mediator demonstrated 100 charge/discharge cycles.}, author = {Chen, Yuhui and Freunberger, Stefan Alexander and Peng, Zhangquan and Fontaine, Olivier and Bruce, Peter G.}, issn = {1755-4330}, journal = {Nature Chemistry}, number = {6}, pages = {489--494}, publisher = {Springer Nature}, title = {{Charging a Li–O2 battery using a redox mediator}}, doi = {10.1038/nchem.1646}, volume = {5}, year = {2013}, } @article{7595, abstract = {Inositol 1,3,4-trisphosphate 5/6 kinase (ITPK) phosphorylates inositol 1,3,4-trisphosphate to form inositol 1,3,4,5-tetrakisphosphate and inositol 1,3,4,6-tetrakisphosphate which can be finally transferred to inositol hexaphosphate (IP6) and play important roles during plant growth and development. There are 4 putative ITPK members in Arabidopsis. Expression pattern analysis showed that ITPK2 is constitutively expressed in various tissues. A T-DNA knockout mutant of ITPK2 was identified and scanning electron microscopy (SEM) analysis showed that the epidermis structure of seed coat was irregularly formed in seeds of itpk2-1 mutant, resulting in the increased permeability of seed coat to tetrazolium salts. Further analysis by gas chromatography coupled with mass spectrometry of lipid polyester monomers in cell wall confirmed a dramatic decrease in composition of suberin and cutin, which relate to the permeability of seed coat and the formation of which is accompanied with seed coat development. These results indicate that ITPK2 plays an essential role in seed coat development and lipid polyester barrier formation.}, author = {Tang, Yong and Tan, Shutang and Xue, Hongwei}, issn = {1745-7270}, journal = {Acta Biochimica et Biophysica Sinica}, number = {7}, pages = {549--560}, publisher = {Oxford University Press}, title = {{Arabidopsis inositol 1,3,4-trisphosphate 5/6 kinase 2 is required for seed coat development}}, doi = {10.1093/abbs/gmt039}, volume = {45}, year = {2013}, } @article{7596, abstract = {Casein kinase1 (CK1) plays crucial roles in regulating growth and development via phosphorylating various substrates throughout the eukaryote kingdom. Blue light is crucial for normal growth of both plants and animals, and blue light receptor cryptochrome2 (CRY2) undergoes blue light–dependent phosphorylation and degradation in planta. To study the function of plant CK1s, systematic genetic analysis showed that deficiency of two paralogous Arabidopsis thaliana CK1s, CK1.3 and CK1.4, caused shortened hypocotyls, especially under blue light, while overexpression of either CK1.3 or CK1.4 resulted in the insensitive response to blue light and delayed flowering under long-day conditions. CK1.3 or CK1.4 act dependently on CRY2, and overexpression of CK1.3 or CK1.4 significantly suppresses the hypersensitive response to blue light by CRY2 overexpression. Biochemical studies showed that CK1.3 and CK1.4 directly phosphorylate CRY2 at Ser-587 and Thr-603 in vitro and negatively regulate CRY2 stability in planta, which are stimulated by blue light, further confirming the crucial roles of CK1.3 and CK1.4 in blue light responses through phosphorylating CRY2. Interestingly, expression of CK1.3 and CK1.4 is stimulated by blue light and feedback regulated by CRY2-mediated signaling. These results provide direct evidence for CRY2 phosphorylation and informative clues on the mechanisms of CRY2-mediated light responses.}, author = {Tan, Shutang and Dai, C. and Liu, H.-T. and Xue, H.-W.}, issn = {1040-4651}, journal = {The Plant Cell}, number = {7}, pages = {2618--2632}, publisher = {American Society of Plant Biologists}, title = {{Arabidopsis casein kinase1 proteins CK1.3 and CK1.4 phosphorylate cryptochrome2 to regulate blue light signaling}}, doi = {10.1105/tpc.113.114322}, volume = {25}, year = {2013}, } @inproceedings{765, abstract = {Renaming is a classic distributed coordination task in which a set of processes must pick distinct identifiers from a small namespace. In this paper, we consider the time complexity of this problem when the namespace is linear in the number of participants, a variant known as loose renaming. We give a non-adaptive algorithm with O(log log n) (individual) step complexity, where n is a known upper bound on contention, and an adaptive algorithm with step complexity O((log log k)2), where k is the actual contention in the execution. We also present a variant of the adaptive algorithm which requires O(k log log k) total process steps. All upper bounds hold with high probability against a strong adaptive adversary. We complement the algorithms with an ω(log log n) expected time lower bound on the complexity of randomized renaming using test-and-set operations and linear space. The result is based on a new coupling technique, and is the first to apply to non-adaptive randomized renaming. Since our algorithms use O(n) test-and-set objects, our results provide matching bounds on the cost of loose renaming in this setting.}, author = {Alistarh, Dan-Adrian and Aspnes, James and Giakkoupis, George and Woelfel, Philipp}, pages = {200 -- 209}, publisher = {ACM}, title = {{Randomized loose renaming in O(loglogn) time}}, doi = {10.1145/2484239.2484240}, year = {2013}, } @article{7745, abstract = {The underlying basis of genetic variation in quantitative traits, in terms of the number of causal variants and the size of their effects, is largely unknown in natural populations. The expectation is that complex quantitative trait variation is attributable to many, possibly interacting, causal variants, whose effects may depend upon the sex, age and the environment in which they are expressed. A recently developed methodology in animal breeding derives a value of relatedness among individuals from high‐density genomic marker data, to estimate additive genetic variance within livestock populations. Here, we adapt and test the effectiveness of these methods to partition genetic variation for complex traits across genomic regions within ecological study populations where individuals have varying degrees of relatedness. We then apply this approach for the first time to a natural population and demonstrate that genetic variation in wing length in the great tit (Parus major) reflects contributions from multiple genomic regions. We show that a polygenic additive mode of gene action best describes the patterns observed, and we find no evidence of dosage compensation for the sex chromosome. Our results suggest that most of the genomic regions that influence wing length have the same effects in both sexes. We found a limited amount of genetic variance in males that is attributed to regions that have no effects in females, which could facilitate the sexual dimorphism observed for this trait. Although this exploratory work focuses on one complex trait, the methodology is generally applicable to any trait for any laboratory or wild population, paving the way for investigating sex‐, age‐ and environment‐specific genetic effects and thus the underlying genetic architecture of phenotype in biological study systems.}, author = {Robinson, Matthew Richard and Santure, Anna W. and DeCauwer, Isabelle and Sheldon, Ben C. and Slate, Jon}, issn = {0962-1083}, journal = {Molecular Ecology}, number = {15}, pages = {3963--3980}, publisher = {Wiley}, title = {{Partitioning of genetic variation across the genome using multimarker methods in a wild bird population}}, doi = {10.1111/mec.12375}, volume = {22}, year = {2013}, } @article{7746, abstract = {Clutch size and egg mass are life history traits that have been extensively studied in wild bird populations, as life history theory predicts a negative trade‐off between them, either at the phenotypic or at the genetic level. Here, we analyse the genomic architecture of these heritable traits in a wild great tit (Parus major) population, using three marker‐based approaches – chromosome partitioning, quantitative trait locus (QTL) mapping and a genome‐wide association study (GWAS). The variance explained by each great tit chromosome scales with predicted chromosome size, no location in the genome contains genome‐wide significant QTL, and no individual SNPs are associated with a large proportion of phenotypic variation, all of which may suggest that variation in both traits is due to many loci of small effect, located across the genome. There is no evidence that any regions of the genome contribute significantly to both traits, which combined with a small, nonsignificant negative genetic covariance between the traits, suggests the absence of genetic constraints on the independent evolution of these traits. Our findings support the hypothesis that variation in life history traits in natural populations is likely to be determined by many loci of small effect spread throughout the genome, which are subject to continued input of variation by mutation and migration, although we cannot exclude the possibility of an additional input of major effect genes influencing either trait.}, author = {Santure, Anna W. and De Cauwer, Isabelle and Robinson, Matthew Richard and Poissant, Jocelyn and Sheldon, Ben C. and Slate, Jon}, issn = {0962-1083}, journal = {Molecular Ecology}, number = {15}, pages = {3949--3962}, publisher = {Wiley}, title = {{Genomic dissection of variation in clutch size and egg mass in a wild great tit (Parus major) population}}, doi = {10.1111/mec.12376}, volume = {22}, year = {2013}, } @article{7747, abstract = {Acquisition and allocation of resources are central to life‐history theory. However, empirical work typically focuses only on allocation despite the fact that relationships between fitness components may be governed by differences in the ability of individuals to acquire resources across environments. Here, we outline a statistical framework to partition the genetic basis of multivariate plasticity into independent axes of genetic variation, and quantify for the first time, the extent to which specific traits drive multitrait genotype–environment interactions. Our framework generalises to analyses of plasticity, growth and ageing. We apply this approach to a unique, large‐scale, multivariate study of acquisition, allocation and plasticity in the life history of the cricket, Gryllus firmus. We demonstrate that resource acquisition and allocation are genetically correlated, and that plasticity in trade‐offs between allocation to components of fitness is 90% dependent on genetic variance for total resource acquisition. These results suggest that genotype–environment effects for resource acquisition can maintain variation in life‐history components that are typically observed in the wild.}, author = {Robinson, Matthew Richard and Beckerman, Andrew P.}, issn = {1461-023X}, journal = {Ecology Letters}, number = {3}, pages = {281--290}, publisher = {Wiley}, title = {{Quantifying multivariate plasticity: Genetic variation in resource acquisition drives plasticity in resource allocation to components of life history}}, doi = {10.1111/ele.12047}, volume = {16}, year = {2013}, }