TY - JOUR AB - Cu2ZnSnS4, based on abundant and environmental friendly elements and with a direct band gap of 1.5 eV, is a main candidate material for solar energy conversion through both photovoltaics and photocatalysis. We detail here the synthesis of quasi-spherical Cu 2ZnSnS4 nanoparticles with unprecedented narrow size distributions. We further detail their use as seeds to produce CZTS-Au and CZTS-Pt heterostructured nanoparticles. Such heterostructured nanoparticles are shown to have excellent photocatalytic properties toward degradation of Rhodamine B and hydrogen generation by water splitting. AU - Yu, Xuelian AU - Shavel, Alexey AU - An, Xiaoqiang AU - Luo, Zhishan AU - Ibáñez, Maria AU - Cabot, Andreu ID - 356 IS - 26 JF - Journal of the American Chemical Society TI - Cu2ZnSnS4-Pt and Cu2ZnSnS4-Au heterostructured nanoparticles for photocatalytic water splitting and pollutant degradation VL - 136 ER - TY - JOUR AB - Monodispersed Pt3Sn nanoparticles were prepared through a mild thermal synthesis in the presence of surfactants. The performance of Pt3Sn for the electrooxidation of ethanol and adsorbed carbon monoxide (COad) in acid medium was studied by a combination of electrochemical and insitu spectroscopic methods, namely, infrared reflection absorption spectroscopy and differential electrochemical mass spectrometry (DEMS), and the results were compared to those obtained with the use of Pt black. The formation of the Pt3Sn solid solution promoted the oxidation of COad at less-positive potentials than those required for Pt black. Also, the electrooxidation of ethanol, especially at lower potentials, was more favorable with Pt3Sn, as deduced from the higher faradaic currents recorded during the ethanol oxidation reaction (EOR). However, the distribution of products as deduced by DEMS analysis suggested that the formation of C1 products, CO2 inclusive, is less significant on Pt3Sn than on Pt. In fact, the higher faradaic current recorded with the former catalyst can be attributed to the greater amounts of acetaldehyde and acetic acid formed. After the EOR, the surface of both Pt and Pt3Sn remained covered by ethanol adsorbates. Whereas C2 fragments were the main adsorbates at the surface of Pt3Sn after the EOR, both C1 and C2 species remained adsorbed at Pt black. AU - Herranz, Tirma AU - Ibáñez, Maria AU - Gómez De La Fuente, José AU - Pérez Alonso, Francisco AU - Peña, Miguel AU - Cabot, Andreu AU - Rojas, Sergio ID - 358 IS - 5 JF - ChemElectroChem TI - In situ study of ethanol electrooxidation on monodispersed Pt inf 3 inf Sn nanoparticles VL - 1 ER - TY - JOUR AB - We introduce algorithms for the computation of homology, cohomology, and related operations on cubical cell complexes, using the technique based on a chain contraction from the original chain complex to a reduced one that represents its homology. This work is based on previous results for simplicial complexes, and uses Serre’s diagonalization for cubical cells. An implementation in C++ of the introduced algorithms is available at http://www.pawelpilarczyk.com/chaincon/ together with some examples. The paper is self-contained as much as possible, and is written at a very elementary level, so that basic knowledge of algebraic topology should be sufficient to follow it. AU - Pawel Pilarczyk AU - Real, Pedro ID - 451 IS - 1 JF - Advances in Computational Mathematics TI - Computation of cubical homology, cohomology, and (co)homological operations via chain contraction VL - 41 ER - TY - JOUR AB - Invasive alien parasites and pathogens are a growing threat to biodiversity worldwide, which can contribute to the extinction of endemic species. On the Galápagos Islands, the invasive parasitic fly Philornis downsi poses a major threat to the endemic avifauna. Here, we investigated the influence of this parasite on the breeding success of two Darwin's finch species, the warbler finch (Certhidea olivacea) and the sympatric small tree finch (Camarhynchus parvulus), on Santa Cruz Island in 2010 and 2012. While the population of the small tree finch appeared to be stable, the warbler finch has experienced a dramatic decline in population size on Santa Cruz Island since 1997. We aimed to identify whether warbler finches are particularly vulnerable during different stages of the breeding cycle. Contrary to our prediction, breeding success was lower in the small tree finch than in the warbler finch. In both species P. downsi had a strong negative impact on breeding success and our data suggest that heavy rain events also lowered the fledging success. On the one hand parents might be less efficient in compensating their chicks' energy loss due to parasitism as they might be less efficient in foraging on days of heavy rain. On the other hand, intense rainfalls might lead to increased humidity and more rapid cooling of the nests. In the case of the warbler finch we found that the control of invasive plant species with herbicides had a significant additive negative impact on the breeding success. It is very likely that the availability of insects (i.e. food abundance) is lower in such controlled areas, as herbicide usage led to the removal of the entire understory. Predation seems to be a minor factor in brood loss. AU - Cimadom, Arno AU - Ulloa, Angel AU - Meidl, Patrick AU - Zöttl, Markus AU - Zöttl, Elisabet AU - Fessl, Birgit AU - Nemeth, Erwin AU - Dvorak, Michael AU - Cunninghame, Francesca AU - Tebbich, Sabine ID - 468 IS - 9 JF - PLoS One TI - Invasive parasites habitat change and heavy rainfall reduce breeding success in Darwin's finches VL - 9 ER - TY - CONF AB - First cycle games (FCG) are played on a finite graph by two players who push a token along the edges until a vertex is repeated, and a simple cycle is formed. The winner is determined by some fixed property Y of the sequence of labels of the edges (or nodes) forming this cycle. These games are traditionally of interest because of their connection with infinite-duration games such as parity and mean-payoff games. We study the memory requirements for winning strategies of FCGs and certain associated infinite duration games. We exhibit a simple FCG that is not memoryless determined (this corrects a mistake in Memoryless determinacy of parity and mean payoff games: a simple proof by Bj⋯orklund, Sandberg, Vorobyov (2004) that claims that FCGs for which Y is closed under cyclic permutations are memoryless determined). We show that θ (n)! memory (where n is the number of nodes in the graph), which is always sufficient, may be necessary to win some FCGs. On the other hand, we identify easy to check conditions on Y (i.e., Y is closed under cyclic permutations, and both Y and its complement are closed under concatenation) that are sufficient to ensure that the corresponding FCGs and their associated infinite duration games are memoryless determined. We demonstrate that many games considered in the literature, such as mean-payoff, parity, energy, etc., satisfy these conditions. On the complexity side, we show (for efficiently computable Y) that while solving FCGs is in PSPACE, solving some families of FCGs is PSPACE-hard. AU - Aminof, Benjamin AU - Rubin, Sasha ID - 475 T2 - Electronic Proceedings in Theoretical Computer Science, EPTCS TI - First cycle games VL - 146 ER - TY - CONF AB - In this paper, we introduce planar matchings on directed pseudo-line arrangements, which yield a planar set of pseudo-line segments such that only matching-partners are adjacent. By translating the planar matching problem into a corresponding stable roommates problem we show that such matchings always exist. Using our new framework, we establish, for the first time, a complete, rigorous definition of weighted straight skeletons, which are based on a so-called wavefront propagation process. We present a generalized and unified approach to treat structural changes in the wavefront that focuses on the restoration of weak planarity by finding planar matchings. AU - Biedl, Therese AU - Huber, Stefan AU - Palfrader, Peter ID - 10892 SN - 0302-9743 T2 - 25th International Symposium, ISAAC 2014 TI - Planar matchings for weighted straight skeletons VL - 8889 ER - TY - JOUR AB - Transgenerational effects are broader than only parental relationships. Despite mounting evidence that multigenerational effects alter phenotypic and life-history traits, our understanding of how they combine to determine fitness is not well developed because of the added complexity necessary to study them. Here, we derive a quantitative genetic model of adaptation to an extraordinary new environment by an additive genetic component, phenotypic plasticity, maternal and grandmaternal effects. We show how, at equilibrium, negative maternal and negative grandmaternal effects maximize expected population mean fitness. We define negative transgenerational effects as those that have a negative effect on trait expression in the subsequent generation, that is, they slow, or potentially reverse, the expected evolutionary dynamic. When maternal effects are positive, negative grandmaternal effects are preferred. As expected under Mendelian inheritance, the grandmaternal effects have a lower impact on fitness than the maternal effects, but this dual inheritance model predicts a more complex relationship between maternal and grandmaternal effects to constrain phenotypic variance and so maximize expected population mean fitness in the offspring. AU - Prizak, Roshan AU - Ezard, Thomas AU - Hoyle, Rebecca ID - 537 IS - 15 JF - Ecology and Evolution TI - Fitness consequences of maternal and grandmaternal effects VL - 4 ER - TY - CONF AB - We consider two-player zero-sum partial-observation stochastic games on graphs. Based on the information available to the players these games can be classified as follows: (a) general partial-observation (both players have partial view of the game); (b) one-sided partial-observation (one player has partial-observation and the other player has complete-observation); and (c) perfect-observation (both players have complete view of the game). The one-sided partial-observation games subsumes the important special case of one-player partial-observation stochastic games (or partial-observation Markov decision processes (POMDPs)). Based on the randomization available for the strategies, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization. We consider all these classes of games with reachability, and parity objectives that can express all ω-regular objectives. The analysis problems are classified into the qualitative analysis that asks for the existence of a strategy that ensures the objective with probability 1; and the quantitative analysis that asks for the existence of a strategy that ensures the objective with probability at least λ (0,1). In this talk we will cover a wide range of results: for perfect-observation games; for POMDPs; for one-sided partial-observation games; and for general partial-observation games. AU - Chatterjee, Krishnendu ID - 1903 IS - PART 1 TI - Partial-observation stochastic reachability and parity games VL - 8634 ER - TY - JOUR AB - In two-player finite-state stochastic games of partial observation on graphs, in every state of the graph, the players simultaneously choose an action, and their joint actions determine a probability distribution over the successor states. The game is played for infinitely many rounds and thus the players construct an infinite path in the graph. We consider reachability objectives where the first player tries to ensure a target state to be visited almost-surely (i.e., with probability 1) or positively (i.e., with positive probability), no matter the strategy of the second player. We classify such games according to the information and to the power of randomization available to the players. On the basis of information, the game can be one-sided with either (a) player 1, or (b) player 2 having partial observation (and the other player has perfect observation), or two-sided with (c) both players having partial observation. On the basis of randomization, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization. Our main results for pure strategies are as follows: (1) For one-sided games with player 2 having perfect observation we show that (in contrast to full randomized strategies) belief-based (subset-construction based) strategies are not sufficient, and we present an exponential upper bound on memory both for almost-sure and positive winning strategies; we show that the problem of deciding the existence of almost-sure and positive winning strategies for player 1 is EXPTIME-complete and present symbolic algorithms that avoid the explicit exponential construction. (2) For one-sided games with player 1 having perfect observation we show that nonelementarymemory is both necessary and sufficient for both almost-sure and positive winning strategies. (3) We show that for the general (two-sided) case finite-memory strategies are sufficient for both positive and almost-sure winning, and at least nonelementary memory is required. We establish the equivalence of the almost-sure winning problems for pure strategies and for randomized strategies with actions invisible. Our equivalence result exhibit serious flaws in previous results of the literature: we show a nonelementary memory lower bound for almost-sure winning whereas an exponential upper bound was previously claimed. AU - Chatterjee, Krishnendu AU - Doyen, Laurent ID - 2211 IS - 2 JF - ACM Transactions on Computational Logic (TOCL) TI - Partial-observation stochastic games: How to win when belief fails VL - 15 ER - TY - JOUR AB - Recently, there has been an effort to add quantitative objectives to formal verification and synthesis. We introduce and investigate the extension of temporal logics with quantitative atomic assertions. At the heart of quantitative objectives lies the accumulation of values along a computation. It is often the accumulated sum, as with energy objectives, or the accumulated average, as with mean-payoff objectives. We investigate the extension of temporal logics with the prefix-accumulation assertions Sum(v) ≥ c and Avg(v) ≥ c, where v is a numeric (or Boolean) variable of the system, c is a constant rational number, and Sum(v) and Avg(v) denote the accumulated sum and average of the values of v from the beginning of the computation up to the current point in time. We also allow the path-accumulation assertions LimInfAvg(v) ≥ c and LimSupAvg(v) ≥ c, referring to the average value along an entire infinite computation. We study the border of decidability for such quantitative extensions of various temporal logics. In particular, we show that extending the fragment of CTL that has only the EX, EF, AX, and AG temporal modalities with both prefix-accumulation assertions, or extending LTL with both path-accumulation assertions, results in temporal logics whose model-checking problem is decidable. Moreover, the prefix-accumulation assertions may be generalized with "controlled accumulation," allowing, for example, to specify constraints on the average waiting time between a request and a grant. On the negative side, we show that this branching-time logic is, in a sense, the maximal logic with one or both of the prefix-accumulation assertions that permits a decidable model-checking procedure. Extending a temporal logic that has the EG or EU modalities, such as CTL or LTL, makes the problem undecidable. AU - Boker, Udi AU - Chatterjee, Krishnendu AU - Henzinger, Thomas A AU - Kupferman, Orna ID - 2038 IS - 4 JF - ACM Transactions on Computational Logic (TOCL) TI - Temporal specifications with accumulative values VL - 15 ER - TY - CONF AB - We study two-player (zero-sum) concurrent mean-payoff games played on a finite-state graph. We focus on the important sub-class of ergodic games where all states are visited infinitely often with probability 1. The algorithmic study of ergodic games was initiated in a seminal work of Hoffman and Karp in 1966, but all basic complexity questions have remained unresolved. Our main results for ergodic games are as follows: We establish (1) an optimal exponential bound on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy); (2) the approximation problem lies in FNP; (3) the approximation problem is at least as hard as the decision problem for simple stochastic games (for which NP ∩ coNP is the long-standing best known bound). We present a variant of the strategy-iteration algorithm by Hoffman and Karp; show that both our algorithm and the classical value-iteration algorithm can approximate the value in exponential time; and identify a subclass where the value-iteration algorithm is a FPTAS. We also show that the exact value can be expressed in the existential theory of the reals, and establish square-root sum hardness for a related class of games. AU - Chatterjee, Krishnendu AU - Ibsen-Jensen, Rasmus ID - 2162 IS - Part 2 TI - The complexity of ergodic mean payoff games VL - 8573 ER - TY - CONF AB - We consider two-player partial-observation stochastic games on finitestate graphs where player 1 has partial observation and player 2 has perfect observation. The winning condition we study are ε-regular conditions specified as parity objectives. The qualitative-analysis problem given a partial-observation stochastic game and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). These qualitative-analysis problems are known to be undecidable. However in many applications the relevant question is the existence of finite-memory strategies, and the qualitative-analysis problems under finite-memory strategies was recently shown to be decidable in 2EXPTIME.We improve the complexity and show that the qualitative-analysis problems for partial-observation stochastic parity games under finite-memory strategies are EXPTIME-complete; and also establish optimal (exponential) memory bounds for finite-memory strategies required for qualitative analysis. AU - Chatterjee, Krishnendu AU - Doyen, Laurent AU - Nain, Sumit AU - Vardi, Moshe ID - 2213 TI - The complexity of partial-observation stochastic parity games with finite-memory strategies VL - 8412 ER - TY - CONF AB - The theory of graph games is the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic processes, we use 2 1/2-player games where some transitions of the game graph are controlled by two adversarial players, the System and the Environment, and the other transitions are determined probabilistically. We consider 2 1/2-player games where the objective of the System is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a mean-payoff condition). We establish that the problem of deciding whether the System can ensure that the probability to satisfy the mean-payoff parity objective is at least a given threshold is in NP ∩ coNP, matching the best known bound in the special case of 2-player games (where all transitions are deterministic). We present an algorithm running in time O(d·n2d·MeanGame) to compute the set of almost-sure winning states from which the objective can be ensured with probability 1, where n is the number of states of the game, d the number of priorities of the parity objective, and MeanGame is the complexity to compute the set of almost-sure winning states in 2 1/2-player mean-payoff games. Our results are useful in the synthesis of stochastic reactive systems with both functional requirement (given as a qualitative objective) and performance requirement (given as a quantitative objective). AU - Chatterjee, Krishnendu AU - Doyen, Laurent AU - Gimbert, Hugo AU - Oualhadj, Youssouf ID - 2212 TI - Perfect-information stochastic mean-payoff parity games VL - 8412 ER - TY - CONF AB - The edit distance between two (untimed) traces is the minimum cost of a sequence of edit operations (insertion, deletion, or substitution) needed to transform one trace to the other. Edit distances have been extensively studied in the untimed setting, and form the basis for approximate matching of sequences in different domains such as coding theory, parsing, and speech recognition. In this paper, we lift the study of edit distances from untimed languages to the timed setting. We define an edit distance between timed words which incorporates both the edit distance between the untimed words and the absolute difference in time stamps. Our edit distance between two timed words is computable in polynomial time. Further, we show that the edit distance between a timed word and a timed language generated by a timed automaton, defined as the edit distance between the word and the closest word in the language, is PSPACE-complete. While computing the edit distance between two timed automata is undecidable, we show that the approximate version, where we decide if the edit distance between two timed automata is either less than a given parameter or more than δ away from the parameter, for δ > 0, can be solved in exponential space and is EXPSPACE-hard. Our definitions and techniques can be generalized to the setting of hybrid systems, and analogous decidability results hold for rectangular automata. AU - Chatterjee, Krishnendu AU - Ibsen-Jensen, Rasmus AU - Majumdar, Ritankar ID - 2216 TI - Edit distance for timed automata ER - TY - GEN AB - Model-based testing is a promising technology for black-box software and hardware testing, in which test cases are generated automatically from high-level specifications. Nowadays, systems typically consist of multiple interacting components and, due to their complexity, testing presents a considerable portion of the effort and cost in the design process. Exploiting the compositional structure of system specifications can considerably reduce the effort in model-based testing. Moreover, inferring properties about the system from testing its individual components allows the designer to reduce the amount of integration testing. In this paper, we study compositional properties of the IOCO-testing theory. We propose a new approach to composition and hiding operations, inspired by contract-based design and interface theories. These operations preserve behaviors that are compatible under composition and hiding, and prune away incompatible ones. The resulting specification characterizes the input sequences for which the unit testing of components is sufficient to infer the correctness of component integration without the need for further tests. We provide a methodology that uses these results to minimize integration testing effort, but also to detect potential weaknesses in specifications. While we focus on asynchronous models and the IOCO conformance relation, the resulting methodology can be applied to a broader class of systems. AU - Daca, Przemyslaw AU - Henzinger, Thomas A AU - Krenn, Willibald AU - Nickovic, Dejan ID - 5411 SN - 2664-1690 TI - Compositional specifications for IOCO testing ER - TY - GEN AB - We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability. We introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation. We present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. AU - Chatterjee, Krishnendu AU - Daca, Przemyslaw AU - Chmelik, Martin ID - 5413 SN - 2664-1690 TI - CEGAR for qualitative analysis of probabilistic systems ER - TY - GEN AB - We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability. We introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation. We present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. AU - Chatterjee, Krishnendu AU - Daca, Przemyslaw AU - Chmelik, Martin ID - 5414 SN - 2664-1690 TI - CEGAR for qualitative analysis of probabilistic systems ER - TY - GEN AB - We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability. We introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph theoretic algorithms with quadratic complexity to compute the simulation relation. We present an automated technique for assume-guarantee style reasoning for compositional analysis of MDPs with qualitative properties by giving a counter-example guided abstraction-refinement approach to compute our new simulation relation. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. AU - Chatterjee, Krishnendu AU - Daca, Przemyslaw AU - Chmelik, Martin ID - 5412 SN - 2664-1690 TI - CEGAR for qualitative analysis of probabilistic systems ER - TY - CONF AB - We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable in general, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. From our results we derive new complexity results for partial-observation stochastic games. AU - Chatterjee, Krishnendu AU - Doyen, Laurent ID - 2163 IS - Part 2 T2 - Lecture Notes in Computer Science TI - Games with a weak adversary VL - 8573 ER - TY - GEN AB - We consider the reachability and shortest path problems on low tree-width graphs, with n nodes, m edges, and tree-width t, on a standard RAM with wordsize W. We use O to hide polynomial factors of the inverse of the Ackermann function. Our main contributions are three fold: 1. For reachability, we present an algorithm that requires O(n·t2·log(n/t)) preprocessing time, O(n·(t·log(n/t))/W) space, and O(t/W) time for pair queries and O((n·t)/W) time for single-source queries. Note that for constant t our algorithm uses O(n·logn) time for preprocessing; and O(n/W) time for single-source queries, which is faster than depth first search/breath first search (after the preprocessing). 2. We present an algorithm for shortest path that requires O(n·t2) preprocessing time, O(n·t) space, and O(t2) time for pair queries and O(n·t) time single-source queries. 3. We give a space versus query time trade-off algorithm for shortest path that, given any constant >0, requires O(n·t2) preprocessing time, O(n·t2) space, and O(n1−·t2) time for pair queries. Our algorithms improve all existing results, and use very simple data structures. AU - Chatterjee, Krishnendu AU - Ibsen-Jensen, Rasmus AU - Pavlogiannis, Andreas ID - 5419 SN - 2664-1690 TI - Improved algorithms for reachability and shortest path on low tree-width graphs ER - TY - CONF AB - As hybrid systems involve continuous behaviors, they should be evaluated by quantitative methods, rather than qualitative methods. In this paper we adapt a quantitative framework, called model measuring, to the hybrid systems domain. The model-measuring problem asks, given a model M and a specification, what is the maximal distance such that all models within that distance from M satisfy (or violate) the specification. A distance function on models is given as part of the input of the problem. Distances, especially related to continuous behaviors are more natural in the hybrid case than the discrete case. We are interested in distances represented by monotonic hybrid automata, a hybrid counterpart of (discrete) weighted automata, whose recognized timed languages are monotone (w.r.t. inclusion) in the values of parameters. The contributions of this paper are twofold. First, we give sufficient conditions under which the model-measuring problem can be solved. Second, we discuss the modeling of distances and applications of the model-measuring problem. AU - Henzinger, Thomas A AU - Otop, Jan ID - 2217 T2 - Proceedings of the 17th international conference on Hybrid systems: computation and control TI - Model measuring for hybrid systems ER - TY - GEN AB - We define the model-measuring problem: given a model M and specification φ, what is the maximal distance ρ such that all models M'within distance ρ from M satisfy (or violate)φ. The model measuring problem presupposes a distance function on models. We concentrate on automatic distance functions, which are defined by weighted automata. The model-measuring problem subsumes several generalizations of the classical model-checking problem, in particular, quantitative model-checking problems that measure the degree of satisfaction of a specification, and robustness problems that measure how much a model can be perturbed without violating the specification. We show that for automatic distance functions, and ω-regular linear-time and branching-time specifications, the model-measuring problem can be solved. We use automata-theoretic model-checking methods for model measuring, replacing the emptiness question for standard word and tree automata by the optimal-weight question for the weighted versions of these automata. We consider weighted automata that accumulate weights by maximizing, summing, discounting, and limit averaging. We give several examples of using the model-measuring problem to compute various notions of robustness and quantitative satisfaction for temporal specifications. AU - Henzinger, Thomas A AU - Otop, Jan ID - 5417 SN - 2664-1690 TI - From model checking to model measuring ER - TY - GEN AB - As hybrid systems involve continuous behaviors, they should be evaluated by quantitative methods, rather than qualitative methods. In this paper we adapt a quantitative framework, called model measuring, to the hybrid systems domain. The model-measuring problem asks, given a model M and a specification, what is the maximal distance such that all models within that distance from M satisfy (or violate) the specification. A distance function on models is given as part of the input of the problem. Distances, especially related to continuous behaviors are more natural in the hybrid case than the discrete case. We are interested in distances represented by monotonic hybrid automata, a hybrid counterpart of (discrete) weighted automata, whose recognized timed languages are monotone (w.r.t. inclusion) in the values of parameters.The contributions of this paper are twofold. First, we give sufficient conditions under which the model-measuring problem can be solved. Second, we discuss the modeling of distances and applications of the model-measuring problem. AU - Henzinger, Thomas A AU - Otop, Jan ID - 5416 SN - 2664-1690 TI - Model measuring for hybrid systems ER - TY - GEN AB - We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. Our results have tight connections with partial-observation stochastic games for which we derive new complexity results. AU - Chatterjee, Krishnendu AU - Doyen, Laurent ID - 5418 SN - 2664-1690 TI - Games with a weak adversary ER - TY - GEN AB - We consider concurrent mean-payoff games, a very well-studied class of two-player (player 1 vs player 2) zero-sum games on finite-state graphs where every transition is assigned a reward between 0 and 1, and the payoff function is the long-run average of the rewards. The value is the maximal expected payoff that player 1 can guarantee against all strategies of player 2. We consider the computation of the set of states with value 1 under finite-memory strategies for player 1, and our main results for the problem are as follows: (1) we present a polynomial-time algorithm; (2) we show that whenever there is a finite-memory strategy, there is a stationary strategy that does not need memory at all; and (3) we present an optimal bound (which is double exponential) on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy). AU - Chatterjee, Krishnendu AU - Ibsen-Jensen, Rasmus ID - 5420 SN - 2664-1690 TI - The value 1 problem for concurrent mean-payoff games ER - TY - GEN AB - Notes from the Third Plenary for the Research Data Alliance in Dublin, Ireland on March 26 to 28, 2014 with focus on starting an institutional research data repository. AU - Porsche, Jana ID - 5422 TI - Notes from Research Data Alliance Plenary Meeting in Dublin, Ireland ER - TY - GEN AB - We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty. AU - Chatterjee, Krishnendu AU - Chmelik, Martin AU - Gupta, Raghav AU - Kanodia, Ayush ID - 5424 SN - 2664-1690 TI - Qualitative analysis of POMDPs with temporal logic specifications for robotics applications ER - TY - GEN AB - We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty. AU - Chatterjee, Krishnendu AU - Chmelik, Martin AU - Gupta, Raghav AU - Kanodia, Ayush ID - 5426 SN - 2664-1690 TI - Qualitative analysis of POMDPs with temporal logic specifications for robotics applications ER - TY - GEN AB - We present a flexible framework for the automated competitive analysis of on-line scheduling algorithms for firm- deadline real-time tasks based on multi-objective graphs: Given a taskset and an on-line scheduling algorithm specified as a labeled transition system, along with some optional safety, liveness, and/or limit-average constraints for the adversary, we automatically compute the competitive ratio of the algorithm w.r.t. a clairvoyant scheduler. We demonstrate the flexibility and power of our approach by comparing the competitive ratio of several on-line algorithms, including D(over), that have been proposed in the past, for various tasksets. Our experimental results reveal that none of these algorithms is universally optimal, in the sense that there are tasksets where other schedulers provide better performance. Our framework is hence a very useful design tool for selecting optimal algorithms for a given application. AU - Chatterjee, Krishnendu AU - Kössler, Alexander AU - Pavlogiannis, Andreas AU - Schmid, Ulrich ID - 5423 SN - 2664-1690 TI - A framework for automated competitive analysis of on-line scheduling of firm-deadline tasks ER - TY - GEN AB - We consider graphs with n nodes together with their tree-decomposition that has b = O ( n ) bags and width t , on the standard RAM computational model with wordsize W = Θ (log n ) . Our contributions are two-fold: Our first contribution is an algorithm that given a graph and its tree-decomposition as input, computes a binary and balanced tree-decomposition of width at most 4 · t + 3 of the graph in O ( b ) time and space, improving a long-standing (from 1992) bound of O ( n · log n ) time for constant treewidth graphs. Our second contribution is on reachability queries for low treewidth graphs. We build on our tree-balancing algorithm and present a data-structure for graph reachability that requires O ( n · t 2 ) preprocessing time, O ( n · t ) space, and O ( d t/ log n e ) time for pair queries, and O ( n · t · log t/ log n ) time for single-source queries. For constant t our data-structure uses O ( n ) time for preprocessing, O (1) time for pair queries, and O ( n/ log n ) time for single-source queries. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries. AU - Chatterjee, Krishnendu AU - Ibsen-Jensen, Rasmus AU - Pavlogiannis, Andreas ID - 5427 SN - 2664-1690 TI - Optimal tree-decomposition balancing and reachability on low treewidth graphs ER - TY - GEN AB - We consider partially observable Markov decision processes (POMDPs) with a set of target states and every transition is associated with an integer cost. The optimization objective we study asks to minimize the expected total cost till the target set is reached, while ensuring that the target set is reached almost-surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost and the bound is double exponential; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst-case running time of our algorithm is double exponential, we also present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples of interest. AU - Anonymous, 1 AU - Anonymous, 2 AU - Anonymous, 3 AU - Anonymous, 4 ID - 5425 SN - 2664-1690 TI - Optimal cost almost-sure reachability in POMDPs ER - TY - GEN AB - Recently there has been a significant effort to add quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, several basic system properties such as average response time cannot be expressed with weighted automata. In this work, we introduce nested weighted automata as a new formalism for expressing important quantitative properties such as average response time. We establish an almost complete decidability picture for the basic decision problems for nested weighted automata, and illustrate its applicability in several domains. AU - Chatterjee, Krishnendu AU - Henzinger, Thomas A AU - Otop, Jan ID - 5415 SN - 2664-1690 TI - Nested weighted automata ER - TY - GEN AB - Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom in the context of evolution. The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are: (1) We show that the qualitative question is NP-complete and the quantitative approximation question is #P-hard in the special case when the interaction and the replacement graphs coincide and even with the restriction that the resident individuals do not reproduce (which corresponds to an invading population taking over an empty structure). (2) We show that in general the qualitative question is PSPACE-complete and the quantitative approximation question is PSPACE-hard and can be solved in exponential time. AU - Chatterjee, Krishnendu AU - Ibsen-Jensen, Rasmus AU - Nowak, Martin ID - 5421 SN - 2664-1690 TI - The complexity of evolution on graphs ER - TY - JOUR AB - We consider homogeneous Bose gas in a large cubic box with periodic boundary conditions, at zero temperature. We analyze its excitation spectrum in a certain kind of a mean-field infinite-volume limit. We prove that under appropriate conditions the excitation spectrum has the form predicted by the Bogoliubov approximation. Our result can be viewed as an extension of the result of Seiringer (Commun. Math. Phys.306:565–578, 2011) to large volumes. AU - Dereziński, Jan AU - Napiórkowski, Marcin M ID - 5813 IS - 12 JF - Annales Henri Poincaré SN - 1424-0637 TI - Excitation spectrum of interacting bosons in the Mean-Field Infinite-Volume limit VL - 15 ER - TY - CONF AB - A discrete spherical geodesic path between two voxels s and t lying on a discrete sphere is a/the 1-connected shortest path from s to t, comprising voxels of the discrete sphere intersected by the real plane passing through s, t, and the center of the sphere. We show that the set of sphere voxels intersected by the aforesaid real plane always contains a 1-connected cycle passing through s and t, and each voxel in this set lies within an isothetic distance of 32 from the concerned plane. Hence, to compute the path, the algorithm starts from s, and iteratively computes each voxel p of the path from the predecessor of p. A novel number-theoretic property and the 48-symmetry of discrete sphere are used for searching the 1-connected voxels comprising the path. The algorithm is output-sensitive, having its time and space complexities both linear in the length of the path. It can be extended for constructing 1-connected discrete 3D circles of arbitrary orientations, specified by a few appropriate input parameters. Experimental results and related analysis demonstrate its efficiency and versatility. AU - Biswas, Ranita AU - Bhowmick, Partha ID - 5810 SN - 0302-9743 TI - On Finding Spherical Geodesic Paths and Circles in ℤ3 VL - 8668 ER - TY - JOUR AB - We demonstrate a many-atom-cavity system with a high-finesse dual-wavelength standing wave cavity in which all participating rubidium atoms are nearly identically coupled to a 780-nm cavity mode. This homogeneous coupling is enforced by a one-dimensional optical lattice formed by the field of a 1560-nm cavity mode. AU - Lee, Jongmin AU - Vrijsen, Geert AU - Teper, Igor AU - Onur Hosten AU - Kasevich, Mark A ID - 589 IS - 13 JF - Optics Letters TI - Many-atom-cavity QED system with homogeneous atom-cavity coupling VL - 39 ER - TY - JOUR AB - Aerobic animals constantly monitor and adapt to changes in O2 levels. The molecular mechanisms involved in sensing O2 are, however, incompletely understood. Previous studies showed that a hexacoordinated globin called GLB-5 tunes the dynamic range of O2-sensing neurons in natural C. elegans isolates, but is defective in the N2 lab reference strain (McGrath et al., 2009; Persson et al., 2009). GLB-5 enables a sharp behavioral switch when O2 changes between 21 and 17%. Here, we show that GLB-5 also confers rapid behavioral and cellular recovery from exposure to hypoxia. Hypoxia reconfigures O2-evoked Ca2+ responses in the URX O2 sensors, and GLB-5 enables rapid recovery of these responses upon re-oxygenation. Forward genetic screens indicate that GLB-5's effects on O2 sensing require PDL-1, the C. elegans ortholog of mammalian PrBP/PDE6δ protein. In mammals, PDE6δ regulates the traffic and activity of prenylated proteins (Zhang et al., 2004; Norton et al., 2005). PDL-1 promotes localization of GCY-33 and GCY-35, atypical soluble guanylate cyclases that act as O2 sensors, to the dendritic endings of URX and BAG neurons, where they colocalize with GLB-5. Both GCY-33 and GCY-35 are predicted to be prenylated. Dendritic localization is not essential for GCY-35 to function as an O2 sensor, but disrupting pdl-1 alters the URX neuron's O2 response properties. Functional GLB-5 can restore dendritic localization of GCY-33 in pdl-1 mutants, suggesting GCY-33 and GLB-5 are in a complex. Our data suggest GLB-5 and the soluble guanylate cyclases operate in close proximity to sculpt O2 responses. AU - Gross, E. AU - Soltesz, Z. AU - Oda, S. AU - Zelmanovich, V. AU - Abergel, Z. AU - de Bono, Mario ID - 6126 IS - 50 JF - Journal of Neuroscience SN - 0270-6474 TI - GLOBIN-5-dependent O2 responses are regulated by PDL-1/PrBP that targets prenylated soluble guanylate cyclases to dendritic endings VL - 34 ER - TY - JOUR AB - Despite the importance of G-protein coupled receptors (GPCRs) their biogenesis is poorly understood. Like vertebrates, C. elegans uses a large family of GPCRs as chemoreceptors. A subset of these receptors, such as ODR-10, requires the odr-4 and odr-8 genes to be appropriately localized to sensory cilia. The odr-4 gene encodes a conserved tail-anchored transmembrane protein; the molecular identity of odr-8 is unknown. Here, we show that odr-8 encodes the C. elegans ortholog of Ufm1-specific protease 2 (UfSP2). UfSPs are cysteine proteases identified biochemically by their ability to liberate the ubiquitin-like modifier Ufm1 from its pro-form and protein conjugates. ODR-8/UfSP2 and ODR-4 are expressed in the same set of twelve chemosensory neurons, and physically interact at the ER membrane. ODR-4 also binds ODR-10, suggesting that an ODR-4/ODR-8 complex promotes GPCR folding, maturation, or export from the ER. The physical interaction between human ODR4 and UfSP2 suggests that this complex's role in GPCR biogenesis may be evolutionarily conserved. Unexpectedly, mutant versions of ODR-8/UfSP2 lacking catalytic residues required for protease activity can rescue all odr-8 mutant phenotypes tested. Moreover, deleting C. elegans ufm-1 does not alter chemoreceptor traffic to cilia, either in wild type or in odr-8 mutants. Thus, UfSP2 proteins have protease- and Ufm1-independent functions in GPCR biogenesis. AU - Chen, Changchun AU - Itakura, Eisuke AU - Weber, Katherine P. AU - Hegde, Ramanujan S. AU - de Bono, Mario ID - 6124 IS - 3 JF - PLoS Genetics SN - 1553-7404 TI - An ER complex of ODR-4 and ODR-8/Ufm1 specific protease 2 promotes GPCR maturation by a Ufm1-independent mechanism VL - 10 ER - TY - JOUR AU - Linneweber, Gerit A. AU - Jacobson, Jake AU - Busch, Karl Emanuel AU - Hudry, Bruno AU - Christov, Christo P. AU - Dormann, Dirk AU - Yuan, Michaela AU - Otani, Tomoki AU - Knust, Elisabeth AU - de Bono, Mario AU - Miguel-Aliaga, Irene ID - 6122 IS - 1-2 JF - Cell SN - 0092-8674 TI - Neuronal control of metabolism through nutrient-dependent modulation of tracheal branching VL - 156 ER - TY - JOUR AB - Nous étudions le comportement asymptotique du nombre de variétés dans une certaine classe ne satisfaisant pas le principe de Hasse. Cette étude repose sur des résultats récemmentobtenus par Colliot-Thélène. AU - Bretèche, Régis de la AU - Browning, Timothy D ID - 6319 IS - 1 JF - Journal de Théorie des Nombres de Bordeaux SN - 1246-7405 TI - Contre-exemples au principe de Hasse pour certains tores coflasques VL - 26 ER - TY - CONF AB - We describe coding techniques that achieve the capacity of a discrete memoryless asymmetric channel. To do so, we discuss how recent advances in coding for symmetric channels yield more efficient solutions also for the asymmetric case. In more detail, we consider three basic approaches. The first one is Gallager's scheme that concatenates a linear code with a non-linear mapper, in order to bias the input distribution. We explicitly show that both polar codes and spatially coupled codes can be employed in this scenario. Further, we derive a scaling law between the gap to capacity, the cardinality of channel input and output alphabets, and the required size of the mapper. The second one is an integrated approach in which the coding scheme is used both for source coding, in order to create codewords with the capacity-achieving distribution, and for channel coding, in order to provide error protection. Such a technique has been recently introduced by Honda and Yamamoto in the context of polar codes, and we show how to apply it also to the design of sparse graph codes. The third approach is based on an idea due to Böcherer and Mathar and separates completely the two tasks of source coding and channel coding by “chaining” together several codewords. We prove that we can combine any suitable source code with any suitable channel code in order to provide optimal schemes for asymmetric channels. In particular, polar codes and spatially coupled codes fulfill the required conditions. AU - Mondelli, Marco AU - Urbanke, Rudiger AU - Hassani, Hamed ID - 6740 T2 - 52nd Annual Allerton Conference on Communication, Control, and Computing TI - How to achieve the capacity of asymmetric channels ER - TY - JOUR AB - We explore the relationship between polar and RM codes and we describe a coding scheme which improves upon the performance of the standard polar code at practical block lengths. Our starting point is the experimental observation that RM codes have a smaller error probability than polar codes under MAP decoding. This motivates us to introduce a family of codes that “interpolates” between RM and polar codes, call this family C inter = {C α : α ∈ [0, 1j}, where C α|α=1 is the original polar code, and C α|α=0 is an RM code. Based on numerical observations, we remark that the error probability under MAP decoding is an increasing function of α. MAP decoding has in general exponential complexity, but empirically the performance of polar codes at finite block lengths is boosted by moving along the family Cinter even under low-complexity decoding schemes such as, for instance, belief propagation or successive cancellation list decoder. We demonstrate the performance gain via numerical simulations for transmission over the erasure channel as well as the Gaussian channel. AU - Mondelli, Marco AU - Hassani, Hamed AU - Urbanke, Rudiger ID - 6739 IS - 9 JF - IEEE Transactions on Communications SN - 0090-6778 TI - From polar to Reed-Muller codes: A technique to improve the finite-length performance VL - 62 ER - TY - JOUR AB - With the aim of extending the coverage and improving the performance of impulse radio ultra-wideband (UWB) systems, this paper focuses on developing a novel single differential encoded decode and forward (DF) non-cooperative relaying scheme (NCR). To favor simple receiver structures, differential noncoherent detection is employed which enables effective energy capture without any channel estimation. Putting emphasis on the general case of multi-hop relaying, we illustrate an original algorithm for the joint power allocation and path selection (JPAPS), minimizing an approximate expression of the overall bit error rate (BER). In particular, after deriving a closed-form power allocation strategy, the optimal path selection is reduced to a shortest path problem on a connected graph, which can be solved without any topology information with complexity O(N 3 ), N being the number of available relays of the network. An approximate scheme is also presented, which reduces the complexity to O(N 2 ) while showing a negligible performance loss, and for benchmarking purposes, an exhaustive-search based multi-hop DF cooperative strategy is derived. Simulation results for various network setups corroborate the effectiveness of the proposed low-complexity JPAPS algorithm, which favorably compares to existing AF and DF relaying methods. AU - Mondelli, Marco AU - Zhou, Qi AU - Lottici, Vincenzo AU - Ma, Xiaoli ID - 6744 IS - 3 JF - IEEE Transactions on Wireless Communications TI - Joint power allocation and path selection for multi-hop noncoherent decode and forward UWB communications VL - 13 ER - TY - CONF AB - Two-player games on graphs provide the theoretical framework for many important problems such as reactive synthesis. While the traditional study of two-player zero-sum games has been extended to multi-player games with several notions of equilibria, they are decidable only for perfect-information games, whereas several applications require imperfect-information games. In this paper we propose a new notion of equilibria, called doomsday equilibria, which is a strategy profile such that all players satisfy their own objective, and if any coalition of players deviates and violates even one of the players objective, then the objective of every player is violated. We present algorithms and complexity results for deciding the existence of doomsday equilibria for various classes of ω-regular objectives, both for imperfect-information games, and for perfect-information games.We provide optimal complexity bounds for imperfect-information games, and in most cases for perfect-information games. AU - Chatterjee, Krishnendu AU - Doyen, Laurent AU - Filiot, Emmanuel AU - Raskin, Jean-François ID - 10885 SN - 0302-9743 T2 - VMCAI 2014: Verification, Model Checking, and Abstract Interpretation TI - Doomsday equilibria for omega-regular games VL - 8318 ER - TY - BOOK AB - This monograph presents a short course in computational geometry and topology. In the first part the book covers Voronoi diagrams and Delaunay triangulations, then it presents the theory of alpha complexes which play a crucial role in biology. The central part of the book is the homology theory and their computation, including the theory of persistence which is indispensable for applications, e.g. shape reconstruction. The target audience comprises researchers and practitioners in mathematics, biology, neuroscience and computer science, but the book may also be beneficial to graduate students of these fields. AU - Edelsbrunner, Herbert ID - 6853 SN - 2191-530X TI - A Short Course in Computational Geometry and Topology ER - TY - GEN AU - Huszár, Kristóf AU - Rolinek, Michal ID - 7038 TI - Playful Math - An introduction to mathematical games ER - TY - JOUR AB - Spin and orbital quantum numbers play a key role in the physics of Mott insulators, but in most systems they are connected only indirectly—via the Pauli exclusion principle and the Coulomb interaction. Iridium-based oxides (iridates) introduce strong spin–orbit coupling directly, such that these numbers become entwined together and the Mott physics attains a strong orbital character. In the layered honeycomb iridates this is thought to generate highly spin–anisotropic magnetic interactions, coupling the spin to a given spatial direction of exchange and leading to strongly frustrated magnetism. Here we report a new iridate structure that has the same local connectivity as the layered honeycomb and exhibits striking evidence for highly spin–anisotropic exchange. The basic structural units of this material suggest that a new family of three-dimensional structures could exist, the ‘harmonic honeycomb’ iridates, of which the present compound is the first example. AU - Modic, Kimberly A AU - Smidt, Tess E. AU - Kimchi, Itamar AU - Breznay, Nicholas P. AU - Biffin, Alun AU - Choi, Sungkyun AU - Johnson, Roger D. AU - Coldea, Radu AU - Watkins-Curry, Pilanda AU - McCandless, Gregory T. AU - Chan, Julia Y. AU - Gandara, Felipe AU - Islam, Z. AU - Vishwanath, Ashvin AU - Shekhter, Arkady AU - McDonald, Ross D. AU - Analytis, James G. ID - 7071 JF - Nature Communications SN - 2041-1723 TI - Realization of a three-dimensional spin–anisotropic harmonic honeycomb iridate VL - 5 ER - TY - JOUR AB - We investigate the structural and magnetic properties of two molecule-based magnets synthesized from the same starting components. Their different structural motifs promote contrasting exchange pathways and consequently lead to markedly different magnetic ground states. Through examination of their structural and magnetic properties we show that [Cu(pyz)(H2O)(gly)2](ClO4)2 may be considered a quasi-one-dimensional quantum Heisenberg antiferromagnet whereas the related compound [Cu(pyz)(gly)](ClO4), which is formed from dimers of antiferromagnetically interacting Cu2+ spins, remains disordered down to at least 0.03 K in zero field but shows a field-temperature phase diagram reminiscent of that seen in materials showing a Bose-Einstein condensation of magnons. AU - Lancaster, T. AU - Goddard, P. A. AU - Blundell, S. J. AU - Foronda, F. R. AU - Ghannadzadeh, S. AU - Möller, J. S. AU - Baker, P. J. AU - Pratt, F. L. AU - Baines, C. AU - Huang, L. AU - Wosnitza, J. AU - McDonald, R. D. AU - Modic, Kimberly A AU - Singleton, J. AU - Topping, C. V. AU - Beale, T. A. W. AU - Xiao, F. AU - Schlueter, J. A. AU - Barton, A. M. AU - Cabrera, R. D. AU - Carreiro, K. E. AU - Tran, H. E. AU - Manson, J. L. ID - 7072 IS - 20 JF - Physical Review Letters SN - 0031-9007 TI - Controlling magnetic order and quantum disorder in molecule-based magnets VL - 112 ER - TY - CHAP AB - The electrolyte in the non-aqueous (aprotic) lithium air battery has a profound influence on the reactions that occur at the anode and cathode, and hence its overall operation on discharge/charge. It must possess a wide range of attributes, exceeding the requirements of electrolytes for Lithium ion batteries by far. The most important additional issues are stability at both anode and cathode in the presence of O2. The known problems with cycling the Li metal/non-aqueous electrolyte interface are further complicated by O2. New and much less understood are the reactions at the O2 cathode/electrolyte interface where the highly reversible formation/decomposition of Li2O2 on discharge/charge is critical for the operation of the non-aqueous lithium air battery. Many aprotic electrolytes exhibit decomposition at the cathode during discharge and charge due to the presence of reactive reduced O2 species affecting potential, capacity and kinetics on discharge and charge, cyclability and calendar life. Identifying suitable electrolytes is one of the key challenges for the non-aqueous lithium air battery at the present time. Following the realisation that cyclability of such cells in the initially used organic carbonate electrolytes is due to back-to-back irreversible reactions the stability of the non-aqueous electrolytes became a major focus of research on rechargeable lithium air batteries. This realisation led to the establishment of a suite of experimental and computational methods capable of screening the stability of electrolytes. These allow for greater mechanistic understanding of the reactivity and guide the way towards designing more stable systems. A range of electrolytes based on ethers, amides, sulfones, ionic liquids and dimethyl sulfoxide have been investigated. All are more stable than the organic carbonates, but not all are equally stable. Even though it was soon realised, by a number of groups, that ethers exhibit side reactions on discharge and charge, they still remain the choice in many studies. To date dimethyl sulfoxide and dimethylacetamide were identified as the most stable electrolytes. In conjunction with the investigation of electrolyte stability the importance of electrode stability became more prominent. The stability of the electrolyte cannot be considered in isolation. Its stability depends on the synergy between electrolyte and electrode. Carbon based electrodes promote electrolyte decomposition and decompose on their own. Although great progress has been made in only a few years, future work on aprotic electrolytes for Li-O2 batteries will need to explore other electrolytes in the quest for yet lower cost, higher safety, stability and low volatility. AU - Freunberger, Stefan Alexander AU - Chen, Yuhui AU - Bardé, Fanny AU - Takechi, Kensuke AU - Mizuno, Fuminori AU - Bruce, Peter G. ED - Imanishi, Nobuyuki ED - Luntz, Alan C. ED - Bruce, Peter ID - 7303 SN - 9781489980618 T2 - The Lithium Air Battery: Fundamentals TI - Nonaqueous Electrolytes ER - TY - JOUR AB - Understanding charge carrier transport in Li2O2, the storage material in the non-aqueous Li-O2 battery, is key to the development of this high-energy battery. Here, we studied ionic transport properties and Li self-diffusion in nanocrystalline Li2O2 by conductivity and temperature variable 7Li NMR spectroscopy. Nanostructured Li2O2, characterized by a mean crystallite size of less than 50 nm as estimated from X-ray diffraction peak broadening, was prepared by high-energy ball milling of microcrystalline lithium peroxide with μm sized crystallites. At room temperature the overall conductivity σ of the microcrystalline reference sample turned out to be very low (3.4 × 10−13 S cm−1) which is in agreement with results from temperature-variable 7Li NMR line shape measurements. Ball-milling, however, leads to an increase of σ by approximately two orders of magnitude (1.1 × 10−10 S cm−1); correspondingly, the activation energy decreases from 0.89 eV to 0.82 eV. The electronic contribution σeon, however, is in the order of 9 × 10−12 S cm−1 which makes less than 10% of the total value. Interestingly, 7Li NMR lines of nano-Li2O2 undergo pronounced heterogeneous motional narrowing which manifests in a two-component line shape emerging with increasing temperatures. Most likely, the enhancement in σ can be traced back to the generation of a spin reservoir with highly mobile Li ions; these are expected to reside in the nearest neighbourhood of defects generated or near the structurally disordered and defect-rich interfacial regions formed during mechanical treatment. AU - Dunst, A. AU - Epp, V. AU - Hanzu, I. AU - Freunberger, Stefan Alexander AU - Wilkening, M. ID - 7302 IS - 8 JF - Energy & Environmental Science SN - 1754-5692 TI - Short-range Li diffusion vs. long-range ionic conduction in nanocrystalline lithium peroxide Li2O2—the discharge product in lithium-air batteries VL - 7 ER - TY - JOUR AB - When lithium–oxygen batteries discharge, O2 is reduced at the cathode to form solid Li2O2. Understanding the fundamental mechanism of O2 reduction in aprotic solvents is therefore essential to realizing their technological potential. Two different models have been proposed for Li2O2 formation, involving either solution or electrode surface routes. Here, we describe a single unified mechanism, which, unlike previous models, can explain O2 reduction across the whole range of solvents and for which the two previous models are limiting cases. We observe that the solvent influences O2 reduction through its effect on the solubility of LiO2, or, more precisely, the free energy of the reaction LiO2* ⇌ Li(sol)+ + O2−(sol) + ion pairs + higher aggregates (clusters). The unified mechanism shows that low-donor-number solvents are likely to lead to premature cell death, and that the future direction of research for lithium–oxygen batteries should focus on the search for new, stable, high-donor-number electrolytes, because they can support higher capacities and can better sustain discharge. AU - Johnson, Lee AU - Li, Chunmei AU - Liu, Zheng AU - Chen, Yuhui AU - Freunberger, Stefan Alexander AU - Ashok, Praveen C. AU - Praveen, Bavishna B. AU - Dholakia, Kishan AU - Tarascon, Jean-Marie AU - Bruce, Peter G. ID - 7305 IS - 12 JF - Nature Chemistry SN - 1755-4330 TI - The role of LiO2 solubility in O2 reduction in aprotic solvents and its consequences for Li–O2 batteries VL - 6 ER - TY - JOUR AB - Lithium-air batteries have received extraordinary attention recently owing to their theoretical gravimetric energies being considerably higher than those of Li-ion batteries. There are, however, significant challenges to practical implementation, including low energy efficiency, cycle life, and power capability. These are due primarily to the lack of fundamental understanding of oxygen reduction and evolution reaction kinetics and parasitic reactions between oxygen redox intermediate species and nominally inactive battery components such as carbon in the oxygen electrode and electrolytes. In this article, we discuss recent advances in the mechanistic understanding of oxygen redox reactions in nonaqueous electrolytes and the search for electrolytes and electrode materials that are chemically stable in the oxygen electrode. In addition, methods to protect lithium metal against corrosion by water and dendrite formation in aqueous lithium-air batteries are discussed. Further materials innovations lie at the heart of research and development efforts that are needed to enable the development of lithium-oxygen batteries with enhanced round-trip efficiency and cycle life. AU - Kwabi, D.G. AU - Ortiz-Vitoriano, N. AU - Freunberger, Stefan Alexander AU - Chen, Y. AU - Imanishi, N. AU - Bruce, P.G. AU - Shao-Horn, Y. ID - 7304 IS - 5 JF - MRS Bulletin SN - 0883-7694 TI - Materials challenges in rechargeable lithium-air batteries VL - 39 ER - TY - JOUR AB - Several problems arise at the O2 (positive) electrode in the Li-air battery, including solvent/electrode decomposition and electrode passivation by insulating Li2O2. Progress partially depends on exploring the basic electrochemistry of O2 reduction. Here we describe the effect of complexing-cations on the electrochemical reduction of O2 in DMSO in the presence and absence of a Li salt. The solubility of alkaline peroxides in DMSO is enhanced by the complexing-cations, consistent with their strong interaction with reduced O2. The complexing-cations also increase the rate of the 1-electron O2 reduction to O2•– by up to six-fold (k° = 2.4 ×10–3 to 1.5 × 10–2 cm s–1) whether or not Li+ ions are present. In the absence of Li+, the complexing-cations also promote the reduction of O2•– to O22–. In the presence of Li+ and complexing-cations, and despite the interaction of the reduced O2 with the latter, SERS confirms that the product is still Li2O2. AU - Li, Chunmei AU - Fontaine, Olivier AU - Freunberger, Stefan Alexander AU - Johnson, Lee AU - Grugeon, Sylvie AU - Laruelle, Stéphane AU - Bruce, Peter G. AU - Armand, Michel ID - 7301 IS - 7 JF - The Journal of Physical Chemistry C SN - 1932-7447 TI - Aprotic Li–O2 battery: Influence of complexing agents on oxygen reduction in an aprotic solvent VL - 118 ER - TY - JOUR AB - Photoinduced electron transfer (PET), which causes pH-dependent quenching of fluorescent dyes, is more effectively introduced by phenolic groups than by amino groups which have been much more commonly used so far. That is demonstrated by fluorescence measurements involving several classes of fluorophores. Electrochemical measurements show that PET in several amino-modified dyes is thermodynamically favorable, even though it was not experimentally found, underlining the importance of kinetic aspects to the process. Consequently, the attachment of phenolic groups allows for fast and simple preparation of a wide selection of fluorescent pH-probes with tailor-made spectral properties, sensitive ranges, and individual advantages, so that a large number of applications can be realized. Fluorophores carrying phenolic groups may also be used for sensing analytes other than pH or molecular switching and signaling. AU - Aigner, Daniel AU - Freunberger, Stefan Alexander AU - Wilkening, Martin AU - Saf, Robert AU - Borisov, Sergey M. AU - Klimant, Ingo ID - 7300 IS - 18 JF - Analytical Chemistry SN - 0003-2700 TI - Enhancing photoinduced electron transfer efficiency of fluorescent pH-probes with halogenated phenols VL - 86 ER - TY - JOUR AB - Bistable switches are fundamental regulatory elements of complex systems, ranging from electronics to living cells. Designed genetic toggle switches have been constructed from pairs of natural transcriptional repressors wired to inhibit one another. The complexity of the engineered regulatory circuits can be increased using orthogonal transcriptional regulators based on designed DNA-binding domains. However, a mutual repressor-based toggle switch comprising DNA-binding domains of transcription-activator-like effectors (TALEs) did not support bistability in mammalian cells. Here, the challenge of engineering a bistable switch based on monomeric DNA-binding domains is solved via the introduction of a positive feedback loop composed of activators based on the same TALE domains as their opposing repressors and competition for the same DNA operator site. This design introduces nonlinearity and results in epigenetic bistability. This principle could be used to employ other monomeric DNA-binding domains such as CRISPR for applications ranging from reprogramming cells to building digital biological memory. AU - Lebar, Tina AU - Bezeljak, Urban AU - Golob, Anja AU - Jerala, Miha AU - Kadunc, Lucija AU - Pirš, Boštjan AU - Stražar, Martin AU - Vučko, Dušan AU - Zupančič, Uroš AU - Benčina, Mojca AU - Forstnerič, Vida AU - Gaber, Rok AU - Lonzarić, Jan AU - Majerle, Andreja AU - Oblak, Alja AU - Smole, Anže AU - Jerala, Roman ID - 7361 IS - 1 JF - Nature Communications SN - 2041-1723 TI - A bistable genetic switch based on designable DNA-binding domains VL - 5 ER - TY - JOUR AB - The reaction between NiO and (0001)- and ([1\bar102])-oriented Al2O3 single crystals has been investigated on model experimental systems by using the ReflEXAFS technique. Depth-sensitive information is obtained by collecting data above and below the critical angle for total reflection. A systematic protocol for data analysis, based on the recently developed CARD code, was implemented, and a detailed description of the reactive systems was obtained. In particular, for ([1\bar102])-oriented Al2O3, the reaction with NiO is almost complete after heating for 6 h at 1273 K, and an almost uniform layer of spinel is found below a mixed (NiO + spinel) layer at the very upmost part of the sample. In the case of the (0001)-oriented Al2O3, for the same temperature and heating time, the reaction shows a lower advancement degree and a residual fraction of at least 30% NiO is detected in the ReflEXAFS spectra. AU - Costanzo, Tommaso AU - Benzi, Federico AU - Ghigna, Paolo AU - Pin, Sonia AU - Spinolo, Giorgio AU - d'Acapito, Francesco ID - 7455 IS - 2 JF - Journal of Synchrotron Radiation SN - 1600-5775 TI - Studying the surface reaction between NiO and Al2O3viatotal reflection EXAFS (ReflEXAFS) VL - 21 ER - TY - JOUR AU - Tan, Shutang AU - Xue, Hong-Wei ID - 7598 IS - 5 JF - Cell Reports SN - 2211-1247 TI - Casein kinase 1 regulates ethylene synthesis by phosphorylating and promoting the turnover of ACS5 VL - 9 ER - TY - CONF AB - Task allocation is a classic distributed problem in which a set of p potentially faulty processes must cooperate to perform a set of tasks. This paper considers a new dynamic version of the problem, in which tasks are injected adversarially during an asynchronous execution. We give the first asynchronous shared-memory algorithm for dynamic task allocation, and we prove that our solution is optimal within logarithmic factors. The main algorithmic idea is a randomized concurrent data structure called a dynamic to-do tree, which allows processes to pick new tasks to perform at random from the set of available tasks, and to insert tasks at random empty locations in the data structure. Our analysis shows that these properties avoid duplicating work unnecessarily. On the other hand, since the adversary controls the input as well the scheduling, it can induce executions where lots of processes contend for a few available tasks, which is inefficient. However, we prove that every algorithm has the same problem: given an arbitrary input, if OPT is the worst-case complexity of the optimal algorithm on that input, then the expected work complexity of our algorithm on the same input is O(OPT log3 m), where m is an upper bound on the number of tasks that are present in the system at any given time. AU - Alistarh, Dan-Adrian AU - Aspnes, James AU - Bender, Michael AU - Gelashvili, Rati AU - Gilbert, Seth ID - 768 TI - Dynamic task allocation in asynchronous shared memory ER - TY - JOUR AB - This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace. We first prove an individual lower bound of ω(k) process steps for deterministic renaming into any namespace of size subexponential in k, where k is the number of participants. The bound is tight: it draws an exponential separation between deterministic and randomized solutions, and implies new tight bounds for deterministic concurrent fetch-and-increment counters, queues, and stacks. The proof is based on a new reduction from renaming to another fundamental problem in distributed computing: mutual exclusion. We complement this individual bound with a global lower bound of ω(klog(k/c)) on the total step complexity of renaming into a namespace of size ck, for any c = 1. This result applies to randomized algorithms against a strong adversary, and helps derive new global lower bounds for randomized approximate counter implementations, that are tight within logarithmic factors. On the algorithmic side, we give a protocol that transforms any sorting network into a randomized strong adaptive renaming algorithm, with expected cost equal to the depth of the sorting network. This gives a tight adaptive renaming algorithm with expected step complexity O(log k), where k is the contention in the current execution. This algorithm is the first to achieve sublinear time, and it is time-optimal as per our randomized lower bound. Finally, we use this renaming protocol to build monotone-consistent counters with logarithmic step complexity and linearizable fetch-and-increment registers with polylogarithmic cost. AU - Alistarh, Dan-Adrian AU - Aspnes, James AU - Censor Hillel, Keren AU - Gilbert, Seth AU - Guerraoui, Rachid ID - 769 IS - 3 JF - Journal of the ACM TI - Tight bounds for asynchronous renaming VL - 61 ER - TY - CONF AB - Dynamic memory reclamation is arguably the biggest open problem in concurrent data structure design: All known solutions induce high overhead, or must be customized to the specific data structure by the programmer, or both. This paper presents StackTrack, the first concurrent memory reclamation scheme that can be applied automatically by a compiler, while maintaining efficiency. StackTrack eliminates most of the expensive bookkeeping required for memory reclamation by leveraging the power of hardware transactional memory (HTM) in a new way: it tracks thread variables dynamically, and in an atomic fashion. This effectively makes all memory references visible without having threads pay the overhead of writing out this information. Our empirical results show that this new approach matches or outperforms prior, non-automated, techniques. AU - Alistarh, Dan-Adrian AU - Eugster, Patrick AU - Herlihy, Maurice AU - Matveev, Alexander AU - Shavit, Nir ID - 770 TI - StackTrack: An automated transactional approach to concurrent memory reclamation ER - TY - CONF AB - We consider the following natural problem: n failure-prone servers, communicating synchronously through message passing, must assign themselves one-to-one to n distinct items. Existing literature suggests two possible approaches to this problem. First, model it as an instance of tight renaming in synchronous message-passing systems; for deterministic solutions, a tight bound of ©(logn) communication rounds is known. Second, model the scenario as an instance of randomized load-balancing, for which elegant sub-logarithmic solutions exist. However, careful examination reveals that known load-balancing schemes do not apply to our scenario, because they either do not tolerate faults or do not ensure one-to-one allocation. It is thus natural to ask if sublogarithmic solutions exist for this apparently simple but intriguing problem. In this paper, we combine the two approaches to provide a new randomized solution for tight renaming, which terminates in O (log log n) communication rounds with high probability, against a strong adaptive adversary. Our solution, called Balls-into-Leaves, combines the deterministic approach with a new randomized scheme to obtain perfectly balanced allocations. The algorithm arranges the items as leaves of a tree, and participants repeatedly perform random choices among the leaves. The algorithm exchanges information in each round to split the participants into progressively smaller groups whose random choices do not conflict. We then extend the algorithm to terminate early in O(log log) rounds w.h.p., where is the actual number of failures. These results imply an exponential separation between deterministic and randomized algorithms for the tight renaming problem in message-passing systems. AU - Alistarh, Dan-Adrian AU - Denysyuk, Oksana AU - Rodrígues, Luís AU - Shavit, Nir ID - 771 TI - Balls-into-Leaves: Sub-logarithmic renaming in synchronous message-passing systems ER - TY - CONF AB - Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. While obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most non-blocking commercial code is only lock-free. This paper suggests a simple solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a general subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst case adversary, in a stochastic model capturing their expected asymptotic behavior. AU - Alistarh, Dan-Adrian AU - Censor Hillel, Keren AU - Shavit, Nir ID - 772 TI - Are lock-free concurrent algorithms practically wait-free? ER - TY - CONF AB - We describe a new randomized consensus protocol with expected message complexity O(n2log2n) when fewer than n/2 processes may fail by crashing. This is an almost-linear improvement over the best previously known protocol, and within logarithmic factors of a known Ω(n2) message lower bound. The protocol further ensures that no process sends more than O(n log3n) messages in expectation, which is again within logarithmic factors of optimal.We also present a generalization of the algorithm to an arbitrary number of failures t, which uses expected O(nt + t2log2t) total messages. Our protocol uses messages of size O(log n), and can therefore scale to large networks. We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary. Our approach is to build a message-efficient, resilient mechanism for aggregating individual processor votes, implementing the message-passing equivalent of a weak shared coin. Roughly, in our protocol, a processor first announces its votes to small groups, then propagates them to increasingly larger groups as it generates more and more votes. To bound the number of messages that an individual process might have to send or receive, the protocol progressively increases the weight of generated votes. The main technical challenge is bounding the impact of votes that are still “in flight” (generated, but not fully propagated) on the final outcome of the shared coin, especially since such votes might have different weights. We achieve this by leveraging the structure of the algorithm, and a technical argument based on martingale concentration bounds. Overall, we show that it is possible to build an efficient message-passing implementation of a shared coin, and in the process (almost-optimally) solve the classic consensus problem in the asynchronous message-passing model. AU - Alistarh, Dan-Adrian AU - Aspnes, James AU - King, Valerie AU - Saia, Jared ED - Kuhn, Fabian ID - 773 TI - Communication-efficient randomized consensus VL - 8784 ER - TY - CONF AB - Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers would prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is in general a complex undertaking, and the resulting algorithms are not always efficient, so most non-blocking commercial code is only lock-free, and the design of efficient wait-free algorithms has been left to the academic community. In [2], we suggest a solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a broad subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. AU - Alistarh, Dan-Adrian AU - Censor Hille, Keren AU - Shavit, Nir ID - 774 TI - Brief announcement: Are lock-free concurrent algorithms practically wait-free? ER - TY - CONF AB - The long-lived renaming problem appears in shared-memory systems where a set of threads need to register and deregister frequently from the computation, while concurrent operations scan the set of currently registered threads. Instances of this problem show up in concurrent implementations of transactional memory, flat combining, thread barriers, and memory reclamation schemes for lock-free data structures. In this paper, we analyze a randomized solution for long-lived renaming. The algorithmic technique we consider, called the Level Array, has previously been used for hashing and one-shot (single-use) renaming. Our main contribution is to prove that, in long-lived executions, where processes may register and deregister polynomially many times, the technique guarantees constant steps on average and O (log log n) steps with high probability for registering, unit cost for deregistering, and O (n) steps for collect queries, where n is an upper bound on the number of processes that may be active at any point in time. We also show that the algorithm has the surprising property that it is self-healing: under reasonable assumptions on the schedule, operations running while the data structure is in a degraded state implicitly help the data structure re-balance itself. This subtle mechanism obviates the need for expensive periodic rebuilding procedures. Our benchmarks validate this approach, showing that, for typical use parameters, the average number of steps a process takes to register is less than two and the worst-case number of steps is bounded by six, even in executions with billions of operations. We contrast this with other randomized implementations, whose worst-case behavior we show to be unreliable, and with deterministic implementations, whose cost is linear in n. AU - Alistarh, Dan-Adrian AU - Kopinsky, Justin AU - Matveev, Alexander AU - Shavit, Nir ID - 775 TI - The levelarray: A fast, practical long-lived renaming algorithm ER - TY - CHAP AB - Experimental studies have demonstrated that environmental variation can create genotype‐environment interactions (GEIs) in the traits involved in sexual selection. Understanding the genetic architecture of phenotype across environments will require statistical tests that can describe both changes in genetic variance and covariance across environments. This chapter outlines the theoretical framework for the processes of sexual selection in the wild, identifying key parameters in wild systems, and highlighting the potential effects of the environment. It describes the proposed approaches for the estimation of these key parameters in a quantitative genetic framework within naturally occurring pedigreed populations. The chapter provides a worked example for a range of analysis methods. It aims to provide an overview of the analytical methods that can be used to model GEIs for traits involved in sexual selection in naturally occurring pedigreed populations. AU - Robinson, Matthew Richard AU - Qvarnström, Anna ED - Hunt, John ED - Hosken, David ID - 7743 SN - 9780470671795 T2 - Genotype-by-Environment Interactions and Sexual Selection TI - Influence of the environment on the genetic architecture of traits involved in sexual selection within wild populations ER - TY - JOUR AU - Robinson, Matthew Richard AU - Wray, Naomi R. AU - Visscher, Peter M. ID - 7744 IS - 4 JF - Trends in Genetics SN - 0168-9525 TI - Explaining additional genetic variation in complex traits VL - 30 ER - TY - JOUR AB - We investigate the vibrational modes of quasi-two-dimensional disordered colloidal packings of hard colloidal spheres with short-range attractions as a function of packing fraction. Certain properties of the vibrational density of states (vDOS) are shown to correlate with the density and structure of the samples (i.e., in sparsely versus densely packed samples). Specifically, a crossover from dense glassy to sparse gel-like states is suggested by an excess of phonon modes at low frequency and by a variation in the slope of the vDOS with frequency at low frequency. This change in phonon mode distribution is demonstrated to arise largely from localized vibrations that involve individual and/or small clusters of particles with few local bonds. Conventional order parameters and void statistics did not exhibit obvious gel-glass signatures as a function of volume fraction. These mode behaviors and accompanying structural insights offer a potentially new set of indicators for identification of glass-gel transitions and for assignment of gel-like versus glass-like character to a disordered solid material. AU - Lohr, Matthew A. AU - Still, Tim AU - Ganti, Raman AU - Gratale, Matthew D. AU - Davidson, Zoey S. AU - Aptowicz, Kevin B. AU - Goodrich, Carl Peter AU - Sussman, Daniel M. AU - Yodh, A. G. ID - 7768 IS - 6 JF - Physical Review E SN - 1539-3755 TI - Vibrational and structural signatures of the crossover between dense glassy and sparse gel-like attractive colloidal packings VL - 90 ER - TY - JOUR AB - In their Letter, Schreck, Bertrand, O'Hern and Shattuck [Phys. Rev. Lett. 107, 078301 (2011)] study nonlinearities in jammed particulate systems that arise when contacts are altered. They conclude that there is "no harmonic regime in the large system limit for all compressions" and "at jamming onset for any system size." Their argument rests on the claim that for finite-range repulsive potentials, of the form used in studies of jamming, the breaking or forming of a single contact is sufficient to destroy the linear regime. We dispute these conclusions and argue that linear response is both justified and essential for understanding the nature of the jammed solid. AU - Goodrich, Carl Peter AU - Liu, Andrea J. AU - Nagel, Sidney R. ID - 7771 IS - 4 JF - Physical Review Letters SN - 0031-9007 TI - Comment on “Repulsive contact interactions make jammed particulate systems inherently nonharmonic” VL - 112 ER - TY - JOUR AB - Particle tracking and displacement covariance matrix techniques are employed to investigate the phonon dispersion relations of two-dimensional colloidal glasses composed of soft, thermoresponsive microgel particles whose temperature-sensitive size permits in situ variation of particle packing fraction. Bulk, B, and shear, G, moduli of the colloidal glasses are extracted from the dispersion relations as a function of packing fraction, and variation of the ratio G/B with packing fraction is found to agree quantitatively with predictions for jammed packings of frictional soft particles. In addition, G and B individually agree with numerical predictions for frictional particles. This remarkable level of agreement enabled us to extract an energy scale for the interparticle interaction from the individual elastic constants and to derive an approximate estimate for the interparticle friction coefficient. AU - Still, Tim AU - Goodrich, Carl Peter AU - Chen, Ke AU - Yunker, Peter J. AU - Schoenholz, Samuel AU - Liu, Andrea J. AU - Yodh, A. G. ID - 7772 IS - 1 JF - Physical Review E SN - 1539-3755 TI - Phonon dispersion and elastic moduli of two-dimensional disordered colloidal packings of soft particles with frictional interactions VL - 89 ER - TY - JOUR AB - For more than a century, physicists have described real solids in terms of perturbations about perfect crystalline order1. Such an approach takes us only so far: a glass, another ubiquitous form of rigid matter, cannot be described in any meaningful sense as a defected crystal2. Is there an opposite extreme to a crystal—a solid with complete disorder—that forms an alternative starting point for understanding real materials? Here, we argue that the solid comprising particles with finite-ranged interactions at the jamming transition3,4,5 constitutes such a limit. It has been shown that the physics associated with this transition can be extended to interactions that are long ranged6. We demonstrate that jamming physics is not restricted to amorphous systems, but dominates the behaviour of solids with surprisingly high order. Just as the free-electron and tight-binding models represent two idealized cases from which to understand electronic structure1, we identify two extreme limits of mechanical behaviour. Thus, the physics of jamming can be set side by side with the physics of crystals to provide an organizing structure for understanding the mechanical properties of solids over the entire spectrum of disorder. AU - Goodrich, Carl Peter AU - Liu, Andrea J. AU - Nagel, Sidney R. ID - 7773 IS - 8 JF - Nature Physics SN - 1745-2473 TI - Solids between the mechanical extremes of order and disorder VL - 10 ER - TY - JOUR AB - Athermal packings of soft repulsive spheres exhibit a sharp jamming transition in the thermodynamic limit. Upon further compression, various structural and mechanical properties display clean power-law behavior over many decades in pressure. As with any phase transition, the rounding of such behavior in finite systems close to the transition plays an important role in understanding the nature of the transition itself. The situation for jamming is surprisingly rich: the assumption that jammed packings are isotropic is only strictly true in the large-size limit, and finite-size has a profound effect on the very meaning of jamming. Here, we provide a comprehensive numerical study of finite-size effects in sphere packings above the jamming transition, focusing on stability as well as the scaling of the contact number and the elastic response. AU - Goodrich, Carl Peter AU - Dagois-Bohy, Simon AU - Tighe, Brian P. AU - van Hecke, Martin AU - Liu, Andrea J. AU - Nagel, Sidney R. ID - 7769 IS - 2 JF - Physical Review E SN - 1539-3755 TI - Jamming in finite systems: Stability, anisotropy, fluctuations, and scaling VL - 90 ER - TY - JOUR AB - Packings of frictionless athermal particles that interact only when they overlap experience a jamming transition as a function of packing density. Such packings provide the foundation for the theory of jamming. This theory rests on the observation that, despite the multitude of disordered configurations, the mechanical response to linear order depends only on the distance to the transition. We investigate the validity and utility of such measurements that invoke the harmonic approximation and show that, despite particles coming in and out of contact, there is a well-defined linear regime in the thermodynamic limit. AU - Goodrich, Carl Peter AU - Liu, Andrea J. AU - Nagel, Sidney R. ID - 7770 IS - 2 JF - Physical Review E SN - 1539-3755 TI - Contact nonlinearities and linear response in jammed particulate packings VL - 90 ER - TY - JOUR AB - Most excitatory inputs in the mammalian brain are made on dendritic spines, rather than on dendritic shafts. Spines compartmentalize calcium, and this biochemical isolation can underlie input-specific synaptic plasticity, providing a raison d'etre for spines. However, recent results indicate that the spine can experience a membrane potential different from that in the parent dendrite, as though the spine neck electrically isolated the spine. Here we use two-photon calcium imaging of mouse neocortical pyramidal neurons to analyze the correlation between the morphologies of spines activated under minimal synaptic stimulation and the excitatory postsynaptic potentials they generate. We find that excitatory postsynaptic potential amplitudes are inversely correlated with spine neck lengths. Furthermore, a spike timing-dependent plasticity protocol, in which two-photon glutamate uncaging over a spine is paired with postsynaptic spikes, produces rapid shrinkage of the spine neck and concomitant increases in the amplitude of the evoked spine potentials. Using numerical simulations, we explore the parameter regimes for the spine neck resistance and synaptic conductance changes necessary to explain our observations. Our data, directly correlating synaptic and morphological plasticity, imply that long-necked spines have small or negligible somatic voltage contributions, but that, upon synaptic stimulation paired with postsynaptic activity, they can shorten their necks and increase synaptic efficacy, thus changing the input/output gain of pyramidal neurons. AU - Araya, R. AU - Vogels, Tim P AU - Yuste, R. ID - 8021 IS - 28 JF - Proceedings of the National Academy of Sciences SN - 0027-8424 TI - Activity-dependent dendritic spine neck changes are correlated with synaptic strength VL - 111 ER - TY - JOUR AB - Uniform random sparse network architectures are ubiquitous in computational neuroscience, but the implicit hypothesis that they are a good representation of real neuronal networks has been met with skepticism. Here we used two experimental data sets, a study of triplet connectivity statistics and a data set measuring neuronal responses to channelrhodopsin stimuli, to evaluate the fidelity of thousands of model networks. Network architectures comprised three neuron types (excitatory, fast spiking, and nonfast spiking inhibitory) and were created from a set of rules that govern the statistics of the resulting connection types. In a high-dimensional parameter scan, we varied the degree distributions (i.e., how many cells each neuron connects with) and the synaptic weight correlations of synapses from or onto the same neuron. These variations converted initially uniform random and homogeneously connected networks, in which every neuron sent and received equal numbers of synapses with equal synaptic strength distributions, to highly heterogeneous networks in which the number of synapses per neuron, as well as average synaptic strength of synapses from or to a neuron were variable. By evaluating the impact of each variable on the network structure and dynamics, and their similarity to the experimental data, we could falsify the uniform random sparse connectivity hypothesis for 7 of 36 connectivity parameters, but we also confirmed the hypothesis in 8 cases. Twenty-one parameters had no substantial impact on the results of the test protocols we used. AU - Tomm, Christian AU - Avermann, Michael AU - Petersen, Carl AU - Gerstner, Wulfram AU - Vogels, Tim P ID - 8023 IS - 8 JF - Journal of Neurophysiology SN - 0022-3077 TI - Connection-type-specific biases make uniform random network models consistent with cortical recordings VL - 112 ER - TY - JOUR AB - Populations of neurons in motor cortex engage in complex transient dynamics of large amplitude during the execution of limb movements. Traditional network models with stochastically assigned synapses cannot reproduce this behavior. Here we introduce a class of cortical architectures with strong and random excitatory recurrence that is stabilized by intricate, fine-tuned inhibition, optimized from a control theory perspective. Such networks transiently amplify specific activity states and can be used to reliably execute multidimensional movement patterns. Similar to the experimental observations, these transients must be preceded by a steady-state initialization phase from which the network relaxes back into the background state by way of complex internal dynamics. In our networks, excitation and inhibition are as tightly balanced as recently reported in experiments across several brain areas, suggesting inhibitory control of complex excitatory recurrence as a generic organizational principle in cortex. AU - Hennequin, Guillaume AU - Vogels, Tim P AU - Gerstner, Wulfram ID - 8022 IS - 6 JF - Neuron SN - 0896-6273 TI - Optimal control of transient dynamics in balanced networks supports generation of complex movements VL - 82 ER - TY - JOUR AB - The assembly of HIV-1 is mediated by oligomerization of the major structural polyprotein, Gag, into a hexameric protein lattice at the plasma membrane of the infected cell. This leads to budding and release of progeny immature virus particles. Subsequent proteolytic cleavage of Gag triggers rearrangement of the particles to form mature infectious virions. Obtaining a structural model of the assembled lattice of Gag within immature virus particles is necessary to understand the interactions that mediate assembly of HIV-1 particles in the infected cell, and to describe the substrate that is subsequently cleaved by the viral protease. An 8-Å resolution structure of an immature virus-like tubular array assembled from a Gag-derived protein of the related retrovirus Mason-Pfizer monkey virus (M-PMV) has previously been reported, and a model for the arrangement of the HIV-1 capsid (CA) domains has been generated based on homology to this structure. Here we have assembled tubular arrays of a HIV-1 Gag-derived protein with an immature-like arrangement of the C-terminal CA domains and have solved their structure by using hybrid cryo-EM and tomography analysis. The structure reveals the arrangement of the C-terminal domain of CA within an immature-like HIV-1 Gag lattice, and provides, to our knowledge, the first high-resolution view of the region immediately downstream of CA, which is essential for assembly, and is significantly different from the respective region in M-PMV. Our results reveal a hollow column of density for this region in HIV-1 that is compatible with the presence of a six-helix bundle at this position. AU - Bharata, Tanmay A AU - Menendez, Luis R AU - Hagena, Wim J AU - Luxd, Vanda AU - Igonete, Sebastien AU - Schorba, Martin AU - Florian Schur AU - Kraüsslich, Hans Georg AU - Briggsa, John A ID - 809 IS - 22 JF - PNAS TI - Cryo electron microscopy of tubular arrays of HIV-1 Gag resolves structures essential for immature virus assembly VL - 111 ER - TY - JOUR AB - Passive immunotherapy with monoclonal antibodies represents a cornerstone of human anticancer therapies, but has not been established in veterinary medicine yet. As the tumor-associated antigen EGFR (ErbB-1) is highly conserved between humans and dogs, and considering the effectiveness of the anti-EGFR antibody cetuximab in human clinical oncology, we present here a “caninized” version of this antibody, can225IgG, for comparative oncology studies. Variable region genes of 225, the murine precursor of cetuximab, were fused with canine constant heavy gamma and kappa chain genes, respectively, and transfected into Chinese hamster ovary (CHO) DUKX-B11 cells. Of note, 480 clones were screened and the best clones were selected according to productivity and highest specificity in EGFR-coated ELISA. Upon purification with Protein G, the recombinant cetuximab-like canine IgG was tested for integrity, correct assembly, and functionality. Specific binding to the surface of EGFR-overexpressing cells was assessed by flow cytometry and immunofluorescence; moreover, binding to canine mammary tissue was demonstrated by immunohistochemistry. In cell viability and proliferation assays, incubation with can225IgG led to significant tumor cell growth inhibition. Moreover, this antibody mediated significant tumor cell killing via phagocytosis in vitro. We thus present here, for the first time, the generation of a canine IgG antibody and its hypothetical structure. On the basis of its cetuximab-like binding site, on the one hand, and the expression of a 91% homologous EGFR molecule in canine cancer, on the other hand, this antibody may be a promising research compound to establish passive immunotherapy in dog patients with cancer. AU - Singer, J. AU - Fazekas, Judit AU - Wang, W. AU - Weichselbaumer, M. AU - Matz, M. AU - Mader, A. AU - Steinfellner, W. AU - Meitz, S. AU - Mechtcheriakova, D. AU - Sobanov, Y. AU - Willmann, M. AU - Stockner, T. AU - Spillner, E. AU - Kunert, R. AU - Jensen-Jarolim, E. ID - 8244 IS - 7 JF - Molecular Cancer Therapeutics SN - 1535-7163 TI - Generation of a canine anti-EGFR (ErbB-1) antibody for passive immunotherapy in dog cancer patients VL - 13 ER - TY - JOUR AB - Nuclear magnetic resonance (NMR) is a powerful tool for observing the motion of biomolecules at the atomic level. One technique, the analysis of relaxation dispersion phenomenon, is highly suited for studying the kinetics and thermodynamics of biological processes. Built on top of the relax computational environment for NMR dynamics is a new dispersion analysis designed to be comprehensive, accurate and easy-to-use. The software supports more models, both numeric and analytic, than current solutions. An automated protocol, available for scripting and driving the graphical user interface (GUI), is designed to simplify the analysis of dispersion data for NMR spectroscopists. Decreases in optimization time are granted by parallelization for running on computer clusters and by skipping an initial grid search by using parameters from one solution as the starting point for another —using analytic model results for the numeric models, taking advantage of model nesting, and using averaged non-clustered results for the clustered analysis. AU - Morin, Sébastien AU - Linnet, Troels E AU - Lescanne, Mathilde AU - Schanda, Paul AU - Thompson, Gary S AU - Tollinger, Martin AU - Teilum, Kaare AU - Gagné, Stéphane AU - Marion, Dominique AU - Griesinger, Christian AU - Blackledge, Martin AU - d’Auvergne, Edward J ID - 8459 IS - 15 JF - Bioinformatics KW - Statistics and Probability KW - Computational Theory and Mathematics KW - Biochemistry KW - Molecular Biology KW - Computational Mathematics KW - Computer Science Applications SN - 1367-4803 TI - Relax: The analysis of biomolecular kinetics and thermodynamics using NMR relaxation dispersion data VL - 30 ER - TY - JOUR AB - The maintenance of bacterial cell shape and integrity is largely attributed to peptidoglycan, a highly cross-linked biopolymer. The transpeptidases that perform this cross-linking are important targets for antibiotics. Despite this biomedical importance, to date no structure of a protein in complex with an intact bacterial peptidoglycan has been resolved, primarily due to the large size and flexibility of peptidoglycan sacculi. Here we use solid-state NMR spectroscopy to derive for the first time an atomic model of an l,d-transpeptidase from Bacillus subtilis bound to its natural substrate, the intact B. subtilis peptidoglycan. Importantly, the model obtained from protein chemical shift perturbation data shows that both domains—the catalytic domain as well as the proposed peptidoglycan recognition domain—are important for the interaction and reveals a novel binding motif that involves residues outside of the classical enzymatic pocket. Experiments on mutants and truncated protein constructs independently confirm the binding site and the implication of both domains. Through measurements of dipolar-coupling derived order parameters of bond motion we show that protein binding reduces the flexibility of peptidoglycan. This first report of an atomic model of a protein–peptidoglycan complex paves the way for the design of new antibiotic drugs targeting l,d-transpeptidases. The strategy developed here can be extended to the study of a large variety of enzymes involved in peptidoglycan morphogenesis. AU - Schanda, Paul AU - Triboulet, Sébastien AU - Laguri, Cédric AU - Bougault, Catherine M. AU - Ayala, Isabel AU - Callon, Morgane AU - Arthur, Michel AU - Simorre, Jean-Pierre ID - 8458 IS - 51 JF - Journal of the American Chemical Society SN - 0002-7863 TI - Atomic model of a cell-wall cross-linking enzyme in complex with an intact bacterial peptidoglycan VL - 136 ER - TY - JOUR AB - The function of proteins depends on their ability to sample a variety of states differing in structure and free energy. Deciphering how the various thermally accessible conformations are connected, and understanding their structures and relative energies is crucial in rationalizing protein function. Many biomolecular reactions take place within microseconds to milliseconds, and this timescale is therefore of central functional importance. Here we show that R1ρ relaxation dispersion experiments in magic‐angle‐spinning solid‐state NMR spectroscopy make it possible to investigate the thermodynamics and kinetics of such exchange process, and gain insight into structural features of short‐lived states. AU - Ma, Peixiang AU - Haller, Jens D. AU - Zajakala, Jérémy AU - Macek, Pavel AU - Sivertsen, Astrid C. AU - Willbold, Dieter AU - Boisbouvier, Jérôme AU - Schanda, Paul ID - 8460 IS - 17 JF - Angewandte Chemie International Edition SN - 1433-7851 TI - Probing transient conformational states of proteins by solid-state R1ρ relaxation-dispersion NMR spectroscopy VL - 53 ER - TY - JOUR AB - In this paper, we study small perturbations of a class of non-convex integrable Hamiltonians with two degrees of freedom, and we prove a result of diffusion for an open and dense set of perturbations, with an optimal time of diffusion which grows linearly with respect to the inverse of the size of the perturbation. AU - Bounemoura, Abed AU - Kaloshin, Vadim ID - 8501 IS - 2 JF - Moscow Mathematical Journal KW - General Mathematics SN - 1609-3321 TI - Generic fast diffusion for a class of non-convex Hamiltonians with two degrees of freedom VL - 14 ER - TY - JOUR AB - The main model studied in this paper is a lattice of pendula with a nearest‐neighbor coupling. If the coupling is weak, then the system is near‐integrable and KAM tori fill most of the phase space. For all KAM trajectories the energy of each pendulum stays within a narrow band for all time. Still, we show that for an arbitrarily weak coupling of a certain localized type, the neighboring pendula can exchange energy. In fact, the energy can be transferred between the pendula in any prescribed way. AU - Kaloshin, Vadim AU - Levi, Mark AU - Saprykina, Maria ID - 8500 IS - 5 JF - Communications on Pure and Applied Mathematics KW - Applied Mathematics KW - General Mathematics SN - 0010-3640 TI - Arnol′d diffusion in a pendulum lattice VL - 67 ER - TY - JOUR AB - Rapid divergence of gene copies after duplication is thought to determine the fate of the copies and evolution of novel protein functions. However, data on howlong the gene copies continue to experience an elevated rate of evolution remain scarce. Standard theory of gene duplications based on some level of genetic redundancy of gene copies predicts that the period of accelerated evolutionmust end relatively quickly. Using a maximum-likelihood approach we estimate preduplication, initial postduplication, and recent postduplication rates of evolution that occurred in themammalian lineage.Wefind that both gene copies experience a similar in magnitude acceleration in their rate of evolution. The copy located in the original genomic position typically returns to the preduplication rates of evolution in a short period of time. The burst of faster evolution of the copy that is located in a new genomic position typically lasts longer. Furthermore, the fast-evolving copies on average continue to evolve faster than the preduplication rates far longer than predicted by standard theory of gene duplications.We hypothesize that the prolonged elevated rates of evolution are determined by functional properties that were acquired during, or soon after, the gene duplication event. AU - Rosello, Oriol P AU - Fyodor Kondrashov ID - 852 IS - 8 JF - Genome Biology and Evolution TI - Long-Term asymmetrical acceleration of protein evolution after gene duplication VL - 6 ER - TY - JOUR AB - The emergence of new genes throughout evolution requires rewiring and extension of regulatory networks. However, the molecular details of how the transcriptional regulation of new gene copies evolves remain largely unexplored. Here we show how duplication of a transcription factor gene allowed the emergence of two independent regulatory circuits. Interestingly, the ancestral transcription factor was promiscuous and could bind different motifs in its target promoters. After duplication, one paralogue evolved increased binding specificity so that it only binds one type of motif, whereas the other copy evolved a decreased activity so that it only activates promoters that contain multiple binding sites. Interestingly, only a few mutations in both the DNA-binding domains and in the promoter binding sites were required to gradually disentangle the two networks. These results reveal how duplication of a promiscuous transcription factor followed by concerted cis and trans mutations allows expansion of a regulatory network. AU - Pougach, Ksenia S AU - Voet, Arnout R AU - Fyodor Kondrashov AU - Voordeckers, Karin AU - Christiaens, Joaquin F AU - Baying, Bianka AU - Bénès, Vladimı́r AU - Sakai, Ryo AU - Aerts, Jan A AU - Zhu, Bo AU - Van Dijck, Patrick AU - Verstrepen, Kevin J ID - 856 JF - Nature Communications TI - Duplication of a promiscuous transcription factor drives the emergence of a new regulatory network VL - 5 ER - TY - JOUR AB - The origins of neural systems remain unresolved. In contrast to other basal metazoans, ctenophores (comb jellies) have both complex nervous and mesoderm-derived muscular systems. These holoplanktonic predators also have sophisticated ciliated locomotion, behaviour and distinct development. Here we present the draft genome of Pleurobrachia bachei, Pacific sea gooseberry, together with ten other ctenophore transcriptomes, and show that they are remarkably distinct from other animal genomes in their content of neurogenic, immune and developmental genes. Our integrative analyses place Ctenophora as the earliest lineage within Metazoa. This hypothesis is supported by comparative analysis of multiple gene families, including the apparent absence of HOX genes, canonical microRNA machinery, and reduced immune complement in ctenophores. Although two distinct nervous systems are well recognized in ctenophores, many bilaterian neuron-specific genes and genes of 'classical' neurotransmitter pathways either are absent or, if present, are not expressed in neurons. Our metabolomic and physiological data are consistent with the hypothesis that ctenophore neural systems, and possibly muscle specification, evolved independently from those in other animals. AU - Moroz, Leonid L AU - Kocot, Kevin M AU - Citarella, Mathew R AU - Dosung, Sohn AU - Norekian, Tigran P AU - Povolotskaya, Inna AU - Grigorenko, Anastasia P AU - Dailey, Christopher A AU - Berezikov, Eugene AU - Buckley, Katherine M AU - Ptitsyn, Andrey A AU - Reshetov, Denis A AU - Mukherjee, Krishanu AU - Moroz, Tatiana P AU - Bobkova, Yelena V AU - Yu, Fahong AU - Kapitonov, Vladimir V AU - Jurka, Jerzy W AU - Bobkov, Yuriy V AU - Swore, Joshua J AU - Girardo, David O AU - Fodor, Alexander AU - Gusev, Fedor E AU - Sanford, Rachel S AU - Bruders, Rebecca AU - Kittler, Ellen L AU - Mills, Claudia E AU - Rast, Jonathan P AU - Derelle, Romain AU - Solovyev, Victor AU - Fyodor Kondrashov AU - Swalla, Billie J AU - Sweedler, Jonathan V AU - Rogaev, Evgeny I AU - Halanych, Kenneth M AU - Kohn, Andrea B ID - 863 IS - 7503 JF - Nature TI - The ctenophore genome and the evolutionary origins of neural systems VL - 510 ER - TY - JOUR AB - Research on existing drugs often discovers novel mechanisms of their action and leads to the expansion of their therapeutic scope and subsequent remarketing. The Wnt signaling pathway is of the immediate therapeutic relevance, as it plays critical roles in cancer development and progression. However, drugs which disrupt this pathway are unavailable despite the high demand. Here we report an attempt to identify antagonists of the Wnt-FZD interaction among the library of the FDA-approved drugs. We performed an in silico screening which brought up several potential antagonists of the ligand-receptor interaction. 14 of these substances were tested using the TopFlash luciferase reporter assay and four of them identified as active and specific inhibitors of the Wnt3a-induced signaling. However, further analysis through GTP-binding and β-catenin stabilization assays showed that the compounds do not target the Wnt-FZD pair, but inhibit the signaling at downstream levels. We further describe the previously unknown inhibitory activity of an anti-leprosy drug clofazimine in the Wnt pathway and provide data demonstrating its efficiency in suppressing growth of Wnt-dependent triple-negative breast cancer cells. These data provide a basis for further investigations of the efficiency of clofazimine in treatment of Wnt-dependent cancers. AU - Koval, Alexey V AU - Vlasov, Peter K AU - Shichkova, Polina AU - Khunderyakova, S AU - Markov, Yury AU - Panchenko, J AU - Volodina, A AU - Fyodor Kondrashov AU - Katanaev, Vladimir L ID - 865 IS - 4 JF - Biochemical Pharmacology TI - Anti leprosy drug clofazimine inhibits growth of triple-negative breast cancer cells via inhibition of canonical Wnt signaling VL - 87 ER - TY - JOUR AB - The morphological stability of biological tubes is crucial for the efficient circulation of fluids and gases. Failure of this stability causes irregularly shaped tubes found in multiple pathological conditions. Here, we report that Drosophila mutants of the ESCRT III component Shrub/Vps32 exhibit a strikingly elongated sinusoidal tube phenotype. This is caused by excessive apical membrane synthesis accompanied by the ectopic accumulation and overactivation of Crumbs in swollen endosomes. Furthermore, we demonstrate that the apical extracellular matrix (aECM) of the tracheal tube is a viscoelastic material coupled with the apical membrane. We present a simple mechanical model in which aECM elasticity, apical membrane growth, and their interaction are three vital parameters determining the stability of biological tubes. Our findings demonstrate a mechanical role for the extracellular matrix and suggest that the interaction of the apical membrane and an elastic aECM determines the final morphology of biological tubes independent of cell shape. AU - Dong, Bo AU - Hannezo, Edouard B AU - Hayashi, Shigeo ID - 925 IS - 4 JF - Cell Reports TI - Balance between apical membrane growth and luminal matrix resistance determines epithelial tubule shape VL - 7 ER - TY - JOUR AB - Morphogenesis during embryo development requires the coordination of mechanical forces to generate the macroscopic shapes of organs. We propose a minimal theoretical model, based on cell adhesion and actomyosin contractility, which describes the various shapes of epithelial cells and the bending and buckling of epithelial sheets, as well as the relative stability of cellular tubes and spheres. We show that, to understand these processes, a full 3D description of the cells is needed, but that simple scaling laws can still be derived. The morphologies observed in vivo can be understood as stable points of mechanical equations and the transitions between them are either continuous or discontinuous. We then focus on epithelial sheet bending, a ubiquitous morphogenetic process. We calculate the curvature of an epithelium as a function of actin belt tension as well as of cell-cell and and cell-substrate tension. The model allows for a comparison of the relative stabilities of spherical or cylindrical cellular structures (acini or tubes). Finally, we propose a unique type of buckling instability of epithelia, driven by a flattening of individual cell shapes, and discuss experimental tests to verify our predictions. AU - Hannezo, Edouard B AU - Prost, Jacques AU - Joanny, Jean ID - 927 IS - 1 JF - PNAS TI - Theory of epithelial sheet morphology in three dimensions VL - 111 ER - TY - JOUR AB - Transposons are selfish genetic sequences that can increase their copy number and inflict substantial damage on their hosts. To combat these genomic parasites, plants have evolved multiple pathways to identify and silence transposons by methylating their DNA. Plants have also evolved mechanisms to limit the collateral damage from the antitransposon machinery. In this review, we examine recent developments that have elucidated many of the molecular workings of these pathways. We also highlight the evidence that the methylation and demethylation pathways interact, indicating that plants have a highly sophisticated, integrated system of transposon defense that has an important role in the regulation of gene expression. AU - Kim, M. Yvonne AU - Zilberman, Daniel ID - 9519 IS - 5 JF - Trends in Plant Science SN - 1360-1385 TI - DNA methylation as a system of plant genomic immunity VL - 19 ER - TY - JOUR AB - Multielectron spin qubits are demonstrated, and performance examined by comparing coherent exchange oscillations in coupled single-electron and multielectron quantum dots, measured in the same device. Fast (>1 GHz) exchange oscillations with a quality factor Q∼15 are found for the multielectron case, compared to Q∼2 for the single-electron case, the latter consistent with experiments in the literature. A model of dephasing that includes voltage and hyperfine noise is developed that is in good agreement with both single- and multielectron data, though in both cases additional exchange-independent dephasing is needed to obtain quantitative agreement across a broad parameter range. AU - Higginbotham, Andrew P AU - Kuemmeth, Ferdinand AU - Hanson, Micah AU - Gossard, Arthur AU - Marcus, Charles ID - 96 IS - 2 JF - APS Physics, Physical Review Letters TI - Coherent operations and screening in multielectron spin qubits VL - 112 ER - TY - JOUR AB - Let d≥3 be a fixed integer. We give an asympotic formula for the expected number of spanning trees in a uniformly random d-regular graph with n vertices. (The asymptotics are as n→∞, restricted to even n if d is odd.) We also obtain the asymptotic distribution of the number of spanning trees in a uniformly random cubic graph, and conjecture that the corresponding result holds for arbitrary (fixed) d. Numerical evidence is presented which supports our conjecture. AU - Greenhill, Catherine AU - Kwan, Matthew Alan AU - Wind, David ID - 9594 IS - 1 JF - The Electronic Journal of Combinatorics TI - On the number of spanning trees in random regular graphs VL - 21 ER - TY - JOUR AB - Correlative microscopy incorporates the specificity of fluorescent protein labeling into high-resolution electron micrographs. Several approaches exist for correlative microscopy, most of which have used the green fluorescent protein (GFP) as the label for light microscopy. Here we use chemical tagging and synthetic fluorophores instead, in order to achieve protein-specific labeling, and to perform multicolor imaging. We show that synthetic fluorophores preserve their post-embedding fluorescence in the presence of uranyl acetate. Post-embedding fluorescence is of such quality that the specimen can be prepared with identical protocols for scanning electron microscopy (SEM) and transmission electron microscopy (TEM); this is particularly valuable when singular or otherwise difficult samples are examined. We show that synthetic fluorophores give bright, well-resolved signals in super-resolution light microscopy, enabling us to superimpose light microscopic images with a precision of up to 25 nm in the x–y plane on electron micrographs. To exemplify the preservation quality of our new method we visualize the molecular arrangement of cadherins in adherens junctions of mouse epithelial cells. AU - Perkovic, Mario AU - Kunz, Michael AU - Endesfelder, Ulrike AU - Bunse, Stefanie AU - Wigge, Christoph AU - Yu, Zhou AU - Hodirnau, Victor-Valentin AU - Scheffer, Margot P. AU - Seybert, Anja AU - Malkusch, Sebastian AU - Schuman, Erin M. AU - Heilemann, Mike AU - Frangakis, Achilleas S. ID - 9655 IS - 2 JF - Journal of Structural Biology SN - 1047-8477 TI - Correlative light- and electron microscopy with chemical tags VL - 186 ER - TY - JOUR AB - It is well known that ultrasonic vibration can soften metals, and this phenomenon has been widely exploited in industrial applications concerning metal forming and bonding. Recent experiments show that the simultaneous application of oscillatory stresses from audible to ultrasonic frequency ranges can lead to not only softening but also significant dislocation annihilation and subgrain formation in metal samples from the nano- to macro-size range. These findings indicate that the existing understanding of ultrasound softening – that the vibrations either impose additional stress waves to augment the quasi-static applied load, or cause heating of the metal, whereas the metal’s intrinsic deformation resistance or mechanism remains unaltered – is far from complete. To understand the softening and the associated enhanced subgrain formation and dislocation annihilation, a new simulator based on the dynamics of dislocation-density functions is employed. This new simulator considers the flux, production and annihilation, as well as the Taylor and elastic interactions between dislocation densities. Softening during vibrations as well as enhanced cell formation is predicted. The simulations reveal the main mechanism for subcell formation under oscillatory loadings to be the enhanced elimination of statistically stored dislocations (SSDs) by the oscillatory stress, leaving behind geometrically necessary dislocations with low Schmid factors which then form the subgrain walls. The oscillatory stress helps the depletion of the SSDs, because the chance for them to meet up and annihilate is increased with reversals of dislocation motions. This is the first simulation effort to successfully predict the cell formation phenomenon under vibratory loadings. AU - Cheng, Bingqing AU - Leung, H.S. AU - Ngan, A.H.W. ID - 9686 IS - 16-18 JF - Philosophical Magazine SN - 1478-6435 TI - Strength of metals under vibrations – dislocation-density-function dynamics simulations VL - 95 ER - TY - JOUR AB - Understanding the effects of sex and migration on adaptation to novel environments remains a key problem in evolutionary biology. Using a single-cell alga Chlamydomonas reinhardtii, we investigated how sex and migration affected rates of evolutionary rescue in a sink environment, and subsequent changes in fitness following evolutionary rescue. We show that sex and migration affect both the rate of evolutionary rescue and subsequent adaptation. However, their combined effects change as the populations adapt to a sink habitat. Both sex and migration independently increased rates of evolutionary rescue, but the effect of sex on subsequent fitness improvements, following initial rescue, changed with migration, as sex was beneficial in the absence of migration but constraining adaptation when combined with migration. These results suggest that sex and migration are beneficial during the initial stages of adaptation, but can become detrimental as the population adapts to its environment. AU - Lagator, Mato AU - Morgan, Andrew AU - Neve, Paul AU - Colegrave, Nick ID - 2083 IS - 8 JF - Evolution TI - Role of sex and migration in adaptation to sink environments VL - 68 ER - TY - GEN AB - Understanding the effects of sex and migration on adaptation to novel environments remains a key problem in evolutionary biology. Using a single-cell alga Chlamydomonas reinhardtii, we investigated how sex and migration affected rates of evolutionary rescue in a sink environment, and subsequent changes in fitness following evolutionary rescue. We show that sex and migration affect both the rate of evolutionary rescue and subsequent adaptation. However, their combined effects change as the populations adapt to a sink habitat. Both sex and migration independently increased rates of evolutionary rescue, but the effect of sex on subsequent fitness improvements, following initial rescue, changed with migration, as sex was beneficial in the absence of migration but constraining adaptation when combined with migration. These results suggest that sex and migration are beneficial during the initial stages of adaptation, but can become detrimental as the population adapts to its environment. AU - Lagator, Mato AU - Morgan, Andrew AU - Neve, Paul AU - Colegrave, Nick ID - 9747 TI - Data from: Role of sex and migration in adaptation to sink environments ER - TY - JOUR AB - We propose a method for detecting many-body localization (MBL) in disordered spin systems. The method involves pulsed coherent spin manipulations that probe the dephasing of a given spin due to its entanglement with a set of distant spins. It allows one to distinguish the MBL phase from a noninteracting localized phase and a delocalized phase. In particular, we show that for a properly chosen pulse sequence the MBL phase exhibits a characteristic power-law decay reflecting its slow growth of entanglement. We find that this power-law decay is robust with respect to thermal and disorder averaging, provide numerical simulations supporting our results, and discuss possible experimental realizations in solid-state and cold-atom systems. AU - Maksym Serbyn AU - Knap, Michael J AU - Gopalakrishnan, Sarang AU - Papić, Zlatko AU - Yao, Norman Y AU - Laumann, Chris R AU - Abanin, Dmitry A AU - Lukin, Mikhail D AU - Demler, Eugene A ID - 977 IS - 14 JF - Physical Review Letters TI - Interferometric probes of many-body localization VL - 113 ER - TY - JOUR AB - Many-body localized (MBL) systems are characterized by the absence of transport and thermalization and, therefore, cannot be described by conventional statistical mechanics. In this paper, using analytic arguments and numerical simulations, we study the behavior of local observables in an isolated MBL system following a quantum quench. For the case of a global quench, we find that the local observables reach stationary, highly nonthermal values at long times as a result of slow dephasing characteristic of the MBL phase. These stationary values retain the local memory of the initial state due to the existence of local integrals of motion in the MBL phase. The temporal fluctuations around stationary values exhibit universal power-law decay in time, with an exponent set by the localization length and the diagonal entropy of the initial state. Such a power-law decay holds for any local observable and is related to the logarithmic in time growth of entanglement in the MBL phase. This behavior distinguishes the MBL phase from both the Anderson insulator (where no stationary state is reached) and from the ergodic phase (where relaxation is expected to be exponential). For the case of a local quench, we also find a power-law approach of local observables to their stationary values when the system is prepared in a mixed state. Quench protocols considered in this paper can be naturally implemented in systems of ultracold atoms in disordered optical lattices, and the behavior of local observables provides a direct experimental signature of many-body localization. AU - Maksym Serbyn AU - Papić, Zlatko AU - Abanin, Dmitry A ID - 980 IS - 17 JF - Physical Review B - Condensed Matter and Materials Physics TI - Quantum quenches in the many-body localized phase VL - 90 ER - TY - JOUR AB - Relaxation and dephasing of hole spins are measured in a gate-defined Ge/Si nanowire double quantum dot using a fast pulsed-gate method and dispersive readout. An inhomogeneous dephasing time T2* ∼ 0.18 μs exceeds corresponding measurements in III-V semiconductors by more than an order of magnitude, as expected for predominately nuclear-spin-free materials. Dephasing is observed to be exponential in time, indicating the presence of a broadband noise source, rather than Gaussian, previously seen in systems with nuclear-spin-dominated dephasing. AU - Higginbotham, Andrew P AU - Larsen, Thorvald AU - Yao, Jun AU - Yan, Hao AU - Lieber, Charles AU - Marcus, Charles AU - Kuemmeth, Ferdinand ID - 98 IS - 6 JF - Nano Letters TI - Hole spin coherence in a Ge/Si heterostructure nanowire VL - 14 ER - TY - JOUR AB - Pathogens may gain a fitness advantage through manipulation of the behaviour of their hosts. Likewise, host behavioural changes can be a defence mechanism, counteracting the impact of pathogens on host fitness. We apply harmonic radar technology to characterize the impact of an emerging pathogen - Nosema ceranae (Microsporidia) - on honeybee (Apis mellifera) flight and orientation performance in the field. Honeybees are the most important commercial pollinators. Emerging diseases have been proposed to play a prominent role in colony decline, partly through sub-lethal behavioural manipulation of their hosts. We found that homing success was significantly reduced in diseased (65.8%) versus healthy foragers (92.5%). Although lost bees had significantly reduced continuous flight times and prolonged resting times, other flight characteristics and navigational abilities showed no significant difference between infected and non-infected bees. Our results suggest that infected bees express normal flight characteristics but are constrained in their homing ability, potentially compromising the colony by reducing its resource inputs, but also counteracting the intra-colony spread of infection. We provide the first high-resolution analysis of sub-lethal effects of an emerging disease on insect flight behaviour. The potential causes and the implications for both host and parasite are discussed. AU - Wolf, Stephan AU - Mcmahon, Dino AU - Lim, Ka AU - Pull, Christopher AU - Clark, Suzanne AU - Paxton, Robert AU - Osborne, Juliet ID - 2086 IS - 8 JF - PLoS One TI - So near and yet so far: Harmonic radar reveals reduced homing ability of Nosema infected honeybees VL - 9 ER -