@article{7421, abstract = {X and Y chromosomes can diverge when rearrangements block recombination between them. Here we present the first genomic view of a reciprocal translocation that causes two physically unconnected pairs of chromosomes to be coinherited as sex chromosomes. In a population of the common frog (Rana temporaria), both pairs of X and Y chromosomes show extensive sequence differentiation, but not degeneration of the Y chromosomes. A new method based on gene trees shows both chromosomes are sex‐linked. Furthermore, the gene trees from the two Y chromosomes have identical topologies, showing they have been coinherited since the reciprocal translocation occurred. Reciprocal translocations can thus reshape sex linkage on a much greater scale compared with inversions, the type of rearrangement that is much better known in sex chromosome evolution, and they can greatly amplify the power of sexually antagonistic selection to drive genomic rearrangement. Two more populations show evidence of other rearrangements, suggesting that this species has unprecedented structural polymorphism in its sex chromosomes.}, author = {Toups, Melissa A and Rodrigues, Nicolas and Perrin, Nicolas and Kirkpatrick, Mark}, issn = {1365-294X}, journal = {Molecular Ecology}, number = {8}, pages = {1877--1889}, publisher = {Wiley}, title = {{A reciprocal translocation radically reshapes sex‐linked inheritance in the common frog}}, doi = {10.1111/mec.14990}, volume = {28}, year = {2019}, } @inproceedings{7411, abstract = {Proofs of sequential work (PoSW) are proof systems where a prover, upon receiving a statement χ and a time parameter T computes a proof ϕ(χ,T) which is efficiently and publicly verifiable. The proof can be computed in T sequential steps, but not much less, even by a malicious party having large parallelism. A PoSW thus serves as a proof that T units of time have passed since χ was received. PoSW were introduced by Mahmoody, Moran and Vadhan [MMV11], a simple and practical construction was only recently proposed by Cohen and Pietrzak [CP18]. In this work we construct a new simple PoSW in the random permutation model which is almost as simple and efficient as [CP18] but conceptually very different. Whereas the structure underlying [CP18] is a hash tree, our construction is based on skip lists and has the interesting property that computing the PoSW is a reversible computation. The fact that the construction is reversible can potentially be used for new applications like constructing proofs of replication. We also show how to “embed” the sloth function of Lenstra and Weselowski [LW17] into our PoSW to get a PoSW where one additionally can verify correctness of the output much more efficiently than recomputing it (though recent constructions of “verifiable delay functions” subsume most of the applications this construction was aiming at).}, author = {Abusalah, Hamza M and Kamath Hosdurg, Chethan and Klein, Karen and Pietrzak, Krzysztof Z and Walter, Michael}, booktitle = {Advances in Cryptology – EUROCRYPT 2019}, isbn = {9783030176556}, issn = {1611-3349}, location = {Darmstadt, Germany}, pages = {277--291}, publisher = {Springer International Publishing}, title = {{Reversible proofs of sequential work}}, doi = {10.1007/978-3-030-17656-3_10}, volume = {11477}, year = {2019}, } @article{7406, abstract = {Background Synaptic vesicles (SVs) are an integral part of the neurotransmission machinery, and isolation of SVs from their host neuron is necessary to reveal their most fundamental biochemical and functional properties in in vitro assays. Isolated SVs from neurons that have been genetically engineered, e.g. to introduce genetically encoded indicators, are not readily available but would permit new insights into SV structure and function. Furthermore, it is unclear if cultured neurons can provide sufficient starting material for SV isolation procedures. New method Here, we demonstrate an efficient ex vivo procedure to obtain functional SVs from cultured rat cortical neurons after genetic engineering with a lentivirus. Results We show that ∼108 plated cortical neurons allow isolation of suitable SV amounts for functional analysis and imaging. We found that SVs isolated from cultured neurons have neurotransmitter uptake comparable to that of SVs isolated from intact cortex. Using total internal reflection fluorescence (TIRF) microscopy, we visualized an exogenous SV-targeted marker protein and demonstrated the high efficiency of SV modification. Comparison with existing methods Obtaining SVs from genetically engineered neurons currently generally requires the availability of transgenic animals, which is constrained by technical (e.g. cost and time) and biological (e.g. developmental defects and lethality) limitations. Conclusions These results demonstrate the modification and isolation of functional SVs using cultured neurons and viral transduction. The ability to readily obtain SVs from genetically engineered neurons will permit linking in situ studies to in vitro experiments in a variety of genetic contexts.}, author = {Mckenzie, Catherine and Spanova, Miroslava and Johnson, Alexander J and Kainrath, Stephanie and Zheden, Vanessa and Sitte, Harald H. and Janovjak, Harald L}, issn = {0165-0270}, journal = {Journal of Neuroscience Methods}, pages = {114--121}, publisher = {Elsevier}, title = {{Isolation of synaptic vesicles from genetically engineered cultured neurons}}, doi = {10.1016/j.jneumeth.2018.11.018}, volume = {312}, year = {2019}, } @inproceedings{7437, abstract = {Most of today's distributed machine learning systems assume reliable networks: whenever two machines exchange information (e.g., gradients or models), the network should guarantee the delivery of the message. At the same time, recent work exhibits the impressive tolerance of machine learning algorithms to errors or noise arising from relaxed communication or synchronization. In this paper, we connect these two trends, and consider the following question: Can we design machine learning systems that are tolerant to network unreliability during training? With this motivation, we focus on a theoretical problem of independent interest-given a standard distributed parameter server architecture, if every communication between the worker and the server has a non-zero probability p of being dropped, does there exist an algorithm that still converges, and at what speed? The technical contribution of this paper is a novel theoretical analysis proving that distributed learning over unreliable network can achieve comparable convergence rate to centralized or distributed learning over reliable networks. Further, we prove that the influence of the packet drop rate diminishes with the growth of the number of parameter servers. We map this theoretical result onto a real-world scenario, training deep neural networks over an unreliable network layer, and conduct network simulation to validate the system improvement by allowing the networks to be unreliable.}, author = {Yu, Chen and Tang, Hanlin and Renggli, Cedric and Kassing, Simon and Singla, Ankit and Alistarh, Dan-Adrian and Zhang, Ce and Liu, Ji}, booktitle = {36th International Conference on Machine Learning, ICML 2019}, isbn = {9781510886988}, location = {Long Beach, CA, United States}, pages = {12481--12512}, publisher = {IMLS}, title = {{Distributed learning over unreliable networks}}, volume = {2019-June}, year = {2019}, } @article{7412, abstract = {We develop a framework for the rigorous analysis of focused stochastic local search algorithms. These algorithms search a state space by repeatedly selecting some constraint that is violated in the current state and moving to a random nearby state that addresses the violation, while (we hope) not introducing many new violations. An important class of focused local search algorithms with provable performance guarantees has recently arisen from algorithmizations of the Lovász local lemma (LLL), a nonconstructive tool for proving the existence of satisfying states by introducing a background measure on the state space. While powerful, the state transitions of algorithms in this class must be, in a precise sense, perfectly compatible with the background measure. In many applications this is a very restrictive requirement, and one needs to step outside the class. Here we introduce the notion of measure distortion and develop a framework for analyzing arbitrary focused stochastic local search algorithms, recovering LLL algorithmizations as the special case of no distortion. Our framework takes as input an arbitrary algorithm of such type and an arbitrary probability measure and shows how to use the measure as a yardstick of algorithmic progress, even for algorithms designed independently of the measure.}, author = {Achlioptas, Dimitris and Iliopoulos, Fotis and Kolmogorov, Vladimir}, issn = {1095-7111}, journal = {SIAM Journal on Computing}, number = {5}, pages = {1583--1602}, publisher = {SIAM}, title = {{A local lemma for focused stochastical algorithms}}, doi = {10.1137/16m109332x}, volume = {48}, year = {2019}, } @article{7418, abstract = {Multiple importance sampling (MIS) has become an indispensable tool in Monte Carlo rendering, widely accepted as a near-optimal solution for combining different sampling techniques. But an MIS combination, using the common balance or power heuristics, often results in an overly defensive estimator, leading to high variance. We show that by generalizing the MIS framework, variance can be substantially reduced. Specifically, we optimize one of the combined sampling techniques so as to decrease the overall variance of the resulting MIS estimator. We apply the approach to the computation of direct illumination due to an HDR environment map and to the computation of global illumination using a path guiding algorithm. The implementation can be as simple as subtracting a constant value from the tabulated sampling density done entirely in a preprocessing step. This produces a consistent noise reduction in all our tests with no negative influence on run time, no artifacts or bias, and no failure cases.}, author = {Karlík, Ondřej and Šik, Martin and Vévoda, Petr and Skrivan, Tomas and Křivánek, Jaroslav}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, number = {6}, publisher = {ACM}, title = {{MIS compensation: Optimizing sampling techniques in multiple importance sampling}}, doi = {10.1145/3355089.3356565}, volume = {38}, year = {2019}, } @article{7413, abstract = {We consider Bose gases consisting of N particles trapped in a box with volume one and interacting through a repulsive potential with scattering length of order N−1 (Gross–Pitaevskii regime). We determine the ground state energy and the low-energy excitation spectrum, up to errors vanishing as N→∞. Our results confirm Bogoliubov’s predictions.}, author = {Boccato, Chiara and Brennecke, Christian and Cenatiempo, Serena and Schlein, Benjamin}, issn = {1871-2509}, journal = {Acta Mathematica}, number = {2}, pages = {219--335}, publisher = {International Press of Boston}, title = {{Bogoliubov theory in the Gross–Pitaevskii limit}}, doi = {10.4310/acta.2019.v222.n2.a1}, volume = {222}, year = {2019}, } @article{7393, abstract = {The study of parallel ecological divergence provides important clues to the operation of natural selection. Parallel divergence often occurs in heterogeneous environments with different kinds of environmental gradients in different locations, but the genomic basis underlying this process is unknown. We investigated the genomics of rapid parallel adaptation in the marine snail Littorina saxatilis in response to two independent environmental axes (crab-predation versus wave-action and low-shore versus high-shore). Using pooled whole-genome resequencing, we show that sharing of genomic regions of high differentiation between environments is generally low but increases at smaller spatial scales. We identify different shared genomic regions of divergence for each environmental axis and show that most of these regions overlap with candidate chromosomal inversions. Several inversion regions are divergent and polymorphic across many localities. We argue that chromosomal inversions could store shared variation that fuels rapid parallel adaptation to heterogeneous environments, possibly as balanced polymorphism shared by adaptive gene flow.}, author = {Morales, Hernán E. and Faria, Rui and Johannesson, Kerstin and Larsson, Tomas and Panova, Marina and Westram, Anja M and Butlin, Roger K.}, issn = {2375-2548}, journal = {Science Advances}, number = {12}, publisher = {AAAS}, title = {{Genomic architecture of parallel ecological divergence: Beyond a single environmental contrast}}, doi = {10.1126/sciadv.aav9963}, volume = {5}, year = {2019}, } @article{7397, abstract = {Polymer additives can substantially reduce the drag of turbulent flows and the upperlimit, the so called “maximum drag reduction” (MDR) asymptote is universal, i.e. inde-pendent of the type of polymer and solvent used. Until recently, the consensus was that,in this limit, flows are in a marginal state where only a minimal level of turbulence activ-ity persists. Observations in direct numerical simulations using minimal sized channelsappeared to support this view and reported long “hibernation” periods where turbu-lence is marginalized. In simulations of pipe flow we find that, indeed, with increasingWeissenberg number (Wi), turbulence expresses long periods of hibernation if the domainsize is small. However, with increasing pipe length, the temporal hibernation continuouslyalters to spatio-temporal intermittency and here the flow consists of turbulent puffs sur-rounded by laminar flow. Moreover, upon an increase in Wi, the flow fully relaminarises,in agreement with recent experiments. At even larger Wi, a different instability is en-countered causing a drag increase towards MDR. Our findings hence link earlier minimalflow unit simulations with recent experiments and confirm that the addition of polymersinitially suppresses Newtonian turbulence and leads to a reverse transition. The MDRstate on the other hand results from a separate instability and the underlying dynamicscorresponds to the recently proposed state of elasto-inertial-turbulence (EIT).}, author = {Lopez Alonso, Jose M and Choueiri, George H and Hof, Björn}, issn = {1469-7645}, journal = {Journal of Fluid Mechanics}, pages = {699--719}, publisher = {CUP}, title = {{Dynamics of viscoelastic pipe flow at low Reynolds numbers in the maximum drag reduction limit}}, doi = {10.1017/jfm.2019.486}, volume = {874}, year = {2019}, } @article{5678, abstract = {The order-k Voronoi tessellation of a locally finite set 𝑋⊆ℝ𝑛 decomposes ℝ𝑛 into convex domains whose points have the same k nearest neighbors in X. Assuming X is a stationary Poisson point process, we give explicit formulas for the expected number and total area of faces of a given dimension per unit volume of space. We also develop a relaxed version of discrete Morse theory and generalize by counting only faces, for which the k nearest points in X are within a given distance threshold.}, author = {Edelsbrunner, Herbert and Nikitenko, Anton}, issn = {14320444}, journal = {Discrete and Computational Geometry}, number = {4}, pages = {865–878}, publisher = {Springer}, title = {{Poisson–Delaunay Mosaics of Order k}}, doi = {10.1007/s00454-018-0049-2}, volume = {62}, year = {2019}, }