TY - JOUR AB - Auxin is a major plant growth regulator, but current models on auxin perception and signaling cannot explain the whole plethora of auxin effects, in particular those associated with rapid responses. A possible candidate for a component of additional auxin perception mechanisms is the AUXIN BINDING PROTEIN 1 (ABP1), whose function in planta remains unclear. Here we combined expression analysis with gain- and loss-of-function approaches to analyze the role of ABP1 in plant development. ABP1 shows a broad expression largely overlapping with, but not regulated by, transcriptional auxin response activity. Furthermore, ABP1 activity is not essential for the transcriptional auxin signaling. Genetic in planta analysis revealed that abp1 loss-of-function mutants show largely normal development with minor defects in bolting. On the other hand, ABP1 gain-of-function alleles show a broad range of growth and developmental defects, including root and hypocotyl growth and bending, lateral root and leaf development, bolting, as well as response to heat stress. At the cellular level, ABP1 gain-of-function leads to impaired auxin effect on PIN polar distribution and affects BFA-sensitive PIN intracellular aggregation. The gain-of-function analysis suggests a broad, but still mechanistically unclear involvement of ABP1 in plant development, possibly masked in abp1 loss-of-function mutants by a functional redundancy. AU - Gelová, Zuzana AU - Gallei, Michelle C AU - Pernisová, Markéta AU - Brunoud, Géraldine AU - Zhang, Xixi AU - Glanc, Matous AU - Li, Lanxin AU - Michalko, Jaroslav AU - Pavlovicova, Zlata AU - Verstraeten, Inge AU - Han, Huibin AU - Hajny, Jakub AU - Hauschild, Robert AU - Čovanová, Milada AU - Zwiewka, Marta AU - Hörmayer, Lukas AU - Fendrych, Matyas AU - Xu, Tongda AU - Vernoux, Teva AU - Friml, Jiří ID - 8931 JF - Plant Science KW - Agronomy and Crop Science KW - Plant Science KW - Genetics KW - General Medicine SN - 0168-9452 TI - Developmental roles of auxin binding protein 1 in Arabidopsis thaliana VL - 303 ER - TY - JOUR AB - The phytohormone auxin and its directional transport through tissues are intensively studied. However, a mechanistic understanding of auxin-mediated feedback on endocytosis and polar distribution of PIN auxin transporters remains limited due to contradictory observations and interpretations. Here, we used state-of-the-art methods to reexamine the auxin effects on PIN endocytic trafficking. We used high auxin concentrations or longer treatments versus lower concentrations and shorter treatments of natural (IAA) and synthetic (NAA) auxins to distinguish between specific and nonspecific effects. Longer treatments of both auxins interfere with Brefeldin A-mediated intracellular PIN2 accumulation and also with general aggregation of endomembrane compartments. NAA treatment decreased the internalization of the endocytic tracer dye, FM4-64; however, NAA treatment also affected the number, distribution, and compartment identity of the early endosome/trans-Golgi network (EE/TGN), rendering the FM4-64 endocytic assays at high NAA concentrations unreliable. To circumvent these nonspecific effects of NAA and IAA affecting the endomembrane system, we opted for alternative approaches visualizing the endocytic events directly at the plasma membrane (PM). Using Total Internal Reflection Fluorescence (TIRF) microscopy, we saw no significant effects of IAA or NAA treatments on the incidence and dynamics of clathrin foci, implying that these treatments do not affect the overall endocytosis rate. However, both NAA and IAA at low concentrations rapidly and specifically promoted endocytosis of photo-converted PIN2 from the PM. These analyses identify a specific effect of NAA and IAA on PIN2 endocytosis, thus contributing to its polarity maintenance and furthermore illustrate that high auxin levels have nonspecific effects on trafficking and endomembrane compartments. AU - Narasimhan, Madhumitha AU - Gallei, Michelle C AU - Tan, Shutang AU - Johnson, Alexander J AU - Verstraeten, Inge AU - Li, Lanxin AU - Rodriguez Solovey, Lesia AU - Han, Huibin AU - Himschoot, E AU - Wang, R AU - Vanneste, S AU - Sánchez-Simarro, J AU - Aniento, F AU - Adamowski, Maciek AU - Friml, Jiří ID - 9287 IS - 2 JF - Plant Physiology SN - 0032-0889 TI - Systematic analysis of specific and nonspecific auxin effects on endocytosis and trafficking VL - 186 ER - TY - THES AB - Plant motions occur across a wide spectrum of timescales, ranging from seed dispersal through bursting (milliseconds) and stomatal opening (minutes) to long-term adaptation of gross architecture. Relatively fast motions include water-driven growth as exemplified by root cell expansion under abiotic/biotic stresses or during gravitropism. A showcase is a root growth inhibition in 30 seconds triggered by the phytohormone auxin. However, the cellular and molecular mechanisms are still largely unknown. This thesis covers the studies about this topic as follows. By taking advantage of microfluidics combined with live imaging, pharmaceutical tools, and transgenic lines, we examined the kinetics of and causal relationship among various auxininduced rapid cellular changes in root growth, apoplastic pH, cytosolic Ca2+, cortical microtubule (CMT) orientation, and vacuolar morphology. We revealed that CMT reorientation and vacuolar constriction are the consequence of growth itself instead of responding directly to auxin. In contrast, auxin induces apoplast alkalinization to rapidly inhibit root growth in 30 seconds. This auxin-triggered apoplast alkalinization results from rapid H+- influx that is contributed by Ca2+ inward channel CYCLIC NUCLEOTIDE-GATED CHANNEL 14 (CNGC14)-dependent Ca2+ signaling. To dissect which auxin signaling mediates the rapid apoplast alkalinization, we combined microfluidics and genetic engineering to verify that TIR1/AFB receptors conduct a non-transcriptional regulation on Ca2+ and H+ -influx. This non-canonical pathway is mostly mediated by the cytosolic portion of TIR1/AFB. On the other hand, we uncovered, using biochemical and phospho-proteomic analysis, that auxin cell surface signaling component TRANSMEMBRANE KINASE 1 (TMK1) plays a negative role during auxin-trigger apoplast alkalinization and root growth inhibition through directly activating PM H+ -ATPases. Therefore, we discovered that PM H+ -ATPases counteract instead of mediate the auxintriggered rapid H+ -influx, and that TIR1/AFB and TMK1 regulate root growth antagonistically. This opposite effect of TIR1/AFB and TMK1 is consistent during auxin-induced hypocotyl elongation, leading us to explore the relation of two signaling pathways. Assisted with biochemistry and fluorescent imaging, we verified for the first time that TIR1/AFB and TMK1 can interact with each other. The ability of TIR1/AFB binding to membrane lipid provides a basis for the interaction of plasma membrane- and cytosol-localized proteins. Besides, transgenic analysis combined with genetic engineering and biochemistry showed that vi they do function in the same pathway. Particularly, auxin-induced TMK1 increase is TIR1/AFB dependent, suggesting TIR1/AFB regulation on TMK1. Conversely, TMK1 also regulates TIR1/AFB protein levels and thus auxin canonical signaling. To follow the study of rapid growth regulation, we analyzed another rapid growth regulator, signaling peptide RALF1. We showed that RALF1 also triggers a rapid and reversible growth inhibition caused by H + influx, highly resembling but not dependent on auxin. Besides, RALF1 promotes auxin biosynthesis by increasing expression of auxin biosynthesis enzyme YUCCAs and thus induces auxin signaling in ca. 1 hour, contributing to the sustained RALF1-triggered growth inhibition. These studies collectively contribute to understanding rapid regulation on plant cell growth, novel auxin signaling pathway as well as auxin-peptide crosstalk. AU - Li, Lanxin ID - 10083 SN - 2663-337X TI - Rapid cell growth regulation in Arabidopsis ER - TY - JOUR AB - Auxin plays a dual role in growth regulation and, depending on the tissue and concentration of the hormone, it can either promote or inhibit division and expansion processes in plants. Recent studies have revealed that, beyond transcriptional reprogramming, alternative auxincontrolled mechanisms regulate root growth. Here, we explored the impact of different concentrations of the synthetic auxin NAA that establish growth-promoting and -repressing conditions on the root tip proteome and phosphoproteome, generating a unique resource. From the phosphoproteome data, we pinpointed (novel) growth regulators, such as the RALF34-THE1 module. Our results, together with previously published studies, suggest that auxin, H+-ATPases, cell wall modifications and cell wall sensing receptor-like kinases are tightly embedded in a pathway regulating cell elongation. Furthermore, our study assigned a novel role to MKK2 as a regulator of primary root growth and a (potential) regulator of auxin biosynthesis and signalling, and suggests the importance of the MKK2 Thr31 phosphorylation site for growth regulation in the Arabidopsis root tip. AU - Nikonorova, N AU - Murphy, E AU - Fonseca de Lima, CF AU - Zhu, S AU - van de Cotte, B AU - Vu, LD AU - Balcerowicz, D AU - Li, Lanxin AU - Kong, X AU - De Rop, G AU - Beeckman, T AU - Friml, Jiří AU - Vissenberg, K AU - Morris, PC AU - Ding, Z AU - De Smet, I ID - 10015 JF - Cells KW - primary root KW - (phospho)proteomics KW - auxin KW - (receptor) kinase SN - 2073-4409 TI - The Arabidopsis root tip (phospho)proteomes at growth-promoting versus growth-repressing conditions reveal novel root growth regulators VL - 10 ER - TY - GEN AB - Growth regulation tailors plant development to its environment. A showcase is response to gravity, where shoots bend up and roots down1. This paradox is based on opposite effects of the phytohormone auxin, which promotes cell expansion in shoots, while inhibiting it in roots via a yet unknown cellular mechanism2. Here, by combining microfluidics, live imaging, genetic engineering and phospho-proteomics in Arabidopsis thaliana, we advance our understanding how auxin inhibits root growth. We show that auxin activates two distinct, antagonistically acting signalling pathways that converge on the rapid regulation of the apoplastic pH, a causative growth determinant. Cell surface-based TRANSMEMBRANE KINASE1 (TMK1) interacts with and mediates phosphorylation and activation of plasma membrane H+-ATPases for apoplast acidification, while intracellular canonical auxin signalling promotes net cellular H+-influx, causing apoplast alkalinisation. The simultaneous activation of these two counteracting mechanisms poises the root for a rapid, fine-tuned growth modulation while navigating complex soil environment. AU - Li, Lanxin AU - Verstraeten, Inge AU - Roosjen, Mark AU - Takahashi, Koji AU - Rodriguez Solovey, Lesia AU - Merrin, Jack AU - Chen, Jian AU - Shabala, Lana AU - Smet, Wouter AU - Ren, Hong AU - Vanneste, Steffen AU - Shabala, Sergey AU - De Rybel, Bert AU - Weijers, Dolf AU - Kinoshita, Toshinori AU - Gray, William M. AU - Friml, Jiří ID - 10095 SN - 2693-5015 T2 - Research Square TI - Cell surface and intracellular auxin signalling for H+-fluxes in root growth ER - TY - THES AB - Indirect reciprocity in evolutionary game theory is a prominent mechanism for explaining the evolution of cooperation among unrelated individuals. In contrast to direct reciprocity, which is based on individuals meeting repeatedly, and conditionally cooperating by using their own experiences, indirect reciprocity is based on individuals’ reputations. If a player helps another, this increases the helper’s public standing, benefitting them in the future. This lets cooperation in the population emerge without individuals having to meet more than once. While the two modes of reciprocity are intertwined, they are difficult to compare. Thus, they are usually studied in isolation. Direct reciprocity can maintain cooperation with simple strategies, and is robust against noise even when players do not remember more than their partner’s last action. Meanwhile, indirect reciprocity requires its successful strategies, or social norms, to be more complex. Exhaustive search previously identified eight such norms, called the “leading eight”, which excel at maintaining cooperation. However, as the first result of this thesis, we show that the leading eight break down once we remove the fundamental assumption that information is synchronized and public, such that everyone agrees on reputations. Once we consider a more realistic scenario of imperfect information, where reputations are private, and individuals occasionally misinterpret or miss observations, the leading eight do not promote cooperation anymore. Instead, minor initial disagreements can proliferate, fragmenting populations into subgroups. In a next step, we consider ways to mitigate this issue. We first explore whether introducing “generosity” can stabilize cooperation when players use the leading eight strategies in noisy environments. This approach of modifying strategies to include probabilistic elements for coping with errors is known to work well in direct reciprocity. However, as we show here, it fails for the more complex norms of indirect reciprocity. Imperfect information still prevents cooperation from evolving. On the other hand, we succeeded to show in this thesis that modifying the leading eight to use “quantitative assessment”, i.e. tracking reputation scores on a scale beyond good and bad, and making overall judgments of others based on a threshold, is highly successful, even when noise increases in the environment. Cooperation can flourish when reputations are more nuanced, and players have a broader understanding what it means to be “good.” Finally, we present a single theoretical framework that unites the two modes of reciprocity despite their differences. Within this framework, we identify a novel simple and successful strategy for indirect reciprocity, which can cope with noisy environments and has an analogue in direct reciprocity. We can also analyze decision making when different sources of information are available. Our results help highlight that for sustaining cooperation, already the most simple rules of reciprocity can be sufficient. AU - Schmid, Laura ID - 10293 SN - 2663-337X TI - Evolution of cooperation via (in)direct reciprocity under imperfect information ER - TY - JOUR AB - Indirect reciprocity is a mechanism for the evolution of cooperation based on social norms. This mechanism requires that individuals in a population observe and judge each other’s behaviors. Individuals with a good reputation are more likely to receive help from others. Previous work suggests that indirect reciprocity is only effective when all relevant information is reliable and publicly available. Otherwise, individuals may disagree on how to assess others, even if they all apply the same social norm. Such disagreements can lead to a breakdown of cooperation. Here we explore whether the predominantly studied ‘leading eight’ social norms of indirect reciprocity can be made more robust by equipping them with an element of generosity. To this end, we distinguish between two kinds of generosity. According to assessment generosity, individuals occasionally assign a good reputation to group members who would usually be regarded as bad. According to action generosity, individuals occasionally cooperate with group members with whom they would usually defect. Using individual-based simulations, we show that the two kinds of generosity have a very different effect on the resulting reputation dynamics. Assessment generosity tends to add to the overall noise and allows defectors to invade. In contrast, a limited amount of action generosity can be beneficial in a few cases. However, even when action generosity is beneficial, the respective simulations do not result in full cooperation. Our results suggest that while generosity can favor cooperation when individuals use the most simple strategies of reciprocity, it is disadvantageous when individuals use more complex social norms. AU - Schmid, Laura AU - Shati, Pouya AU - Hilbe, Christian AU - Chatterjee, Krishnendu ID - 9997 IS - 1 JF - Scientific Reports KW - Multidisciplinary TI - The evolution of indirect reciprocity under action and assessment generosity VL - 11 ER - TY - JOUR AB - Direct and indirect reciprocity are key mechanisms for the evolution of cooperation. Direct reciprocity means that individuals use their own experience to decide whether to cooperate with another person. Indirect reciprocity means that they also consider the experiences of others. Although these two mechanisms are intertwined, they are typically studied in isolation. Here, we introduce a mathematical framework that allows us to explore both kinds of reciprocity simultaneously. We show that the well-known ‘generous tit-for-tat’ strategy of direct reciprocity has a natural analogue in indirect reciprocity, which we call ‘generous scoring’. Using an equilibrium analysis, we characterize under which conditions either of the two strategies can maintain cooperation. With simulations, we additionally explore which kind of reciprocity evolves when members of a population engage in social learning to adapt to their environment. Our results draw unexpected connections between direct and indirect reciprocity while highlighting important differences regarding their evolvability. AU - Schmid, Laura AU - Chatterjee, Krishnendu AU - Hilbe, Christian AU - Nowak, Martin A. ID - 9402 IS - 10 JF - Nature Human Behaviour TI - A unified framework of direct and indirect reciprocity VL - 5 ER - TY - JOUR AB - Elastic bending of initially flat slender elements allows the realization and economic fabrication of intriguing curved shapes. In this work, we derive an intuitive but rigorous geometric characterization of the design space of plane elastic rods with variable stiffness. It enables designers to determine which shapes are physically viable with active bending by visual inspection alone. Building on these insights, we propose a method for efficiently designing the geometry of a flat elastic rod that realizes a target equilibrium curve, which only requires solving a linear program. We implement this method in an interactive computational design tool that gives feedback about the feasibility of a design, and computes the geometry of the structural elements necessary to realize it within an instant. The tool also offers an iterative optimization routine that improves the fabricability of a model while modifying it as little as possible. In addition, we use our geometric characterization to derive an algorithm for analyzing and recovering the stability of elastic curves that would otherwise snap out of their unstable equilibrium shapes by buckling. We show the efficacy of our approach by designing and manufacturing several physical models that are assembled from flat elements. AU - Hafner, Christian AU - Bickel, Bernd ID - 9817 IS - 4 JF - ACM Transactions on Graphics KW - Computing methodologies KW - shape modeling KW - modeling and simulation KW - theory of computation KW - computational geometry KW - mathematics of computing KW - mathematical optimization SN - 0730-0301 TI - The design space of plane elastic curves VL - 40 ER - TY - THES AB - Plants maintain the capacity to develop new organs e.g. lateral roots post-embryonically throughout their whole life and thereby flexibly adapt to ever-changing environmental conditions. Plant hormones auxin and cytokinin are the main regulators of the lateral root organogenesis. Additionally to their solo activities, the interaction between auxin and cytokinin plays crucial role in fine-tuning of lateral root development and growth. In particular, cytokinin modulates auxin distribution within the developing lateral root by affecting the endomembrane trafficking of auxin transporter PIN1 and promoting its vacuolar degradation (Marhavý et al., 2011, 2014). This effect is independent of transcription and translation. Therefore, it suggests novel, non-canonical cytokinin activity occuring possibly on the posttranslational level. Impact of cytokinin and other plant hormones on auxin transporters (including PIN1) on the posttranslational level is described in detail in the introduction part of this thesis in a form of a review (Semeradova et al., 2020). To gain insights into the molecular machinery underlying cytokinin effect on the endomembrane trafficking in the plant cell, in particular on the PIN1 degradation, we conducted two large proteomic screens: 1) Identification of cytokinin binding proteins using chemical proteomics. 2) Monitoring of proteomic and phosphoproteomic changes upon cytokinin treatment. In the first screen, we identified DYNAMIN RELATED PROTEIN 2A (DRP2A). We found that DRP2A plays a role in cytokinin regulated processes during the plant growth and that cytokinin treatment promotes destabilization of DRP2A protein. However, the role of DRP2A in the PIN1 degradation remains to be elucidated. In the second screen, we found VACUOLAR PROTEIN SORTING 9A (VPS9A). VPS9a plays crucial role in plant’s response to cytokin and in cytokinin mediated PIN1 degradation. Altogether, we identified proteins, which bind to cytokinin and proteins that in response to cytokinin exhibit significantly changed abundance or phosphorylation pattern. By combining information from these two screens, we can pave our way towards understanding of noncanonical cytokinin effects. AU - Semerádová, Hana ID - 10135 SN - 2663-337X TI - Molecular mechanisms of the cytokinin-regulated endomembrane trafficking to coordinate plant organogenesis ER - TY - THES AB - Most real-world flows are multiphase, yet we know little about them compared to their single-phase counterparts. Multiphase flows are more difficult to investigate as their dynamics occur in large parameter space and involve complex phenomena such as preferential concentration, turbulence modulation, non-Newtonian rheology, etc. Over the last few decades, experiments in particle-laden flows have taken a back seat in favour of ever-improving computational resources. However, computers are still not powerful enough to simulate a real-world fluid with millions of finite-size particles. Experiments are essential not only because they offer a reliable way to investigate real-world multiphase flows but also because they serve to validate numerical studies and steer the research in a relevant direction. In this work, we have experimentally investigated particle-laden flows in pipes, and in particular, examined the effect of particles on the laminar-turbulent transition and the drag scaling in turbulent flows. For particle-laden pipe flows, an earlier study [Matas et al., 2003] reported how the sub-critical (i.e., hysteretic) transition that occurs via localised turbulent structures called puffs is affected by the addition of particles. In this study, in addition to this known transition, we found a super-critical transition to a globally fluctuating state with increasing particle concentration. At the same time, the Newtonian-type transition via puffs is delayed to larger Reynolds numbers. At an even higher concentration, only the globally fluctuating state is found. The dynamics of particle-laden flows are hence determined by two competing instabilities that give rise to three flow regimes: Newtonian-type turbulence at low, a particle-induced globally fluctuating state at high, and a coexistence state at intermediate concentrations. The effect of particles on turbulent drag is ambiguous, with studies reporting drag reduction, no net change, and even drag increase. The ambiguity arises because, in addition to particle concentration, particle shape, size, and density also affect the net drag. Even similar particles might affect the flow dissimilarly in different Reynolds number and concentration ranges. In the present study, we explored a wide range of both Reynolds number and concentration, using spherical as well as cylindrical particles. We found that the spherical particles do not reduce drag while the cylindrical particles are drag-reducing within a specific Reynolds number interval. The interval strongly depends on the particle concentration and the relative size of the pipe and particles. Within this interval, the magnitude of drag reduction reaches a maximum. These drag reduction maxima appear to fall onto a distinct power-law curve irrespective of the pipe diameter and particle concentration, and this curve can be considered as the maximum drag reduction asymptote for a given fibre shape. Such an asymptote is well known for polymeric flows but had not been identified for particle-laden flows prior to this work. AU - Agrawal, Nishchal ID - 9728 KW - Drag Reduction KW - Transition to Turbulence KW - Multiphase Flows KW - particle Laden Flows KW - Complex Flows KW - Experiments KW - Fluid Dynamics SN - 2663-337X TI - Transition to turbulence and drag reduction in particle-laden pipe flows ER - TY - CONF AB - We propose a neural information processing system obtained by re-purposing the function of a biological neural circuit model to govern simulated and real-world control tasks. Inspired by the structure of the nervous system of the soil-worm, C. elegans, we introduce ordinary neural circuits (ONCs), defined as the model of biological neural circuits reparameterized for the control of alternative tasks. We first demonstrate that ONCs realize networks with higher maximum flow compared to arbitrary wired networks. We then learn instances of ONCs to control a series of robotic tasks, including the autonomous parking of a real-world rover robot. For reconfiguration of the purpose of the neural circuit, we adopt a search-based optimization algorithm. Ordinary neural circuits perform on par and, in some cases, significantly surpass the performance of contemporary deep learning models. ONC networks are compact, 77% sparser than their counterpart neural controllers, and their neural dynamics are fully interpretable at the cell-level. AU - Hasani, Ramin AU - Lechner, Mathias AU - Amini, Alexander AU - Rus, Daniela AU - Grosu, Radu ID - 10673 SN - 2640-3498 T2 - Proceedings of the 37th International Conference on Machine Learning TI - A natural lottery ticket winner: Reinforcement learning with ordinary neural circuits ER - TY - CONF AB - Many systems rely on optimistic concurrent search trees for multi-core scalability. In principle, optimistic trees have a simple performance story: searches are read-only and so run in parallel, with writes to shared memory occurring only when modifying the data structure. However, this paper shows that in practice, obtaining the full performance benefits of optimistic search trees is not so simple. We focus on optimistic binary search trees (BSTs) and perform a detailed performance analysis of 10 state-of-the-art BSTs on large scale x86-64 hardware, using both microbenchmarks and an in-memory database system. We find and explain significant unexpected performance differences between BSTs with similar tree structure and search implementations, which we trace to subtle performance-degrading interactions of BSTs with systems software and hardware subsystems. We further derive a prescriptive approach to avoid this performance degradation, as well as algorithmic insights on optimistic BST design. Our work underlines the gap between the theory and practice of multi-core performance, and calls for further research to help bridge this gap. AU - Arbel-Raviv, Maya AU - Brown, Trevor A AU - Morrison, Adam ID - 7272 SN - 9781939133021 T2 - Proceedings of the 2018 USENIX Annual Technical Conference TI - Getting to the root of concurrent binary search tree performance ER - TY - CONF AB - The Price of Anarchy (PoA) is a well-established game-theoretic concept to shed light on coordination issues arising in open distributed systems. Leaving agents to selfishly optimize comes with the risk of ending up in sub-optimal states (in terms of performance and/or costs), compared to a centralized system design. However, the PoA relies on strong assumptions about agents' rationality (e.g., resources and information) and interactions, whereas in many distributed systems agents interact locally with bounded resources. They do so repeatedly over time (in contrast to "one-shot games"), and their strategies may evolve. Using a more realistic evolutionary game model, this paper introduces a realized evolutionary Price of Anarchy (ePoA). The ePoA allows an exploration of equilibrium selection in dynamic distributed systems with multiple equilibria, based on local interactions of simple memoryless agents. Considering a fundamental game related to virus propagation on networks, we present analytical bounds on the ePoA in basic network topologies and for different strategy update dynamics. In particular, deriving stationary distributions of the stochastic evolutionary process, we find that the Nash equilibria are not always the most abundant states, and that different processes can feature significant off-equilibrium behavior, leading to a significantly higher ePoA compared to the PoA studied traditionally in the literature. AU - Schmid, Laura AU - Chatterjee, Krishnendu AU - Schmid, Stefan ID - 7346 T2 - Proceedings of the 23rd International Conference on Principles of Distributed Systems TI - The evolutionary price of anarchy: Locally bounded agents in a dynamic virus game VL - 153 ER - TY - CONF AB - The monitoring of event frequencies can be used to recognize behavioral anomalies, to identify trends, and to deduce or discard hypotheses about the underlying system. For example, the performance of a web server may be monitored based on the ratio of the total count of requests from the least and most active clients. Exact frequency monitoring, however, can be prohibitively expensive; in the above example it would require as many counters as there are clients. In this paper, we propose the efficient probabilistic monitoring of common frequency properties, including the mode (i.e., the most common event) and the median of an event sequence. We define a logic to express composite frequency properties as a combination of atomic frequency properties. Our main contribution is an algorithm that, under suitable probabilistic assumptions, can be used to monitor these important frequency properties with four counters, independent of the number of different events. Our algorithm samples longer and longer subwords of an infinite event sequence. We prove the almost-sure convergence of our algorithm by generalizing ergodic theory from increasing-length prefixes to increasing-length subwords of an infinite sequence. A similar algorithm could be used to learn a connected Markov chain of a given structure from observing its outputs, to arbitrary precision, for a given confidence. AU - Ferrere, Thomas AU - Henzinger, Thomas A AU - Kragl, Bernhard ID - 7348 SN - 1868-8969 T2 - 28th EACSL Annual Conference on Computer Science Logic TI - Monitoring event frequencies VL - 152 ER - TY - JOUR AB - Coxeter triangulations are triangulations of Euclidean space based on a single simplex. By this we mean that given an individual simplex we can recover the entire triangulation of Euclidean space by inductively reflecting in the faces of the simplex. In this paper we establish that the quality of the simplices in all Coxeter triangulations is O(1/d−−√) of the quality of regular simplex. We further investigate the Delaunay property for these triangulations. Moreover, we consider an extension of the Delaunay property, namely protection, which is a measure of non-degeneracy of a Delaunay triangulation. In particular, one family of Coxeter triangulations achieves the protection O(1/d2). We conjecture that both bounds are optimal for triangulations in Euclidean space. AU - Choudhary, Aruni AU - Kachanovich, Siargey AU - Wintraecken, Mathijs ID - 7567 JF - Mathematics in Computer Science SN - 1661-8270 TI - Coxeter triangulations have good quality VL - 14 ER - TY - JOUR AB - The concept of the entanglement between spin and orbital degrees of freedom plays a crucial role in our understanding of various phases and exotic ground states in a broad class of materials, including orbitally ordered materials and spin liquids. We investigate how the spin-orbital entanglement in a Mott insulator depends on the value of the spin-orbit coupling of the relativistic origin. To this end, we numerically diagonalize a one-dimensional spin-orbital model with Kugel-Khomskii exchange interactions between spins and orbitals on different sites supplemented by the on-site spin-orbit coupling. In the regime of small spin-orbit coupling with regard to the spin-orbital exchange, the ground state to a large extent resembles the one obtained in the limit of vanishing spin-orbit coupling. On the other hand, for large spin-orbit coupling the ground state can, depending on the model parameters, either still show negligible spin-orbital entanglement or evolve to a highly spin-orbitally-entangled phase with completely distinct properties that are described by an effective XXZ model. The presented results suggest that (i) the spin-orbital entanglement may be induced by large on-site spin-orbit coupling, as found in the 5d transition metal oxides, such as the iridates; (ii) for Mott insulators with weak spin-orbit coupling of Ising type, such as, e.g., the alkali hyperoxides, the effects of the spin-orbit coupling on the ground state can, in the first order of perturbation theory, be neglected. AU - Gotfryd, Dorota AU - Paerschke, Ekaterina AU - Chaloupka, Jiri AU - Oles, Andrzej M. AU - Wohlfeld, Krzysztof ID - 7594 IS - 1 JF - Physical Review Research TI - How spin-orbital entanglement depends on the spin-orbit coupling in a Mott insulator VL - 2 ER - TY - CONF AB - Union-Find (or Disjoint-Set Union) is one of the fundamental problems in computer science; it has been well-studied from both theoretical and practical perspectives in the sequential case. Recently, there has been mounting interest in analyzing this problem in the concurrent scenario, and several asymptotically-efficient algorithms have been proposed. Yet, to date, there is very little known about the practical performance of concurrent Union-Find. This work addresses this gap. We evaluate and analyze the performance of several concurrent Union-Find algorithms and optimization strategies across a wide range of platforms (Intel, AMD, and ARM) and workloads (social, random, and road networks, as well as integrations into more complex algorithms). We first observe that, due to the limited computational cost, the number of induced cache misses is the critical determining factor for the performance of existing algorithms. We introduce new techniques to reduce this cost by storing node priorities implicitly and by using plain reads and writes in a way that does not affect the correctness of the algorithms. Finally, we show that Union-Find implementations are an interesting application for Transactional Memory (TM): one of the fastest algorithm variants we discovered is a sequential one that uses coarse-grained locking with the lock elision optimization to reduce synchronization cost and increase scalability. AU - Alistarh, Dan-Adrian AU - Fedorov, Alexander AU - Koval, Nikita ID - 7605 SN - 18688969 T2 - 23rd International Conference on Principles of Distributed Systems TI - In search of the fastest concurrent union-find algorithm VL - 153 ER - TY - GEN AB - Plasmodesmata (PD) are crucial structures for intercellular communication in multicellular plants with remorins being their crucial plant-specific structural and functional constituents. The PD biogenesis is an intriguing but poorly understood process. By expressing an Arabidopsis remorin protein in mammalian cells, we have reconstituted a PD-like filamentous structure, termed remorin filament (RF), connecting neighboring cells physically and physiologically. Notably, RFs are capable of transporting macromolecules intercellularly, in a way similar to plant PD. With further super-resolution microscopic analysis and biochemical characterization, we found that RFs are also composed of actin filaments, forming the core skeleton structure, aligned with the remorin protein. This unique heterologous filamentous structure might explain the molecular mechanism for remorin function as well as PD construction. Furthermore, remorin protein exhibits a specific distribution manner in the plasma membrane in mammalian cells, representing a lipid nanodomain, depending on its lipid modification status. Our studies not only provide crucial insights into the mechanism of PD biogenesis, but also uncovers unsuspected fundamental mechanistic and evolutionary links between intercellular communication systems of plants and animals. AU - Wei, Zhuang AU - Tan, Shutang AU - Liu, Tao AU - Wu, Yuan AU - Lei, Ji-Gang AU - Chen, ZhengJun AU - Friml, Jiří AU - Xue, Hong-Wei AU - Liao, Kan ID - 7601 T2 - bioRxiv TI - Plasmodesmata-like intercellular connections by plant remorin in animal cells ER - TY - JOUR AB - The growth of snail shells can be described by simple mathematical rules. Variation in a few parameters can explain much of the diversity of shell shapes seen in nature. However, empirical studies of gastropod shell shape variation typically use geometric morphometric approaches, which do not capture this growth pattern. We have developed a way to infer a set of developmentally descriptive shape parameters based on three-dimensional logarithmic helicospiral growth and using landmarks from two-dimensional shell images as input. We demonstrate the utility of this approach, and compare it to the geometric morphometric approach, using a large set of Littorina saxatilis shells in which locally adapted populations differ in shape. Our method can be modified easily to make it applicable to a wide range of shell forms, which would allow for investigations of the similarities and differences between and within many different species of gastropods. AU - Larsson, J. AU - Westram, Anja M AU - Bengmark, S. AU - Lundh, T. AU - Butlin, R. K. ID - 7651 IS - 163 JF - Journal of The Royal Society Interface SN - 1742-5689 TI - A developmentally descriptive method for quantifying shape in gastropod shells VL - 17 ER -