@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}, } @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}, } @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{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{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{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{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{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}, } @inproceedings{1174, abstract = {Security of cryptographic applications is typically defined by security games. The adversary, within certain resources, cannot win with probability much better than 0 (for unpredictability applications, like one-way functions) or much better than 1/2 (indistinguishability applications for instance encryption schemes). In so called squared-friendly applications the winning probability of the adversary, for different values of the application secret randomness, is not only close to 0 or 1/2 on average, but also concentrated in the sense that its second central moment is small. The class of squared-friendly applications, which contains all unpredictability applications and many indistinguishability applications, is particularly important for key derivation. Barak et al. observed that for square-friendly applications one can beat the "RT-bound", extracting secure keys with significantly smaller entropy loss. In turn Dodis and Yu showed that in squared-friendly applications one can directly use a "weak" key, which has only high entropy, as a secure key. In this paper we give sharp lower bounds on square security assuming security for "weak" keys. We show that any application which is either (a) secure with weak keys or (b) allows for entropy savings for keys derived by universal hashing, must be square-friendly. Quantitatively, our lower bounds match the positive results of Dodis and Yu and Barak et al. (TCC\'13, CRYPTO\'11) Hence, they can be understood as a general characterization of squared-friendly applications. While the positive results on squared-friendly applications where derived by one clever application of the Cauchy-Schwarz Inequality, for tight lower bounds we need more machinery. In our approach we use convex optimization techniques and some theory of circular matrices.}, author = {Skórski, Maciej}, issn = {18688969}, location = {Hannover, Germany}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Lower bounds on key derivation for square-friendly applications}}, doi = {10.4230/LIPIcs.STACS.2017.57}, volume = {66}, year = {2017}, } @inproceedings{1176, abstract = {The algorithm Argon2i-B of Biryukov, Dinu and Khovratovich is currently being considered by the IRTF (Internet Research Task Force) as a new de-facto standard for password hashing. An older version (Argon2i-A) of the same algorithm was chosen as the winner of the recent Password Hashing Competition. An important competitor to Argon2i-B is the recently introduced Balloon Hashing (BH) algorithm of Corrigan-Gibs, Boneh and Schechter. A key security desiderata for any such algorithm is that evaluating it (even using a custom device) requires a large amount of memory amortized across multiple instances. Alwen and Blocki (CRYPTO 2016) introduced a class of theoretical attacks against Argon2i-A and BH. While these attacks yield large asymptotic reductions in the amount of memory, it was not, a priori, clear if (1) they can be extended to the newer Argon2i-B, (2) the attacks are effective on any algorithm for practical parameter ranges (e.g., 1GB of memory) and (3) if they can be effectively instantiated against any algorithm under realistic hardware constrains. In this work we answer all three of these questions in the affirmative for all three algorithms. This is also the first work to analyze the security of Argon2i-B. In more detail, we extend the theoretical attacks of Alwen and Blocki (CRYPTO 2016) to the recent Argon2i-B proposal demonstrating severe asymptotic deficiencies in its security. Next we introduce several novel heuristics for improving the attack's concrete memory efficiency even when on-chip memory bandwidth is bounded. We then simulate our attacks on randomly sampled Argon2i-A, Argon2i-B and BH instances and measure the resulting memory consumption for various practical parameter ranges and for a variety of upperbounds on the amount of parallelism available to the attacker. Finally we describe, implement, and test a new heuristic for applying the Alwen-Blocki attack to functions employing a technique developed by Corrigan-Gibs et al. for improving concrete security of memory-hard functions. We analyze the collected data and show the effects various parameters have on the memory consumption of the attack. In particular, we can draw several interesting conclusions about the level of security provided by these functions. · For the Alwen-Blocki attack to fail against practical memory parameters, Argon2i-B must be instantiated with more than 10 passes on memory - beyond the "paranoid" parameter setting in the current IRTF proposal. · The technique of Corrigan-Gibs for improving security can also be overcome by the Alwen-Blocki attack under realistic hardware constraints. · On a positive note, both the asymptotic and concrete security of Argon2i-B seem to improve on that of Argon2i-A.}, author = {Alwen, Joel F and Blocki, Jeremiah}, isbn = {978-150905761-0}, location = {Paris, France}, publisher = {IEEE}, title = {{Towards practical attacks on Argon2i and balloon hashing}}, doi = {10.1109/EuroSP.2017.47}, year = {2017}, } @article{1187, abstract = {We construct efficient authentication protocols and message authentication codes (MACs) whose security can be reduced to the learning parity with noise (LPN) problem. Despite a large body of work—starting with the (Formula presented.) protocol of Hopper and Blum in 2001—until now it was not even known how to construct an efficient authentication protocol from LPN which is secure against man-in-the-middle attacks. A MAC implies such a (two-round) protocol.}, author = {Kiltz, Eike and Pietrzak, Krzysztof Z and Venturi, Daniele and Cash, David and Jain, Abhishek}, journal = {Journal of Cryptology}, number = {4}, pages = {1238 -- 1275}, publisher = {Springer}, title = {{Efficient authentication from hard learning problems}}, doi = {10.1007/s00145-016-9247-3}, volume = {30}, year = {2017}, } @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}, } @article{1180, abstract = {In this article we define an algebraic vertex of a generalized polyhedron and show that the set of algebraic vertices is the smallest set of points needed to define the polyhedron. We prove that the indicator function of a generalized polytope P is a linear combination of indicator functions of simplices whose vertices are algebraic vertices of P. We also show that the indicator function of any generalized polyhedron is a linear combination, with integer coefficients, of indicator functions of cones with apices at algebraic vertices and line-cones. The concept of an algebraic vertex is closely related to the Fourier–Laplace transform. We show that a point v is an algebraic vertex of a generalized polyhedron P if and only if the tangent cone of P, at v, has non-zero Fourier–Laplace transform.}, author = {Akopyan, Arseniy and Bárány, Imre and Robins, Sinai}, issn = {00018708}, journal = {Advances in Mathematics}, pages = {627 -- 644}, publisher = {Academic Press}, title = {{Algebraic vertices of non-convex polyhedra}}, doi = {10.1016/j.aim.2016.12.026}, volume = {308}, year = {2017}, } @article{1159, abstract = {Auxin steers numerous physiological processes in plants, making the tight control of its endogenous levels and spatiotemporal distribution a necessity. This regulation is achieved by different mechanisms, including auxin biosynthesis, metabolic conversions, degradation, and transport. Here, we introduce cis-cinnamic acid (c-CA) as a novel and unique addition to a small group of endogenous molecules affecting in planta auxin concentrations. c-CA is the photo-isomerization product of the phenylpropanoid pathway intermediate trans-CA (t-CA). When grown on c-CA-containing medium, an evolutionary diverse set of plant species were shown to exhibit phenotypes characteristic for high auxin levels, including inhibition of primary root growth, induction of root hairs, and promotion of adventitious and lateral rooting. By molecular docking and receptor binding assays, we showed that c-CA itself is neither an auxin nor an anti-auxin, and auxin profiling data revealed that c-CA does not significantly interfere with auxin biosynthesis. Single cell-based auxin accumulation assays showed that c-CA, and not t-CA, is a potent inhibitor of auxin efflux. Auxin signaling reporters detected changes in spatiotemporal distribution of the auxin response along the root of c-CA-treated plants, and long-distance auxin transport assays showed no inhibition of rootward auxin transport. Overall, these results suggest that the phenotypes of c-CA-treated plants are the consequence of a local change in auxin accumulation, induced by the inhibition of auxin efflux. This work reveals a novel mechanism how plants may regulate auxin levels and adds a novel, naturally occurring molecule to the chemical toolbox for the studies of auxin homeostasis.}, author = {Steenackers, Ward and Klíma, Petr and Quareshy, Mussa and Cesarino, Igor and Kumpf, Robert and Corneillie, Sander and Araújo, Pedro and Viaene, Tom and Goeminne, Geert and Nowack, Moritz and Ljung, Karin and Friml, Jirí and Blakeslee, Joshua and Novák, Ondřej and Zažímalová, Eva and Napier, Richard and Boerjan, Wout and Vanholme, Bartel}, issn = {0032-0889}, journal = {Plant Physiology}, number = {1}, pages = {552 -- 565}, publisher = {American Society of Plant Biologists}, title = {{Cis-cinnamic acid is a novel natural auxin efflux inhibitor that promotes lateral root formation}}, doi = {10.1104/pp.16.00943}, volume = {173}, year = {2017}, } @article{1169, abstract = {Dispersal is a crucial factor in natural evolution, since it determines the habitat experienced by any population and defines the spatial scale of interactions between individuals. There is compelling evidence for systematic differences in dispersal characteristics within the same population, i.e., genotype-dependent dispersal. The consequences of genotype-dependent dispersal on other evolutionary phenomena, however, are poorly understood. In this article we investigate the effect of genotype-dependent dispersal on spatial gene frequency patterns, using a generalization of the classical diffusion model of selection and dispersal. Dispersal is characterized by the variance of dispersal (diffusion coefficient) and the mean displacement (directional advection term). We demonstrate that genotype-dependent dispersal may change the qualitative behavior of Fisher waves, which change from being “pulled” to being “pushed” wave fronts as the discrepancy in dispersal between genotypes increases. The speed of any wave is partitioned into components due to selection, genotype-dependent variance of dispersal, and genotype-dependent mean displacement. We apply our findings to wave fronts maintained by selection against heterozygotes. Furthermore, we identify a benefit of increased variance of dispersal, quantify its effect on the speed of the wave, and discuss the implications for the evolution of dispersal strategies.}, author = {Novak, Sebastian and Kollár, Richard}, issn = {00166731}, journal = {Genetics}, number = {1}, pages = {367 -- 374}, publisher = {Genetics Society of America}, title = {{Spatial gene frequency waves under genotype dependent dispersal}}, doi = {10.1534/genetics.116.193946}, volume = {205}, year = {2017}, } @article{1160, abstract = {We investigate fundamental nonlinear dynamics of ferrofluidic Taylor-Couette flow - flow confined be-tween two concentric independently rotating cylinders - consider small aspect ratio by solving the ferro-hydrodynamical equations, carrying out systematic bifurcation analysis. Without magnetic field, we find steady flow patterns, previously observed with a simple fluid, such as those containing normal one- or two vortex cells, as well as anomalous one-cell and twin-cell flow states. However, when a symmetry-breaking transverse magnetic field is present, all flow states exhibit stimulated, finite two-fold mode. Various bifurcations between steady and unsteady states can occur, corresponding to the transitions between the two-cell and one-cell states. While unsteady, axially oscillating flow states can arise, we also detect the emergence of new unsteady flow states. In particular, we uncover two new states: one contains only the azimuthally oscillating solution in the configuration of the twin-cell flow state, and an-other a rotating flow state. Topologically, these flow states are a limit cycle and a quasiperiodic solution on a two-torus, respectively. Emergence of new flow states in addition to observed ones with classical fluid, indicates that richer but potentially more controllable dynamics in ferrofluidic flows, as such flow states depend on the external magnetic field.}, author = {Altmeyer, Sebastian and Do, Younghae and Lai, Ying}, issn = {20452322}, journal = {Scientific Reports}, publisher = {Nature Publishing Group}, title = {{Dynamics of ferrofluidic flow in the Taylor-Couette system with a small aspect ratio}}, doi = {10.1038/srep40012}, volume = {7}, year = {2017}, } @article{1162, abstract = {Selected universal experimental properties of high-temperature superconducting (HTS) cuprates have been singled out in the last decade. One of the pivotal challenges in this field is the designation of a consistent interpretation framework within which we can describe quantitatively the universal features of those systems. Here we analyze in a detailed manner the principal experimental data and compare them quantitatively with the approach based on a single-band model of strongly correlated electrons supplemented with strong antiferromagnetic (super)exchange interaction (the so-called t−J−U model). The model rationale is provided by estimating its microscopic parameters on the basis of the three-band approach for the Cu-O plane. We use our original full Gutzwiller wave-function solution by going beyond the renormalized mean-field theory (RMFT) in a systematic manner. Our approach reproduces very well the observed hole doping (δ) dependence of the kinetic-energy gain in the superconducting phase, one of the principal non-Bardeen-Cooper-Schrieffer features of the cuprates. The calculated Fermi velocity in the nodal direction is practically δ-independent and its universal value agrees very well with that determined experimentally. Also, a weak doping dependence of the Fermi wave vector leads to an almost constant value of the effective mass in a pure superconducting phase which is both observed in experiment and reproduced within our approach. An assessment of the currently used models (t−J, Hubbard) is carried out and the results of the canonical RMFT as a zeroth-order solution are provided for comparison to illustrate the necessity of the introduced higher-order contributions.}, author = {Spałek, Jozef and Zegrodnik, Michał and Kaczmarczyk, Jan}, issn = {24699950}, journal = {Physical Review B - Condensed Matter and Materials Physics}, number = {2}, publisher = {American Physical Society}, title = {{Universal properties of high temperature superconductors from real space pairing t-J-U model and its quantitative comparison with experiment}}, doi = {10.1103/PhysRevB.95.024506}, volume = {95}, year = {2017}, } @article{1152, abstract = {We propose a new memetic strategy that can solve the multi-physics, complex inverse problems, formulated as the multi-objective optimization ones, in which objectives are misfits between the measured and simulated states of various governing processes. The multi-deme structure of the strategy allows for both, intensive, relatively cheap exploration with a moderate accuracy and more accurate search many regions of Pareto set in parallel. The special type of selection operator prefers the coherent alternative solutions, eliminating artifacts appearing in the particular processes. The additional accuracy increment is obtained by the parallel convex searches applied to the local scalarizations of the misfit vector. The strategy is dedicated for solving ill-conditioned problems, for which inverting the single physical process can lead to the ambiguous results. The skill of the selection in artifact elimination is shown on the benchmark problem, while the whole strategy was applied for identification of oil deposits, where the misfits are related to various frequencies of the magnetic and electric waves of the magnetotelluric measurements. 2016 Elsevier B.V.}, author = {Gajda-Zagorska, Ewa P and Schaefer, Robert and Smołka, Maciej and Pardo, David and Alvarez Aramberri, Julen}, issn = {18777503}, journal = {Journal of Computational Science}, pages = {85 -- 94}, publisher = {Elsevier}, title = {{A multi objective memetic inverse solver reinforced by local optimization methods}}, doi = {10.1016/j.jocs.2016.06.007}, volume = {18}, year = {2017}, } @article{1168, abstract = {Optimum experimental design theory has recently been extended for parameter estimation in copula models. The use of these models allows one to gain in flexibility by considering the model parameter set split into marginal and dependence parameters. However, this separation also leads to the natural issue of estimating only a subset of all model parameters. In this work, we treat this problem with the application of the (Formula presented.)-optimality to copula models. First, we provide an extension of the corresponding equivalence theory. Then, we analyze a wide range of flexible copula models to highlight the usefulness of (Formula presented.)-optimality in many possible scenarios. Finally, we discuss how the usage of the introduced design criterion also relates to the more general issue of copula selection and optimal design for model discrimination.}, author = {Perrone, Elisa and Rappold, Andreas and Müller, Werner}, journal = {Statistical Methods and Applications}, number = {3}, pages = {403 -- 418}, publisher = {Springer}, title = {{D inf s optimality in copula models}}, doi = {10.1007/s10260-016-0375-6}, volume = {26}, year = {2017}, } @article{1163, abstract = {We investigate the effect of the electron-hole (e-h) symmetry breaking on d-wave superconductivity induced by non-local effects of correlations in the generalized Hubbard model. The symmetry breaking is introduced in a two-fold manner: by the next-to-nearest neighbor hopping of electrons and by the charge-bond interaction - the off-diagonal term of the Coulomb potential. Both terms lead to a pronounced asymmetry of the superconducting order parameter. The next-to-nearest neighbor hopping enhances superconductivity for h-doping, while diminishes it for e-doping. The charge-bond interaction alone leads to the opposite effect and, additionally, to the kinetic-energy gain upon condensation in the underdoped regime. With both terms included, with similar amplitudes, the height of the superconducting dome and the critical doping remain in favor of h-doping. The influence of the charge-bond interaction on deviations from symmetry of the shape of the gap at the Fermi surface in the momentum space is briefly discussed.}, author = {Wysokiński, Marcin and Kaczmarczyk, Jan}, issn = {09538984}, journal = {Journal of Physics: Condensed Matter}, number = {8}, publisher = {IOP Publishing Ltd.}, title = {{Unconventional superconductivity in generalized Hubbard model role of electron–hole symmetry breaking terms}}, doi = {10.1088/1361-648X/aa532f}, volume = {29}, year = {2017}, } @article{1173, abstract = {We introduce the Voronoi functional of a triangulation of a finite set of points in the Euclidean plane and prove that among all geometric triangulations of the point set, the Delaunay triangulation maximizes the functional. This result neither extends to topological triangulations in the plane nor to geometric triangulations in three and higher dimensions.}, author = {Edelsbrunner, Herbert and Glazyrin, Alexey and Musin, Oleg and Nikitenko, Anton}, issn = {02099683}, journal = {Combinatorica}, number = {5}, pages = {887 -- 910}, publisher = {Springer}, title = {{The Voronoi functional is maximized by the Delaunay triangulation in the plane}}, doi = {10.1007/s00493-016-3308-y}, volume = {37}, year = {2017}, } @article{1161, abstract = {Coordinated changes of cell shape are often the result of the excitable, wave-like dynamics of the actin cytoskeleton. New work shows that, in migrating cells, protrusion waves arise from mechanochemical crosstalk between adhesion sites, membrane tension and the actin protrusive machinery.}, author = {Müller, Jan and Sixt, Michael K}, issn = {09609822}, journal = {Current Biology}, number = {1}, pages = {R24 -- R25}, publisher = {Cell Press}, title = {{Cell migration: Making the waves}}, doi = {10.1016/j.cub.2016.11.035}, volume = {27}, year = {2017}, } @inproceedings{1116, abstract = {Time-triggered switched networks are a deterministic communication infrastructure used by real-time distributed embedded systems. Due to the criticality of the applications running over them, developers need to ensure that end-to-end communication is dependable and predictable. Traditional approaches assume static networks that are not flexible to changes caused by reconfigurations or, more importantly, faults, which are dealt with in the application using redundancy. We adopt the concept of handling faults in the switches from non-real-time networks while maintaining the required predictability. We study a class of forwarding schemes that can handle various types of failures. We consider probabilistic failures. We study a class of forwarding schemes that can handle various types of failures. We consider probabilistic failures. For a given network with a forwarding scheme and a constant ℓ, we compute the {\em score} of the scheme, namely the probability (induced by faults) that at least ℓ messages arrive on time. We reduce the scoring problem to a reachability problem on a Markov chain with a "product-like" structure. Its special structure allows us to reason about it symbolically, and reduce the scoring problem to #SAT. Our solution is generic and can be adapted to different networks and other contexts. Also, we show the computational complexity of the scoring problem is #P-complete, and we study methods to estimate the score. We evaluate the effectiveness of our techniques with an implementation. }, author = {Avni, Guy and Goel, Shubham and Henzinger, Thomas A and Rodríguez Navas, Guillermo}, issn = {03029743}, location = {Uppsala, Sweden}, pages = {169 -- 187}, publisher = {Springer}, title = {{Computing scores of forwarding schemes in switched networks with probabilistic faults}}, doi = {10.1007/978-3-662-54580-5_10}, volume = {10206}, year = {2017}, } @article{1118, abstract = {Sharp wave-ripple (SWR) oscillations play a key role in memory consolidation during non-rapid eye movement sleep, immobility, and consummatory behavior. However, whether temporally modulated synaptic excitation or inhibition underlies the ripples is controversial. To address this question, we performed simultaneous recordings of excitatory and inhibitory postsynaptic currents (EPSCs and IPSCs) and local field potentials (LFPs) in the CA1 region of awake mice in vivo. During SWRs, inhibition dominated over excitation, with a peak conductance ratio of 4.1 ± 0.5. Furthermore, the amplitude of SWR-associated IPSCs was positively correlated with SWR magnitude, whereas that of EPSCs was not. Finally, phase analysis indicated that IPSCs were phase-locked to individual ripple cycles, whereas EPSCs were uniformly distributed in phase space. Optogenetic inhibition indicated that PV+ interneurons provided a major contribution to SWR-associated IPSCs. Thus, phasic inhibition, but not excitation, shapes SWR oscillations in the hippocampal CA1 region in vivo.}, author = {Gan, Jian and Weng, Shih-Ming and Pernia-Andrade, Alejandro and Csicsvari, Jozsef L and Jonas, Peter M}, journal = {Neuron}, number = {2}, pages = {308 -- 314}, publisher = {Elsevier}, title = {{Phase-locked inhibition, but not excitation, underlies hippocampal ripple oscillations in awake mice in vivo}}, doi = {10.1016/j.neuron.2016.12.018}, volume = {93}, year = {2017}, } @article{1117, abstract = {GABAergic synapses in brain circuits generate inhibitory output signals with submillisecond latency and temporal precision. Whether the molecular identity of the release sensor contributes to these signaling properties remains unclear. Here, we examined the Ca^2+ sensor of exocytosis at GABAergic basket cell (BC) to Purkinje cell (PC) synapses in cerebellum. Immunolabeling suggested that BC terminals selectively expressed synaptotagmin 2 (Syt2), whereas synaptotagmin 1 (Syt1) was enriched in excitatory terminals. Genetic elimination of Syt2 reduced action potential-evoked release to ∼10%, identifying Syt2 as the major Ca^2+ sensor at BC-PC synapses. Differential adenovirus-mediated rescue revealed that Syt2 triggered release with shorter latency and higher temporal precision and mediated faster vesicle pool replenishment than Syt1. Furthermore, deletion of Syt2 severely reduced and delayed disynaptic inhibition following parallel fiber stimulation. Thus, the selective use of Syt2 as release sensor at BC-PC synapses ensures fast and efficient feedforward inhibition in cerebellar microcircuits. #bioimagingfacility-author}, author = {Chen, Chong and Arai, Itaru and Satterield, Rachel and Young, Samuel and Jonas, Peter M}, issn = {22111247}, journal = {Cell Reports}, number = {3}, pages = {723 -- 736}, publisher = {Cell Press}, title = {{Synaptotagmin 2 is the fast Ca2+ sensor at a central inhibitory synapse}}, doi = {10.1016/j.celrep.2016.12.067}, volume = {18}, year = {2017}, } @article{1132, abstract = {The hippocampus is thought to initiate systems-wide mnemonic processes through the reactivation of previously acquired spatial and episodic memory traces, which can recruit the entorhinal cortex as a first stage of memory redistribution to other brain areas. Hippocampal reactivation occurs during sharp wave-ripples, in which synchronous network firing encodes sequences of places.We investigated the coordination of this replay by recording assembly activity simultaneously in the CA1 region of the hippocampus and superficial layers of the medial entorhinal cortex. We found that entorhinal cell assemblies can replay trajectories independently of the hippocampus and sharp wave-ripples. This suggests that the hippocampus is not the sole initiator of spatial and episodic memory trace reactivation. Memory systems involved in these processes may include nonhierarchical, parallel components.}, author = {O'Neill, Joseph and Boccara, Charlotte and Stella, Federico and Schönenberger, Philipp and Csicsvari, Jozsef L}, issn = {00368075}, journal = {Science}, number = {6321}, pages = {184 -- 188}, publisher = {American Association for the Advancement of Science}, title = {{Superficial layers of the medial entorhinal cortex replay independently of the hippocampus}}, doi = {10.1126/science.aag2787}, volume = {355}, year = {2017}, } @article{1120, abstract = {The existence of a self-localization transition in the polaron problem has been under an active debate ever since Landau suggested it 83 years ago. Here we reveal the self-localization transition for the rotational analogue of the polaron -- the angulon quasiparticle. We show that, unlike for the polarons, self-localization of angulons occurs at finite impurity-bath coupling already at the mean-field level. The transition is accompanied by the spherical-symmetry breaking of the angulon ground state and a discontinuity in the first derivative of the ground-state energy. Moreover, the type of the symmetry breaking is dictated by the symmetry of the microscopic impurity-bath interaction, which leads to a number of distinct self-localized states. The predicted effects can potentially be addressed in experiments on cold molecules trapped in superfluid helium droplets and ultracold quantum gases, as well as on electronic excitations in solids and Bose-Einstein condensates. }, author = {Li, Xiang and Seiringer, Robert and Lemeshko, Mikhail}, issn = {24699926}, journal = {Physical Review A}, number = {3}, publisher = {American Physical Society}, title = {{Angular self-localization of impurities rotating in a bosonic bath}}, doi = {10.1103/PhysRevA.95.033608}, volume = {95}, year = {2017}, } @article{1133, abstract = {It is a common knowledge that an effective interaction of a quantum impurity with an electromagnetic field can be screened by surrounding charge carriers, whether mobile or static. Here we demonstrate that very strong, "anomalous" screening can take place in the presence of a neutral, weakly polarizable environment, due to an exchange of orbital angular momentum between the impurity and the bath. Furthermore, we show that it is possible to generalize all phenomena related to isolated impurities in an external field to the case when a many-body environment is present, by casting the problem in terms of the angulon quasiparticle. As a result, the relevant observables such as the effective Rabi frequency, geometric phase, and impurity spatial alignment are straightforward to evaluate in terms of a single parameter: the angular-momentum-dependent screening factor.}, author = {Yakaboylu, Enderalp and Lemeshko, Mikhail}, issn = {00319007}, journal = {Physical Review Letters}, number = {8}, publisher = {American Physical Society}, title = {{Anomalous screening of quantum impurities by a neutral environment}}, doi = {10.1103/PhysRevLett.118.085302}, volume = {118}, year = {2017}, } @article{1119, abstract = {Understanding the behavior of molecules interacting with superfluid helium represents a formidable challenge and, in general, requires approaches relying on large-scale numerical simulations. Here we demonstrate that experimental data collected over the last 20 years provide evidence that molecules immersed in superfluid helium form recently-predicted angulon quasiparticles [Phys. Rev. Lett. 114, 203001 (2015)]. Most importantly, casting the many-body problem in terms of angulons amounts to a drastic simplification and yields effective molecular moments of inertia as straightforward analytic solutions of a simple microscopic Hamiltonian. The outcome of the angulon theory is in good agreement with experiment for a broad range of molecular impurities, from heavy to medium-mass to light species. These results pave the way to understanding molecular rotation in liquid and crystalline phases in terms of the angulon quasiparticle.}, author = {Lemeshko, Mikhail}, issn = {00319007}, journal = {Physical Review Letters}, number = {9}, publisher = {American Physical Society}, title = {{Quasiparticle approach to molecules interacting with quantum solvents}}, doi = {10.1103/PhysRevLett.118.095301}, volume = {118}, year = {2017}, } @article{1110, abstract = {The phytohormone auxin is a major determinant and regulatory component important for plant development. Auxin transport between cells is mediated by a complex system of transporters such as AUX1/LAX, PIN, and ABCB proteins, and their localization and activity is thought to be influenced by phosphatases and kinases. Flavonols have been shown to alter auxin transport activity and changes in flavonol accumulation in the Arabidopsis thaliana rol1-2 mutant cause defects in auxin transport and seedling development. A new mutation in ROOTS CURL IN NPA 1 (RCN1), encoding a regulatory subunit of the phosphatase PP2A, was found to suppress the growth defects of rol1-2 without changing the flavonol content. rol1-2 rcn1-3 double mutants show wild type-like auxin transport activity while levels of free auxin are not affected by rcn1-3. In the rol1-2 mutant, PIN2 shows a flavonol-induced basal-to-apical shift in polar localization which is reversed in the rol1-2 rcn1-3 to basal localization. In vivo analysis of PINOID action, a kinase known to influence PIN protein localization in a PP2A-antagonistic manner, revealed a negative impact of flavonols on PINOID activity. Together, these data suggest that flavonols affect auxin transport by modifying the antagonistic kinase/phosphatase equilibrium.}, author = {Kuhn, Benjamin and Nodzyński, Tomasz and Errafi, Sanae and Bucher, Rahel and Gupta, Shibu and Aryal, Bibek and Dobrev, Petre and Bigler, Laurent and Geisler, Markus and Zažímalová, Eva and Friml, Jirí and Ringli, Christoph}, issn = {20452322}, journal = {Scientific Reports}, publisher = {Nature Publishing Group}, title = {{Flavonol-induced changes in PIN2 polarity and auxin transport in the Arabidopsis thaliana rol1-2 mutant require phosphatase activity}}, doi = {10.1038/srep41906}, volume = {7}, year = {2017}, } @article{1104, abstract = {In the early visual system, cells of the same type perform the same computation in different places of the visual field. How these cells code together a complex visual scene is unclear. A common assumption is that cells of a single-type extract a single-stimulus feature to form a feature map, but this has rarely been observed directly. Using large-scale recordings in the rat retina, we show that a homogeneous population of fast OFF ganglion cells simultaneously encodes two radically different features of a visual scene. Cells close to a moving object code quasilinearly for its position, while distant cells remain largely invariant to the object's position and, instead, respond nonlinearly to changes in the object's speed. We develop a quantitative model that accounts for this effect and identify a disinhibitory circuit that mediates it. Ganglion cells of a single type thus do not code for one, but two features simultaneously. This richer, flexible neural map might also be present in other sensory systems.}, author = {Deny, Stephane and Ferrari, Ulisse and Mace, Emilie and Yger, Pierre and Caplette, Romain and Picaud, Serge and Tkacik, Gasper and Marre, Olivier}, issn = {20411723}, journal = {Nature Communications}, number = {1}, publisher = {Nature Publishing Group}, title = {{Multiplexed computations in retinal ganglion cells of a single type}}, doi = {10.1038/s41467-017-02159-y}, volume = {8}, year = {2017}, } @article{1114, abstract = {Nonequilibrium phase transitions exist in damped-driven open quantum systems when the continuous tuning of an external parameter leads to a transition between two robust steady states. In second-order transitions this change is abrupt at a critical point, whereas in first-order transitions the two phases can coexist in a critical hysteresis domain. Here, we report the observation of a first-order dissipative quantum phase transition in a driven circuit quantum electrodynamics system. It takes place when the photon blockade of the driven cavity-atom system is broken by increasing the drive power. The observed experimental signature is a bimodal phase space distribution with varying weights controlled by the drive strength. Our measurements show an improved stabilization of the classical attractors up to the millisecond range when the size of the quantum system is increased from one to three artificial atoms. The formation of such robust pointer states could be used for new quantum measurement schemes or to investigate multiphoton phases of finite-size, nonlinear, open quantum systems.}, author = {Fink, Johannes M and Dombi, András and Vukics, András and Wallraff, Andreas and Domokos, Peter}, issn = {21603308}, journal = {Physical Review X}, number = {1}, publisher = {American Physical Society}, title = {{Observation of the photon blockade breakdown phase transition}}, doi = {10.1103/PhysRevX.7.011012}, volume = {7}, year = {2017}, } @article{1111, abstract = {Adaptation depends critically on the effects of new mutations and their dependency on the genetic background in which they occur. These two factors can be summarized by the fitness landscape. However, it would require testing all mutations in all backgrounds, making the definition and analysis of fitness landscapes mostly inaccessible. Instead of postulating a particular fitness landscape, we address this problem by considering general classes of landscapes and calculating an upper limit for the time it takes for a population to reach a fitness peak, circumventing the need to have full knowledge about the fitness landscape. We analyze populations in the weak-mutation regime and characterize the conditions that enable them to quickly reach the fitness peak as a function of the number of sites under selection. We show that for additive landscapes there is a critical selection strength enabling populations to reach high-fitness genotypes, regardless of the distribution of effects. This threshold scales with the number of sites under selection, effectively setting a limit to adaptation, and results from the inevitable increase in deleterious mutational pressure as the population adapts in a space of discrete genotypes. Furthermore, we show that for the class of all unimodal landscapes this condition is sufficient but not necessary for rapid adaptation, as in some highly epistatic landscapes the critical strength does not depend on the number of sites under selection; effectively removing this barrier to adaptation.}, author = {Heredia, Jorge and Trubenova, Barbora and Sudholt, Dirk and Paixao, Tiago}, issn = {00166731}, journal = {Genetics}, number = {2}, pages = {803 -- 825}, publisher = {Genetics Society of America}, title = {{Selection limits to adaptive walks on correlated landscapes}}, doi = {10.1534/genetics.116.189340}, volume = {205}, year = {2017}, } @article{1109, abstract = {Rotation of molecules embedded in He nanodroplets is explored by a combination of fs laser-induced alignment experiments and angulon quasiparticle theory. We demonstrate that at low fluence of the fs alignment pulse, the molecule and its solvation shell can be set into coherent collective rotation lasting long enough to form revivals. With increasing fluence, however, the revivals disappear -- instead, rotational dynamics as rapid as for an isolated molecule is observed during the first few picoseconds. Classical calculations trace this phenomenon to transient decoupling of the molecule from its He shell. Our results open novel opportunities for studying non-equilibrium solute-solvent dynamics and quantum thermalization. }, author = {Shepperson, Benjamin and Søndergaard, Anders and Christiansen, Lars and Kaczmarczyk, Jan and Zillich, Robert and Lemeshko, Mikhail and Stapelfeldt, Henrik}, journal = {Physical Review Letters}, number = {20}, publisher = {American Physical Society}, title = {{Laser-induced rotation of iodine molecules in helium nanodroplets: Revivals and breaking-free}}, doi = {10.1103/PhysRevLett.118.203203}, volume = {118}, year = {2017}, } @article{1087, abstract = {Using extensive direct numerical simulations, the dynamics of laminar-turbulent fronts in pipe flow is investigated for Reynolds numbers between and 5500. We here investigate the physical distinction between the fronts of weak and strong slugs both by analysing the turbulent kinetic energy budget and by comparing the downstream front motion to the advection speed of bulk turbulent structures. Our study shows that weak downstream fronts travel slower than turbulent structures in the bulk and correspond to decaying turbulence at the front. At the downstream front speed becomes faster than the advection speed, marking the onset of strong fronts. In contrast to weak fronts, turbulent eddies are generated at strong fronts by feeding on the downstream laminar flow. Our study also suggests that temporal fluctuations of production and dissipation at the downstream laminar-turbulent front drive the dynamical switches between the two types of front observed up to.}, author = {Song, Baofang and Barkley, Dwight and Hof, Björn and Avila, Marc}, issn = {00221120}, journal = {Journal of Fluid Mechanics}, pages = {1045 -- 1059}, publisher = {Cambridge University Press}, title = {{Speed and structure of turbulent fronts in pipe flow}}, doi = {10.1017/jfm.2017.14}, volume = {813}, year = {2017}, } @article{1089, abstract = {We discuss properties of distributions that are multivariate totally positive of order two (MTP2) related to conditional independence. In particular, we show that any independence model generated by an MTP2 distribution is a compositional semigraphoid which is upward-stable and singleton-transitive. In addition, we prove that any MTP2 distribution satisfying an appropriate support condition is faithful to its concentration graph. Finally, we analyze factorization properties of MTP2 distributions and discuss ways of constructing MTP2 distributions; in particular we give conditions on the log-linear parameters of a discrete distribution which ensure MTP2 and characterize conditional Gaussian distributions which satisfy MTP2.}, author = {Fallat, Shaun and Lauritzen, Steffen and Sadeghi, Kayvan and Uhler, Caroline and Wermuth, Nanny and Zwiernik, Piotr}, issn = {00905364}, journal = {Annals of Statistics}, number = {3}, pages = {1152 -- 1184}, publisher = {Institute of Mathematical Statistics}, title = {{Total positivity in Markov structures}}, doi = {10.1214/16-AOS1478}, volume = {45}, year = {2017}, } @article{1080, abstract = {Reconstructing the evolutionary history of metastases is critical for understanding their basic biological principles and has profound clinical implications. Genome-wide sequencing data has enabled modern phylogenomic methods to accurately dissect subclones and their phylogenies from noisy and impure bulk tumour samples at unprecedented depth. However, existing methods are not designed to infer metastatic seeding patterns. Here we develop a tool, called Treeomics, to reconstruct the phylogeny of metastases and map subclones to their anatomic locations. Treeomics infers comprehensive seeding patterns for pancreatic, ovarian, and prostate cancers. Moreover, Treeomics correctly disambiguates true seeding patterns from sequencing artifacts; 7% of variants were misclassified by conventional statistical methods. These artifacts can skew phylogenies by creating illusory tumour heterogeneity among distinct samples. In silico benchmarking on simulated tumour phylogenies across a wide range of sample purities (15–95%) and sequencing depths (25-800 × ) demonstrates the accuracy of Treeomics compared with existing methods.}, author = {Reiter, Johannes and Makohon Moore, Alvin and Gerold, Jeffrey and Božić, Ivana and Chatterjee, Krishnendu and Iacobuzio Donahue, Christine and Vogelstein, Bert and Nowak, Martin}, issn = {20411723}, journal = {Nature Communications}, publisher = {Nature Publishing Group}, title = {{Reconstructing metastatic seeding patterns of human cancers}}, doi = {10.1038/ncomms14114}, volume = {8}, year = {2017}, } @article{1085, abstract = {Sex chromosomes evolve once recombination is halted between a homologous pair of chromosomes. The dominant model of sex chromosome evolution posits that recombination is suppressed between emerging X and Y chromosomes in order to resolve sexual conflict. Here we test this model using whole genome and transcriptome resequencing data in the guppy, a model for sexual selection with many Y-linked colour traits. We show that although the nascent Y chromosome encompasses nearly half of the linkage group, there has been no perceptible degradation of Y chromosome gene content or activity. Using replicate wild populations with differing levels of sexually antagonistic selection for colour, we also show that sexual selection leads to greater expansion of the non-recombining region and increased Y chromosome divergence. These results provide empirical support for longstanding models of sex chromosome catalysis, and suggest an important role for sexual selection and sexual conflict in genome evolution.}, author = {Wright, Alison and Darolti, Iulia and Bloch, Natasha and Oostra, Vicencio and Sandkam, Benjamin and Buechel, Séverine and Kolm, Niclas and Breden, Felix and Vicoso, Beatriz and Mank, Judith}, issn = {20411723}, journal = {Nature Communications}, publisher = {Nature Publishing Group}, title = {{Convergent recombination suppression suggests role of sexual selection in guppy sex chromosome formation}}, doi = {10.1038/ncomms14251}, volume = {8}, year = {2017}, } @article{1084, abstract = {BceRS and PsdRS are paralogous two-component systems in Bacillus subtilis controlling the response to antimicrobial peptides. In the presence of extracellular bacitracin and nisin, respectively, the two response regulators (RRs) bind their target promoters, PbceA or PpsdA, resulting in a strong up-regulation of target gene expression and ultimately antibiotic resistance. Despite high sequence similarity between the RRs BceR and PsdR and their known binding sites, no cross-regulation has been observed between them. We therefore investigated the specificity determinants of PbceA and PpsdA that ensure the insulation of these two paralogous pathways at the RR–promoter interface. In vivo and in vitro analyses demonstrate that the regulatory regions within these two promoters contain three important elements: in addition to the known (main) binding site, we identified a linker region and a secondary binding site that are crucial for functionality. Initial binding to the high-affinity, low-specificity main binding site is a prerequisite for the subsequent highly specific binding of a second RR dimer to the low-affinity secondary binding site. In addition to this hierarchical cooperative binding, discrimination requires a competition of the two RRs for their respective binding site mediated by only slight differences in binding affinities.}, author = {Fang, Chong and Nagy-Staron, Anna A and Grafe, Martin and Heermann, Ralf and Jung, Kirsten and Gebhard, Susanne and Mascher, Thorsten}, issn = { 0950382X}, journal = {Molecular Microbiology}, number = {1}, pages = {16 -- 31}, publisher = {Wiley-Blackwell}, title = {{Insulation and wiring specificity of BceR like response regulators and their target promoters in Bacillus subtilis}}, doi = {10.1111/mmi.13597}, volume = {104}, year = {2017}, } @article{1079, abstract = {We study the ionization problem in the Thomas-Fermi-Dirac-von Weizsäcker theory for atoms and molecules. We prove the nonexistence of minimizers for the energy functional when the number of electrons is large and the total nuclear charge is small. This nonexistence result also applies to external potentials decaying faster than the Coulomb potential. In the case of arbitrary nuclear charges, we obtain the nonexistence of stable minimizers and radial minimizers.}, author = {Nam, Phan and Van Den Bosch, Hanne}, issn = {13850172}, journal = {Mathematical Physics, Analysis and Geometry}, number = {2}, publisher = {Springer}, title = {{Nonexistence in Thomas Fermi-Dirac-von Weizsäcker theory with small nuclear charges}}, doi = {10.1007/s11040-017-9238-0}, volume = {20}, year = {2017}, } @article{1077, abstract = {Viral capsids are structurally constrained by interactions among the amino acids (AAs) of their constituent proteins. Therefore, epistasis is expected to evolve among physically interacting sites and to influence the rates of substitution. To study the evolution of epistasis, we focused on the major structural protein of the fX174 phage family by first reconstructing the ancestral protein sequences of 18 species using a Bayesian statistical framework. The inferred ancestral reconstruction differed at eight AAs, for a total of 256 possible ancestral haplotypes. For each ancestral haplotype and the extant species, we estimated, in silico, the distribution of free energies and epistasis of the capsid structure. We found that free energy has not significantly increased but epistasis has. We decomposed epistasis up to fifth order and found that higher-order epistasis sometimes compensates pairwise interactions making the free energy seem additive. The dN/dS ratio is low, suggesting strong purifying selection, and that structure is under stabilizing selection. We synthesized phages carrying ancestral haplotypes of the coat protein gene and measured their fitness experimentally. Our findings indicate that stabilizing mutations can have higher fitness, and that fitness optima do not necessarily coincide with energy minima.}, author = {Fernandes Redondo, Rodrigo A and Vladar, Harold and Włodarski, Tomasz and Bollback, Jonathan P}, issn = {17425689}, journal = {Journal of the Royal Society Interface}, number = {126}, publisher = {Royal Society of London}, title = {{Evolutionary interplay between structure, energy and epistasis in the coat protein of the ϕX174 phage family}}, doi = {10.1098/rsif.2016.0139}, volume = {14}, year = {2017}, } @article{1067, abstract = {Embryo morphogenesis relies on highly coordinated movements of different tissues. However, remarkably little is known about how tissues coordinate their movements to shape the embryo. In zebrafish embryogenesis, coordinated tissue movements first become apparent during “doming,” when the blastoderm begins to spread over the yolk sac, a process involving coordinated epithelial surface cell layer expansion and mesenchymal deep cell intercalations. Here, we find that active surface cell expansion represents the key process coordinating tissue movements during doming. By using a combination of theory and experiments, we show that epithelial surface cells not only trigger blastoderm expansion by reducing tissue surface tension, but also drive blastoderm thinning by inducing tissue contraction through radial deep cell intercalations. Thus, coordinated tissue expansion and thinning during doming relies on surface cells simultaneously controlling tissue surface tension and radial tissue contraction.}, author = {Morita, Hitoshi and Grigolon, Silvia and Bock, Martin and Krens, Gabriel and Salbreux, Guillaume and Heisenberg, Carl-Philipp J}, issn = {15345807}, journal = {Developmental Cell}, number = {4}, pages = {354 -- 366}, publisher = {Cell Press}, title = {{The physical basis of coordinated tissue spreading in zebrafish gastrulation}}, doi = {10.1016/j.devcel.2017.01.010}, volume = {40}, year = {2017}, } @article{1074, abstract = {Recently it has become feasible to detect long blocks of nearly identical sequence shared between pairs of genomes. These IBD blocks are direct traces of recent coalescence events and, as such, contain ample signal to infer recent demography. Here, we examine sharing of such blocks in two-dimensional populations with local migration. Using a diffusion approximation to trace genetic ancestry, we derive analytical formulae for patterns of isolation by distance of IBD blocks, which can also incorporate recent population density changes. We introduce an inference scheme that uses a composite likelihood approach to fit these formulae. We then extensively evaluate our theory and inference method on a range of scenarios using simulated data. We first validate the diffusion approximation by showing that the theoretical results closely match the simulated block sharing patterns. We then demonstrate that our inference scheme can accurately and robustly infer dispersal rate and effective density, as well as bounds on recent dynamics of population density. To demonstrate an application, we use our estimation scheme to explore the fit of a diffusion model to Eastern European samples in the POPRES data set. We show that ancestry diffusing with a rate of σ ≈ 50–100 km/√gen during the last centuries, combined with accelerating population growth, can explain the observed exponential decay of block sharing with increasing pairwise sample distance.}, author = {Ringbauer, Harald and Coop, Graham and Barton, Nicholas H}, issn = {00166731}, journal = {Genetics}, number = {3}, pages = {1335 -- 1351}, publisher = {Genetics Society of America}, title = {{Inferring recent demography from isolation by distance of long shared sequence blocks}}, doi = {10.1534/genetics.116.196220}, volume = {205}, year = {2017}, } @article{1076, abstract = {Signatures of the Coulomb corrections in the photoelectron momentum distribution during laser-induced ionization of atoms or ions in tunneling and multiphoton regimes are investigated analytically in the case of a one-dimensional problem. A high-order Coulomb-corrected strong-field approximation is applied, where the exact continuum state in the S matrix is approximated by the eikonal Coulomb-Volkov state including the second-order corrections to the eikonal. Although without high-order corrections our theory coincides with the known analytical R-matrix (ARM) theory, we propose a simplified procedure for the matrix element derivation. Rather than matching the eikonal Coulomb-Volkov wave function with the bound state as in the ARM theory to remove the Coulomb singularity, we calculate the matrix element via the saddle-point integration method by time as well as by coordinate, and in this way avoiding the Coulomb singularity. The momentum shift in the photoelectron momentum distribution with respect to the ARM theory due to high-order corrections is analyzed for tunneling and multiphoton regimes. The relation of the quantum corrections to the tunneling delay time is discussed.}, author = {Klaiber, Michael and Daněk, Jiří and Yakaboylu, Enderalp and Hatsagortsyan, Karen and Keitel, Christoph}, issn = {24699926}, journal = { Physical Review A - Atomic, Molecular, and Optical Physics}, number = {2}, publisher = {American Physical Society}, title = {{Strong-field ionization via a high-order Coulomb-corrected strong-field approximation}}, doi = {10.1103/PhysRevA.95.023403}, volume = {95}, year = {2017}, } @article{1072, abstract = {Given a finite set of points in Rn and a radius parameter, we study the Čech, Delaunay–Čech, Delaunay (or alpha), and Wrap complexes in the light of generalized discrete Morse theory. Establishing the Čech and Delaunay complexes as sublevel sets of generalized discrete Morse functions, we prove that the four complexes are simple-homotopy equivalent by a sequence of simplicial collapses, which are explicitly described by a single discrete gradient field.}, author = {Bauer, Ulrich and Edelsbrunner, Herbert}, journal = {Transactions of the American Mathematical Society}, number = {5}, pages = {3741 -- 3762}, publisher = {American Mathematical Society}, title = {{The Morse theory of Čech and delaunay complexes}}, doi = {10.1090/tran/6991}, volume = {369}, year = {2017}, } @article{1073, abstract = {Let X and Y be finite simplicial sets (e.g. finite simplicial complexes), both equipped with a free simplicial action of a finite group G. Assuming that Y is d-connected and dimX≤2d, for some d≥1, we provide an algorithm that computes the set of all equivariant homotopy classes of equivariant continuous maps |X|→|Y|; the existence of such a map can be decided even for dimX≤2d+1. This yields the first algorithm for deciding topological embeddability of a k-dimensional finite simplicial complex into Rn under the condition k≤23n−1. More generally, we present an algorithm that, given a lifting-extension problem satisfying an appropriate stability assumption, computes the set of all homotopy classes of solutions. This result is new even in the non-equivariant situation.}, author = {Čadek, Martin and Krcál, Marek and Vokřínek, Lukáš}, issn = {01795376}, journal = {Discrete & Computational Geometry}, number = {4}, pages = {915 -- 965}, publisher = {Springer}, title = {{Algorithmic solvability of the lifting extension problem}}, doi = {10.1007/s00454-016-9855-6}, volume = {54}, year = {2017}, } @article{1065, abstract = {We consider the problem of reachability in pushdown graphs. We study the problem for pushdown graphs with constant treewidth. Even for pushdown graphs with treewidth 1, for the reachability problem we establish the following: (i) the problem is PTIME-complete, and (ii) any subcubic algorithm for the problem would contradict the k-clique conjecture and imply faster combinatorial algorithms for cliques in graphs.}, author = {Chatterjee, Krishnendu and Osang, Georg F}, issn = {00200190}, journal = {Information Processing Letters}, pages = {25 -- 29}, publisher = {Elsevier}, title = {{Pushdown reachability with constant treewidth}}, doi = {10.1016/j.ipl.2017.02.003}, volume = {122}, year = {2017}, } @article{1063, abstract = {Severe environmental change can drive a population extinct unless the population adapts in time to the new conditions (“evolutionary rescue”). How does biparental sexual reproduction influence the chances of population persistence compared to clonal reproduction or selfing? In this article, we set up a one‐locus two‐allele model for adaptation in diploid species, where rescue is contingent on the establishment of the mutant homozygote. Reproduction can occur by random mating, selfing, or clonally. Random mating generates and destroys the rescue mutant; selfing is efficient at generating it but at the same time depletes the heterozygote, which can lead to a low mutant frequency in the standing genetic variation. Due to these (and other) antagonistic effects, we find a nontrivial dependence of population survival on the rate of sex/selfing, which is strongly influenced by the dominance coefficient of the mutation before and after the environmental change. Importantly, since mating with the wild‐type breaks the mutant homozygote up, a slow decay of the wild‐type population size can impede rescue in randomly mating populations.}, author = {Uecker, Hildegard}, issn = {00143820}, journal = {Evolution}, number = {4}, pages = {845 -- 858}, publisher = {Wiley-Blackwell}, title = {{Evolutionary rescue in randomly mating, selfing, and clonal populations}}, doi = {10.1111/evo.13191}, volume = {71}, year = {2017}, } @article{1066, abstract = {Simulation is an attractive alternative to language inclusion for automata as it is an under-approximation of language inclusion, but usually has much lower complexity. Simulation has also been extended in two orthogonal directions, namely, (1) fair simulation, for simulation over specified set of infinite runs; and (2) quantitative simulation, for simulation between weighted automata. While fair trace inclusion is PSPACE-complete, fair simulation can be computed in polynomial time. For weighted automata, the (quantitative) language inclusion problem is undecidable in general, whereas the (quantitative) simulation reduces to quantitative games, which admit pseudo-polynomial time algorithms. In this work, we study (quantitative) simulation for weighted automata with Büchi acceptance conditions, i.e., we generalize fair simulation from non-weighted automata to weighted automata. We show that imposing Büchi acceptance conditions on weighted automata changes many fundamental properties of the simulation games, yet they still admit pseudo-polynomial time algorithms.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan and Velner, Yaron}, journal = {Information and Computation}, number = {2}, pages = {143 -- 166}, publisher = {Elsevier}, title = {{Quantitative fair simulation games}}, doi = {10.1016/j.ic.2016.10.006}, volume = {254}, year = {2017}, } @article{1023, abstract = {We consider products of independent square non-Hermitian random matrices. More precisely, let X1,…, Xn be independent N × N random matrices with independent entries (real or complex with independent real and imaginary parts) with zero mean and variance 1/N. Soshnikov-O’Rourke [19] and Götze-Tikhomirov [15] showed that the empirical spectral distribution of the product of n random matrices with iid entries converges to (equation found). We prove that if the entries of the matrices X1,…, Xn are independent (but not necessarily identically distributed) and satisfy uniform subexponential decay condition, then in the bulk the convergence of the ESD of X1,…, Xn to (0.1) holds up to the scale N–1/2+ε.}, author = {Nemish, Yuriy}, issn = {10836489}, journal = {Electronic Journal of Probability}, publisher = {Institute of Mathematical Statistics}, title = {{Local law for the product of independent non-Hermitian random matrices with independent entries}}, doi = {10.1214/17-EJP38}, volume = {22}, year = {2017}, } @article{1022, abstract = {We introduce a multiscale topological description of the Megaparsec web-like cosmic matter distribution. Betti numbers and topological persistence offer a powerful means of describing the rich connectivity structure of the cosmic web and of its multiscale arrangement of matter and galaxies. Emanating from algebraic topology and Morse theory, Betti numbers and persistence diagrams represent an extension and deepening of the cosmologically familiar topological genus measure and the related geometric Minkowski functionals. In addition to a description of the mathematical background, this study presents the computational procedure for computing Betti numbers and persistence diagrams for density field filtrations. The field may be computed starting from a discrete spatial distribution of galaxies or simulation particles. The main emphasis of this study concerns an extensive and systematic exploration of the imprint of different web-like morphologies and different levels of multiscale clustering in the corresponding computed Betti numbers and persistence diagrams. To this end, we use Voronoi clustering models as templates for a rich variety of web-like configurations and the fractal-like Soneira-Peebles models exemplify a range of multiscale configurations. We have identified the clear imprint of cluster nodes, filaments, walls, and voids in persistence diagrams, along with that of the nested hierarchy of structures in multiscale point distributions. We conclude by outlining the potential of persistent topology for understanding the connectivity structure of the cosmic web, in large simulations of cosmic structure formation and in the challenging context of the observed galaxy distribution in large galaxy surveys.}, author = {Pranav, Pratyush and Edelsbrunner, Herbert and Van De Weygaert, Rien and Vegter, Gert and Kerber, Michael and Jones, Bernard and Wintraecken, Mathijs}, issn = {00358711}, journal = {Monthly Notices of the Royal Astronomical Society}, number = {4}, pages = {4281 -- 4310}, publisher = {Oxford University Press}, title = {{The topology of the cosmic web in terms of persistent Betti numbers}}, doi = {10.1093/mnras/stw2862}, volume = {465}, year = {2017}, } @article{1026, abstract = {The optogenetic revolution enabled spatially-precise and temporally-precise control over protein function, signaling pathway activation, and animal behavior with tremendous success in the dissection of signaling networks and neural circuits. Very recently, optogenetic methods have been paired with optical reporters in novel drug screening platforms. In these all-optical platforms, light remotely activated ion channels and kinases thereby obviating the use of electrophysiology or reagents. Consequences were remarkable operational simplicity, throughput, and cost-effectiveness that culminated in the identification of new drug candidates. These blueprints for all-optical assays also revealed potential pitfalls and inspire all-optical variants of other screens, such as those that aim at better understanding dynamic drug action or orphan protein function.}, author = {Agus, Viviana and Janovjak, Harald L}, issn = {09581669}, journal = {Current Opinion in Biotechnology}, pages = {8 -- 14}, publisher = {Elsevier}, title = {{Optogenetic methods in drug screening: Technologies and applications}}, doi = {10.1016/j.copbio.2017.02.006}, volume = {48}, year = {2017}, } @article{1020, abstract = {Cellulose is the most abundant biopolymer on Earth. Cellulose fibers, such as the one extracted form cotton or woodpulp, have been used by humankind for hundreds of years to make textiles and paper. Here we show how, by engineering light-matter interaction, we can optimize light scattering using exclusively cellulose nanocrystals. The produced material is sustainable, biocompatible, and when compared to ordinary microfiber-based paper, it shows enhanced scattering strength (×4), yielding a transport mean free path as low as 3.5 μm in the visible light range. The experimental results are in a good agreement with the theoretical predictions obtained with a diffusive model for light propagation.}, author = {Caixeiro, Soraya and Peruzzo, Matilda and Onelli, Olimpia and Vignolini, Silvia and Sapienza, Riccardo}, issn = {19448244}, journal = {ACS Applied Materials and Interfaces}, number = {9}, pages = {7885 -- 7890}, publisher = {American Chemical Society}, title = {{Disordered cellulose based nanostructures for enhanced light scattering}}, doi = {10.1021/acsami.6b15986}, volume = {9}, year = {2017}, } @article{1021, abstract = {Most flows in nature and engineering are turbulent because of their large velocities and spatial scales. Laboratory experiments on rotating quasi-Keplerian flows, for which the angular velocity decreases radially but the angular momentum increases, are however laminar at Reynolds numbers exceeding one million. This is in apparent contradiction to direct numerical simulations showing that in these experiments turbulence transition is triggered by the axial boundaries. We here show numerically that as the Reynolds number increases, turbulence becomes progressively confined to the boundary layers and the flow in the bulk fully relaminarizes. Our findings support that turbulence is unlikely to occur in isothermal constant-density quasi-Keplerian flows.}, author = {Lopez Alonso, Jose M and Avila, Marc}, issn = {00221120}, journal = {Journal of Fluid Mechanics}, pages = {21 -- 34}, publisher = {Cambridge University Press}, title = {{Boundary layer turbulence in experiments on quasi Keplerian flows}}, doi = {10.1017/jfm.2017.109}, volume = {817}, year = {2017}, } @article{1025, abstract = {Many organ surfaces are covered by a protective epithelial-cell layer. It emerges that such layers are maintained by cell stretching that triggers cell division mediated by the force-sensitive ion-channel protein Piezo1. See Letter p.118}, author = {Heisenberg, Carl-Philipp J}, issn = {00280836}, journal = {Nature}, number = {7643}, pages = {43 -- 44}, publisher = {Nature Publishing Group}, title = {{Cell biology: Stretched divisions}}, doi = {10.1038/nature21502}, volume = {543}, year = {2017}, } @article{1017, abstract = {The development of the vertebrate central nervous system is reliant on a complex cascade of biological processes that include mitotic division, relocation of migrating neurons, and the extension of dendritic and axonal processes. Each of these cellular events requires the diverse functional repertoire of the microtubule cytoskeleton for the generation of forces, assembly of macromolecular complexes and transport of molecules and organelles. The tubulins are a multi-gene family that encode for the constituents of microtubules, and have been implicated in a spectrum of neurological disorders. Evidence is building that different tubulins tune the functional properties of the microtubule cytoskeleton dependent on the cell type, developmental profile and subcellular localisation. Here we review of the origins of the functional specification of the tubulin gene family in the developing brain at a transcriptional, translational, and post-transcriptional level. We remind the reader that tubulins are not just loading controls for your average Western blot.}, author = {Breuss, Martin and Leca, Ines and Gstrein, Thomas and Hansen, Andi H and Keays, David}, issn = {10447431}, journal = {Molecular and Cellular Neuroscience}, pages = {58 -- 67}, publisher = {Academic Press}, title = {{Tubulins and brain development: The origins of functional specification}}, doi = {10.1016/j.mcn.2017.03.002}, volume = {84}, year = {2017}, } @article{1015, abstract = {Vortices are commonly observed in the context of classical hydrodynamics: from whirlpools after stirring the coffee in a cup to a violent atmospheric phenomenon such as a tornado, all classical vortices are characterized by an arbitrary circulation value of the local velocity field. On the other hand the appearance of vortices with quantized circulation represents one of the fundamental signatures of macroscopic quantum phenomena. In two-dimensional superfluids quantized vortices play a key role in determining finite-temperature properties, as the superfluid phase and the normal state are separated by a vortex unbinding transition, the Berezinskii-Kosterlitz-Thouless transition. Very recent experiments with two-dimensional superfluid fermions motivate the present work: we present theoretical results based on the renormalization group showing that the universal jump of the superfluid density and the critical temperature crucially depend on the interaction strength, providing a strong benchmark for forthcoming investigations.}, author = {Bighin, Giacomo and Salasnich, Luca}, issn = {20452322}, journal = {Scientific Reports}, publisher = {Nature Publishing Group}, title = {{Vortices and antivortices in two-dimensional ultracold Fermi gases}}, doi = {10.1038/srep45702}, volume = {7}, year = {2017}, } @article{1016, abstract = {The integrity and dynamic properties of the microtubule cytoskeleton are indispensable for the development of the mammalian brain. Consequently, mutations in the genes that encode the structural component (the α/β-tubulin heterodimer) can give rise to severe, sporadic neurodevelopmental disorders. These are commonly referred to as the tubulinopathies. Here we report the addition of recessive quadrupedalism, also known as Uner Tan syndrome (UTS), to the growing list of diseases caused by tubulin variants. Analysis of a consanguineous UTS family identified a biallelic TUBB2B mutation, resulting in a p.R390Q amino acid substitution. In addition to the identifying quadrupedal locomotion, all three patients showed severe cerebellar hypoplasia. None, however, displayed the basal ganglia malformations typically associated with TUBB2B mutations. Functional analysis of the R390Q substitution revealed that it did not affect the ability of β-tubulin to fold or become assembled into the α/β-heterodimer, nor did it influence the incorporation of mutant-containing heterodimers into microtubule polymers. The 390Q mutation in S. cerevisiae TUB2 did not affect growth under basal conditions, but did result in increased sensitivity to microtubule-depolymerizing drugs, indicative of a mild impact of this mutation on microtubule function. The TUBB2B mutation described here represents an unusual recessive mode of inheritance for missense-mediated tubulinopathies and reinforces the sensitivity of the developing cerebellum to microtubule defects.}, author = {Breuss, Martin and Nguyen, Thai and Srivatsan, Anjana and Leca, Ines and Tian, Guoling and Fritz, Tanja and Hansen, Andi H and Musaev, Damir and Mcevoy Venneri, Jennifer and Kiely, James and Rosti, Rasim and Scott, Eric and Tan, Uner and Kolodner, Richard and Cowan, Nicholas and Keays, David and Gleeson, Joseph}, issn = {09646906}, journal = {Human Molecular Genetics}, number = {2}, pages = {258 -- 269}, publisher = {Oxford University Press}, title = {{Uner Tan syndrome caused by a homozygous TUBB2B mutation affecting microtubule stability}}, doi = {10.1093/hmg/ddw383}, volume = {26}, year = {2017}, } @article{1018, abstract = {In plants, the multistep phosphorelay (MSP) pathway mediates a range of regulatory processes, including those activated by cytokinins. The crosstalk between cytokinin response and light is known for a long time. However, the molecular mechanism underlying the interactionbetween light and cytokinin signaling remains elusive. In the screen for upstream regulators we identified a LONG PALE HYPOCOTYL (LPH) gene whose activity is indispensable for spatiotemporally correct expression of CYTOKININ INDEPENDENT-1 (CKI1), encoding the constitutively active sensor histidine kinase that activates MSP signaling. lph is a new allele of HEME OXYGENASE 1 (HY1) which encodes the key protein in the biosynthesis of phytochromobilin, a cofactor of photoconvertiblephytochromes. Our analysis confirmed the light-dependent regulation oftheCKI1 expression pattern. We show that CKI1 expression is under the control of phytochrome A (phyA), functioning as a dual (both positive and negative) regulator of CKI1 expression, presumably via the phyA-regulated transcription factors PHYTOCHROME INTERACTING FACTOR 3 (PIF3) and CIRCADIAN CLOCK ASSOCIATED 1 (CCA1). Changes in CKI1 expression observed in lph/hy1-7 and phy mutants correlatewithmisregulation of MSP signaling, changedcytokinin sensitivity and developmental aberrations,previously shown to be associated with cytokinin and/or CKI1 action. Besides that, we demonstrate novel role of phyA-dependent CKI1 expression in the hypocotyl elongation and hook development during skotomorphogenesis. Based on these results, we propose that the light-dependent regulation of CKI1 provides a plausible mechanistic link underlying the well-known interaction between light- and cytokinin-controlled plant development.}, author = {Dobisova, Tereza and Hrdinova, Vendula and Cuesta, Candela and Michlickova, Sarka and Urbankova, Ivana and Hejatkova, Romana and Zadnikova, Petra and Pernisová, Markéta and Benková, Eva and Hejátko, Jan}, journal = {Plant Physiology}, number = {1}, pages = {387 -- 404}, publisher = {American Society of Plant Biologists}, title = {{Light regulated expression of sensor histidine kinase CKI1 controls cytokinin related development}}, doi = {10.1104/pp.16.01964}, volume = {174}, year = {2017}, } @article{1019, abstract = {As a consequence of its difference in copy number between males and females, the X chromosome is subject to unique evolutionary forces and gene regulatory mechanisms. Previous studies of Drosophila melanogaster have shown that the expression of X-linked, testis-specific reporter genes is suppressed in the male germline. However, it is not known whether this phenomenon is restricted to testis-expressed genes or if it is a more general property of genes with tissue-specific expression, which are also underrepresented on the X chromosome. To test this, we compared the expression of three tissue-specific reporter genes (ovary, accessory gland and Malpighian tubule) inserted at various autosomal and X-chromosomal locations. In contrast to testis-specific reporter genes, we found no reduction of X-linked expression in any of the other tissues. In accessory gland and Malpighian tubule, we detected higher expression of the X-linked reporter genes, which suggests that they are at least partially dosage compensated. We found no difference in the tissue-specificity of X-linked and autosomal reporter genes. These findings indicate that, in general, the X chromosome is not a detrimental environment for tissue-specific gene expression and that the suppression of X-linked expression is limited to the male germline.}, author = {Argyridou, Eliza and Huylmans, Ann K and Königer, Annabella and Parsch, John}, issn = {0018067X}, journal = {Heredity}, number = {1}, pages = {27 -- 34}, publisher = {Nature Publishing Group}, title = {{X-linkage is not a general inhibitor of tissue-specific gene expression in Drosophila melanogaster}}, doi = {10.1038/hdy.2017.12}, volume = {119}, year = {2017}, } @misc{9861, abstract = {As a consequence of its difference in copy number between males and females, the X chromosome is subject to unique evolutionary forces and gene regulatory mechanisms. Previous studies of Drosophila melanogaster have shown that the expression of X-linked, testis-specific reporter genes is suppressed in the male germline. However, it is not known whether this phenomenon is restricted to testis-expressed genes or if it is a more general property of genes with tissue-specific expression, which are also underrepresented on the X chromosome. To test this, we compared the expression of three tissue-specific reporter genes (ovary, accessory gland and Malpighian tubule) inserted at various autosomal and X-chromosomal locations. In contrast to testis-specific reporter genes, we found no reduction of X-linked expression in any of the other tissues. In accessory gland and Malpighian tubule, we detected higher expression of the X-linked reporter genes, which suggests that they are at least partially dosage compensated. We found no difference in the tissue-specificity of X-linked and autosomal reporter genes. These findings indicate that, in general, the X chromosome is not a detrimental environment for tissue-specific gene expression and that the suppression of X-linked expression is limited to the male germline.}, author = {Argyridou, Eliza and Huylmans, Ann K and Königer, Annabella and Parsch, John}, publisher = {Dryad}, title = {{Data from: X-linkage is not a general inhibitor of tissue-specific gene expression in Drosophila melanogaster}}, doi = {10.5061/dryad.02f6r}, year = {2017}, } @article{1006, abstract = {Background: The phenomenon of immune priming, i.e. enhanced protection following a secondary exposure to a pathogen, has now been demonstrated in a wide range of invertebrate species. Despite accumulating phenotypic evidence, knowledge of its mechanistic underpinnings is currently very limited. Here we used the system of the red flour beetle, Tribolium castaneum and the insect pathogen Bacillus thuringiensis (Bt) to further our molecular understanding of the oral immune priming phenomenon. We addressed how ingestion of bacterial cues (derived from spore supernatants) of an orally pathogenic and non-pathogenic Bt strain affects gene expression upon later challenge exposure, using a whole-transcriptome sequencing approach. Results: Whereas gene expression of individuals primed with the orally non-pathogenic strain showed minor changes to controls, we found that priming with the pathogenic strain induced regulation of a large set of distinct genes, many of which are known immune candidates. Intriguingly, the immune repertoire activated upon priming and subsequent challenge qualitatively differed from the one mounted upon infection with Bt without previous priming. Moreover, a large subset of priming-specific genes showed an inverse regulation compared to their regulation upon challenge only. Conclusions: Our data demonstrate that gene expression upon infection is strongly affected by previous immune priming. We hypothesise that this shift in gene expression indicates activation of a more targeted and efficient response towards a previously encountered pathogen, in anticipation of potential secondary encounter.}, author = {Greenwood, Jenny and Milutinovic, Barbara and Peuß, Robert and Behrens, Sarah and Essar, Daniela and Rosenstiel, Philip and Schulenburg, Hinrich and Kurtz, Joachim}, issn = {14712164}, journal = {BMC Genomics}, number = {1}, pages = {329}, publisher = {BioMed Central}, title = {{Oral immune priming with Bacillus thuringiensis induces a shift in the gene expression of Tribolium castaneum larvae}}, doi = {10.1186/s12864-017-3705-7}, volume = {18}, year = {2017}, } @inproceedings{1011, abstract = {Pushdown systems (PDSs) and recursive state machines (RSMs), which are linearly equivalent, are standard models for interprocedural analysis. Yet RSMs are more convenient as they (a) explicitly model function calls and returns, and (b) specify many natural parameters for algorithmic analysis, e.g., the number of entries and exits. We consider a general framework where RSM transitions are labeled from a semiring and path properties are algebraic with semiring operations, which can model, e.g., interprocedural reachability and dataflow analysis problems. Our main contributions are new algorithms for several fundamental problems. As compared to a direct translation of RSMs to PDSs and the best-known existing bounds of PDSs, our analysis algorithm improves the complexity for finite-height semirings (that subsumes reachability and standard dataflow properties). We further consider the problem of extracting distance values from the representation structures computed by our algorithm, and give efficient algorithms that distinguish the complexity of a one-time preprocessing from the complexity of each individual query. Another advantage of our algorithm is that our improvements carry over to the concurrent setting, where we improve the bestknown complexity for the context-bounded analysis of concurrent RSMs. Finally, we provide a prototype implementation that gives a significant speed-up on several benchmarks from the SLAM/SDV project.}, author = {Chatterjee, Krishnendu and Kragl, Bernhard and Mishra, Samarth and Pavlogiannis, Andreas}, editor = {Yang, Hongseok}, issn = {03029743}, location = {Uppsala, Sweden}, pages = {287 -- 313}, publisher = {Springer}, title = {{Faster algorithms for weighted recursive state machines}}, doi = {10.1007/978-3-662-54434-1_11}, volume = {10201}, year = {2017}, } @article{1004, abstract = {The fundamental tasks of the root system are, besides anchoring, mediating interactions between plant and soil and providing the plant with water and nutrients. The architecture of the root system is controlled by endogenous mechanisms that constantly integrate environmental signals, such as availability of nutrients and water. Extremely important for efficient soil exploitation and survival under less favorable conditions is the developmental flexibility of the root system that is largely determined by its postembryonic branching capacity. Modulation of initiation and outgrowth of lateral roots provides roots with an exceptional plasticity, allows optimal adjustment to underground heterogeneity, and enables effective soil exploitation and use of resources. Here we discuss recent advances in understanding the molecular mechanisms that shape the plant root system and integrate external cues to adapt to the changing environment.}, author = {Ötvös, Krisztina and Benková, Eva}, issn = {0959437X}, journal = {Current Opinion in Genetics & Development}, pages = {82 -- 89}, publisher = {Elsevier}, title = {{Spatiotemporal mechanisms of root branching}}, doi = {10.1016/j.gde.2017.03.010}, volume = {45}, year = {2017}, } @article{1010, abstract = {We prove a local law in the bulk of the spectrum for random Gram matrices XX∗, a generalization of sample covariance matrices, where X is a large matrix with independent, centered entries with arbitrary variances. The limiting eigenvalue density that generalizes the Marchenko-Pastur law is determined by solving a system of nonlinear equations. Our entrywise and averaged local laws are on the optimal scale with the optimal error bounds. They hold both in the square case (hard edge) and in the properly rectangular case (soft edge). In the latter case we also establish a macroscopic gap away from zero in the spectrum of XX∗. }, author = {Alt, Johannes and Erdös, László and Krüger, Torben H}, issn = {10836489}, journal = {Electronic Journal of Probability}, publisher = {Institute of Mathematical Statistics}, title = {{Local law for random Gram matrices}}, doi = {10.1214/17-EJP42}, volume = {22}, year = {2017}, } @inproceedings{1009, abstract = {A standard objective in partially-observable Markov decision processes (POMDPs) is to find a policy that maximizes the expected discounted-sum payoff. However, such policies may still permit unlikely but highly undesirable outcomes, which is problematic especially in safety-critical applications. Recently, there has been a surge of interest in POMDPs where the goal is to maximize the probability to ensure that the payoff is at least a given threshold, but these approaches do not consider any optimization beyond satisfying this threshold constraint. In this work we go beyond both the “expectation” and “threshold” approaches and consider a “guaranteed payoff optimization (GPO)” problem for POMDPs, where we are given a threshold t and the objective is to find a policy σ such that a) each possible outcome of σ yields a discounted-sum payoff of at least t, and b) the expected discounted-sum payoff of σ is optimal (or near-optimal) among all policies satisfying a). We present a practical approach to tackle the GPO problem and evaluate it on standard POMDP benchmarks.}, author = {Chatterjee, Krishnendu and Novotny, Petr and Pérez, Guillermo and Raskin, Jean and Zikelic, Djordje}, booktitle = {Proceedings of the 31st AAAI Conference on Artificial Intelligence}, location = {San Francisco, CA, United States}, pages = {3725 -- 3732}, publisher = {AAAI Press}, title = {{Optimizing expectation with guarantees in POMDPs}}, volume = {5}, year = {2017}, } @misc{9859, abstract = {Lists of all differentially expressed genes in the different priming-challenge treatments (compared to the fully naïve control; xlsx file). Relevant columns include the following: sample_1 and sample_2 – treatment groups being compared; Normalised FPKM sample_1 and sample_2 – FPKM of samples being compared; log2(fold_change) – log2(FPKM sample 2/FPKM sample 1), i.e. negative means sample 1 upregulated compared with sample 2, positive means sample 2 upregulated compared with sample 1; cuffdiff test_statistic – test statistic of differential expression test; p_value – p-value of differential expression test; q_value (FDR correction) – adjusted P-value of differential expression test. (XLSX 598 kb)}, author = {Greenwood, Jenny and Milutinovic, Barbara and Peuß, Robert and Behrens, Sarah and Essar, Daniela and Rosenstiel, Philip and Schulenburg, Hinrich and Kurtz, Joachim}, publisher = {Springer Nature}, title = {{Additional file 1: Table S1. of Oral immune priming with Bacillus thuringiensis induces a shift in the gene expression of Tribolium castaneum larvae}}, doi = {10.6084/m9.figshare.c.3756974_d1.v1}, year = {2017}, } @misc{9860, author = {Greenwood, Jenny and Milutinovic, Barbara and Peuß, Robert and Behrens, Sarah and Essar, Daniela and Rosenstiel, Philip and Schulenburg, Hinrich and Kurtz, Joachim}, publisher = {Springer Nature}, title = {{Additional file 5: Table S3. of Oral immune priming with Bacillus thuringiensis induces a shift in the gene expression of Tribolium castaneum larvae}}, doi = {10.6084/m9.figshare.c.3756974_d5.v1}, year = {2017}, } @inproceedings{1002, abstract = { We present an interactive design system to create functional mechanical objects. Our computational approach allows novice users to retarget an existing mechanical template to a user-specified input shape. Our proposed representation for a mechanical template encodes a parameterized mechanism, mechanical constraints that ensure a physically valid configuration, spatial relationships of mechanical parts to the user-provided shape, and functional constraints that specify an intended functionality. We provide an intuitive interface and optimization-in-the-loop approach for finding a valid configuration of the mechanism and the shape to ensure that higher-level functional goals are met. Our algorithm interactively optimizes the mechanism while the user manipulates the placement of mechanical components and the shape. Our system allows users to efficiently explore various design choices and to synthesize customized mechanical objects that can be fabricated with rapid prototyping technologies. We demonstrate the efficacy of our approach by retargeting various mechanical templates to different shapes and fabricating the resulting functional mechanical objects. }, author = {Zhang, Ran and Auzinger, Thomas and Ceylan, Duygu and Li, Wilmot and Bickel, Bernd}, issn = {07300301}, location = {Los Angeles, CA, United States }, number = {4}, publisher = {ACM}, title = {{Functionality-aware retargeting of mechanisms to 3D shapes}}, doi = {10.1145/3072959.3073710}, volume = {36}, year = {2017}, } @inproceedings{1001, abstract = {We present a computational approach for designing CurveUps, curvy shells that form from an initially flat state. They consist of small rigid tiles that are tightly held together by two pre-stretched elastic sheets attached to them. Our method allows the realization of smooth, doubly curved surfaces that can be fabricated as a flat piece. Once released, the restoring forces of the pre-stretched sheets support the object to take shape in 3D. CurveUps are structurally stable in their target configuration. The design process starts with a target surface. Our method generates a tile layout in 2D and optimizes the distribution, shape, and attachment areas of the tiles to obtain a configuration that is fabricable and in which the curved up state closely matches the target. Our approach is based on an efficient approximate model and a local optimization strategy for an otherwise intractable nonlinear optimization problem. We demonstrate the effectiveness of our approach for a wide range of shapes, all realized as physical prototypes.}, author = {Guseinov, Ruslan and Miguel, Eder and Bickel, Bernd}, location = {Los Angeles, CA, United States}, number = {4}, publisher = {ACM}, title = {{CurveUps: Shaping objects from flat plates with tension-actuated curvature}}, doi = {10.1145/3072959.3073709}, volume = {36}, year = {2017}, } @inproceedings{1003, abstract = {Network games (NGs) are played on directed graphs and are extensively used in network design and analysis. Search problems for NGs include finding special strategy profiles such as a Nash equilibrium and a globally optimal solution. The networks modeled by NGs may be huge. In formal verification, abstraction has proven to be an extremely effective technique for reasoning about systems with big and even infinite state spaces. We describe an abstraction-refinement methodology for reasoning about NGs. Our methodology is based on an abstraction function that maps the state space of an NG to a much smaller state space. We search for a global optimum and a Nash equilibrium by reasoning on an under- and an overapproximation defined on top of this smaller state space. When the approximations are too coarse to find such profiles, we refine the abstraction function. Our experimental results demonstrate the efficiency of the methodology.}, author = {Avni, Guy and Guha, Shibashis and Kupferman, Orna}, issn = {10450823}, location = {Melbourne, Australia}, pages = {70 -- 76}, publisher = {AAAI Press}, title = {{An abstraction-refinement methodology for reasoning about network games}}, doi = {10.24963/ijcai.2017/11}, year = {2017}, } @inproceedings{1000, abstract = {We study probabilistic models of natural images and extend the autoregressive family of PixelCNN models by incorporating latent variables. Subsequently, we describe two new generative image models that exploit different image transformations as latent variables: a quantized grayscale view of the image or a multi-resolution image pyramid. The proposed models tackle two known shortcomings of existing PixelCNN models: 1) their tendency to focus on low-level image details, while largely ignoring high-level image information, such as object shapes, and 2) their computationally costly procedure for image sampling. We experimentally demonstrate benefits of our LatentPixelCNN models, in particular showing that they produce much more realistically looking image samples than previous state-of-the-art probabilistic models. }, author = {Kolesnikov, Alexander and Lampert, Christoph}, booktitle = {34th International Conference on Machine Learning}, isbn = {978-151085514-4}, location = {Sydney, Australia}, pages = {1905 -- 1914}, publisher = {JMLR}, title = {{PixelCNN models with auxiliary variables for natural image modeling}}, volume = {70}, year = {2017}, } @inproceedings{998, abstract = {A major open problem on the road to artificial intelligence is the development of incrementally learning systems that learn about more and more concepts over time from a stream of data. In this work, we introduce a new training strategy, iCaRL, that allows learning in such a class-incremental way: only the training data for a small number of classes has to be present at the same time and new classes can be added progressively. iCaRL learns strong classifiers and a data representation simultaneously. This distinguishes it from earlier works that were fundamentally limited to fixed data representations and therefore incompatible with deep learning architectures. We show by experiments on CIFAR-100 and ImageNet ILSVRC 2012 data that iCaRL can learn many classes incrementally over a long period of time where other strategies quickly fail. }, author = {Rebuffi, Sylvestre Alvise and Kolesnikov, Alexander and Sperl, Georg and Lampert, Christoph}, isbn = {978-153860457-1}, location = {Honolulu, HA, United States}, pages = {5533 -- 5542}, publisher = {IEEE}, title = {{iCaRL: Incremental classifier and representation learning}}, doi = {10.1109/CVPR.2017.587}, volume = {2017}, year = {2017}, } @article{990, abstract = {Assortative mating is an important driver of speciation in populations with gene flow and is predicted to evolve under certain conditions in few-locus models. However, the evolution of assortment is less understood for mating based on quantitative traits, which are often characterized by high genetic variability and extensive linkage disequilibrium between trait loci. We explore this scenario for a two-deme model with migration, by considering a single polygenic trait subject to divergent viability selection across demes, as well as assortative mating and sexual selection within demes, and investigate how trait divergence is shaped by various evolutionary forces. Our analysis reveals the existence of sharp thresholds of assortment strength, at which divergence increases dramatically. We also study the evolution of assortment via invasion of modifiers of mate discrimination and show that the ES assortment strength has an intermediate value under a range of migration-selection parameters, even in diverged populations, due to subtle effects which depend sensitively on the extent of phenotypic variation within these populations. The evolutionary dynamics of the polygenic trait is studied using the hypergeometric and infinitesimal models. We further investigate the sensitivity of our results to the assumptions of the hypergeometric model, using individual-based simulations.}, author = {Sachdeva, Himani and Barton, Nicholas H}, issn = {00143820}, journal = {Evolution; International Journal of Organic Evolution}, number = {6}, pages = {1478 -- 1493 }, publisher = {Wiley-Blackwell}, title = {{Divergence and evolution of assortative mating in a polygenic trait model of speciation with gene flow}}, doi = {10.1111/evo.13252}, volume = {71}, year = {2017}, } @article{988, abstract = {The current-phase relation (CPR) of a Josephson junction (JJ) determines how the supercurrent evolves with the superconducting phase difference across the junction. Knowledge of the CPR is essential in order to understand the response of a JJ to various external parameters. Despite the rising interest in ultraclean encapsulated graphene JJs, the CPR of such junctions remains unknown. Here, we use a fully gate-tunable graphene superconducting quantum intereference device (SQUID) to determine the CPR of ballistic graphene JJs. Each of the two JJs in the SQUID is made with graphene encapsulated in hexagonal boron nitride. By independently controlling the critical current of the JJs, we can operate the SQUID either in a symmetric or asymmetric configuration. The highly asymmetric SQUID allows us to phase-bias one of the JJs and thereby directly obtain its CPR. The CPR is found to be skewed, deviating significantly from a sinusoidal form. The skewness can be tuned with the gate voltage and oscillates in antiphase with Fabry-Pérot resistance oscillations of the ballistic graphene cavity. We compare our experiments with tight-binding calculations that include realistic graphene-superconductor interfaces and find a good qualitative agreement.}, author = {Nanda, Gaurav and Aguilera Servin, Juan L and Rakyta, Péter and Kormányos, Andor and Kleiner, Reinhold and Koelle, Dieter and Watanabe, Kazuo and Taniguchi, Takashi and Vandersypen, Lieven and Goswami, Srijit}, issn = {15306984}, journal = {Nano Letters}, number = {6}, pages = {3396 -- 3401}, publisher = {American Chemical Society}, title = {{Current-phase relation of ballistic graphene Josephson junctions}}, doi = {10.1021/acs.nanolett.7b00097}, volume = {17}, year = {2017}, } @article{993, abstract = {In real-world applications, observations are often constrained to a small fraction of a system. Such spatial subsampling can be caused by the inaccessibility or the sheer size of the system, and cannot be overcome by longer sampling. Spatial subsampling can strongly bias inferences about a system’s aggregated properties. To overcome the bias, we derive analytically a subsampling scaling framework that is applicable to different observables, including distributions of neuronal avalanches, of number of people infected during an epidemic outbreak, and of node degrees. We demonstrate how to infer the correct distributions of the underlying full system, how to apply it to distinguish critical from subcritical systems, and how to disentangle subsampling and finite size effects. Lastly, we apply subsampling scaling to neuronal avalanche models and to recordings from developing neural networks. We show that only mature, but not young networks follow power-law scaling, indicating self-organization to criticality during development.}, author = {Levina (Martius), Anna and Priesemann, Viola}, issn = {20411723}, journal = {Nature Communications}, publisher = {Nature Publishing Group}, title = {{Subsampling scaling}}, doi = {10.1038/ncomms15140}, volume = {8}, year = {2017}, } @article{995, abstract = {Recently it was shown that an impurity exchanging orbital angular momentum with a surrounding bath can be described in terms of the angulon quasiparticle [Phys. Rev. Lett. 118, 095301 (2017)]. The angulon consists of a quantum rotor dressed by a many-particle field of boson excitations, and can be formed out of, for example, a molecule or a nonspherical atom in superfluid helium, or out of an electron coupled to lattice phonons or a Bose condensate. Here we develop an approach to the angulon based on the path-integral formalism, which sets the ground for a systematic, perturbative treatment of the angulon problem. The resulting perturbation series can be interpreted in terms of Feynman diagrams, from which, in turn, one can derive a set of diagrammatic rules. These rules extend the machinery of the graphical theory of angular momentum - well known from theoretical atomic spectroscopy - to the case where an environment with an infinite number of degrees of freedom is present. In particular, we show that each diagram can be interpreted as a 'skeleton', which enforces angular momentum conservation, dressed by an additional many-body contribution. This connection between the angulon theory and the graphical theory of angular momentum is particularly important as it allows to systematically and substantially simplify the analytical representation of each diagram. In order to exemplify the technique, we calculate the 1- and 2-loop contributions to the angulon self-energy, the spectral function, and the quasiparticle weight. The diagrammatic theory we develop paves the way to investigate next-to-leading order quantities in a more compact way compared to the variational approaches.}, author = {Bighin, Giacomo and Lemeshko, Mikhail}, issn = {24699950}, journal = {Physical Review B - Condensed Matter and Materials Physics}, number = {8}, publisher = {American Physical Society}, title = {{Diagrammatic approach to orbital quantum impurities interacting with a many-particle environment}}, doi = {10.1103/PhysRevB.96.085410}, volume = {96}, year = {2017}, } @inproceedings{989, abstract = {We present a generalized optimal transport model in which the mass-preserving constraint for the L2-Wasserstein distance is relaxed by introducing a source term in the continuity equation. The source term is also incorporated in the path energy by means of its squared L2-norm in time of a functional with linear growth in space. This extension of the original transport model enables local density modulations, which is a desirable feature in applications such as image warping and blending. A key advantage of the use of a functional with linear growth in space is that it allows for singular sources and sinks, which can be supported on points or lines. On a technical level, the L2-norm in time ensures a disintegration of the source in time, which we use to obtain the well-posedness of the model and the existence of geodesic paths. The numerical discretization is based on the proximal splitting approach [18] and selected numerical test cases show the potential of the proposed approach. Furthermore, the approach is applied to the warping and blending of textures.}, author = {Maas, Jan and Rumpf, Martin and Simon, Stefan}, editor = {Lauze, François and Dong, Yiqiu and Bjorholm Dahl, Anders}, issn = {03029743}, location = {Kolding, Denmark}, pages = {563 -- 577}, publisher = {Springer}, title = {{Transport based image morphing with intensity modulation}}, doi = {10.1007/978-3-319-58771-4_45}, volume = {10302}, year = {2017}, } @article{994, abstract = {The formation of vortices is usually considered to be the main mechanism of angular momentum disposal in superfluids. Recently, it was predicted that a superfluid can acquire angular momentum via an alternative, microscopic route -- namely, through interaction with rotating impurities, forming so-called `angulon quasiparticles' [Phys. Rev. Lett. 114, 203001 (2015)]. The angulon instabilities correspond to transfer of a small number of angular momentum quanta from the impurity to the superfluid, as opposed to vortex instabilities, where angular momentum is quantized in units of ℏ per atom. Furthermore, since conventional impurities (such as molecules) represent three-dimensional (3D) rotors, the angular momentum transferred is intrinsically 3D as well, as opposed to a merely planar rotation which is inherent to vortices. Herein we show that the angulon theory can explain the anomalous broadening of the spectroscopic lines observed for CH 3 and NH 3 molecules in superfluid helium nanodroplets, thereby providing a fingerprint of the emerging angulon instabilities in experiment.}, author = {Cherepanov, Igor and Lemeshko, Mikhail}, journal = {Physical Review Materials}, number = {3}, publisher = {American Physical Society}, title = {{Fingerprints of angulon instabilities in the spectra of matrix-isolated molecules}}, doi = {10.1103/PhysRevMaterials.1.035602}, volume = {1}, year = {2017}, } @article{991, abstract = {Synaptotagmin 7 (Syt7) was originally identified as a slow Ca2+ sensor for lysosome fusion, but its function at fast synapses is controversial. The paper by Luo and Südhof (2017) in this issue of Neuron shows that at the calyx of Held in the auditory brainstem Syt7 triggers asynchronous release during stimulus trains, resulting in reliable and temporally precise high-frequency transmission. Thus, a slow Ca2+ sensor contributes to the fast signaling properties of the calyx synapse.}, author = {Chen, Chong and Jonas, Peter M}, issn = {08966273}, journal = {Neuron}, number = {4}, pages = {694 -- 696}, publisher = {Elsevier}, title = {{Synaptotagmins: That’s why so many}}, doi = {10.1016/j.neuron.2017.05.011}, volume = {94}, year = {2017}, } @article{954, abstract = {Understanding the relation between genotype and phenotype remains a major challenge. The difficulty of predicting individual mutation effects, and particularly the interactions between them, has prevented the development of a comprehensive theory that links genotypic changes to their phenotypic effects. We show that a general thermodynamic framework for gene regulation, based on a biophysical understanding of protein-DNA binding, accurately predicts the sign of epistasis in a canonical cis-regulatory element consisting of overlapping RNA polymerase and repressor binding sites. Sign and magnitude of individual mutation effects are sufficient to predict the sign of epistasis and its environmental dependence. Thus, the thermodynamic model offers the correct null prediction for epistasis between mutations across DNA-binding sites. Our results indicate that a predictive theory for the effects of cis-regulatory mutations is possible from first principles, as long as the essential molecular mechanisms and the constraints these impose on a biological system are accounted for.}, author = {Lagator, Mato and Paixao, Tiago and Barton, Nicholas H and Bollback, Jonathan P and Guet, Calin C}, issn = {2050084X}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{On the mechanistic nature of epistasis in a canonical cis-regulatory element}}, doi = {10.7554/eLife.25192}, volume = {6}, year = {2017}, } @article{955, abstract = {Gene expression is controlled by networks of regulatory proteins that interact specifically with external signals and DNA regulatory sequences. These interactions force the network components to co-evolve so as to continually maintain function. Yet, existing models of evolution mostly focus on isolated genetic elements. In contrast, we study the essential process by which regulatory networks grow: the duplication and subsequent specialization of network components. We synthesize a biophysical model of molecular interactions with the evolutionary framework to find the conditions and pathways by which new regulatory functions emerge. We show that specialization of new network components is usually slow, but can be drastically accelerated in the presence of regulatory crosstalk and mutations that promote promiscuous interactions between network components.}, author = {Friedlander, Tamar and Prizak, Roshan and Barton, Nicholas H and Tkacik, Gasper}, issn = {20411723}, journal = {Nature Communications}, number = {1}, publisher = {Nature Publishing Group}, title = {{Evolution of new regulatory functions on biophysically realistic fitness landscapes}}, doi = {10.1038/s41467-017-00238-8}, volume = {8}, year = {2017}, } @inproceedings{962, abstract = {We present a new algorithm for model counting of a class of string constraints. In addition to the classic operation of concatenation, our class includes some recursively defined operations such as Kleene closure, and replacement of substrings. Additionally, our class also includes length constraints on the string expressions, which means, by requiring reasoning about numbers, that we face a multi-sorted logic. In the end, our string constraints are motivated by their use in programming for web applications. Our algorithm comprises two novel features: the ability to use a technique of (1) partial derivatives for constraints that are already in a solved form, i.e. a form where its (string) satisfiability is clearly displayed, and (2) non-progression, where cyclic reasoning in the reduction process may be terminated (thus allowing for the algorithm to look elsewhere). Finally, we experimentally compare our model counter with two recent works on model counting of similar constraints, SMC [18] and ABC [5], to demonstrate its superior performance.}, author = {Trinh, Minh and Chu, Duc Hiep and Jaffar, Joxan}, editor = {Majumdar, Rupak and Kunčak, Viktor}, issn = {03029743}, location = {Heidelberg, Germany}, pages = {399 -- 418}, publisher = {Springer}, title = {{Model counting for recursively-defined strings}}, doi = {10.1007/978-3-319-63390-9_21}, volume = {10427}, year = {2017}, } @article{953, abstract = {The role of natural selection in the evolution of adaptive phenotypes has undergone constant probing by evolutionary biologists, employing both theoretical and empirical approaches. As Darwin noted, natural selection can act together with other processes, including random changes in the frequencies of phenotypic differences that are not under strong selection, and changes in the environment, which may reflect evolutionary changes in the organisms themselves. As understanding of genetics developed after 1900, the new genetic discoveries were incorporated into evolutionary biology. The resulting general principles were summarized by Julian Huxley in his 1942 book Evolution: the modern synthesis. Here, we examine how recent advances in genetics, developmental biology and molecular biology, including epigenetics, relate to today's understanding of the evolution of adaptations. We illustrate how careful genetic studies have repeatedly shown that apparently puzzling results in a wide diversity of organisms involve processes that are consistent with neo-Darwinism. They do not support important roles in adaptation for processes such as directed mutation or the inheritance of acquired characters, and therefore no radical revision of our understanding of the mechanism of adaptive evolution is needed.}, author = {Charlesworth, Deborah and Barton, Nicholas H and Charlesworth, Brian}, journal = {Proceedings of the Royal Society of London Series B Biological Sciences}, number = {1855}, publisher = {Royal Society, The}, title = {{The sources of adaptive evolution}}, doi = {10.1098/rspb.2016.2864}, volume = {284}, year = {2017}, } @article{959, abstract = {In this work it is shown that scale-free tails in metabolic flux distributions inferred in stationary models are an artifact due to reactions involved in thermodynamically unfeasible cycles, unbounded by physical constraints and in principle able to perform work without expenditure of free energy. After implementing thermodynamic constraints by removing such loops, metabolic flux distributions scale meaningfully with the physical limiting factors, acquiring in turn a richer multimodal structure potentially leading to symmetry breaking while optimizing for objective functions.}, author = {De Martino, Daniele}, issn = {24700045}, journal = { Physical Review E Statistical Nonlinear and Soft Matter Physics }, number = {6}, pages = {062419}, publisher = {American Institute of Physics}, title = {{Scales and multimodal flux distributions in stationary metabolic network models via thermodynamics}}, doi = {10.1103/PhysRevE.95.062419}, volume = {95}, year = {2017}, } @article{956, abstract = {We study a class of ergodic quantum Markov semigroups on finite-dimensional unital C⁎-algebras. These semigroups have a unique stationary state σ, and we are concerned with those that satisfy a quantum detailed balance condition with respect to σ. We show that the evolution on the set of states that is given by such a quantum Markov semigroup is gradient flow for the relative entropy with respect to σ in a particular Riemannian metric on the set of states. This metric is a non-commutative analog of the 2-Wasserstein metric, and in several interesting cases we are able to show, in analogy with work of Otto on gradient flows with respect to the classical 2-Wasserstein metric, that the relative entropy is strictly and uniformly convex with respect to the Riemannian metric introduced here. As a consequence, we obtain a number of new inequalities for the decay of relative entropy for ergodic quantum Markov semigroups with detailed balance.}, author = {Carlen, Eric and Maas, Jan}, issn = {00221236}, journal = {Journal of Functional Analysis}, number = {5}, pages = {1810 -- 1869}, publisher = {Academic Press}, title = {{Gradient flow and entropy inequalities for quantum Markov semigroups with detailed balance}}, doi = {10.1016/j.jfa.2017.05.003}, volume = {273}, year = {2017}, } @article{952, abstract = {A novel strategy for controlling the spread of arboviral diseases such as dengue, Zika and chikungunya is to transform mosquito populations with virus-suppressing Wolbachia. In general, Wolbachia transinfected into mosquitoes induce fitness costs through lower viability or fecundity. These maternally inherited bacteria also produce a frequency-dependent advantage for infected females by inducing cytoplasmic incompatibility (CI), which kills the embryos produced by uninfected females mated to infected males. These competing effects, a frequency-dependent advantage and frequency-independent costs, produce bistable Wolbachia frequency dynamics. Above a threshold frequency, denoted pˆ, CI drives fitness-decreasing Wolbachia transinfections through local populations; but below pˆ, infection frequencies tend to decline to zero. If pˆ is not too high, CI also drives spatial spread once infections become established over sufficiently large areas. We illustrate how simple models provide testable predictions concerning the spatial and temporal dynamics of Wolbachia introductions, focusing on rate of spatial spread, the shape of spreading waves, and the conditions for initiating spread from local introductions. First, we consider the robustness of diffusion-based predictions to incorporating two important features of wMel-Aedes aegypti biology that may be inconsistent with the diffusion approximations, namely fast local dynamics induced by complete CI (i.e., all embryos produced from incompatible crosses die) and long-tailed, non-Gaussian dispersal. With complete CI, our numerical analyses show that long-tailed dispersal changes wave-width predictions only slightly; but it can significantly reduce wave speed relative to the diffusion prediction; it also allows smaller local introductions to initiate spatial spread. Second, we use approximations for pˆ and dispersal distances to predict the outcome of 2013 releases of wMel-infected Aedes aegypti in Cairns, Australia, Third, we describe new data from Ae. aegypti populations near Cairns, Australia that demonstrate long-distance dispersal and provide an approximate lower bound on pˆ for wMel in northeastern Australia. Finally, we apply our analyses to produce operational guidelines for efficient transformation of vector populations over large areas. We demonstrate that even very slow spatial spread, on the order of 10-20 m/month (as predicted), can produce area-wide population transformation within a few years following initial releases covering about 20-30% of the target area.}, author = {Turelli, Michael and Barton, Nicholas H}, issn = {00405809}, journal = {Theoretical Population Biology}, pages = {45 -- 60}, publisher = {Elsevier}, title = {{Deploying dengue-suppressing Wolbachia: Robust models predict slow but effective spatial spread in Aedes aegypti}}, doi = {10.1016/j.tpb.2017.03.003}, volume = {115}, year = {2017}, } @article{951, abstract = {Dengue-suppressing Wolbachia strains are promising tools for arbovirus control, particularly as they have the potential to self-spread following local introductions. To test this, we followed the frequency of the transinfected Wolbachia strain wMel through Ae. aegypti in Cairns, Australia, following releases at 3 nonisolated locations within the city in early 2013. Spatial spread was analysed graphically using interpolation and by fitting a statistical model describing the position and width of the wave. For the larger 2 of the 3 releases (covering 0.97 km2 and 0.52 km2), we observed slow but steady spatial spread, at about 100–200 m per year, roughly consistent with theoretical predictions. In contrast, the smallest release (0.11 km2) produced erratic temporal and spatial dynamics, with little evidence of spread after 2 years. This is consistent with the prediction concerning fitness-decreasing Wolbachia transinfections that a minimum release area is needed to achieve stable local establishment and spread in continuous habitats. Our graphical and likelihood analyses produced broadly consistent estimates of wave speed and wave width. Spread at all sites was spatially heterogeneous, suggesting that environmental heterogeneity will affect large-scale Wolbachia transformations of urban mosquito populations. The persistence and spread of Wolbachia in release areas meeting minimum area requirements indicates the promise of successful large-scale population transfo}, author = {Schmidt, Tom and Barton, Nicholas H and Rasic, Gordana and Turley, Andrew and Montgomery, Brian and Iturbe Ormaetxe, Inaki and Cook, Peter and Ryan, Peter and Ritchie, Scott and Hoffmann, Ary and O’Neill, Scott and Turelli, Michael}, issn = {15449173}, journal = {PLoS Biology}, number = {5}, publisher = {Public Library of Science}, title = {{Local introduction and heterogeneous spatial spread of dengue-suppressing Wolbachia through an urban population of Aedes Aegypti}}, doi = {10.1371/journal.pbio.2001894}, volume = {15}, year = {2017}, } @article{947, abstract = {Viewing the ways a living cell can organize its metabolism as the phase space of a physical system, regulation can be seen as the ability to reduce the entropy of that space by selecting specific cellular configurations that are, in some sense, optimal. Here we quantify the amount of regulation required to control a cell's growth rate by a maximum-entropy approach to the space of underlying metabolic phenotypes, where a configuration corresponds to a metabolic flux pattern as described by genome-scale models. We link the mean growth rate achieved by a population of cells to the minimal amount of metabolic regulation needed to achieve it through a phase diagram that highlights how growth suppression can be as costly (in regulatory terms) as growth enhancement. Moreover, we provide an interpretation of the inverse temperature β controlling maximum-entropy distributions based on the underlying growth dynamics. Specifically, we show that the asymptotic value of β for a cell population can be expected to depend on (i) the carrying capacity of the environment, (ii) the initial size of the colony, and (iii) the probability distribution from which the inoculum was sampled. Results obtained for E. coli and human cells are found to be remarkably consistent with empirical evidence.}, author = {De Martino, Daniele and Capuani, Fabrizio and De Martino, Andrea}, issn = {24700045}, journal = { Physical Review E Statistical Nonlinear and Soft Matter Physics }, number = {1}, publisher = {American Institute of Physics}, title = {{Quantifying the entropic cost of cellular growth control}}, doi = {10.1103/PhysRevE.96.010401}, volume = {96}, year = {2017}, } @misc{9858, author = {Schmidt, Tom and Barton, Nicholas H and Rasic, Gordana and Turley, Andrew and Montgomery, Brian and Iturbe Ormaetxe, Inaki and Cook, Peter and Ryan, Peter and Ritchie, Scott and Hoffmann, Ary and O’Neill, Scott and Turelli, Michael}, publisher = {Public Library of Science}, title = {{Excel file with data on mosquito densities, Wolbachia infection status and housing characteristics}}, doi = {10.1371/journal.pbio.2001894.s016}, year = {2017}, } @misc{9857, author = {Schmidt, Tom and Barton, Nicholas H and Rasic, Gordana and Turley, Andrew and Montgomery, Brian and Iturbe Ormaetxe, Inaki and Cook, Peter and Ryan, Peter and Ritchie, Scott and Hoffmann, Ary and O’Neill, Scott and Turelli, Michael}, publisher = {Public Library of Science }, title = {{Supporting information concerning observed wMel frequencies and analyses of habitat variables}}, doi = {10.1371/journal.pbio.2001894.s015}, year = {2017}, } @misc{9856, author = {Schmidt, Tom and Barton, Nicholas H and Rasic, Gordana and Turley, Andrew and Montgomery, Brian and Iturbe Ormaetxe, Inaki and Cook, Peter and Ryan, Peter and Ritchie, Scott and Hoffmann, Ary and O’Neill, Scott and Turelli, Michael}, publisher = {Public Library of Science}, title = {{Supporting Information concerning additional likelihood analyses and results}}, doi = {10.1371/journal.pbio.2001894.s014}, year = {2017}, } @article{945, abstract = {While chromosome-wide dosage compensation of the X chromosome has been found in many species, studies in ZW clades have indicated that compensation of the Z is more localized and/or incomplete. In the ZW Lepidoptera, some species show complete compensation of the Z chromosome, while others lack full equalization, but what drives these inconsistencies is unclear. Here, we compare patterns of male and female gene expression on the Z chromosome of two closely related butterfly species, Papilio xuthus and Papilio machaon, and in multiple tissues of two moths species, Plodia interpunctella and Bombyx mori, which were previously found to differ in the extent to which they equalize Z-linked gene expression between the sexes. We find that, while some species and tissues seem to have incomplete dosage compensation, this is in fact due to the accumulation of male-biased genes and the depletion of female-biased genes on the Z chromosome. Once this is accounted for, the Z chromosome is fully compensated in all four species, through the up-regulation of Z expression in females and in some cases additional down-regulation in males. We further find that both sex-biased genes and Z-linked genes have increased rates of expression divergence in this clade, and that this can lead to fast shifts in patterns of gene expression even between closely related species. Taken together, these results show that the uneven distribution of sex-biased genes on sex chromosomes can confound conclusions about dosage compensation and that Z chromosome-wide dosage compensation is not only possible but ubiquitous among Lepidoptera.}, author = {Huylmans, Ann K and Macon, Ariana and Vicoso, Beatriz}, issn = {07374038}, journal = {Molecular Biology and Evolution}, number = {10}, pages = {2637 -- 2649}, publisher = {Oxford University Press}, title = {{Global dosage compensation is ubiquitous in Lepidoptera, but counteracted by the masculinization of the Z chromosome}}, doi = {10.1093/molbev/msx190}, volume = {34}, year = {2017}, } @article{751, abstract = {The basement membrane (BM) is a thin layer of extracellular matrix (ECM) beneath nearly all epithelial cell types that is critical for cellular and tissue function. It is composed of numerous components conserved among all bilaterians [1]; however, it is unknown how all of these components are generated and subsequently constructed to form a fully mature BM in the living animal. Although BM formation is thought to simply involve a process of self-assembly [2], this concept suffers from a number of logistical issues when considering its construction in vivo. First, incorporation of BM components appears to be hierarchical [3-5], yet it is unclear whether their production during embryogenesis must also be regulated in a temporal fashion. Second, many BM proteins are produced not only by the cells residing on the BM but also by surrounding cell types [6-9], and it is unclear how large, possibly insoluble protein complexes [10] are delivered into the matrix. Here we exploit our ability to live image and genetically dissect de novo BM formation during Drosophila development. This reveals that there is a temporal hierarchy of BM protein production that is essential for proper component incorporation. Furthermore, we show that BM components require secretion by migrating macrophages (hemocytes) during their developmental dispersal, which is critical for embryogenesis. Indeed, hemocyte migration is essential to deliver a subset of ECM components evenly throughout the embryo. This reveals that de novo BM construction requires a combination of both production and distribution logistics allowing for the timely delivery of core components.}, author = {Matsubayashi, Yutaka and Louani, Adam and Dragu, Anca and Sanchez Sanchez, Besaiz and Serna Morales, Eduardo and Yolland, Lawrence and György, Attila and Vizcay, Gema and Fleck, Roland and Heddleston, John and Chew, Teng and Siekhaus, Daria E and Stramer, Brian}, issn = {09609822}, journal = {Current Biology}, number = {22}, pages = {3526 -- 3534e.4}, publisher = {Cell Press}, title = {{A moving source of matrix components is essential for De Novo basement membrane formation}}, doi = {10.1016/j.cub.2017.10.001}, volume = {27}, year = {2017}, } @article{798, abstract = {Nonreciprocal circuit elements form an integral part of modern measurement and communication systems. Mathematically they require breaking of time-reversal symmetry, typically achieved using magnetic materials and more recently using the quantum Hall effect, parametric permittivity modulation or Josephson nonlinearities. Here we demonstrate an on-chip magnetic-free circulator based on reservoir-engineered electromechanic interactions. Directional circulation is achieved with controlled phase-sensitive interference of six distinct electro-mechanical signal conversion paths. The presented circulator is compact, its silicon-on-insulator platform is compatible with both superconducting qubits and silicon photonics, and its noise performance is close to the quantum limit. With a high dynamic range, a tunable bandwidth of up to 30 MHz and an in situ reconfigurability as beam splitter or wavelength converter, it could pave the way for superconducting qubit processors with multiplexed on-chip signal processing and readout.}, author = {Barzanjeh, Shabir and Wulf, Matthias and Peruzzo, Matilda and Kalaee, Mahmoud and Dieterle, Paul and Painter, Oskar and Fink, Johannes M}, issn = {20411723}, journal = {Nature Communications}, number = {1}, publisher = {Nature Publishing Group}, title = {{Mechanical on chip microwave circulator}}, doi = {10.1038/s41467-017-01304-x}, volume = {8}, year = {2017}, } @inproceedings{791, abstract = {Consider the following random process: we are given n queues, into which elements of increasing labels are inserted uniformly at random. To remove an element, we pick two queues at random, and remove the element of lower label (higher priority) among the two. The cost of a removal is the rank of the label removed, among labels still present in any of the queues, that is, the distance from the optimal choice at each step. Variants of this strategy are prevalent in state-of-the-art concurrent priority queue implementations. Nonetheless, it is not known whether such implementations provide any rank guarantees, even in a sequential model. We answer this question, showing that this strategy provides surprisingly strong guarantees: Although the single-choice process, where we always insert and remove from a single randomly chosen queue, has degrading cost, going to infinity as we increase the number of steps, in the two choice process, the expected rank of a removed element is O(n) while the expected worst-case cost is O(n log n). These bounds are tight, and hold irrespective of the number of steps for which we run the process. The argument is based on a new technical connection between "heavily loaded" balls-into-bins processes and priority scheduling. Our analytic results inspire a new concurrent priority queue implementation, which improves upon the state of the art in terms of practical performance.}, author = {Alistarh, Dan-Adrian and Kopinsky, Justin and Li, Jerry and Nadiradze, Giorgi}, booktitle = {Proceedings of the ACM Symposium on Principles of Distributed Computing}, isbn = {978-145034992-5}, location = {Washington, WA, USA}, pages = {283 -- 292}, publisher = {ACM}, title = {{The power of choice in priority scheduling}}, doi = {10.1145/3087801.3087810}, volume = {Part F129314}, year = {2017}, } @article{792, abstract = {The chaotic dynamics of low-dimensional systems, such as Lorenz or Rössler flows, is guided by the infinity of periodic orbits embedded in their strange attractors. Whether this is also the case for the infinite-dimensional dynamics of Navier–Stokes equations has long been speculated, and is a topic of ongoing study. Periodic and relative periodic solutions have been shown to be involved in transitions to turbulence. Their relevance to turbulent dynamics – specifically, whether periodic orbits play the same role in high-dimensional nonlinear systems like the Navier–Stokes equations as they do in lower-dimensional systems – is the focus of the present investigation. We perform here a detailed study of pipe flow relative periodic orbits with energies and mean dissipations close to turbulent values. We outline several approaches to reduction of the translational symmetry of the system. We study pipe flow in a minimal computational cell at Re=2500, and report a library of invariant solutions found with the aid of the method of slices. Detailed study of the unstable manifolds of a sample of these solutions is consistent with the picture that relative periodic orbits are embedded in the chaotic saddle and that they guide the turbulent dynamics.}, author = {Budanur, Nazmi B and Short, Kimberly and Farazmand, Mohammad and Willis, Ashley and Cvitanović, Predrag}, issn = {00221120}, journal = {Journal of Fluid Mechanics}, pages = {274 -- 301}, publisher = {Cambridge University Press}, title = {{Relative periodic orbits form the backbone of turbulent pipe flow}}, doi = {10.1017/jfm.2017.699}, volume = {833}, year = {2017}, } @article{796, abstract = {We present the fabrication and characterization of an aluminum transmon qubit on a silicon-on-insulator substrate. Key to the qubit fabrication is the use of an anhydrous hydrofluoric vapor process which selectively removes the lossy silicon oxide buried underneath the silicon device layer. For a 5.6 GHz qubit measured dispersively by a 7.1 GHz resonator, we find T1 = 3.5 μs and T∗2 = 2.2 μs. This process in principle permits the co-fabrication of silicon photonic and mechanical elements, providing a route towards chip-scale integration of electro-opto-mechanical transducers for quantum networking of superconducting microwave quantum circuits. The additional processing steps are compatible with established fabrication techniques for aluminum transmon qubits on silicon.}, author = {Keller, Andrew J and Dieterle, Paul and Fang, Michael and Berger, Brett and Fink, Johannes M and Painter, Oskar}, issn = {00036951}, journal = {Applied Physics Letters}, number = {4}, publisher = {American Institute of Physics}, title = {{Al transmon qubits on silicon on insulator for quantum device integration}}, doi = {10.1063/1.4994661}, volume = {111}, year = {2017}, } @article{793, abstract = {Let P be a finite point set in the plane. A cordinary triangle in P is a subset of P consisting of three non-collinear points such that each of the three lines determined by the three points contains at most c points of P . Motivated by a question of Erdös, and answering a question of de Zeeuw, we prove that there exists a constant c > 0such that P contains a c-ordinary triangle, provided that P is not contained in the union of two lines. Furthermore, the number of c-ordinary triangles in P is Ω(| P |). }, author = {Fulek, Radoslav and Mojarrad, Hossein and Naszódi, Márton and Solymosi, József and Stich, Sebastian and Szedlák, May}, issn = {09257721}, journal = {Computational Geometry: Theory and Applications}, pages = {28 -- 31}, publisher = {Elsevier}, title = {{On the existence of ordinary triangles}}, doi = {10.1016/j.comgeo.2017.07.002}, volume = {66}, year = {2017}, } @article{794, abstract = {We show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle.}, author = {Fulek, Radoslav}, journal = {Computational Geometry: Theory and Applications}, pages = {1 -- 13}, publisher = {Elsevier}, title = {{C-planarity of embedded cyclic c-graphs}}, doi = {10.1016/j.comgeo.2017.06.016}, volume = {66}, year = {2017}, }