@article{17698, abstract = {Gaseous circumbinary accretion discs provide a promising mechanism to facilitate the mergers of supermassive black holes (SMBHs) in galactic nuclei. We measure the torques exerted on accreting SMBH binaries, using 2D, isothermal, moving-mesh, viscous hydrodynamical simulations of circumbinary accretion discs. Our computational domain includes the entire inner region of the circumbinary disk with the individual black holes (BHs) included as point masses on the grid and a sink prescription to model accretion onto each BH. The BHs each acquire their own well-resolved accretion discs ("minidiscs"). We explore a range of mass removal rates for the sink prescription removing gas from the central regions of the minidiscs. We find that the torque exerted on the binary is primarily gravitational, and dominated by the gas orbiting close behind and ahead of the individual BHs. The torques from the distorted circumbinary disc farther out and from the direct accretion of angular momentum are subdominant. The torques are sensitive to the sink prescription: slower sinks result in more gas accumulating near the BHs and more negative torques, driving the binary to merger more rapidly. For faster sinks, the torques are less negative and eventually turn positive (for unphysically fast sinks). When the minidiscs are modeled as standard alpha discs, our results are insensitive to the choice of sink radius. Scaling the simulations to a binary orbital period tbin = 1yr and background disc accretion rate Mdot = 0.3MEdd in Eddington units, the binary inspirals on a timescale of 3X10^6 years, irrespective of the SMBH masses. For binaries with total mass <10^7Msun, this is shorter than the inspiral time due to gravitational wave (GW) emission alone, implying that gas discs will have a significant impact on the SMBH binary population and can affect the GW signal for Pulsar Timing Arrays.}, author = {Tang, Yike and MacFadyen, Andrew and Haiman, Zoltán}, issn = {0035-8711}, journal = {Monthly Notices of the Royal Astronomical Society}, number = {4}, pages = {4258--4267}, publisher = {Oxford University Press}, title = {{On the orbital evolution of supermassive black hole binaries with circumbinary accretion discs}}, doi = {10.1093/mnras/stx1130}, volume = {469}, year = {2017}, } @article{17706, abstract = {The Laser Interferometer Gravitational-Wave Observatory, LIGO, found direct evidence for double black hole binaries emitting gravitational waves. Galactic nuclei are expected to harbor the densest population of stellar-mass black holes. A significant fraction (∼30%) of these black holes can reside in binaries. We examine the fate of the black hole binaries in active galactic nuclei, which get trapped in the inner region of the accretion disk around the central supermassive black hole. We show that binary black holes can migrate into and then rapidly merge within the disk well within a Salpeter time. The binaries may also accrete a significant amount of gas from the disk, well above the Eddington rate. This could lead to detectable X-ray or gamma-ray emission, but would require hyper-Eddington accretion with a few percent radiative efficiency, comparable to thin disks. We discuss implications for gravitational wave observations and black hole population studies. We estimate that Advanced LIGO may detect ∼20 such, gas-induced binary mergers per year.}, author = {Bartos, Imre and Kocsis, Bence and Haiman, Zoltán and Márka, Szabolcs}, issn = {0004-637X}, journal = {The Astrophysical Journal}, number = {2}, publisher = {American Astronomical Society}, title = {{Rapid and bright stellar-mass binary black hole mergers in active galactic nuclei}}, doi = {10.3847/1538-4357/835/2/165}, volume = {835}, year = {2017}, } @article{17707, abstract = {The gravitational waves (GWs) from a binary black hole (BBH) with masses between 10^4 and 10^7 Msun can be detected with the Laser Interferometer Space Antenna (LISA) once their orbital frequency exceeds 10^-4 - 10^-5 Hz. The binary separation at this stage is approximately a=100 R_g (gravitational radius), and the orbital speed is of order v/c=0.1. We argue that at this stage, the binary will be producing bright electromagnetic (EM) radiation via gas bound to the individual BHs. Both BHs will have their own photospheres in X-ray and possibly also in optical bands. Relativistic Doppler modulations and lensing effects will inevitably imprint periodic variability in the EM light-curve, tracking the phase of the orbital motion, and serving as a template for the GW inspiral waveform. Advanced localization of the source by LISA weeks to months prior to merger will enable a measurement of this EM chirp by wide-field X-ray or optical instruments. A comparison of the phases of the GW and EM chirp signals will help break degeneracies between system parameters, and probe a fractional difference difference Delta v in the propagation speed of photons and gravitons as low as Delta v/c = O(10^-17).}, author = {Haiman, Zoltán}, issn = {2470-0010}, journal = {Physical Review D}, number = {2}, publisher = {American Physical Society}, title = {{Electromagnetic chirp of a compact binary black hole: A phase template for the gravitational wave inspiral}}, doi = {10.1103/physrevd.96.023004}, volume = {96}, year = {2017}, } @article{17708, abstract = {We explore the sensitivity of weak lensing observables to the expansion history of the universe and to the growth of cosmic structures, as well as the relative contribution of both effects to constraining cosmological parameters. We utilize ray-tracing dark-matter-only N-body simulations and validate our technique by comparing our results for the convergence power spectrum with analytic results from past studies. We then extend our analysis to non-Gaussian observables which cannot be easily treated analytically. We study the convergence (equilateral) bispectrum and two topological observables, lensing peaks and Minkowski functionals, focusing on their sensitivity to the matter density Ωm and the dark energy equation of state w. We find that a cancelation between the geometry and growth effects is a common feature for all observables, and exists at the map level. It weakens the overall sensitivity by up to a factor of 3 and 1.5 for w and Ωm, respectively, with the bispectrum worst affected. However, combining geometry and growth information alleviates the degeneracy between Ωm and w from either effect alone. As a result, the magnitude of marginalized errors remain similar to those obtained from growth-only effects, but with the correlation between the two parameters switching sign. These results shed light on the origin of cosmology-sensitivity of non-Gaussian statistics, and should be useful in optimizing combinations of observables.}, author = {Matilla, José Manuel Zorrilla and Haiman, Zoltán and Petri, Andrea and Namikawa, Toshiya}, issn = {2470-0010}, journal = {Physical Review D}, number = {2}, publisher = {American Physical Society}, title = {{Geometry and growth contributions to cosmic shear observables}}, doi = {10.1103/physrevd.96.023513}, volume = {96}, year = {2017}, } @article{17711, abstract = {The recent discovery of gravitational waves from stellar-mass binary black hole mergers by the Laser Interferometer Gravitational-wave Observatory opened the door to alternative probes of stellar and galactic evolution, cosmology and fundamental physics. Probing the origin of binary black hole mergers will be difficult due to the expected lack of electromagnetic emission and limited localization accuracy. Associations with rare host galaxy types—such as active galactic nuclei—can nevertheless be identified statistically through spatial correlation. Here we establish the feasibility of statistically proving the connection between binary black hole mergers and active galactic nuclei as hosts, even if only a sub-population of mergers originate from active galactic nuclei. Our results are the demonstration that the limited localization of gravitational waves, previously written off as not useful to distinguish progenitor channels, can in fact contribute key information, broadening the range of astrophysical questions probed by binary black hole observations.}, author = {Bartos, I. and Haiman, Zoltán and Marka, Z. and Metzger, B. D. and Stone, N. C. and Marka, S.}, issn = {2041-1723}, journal = {Nature Communications}, number = {1}, publisher = {Springer Science and Business Media LLC}, title = {{Gravitational-wave localization alone can probe origin of stellar-mass black hole mergers}}, doi = {10.1038/s41467-017-00851-7}, volume = {8}, year = {2017}, } @article{17712, abstract = {Multi-frequency gravitational wave (GW) observations are useful probes of the formation processes of coalescing stellar-mass binary black holes (BBHs). We discuss the phase drift in the GW inspiral waveform of the merging BBH caused by its center-of-mass acceleration. The acceleration strongly depends on the location where a BBH forms within a galaxy, allowing observations of the early inspiral phase of LIGO-like BBH mergers by the Laser Interferometer Space Antenna (LISA) to test the formation mechanism. In particular, BBHs formed in dense nuclear star clusters or via compact accretion disks around a nuclear supermassive black hole in active galactic nuclei would suffer strong acceleration, and produce large phase drifts measurable by LISA. The host galaxies of the coalescing BBHs in these scenarios can also be uniquely identified in the LISA error volume, without electromagnetic counterparts. A non-detection of phase drifts would rule out or constrain the contribution of the nuclear formation channels to the stellar-mass BBH population.}, author = {Inayoshi, Kohei and Tamanini, Nicola and Caprini, Chiara and Haiman, Zoltán}, issn = {2470-0010}, journal = {Physical Review D}, number = {6}, publisher = {American Physical Society }, title = {{Probing stellar binary black hole formation in galactic nuclei via the imprint of their center of mass acceleration on their gravitational wave signal}}, doi = {10.1103/physrevd.96.063014}, volume = {96}, year = {2017}, } @article{7725, abstract = {Phenotypic plasticity is the ability of an individual genotype to alter aspects of its phenotype depending on the current environment. It is central to the persistence, resistance and resilience of populations facing variation in physical or biological factors. Genetic variation in plasticity is pervasive, which suggests its local adaptation is plausible. Existing studies on the adaptation of plasticity typically focus on single traits and a few populations, while theory about interactions among genes (for example, pleiotropy) suggests that a multi-trait, landscape scale (for example, multiple populations) perspective is required. We present data from a landscape scale, replicated, multi-trait experiment using a classic predator–prey system centred on the water flea Daphnia pulex. We find predator regime-driven differences in genetic variation of multivariate plasticity. These differences are associated with strong divergent selection linked to a predation regime. Our findings are evidence for local adaptation of plasticity, suggesting that responses of populations to environmental variation depend on the conditions in which they evolved in the past.}, author = {Reger, Julia and Lind, Martin I. and Robinson, Matthew Richard and Beckerman, Andrew P.}, issn = {2397-334X}, journal = {Nature Ecology & Evolution}, pages = {100--107}, publisher = {Springer Nature}, title = {{Predation drives local adaptation of phenotypic plasticity}}, doi = {10.1038/s41559-017-0373-6}, volume = {2}, year = {2017}, } @article{7727, abstract = {Genes of the major histocompatibility complex (MHC) have been shown to influence social signalling and mate preferences in many species, including humans. First observations suggest that MHC signalling may also affect female fertility. To test this hypothesis, we exposed 191 female horses (Equus caballus) to either an MHC-similar or an MHC-dissimilar stimulus male around the time of ovulation and conception. A within-subject experimental design controlled for non-MHC-linked male characteristics, and instrumental insemination with semen of other males (n = 106) controlled for potential confounding effects of semen or embryo characteristics. We found that females were more likely to become pregnant if exposed to an MHC-dissimilar than to an MHC-similar male, while overall genetic distance to the stimulus males (based on microsatellite markers on 20 chromosomes) had no effect. Our results demonstrate that early pregnancy failures can be due to maternal life-history decisions (cryptic female choice) influenced by MHC-linked social signalling.}, author = {Burger, D. and Thomas, S. and Aepli, H. and Dreyer, M. and Fabre, G. and Marti, E. and Sieme, H. and Robinson, Matthew Richard and Wedekind, C.}, issn = {0962-8452}, journal = {Proceedings of the Royal Society B: Biological Sciences}, number = {1868}, publisher = {The Royal Society}, title = {{Major histocompatibility complex-linked social signalling affects female fertility}}, doi = {10.1098/rspb.2017.1824}, volume = {284}, year = {2017}, } @article{7728, abstract = {Meta-analyses of genome-wide association studies, which dominate genetic discovery, are based on data from diverse historical time periods and populations. Genetic scores derived from genome-wide association studies explain only a fraction of the heritability estimates obtained from whole-genome studies on single populations, known as the ‘hidden heritability’ puzzle. Using seven sampling populations (n = 35,062), we test whether hidden heritability is attributed to heterogeneity across sampling populations and time, showing that estimates are substantially smaller across populations compared with within populations. We show that the hidden heritability varies substantially: from zero for height to 20% for body mass index, 37% for education, 40% for age at first birth and up to 75% for number of children. Simulations demonstrate that our results are more likely to reflect heterogeneity in phenotypic measurement or gene–environment interactions than genetic heterogeneity. These findings have substantial implications for genetic discovery, suggesting that large homogenous datasets are required for behavioural phenotypes and that gene–environment interaction may be a central challenge for genetic discovery.}, author = {Tropf, Felix C. and Lee, S. Hong and Verweij, Renske M. and Stulp, Gert and van der Most, Peter J. and de Vlaming, Ronald and Bakshi, Andrew and Briley, Daniel A. and Rahal, Charles and Hellpap, Robert and Iliadou, Anastasia N. and Esko, Tõnu and Metspalu, Andres and Medland, Sarah E. and Martin, Nicholas G. and Barban, Nicola and Snieder, Harold and Robinson, Matthew Richard and Mills, Melinda C.}, issn = {2397-3374}, journal = {Nature Human Behaviour}, number = {10}, pages = {757--765}, publisher = {Springer Nature}, title = {{Hidden heritability due to heterogeneity across seven populations}}, doi = {10.1038/s41562-017-0195-1}, volume = {1}, year = {2017}, } @article{7729, abstract = {Quantifying the effects of inbreeding is critical to characterizing the genetic architecture of complex traits. This study highlights through theory and simulations the strengths and shortcomings of three SNP-based inbreeding measures commonly used to estimate inbreeding depression (ID). We demonstrate that heterogeneity in linkage disequilibrium (LD) between causal variants and SNPs biases ID estimates, and we develop an approach to correct this bias using LD and minor allele frequency stratified inference (LDMS). We quantified ID in 25 traits measured in ∼140,000 participants of the UK Biobank, using LDMS, and confirmed previously published ID for 4 traits. We find unique evidence of ID for handgrip strength, waist/hip ratio, and visual and auditory acuity (ID between −2.3 and −5.2 phenotypic SDs for complete inbreeding; P<0.001). Our results illustrate that a careful choice of the measure of inbreeding combined with LDMS stratification improves both detection and quantification of ID using SNP data.}, author = {Yengo, Loic and Zhu, Zhihong and Wray, Naomi R. and Weir, Bruce S. and Yang, Jian and Robinson, Matthew Richard and Visscher, Peter M.}, issn = {0027-8424}, journal = {Proceedings of the National Academy of Sciences}, number = {32}, pages = {8602--8607}, publisher = {Proceedings of the National Academy of Sciences}, title = {{Detection and quantification of inbreeding depression for complex traits from SNP data}}, doi = {10.1073/pnas.1621096114}, volume = {114}, year = {2017}, } @article{7731, abstract = {Genetic association studies in admixed populations are underrepresented in the genomics literature, with a key concern for researchers being the adequate control of spurious associations due to population structure. Linear mixed models (LMMs) are well suited for genome-wide association studies (GWAS) because they account for both population stratification and cryptic relatedness and achieve increased statistical power by jointly modeling all genotyped markers. Additionally, Bayesian LMMs allow for more flexible assumptions about the underlying distribution of genetic effects, and can concurrently estimate the proportion of phenotypic variance explained by genetic markers. Using three recently published Bayesian LMMs, Bayes R, BSLMM, and BOLT-LMM, we investigate an existing data set on eye (n = 625) and skin (n = 684) color from Cape Verde, an island nation off West Africa that is home to individuals with a broad range of phenotypic values for eye and skin color due to the mix of West African and European ancestry. We use simulations to demonstrate the utility of Bayesian LMMs for mapping loci and studying the genetic architecture of quantitative traits in admixed populations. The Bayesian LMMs provide evidence for two new pigmentation loci: one for eye color (AHRR) and one for skin color (DDB1).}, author = {Lloyd-Jones, Luke R. and Robinson, Matthew Richard and Moser, Gerhard and Zeng, Jian and Beleza, Sandra and Barsh, Gregory S. and Tang, Hua and Visscher, Peter M.}, issn = {0016-6731}, journal = {Genetics}, number = {2}, pages = {1113--1126}, publisher = {Genetics Society of America}, title = {{Inference on the genetic basis of eye and skin color in an admixed population via Bayesian linear mixed models}}, doi = {10.1534/genetics.116.193383}, volume = {206}, year = {2017}, } @article{7733, abstract = {Sections PDFPDF Tools Share Abstract Background: Gene discovery has provided remarkable biological insights into amyotrophic lateral sclerosis (ALS). One challenge for clinical application of genetic testing is critical evaluation of the significance of reported variants. Methods: We use whole exome sequencing (WES) to develop a clinically relevant approach to identify a subset of ALS patients harboring likely pathogenic mutations. In parallel, we assess if DNA methylation can be used to screen for pathogenicity of novel variants since a methylation signature has been shown to associate with the pathogenic C9orf72 expansion, but has not been explored for other ALS mutations. Australian patients identified with ALS‐relevant variants were cross‐checked with population databases and case reports to critically assess whether they were “likely causal,” “uncertain significance,” or “unlikely causal.” Results: Published ALS variants were identified in >10% of patients; however, in only 3% of patients (4/120) could these be confidently considered pathogenic (in SOD1 and TARDBP). We found no evidence for a differential DNA methylation signature in these mutation carriers. Conclusions: The use of WES in a typical ALS clinic demonstrates a critical approach to variant assessment with the capability to combine cohorts to enhance the largely unknown genetic basis of ALS.}, author = {Garton, Fleur C. and Benyamin, Beben and Zhao, Qiongyi and Liu, Zhijun and Gratten, Jacob and Henders, Anjali K. and Zhang, Zong-Hong and Edson, Janette and Furlong, Sarah and Morgan, Sarah and Heggie, Susan and Thorpe, Kathryn and Pfluger, Casey and Mather, Karen A. and Sachdev, Perminder S. and McRae, Allan F. and Robinson, Matthew Richard and Shah, Sonia and Visscher, Peter M. and Mangelsdorf, Marie and Henderson, Robert D. and Wray, Naomi R. and McCombe, Pamela A.}, issn = {2324-9269}, journal = {Molecular Genetics & Genomic Medicine}, number = {4}, pages = {418--428}, publisher = {Wiley}, title = {{Whole exome sequencing and DNA methylation analysis in a clinical amyotrophic lateral sclerosis cohort}}, doi = {10.1002/mgg3.302}, volume = {5}, year = {2017}, } @article{7755, abstract = {We give a bird's-eye view of the plastic deformation of crystals aimed at the statistical physics community, as well as a broad introduction to the statistical theories of forced rigid systems aimed at the plasticity community. Memory effects in magnets, spin glasses, charge density waves, and dilute colloidal suspensions are discussed in relation to the onset of plastic yielding in crystals. Dislocation avalanches and complex dislocation tangles are discussed via a brief introduction to the renormalization group and scaling. Analogies to emergent scale invariance in fracture, jamming, coarsening, and a variety of depinning transitions are explored. Dislocation dynamics in crystals challenge nonequilibrium statistical physics. Statistical physics provides both cautionary tales of subtle memory effects in nonequilibrium systems and systematic tools designed to address complex scale-invariant behavior on multiple length scales and timescales.}, author = {Sethna, James P. and Bierbaum, Matthew K. and Dahmen, Karin A. and Goodrich, Carl Peter and Greer, Julia R. and Hayden, Lorien X. and Kent-Dobias, Jaron P. and Lee, Edward D. and Liarte, Danilo B. and Ni, Xiaoyue and Quinn, Katherine N. and Raju, Archishman and Rocklin, D. Zeb and Shekhawat, Ashivni and Zapperi, Stefano}, issn = {1531-7331}, journal = {Annual Review of Materials Research}, pages = {217--246}, publisher = {Annual Reviews}, title = {{Deformation of crystals: Connections with statistical physics}}, doi = {10.1146/annurev-matsci-070115-032036}, volume = {47}, year = {2017}, } @article{7756, abstract = {We study the shear jamming of athermal frictionless soft spheres, and find that in the thermodynamic limit, a shear-jammed state exists with different elastic properties from the isotropically-jammed state. For example, shear-jammed states can have a non-zero residual shear stress in the thermodynamic limit that arises from long-range stress-stress correlations. As a result, the ratio of the shear and bulk moduli, which in isotropically-jammed systems vanishes as the jamming transition is approached from above, instead approaches a constant. Despite these striking differences, we argue that in a deeper sense, the shear jamming and isotropic jamming transitions actually have the same symmetry, and that the differences can be fully understood by rotating the six-dimensional basis of the elastic modulus tensor.}, author = {Baity-Jesi, Marco and Goodrich, Carl Peter and Liu, Andrea J. and Nagel, Sidney R. and Sethna, James P.}, issn = {0022-4715}, journal = {Journal of Statistical Physics}, number = {3-4}, pages = {735--748}, publisher = {Springer Nature}, title = {{Emergent SO(3) symmetry of the frictionless shear jamming transition}}, doi = {10.1007/s10955-016-1703-9}, volume = {167}, year = {2017}, } @article{7757, abstract = {Recent advances in designing metamaterials have demonstrated that global mechanical properties of disordered spring networks can be tuned by selectively modifying only a small subset of bonds. Here, using a computationally efficient approach, we extend this idea to tune more general properties of networks. With nearly complete success, we are able to produce a strain between any two target nodes in a network in response to an applied source strain on any other pair of nodes by removing only ∼1% of the bonds. We are also able to control multiple pairs of target nodes, each with a different individual response, from a single source, and to tune multiple independent source/target responses simultaneously into a network. We have fabricated physical networks in macroscopic 2D and 3D systems that exhibit these responses. This work is inspired by the long-range coupled conformational changes that constitute allosteric function in proteins. The fact that allostery is a common means for regulation in biological molecules suggests that it is a relatively easy property to develop through evolution. In analogy, our results show that long-range coupled mechanical responses are similarly easy to achieve in disordered networks.}, author = {Rocks, Jason W. and Pashine, Nidhi and Bischofberger, Irmgard and Goodrich, Carl Peter and Liu, Andrea J. and Nagel, Sidney R.}, issn = {0027-8424}, journal = {Proceedings of the National Academy of Sciences}, number = {10}, pages = {2520--2525}, publisher = {Proceedings of the National Academy of Sciences}, title = {{Designing allostery-inspired response in mechanical networks}}, doi = {10.1073/pnas.1612139114}, volume = {114}, year = {2017}, } @article{7758, abstract = {Controlling motion at the microscopic scale is a fundamental goal in the development of biologically inspired systems. We show that the motion of active, self-propelled colloids can be sufficiently controlled for use as a tool to assemble complex structures such as braids and weaves out of microscopic filaments. Unlike typical self-assembly paradigms, these structures are held together by geometric constraints rather than adhesive bonds. The out-of-equilibrium assembly that we propose involves precisely controlling the 2D motion of active colloids so that their path has a nontrivial topology. We demonstrate with proof-of-principle Brownian dynamics simulations that, when the colloids are attached to long semiflexible filaments, this motion causes the filaments to braid. The ability of the active particles to provide sufficient force necessary to bend the filaments into a braid depends on a number of factors, including the self-propulsion mechanism, the properties of the filament, and the maximum curvature in the braid. Our work demonstrates that nonequilibrium assembly pathways can be designed using active particles.}, author = {Goodrich, Carl Peter and Brenner, Michael P.}, issn = {0027-8424}, journal = {Proceedings of the National Academy of Sciences}, number = {2}, pages = {257--262}, publisher = {Proceedings of the National Academy of Sciences}, title = {{Using active colloids as machines to weave and braid on the micrometer scale}}, doi = {10.1073/pnas.1608838114}, volume = {114}, year = {2017}, } @inproceedings{787, abstract = {Population protocols are a popular model of distributed computing, in which randomly-interacting agents with little computational power cooperate to jointly perform computational tasks. Inspired by developments in molecular computation, and in particular DNA computing, recent algorithmic work has focused on the complexity of solving simple yet fundamental tasks in the population model, such as leader election (which requires convergence to a single agent in a special "leader" state), and majority (in which agents must converge to a decision as to which of two possible initial states had higher initial count). Known results point towards an inherent trade-off between the time complexity of such algorithms, and the space complexity, i.e. size of the memory available to each agent. In this paper, we explore this trade-off and provide new upper and lower bounds for majority and leader election. First, we prove a unified lower bound, which relates the space available per node with the time complexity achievable by a protocol: for instance, our result implies that any protocol solving either of these tasks for n agents using O(log log n) states must take (n=polylogn) expected time. This is the first result to characterize time complexity for protocols which employ super-constant number of states per node, and proves that fast, poly-logarithmic running times require protocols to have relatively large space costs. On the positive side, we give algorithms showing that fast, poly-logarithmic convergence time can be achieved using O(log2 n) space per node, in the case of both tasks. Overall, our results highlight a time complexity separation between O(log log n) and (log2 n) state space size for both majority and leader election in population protocols, and introduce new techniques, which should be applicable more broadly.}, author = {Alistarh, Dan-Adrian and Aspnes, James and Eisenstat, David and Rivest, Ronald and Gelashvili, Rati}, booktitle = {Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms}, location = {Barcelona, Spain}, pages = {2560 -- 2579}, publisher = {SIAM}, title = {{Time-space trade-offs in population protocols}}, doi = {10.1137/1.9781611974782.169}, year = {2017}, } @inproceedings{788, abstract = {In contrast to electronic computation, chemical computation is noisy and susceptible to a variety of sources of error, which has prevented the construction of robust complex systems. To be effective, chemical algorithms must be designed with an appropriate error model in mind. Here we consider the model of chemical reaction networks that preserve molecular count (population protocols), and ask whether computation can be made robust to a natural model of unintended “leak” reactions. Our definition of leak is motivated by both the particular spurious behavior seen when implementing chemical reaction networks with DNA strand displacement cascades, as well as the unavoidable side reactions in any implementation due to the basic laws of chemistry. We develop a new “Robust Detection” algorithm for the problem of fast (logarithmic time) single molecule detection, and prove that it is robust to this general model of leaks. Besides potential applications in single molecule detection, the error-correction ideas developed here might enable a new class of robust-by-design chemical algorithms. Our analysis is based on a non-standard hybrid argument, combining ideas from discrete analysis of population protocols with classic Markov chain techniques.}, author = {Alistarh, Dan-Adrian and Dudek, Bartłomiej and Kosowski, Adrian and Soloveichik, David and Uznański, Przemysław}, pages = {155 -- 171}, publisher = {Springer}, title = {{Robust detection in leak-prone population protocols}}, doi = {10.1007/978-3-319-66799-7_11}, volume = {10467 LNCS}, year = {2017}, } @inproceedings{789, abstract = {The problem of efficient concurrent memory reclamation in unmanaged languages such as C or C++ is one of the major challenges facing the parallelization of billions of lines of legacy code. Garbage collectors for C/C++ can be inefficient; thus, programmers are often forced to use finely-crafted concurrent memory reclamation techniques. These techniques can provide good performance, but require considerable programming effort to deploy, and have strict requirements, allowing the programmer very little room for error. In this work, we present Forkscan, a new conservative concurrent memory reclamation scheme which is fully automatic and surprisingly scalable. Forkscan's semantics place it between automatic garbage collectors (it requires the programmer to explicitly retire nodes before they can be reclaimed), and concurrent memory reclamation techniques (as it does not assume that nodes are completely unlinked from the data structure for correctness). Forkscan's implementation exploits these new semantics for efficiency: we leverage parallelism and optimized implementations of signaling and copy-on-write in modern operating systems to efficiently obtain and process consistent snapshots of memory that can be scanned concurrently with the normal program operation. Empirical evaluation on a range of classical concurrent data structure microbenchmarks shows that Forkscan can preserve the scalability of the original code, while maintaining an order of magnitude lower latency than automatic garbage collection, and demonstrating competitive performance with finely crafted memory reclamation techniques.}, author = {Alistarh, Dan-Adrian and Leiserson, William and Matveev, Alexander and Shavit, Nir}, pages = {483 -- 498}, publisher = {ACM}, title = {{Forkscan: Conservative memory reclamation for modern operating systems}}, doi = {10.1145/3064176.3064214}, year = {2017}, } @inproceedings{790, abstract = {Stochastic gradient descent (SGD) is a commonly used algorithm for training linear machine learning models. Based on vector algebra, it benefits from the inherent parallelism available in an FPGA. In this paper, we first present a single-precision floating-point SGD implementation on an FPGA that provides similar performance as a 10-core CPU. We then adapt the design to make it capable of processing low-precision data. The low-precision data is obtained from a novel compression scheme - called stochastic quantization, specifically designed for machine learning applications. We test both full-precision and low-precision designs on various regression and classification data sets. We achieve up to an order of magnitude training speedup when using low-precision data compared to a full-precision SGD on the same FPGA and a state-of-the-art multi-core solution, while maintaining the quality of training. We open source the designs presented in this paper.}, author = {Kara, Kaan and Alistarh, Dan-Adrian and Alonso, Gustavo and Mutlu, Onur and Zhang, Ce}, pages = {160 -- 167}, publisher = {IEEE}, title = {{FPGA-accelerated dense linear machine learning: A precision-convergence trade-off}}, doi = {10.1109/FCCM.2017.39}, year = {2017}, }