@misc{6440, abstract = {In order to guarantee that each method of a data structure updates the logical state exactly once, al-most all non-blocking implementations employ Compare-And-Swap (CAS) based synchronization. For FIFO queue implementations this translates into concurrent enqueue or dequeue methods competing among themselves to update the same variable, the tail or the head, respectively, leading to high contention and poor scalability. Recent non-blocking queue implementations try to alleviate high contentionby increasing the number of contention points, all the while using CAS-based synchronization. Furthermore, obtaining a wait-free implementation with competition is achieved by additional synchronization which leads to further degradation of performance.In this paper we formalize the notion of competitiveness of a synchronizing statement which can beused as a measure for the scalability of concurrent implementations. We present a new queue implementation, the Speculative Pairing (SP) queue, which, as we show, decreases competitiveness by using Fetch-And-Increment (FAI) instead of CAS. We prove that the SP queue is linearizable and lock-free.We also show that replacing CAS with FAI leads to wait-freedom for dequeue methods without an adverse effect on performance. In fact, our experiments suggest that the SP queue can perform and scale better than the state-of-the-art queue implementations.}, author = {Henzinger, Thomas A and Payer, Hannes and Sezgin, Ali}, issn = {2664-1690}, pages = {23}, publisher = {IST Austria}, title = {{Replacing competition with cooperation to achieve scalable lock-free FIFO queues }}, doi = {10.15479/AT:IST-2013-124-v1-1}, year = {2013}, } @article{6768, abstract = {The paper presents an algorithm that applies a stack filter simulating the Mean Curvature Motion equation via a finite difference scheme.}, author = {Mondelli, Marco}, issn = {2105-1232}, journal = {Image Processing On Line}, pages = {68--111}, publisher = {Image Processing On Line}, title = {{A finite difference scheme for the stack filter simulating the MCM}}, doi = {10.5201/ipol.2013.53}, volume = {3}, year = {2013}, } @article{10384, abstract = {Recent studies aimed at investigating artificial analogs of bacterial colonies have shown that low-density suspensions of self-propelled particles confined in two dimensions can assemble into finite aggregates that merge and split, but have a typical size that remains constant (living clusters). In this Letter, we address the problem of the formation of living clusters and crystals of active particles in three dimensions. We study two systems: self-propelled particles interacting via a generic attractive potential and colloids that can move toward each other as a result of active agents (e.g., by molecular motors). In both cases, fluidlike “living” clusters form. We explain this general feature in terms of the balance between active forces and regression to thermodynamic equilibrium. This balance can be quantified in terms of a dimensionless number that allows us to collapse the observed clustering behavior onto a universal curve. We also discuss how active motion affects the kinetics of crystal formation.}, author = {Mognetti, B. M. and Šarić, Anđela and Angioletti-Uberti, S. and Cacciuto, A. and Valeriani, C. and Frenkel, D.}, issn = {1079-7114}, journal = {Physical Review Letters}, keywords = {general physics and astronomy}, number = {24}, publisher = {American Physical Society}, title = {{Living clusters and crystals from low-density suspensions of active colloids}}, doi = {10.1103/physrevlett.111.245702}, volume = {111}, year = {2013}, } @article{10396, abstract = {Stimfit is a free cross-platform software package for viewing and analyzing electrophysiological data. It supports most standard file types for cellular neurophysiology and other biomedical formats. Its analysis algorithms have been used and validated in several experimental laboratories. Its embedded Python scripting interface makes Stimfit highly extensible and customizable.}, author = {Schlögl, Alois and Jonas, Peter M and Schmidt-Hieber, C. and Guzman, S. J.}, issn = {1862-278X}, journal = {Biomedical Engineering / Biomedizinische Technik}, keywords = {biomedical engineering, data analysis, free software}, location = {Graz, Austria}, number = {SI-1-Track-G}, publisher = {De Gruyter}, title = {{Stimfit: A fast visualization and analysis environment for cellular neurophysiology}}, doi = {10.1515/bmt-2013-4181}, volume = {58}, year = {2013}, } @inproceedings{10749, abstract = {Fluxoid quantization provides a direct means to study phase coherence. In cuprate superconductors, there have been observations which suggest that phase coherent superconducting fluctuations may persist at temperatures significantly above Tc. The focus of this work is to study the vortex states in mesoscopic cuprate superconducting samples to directly probe phase coherence over a wide range of temperatures. We present cantilever torque susceptometry measurements of micron and sub-micron size Bi2212 rings and disks. The high sensitivity of this technique allowed observation of transitions between different fluxoid states of a single ring, and the discrete vortex states of micron size disks. The dependence of magnetic susceptibility on diameter and wall thickness of the ring was investigated. Measurements were made at different values of the in-plane magnetic field, and over a wide range of temperatures.}, author = {Polshyn, Hryhoriy and Budakian, Raffi and Gu, Genda}, booktitle = {APS March Meeting 2013}, issn = {0003-0503}, location = {Baltimore, MD, United States}, number = {1}, publisher = {American Physical Society}, title = {{Cantilever micro-susceptometry of mesoscopic Bi2212 samples}}, volume = {58}, year = {2013}, } @article{9459, abstract = {Nucleosome remodelers of the DDM1/Lsh family are required for DNA methylation of transposable elements, but the reason for this is unknown. How DDM1 interacts with other methylation pathways, such as small-RNA-directed DNA methylation (RdDM), which is thought to mediate plant asymmetric methylation through DRM enzymes, is also unclear. Here, we show that most asymmetric methylation is facilitated by DDM1 and mediated by the methyltransferase CMT2 separately from RdDM. We find that heterochromatic sequences preferentially require DDM1 for DNA methylation and that this preference depends on linker histone H1. RdDM is instead inhibited by heterochromatin and absolutely requires the nucleosome remodeler DRD1. Together, DDM1 and RdDM mediate nearly all transposon methylation and collaborate to repress transposition and regulate the methylation and expression of genes. Our results indicate that DDM1 provides DNA methyltransferases access to H1-containing heterochromatin to allow stable silencing of transposable elements in cooperation with the RdDM pathway.}, author = {Zemach, Assaf and Kim, M. Yvonne and Hsieh, Ping-Hung and Coleman-Derr, Devin and Eshed-Williams, Leor and Thao, Ka and Harmer, Stacey L. and Zilberman, Daniel}, issn = {1097-4172}, journal = {Cell}, number = {1}, pages = {193--205}, publisher = {Elsevier}, title = {{The Arabidopsis nucleosome remodeler DDM1 allows DNA methyltransferases to access H1-containing heterochromatin}}, doi = {10.1016/j.cell.2013.02.033}, volume = {153}, year = {2013}, } @article{9481, abstract = {Arabidopsis thaliana endosperm, a transient tissue that nourishes the embryo, exhibits extensive localized DNA demethylation on maternally inherited chromosomes. Demethylation mediates parent-of-origin–specific (imprinted) gene expression but is apparently unnecessary for the extensive accumulation of maternally biased small RNA (sRNA) molecules detected in seeds. Endosperm DNA in the distantly related monocots rice and maize is likewise locally hypomethylated, but whether this hypomethylation is generally parent-of-origin specific is unknown. Imprinted expression of sRNA also remains uninvestigated in monocot seeds. Here, we report high-coverage sequencing of the Kitaake rice cultivar that enabled us to show that localized hypomethylation in rice endosperm occurs solely on the maternal genome, preferring regions of high DNA accessibility. Maternally expressed imprinted genes are enriched for hypomethylation at putative promoter regions and transcriptional termini and paternally expressed genes at promoters and gene bodies, mirroring our recent results in A. thaliana. However, unlike in A. thaliana, rice endosperm sRNA populations are dominated by specific strong sRNA-producing loci, and imprinted 24-nt sRNAs are expressed from both parental genomes and correlate with hypomethylation. Overlaps between imprinted sRNA loci and imprinted genes expressed from opposite alleles suggest that sRNAs may regulate genomic imprinting. Whereas sRNAs in seedling tissues primarily originate from small class II (cut-and-paste) transposable elements, those in endosperm are more uniformly derived, including sequences from other transposon classes, as well as genic and intergenic regions. Our data indicate that the endosperm exhibits a unique pattern of sRNA expression and suggest that localized hypomethylation of maternal endosperm DNA is conserved in flowering plants.}, author = {Rodrigues, Jessica A. and Ruan, Randy and Nishimura, Toshiro and Sharma, Manoj K. and Sharma, Rita and Ronald, Pamela C and Fischer, Robert L. and Zilberman, Daniel}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, keywords = {Multidisciplinary}, number = {19}, pages = {7934--7939}, publisher = {National Academy of Sciences}, title = {{Imprinted expression of genes and small RNA is associated with localized hypomethylation of the maternal genome in rice endosperm}}, doi = {10.1073/pnas.1306164110}, volume = {110}, year = {2013}, } @article{9520, abstract = {Plants undergo alternation of generation in which reproductive cells develop in the plant body ("sporophytic generation") and then differentiate into a multicellular gamete-forming "gametophytic generation." Different populations of helper cells assist in this transgenerational journey, with somatic tissues supporting early development and single nurse cells supporting gametogenesis. New data reveal a two-way relationship between early reproductive cells and their helpers involving complex epigenetic and signaling networks determining cell number and fate. Later, the egg cell plays a central role in specifying accessory cells, whereas in both gametophytes, companion cells contribute non-cell-autonomously to the epigenetic landscape of the gamete genomes.}, author = {Feng, Xiaoqi and Zilberman, Daniel and Dickinson, Hugh}, issn = {1878-1551}, journal = {Developmental Cell}, number = {3}, pages = {215--225}, publisher = {Elsevier}, title = {{A conversation across generations: Soma-germ cell crosstalk in plants}}, doi = {10.1016/j.devcel.2013.01.014}, volume = {24}, year = {2013}, } @article{9663, abstract = {Molecular dynamics simulations of small Cu nanoparticles using three different interatomic potentials at rising temperature indicate that small nanoparticles can undergo solid-solid structural transitions through a direct geometrical conversion route. The direct geometrical conversion can happen for cuboctahedral nanoparticles, which turn into an icosahedra shape: one diagonal of the square faces contracts, and the faces are folded along the diagonal to give rise to two equilateral triangles. The transition is a kinetic process that cannot be fully explained through an energetic point of view. It has low activation energy and fast reaction time in the simulations. The transition mechanism is via the transmission of shear waves initiated from the particle surface and does not involve dislocation activity.}, author = {Cheng, Bingqing and Ngan, Alfonso H. W.}, issn = {1089-7690}, journal = {The Journal of Chemical Physics}, number = {16}, publisher = {AIP Publishing}, title = {{Thermally induced solid-solid structural transition of copper nanoparticles through direct geometrical conversion}}, doi = {10.1063/1.4802025}, volume = {138}, year = {2013}, } @article{970, abstract = {Recently a new high-mobility Dirac material, trilayer graphene, was realized experimentally. The band structure of ABA-stacked trilayer graphene consists of a monolayer-like and a bilayer-like pair of bands. Here we study electronic properties of ABA-stacked trilayer graphene biased by a perpendicular electric field. We find that the combination of the bias and trigonal warping gives rise to a set of new Dirac points: In each valley, seven species of Dirac fermions with small masses of order of a few meV emerge. The positions and masses of the emergent Dirac fermions are tunable by bias, and one group of Dirac fermions becomes massless at a certain bias value. Therefore, in contrast to bilayer graphene, the conductivity at the neutrality point is expected to show nonmonotonic behavior, becoming of the order of a few e2/h when some Dirac masses vanish. Further, we analyze the evolution of the Landau level spectrum as a function of bias. The emergence of new Dirac points in the band structure translates into new threefold-degenerate groups of Landau levels. This leads to an anomalous quantum Hall effect, in which some quantum Hall steps have a height of 3e2/h. At an intermediate bias, the degeneracies of all Landau levels get lifted, and in this regime all quantum Hall plateaus are spaced by e2/h. Finally, we show that the pattern of Landau level crossings is very sensitive to certain band structure parameters, and can therefore provide a useful tool for determining their precise values.}, author = {Maksym Serbyn and Abanin, Dmitry A}, journal = {Physical Review B - Condensed Matter and Materials Physics}, number = {11}, publisher = {American Physical Society}, title = {{New Dirac points and multiple Landau level crossings in biased trilayer graphene}}, doi = {10.1103/PhysRevB.87.115422}, volume = {87}, year = {2013}, } @article{971, abstract = {We study the stability of the normal state in a mesoscopic NSN junction biased by a constant voltage V with respect to the formation of the superconducting order. Using the linearized time-dependent Ginzburg-Landau equation, we obtain the temperature dependence of the instability line, V inst(T), where nucleation of superconductivity takes place. For sufficiently low biases, a stationary symmetric superconducting state emerges below the instability line. For higher biases, the normal phase is destroyed by the formation of a nonstationary bimodal state with two superconducting nuclei localized near the opposite terminals. The low-temperature and large-voltage behavior of the instability line is highly sensitive to the details of the inelastic relaxation mechanism in the wire. Therefore, experimental studies of Vinst(T) in NSN junctions may be used as an effective tool to access the parameters of the inelastic relaxation in the normal state.}, author = {Maksym Serbyn and Skvortsov, Mikhail A}, journal = {Physical Review B - Condensed Matter and Materials Physics}, number = {2}, publisher = {American Physical Society}, title = {{Onset of superconductivity in a voltage-biased normal-superconducting-normal microbridge}}, doi = {10.1103/PhysRevB.87.020501}, volume = {87}, year = {2013}, } @article{972, abstract = {In topological crystalline insulators (TCIs), topology and crystal symmetry intertwine to create surface states with distinct characteristics. The breaking of crystal symmetry in TCIs is predicted to impart mass to the massless Dirac fermions. Here, we report high-resolution scanning tunneling microscopy studies of a TCI, Pb1-xSnxSe that reveal the coexistence of zero-mass Dirac fermions protected by crystal symmetry with massive Dirac fermions consistent with crystal symmetry breaking. In addition, we show two distinct regimes of the Fermi surface topology separated by a Van-Hove singularity at the Lifshitz transition point. Our work paves the way for engineering the Dirac band gap and realizing interaction-driven topological quantum phenomena in TCIs.}, author = {Okada, Yoshinori and Serbyn, Maksym and Lin, Hsin and Walkup, Daniel and Zhou, Wenwen and Dhital, Chetan and Neupane, Madhab and Xu, Suyang and Wang, Yungjui and Sankar, Raman and Chou, Fangcheng and Bansil, Arun and Hasan, Md and Wilson, Stephen and Fu, Liang and Madhavan, Vidya}, journal = {Science}, number = {6153}, pages = {1496 -- 1499}, publisher = {American Association for the Advancement of Science}, title = {{Observation of dirac node formation and mass acquisition in a topological crystalline insulator}}, doi = {10.1126/science.1239451}, volume = {341}, year = {2013}, } @article{973, abstract = {We construct a complete set of local integrals of motion that characterize the many-body localized (MBL) phase. Our approach relies on the assumption that local perturbations act locally on the eigenstates in the MBL phase, which is supported by numerical simulations of the random-field XXZ spin chain. We describe the structure of the eigenstates in the MBL phase and discuss the implications of local conservation laws for its nonequilibrium quantum dynamics. We argue that the many-body localization can be used to protect coherence in the system by suppressing relaxation between eigenstates with different local integrals of motion.}, author = {Maksym Serbyn and Papić, Zlatko and Abanin, Dmitry A}, journal = {Physical Review Letters}, number = {12}, publisher = {American Physical Society}, title = {{Local conservation laws and the structure of the many body localized states}}, doi = {10.1103/PhysRevLett.111.127201}, volume = {111}, year = {2013}, } @article{974, abstract = {We propose a possible realization of the overscreened Kondo impurity problem by a magnetic s=1/2 impurity embedded in a two-dimensional S=1 U(1) spin liquid with a Fermi surface. This problem contains an interesting interplay between non-Fermi-liquid behavior induced by a U(1) gauge field coupled to fermions and a non-Fermi-liquid fixed point in the overscreened Kondo problem. Using a large-N expansion together with an expansion in the dynamical exponent of the gauge field, we find that the coupling to the gauge field leads to weak but observable changes in the physical properties of the system at the overscreened Kondo fixed point. We discuss the extrapolation of this result to a physical case and argue that the realization of overscreened Kondo physics could lead to observations of effects due to gauge fields.}, author = {Serbyn, Maksym and Senthil, Todadri and Lee, Patrick}, journal = {Physical Review B - Condensed Matter and Materials Physics}, number = {2}, publisher = {American Physical Society}, title = {{Overscreened Kondo fixed point in S=1 spin liquid}}, doi = {10.1103/PhysRevB.88.024419}, volume = {88}, year = {2013}, } @article{975, abstract = {Recent numerical work by Bardarson, Pollmann, and Moore revealed a slow, logarithmic in time, growth of the entanglement entropy for initial product states in a putative many-body localized phase. We show that this surprising phenomenon results from the dephasing due to exponentially small interaction-induced corrections to the eigenenergies of different states. For weak interactions, we find that the entanglement entropy grows as ξln (Vt/), where V is the interaction strength, and ξ is the single-particle localization length. The saturated value of the entanglement entropy at long times is determined by the participation ratios of the initial state over the eigenstates of the subsystem. Our work shows that the logarithmic entanglement growth is a universal phenomenon characteristic of the many-body localized phase in any number of spatial dimensions, and reveals a broad hierarchy of dephasing time scales present in such a phase.}, author = {Maksym Serbyn and Papić, Zlatko and Abanin, Dmitry A}, journal = {Physical Review Letters}, number = {26}, publisher = {American Physical Society}, title = {{Universal slow growth of entanglement in interacting strongly disordered systems}}, doi = {10.1103/PhysRevLett.110.260601}, volume = {110}, year = {2013}, } @misc{9751, abstract = {High relatedness among interacting individuals has generally been considered a precondition for the evolution of altruism. However, kin-selection theory also predicts the evolution of altruism when relatedness is low, as long as the cost of the altruistic act is minor compared to its benefit. Here, we demonstrate evidence for a low-cost altruistic act in bacteria. We investigated Escherichia coli responding to the attack of an obligately lytic phage by committing suicide in order to prevent parasite transmission to nearby relatives. We found that bacterial suicide provides large benefits to survivors at marginal costs to committers. The cost of suicide was low because infected cells are moribund, rapidly dying upon phage infection, such that no more opportunity for reproduction remains. As a consequence of its marginal cost, host suicide was selectively favoured even when relatedness between committers and survivors approached zero. Altogether, our findings demonstrate that low-cost suicide can evolve with ease, represents an effective host-defence strategy, and seems to be widespread among microbes. Moreover, low-cost suicide might also occur in higher organisms as exemplified by infected social insect workers leaving the colony to die in isolation.}, author = {Refardt, Dominik and Bergmiller, Tobias and Kümmerli, Rolf}, publisher = {Dryad}, title = {{Data from: Altruism can evolve when relatedness is low: evidence from bacteria committing suicide upon phage infection}}, doi = {10.5061/dryad.b1q2n}, year = {2013}, } @misc{9754, abstract = {Short-read sequencing technologies have in principle made it feasible to draw detailed inferences about the recent history of any organism. In practice, however, this remains challenging due to the difficulty of genome assembly in most organisms and the lack of statistical methods powerful enough to discriminate among recent, non-equilibrium histories. We address both the assembly and inference challenges. We develop a bioinformatic pipeline for generating outgroup-rooted alignments of orthologous sequence blocks from de novo low-coverage short-read data for a small number of genomes, and show how such sequence blocks can be used to fit explicit models of population divergence and admixture in a likelihood framework. To illustrate our approach, we reconstruct the Pleistocene history of an oak-feeding insect (the oak gallwasp Biorhiza pallida) which, in common with many other taxa, was restricted during Pleistocene ice ages to a longitudinal series of southern refugia spanning theWestern Palaearctic. Our analysis of sequence blocks sampled from a single genome from each of three major glacial refugia reveals support for an unexpected history dominated by recent admixture. Despite the fact that 80% of the genome is affected by admixture during the last glacial cycle, we are able to infer the deeper divergence history of these populations. These inferences are robust to variation in block length, mutation model, and the sampling location of individual genomes within refugia. This combination of de novo assembly and numerical likelihood calculation provides a powerful framework for estimating recent population history that can be applied to any organism without the need for prior genetic resources.}, author = {Hearn, Jack and Stone, Graham and Barton, Nicholas H and Lohse, Konrad and Bunnefeld, Lynsey}, publisher = {Dryad}, title = {{Data from: Likelihood-based inference of population history from low coverage de novo genome assemblies}}, doi = {10.5061/dryad.r3r60}, year = {2013}, } @article{976, abstract = {Motivated by a search for experimental probes to access the physics of fractionalized excitations called spinons in spin liquids, we study the interaction of spinons with lattice vibrations. We consider the case of algebraic spin liquid, when spinons have fermionic statistics and a Dirac-like dispersion. We establish the general procedure for deriving spinon-phonon interactions, which is based on symmetry considerations. The procedure is illustrated for four different algebraic spin liquids: π-flux and staggered-flux phases on a square lattice, π-flux phase on a kagome lattice, and zero-flux phase on a honeycomb lattice. Although the low-energy description is similar for all these phases, different underlying symmetry groups lead to a distinct form of spinon-phonon interaction Hamiltonian. The explicit form of the spinon-phonon interaction is used to estimate the attenuation of ultrasound in an algebraic spin liquid. The prospects of the sound attenuation as a probe of spinons are discussed.}, author = {Maksym Serbyn and Lee, Patrick}, journal = {Physical Review B - Condensed Matter and Materials Physics}, number = {17}, publisher = {American Physical Society}, title = {{Spinon-phonon interaction in algebraic spin liquids}}, doi = {10.1103/PhysRevB.87.174424}, volume = {87}, year = {2013}, } @article{2443, abstract = {The mode of action of auxin is based on its non-uniform distribution within tissues and organs. Despite the wide use of several auxin analogues in research and agriculture, little is known about the specificity of different auxin-related transport and signalling processes towards these compounds. Using seedlings of Arabidopsis thaliana and suspension-cultured cells of Nicotiana tabacum (BY-2), the physiological activity of several auxin analogues was investigated, together with their capacity to induce auxin-dependent gene expression, to inhibit endocytosis and to be transported across the plasma membrane. This study shows that the specificity criteria for different auxin-related processes vary widely. Notably, the special behaviour of some synthetic auxin analogues suggests that they might be useful tools in investigations of the molecular mechanism of auxin action. Thus, due to their differential stimulatory effects on DR5 expression, indole-3-propionic (IPA) and 2,4,5-trichlorophenoxy acetic (2,4,5-T) acids can serve in studies of TRANSPORT INHIBITOR RESPONSE 1/AUXIN SIGNALLING F-BOX (TIR1/AFB)-mediated auxin signalling, and 5-fluoroindole-3-acetic acid (5-F-IAA) can help to discriminate between transcriptional and non-transcriptional pathways of auxin signalling. The results demonstrate that the major determinants for the auxin-like physiological potential of a particular compound are very complex and involve its chemical and metabolic stability, its ability to distribute in tissues in a polar manner and its activity towards auxin signalling machinery.}, author = {Simon, Sibu and Kubeš, Martin and Baster, Pawel and Robert, Stéphanie and Dobrev, Petre and Friml, Jirí and Petrášek, Jan and Zažímalová, Eva}, journal = {New Phytologist}, number = {4}, pages = {1034 -- 1048}, publisher = {Wiley}, title = {{Defining the selectivity of processes along the auxin response chain: A study using auxin analogues}}, doi = {10.1111/nph.12437}, volume = {200}, year = {2013}, } @inproceedings{2444, abstract = {We consider two core algorithmic problems for probabilistic verification: the maximal end-component decomposition and the almost-sure reachability set computation for Markov decision processes (MDPs). For MDPs with treewidth k, we present two improved static algorithms for both the problems that run in time O(n·k 2.38·2k ) and O(m·logn· k), respectively, where n is the number of states and m is the number of edges, significantly improving the previous known O(n·k·√n· k) bound for low treewidth. We also present decremental algorithms for both problems for MDPs with constant treewidth that run in amortized logarithmic time, which is a huge improvement over the previously known algorithms that require amortized linear time.}, author = {Chatterjee, Krishnendu and Ła̧Cki, Jakub}, location = {St. Petersburg, Russia}, pages = {543 -- 558}, publisher = {Springer}, title = {{Faster algorithms for Markov decision processes with low treewidth}}, doi = {10.1007/978-3-642-39799-8_36}, volume = {8044}, year = {2013}, }