@inproceedings{1192, abstract = {The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Knowing that edge CSP is tractable for even Δ-matroid constraints allows us to extend the tractability result to a larger class of Δ-matroids that includes many classes that were known to be tractable before, namely co-independent, compact, local and binary.}, author = {Kazda, Alexandr and Kolmogorov, Vladimir and Rolinek, Michal}, isbn = {978-161197478-2}, location = {Barcelona, Spain}, pages = {307 -- 326}, publisher = {SIAM}, title = {{Even delta-matroids and the complexity of planar Boolean CSPs}}, doi = {10.1137/1.9781611974782.20}, year = {2017}, } @inproceedings{1194, abstract = {Termination is one of the basic liveness properties, and we study the termination problem for probabilistic programs with real-valued variables. Previous works focused on the qualitative problem that asks whether an input program terminates with probability~1 (almost-sure termination). A powerful approach for this qualitative problem is the notion of ranking supermartingales with respect to a given set of invariants. The quantitative problem (probabilistic termination) asks for bounds on the termination probability. A fundamental and conceptual drawback of the existing approaches to address probabilistic termination is that even though the supermartingales consider the probabilistic behavior of the programs, the invariants are obtained completely ignoring the probabilistic aspect. In this work we address the probabilistic termination problem for linear-arithmetic probabilistic programs with nondeterminism. We define the notion of {\em stochastic invariants}, which are constraints along with a probability bound that the constraints hold. We introduce a concept of {\em repulsing supermartingales}. First, we show that repulsing supermartingales can be used to obtain bounds on the probability of the stochastic invariants. Second, we show the effectiveness of repulsing supermartingales in the following three ways: (1)~With a combination of ranking and repulsing supermartingales we can compute lower bounds on the probability of termination; (2)~repulsing supermartingales provide witnesses for refutation of almost-sure termination; and (3)~with a combination of ranking and repulsing supermartingales we can establish persistence properties of probabilistic programs. We also present results on related computational problems and an experimental evaluation of our approach on academic examples. }, author = {Chatterjee, Krishnendu and Novotny, Petr and Zikelic, Djordje}, issn = {07308566}, location = {Paris, France}, number = {1}, pages = {145 -- 160}, publisher = {ACM}, title = {{Stochastic invariants for probabilistic termination}}, doi = {10.1145/3009837.3009873}, volume = {52}, year = {2017}, } @article{1196, 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; robustness problems that measure how much a model can be perturbed without violating the specification; and parameter synthesis for hybrid systems. We show that for automatic distance functions, and (a) . ω-regular linear-time, (b) . ω-regular branching-time, and (c) hybrid specifications, the model-measuring problem can be solved.We use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for word, tree, and hybrid automata by the . optimal-value question for the weighted versions of these automata. For automata over words and trees, we consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging. For hybrid automata, we consider monotonic (parametric) hybrid automata, a hybrid counterpart of (discrete) weighted automata.We give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications. Further, we propose the modeling framework for model measuring to ease the specification and reduce the likelihood of errors in modeling.Finally, we present a variant of the model-measuring problem, called the . model-repair problem. The model-repair problem applies to models that do not satisfy the specification; it can be used to derive restrictions, under which the model satisfies the specification, i.e., to repair the model.}, author = {Henzinger, Thomas A and Otop, Jan}, journal = {Nonlinear Analysis: Hybrid Systems}, pages = {166 -- 190}, publisher = {Elsevier}, title = {{Model measuring for discrete and hybrid systems}}, doi = {10.1016/j.nahs.2016.09.001}, volume = {23}, year = {2017}, } @article{1198, abstract = {We consider a model of fermions interacting via point interactions, defined via a certain weighted Dirichlet form. While for two particles the interaction corresponds to infinite scattering length, the presence of further particles effectively decreases the interaction strength. We show that the model becomes trivial in the thermodynamic limit, in the sense that the free energy density at any given particle density and temperature agrees with the corresponding expression for non-interacting particles.}, author = {Moser, Thomas and Seiringer, Robert}, issn = {03779017}, journal = {Letters in Mathematical Physics}, number = {3}, pages = { 533 -- 552}, publisher = {Springer}, title = {{Triviality of a model of particles with point interactions in the thermodynamic limit}}, doi = {10.1007/s11005-016-0915-x}, volume = {107}, year = {2017}, } @article{1199, abstract = {Much of quantitative genetics is based on the ‘infinitesimal model’, under which selection has a negligible effect on the genetic variance. This is typically justified by assuming a very large number of loci with additive effects. However, it applies even when genes interact, provided that the number of loci is large enough that selection on each of them is weak relative to random drift. In the long term, directional selection will change allele frequencies, but even then, the effects of epistasis on the ultimate change in trait mean due to selection may be modest. Stabilising selection can maintain many traits close to their optima, even when the underlying alleles are weakly selected. However, the number of traits that can be optimised is apparently limited to ~4Ne by the ‘drift load’, and this is hard to reconcile with the apparent complexity of many organisms. Just as for the mutation load, this limit can be evaded by a particular form of negative epistasis. A more robust limit is set by the variance in reproductive success. This suggests that selection accumulates information most efficiently in the infinitesimal regime, when selection on individual alleles is weak, and comparable with random drift. A review of evidence on selection strength suggests that although most variance in fitness may be because of alleles with large Nes, substantial amounts of adaptation may be because of alleles in the infinitesimal regime, in which epistasis has modest effects.}, author = {Barton, Nicholas H}, journal = {Heredity}, pages = {96 -- 109}, publisher = {Nature Publishing Group}, title = {{How does epistasis influence the response to selection?}}, doi = {10.1038/hdy.2016.109}, volume = {118}, year = {2017}, } @article{1207, abstract = {The eigenvalue distribution of the sum of two large Hermitian matrices, when one of them is conjugated by a Haar distributed unitary matrix, is asymptotically given by the free convolution of their spectral distributions. We prove that this convergence also holds locally in the bulk of the spectrum, down to the optimal scales larger than the eigenvalue spacing. The corresponding eigenvectors are fully delocalized. Similar results hold for the sum of two real symmetric matrices, when one is conjugated by Haar orthogonal matrix.}, author = {Bao, Zhigang and Erdös, László and Schnelli, Kevin}, issn = {00103616}, journal = {Communications in Mathematical Physics}, number = {3}, pages = {947 -- 990}, publisher = {Springer}, title = {{Local law of addition of random matrices on optimal scale}}, doi = {10.1007/s00220-016-2805-6}, volume = {349}, year = {2017}, } @article{1208, abstract = {We study parameter estimation in linear Gaussian covariance models, which are p-dimensional Gaussian models with linear constraints on the covariance matrix. Maximum likelihood estimation for this class of models leads to a non-convex optimization problem which typically has many local maxima. Using recent results on the asymptotic distribution of extreme eigenvalues of the Wishart distribution, we provide sufficient conditions for any hill climbing method to converge to the global maximum. Although we are primarily interested in the case in which n≫p, the proofs of our results utilize large sample asymptotic theory under the scheme n/p→γ>1. Remarkably, our numerical simulations indicate that our results remain valid for p as small as 2. An important consequence of this analysis is that, for sample sizes n≃14p, maximum likelihood estimation for linear Gaussian covariance models behaves as if it were a convex optimization problem. © 2016 The Royal Statistical Society and Blackwell Publishing Ltd.}, author = {Zwiernik, Piotr and Uhler, Caroline and Richards, Donald}, issn = {13697412}, journal = {Journal of the Royal Statistical Society. Series B: Statistical Methodology}, number = {4}, pages = {1269 -- 1292}, publisher = {Wiley-Blackwell}, title = {{Maximum likelihood estimation for linear Gaussian covariance models}}, doi = {10.1111/rssb.12217}, volume = {79}, year = {2017}, } @article{1211, abstract = {Systems such as fluid flows in channels and pipes or the complex Ginzburg–Landau system, defined over periodic domains, exhibit both continuous symmetries, translational and rotational, as well as discrete symmetries under spatial reflections or complex conjugation. The simplest, and very common symmetry of this type is the equivariance of the defining equations under the orthogonal group O(2). We formulate a novel symmetry reduction scheme for such systems by combining the method of slices with invariant polynomial methods, and show how it works by applying it to the Kuramoto–Sivashinsky system in one spatial dimension. As an example, we track a relative periodic orbit through a sequence of bifurcations to the onset of chaos. Within the symmetry-reduced state space we are able to compute and visualize the unstable manifolds of relative periodic orbits, their torus bifurcations, a transition to chaos via torus breakdown, and heteroclinic connections between various relative periodic orbits. It would be very hard to carry through such analysis in the full state space, without a symmetry reduction such as the one we present here.}, author = {Budanur, Nazmi B and Cvitanović, Predrag}, journal = {Journal of Statistical Physics}, number = {3-4}, pages = {636--655}, publisher = {Springer}, title = {{Unstable manifolds of relative periodic orbits in the symmetry reduced state space of the Kuramoto–Sivashinsky system}}, doi = {10.1007/s10955-016-1672-z}, volume = {167}, year = {2017}, } @inbook{1213, abstract = {Bacterial cytokinesis is commonly initiated by the Z-ring, a dynamic cytoskeletal structure that assembles at the site of division. Its primary component is FtsZ, a tubulin-like GTPase, that like its eukaryotic relative forms protein filaments in the presence of GTP. Since the discovery of the Z-ring 25 years ago, various models for the role of FtsZ have been suggested. However, important information about the architecture and dynamics of FtsZ filaments during cytokinesis is still missing. One reason for this lack of knowledge has been the small size of bacteria, which has made it difficult to resolve the orientation and dynamics of individual FtsZ filaments in the Z-ring. While superresolution microscopy experiments have helped to gain more information about the organization of the Z-ring in the dividing cell, they were not yet able to elucidate a mechanism of how FtsZ filaments reorganize during assembly and disassembly of the Z-ring. In this chapter, we explain how to use an in vitro reconstitution approach to investigate the self-organization of FtsZ filaments recruited to a biomimetic lipid bilayer by its membrane anchor FtsA. We show how to perform single-molecule experiments to study the behavior of individual FtsZ monomers during the constant reorganization of the FtsZ-FtsA filament network. We describe how to analyze the dynamics of single molecules and explain why this information can help to shed light onto possible mechanism of Z-ring constriction. We believe that similar experimental approaches will be useful to study the mechanism of membrane-based polymerization of other cytoskeletal systems, not only from prokaryotic but also eukaryotic origin.}, author = {Baranova, Natalia and Loose, Martin}, booktitle = {Cytokinesis}, editor = {Echard, Arnaud }, issn = {0091679X}, pages = {355 -- 370}, publisher = {Academic Press}, title = {{Single-molecule measurements to study polymerization dynamics of FtsZ-FtsA copolymers}}, doi = {10.1016/bs.mcb.2016.03.036}, volume = {137}, year = {2017}, } @article{12193, abstract = {DNA methylation regulates eukaryotic gene expression and is extensively reprogrammed during animal development. However, whether developmental methylation reprogramming during the sporophytic life cycle of flowering plants regulates genes is presently unknown. Here we report a distinctive gene-targeted RNA-directed DNA methylation (RdDM) activity in the Arabidopsis thaliana male sexual lineage that regulates gene expression in meiocytes. Loss of sexual-lineage-specific RdDM causes mis-splicing of the MPS1 gene (also known as PRD2), thereby disrupting meiosis. Our results establish a regulatory paradigm in which de novo methylation creates a cell-lineage-specific epigenetic signature that controls gene expression and contributes to cellular function in flowering plants.}, author = {Walker, James and Gao, Hongbo and Zhang, Jingyi and Aldridge, Billy and Vickers, Martin and Higgins, James D. and Feng, Xiaoqi}, issn = {1546-1718}, journal = {Nature Genetics}, keywords = {Genetics}, number = {1}, pages = {130--137}, publisher = {Nature Research}, title = {{Sexual-lineage-specific DNA methylation regulates meiosis in Arabidopsis}}, doi = {10.1038/s41588-017-0008-5}, volume = {50}, year = {2017}, } @article{1228, abstract = {Since 2006, reprogrammed cells have increasingly been used as a biomedical research technique in addition to neuro-psychiatric methods. These rapidly evolving techniques allow for the generation of neuronal sub-populations, and have sparked interest not only in monogenetic neuro-psychiatric diseases, but also in poly-genetic and poly-aetiological disorders such as schizophrenia (SCZ) and bipolar disorder (BPD). This review provides a summary of 19 publications on reprogrammed adult somatic cells derived from patients with SCZ, and five publications using this technique in patients with BPD. As both disorders are complex and heterogeneous, there is a plurality of hypotheses to be tested in vitro. In SCZ, data on alterations of dopaminergic transmission in vitro are sparse, despite the great explanatory power of the so-called DA hypothesis of SCZ. Some findings correspond to perturbations of cell energy metabolism, and observations in reprogrammed cells suggest neuro-developmental alterations. Some studies also report on the efficacy of medicinal compounds to revert alterations observed in cellular models. However, due to the paucity of replication studies, no comprehensive conclusions can be drawn from studies using reprogrammed cells at the present time. In the future, findings from cell culture methods need to be integrated with clinical, epidemiological, pharmacological and imaging data in order to generate a more comprehensive picture of SCZ and BPD.}, author = {Sauerzopf, Ulrich and Sacco, Roberto and Novarino, Gaia and Niello, Marco and Weidenauer, Ana and Praschak Rieder, Nicole and Sitte, Harald and Willeit, Matthaeus}, journal = {European Journal of Neuroscience}, number = {1}, pages = {45 -- 57}, publisher = {Wiley-Blackwell}, title = {{Are reprogrammed cells a useful tool for studying dopamine dysfunction in psychotic disorders? A review of the current evidence}}, doi = {10.1111/ejn.13418}, volume = {45}, year = {2017}, } @inproceedings{12905, author = {Schlögl, Alois and Kiss, Janos}, booktitle = {AHPC17 – Austrian HPC Meeting 2017}, location = {Grundlsee, Austria}, pages = {28}, publisher = {FSP Scientific Computing}, title = {{Scientific Computing at IST Austria}}, year = {2017}, } @article{1294, abstract = {We study controller synthesis problems for finite-state Markov decision processes, where the objective is to optimize the expected mean-payoff performance and stability (also known as variability in the literature). We argue that the basic notion of expressing the stability using the statistical variance of the mean payoff is sometimes insufficient, and propose an alternative definition. We show that a strategy ensuring both the expected mean payoff and the variance below given bounds requires randomization and memory, under both the above definitions. We then show that the problem of finding such a strategy can be expressed as a set of constraints.}, author = {Brázdil, Tomáš and Chatterjee, Krishnendu and Forejt, Vojtěch and Kučera, Antonín}, journal = {Journal of Computer and System Sciences}, pages = {144 -- 170}, publisher = {Elsevier}, title = {{Trading performance for stability in Markov decision processes}}, doi = {10.1016/j.jcss.2016.09.009}, volume = {84}, year = {2017}, } @misc{9707, abstract = {Branching morphogenesis of the epithelial ureteric bud forms the renal collecting duct system and is critical for normal nephron number, while low nephron number is implicated in hypertension and renal disease. Ureteric bud growth and branching requires GDNF signaling from the surrounding mesenchyme to cells at the ureteric bud tips, via the Ret receptor tyrosine kinase and coreceptor Gfrα1; Ret signaling up-regulates transcription factors Etv4 and Etv5, which are also critical for branching. Despite extensive knowledge of the genetic control of these events, it is not understood, at the cellular level, how renal branching morphogenesis is achieved or how Ret signaling influences epithelial cell behaviors to promote this process. Analysis of chimeric embryos previously suggested a role for Ret signaling in promoting cell rearrangements in the nephric duct, but this method was unsuited to study individual cell behaviors during ureteric bud branching. Here, we use Mosaic Analysis with Double Markers (MADM), combined with organ culture and time-lapse imaging, to trace the movements and divisions of individual ureteric bud tip cells. We first examine wild-type clones and then Ret or Etv4 mutant/wild-type clones in which the mutant and wild-type sister cells are differentially and heritably marked by green and red fluorescent proteins. We find that, in normal kidneys, most individual tip cells behave as self-renewing progenitors, some of whose progeny remain at the tips while others populate the growing UB trunks. In Ret or Etv4 MADM clones, the wild-type cells generated at a UB tip are much more likely to remain at, or move to, the new tips during branching and elongation, while their Ret−/− or Etv4−/− sister cells tend to lag behind and contribute only to the trunks. By tracking successive mitoses in a cell lineage, we find that Ret signaling has little effect on proliferation, in contrast to its effects on cell movement. Our results show that Ret/Etv4 signaling promotes directed cell movements in the ureteric bud tips, and suggest a model in which these cell movements mediate branching morphogenesis.}, author = {Riccio, Paul and Cebrián, Christina and Zong, Hui and Hippenmeyer, Simon and Costantini, Frank}, publisher = {Dryad}, title = {{Data from: Ret and Etv4 promote directed movements of progenitor cells during renal branching morphogenesis}}, doi = {10.5061/dryad.pk16b}, year = {2017}, } @misc{9709, abstract = {Across the nervous system, certain population spiking patterns are observed far more frequently than others. A hypothesis about this structure is that these collective activity patterns function as population codewords–collective modes–carrying information distinct from that of any single cell. We investigate this phenomenon in recordings of ∼150 retinal ganglion cells, the retina’s output. We develop a novel statistical model that decomposes the population response into modes; it predicts the distribution of spiking activity in the ganglion cell population with high accuracy. We found that the modes represent localized features of the visual stimulus that are distinct from the features represented by single neurons. Modes form clusters of activity states that are readily discriminated from one another. When we repeated the same visual stimulus, we found that the same mode was robustly elicited. These results suggest that retinal ganglion cells’ collective signaling is endowed with a form of error-correcting code–a principle that may hold in brain areas beyond retina.}, author = {Prentice, Jason and Marre, Olivier and Ioffe, Mark and Loback, Adrianna and Tkačik, Gašper and Berry, Michael}, publisher = {Dryad}, title = {{Data from: Error-robust modes of the retinal population code}}, doi = {10.5061/dryad.1f1rc}, year = {2017}, } @misc{9842, abstract = {Mathematica notebooks used to generate figures.}, author = {Etheridge, Alison and Barton, Nicholas H}, publisher = {Mendeley Data}, title = {{Data for: Establishment in a new habitat by polygenic adaptation}}, doi = {10.17632/nw68fxzjpm.1}, year = {2017}, } @misc{9844, author = {Nikolic, Nela and Schreiber, Frank and Dal Co, Alma and Kiviet, Daniel and Bergmiller, Tobias and Littmann, Sten and Kuypers, Marcel and Ackermann, Martin}, publisher = {Public Library of Science}, title = {{Source data for figures and tables}}, doi = {10.1371/journal.pgen.1007122.s018}, year = {2017}, } @misc{9845, abstract = {Estimates of 13 C-arabinose and 2 H-glucose uptake from the fractions of heavy isotopes measured in single cells}, author = {Nikolic, Nela and Schreiber, Frank and Dal Co, Alma and Kiviet, Daniel and Bergmiller, Tobias and Littmann, Sten and Kuypers, Marcel and Ackermann, Martin}, publisher = {Public Library of Science}, title = {{Mathematical model}}, doi = {10.1371/journal.pgen.1007122.s017}, year = {2017}, } @misc{9846, author = {Nikolic, Nela and Schreiber, Frank and Dal Co, Alma and Kiviet, Daniel and Bergmiller, Tobias and Littmann, Sten and Kuypers, Marcel and Ackermann, Martin}, publisher = {Public Library of Science}, title = {{Supplementary methods}}, doi = {10.1371/journal.pgen.1007122.s016}, year = {2017}, } @misc{9847, abstract = {information on culture conditions, phage mutagenesis, verification and lysate preparation; Raw data}, author = {Pleska, Maros and Guet, Calin C}, publisher = {The Royal Society}, title = {{Supplementary materials and methods; Full data set from effects of mutations in phage restriction sites during escape from restriction–modification}}, doi = {10.6084/m9.figshare.5633917.v1}, year = {2017}, }