TY - CONF AB - We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding ' : G ! M of a graph G into a 2manifold M maps the vertices in V (G) to distinct points and the edges in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to a common node or arc, due to data compression or low resolution. This raises the computational problem of deciding whether a given map ' : G ! M comes from an embedding. A map ' : G ! M is a weak embedding if it can be perturbed into an embedding ψ: G ! M with k' "k < " for every " > 0. A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kyncl [14], which reduces to solving a system of linear equations over Z2. It runs in O(n2!) O(n4:75) time, where 2:373 is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O(n log n). Our algorithm is also conceptually simpler than [14]: We perform a sequence of local operations that gradually "untangles" the image '(G) into an embedding (G), or reports that ' is not a weak embedding. It generalizes a recent technique developed for the case that G is a cycle and the embedding is a simple polygon [1], and combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations. AU - Akitaya, Hugo AU - Fulek, Radoslav AU - Tóth, Csaba ID - 309 TI - Recognizing weak embeddings of graphs ER - TY - JOUR AB - We present an approach to interacting quantum many-body systems based on the notion of quantum groups, also known as q-deformed Lie algebras. In particular, we show that, if the symmetry of a free quantum particle corresponds to a Lie group G, in the presence of a many-body environment this particle can be described by a deformed group, Gq. Crucially, the single deformation parameter, q, contains all the information about the many-particle interactions in the system. We exemplify our approach by considering a quantum rotor interacting with a bath of bosons, and demonstrate that extracting the value of q from closed-form solutions in the perturbative regime allows one to predict the behavior of the system for arbitrary values of the impurity-bath coupling strength, in good agreement with nonperturbative calculations. Furthermore, the value of the deformation parameter allows one to predict at which coupling strengths rotor-bath interactions result in a formation of a stable quasiparticle. The approach based on quantum groups does not only allow for a drastic simplification of impurity problems, but also provides valuable insights into hidden symmetries of interacting many-particle systems. AU - Yakaboylu, Enderalp AU - Shkolnikov, Mikhail AU - Lemeshko, Mikhail ID - 5794 IS - 25 JF - Physical Review Letters SN - 00319007 TI - Quantum groups as hidden symmetries of quantum impurities VL - 121 ER - TY - JOUR AB - Using the geodesic distance on the n-dimensional sphere, we study the expected radius function of the Delaunay mosaic of a random set of points. Specifically, we consider the partition of the mosaic into intervals of the radius function and determine the expected number of intervals whose radii are less than or equal to a given threshold. We find that the expectations are essentially the same as for the Poisson–Delaunay mosaic in n-dimensional Euclidean space. Assuming the points are not contained in a hemisphere, the Delaunay mosaic is isomorphic to the boundary complex of the convex hull in Rn+1, so we also get the expected number of faces of a random inscribed polytope. As proved in Antonelli et al. [Adv. in Appl. Probab. 9–12 (1977–1980)], an orthant section of the n-sphere is isometric to the standard n-simplex equipped with the Fisher information metric. It follows that the latter space has similar stochastic properties as the n-dimensional Euclidean space. Our results are therefore relevant in information geometry and in population genetics. AU - Edelsbrunner, Herbert AU - Nikitenko, Anton ID - 87 IS - 5 JF - Annals of Applied Probability TI - Random inscribed polytopes have similar radius functions as Poisson-Delaunay mosaics VL - 28 ER - TY - JOUR AB - The phytohormone auxin is the information carrier in a plethora of developmental and physiological processes in plants(1). It has been firmly established that canonical, nuclear auxin signalling acts through regulation of gene transcription(2). Here, we combined microfluidics, live imaging, genetic engineering and computational modelling to reanalyse the classical case of root growth inhibition(3) by auxin. We show that Arabidopsis roots react to addition and removal of auxin by extremely rapid adaptation of growth rate. This process requires intracellular auxin perception but not transcriptional reprogramming. The formation of the canonical TIR1/AFB-Aux/IAA co-receptor complex is required for the growth regulation, hinting to a novel, non-transcriptional branch of this signalling pathway. Our results challenge the current understanding of root growth regulation by auxin and suggest another, presumably non-transcriptional, signalling output of the canonical auxin pathway. AU - Fendrych, Matyas AU - Akhmanova, Maria AU - Merrin, Jack AU - Glanc, Matous AU - Hagihara, Shinya AU - Takahashi, Koji AU - Uchida, Naoyuki AU - Torii, Keiko U AU - Friml, Jirí ID - 192 IS - 7 JF - Nature Plants TI - Rapid and reversible root growth inhibition by TIR1 auxin signalling VL - 4 ER - TY - JOUR AB - The intercellular transport of auxin is driven by PIN-formed (PIN) auxin efflux carriers. PINs are localized at the plasma membrane (PM) and on constitutively recycling endomembrane vesicles. Therefore, PINs can mediate auxin transport either by direct translocation across the PM or by pumping auxin into secretory vesicles (SVs), leading to its secretory release upon fusion with the PM. Which of these two mechanisms dominates is a matter of debate. Here, we addressed the issue with a mathematical modeling approach. We demonstrate that the efficiency of secretory transport depends on SV size, half-life of PINs on the PM, pH, exocytosis frequency and PIN density. 3D structured illumination microscopy (SIM) was used to determine PIN density on the PM. Combining this data with published values of the other parameters, we show that the transport activity of PINs in SVs would have to be at least 1000× greater than on the PM in order to produce a comparable macroscopic auxin transport. If both transport mechanisms operated simultaneously and PINs were equally active on SVs and PM, the contribution of secretion to the total auxin flux would be negligible. In conclusion, while secretory vesicle-mediated transport of auxin is an intriguing and theoretically possible model, it is unlikely to be a major mechanism of auxin transport inplanta. AU - Hille, Sander AU - Akhmanova, Maria AU - Glanc, Matous AU - Johnson, Alexander J AU - Friml, Jirí ID - 14 IS - 11 JF - International Journal of Molecular Sciences TI - Relative contribution of PIN-containing secretory vesicles and plasma membrane PINs to the directed auxin transport: Theoretical estimation VL - 19 ER - TY - JOUR AB - We study how a block of genome with a large number of weakly selected loci introgresses under directional selection into a genetically homogeneous population. We derive exact expressions for the expected rate of growth of any fragment of the introduced block during the initial phase of introgression, and show that the growth rate of a single-locus variant is largely insensitive to its own additive effect, but depends instead on the combined effect of all loci within a characteristic linkage scale. The expected growth rate of a fragment is highly correlated with its long-term introgression probability in populations of moderate size, and can hence identify variants that are likely to introgress across replicate populations. We clarify how the introgression probability of an individual variant is determined by the interplay between hitchhiking with relatively large fragments during the early phase of introgression and selection on fine-scale variation within these, which at longer times results in differential introgression probabilities for beneficial and deleterious loci within successful fragments. By simulating individuals, we also investigate how introgression probabilities at individual loci depend on the variance of fitness effects, the net fitness of the introduced block, and the size of the recipient population, and how this shapes the net advance under selection. Our work suggests that even highly replicable substitutions may be associated with a range of selective effects, which makes it challenging to fine map the causal loci that underlie polygenic adaptation. AU - Sachdeva, Himani AU - Barton, Nicholas H ID - 39 IS - 4 JF - Genetics SN - 00166731 TI - Replicability of introgression under linked, polygenic selection VL - 210 ER - TY - JOUR AB - We analyze the theoretical derivation of the beyond-mean-field equation of state for two-dimensional gas of dilute, ultracold alkali-metal atoms in the Bardeen–Cooper–Schrieffer (BCS) to Bose–Einstein condensate (BEC) crossover. We show that at zero temperature our theory — considering Gaussian fluctuations on top of the mean-field equation of state — is in very good agreement with experimental data. Subsequently, we investigate the superfluid density at finite temperature and its renormalization due to the proliferation of vortex–antivortex pairs. By doing so, we determine the Berezinskii–Kosterlitz–Thouless (BKT) critical temperature — at which the renormalized superfluid density jumps to zero — as a function of the inter-atomic potential strength. We find that the Nelson–Kosterlitz criterion overestimates the BKT temperature with respect to the renormalization group equations, this effect being particularly relevant in the intermediate regime of the crossover. AU - Bighin, Giacomo AU - Salasnich, Luca ID - 420 IS - 17 JF - International Journal of Modern Physics B TI - Renormalization of the superfluid density in the two-dimensional BCS-BEC crossover VL - 32 ER - TY - JOUR AB - Genomes of closely-related species or populations often display localized regions of enhanced relative sequence divergence, termed genomic islands. It has been proposed that these islands arise through selective sweeps and/or barriers to gene flow. Here, we genetically dissect a genomic island that controls flower color pattern differences between two subspecies of Antirrhinum majus, A.m.striatum and A.m.pseudomajus, and relate it to clinal variation across a natural hybrid zone. We show that selective sweeps likely raised relative divergence at two tightly-linked MYB-like transcription factors, leading to distinct flower patterns in the two subspecies. The two patterns provide alternate floral guides and create a strong barrier to gene flow where populations come into contact. This barrier affects the selected flower color genes and tightlylinked loci, but does not extend outside of this domain, allowing gene flow to lower relative divergence for the rest of the chromosome. Thus, both selective sweeps and barriers to gene flow play a role in shaping genomic islands: sweeps cause elevation in relative divergence, while heterogeneous gene flow flattens the surrounding "sea," making the island of divergence stand out. By showing how selective sweeps establish alternative adaptive phenotypes that lead to barriers to gene flow, our study sheds light on possible mechanisms leading to reproductive isolation and speciation. AU - Tavares, Hugo AU - Whitley, Annabel AU - Field, David AU - Bradley, Desmond AU - Couchman, Matthew AU - Copsey, Lucy AU - Elleouet, Joane AU - Burrus, Monique AU - Andalo, Christophe AU - Li, Miaomiao AU - Li, Qun AU - Xue, Yongbiao AU - Rebocho, Alexandra B AU - Barton, Nicholas H AU - Coen, Enrico ID - 38 IS - 43 JF - PNAS SN - 00278424 TI - Selection and gene flow shape genomic islands that control floral guides VL - 115 ER - TY - CONF AB - There is currently significant interest in operating devices in the quantum regime, where their behaviour cannot be explained through classical mechanics. Quantum states, including entangled states, are fragile and easily disturbed by excessive thermal noise. Here we address the question of whether it is possible to create non-reciprocal devices that encourage the flow of thermal noise towards or away from a particular quantum device in a network. Our work makes use of the cascaded systems formalism to answer this question in the affirmative, showing how a three-port device can be used as an effective thermal transistor, and illustrates how this formalism maps onto an experimentally-realisable optomechanical system. Our results pave the way to more resilient quantum devices and to the use of thermal noise as a resource. AU - Xuereb, André AU - Aquilina, Matteo AU - Barzanjeh, Shabir ED - Andrews, D L ED - Ostendorf, A ED - Bain, A J ED - Nunzi, J M ID - 155 TI - Routing thermal noise through quantum networks VL - 10672 ER - TY - JOUR AB - Cuprate superconductors have long been thought of as having strong electronic correlations but negligible spin-orbit coupling. Using spin- and angle-resolved photoemission spectroscopy, we discovered that one of the most studied cuprate superconductors, Bi2212, has a nontrivial spin texture with a spin-momentum locking that circles the Brillouin zone center and a spin-layer locking that allows states of opposite spin to be localized in different parts of the unit cell. Our findings pose challenges for the vast majority of models of cuprates, such as the Hubbard model and its variants, where spin-orbit interaction has been mostly neglected, and open the intriguing question of how the high-temperature superconducting state emerges in the presence of this nontrivial spin texture. AU - Gotlieb, Kenneth AU - Lin, Chiu-Yun AU - Serbyn, Maksym AU - Zhang, Wentao AU - Smallwood, Christopher L. AU - Jozwiak, Christopher AU - Eisaki, Hiroshi AU - Hussain, Zahid AU - Vishwanath, Ashvin AU - Lanzara, Alessandra ID - 5767 IS - 6420 JF - Science SN - 0036-8075 TI - Revealing hidden spin-momentum locking in a high-temperature cuprate superconductor VL - 362 ER - TY - JOUR AB - In this paper, we present a formal model-driven design approach to establish a safety-assured implementation of multifunction vehicle bus controller (MVBC), which controls the data transmission among the devices of the vehicle. First, the generic models and safety requirements described in International Electrotechnical Commission Standard 61375 are formalized as time automata and timed computation tree logic formulas, respectively. With model checking tool Uppaal, we verify whether or not the constructed timed automata satisfy the formulas and several logic inconsistencies in the original standard are detected and corrected. Then, we apply the code generation tool Times to generate C code from the verified model, which is later synthesized into a real MVBC chip, with some handwriting glue code. Furthermore, the runtime verification tool RMOR is applied on the integrated code, to verify some safety requirements that cannot be formalized on the timed automata. For evaluation, we compare the proposed approach with existing MVBC design methods, such as BeagleBone, Galsblock, and Simulink. Experiments show that more ambiguousness or bugs in the standard are detected during Uppaal verification, and the generated code of Times outperforms the C code generated by others in terms of the synthesized binary code size. The errors in the standard have been confirmed and the resulting MVBC has been deployed in the real train communication network. AU - Jiang, Yu AU - Liu, Han AU - Song, Huobing AU - Kong, Hui AU - Wang, Rui AU - Guan, Yong AU - Sha, Lui ID - 434 IS - 10 JF - IEEE Transactions on Intelligent Transportation Systems TI - Safety-assured model-driven design of the multifunction vehicle bus controller VL - 19 ER - TY - JOUR AB - Facial shape is the basis for facial recognition and categorization. Facial features reflect the underlying geometry of the skeletal structures. Here, we reveal that cartilaginous nasal capsule (corresponding to upper jaw and face) is shaped by signals generated by neural structures: brain and olfactory epithelium. Brain-derived Sonic Hedgehog (SHH) enables the induction of nasal septum and posterior nasal capsule, whereas the formation of a capsule roof is controlled by signals from the olfactory epithelium. Unexpectedly, the cartilage of the nasal capsule turned out to be important for shaping membranous facial bones during development. This suggests that conserved neurosensory structures could benefit from protection and have evolved signals inducing cranial cartilages encasing them. Experiments with mutant mice revealed that the genomic regulatory regions controlling production of SHH in the nervous system contribute to facial cartilage morphogenesis, which might be a mechanism responsible for the adaptive evolution of animal faces and snouts. AU - Kaucka, Marketa AU - Petersen, Julian AU - Tesarova, Marketa AU - Szarowska, Bara AU - Kastriti, Maria AU - Xie, Meng AU - Kicheva, Anna AU - Annusver, Karl AU - Kasper, Maria AU - Symmons, Orsolya AU - Pan, Leslie AU - Spitz, Francois AU - Kaiser, Jozef AU - Hovorakova, Maria AU - Zikmund, Tomas AU - Sunadome, Kazunori AU - Matise, Michael P AU - Wang, Hui AU - Marklund, Ulrika AU - Abdo, Hind AU - Ernfors, Patrik AU - Maire, Pascal AU - Wurmser, Maud AU - Chagin, Andrei S AU - Fried, Kaj AU - Adameyko, Igor ID - 162 JF - eLife TI - Signals from the brain and olfactory epithelium control shaping of the mammalian nasal capsule cartilage VL - 7 ER - TY - CONF AB - At ITCS 2013, Mahmoody, Moran and Vadhan [MMV13] introduce and construct publicly verifiable proofs of sequential work, which is a protocol for proving that one spent sequential computational work related to some statement. The original motivation for such proofs included non-interactive time-stamping and universally verifiable CPU benchmarks. A more recent application, and our main motivation, are blockchain designs, where proofs of sequential work can be used – in combination with proofs of space – as a more ecological and economical substitute for proofs of work which are currently used to secure Bitcoin and other cryptocurrencies. The construction proposed by [MMV13] is based on a hash function and can be proven secure in the random oracle model, or assuming inherently sequential hash-functions, which is a new standard model assumption introduced in their work. In a proof of sequential work, a prover gets a “statement” χ, a time parameter N and access to a hash-function H, which for the security proof is modelled as a random oracle. Correctness requires that an honest prover can make a verifier accept making only N queries to H, while soundness requires that any prover who makes the verifier accept must have made (almost) N sequential queries to H. Thus a solution constitutes a proof that N time passed since χ was received. Solutions must be publicly verifiable in time at most polylogarithmic in N. The construction of [MMV13] is based on “depth-robust” graphs, and as a consequence has rather poor concrete parameters. But the major drawback is that the prover needs not just N time, but also N space to compute a proof. In this work we propose a proof of sequential work which is much simpler, more efficient and achieves much better concrete bounds. Most importantly, the space required can be as small as log (N) (but we get better soundness using slightly more memory than that). An open problem stated by [MMV13] that our construction does not solve either is achieving a “unique” proof, where even a cheating prover can only generate a single accepting proof. This property would be extremely useful for applications to blockchains. AU - Cohen, Bram AU - Pietrzak, Krzysztof Z ID - 302 TI - Simple proofs of sequential work VL - 10821 ER - TY - JOUR AB - Correlations in sensory neural networks have both extrinsic and intrinsic origins. Extrinsic or stimulus correlations arise from shared inputs to the network and, thus, depend strongly on the stimulus ensemble. Intrinsic or noise correlations reflect biophysical mechanisms of interactions between neurons, which are expected to be robust to changes in the stimulus ensemble. Despite the importance of this distinction for understanding how sensory networks encode information collectively, no method exists to reliably separate intrinsic interactions from extrinsic correlations in neural activity data, limiting our ability to build predictive models of the network response. In this paper we introduce a general strategy to infer population models of interacting neurons that collectively encode stimulus information. The key to disentangling intrinsic from extrinsic correlations is to infer the couplings between neurons separately from the encoding model and to combine the two using corrections calculated in a mean-field approximation. We demonstrate the effectiveness of this approach in retinal recordings. The same coupling network is inferred from responses to radically different stimulus ensembles, showing that these couplings indeed reflect stimulus-independent interactions between neurons. The inferred model predicts accurately the collective response of retinal ganglion cell populations as a function of the stimulus. AU - Ferrari, Ulisse AU - Deny, Stephane AU - Chalk, Matthew J AU - Tkacik, Gasper AU - Marre, Olivier AU - Mora, Thierry ID - 31 IS - 4 JF - Physical Review E SN - 24700045 TI - Separating intrinsic interactions from extrinsic correlations in a network of sensory neurons VL - 98 ER - TY - JOUR AB - Tropical geometry, an established field in pure mathematics, is a place where string theory, mirror symmetry, computational algebra, auction theory, and so forth meet and influence one another. In this paper, we report on our discovery of a tropical model with self-organized criticality (SOC) behavior. Our model is continuous, in contrast to all known models of SOC, and is a certain scaling limit of the sandpile model, the first and archetypical model of SOC. We describe how our model is related to pattern formation and proportional growth phenomena and discuss the dichotomy between continuous and discrete models in several contexts. Our aim in this context is to present an idealized tropical toy model (cf. Turing reaction-diffusion model), requiring further investigation. AU - Kalinin, Nikita AU - Guzmán Sáenz, Aldo AU - Prieto, Y AU - Shkolnikov, Mikhail AU - Kalinina, V AU - Lupercio, Ernesto ID - 64 IS - 35 JF - PNAS: Proceedings of the National Academy of Sciences of the United States of America SN - 00278424 TI - Self-organized criticality and pattern emergence through the lens of tropical geometry VL - 115 ER - TY - GEN AB - Facial shape is the basis for facial recognition and categorization. Facial features reflect the underlying geometry of the skeletal structures. Here we reveal that cartilaginous nasal capsule (corresponding to upper jaw and face) is shaped by signals generated by neural structures: brain and olfactory epithelium. Brain-derived Sonic Hedgehog (SHH) enables the induction of nasal septum and posterior nasal capsule, whereas the formation of a capsule roof is controlled by signals from the olfactory epithelium. Unexpectedly, the cartilage of the nasal capsule turned out to be important for shaping membranous facial bones during development. This suggests that conserved neurosensory structures could benefit from protection and have evolved signals inducing cranial cartilages encasing them. Experiments with mutant mice revealed that the genomic regulatory regions controlling production of SHH in the nervous system contribute to facial cartilage morphogenesis, which might be a mechanism responsible for the adaptive evolution of animal faces and snouts. AU - Kaucka, Marketa AU - Petersen, Julian AU - Tesarova, Marketa AU - Szarowska, Bara AU - Kastriti, Maria Eleni AU - Xie, Meng AU - Kicheva, Anna AU - Annusver, Karl AU - Kasper, Maria AU - Symmons, Orsolya AU - Pan, Leslie AU - Spitz, Francois AU - Kaiser, Jozef AU - Hovorakova, Maria AU - Zikmund, Tomas AU - Sunadome, Kazunori AU - Matise, Michael P AU - Wang, Hui AU - Marklund, Ulrika AU - Abdo, Hind AU - Ernfors, Patrik AU - Maire, Pascal AU - Wurmser, Maud AU - Chagin, Andrei S AU - Fried, Kaj AU - Adameyko, Igor ID - 9838 TI - Data from: Signals from the brain and olfactory epithelium control shaping of the mammalian nasal capsule cartilage ER - TY - JOUR AB - The small-conductance, Ca2+-activated K+ (SK) channel subtype SK2 regulates the spike rate and firing frequency, as well as Ca2+ transients in Purkinje cells (PCs). To understand the molecular basis by which SK2 channels mediate these functions, we analyzed the exact location and densities of SK2 channels along the neuronal surface of the mouse cerebellar PCs using SDS-digested freeze-fracture replica labeling (SDS-FRL) of high sensitivity combined with quantitative analyses. Immunogold particles for SK2 were observed on post- and pre-synaptic compartments showing both scattered and clustered distribution patterns. We found an axo-somato-dendritic gradient of the SK2 particle density increasing 12-fold from soma to dendritic spines. Using two different immunogold approaches, we also found that SK2 immunoparticles were frequently adjacent to, but never overlap with, the postsynaptic density of excitatory synapses in PC spines. Co-immunoprecipitation analysis demonstrated that SK2 channels form macromolecular complexes with two types of proteins that mobilize Ca2+: CaV2.1 channels and mGlu1α receptors in the cerebellum. Freeze-fracture replica double-labeling showed significant co-clustering of particles for SK2 with those for CaV2.1 channels and mGlu1α receptors. SK2 channels were also detected at presynaptic sites, mostly at the presynaptic active zone (AZ), where they are close to CaV2.1 channels, though they are not significantly co-clustered. These data demonstrate that SK2 channels located in different neuronal compartments can associate with distinct proteins mobilizing Ca2+, and suggest that the ultrastructural association of SK2 with CaV2.1 and mGlu1α provides the mechanism that ensures voltage (excitability) regulation by distinct intracellular Ca2+ transients in PCs. AU - Luján, Rafæl AU - Aguado, Carolina AU - Ciruela, Francisco AU - Arus, Xavier AU - Martín Belmonte, Alejandro AU - Alfaro Ruiz, Rocío AU - Martinez Gomez, Jesus AU - De La Ossa, Luis AU - Watanabe, Masahiko AU - Adelman, John AU - Shigemoto, Ryuichi AU - Fukazawa, Yugo ID - 41 JF - Frontiers in Cellular Neuroscience SN - 16625102 TI - Sk2 channels associate with mGlu1α receptors and CaV2.1 channels in Purkinje cells VL - 12 ER - TY - JOUR AB - The strong atomistic spin–orbit coupling of holes makes single-shot spin readout measurements difficult because it reduces the spin lifetimes. By integrating the charge sensor into a high bandwidth radio frequency reflectometry setup, we were able to demonstrate single-shot readout of a germanium quantum dot hole spin and measure the spin lifetime. Hole spin relaxation times of about 90 μs at 500 mT are reported, with a total readout visibility of about 70%. By analyzing separately the spin-to-charge conversion and charge readout fidelities, we have obtained insight into the processes limiting the visibilities of hole spins. The analyses suggest that high hole visibilities are feasible at realistic experimental conditions, underlying the potential of hole spins for the realization of viable qubit devices. AU - Vukušić, Lada AU - Kukucka, Josip AU - Watzinger, Hannes AU - Milem, Joshua M AU - Schäffler, Friedrich AU - Katsaros, Georgios ID - 23 IS - 11 JF - Nano Letters SN - 15306984 TI - Single-shot readout of hole spins in Ge VL - 18 ER - TY - CONF AB - Concurrent accesses to shared data structures must be synchronized to avoid data races. Coarse-grained synchronization, which locks the entire data structure, is easy to implement but does not scale. Fine-grained synchronization can scale well, but can be hard to reason about. Hand-over-hand locking, in which operations are pipelined as they traverse the data structure, combines fine-grained synchronization with ease of use. However, the traditional implementation suffers from inherent overheads. This paper introduces snapshot-based synchronization (SBS), a novel hand-over-hand locking mechanism. SBS decouples the synchronization state from the data, significantly improving cache utilization. Further, it relies on guarantees provided by pipelining to minimize synchronization that requires cross-thread communication. Snapshot-based synchronization thus scales much better than traditional hand-over-hand locking, while maintaining the same ease of use. AU - Gilad, Eran AU - Brown, Trevor A AU - Oskin, Mark AU - Etsion, Yoav ID - 85 SN - 03029743 TI - Snapshot based synchronization: A fast replacement for Hand-over-Hand locking VL - 11014 ER - TY - JOUR AB - Many-body quantum systems typically display fast dynamics and ballistic spreading of information. Here we address the open problem of how slow the dynamics can be after a generic breaking of integrability by local interactions. We develop a method based on degenerate perturbation theory that reveals slow dynamical regimes and delocalization processes in general translation invariant models, along with accurate estimates of their delocalization time scales. Our results shed light on the fundamental questions of the robustness of quantum integrable systems and the possibility of many-body localization without disorder. As an example, we construct a large class of one-dimensional lattice models where, despite the absence of asymptotic localization, the transient dynamics is exceptionally slow, i.e., the dynamics is indistinguishable from that of many-body localized systems for the system sizes and time scales accessible in experiments and numerical simulations. AU - Michailidis, Alexios AU - Žnidarič, Marko AU - Medvedyeva, Mariya AU - Abanin, Dmitry AU - Prosen, Tomaž AU - Papić, Zlatko ID - 327 IS - 10 JF - Physical Review B TI - Slow dynamics in translation-invariant quantum lattice models VL - 97 ER -