On the complexity of breaking pseudoentropy - Skórski, Maciej
Pseudoentropy has found a lot of important applications to cryptography and complexity theory. In this paper we focus on the foundational problem that has not been investigated so far, namely by how much pseudoentropy (the amount seen by computationally bounded attackers) diﬀers from its information-theoretic counterpart (seen by unbounded observers), given certain limits on attacker’s computational power? We provide the following answer for HILL pseudoentropy, which exhibits a threshold behavior around the size exponential in the entropy amount:– If the attacker size (s) and advantage () satisfy s (formula presented) where k is the claimed amount of pseudoentropy, then the pseudoentropy boils down to the information-theoretic smooth entropy. – If s (formula presented) then pseudoentropy could be arbitrarily bigger than the information-theoretic smooth entropy. Besides answering the posted question, we show an elegant application of our result to the complexity theory, namely that it implies the clas-sical result on the existence of functions hard to approximate (due to Pippenger). In our approach we utilize non-constructive techniques: the duality of linear programming and the probabilistic method.

Entropic Ricci curvature for discrete spaces - Maas, Jan (Modern Approaches to Discrete Curvature)
We give a short overview on a recently developed notion of Ricci curvature for discrete spaces. This notion relies on geodesic convexity properties of the relative entropy along geodesics in the space of probability densities, for a metric which is similar to (but different from) the 2-Wasserstein metric. The theory can be considered as a discrete counterpart to the theory of Ricci curvature for geodesic measure spaces developed by Lott–Sturm–Villani.

A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds - Skórski, Maciej
In this work we present a short and unified proof for the Strong and Weak Regularity Lemma, based on the cryptographic tech-nique called low-complexity approximations. In short, both problems reduce to a task of finding constructively an approximation for a certain target function under a class of distinguishers (test functions), where dis-tinguishers are combinations of simple rectangle-indicators. In our case these approximations can be learned by a simple iterative procedure, which yields a unified and simple proof, achieving for any graph with density d and any approximation parameter the partition size. The novelty in our proof is: (a) a simple approach which yields both strong and weaker variant, and (b) improvements when d = o(1). At an abstract level, our proof can be seen a refinement and simplification of the “analytic” proof given by Lovasz and Szegedy.

Improved set-based symbolic algorithms for parity games - Chatterjee, Krishnendu; Dvorák, Wolfgang; Henzinger, Monika H; Loitzenbauer, Veronika
Graph games with omega-regular winning conditions provide a mathematical framework to analyze a wide range of problems in the analysis of reactive systems and programs (such as the synthesis of reactive systems, program repair, and the verification of branching time properties). Parity conditions are canonical forms to specify omega-regular winning conditions. Graph games with parity conditions are equivalent to mu-calculus model checking, and thus a very important algorithmic problem. Symbolic algorithms are of great significance because they provide scalable algorithms for the analysis of large finite-state systems, as well as algorithms for the analysis of infinite-state systems with finite quotient. A set-based symbolic algorithm uses the basic set operations and the one-step predecessor operators. We consider graph games with n vertices and parity conditions with c priorities (equivalently, a mu-calculus formula with c alternations of least and greatest fixed points). While many explicit algorithms exist for graph games with parity conditions, for set-based symbolic algorithms there are only two algorithms (notice that we use space to refer to the number of sets stored by a symbolic algorithm): (a) the basic algorithm that requires O(n^c) symbolic operations and linear space; and (b) an improved algorithm that requires O(n^{c/2+1}) symbolic operations but also O(n^{c/2+1}) space (i.e., exponential space). In this work we present two set-based symbolic algorithms for parity games: (a) our first algorithm requires O(n^{c/2+1}) symbolic operations and only requires linear space; and (b) developing on our first algorithm, we present an algorithm that requires O(n^{c/3+1}) symbolic operations and only linear space. We also present the first linear space set-based symbolic algorithm for parity games that requires at most a sub-exponential number of symbolic operations.

Embedding graphs into embedded graphs - Fulek, Radoslav
A (possibly degenerate) drawing of a graph G in the plane is approximable by an embedding if it can be turned into an embedding by an arbitrarily small perturbation. We show that testing, whether a drawing of a planar graph G in the plane is approximable by an embedding, can be carried out in polynomial time, if a desired embedding of G belongs to a fixed isotopy class, i.e., the rotation system (or equivalently the faces) of the embedding of G and the choice of outer face are fixed. In other words, we show that c-planarity with embedded pipes is tractable for graphs with fixed embeddings. To the best of our knowledge an analogous result was previously known essentially only when G is a cycle.

Dynamical self consistency leads to behavioral development and emergent social interactions in robots - Der, Ralf; Martius, Georg S
We present an approach that enables robots to self-organize their sensorimotor behavior from scratch without providing specific information about neither the robot nor its environment. This is achieved by a simple neural control law that increases the consistency between external sensor dynamics and internal neural dynamics of the utterly simple controller. In this way, the embodiment and the agent-environment coupling are the only source of individual development. We show how an anthropomorphic tendon driven arm-shoulder system develops different behaviors depending on that coupling. For instance: Given a bottle half-filled with water, the arm starts to shake it, driven by the physical response of the water. When attaching a brush, the arm can be manipulated into wiping a table, and when connected to a revolvable wheel it finds out how to rotate it. Thus, the robot may be said to discover the affordances of the world. When allowing two (simulated) humanoid robots to interact physically, they engage into a joint behavior development leading to, for instance, spontaneous cooperation. More social effects are observed if the robots can visually perceive each other. Although, as an observer, it is tempting to attribute an apparent intentionality, there is nothing of the kind put in. As a conclusion, we argue that emergent behavior may be much less rooted in explicit intentions, internal motivations, or specific reward systems than is commonly believed.

Fluid dynamics: Water flows out of touch - Hof, Björn (Nature)
Superhydrophobic surfaces reduce the frictional drag between water and solid materials, but this effect is often temporary. The realization of sustained drag reduction has applications for water vehicles and pipeline flows.

Limited heterogeneity of known driver gene mutations among the metastases of individual patients with pancreatic cancer - Makohon Moore, Alvin; Zhang, Ming; Reiter, Johannes; Božić, Ivana; Allen, Benjamin; Kundu, Deepanjan; Chatterjee, Krishnendu; Wong, Fay; Jiao, Yuchen; Kohutek, Zachary; Hong, Jungeui; Attiyeh, Marc; et al. (Nature Genetics)
The extent of heterogeneity among driver gene mutations present in naturally occurring metastases - that is, treatment-naive metastatic disease - is largely unknown. To address this issue, we carried out 60× whole-genome sequencing of 26 metastases from four patients with pancreatic cancer. We found that identical mutations in known driver genes were present in every metastatic lesion for each patient studied. Passenger gene mutations, which do not have known or predicted functional consequences, accounted for all intratumoral heterogeneity. Even with respect to these passenger mutations, our analysis suggests that the genetic similarity among the founding cells of metastases was higher than that expected for any two cells randomly taken from a normal tissue. The uniformity of known driver gene mutations among metastases in the same patient has critical and encouraging implications for the success of future targeted therapies in advanced-stage disease.

Practical graphs for optimal side-channel resistant memory-hard functions - Alwen, Joel F; Blocki, Jeremiah; Harsha, Ben (Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security)
A memory-hard function (MHF) ƒn with parameter n can be computed in sequential time and space n. Simultaneously, a high amortized parallel area-time complexity (aAT) is incurred per evaluation. In practice, MHFs are used to limit the rate at which an adversary (using a custom computational device) can evaluate a security sensitive function that still occasionally needs to be evaluated by honest users (using an off-the-shelf general purpose device). The most prevalent examples of such sensitive functions are Key Derivation Functions (KDFs) and password hashing algorithms where rate limits help mitigate off-line dictionary attacks. As the honest users' inputs to these functions are often (low-entropy) passwords special attention is given to a class of side-channel resistant MHFs called iMHFs. Essentially all iMHFs can be viewed as some mode of operation (making n calls to some round function) given by a directed acyclic graph (DAG) with very low indegree. Recently, a combinatorial property of a DAG has been identified (called "depth-robustness") which results in good provable security for an iMHF based on that DAG. Depth-robust DAGs have also proven useful in other cryptographic applications. Unfortunately, up till now, all known very depth-robust DAGs are impractically complicated and little is known about their exact (i.e. non-asymptotic) depth-robustness both in theory and in practice. In this work we build and analyze (both formally and empirically) several exceedingly simple and efficient to navigate practical DAGs for use in iMHFs and other applications. For each DAG we: *Prove that their depth-robustness is asymptotically maximal. *Prove bounds of at least 3 orders of magnitude better on their exact depth-robustness compared to known bounds for other practical iMHF. *Implement and empirically evaluate their depth-robustness and aAT against a variety of state-of-the art (and several new) depth-reduction and low aAT attacks. We find that, against all attacks, the new DAGs perform significantly better in practice than Argon2i, the most widely deployed iMHF in practice. Along the way we also improve the best known empirical attacks on the aAT of Argon2i by implementing and testing several heuristic versions of a (hitherto purely theoretical) depth-reduction attack. Finally, we demonstrate practicality of our constructions by modifying the Argon2i code base to use one of the new high aAT DAGs. Experimental benchmarks on a standard off-the-shelf CPU show that the new modifications do not adversely affect the impressive throughput of Argon2i (despite seemingly enjoying significantly higher aAT).

Creating to understand – developmental biology meets engineering in Paris - Kicheva, Anna; Rivron, Nicolas (Development)
In November 2016, developmental biologists, synthetic biologists and engineers gathered in Paris for a meeting called ‘Engineering the embryo’. The participants shared an interest in exploring how synthetic systems can reveal new principles of embryonic development, and how the in vitro manipulation and modeling of development using stem cells can be used to integrate ideas and expertise from physics, developmental biology and tissue engineering. As we review here, the conference pinpointed some of the challenges arising at the intersection of these fields, along with great enthusiasm for finding new approaches and collaborations.

On the complexity of estimating Rènyi divergences - Skórski, Maciej (2017 IEEE International Symposium on Information Theory (ISIT))
This paper studies the complexity of estimating Rényi divergences of discrete distributions: p observed from samples and the baseline distribution q known a priori. Extending the results of Acharya et al. (SODA'15) on estimating Rényi entropy, we present improved estimation techniques together with upper and lower bounds on the sample complexity. We show that, contrarily to estimating Rényi entropy where a sublinear (in the alphabet size) number of samples suffices, the sample complexity is heavily dependent on events occurring unlikely in q, and is unbounded in general (no matter what an estimation technique is used). For any divergence of integer order bigger than 1, we provide upper and lower bounds on the number of samples dependent on probabilities of p and q (the lower bounds hold for non-integer orders as well). We conclude that the worst-case sample complexity is polynomial in the alphabet size if and only if the probabilities of q are non-negligible. This gives theoretical insights into heuristics used in the applied literature to handle numerical instability, which occurs for small probabilities of q. Our result shows that they should be handled with care not only because of numerical issues, but also because of a blow up in the sample complexity.

Bacterial flagella grow through an injection diffusion mechanism - Renault, Thibaud; Abraham, Anthony; Bergmiller, Tobias; Paradis, Guillaume; Rainville, Simon; Charpentier, Emmanuelle; Guet, Calin C; Tu, Yuhai; Namba, Keiichi; Keener, James; Minamino, Tohru; Erhardt, Marc (eLife)
The bacterial flagellum is a self-assembling nanomachine. The external flagellar filament, several times longer than a bacterial cell body, is made of a few tens of thousands subunits of a single protein: flagellin. A fundamental problem concerns the molecular mechanism of how the flagellum grows outside the cell, where no discernible energy source is available. Here, we monitored the dynamic assembly of individual flagella using in situ labelling and real-time immunostaining of elongating flagellar filaments. We report that the rate of flagellum growth, initially ~1,700 amino acids per second, decreases with length and that the previously proposed chain mechanism does not contribute to the filament elongation dynamics. Inhibition of the proton motive force-dependent export apparatus revealed a major contribution of substrate injection in driving filament elongation. The combination of experimental and mathematical evidence demonstrates that a simple, injection-diffusion mechanism controls bacterial flagella growth outside the cell.

Auxin response cell autonomously controls ground tissue initiation in the early arabidopsis embryo - Möller, Barbara; Ten Hove, Colette; Xiang, Daoquan; Williams, Nerys; López, Lorena; Yoshida, Saiko; Smit, Margot; Datla, Raju; Weijers, Dolf (PNAS)
Plant organs are typically organized into three main tissue layers. The middle ground tissue layer comprises the majority of the plant body and serves a wide range of functions, including photosynthesis, selective nutrient uptake and storage, and gravity sensing. Ground tissue patterning and maintenance in Arabidopsis are controlled by a well-established gene network revolving around the key regulator SHORT-ROOT (SHR). In contrast, it is completely unknown how ground tissue identity is first specified from totipotent precursor cells in the embryo. The plant signaling molecule auxin, acting through AUXIN RESPONSE FACTOR (ARF) transcription factors, is critical for embryo patterning. The auxin effector ARF5/MONOPTEROS (MP) acts both cell-autonomously and noncell-autonomously to control embryonic vascular tissue formation and root initiation, respectively. Here we show that auxin response and ARF activity cell-autonomously control the asymmetric division of the first ground tissue cells. By identifying embryonic target genes, we show that MP transcriptionally initiates the ground tissue lineage and acts upstream of the regulatory network that controls ground tissue patterning and maintenance. Strikingly, whereas the SHR network depends on MP, this MP function is, at least in part, SHR independent. Our study therefore identifies auxin response as a regulator of ground tissue specification in the embryonic root, and reveals that ground tissue initiation and maintenance use different regulators and mechanisms. Moreover, our data provide a framework for the simultaneous formation of multiple cell types by the same transcriptional regulator.

Modeling Alzheimer's disease in mice with human neurons - Novarino, Gaia (Science Translational Medicine)
Human neurons transplanted into a mouse model for Alzheimer’s disease show human-specific vulnerability to β-amyloid plaques and may help to identify new therapeutic targets.

Self organized behavior generation for musculoskeletal robots - Der, Ralf; Martius, Georg S (Frontiers in Neurorobotics)
With the accelerated development of robot technologies, control becomes one of the central themes of research. In traditional approaches, the controller, by its internal functionality, finds appropriate actions on the basis of specific objectives for the task at hand. While very successful in many applications, self-organized control schemes seem to be favored in large complex systems with unknown dynamics or which are difficult to model. Reasons are the expected scalability, robustness, and resilience of self-organizing systems. The paper presents a self-learning neurocontroller based on extrinsic differential plasticity introduced recently, applying it to an anthropomorphic musculoskeletal robot arm with attached objects of unknown physical dynamics. The central finding of the paper is the following effect: by the mere feedback through the internal dynamics of the object, the robot is learning to relate each of the objects with a very specific sensorimotor pattern. Specifically, an attached pendulum pilots the arm into a circular motion, a half-filled bottle produces axis oriented shaking behavior, a wheel is getting rotated, and wiping patterns emerge automatically in a table-plus-brush setting. By these object-specific dynamical patterns, the robot may be said to recognize the object's identity, or in other words, it discovers dynamical affordances of objects. Furthermore, when including hand coordinates obtained from a camera, a dedicated hand-eye coordination self-organizes spontaneously. These phenomena are discussed from a specific dynamical system perspective. Central is the dedicated working regime at the border to instability with its potentially infinite reservoir of (limit cycle) attractors "waiting" to be excited. Besides converging toward one of these attractors, variate behavior is also arising from a self-induced attractor morphing driven by the learning rule. We claim that experimental investigations with this anthropomorphic, self-learning robot not only generate interesting and potentially useful behaviors, but may also help to better understand what subjective human muscle feelings are, how they can be rooted in sensorimotor patterns, and how these concepts may feed back on robotics.

FMNL formins boost lamellipodial force generation - Kage, Frieda; Winterhoff, Moritz; Dimchev, Vanessa; Müller, Jan; Thalheim, Tobias; Freise, Anika; Brühmann, Stefan; Kollasser, Jana; Block, Jennifer; Dimchev, Georgi A; Geyer, Matthias; Schnittler, Hams; et al. (Nature Communications)
Migration frequently involves Rac-mediated protrusion of lamellipodia, formed by Arp2/3 complex-dependent branching thought to be crucial for force generation and stability of these networks. The formins FMNL2 and FMNL3 are Cdc42 effectors targeting to the lamellipodium tip and shown here to nucleate and elongate actin filaments with complementary activities in vitro. In migrating B16-F1 melanoma cells, both formins contribute to the velocity of lamellipodium protrusion. Loss of FMNL2/3 function in melanoma cells and fibroblasts reduces lamellipodial width, actin filament density and -bundling, without changing patterns of Arp2/3 complex incorporation. Strikingly, in melanoma cells, FMNL2/3 gene inactivation almost completely abolishes protrusion forces exerted by lamellipodia and modifies their ultrastructural organization. Consistently, CRISPR/Cas-mediated depletion of FMNL2/3 in fibroblasts reduces both migration and capability of cells to move against viscous media. Together, we conclude that force generation in lamellipodia strongly depends on FMNL formin activity, operating in addition to Arp2/3 complex-dependent filament branching.

Steady state EB cap size fluctuations are determined by stochastic microtubule growth and maturation - Rickman, Jamie; Düllberg, Christian F; Cade, Nicholas; Griffin, Lewis; Surrey, Thomas (PNAS)
Growing microtubules are protected from depolymerization by the presence of a GTP or GDP/Pi cap. End-binding proteins of the EB1 family bind to the stabilizing cap, allowing monitoring of its size in real time. The cap size has been shown to correlate with instantaneous microtubule stability. Here we have quantitatively characterized the properties of cap size fluctuations during steadystate growth and have developed a theory predicting their timescale and amplitude from the kinetics of microtubule growth and cap maturation. In contrast to growth speed fluctuations, cap size fluctuations show a characteristic timescale, which is defined by the lifetime of the cap sites. Growth fluctuations affect the amplitude of cap size fluctuations; however, cap size does not affect growth speed, indicating that microtubules are far from instability during most of their time of growth. Our theory provides the basis for a quantitative understanding of microtubule stability fluctuations during steady-state growth.

Hydrodynamic turbulence in quasi Keplerian rotating flows - Shi, Liang; Hof, Björn; Rampp, Markus; Avila, Marc (Physics of Fluids)
We report a direct-numerical-simulation study of the Taylor-Couette flow in the quasi-Keplerian regime at shear Reynolds numbers up to (105). Quasi-Keplerian rotating flow has been investigated for decades as a simplified model system to study the origin of turbulence in accretion disks that is not fully understood. The flow in this study is axially periodic and thus the experimental end-wall effects on the stability of the flow are avoided. Using optimal linear perturbations as initial conditions, our simulations find no sustained turbulence: the strong initial perturbations distort the velocity profile and trigger turbulence that eventually decays.

Safety verification of nonlinear hybrid systems based on invariant clusters - Kong, Hui; Bogomolov, Sergiy; Schilling, Christian; Jiang, Yu; Henzinger, Thomas A (Proceedings of the 20th International Conference on Hybrid Systems)
In this paper, we propose an approach to automatically compute invariant clusters for nonlinear semialgebraic hybrid systems. An invariant cluster for an ordinary differential equation (ODE) is a multivariate polynomial invariant g(u→, x→) = 0, parametric in u→, which can yield an infinite number of concrete invariants by assigning different values to u→ so that every trajectory of the system can be overapproximated precisely by the intersection of a group of concrete invariants. For semialgebraic systems, which involve ODEs with multivariate polynomial right-hand sides, given a template multivariate polynomial g(u→, x→), an invariant cluster can be obtained by first computing the remainder of the Lie derivative of g(u→, x→) divided by g(u→, x→) and then solving the system of polynomial equations obtained from the coefficients of the remainder. Based on invariant clusters and sum-of-squares (SOS) programming, we present a new method for the safety verification of hybrid systems. Experiments on nonlinear benchmark systems from biology and control theory show that our approach is efficient.

The antisocial side of antibiotics - Novarino, Gaia (Science Translational Medicine)
Perinatal exposure to penicillin may result in longlasting gut and behavioral changes.

Multiple roles of filopodial dynamics in particle capture and phagocytosis and phenotypes of Cdc42 and Myo10 deletion - Horsthemke, Markus; Bachg, Anne; Groll, Katharina; Moyzio, Sven; Müther, Barbara; Hemkemeyer, Sandra; Wedlich Söldner, Roland; Sixt, Michael K; Tacke, Sebastian; Bähler, Martin; Hanley, Peter (Journal of Biological Chemistry)
Macrophage filopodia, finger-like membrane protrusions, were first implicated in phagocytosis more than 100 years ago, but little is still known about the involvement of these actin-dependent structures in particle clearance. Using spinning disk confocal microscopy to image filopodial dynamics in mouse resident Lifeact-EGFP macrophages, we show that filopodia, or filopodia-like structures, support pathogen clearance by multiple means. Filopodia supported the phagocytic uptake of bacterial (Escherichia coli) particles by (i) capturing along the filopodial shaft and surfing toward the cell body, the most common mode of capture; (ii) capturing via the tip followed by retraction; (iii) combinations of surfing and retraction; or (iv) sweeping actions. In addition, filopodia supported the uptake of zymosan (Saccharomyces cerevisiae) particles by (i) providing fixation, (ii) capturing at the tip and filopodia-guided actin anterograde flow with phagocytic cup formation, and (iii) the rapid growth of new protrusions. To explore the role of filopodia-inducing Cdc42, we generated myeloid-restricted Cdc42 knock-out mice. Cdc42-deficient macrophages exhibited rapid phagocytic cup kinetics, but reduced particle clearance, which could be explained by the marked rounded-up morphology of these cells. Macrophages lacking Myo10, thought to act downstream of Cdc42, had normal morphology, motility, and phagocytic cup formation, but displayed markedly reduced filopodia formation. In conclusion, live-cell imaging revealed multiple mechanisms involving macrophage filopodia in particle capture and engulfment. Cdc42 is not critical for filopodia or phagocytic cup formation, but plays a key role in driving macrophage lamellipodial spreading.

EXO70C2 is a key regulatory factor for optimal tip growth of pollen - Synek, Lukáš; Vukašinović, Nemanja; Kulich, Ivan; Hála, Michal; Aldorfová, Klára; Fendrych, Matyas; Žárský, Viktor (Plant Physiology)
The exocyst, a eukaryotic tethering complex, coregulates targeted exocytosis as an effector of small GTPases in polarized cell growth. In land plants, several exocyst subunits are encoded by double or triple paralogs, culminating in tens of EXO70 paralogs. Out of 23 Arabidopsis thaliana EXO70 isoforms, we analyzed seven isoforms expressed in pollen. Genetic and microscopic analyses of single mutants in EXO70A2, EXO70C1, EXO70C2, EXO70F1, EXO70H3, EXO70H5, and EXO70H6 genes revealed that only a loss-of-function EXO70C2 allele resulted in a significant male-specific transmission defect (segregation 40%:51%:9%) due to aberrant pollen tube growth. Mutant pollen tubes grown in vitro exhibited an enhanced growth rate and a decreased thickness of the tip cell wall, causing tip bursts. However, exo70C2 pollen tubes could frequently recover and restart their speedy elongation, resulting in a repetitive stop-and-go growth dynamics. A pollenspecific depletion of the closest paralog, EXO70C1, using artificial microRNA in the exo70C2 mutant background, resulted in a complete pollen-specific transmission defect, suggesting redundant functions of EXO70C1 and EXO70C2. Both EXO70C1 and EXO70C2, GFP tagged and expressed under the control of their native promoters, localized in the cytoplasm of pollen grains, pollen tubes, and also root trichoblast cells. The expression of EXO70C2-GFP complemented the aberrant growth of exo70C2 pollen tubes. The absent EXO70C2 interactions with core exocyst subunits in the yeast two-hybrid assay, cytoplasmic localization, and genetic effect suggest an unconventional EXO70 function possibly as a regulator of exocytosis outside the exocyst complex. In conclusion, EXO70C2 is a novel factor contributing to the regulation of optimal tip growth of Arabidopsis pollen tubes.

Partitioned list decoding of polar codes: Analysis and improvement of finite length performance - Hashemi, Seyyed Ali; Mondelli, Marco; Hassani, Hamed; Urbanke, Ruediger; Gross, Warren (2017 IEEE Global Communications Conference)
Polar codes represent one of the major recent breakthroughs in coding theory and, because of their attractive features, they have been selected for the incoming 5G standard. As such, a lot of attention has been devoted to the development of decoding algorithms with good error performance and efficient hardware implementation. One of the leading candidates in this regard is represented by successive-cancellation list (SCL) decoding. However, its hardware implementation requires a large amount of memory. Recently, a partitioned SCL (PSCL) decoder has been proposed to significantly reduce the memory consumption [1]. In this paper, we examine the paradigm of PSCL decoding from both theoretical and practical standpoints: (i) by changing the construction of the code, we are able to improve the performance at no additional computational, latency or memory cost, (ii) we present an optimal scheme to allocate cyclic redundancy checks (CRCs), and (iii) we provide an upper bound on the list size that allows MAP performance.

Memory-n strategies of direct reciprocity - Hilbe, Christian; Martinez, Vaquero; Chatterjee, Krishnendu; Nowak, Martin (PNAS)
Humans routinely use conditionally cooperative strategies when interacting in repeated social dilemmas. They are more likely to cooperate if others cooperated before, and are ready to retaliate if others defected. To capture the emergence of reciprocity, most previous models consider subjects who can only choose from a restricted set of representative strategies, or who react to the outcome of the very last round only. As players memorize more rounds, the dimension of the strategy space increases exponentially. This increasing computational complexity renders simulations for individuals with higher cognitive abilities infeasible, especially if multiplayer interactions are taken into account. Here, we take an axiomatic approach instead. We propose several properties that a robust cooperative strategy for a repeated multiplayer dilemma should have. These properties naturally lead to a unique class of cooperative strategies, which contains the classical Win-Stay Lose-Shift rule as a special case. A comprehensive numerical analysis for the prisoner's dilemma and for the public goods game suggests that strategies of this class readily evolve across various memory-n spaces. Our results reveal that successful strategies depend not only on how cooperative others were in the past but also on the respective context of cooperation.

Interactive paper tearing - Schreck, Camille; Rohmer, Damien; Hahmann, Stefanie (Computer Graphics Forum)
We propose an efficient method to model paper tearing in the context of interactive modeling. The method uses geometrical information to automatically detect potential starting points of tears. We further introduce a new hybrid geometrical and physical-based method to compute the trajectory of tears while procedurally synthesizing high resolution details of the tearing path using a texture based approach. The results obtained are compared with real paper and with previous studies on the expected geometric paths of paper that tears.

Locally triggered release of the chemokine CCL21 promotes dendritic cell transmigration across lymphatic endothelia - Vaahtomeri, Kari; Brown, Markus; Hauschild, Robert; De Vries, Ingrid; Leithner, Alexander F; Mehling, Matthias; Kaufmann, Walter; Sixt, Michael K (Cell Reports)
Trafficking cells frequently transmigrate through epithelial and endothelial monolayers. How monolayers cooperate with the penetrating cells to support their transit is poorly understood. We studied dendritic cell (DC) entry into lymphatic capillaries as a model system for transendothelial migration. We find that the chemokine CCL21, which is the decisive guidance cue for intravasation, mainly localizes in the trans-Golgi network and intracellular vesicles of lymphatic endothelial cells. Upon DC transmigration, these Golgi deposits disperse and CCL21 becomes extracellularly enriched at the sites of endothelial cell-cell junctions. When we reconstitute the transmigration process in vitro, we find that secretion of CCL21-positive vesicles is triggered by a DC contact-induced calcium signal, and selective calcium chelation in lymphatic endothelium attenuates transmigration. Altogether, our data demonstrate a chemokine-mediated feedback between DCs and lymphatic endothelium, which facilitates transendothelial migration.

Construction of polar codes with sublinear complexity - Mondelli, Marco; Hassani, S. Hamed; Urbanke, Rudiger (2017 IEEE International Symposium on Information Theory)
Consider the problem of constructing a polar code of block length N for the transmission over a given channel W. Typically this requires to compute the reliability of all the N synthetic channels and then to include those that are sufficiently reliable. However, we know from [1], [2] that there is a partial order among the synthetic channels. Hence, it is natural to ask whether we can exploit it to reduce the computational burden of the construction problem. We show that, if we take advantage of the partial order [1], [2], we can construct a polar code by computing the reliability of roughly N/ log 3/2 N synthetic channels. Such a set of synthetic channels is universal, in the sense that it allows one to construct polar codes for any W, and it can be identified by solving a maximum matching problem on a bipartite graph. Our proof technique consists in reducing the construction problem to the problem of computing the maximum cardinality of an antichain for a suitable partially ordered set. As such, this method is general and it can be used to further improve the complexity of the construction problem in case a new partial order on the synthetic channels of polar codes is discovered.

Reed–Muller codes achieve capacity on erasure channels - Kudekar, Shrinivas; Kumar, Santhosh; Mondelli, Marco; Pfister, Henry D.; Sasoglu, Eren; Urbanke, Ridiger L. (IEEE Transactions on Information Theory)
We introduce a new approach to proving that a sequence of deterministic linear codes achieves capacity on an erasure channel under maximum a posteriori decoding. Rather than relying on the precise structure of the codes, our method exploits code symmetry. In particular, the technique applies to any sequence of linear codes where the blocklengths are strictly increasing, the code rates converge, and the permutation group of each code is doubly transitive. In other words, we show that symmetry alone implies near-optimal performance. An important consequence of this result is that a sequence of Reed-Muller codes with increasing block length and converging rate achieves capacity. This possibility has been suggested previously in the literature but it has only been proven for cases where the limiting code rate is 0 or 1. Moreover, these results extend naturally to all affine-invariant codes and, thus, to extended primitive narrow-sense BCH codes. This also resolves, in the affirmative, the existence question for capacity-achieving sequences of binary cyclic codes. The primary tools used in the proof are the sharp threshold property for symmetric monotone Boolean functions and the area theorem for extrinsic information transfer functions.

Dendritic cells interpret haptotactic chemokine gradients in a manner governed by signal to noise ratio and dependent on GRK6 - Schwarz, Jan; Bierbaum, Veronika; Vaahtomeri, Kari; Hauschild, Robert; Brown, Markus; De Vries, Ingrid; Leithner, Alexander F; Reversat, Anne; Merrin, Jack; Tarrant, Teresa; Bollenbach, Tobias; Sixt, Michael K (Current Biology)
Navigation of cells along gradients of guidance cues is a determining step in many developmental and immunological processes. Gradients can either be soluble or immobilized to tissues as demonstrated for the haptotactic migration of dendritic cells (DCs) toward higher concentrations of immobilized chemokine CCL21. To elucidate how gradient characteristics govern cellular response patterns, we here introduce an in vitro system allowing to track migratory responses of DCs to precisely controlled immobilized gradients of CCL21. We find that haptotactic sensing depends on the absolute CCL21 concentration and local steepness of the gradient, consistent with a scenario where DC directionality is governed by the signal-to-noise ratio of CCL21 binding to the receptor CCR7. We find that the conditions for optimal DC guidance are perfectly provided by the CCL21 gradients we measure in vivo. Furthermore, we find that CCR7 signal termination by the G-protein-coupled receptor kinase 6 (GRK6) is crucial for haptotactic but dispensable for chemotactic CCL21 gradient sensing in vitro and confirm those observations in vivo. These findings suggest that stable, tissue-bound CCL21 gradients as sustainable “roads” ensure optimal guidance in vivo.

Capacity-achieving rate-compatible polar codes for general channels - Mondelli, Marco; Hassani, Hamed; Maric, Ivana; Hui, Dennis; Hong, Song-Nam (2017 IEEE Wireless Communications and Networking Conference Workshops)
We present a rate-compatible polar coding scheme that achieves the capacity of any family of channels. Our solution generalizes the previous results [1], [2] that provide capacity-achieving rate-compatible polar codes for a degraded family of channels. The motivation for our extension comes from the fact that in many practical scenarios, e.g., MIMO systems and non-Gaussian interference, the channels cannot be ordered by degradation. The main technical contribution of this paper consists in removing the degradation condition. To do so, we exploit the ideas coming from the construction of universal polar codes. Our scheme possesses the usual attractive features of polar codes: low complexity code construction, encoding, and decoding; super-polynomial scaling of the error probability with the block length; and absence of error floors. On the negative side, the scaling of the gap to capacity with the block length is slower than in standard polar codes, and we prove an upper bound on the scaling exponent.

The INO80 complex removes H2A.Z to promote presynaptic filament formation during homologous recombination - Lademann, Claudio; Renkawitz, Jörg; Pfander, Boris; Jentsch, Stefan (Cell Reports)
The INO80 complex (INO80-C) is an evolutionarily conserved nucleosome remodeler that acts in transcription, replication, and genome stability. It is required for resistance against genotoxic agents and is involved in the repair of DNA double-strand breaks (DSBs) by homologous recombination (HR). However, the causes of the HR defect in INO80-C mutant cells are controversial. Here, we unite previous findings using a system to study HR with high spatial resolution in budding yeast. We find that INO80-C has at least two distinct functions during HR—DNA end resection and presynaptic filament formation. Importantly, the second function is linked to the histone variant H2A.Z. In the absence of H2A.Z, presynaptic filament formation and HR are restored in INO80-C-deficient mutants, suggesting that presynaptic filament formation is the crucial INO80-C function during HR.

Multiscale force sensing in development - Petridou, Nicoletta; Spiro, Zoltan P; Heisenberg, Carl-Philipp J (Nature Cell Biology)
The seminal observation that mechanical signals can elicit changes in biochemical signalling within cells, a process commonly termed mechanosensation and mechanotransduction, has revolutionized our understanding of the role of cell mechanics in various fundamental biological processes, such as cell motility, adhesion, proliferation and differentiation. In this Review, we will discuss how the interplay and feedback between mechanical and biochemical signals control tissue morphogenesis and cell fate specification in embryonic development.

Doomsday equilibria for omega-regular games - Chatterjee, Krishnendu; Doyen, Laurent; Filiot, Emmanuel; Raskin, Jean (Information and Computation)
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. In this paper we propose a new notion of equilibria, called doomsday equilibria, which is a strategy profile where 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.

Extrapolation and learning equations - Martius, Georg S; Lampert, Christoph (5th International Conference on Learning Representations, ICLR 2017 - Workshop Track Proceedings)
In classical machine learning, regression is treated as a black box process of identifying a suitable function from a hypothesis set without attempting to gain insight into the mechanism connecting inputs and outputs. In the natural sciences, however, finding an interpretable function for a phenomenon is the prime goal as it allows to understand and generalize results. This paper proposes a novel type of function learning network, called equation learner (EQL), that can learn analytical expressions and is able to extrapolate to unseen domains. It is implemented as an end-to-end differentiable feed-forward network and allows for efficient gradient based training. Due to sparsity regularization concise interpretable expressions can be obtained. Often the true underlying source expression is identified.

Obligation blackwell games and p-automata - Chatterjee, Krishnendu; Piterman, Nir (Journal of Symbolic Logic)
We generalize winning conditions in two-player games by adding a structural acceptance condition called obligations. Obligations are orthogonal to the linear winning conditions that define whether a play is winning. Obligations are a declaration that player 0 can achieve a certain value from a configuration. If the obligation is met, the value of that configuration for player 0 is 1. We define the value in such games and show that obligation games are determined. For Markov chains with Borel objectives and obligations, and finite turn-based stochastic parity games with obligations we give an alternative and simpler characterization of the value function. Based on this simpler definition we show that the decision problem of winning finite turn-based stochastic parity games with obligations is in NP∩co-NP. We also show that obligation games provide a game framework for reasoning about p-automata. © 2017 The Association for Symbolic Logic.

The physics of development 100 years after D'Arcy Thompson's “on growth and form” - Briscoe, James; Kicheva, Anna (Mechanisms of Development)
By applying methods and principles from the physical sciences to biological problems, D'Arcy Thompson's On Growth and Form demonstrated how mathematical reasoning reveals elegant, simple explanations for seemingly complex processes. This has had a profound influence on subsequent generations of developmental biologists. We discuss how this influence can be traced through twentieth century morphologists, embryologists and theoreticians to current research that explores the molecular and cellular mechanisms of tissue growth and patterning, including our own studies of the vertebrate neural tube.

Topological data analysis with Bregman divergences - Edelsbrunner, Herbert; Wagner, Hubert
We show that the framework of topological data analysis can be extended from metrics to general Bregman divergences, widening the scope of possible applications. Examples are the Kullback - Leibler divergence, which is commonly used for comparing text and images, and the Itakura - Saito divergence, popular for speech and sound. In particular, we prove that appropriately generalized čech and Delaunay (alpha) complexes capture the correct homotopy type, namely that of the corresponding union of Bregman balls. Consequently, their filtrations give the correct persistence diagram, namely the one generated by the uniformly growing Bregman balls. Moreover, we show that unlike the metric setting, the filtration of Vietoris-Rips complexes may fail to approximate the persistence diagram. We propose algorithms to compute the thus generalized čech, Vietoris-Rips and Delaunay complexes and experimentally test their efficiency. Lastly, we explain their surprisingly good performance by making a connection with discrete Morse theory.

The critical CoHA of a quiver with potential - Davison, Ben (Quarterly Journal of Mathematics)
Pursuing the similarity between the Kontsevich-Soibelman construction of the cohomological Hall algebra (CoHA) of BPS states and Lusztig's construction of canonical bases for quantum enveloping algebras, and the similarity between the integrality conjecture for motivic Donaldson-Thomas invariants and the PBW theorem for quantum enveloping algebras, we build a coproduct on the CoHA associated to a quiver with potential. We also prove a cohomological dimensional reduction theorem, further linking a special class of CoHAs with Yangians, and explaining how to connect the study of character varieties with the study of CoHAs.

D'Arcy Thompson's ‘on growth and form’: From soap bubbles to tissue self organization - Heisenberg, Carl-Philipp J (Mechanisms of Development)
Tissues are thought to behave like fluids with a given surface tension. Differences in tissue surface tension (TST) have been proposed to trigger cell sorting and tissue envelopment. D'Arcy Thompson in his seminal book ‘On Growth and Form’ has introduced this concept of differential TST as a key physical mechanism dictating tissue formation and organization within the developing organism. Over the past century, many studies have picked up the concept of differential TST and analyzed the role and cell biological basis of TST in development, underlining the importance and influence of this concept in developmental biology.

Rett syndrome modeling goes simian - Novarino, Gaia (Science Translational Medicine)
Rett syndrome modeling in monkey mirrors the human disorder.

Numbers of presynaptic Ca2+ channel clusters match those of functionally defined vesicular docking sites in single central synapses - Miki, Takafumi; Kaufmann, Walter; Malagon, Gerardo; Gomez, Laura; Tabuchi, Katsuhiko; Watanabe, Masahiko; Shigemoto, Ryuichi; Marty, Alain (PNAS)
Many central synapses contain a single presynaptic active zone and a single postsynaptic density. Vesicular release statistics at such “simple synapses” indicate that they contain a small complement of docking sites where vesicles repetitively dock and fuse. In this work, we investigate functional and morphological aspects of docking sites at simple synapses made between cerebellar parallel fibers and molecular layer interneurons. Using immunogold labeling of SDS-treated freeze-fracture replicas, we find that Cav2.1 channels form several clusters per active zone with about nine channels per cluster. The mean value and range of intersynaptic variation are similar for Cav2.1 cluster numbers and for functional estimates of docking-site numbers obtained from the maximum numbers of released vesicles per action potential. Both numbers grow in relation with synaptic size and decrease by a similar extent with age between 2 wk and 4 wk postnatal. Thus, the mean docking-site numbers were 3.15 at 2 wk (range: 1–10) and 2.03 at 4 wk (range: 1–4), whereas the mean numbers of Cav2.1 clusters were 2.84 at 2 wk (range: 1–8) and 2.37 at 4 wk (range: 1–5). These changes were accompanied by decreases of miniature current amplitude (from 93 pA to 56 pA), active-zone surface area (from 0.0427 μm2 to 0.0234 μm2), and initial success rate (from 0.609 to 0.353), indicating a tightening of synaptic transmission with development. Altogether, these results suggest a close correspondence between the number of functionally defined vesicular docking sites and that of clusters of voltage-gated calcium channels.

LCL problems on grids - Brandt, Sebastian; Hirvonen, Juho; Korhonen, Janne H.; Lempiäinen, Tuomo; Östergård, Patric R.J.; Purcell, Christopher; Rybicki, Joel; Suomela, Jukka; Uznański, Przemysław
LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of O(1), Θ(log* n), or Θ(n), and the design of optimal algorithms can be fully automated. This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: O(1), Θ(log* n), and Θ(n). However, given an LCL problem it is undecidable whether its complexity is Θ(log* n) or Θ(n) in 2-dimensional grids. Nevertheless, if we correctly guess that the complexity of a problem is Θ(log* n), we can completely automate the design of optimal algorithms. For any problem we can find an algorithm that is of a normal form A' o Sk, where A' is a finite function, Sk is an algorithm for finding a maximal independent set in kth power of the grid, and k is a constant. Finally, partially with the help of automated design tools, we classify the complexity of several concrete LCL problems related to colourings and orientations.

A dual phenotype of MDA MB 468 cancer cells reveals mutual regulation of tensin3 and adhesion plasticity - Veß, Astrid; Blache, Ulrich; Leitner, Laura; Kurz, Angela; Ehrenpfordt, Anja; Sixt, Michael K; Posern, Guido (Journal of Cell Science)
A change regarding the extent of adhesion - hereafter referred to as adhesion plasticity - between adhesive and less-adhesive states of mammalian cells is important for their behavior. To investigate adhesion plasticity, we have selected a stable isogenic subpopulation of human MDA-MB-468 breast carcinoma cells growing in suspension. These suspension cells are unable to re-adhere to various matrices or to contract three-dimensional collagen lattices. By using transcriptome analysis, we identified the focal adhesion protein tensin3 (Tns3) as a determinant of adhesion plasticity. Tns3 is strongly reduced at mRNA and protein levels in suspension cells. Furthermore, by transiently challenging breast cancer cells to grow under non-adherent conditions markedly reduces Tns3 protein expression, which is regained upon re-adhesion. Stable knockdown of Tns3 in parental MDA-MB-468 cells results in defective adhesion, spreading and migration. Tns3-knockdown cells display impaired structure and dynamics of focal adhesion complexes as determined by immunostaining. Restoration of Tns3 protein expression in suspension cells partially rescues adhesion and focal contact composition. Our work identifies Tns3 as a crucial focal adhesion component regulated by, and functionally contributing to, the switch between adhesive and non-adhesive states in MDA-MB-468 cancer cells.

A perfume collecting male oil bee? Evidences of a novel pollination system involving Anthurium acutifolium Araceae and Paratetrapedia chocoensis Apidae Tapinotaspidini - Etl, Florian; Franschitz, Anna; Aguiar, Antonio; Schönenberger, Jürg; Dötterl, Stefan (Flora: Morphology, Distribution, Functional Ecology of Plants)
It has been known since Stefan Vogel's observations in 1969 that solitary female oil bees collect fatty floral oils from specialized oil-secreting plants with the aid of hairy patches on either their legs or abdomen, a reward used as food for their larvae and/or to line their brood cells. Similar adaptations are also known from male oil bees, although the purpose of their oil-collecting behavior has not yet been clarified. Here, we describe a novel pollination system involving male Paratetrapedia oil bees and the tropical herb Anthurium acutifolium. We present ultrastructural morphological details of bee and plant structures involved in this interaction and the composition of floral scents likely mediating pollinator attraction. Inflorescences of A. acutifolium were visited almost exclusively by male P. chocoensis oil bees. The bees mopped with a hairy patch of their abdominal sterna 3 across the inflorescence surface. During this activity on both staminate and pistillate stage inflorescences, bees’ abdomens and legs became loaded with pollen and contacted receptive stigmas. In contrast to what has been observed in other angiosperms visited for the collection of fatty floral oils, the inflorescences/flowers of A. acutifolium do not have structures specialized in oil secretion, i.e., elaiophores. These inflorescences, nonetheless, were strongly scented during the time interval they were visited by the bees. Gas chromatography/mass spectrometry (GC/MS) analyses of dynamic headspace floral samples revealed that inflorescences of both anthetic phases emitted scent bouquets consisting mainly of aliphatic esters, indole and uncommmon terpenoids (megastigmanes). Interestingly enough, our data suggest that the unusual floral scent of A. acutifolium is a perfume reward collected by male P. chocoensis oil bees. This pollination system thus bears a remarkable resemblence with the interactions between perfume-collecting male euglossine bees and their preferred flowers, discovered by Stefan Vogel half a century ago.

Non uniform attacks against pseudoentropy - Pietrzak, Krzysztof Z; Skórski, Maciej
De, Trevisan and Tulsiani [CRYPTO 2010] show that every distribution over n-bit strings which has constant statistical distance to uniform (e.g., the output of a pseudorandom generator mapping n-1 to n bit strings), can be distinguished from the uniform distribution with advantage epsilon by a circuit of size O( 2^n epsilon^2). We generalize this result, showing that a distribution which has less than k bits of min-entropy, can be distinguished from any distribution with k bits of delta-smooth min-entropy with advantage epsilon by a circuit of size O(2^k epsilon^2/delta^2). As a special case, this implies that any distribution with support at most 2^k (e.g., the output of a pseudoentropy generator mapping k to n bit strings) can be distinguished from any given distribution with min-entropy k+1 with advantage epsilon by a circuit of size O(2^k epsilon^2). Our result thus shows that pseudoentropy distributions face basically the same non-uniform attacks as pseudorandom distributions.

Orientation and repositioning of chromosomes correlate with cell geometry dependent gene expression - Wang, Yejun; Nagarajan, Mallika; Uhler, Caroline; Shivashankar, Gv (Molecular Biology of the Cell)
Extracellular matrix signals from the microenvironment regulate gene expression patterns and cell behavior. Using a combination of experiments and geometric models, we demonstrate correlations between cell geometry, three-dimensional (3D) organization of chromosome territories, and gene expression. Fluorescence in situ hybridization experiments showed that micropatterned fibroblasts cultured on anisotropic versus isotropic substrates resulted in repositioning of specific chromosomes, which contained genes that were differentially regulated by cell geometries. Experiments combined with ellipsoid packing models revealed that the mechanosensitivity of chromosomes was correlated with their orientation in the nucleus. Transcription inhibition experiments suggested that the intermingling degree was more sensitive to global changes in transcription than to chromosome radial positioning and its orientations. These results suggested that cell geometry modulated 3D chromosome arrangement, and their neighborhoods correlated with gene expression patterns in a predictable manner. This is central to understanding geometric control of genetic programs involved in cellular homeostasis and the associated diseases.

The red queen and king in finite populations - Veller, Carl; Hayward, Laura; Nowak, Martin; Hilbe, Christian (PNAS)
In antagonistic symbioses, such as host–parasite interactions, one population’s success is the other’s loss. In mutualistic symbioses, such as division of labor, both parties can gain, but they might have different preferences over the possible mutualistic arrangements. The rates of evolution of the two populations in a symbiosis are important determinants of which population will be more successful: Faster evolution is thought to be favored in antagonistic symbioses (the “Red Queen effect”), but disfavored in certain mutualistic symbioses (the “Red King effect”). However, it remains unclear which biological parameters drive these effects. Here, we analyze the effects of the various determinants of evolutionary rate: generation time, mutation rate, population size, and the intensity of natural selection. Our main results hold for the case where mutation is infrequent. Slower evolution causes a long-term advantage in an important class of mutualistic interactions. Surprisingly, less intense selection is the strongest driver of this Red King effect, whereas relative mutation rates and generation times have little effect. In antagonistic interactions, faster evolution by any means is beneficial. Our results provide insight into the demographic evolution of symbionts.

Optomechanical proposal for monitoring microtubule mechanical vibrations - Barzanjeh, Shabir; Salari, Vahid; Tuszynski, Jack; Cifra, Michal; Simon, Christoph (Physical Review E Statistical Nonlinear and Soft Matter Physics)
Microtubules provide the mechanical force required for chromosome separation during mitosis. However, little is known about the dynamic (high-frequency) mechanical properties of microtubules. Here, we theoretically propose to control the vibrations of a doubly clamped microtubule by tip electrodes and to detect its motion via the optomechanical coupling between the vibrational modes of the microtubule and an optical cavity. In the presence of a red-detuned strong pump laser, this coupling leads to optomechanical-induced transparency of an optical probe field, which can be detected with state-of-the art technology. The center frequency and line width of the transparency peak give the resonance frequency and damping rate of the microtubule, respectively, while the height of the peak reveals information about the microtubule-cavity field coupling. Our method opens the new possibilities to gain information about the physical properties of microtubules, which will enhance our capability to design physical cancer treatment protocols as alternatives to chemotherapeutic drugs.

On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4 - Kynčl, Jan; Patakova, Zuzana (The Electronic Journal of Combinatorics)
A d-dimensional simplex S is called a k-reptile (or a k-reptile simplex) if it can be tiled by k simplices with disjoint interiors that are all mutually congruent and similar to S. For d = 2, triangular k-reptiles exist for all k of the form a^2, 3a^2 or a^2+b^2 and they have been completely characterized by Snover, Waiveris, and Williams. On the other hand, the only k-reptile simplices that are known for d ≥ 3, have k = m^d, where m is a positive integer. We substantially simplify the proof by Matoušek and the second author that for d = 3, k-reptile tetrahedra can exist only for k = m^3. We then prove a weaker analogue of this result for d = 4 by showing that four-dimensional k-reptile simplices can exist only for k = m^2.

The riddle of CHD8 haploinsufficiency in autism spectrum disorder - Novarino, Gaia (Science Translational Medicine)
Leading autism-associated mutation in mouse partially mimics human disorder.

Roles of afadin in functional differentiations of hippocampal mossy fiber synapse - Geng, Xiaoqi; Maruo, Tomohiko; Mandai, Kenji; Supriyanto, Irwan; Miyata, Muneaki; Sakakibara, Shotaro; Mizoguchi, Akira; Takai, Yoshimi; Mori, Masahiro (Genes to Cells)
A hippocampal mossy fiber synapse has a complex structure and is implicated in learning and memory. In this synapse, the mossy fiber boutons attach to the dendritic shaft by puncta adherentia junctions and wrap around a multiply-branched spine, forming synaptic junctions. We have recently shown using transmission electron microscopy, immunoelectron microscopy and serial block face-scanning electron microscopy that atypical puncta adherentia junctions are formed in the afadin-deficient mossy fiber synapse and that the complexity of postsynaptic spines and mossy fiber boutons, the number of spine heads, the area of postsynaptic densities and the density of synaptic vesicles docked to active zones are decreased in the afadin-deficient synapse. We investigated here the roles of afadin in the functional differentiations of the mossy fiber synapse using the afadin-deficient mice. The electrophysiological studies showed that both the release probability of glutamate and the postsynaptic responsiveness to glutamate were markedly reduced, but not completely lost, in the afadin-deficient mossy fiber synapse, whereas neither long-term potentiation nor long-term depression was affected. These results indicate that afadin plays roles in the functional differentiations of the presynapse and the postsynapse of the hippocampal mossy fiber synapse.

Robust spin correlations at high magnetic fields in the harmonic honeycomb iridates - Modic, Kimberly A; Ramshaw, B. J.; Betts, J. B.; Breznay, Nicholas P.; Analytis, James G.; McDonald, Ross D.; Shekhter, Arkady (Nature Communications)
The complex antiferromagnetic orders observed in the honeycomb iridates are a double-edged sword in the search for a quantum spin-liquid: both attesting that the magnetic interactions provide many of the necessary ingredients, while simultaneously impeding access. Focus has naturally been drawn to the unusual magnetic orders that hint at the underlying spin correlations. However, the study of any particular broken symmetry state generally provides little clue about the possibility of other nearby ground states. Here we use magnetic fields approaching 100 Tesla to reveal the extent of the spin correlations in γ-lithium iridate. We find that a small component of field along the magnetic easy-axis melts long-range order, revealing a bistable, strongly correlated spin state. Far from the usual destruction of antiferromagnetism via spin polarization, the high-field state possesses only a small fraction of the total iridium moment, without evidence for long-range order up to the highest attainable magnetic fields.

Broken rotational symmetry on the Fermi surface of a high-Tc superconductor - Ramshaw, B. J.; Harrison, N.; Sebastian, S. E.; Ghannadzadeh, S.; Modic, Kimberly A; Bonn, D. A.; Hardy, W. N.; Liang, Ruixing; Goddard, P. A. (npj Quantum Materials)
Broken fourfold rotational (C4) symmetry is observed in the experimental properties of several classes of unconventional superconductors. It has been proposed that this symmetry breaking is important for superconducting pairing in these materials, but in the high-Tc cuprates this broken symmetry has never been observed on the Fermi surface. Here we report a pronounced anisotropy in the angle dependence of the interlayer magnetoresistance of the underdoped high transition temperature (high-Tc) superconductor YBa2Cu3O6.58, directly revealing broken C4 symmetry on the Fermi surface. Moreover, we demonstrate that this Fermi surface has C2 symmetry of the type produced by a uniaxial or anisotropic density-wave phase. This establishes the central role of C4 symmetry breaking in the Fermi surface reconstruction of YBa2Cu3O6+δ , and suggests a striking degree of universality among unconventional superconductors.

Magnetic field tuning of an excitonic insulator between the weak and strong coupling regimes in quantum limit graphite - Zhu, Z.; McDonald, R. D.; Shekhter, A.; Ramshaw, B. J.; Modic, Kimberly A; Balakirev, F. F.; Harrison, N. (Scientific Reports)
The excitonic insulator phase has long been predicted to form in proximity to a band gap opening in the underlying band structure. The character of the pairing is conjectured to crossover from weak (BCS-like) to strong coupling (BEC-like) as the underlying band structure is tuned from the metallic to the insulating side of the gap opening. Here we report the high-magnetic field phase diagram of graphite to exhibit just such a crossover. By way of comprehensive angle-resolved magnetoresistance measurements, we demonstrate that the underlying band gap opening occurs inside the magnetic field-induced phase, paving the way for a systematic study of the BCS-BEC-like crossover by means of conventional condensed matter probes.

Thermodynamic constraints on the amplitude of quantum oscillations - Shekhter, Arkady; Modic, Kimberly A; McDonald, R. D.; Ramshaw, B. J. (Physical Review B)
Magneto-quantum oscillation experiments in high-temperature superconductors show a strong thermally induced suppression of the oscillation amplitude approaching the critical dopings [B. J. Ramshaw et al., Science 348, 317 (2014); H. Shishido et al., Phys. Rev. Lett. 104, 057008 (2010); P. Walmsley et al., Phys. Rev. Lett. 110, 257002 (2013)]—in support of a quantum-critical origin of their phase diagrams. We suggest that, in addition to a thermodynamic mass enhancement, these experiments may directly indicate the increasing role of quantum fluctuations that suppress the quantum oscillation amplitude through inelastic scattering. We show that the traditional theoretical approaches beyond Lifshitz-Kosevich to calculate the oscillation amplitude in correlated metals result in a contradiction with the third law of thermodynamics and suggest a way to rectify this problem.

A tight estimate for the waist of the ball - Akopyan, Arseniy; Karasev, Roman (Bulletin of the London Mathematical Society)
We answer a question of M. Gromov on the waist of the unit ball.

Different patterns of neuronal activity trigger distinct responses of oligodendrocyte precursor cells in the corpus callosum - Nagy, Balint; Hovhannisyan, Anahit; Barzan, Ruxandra; Chen, Ting; Kukley, Maria (PLoS Biology)
In the developing and adult brain, oligodendrocyte precursor cells (OPCs) are influenced by neuronal activity: they are involved in synaptic signaling with neurons, and their proliferation and differentiation into myelinating glia can be altered by transient changes in neuronal firing. An important question that has been unanswered is whether OPCs can discriminate different patterns of neuronal activity and respond to them in a distinct way. Here, we demonstrate in brain slices that the pattern of neuronal activity determines the functional changes triggered at synapses between axons and OPCs. Furthermore, we show that stimulation of the corpus callosum at different frequencies in vivo affects proliferation and differentiation of OPCs in a dissimilar way. Our findings suggest that neurons do not influence OPCs in “all-or-none” fashion but use their firing pattern to tune the response and behavior of these nonneuronal cells.

Gene expression changes of thermo sensitive transient receptor potential channels in obese mice - Sun, Wuping; Li, Chen; Zhang, Yonghong; Jiang, Changyu; Zhai, Ming-Zhu; Zhou, Qian; Xiao, Lizu; Deng, Qiwen (Cell Biology International)
Adipose tissues play key roles in energy homeostasis. Brown adipocytes and beige adipocytes in white adipose tissue (WAT) share the similar characters of thermogenesis, both of them could be potential targets for obesity management. Several thermo-sensitive transient receptor potential channels (thermoTRPs) are shown to be involved in adipocyte biology. However, the expression pattern of thermoTRPs in adipose tissues from obese mice is still unknown. The mRNA expression of thermoTRPs in subcutaneous WAT (sWAT) and interscapular brown adipose tissue (iBAT) from lean and obese mice were measured using reverse transcriptase-quantitative PCRs (RT-qPCR). The results demonstrated that all 10 thermoTRPs are expressed in both iBAT and sWAT, and without significant difference in the mRNA expression level of thermoTRPs between these two tissues. Moreover, Trpv1 and Trpv3 mRNA expression levels in both iBAT and sWAT were significantly decreased in high fat diet (HFD)-induced obese mice and db/db (leptin receptor deficient) mice. Trpm2 mRNA expression level was significantly decreased only in sWAT from HFD-induced obese mice and db/db mice. On the other hand, Trpv2 and Trpv4 mRNA expression levels in iBAT and sWAT were significantly increased in HFD-induced obese mice and db/db mice. Taken together, we conclude that all 10 thermoTRPs are expressed in iBAT and sWAT. And several thermoTRPs differentially expressed in adipose tissues from HFD-induced obese mice and db/db mice, suggesting a potential involvement in anti-obesity regulations.

Renyi entropy estimation revisited - Obremski, Maciej; Skórski, Maciej
We revisit the problem of estimating entropy of discrete distributions from independent samples, studied recently by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015), improving their upper and lower bounds on the necessary sample size n. For estimating Renyi entropy of order alpha, up to constant accuracy and error probability, we show the following * Upper bounds n = O(1) 2^{(1-1/alpha)H_alpha} for integer alpha>1, as the worst case over distributions with Renyi entropy equal to H_alpha. * Lower bounds n = Omega(1) K^{1-1/alpha} for any real alpha>1, with the constant being an inverse polynomial of the accuracy, as the worst case over all distributions on K elements. Our upper bounds essentially replace the alphabet size by a factor exponential in the entropy, which offers improvements especially in low or medium entropy regimes (interesting for example in anomaly detection). As for the lower bounds, our proof explicitly shows how the complexity depends on both alphabet and accuracy, partially solving the open problem posted in previous works. The argument for upper bounds derives a clean identity for the variance of falling-power sum of a multinomial distribution. Our approach for lower bounds utilizes convex optimization to find a distribution with possibly worse estimation performance, and may be of independent interest as a tool to work with Le Cam’s two point method.

Mapping the mouse Allelome reveals tissue specific regulation of allelic expression - Andergassen, Daniel; Dotter, Christoph; Wenzel, Dyniel; Sigl, Verena; Bammer, Philipp; Muckenhuber, Markus; Mayer, Daniela; Kulinski, Tomasz; Theussl, Hans; Penninger, Josef; Bock, Christoph; Barlow, Denise; et al. (eLife)
To determine the dynamics of allelic-specific expression during mouse development, we analyzed RNA-seq data from 23 F1 tissues from different developmental stages, including 19 female tissues allowing X chromosome inactivation (XCI) escapers to also be detected. We demonstrate that allelic expression arising from genetic or epigenetic differences is highly tissue-specific. We find that tissue-specific strain-biased gene expression may be regulated by tissue-specific enhancers or by post-transcriptional differences in stability between the alleles. We also find that escape from X-inactivation is tissue-specific, with leg muscle showing an unexpectedly high rate of XCI escapers. By surveying a range of tissues during development, and performing extensive validation, we are able to provide a high confidence list of mouse imprinted genes including 18 novel genes. This shows that cluster size varies dynamically during development and can be substantially larger than previously thought, with the Igf2r cluster extending over 10 Mb in placenta.

Bidirectional nested weighted automata - Chatterjee, Krishnendu; Henzinger, Thomas A; Otop, Jan
Nested weighted automata (NWA) present a robust and convenient automata-theoretic formalism for quantitative specifications. Previous works have considered NWA that processed input words only in the forward direction. It is natural to allow the automata to process input words backwards as well, for example, to measure the maximal or average time between a response and the preceding request. We therefore introduce and study bidirectional NWA that can process input words in both directions. First, we show that bidirectional NWA can express interesting quantitative properties that are not expressible by forward-only NWA. Second, for the fundamental decision problems of emptiness and universality, we establish decidability and complexity results for the new framework which match the best-known results for the special case of forward-only NWA. Thus, for NWA, the increased expressiveness of bidirectionality is achieved at no additional computational complexity. This is in stark contrast to the unweighted case, where bidirectional finite automata are no more expressive but exponentially more succinct than their forward-only counterparts.

Weak–strong uniqueness of solutions to entropy dissipating reaction–diffusion equations - Fischer, Julian L (Nonlinear Analysis: Theory, Methods and Applications)
We establish a weak–strong uniqueness principle for solutions to entropy-dissipating reaction–diffusion equations: As long as a strong solution to the reaction–diffusion equation exists, any weak solution and even any renormalized solution must coincide with this strong solution. Our assumptions on the reaction rates are just the entropy condition and local Lipschitz continuity; in particular, we do not impose any growth restrictions on the reaction rates. Therefore, our result applies to any single reversible reaction with mass-action kinetics as well as to systems of reversible reactions with mass-action kinetics satisfying the detailed balance condition. Renormalized solutions are known to exist globally in time for reaction–diffusion equations with entropy-dissipating reaction rates; in contrast, the global-in-time existence of weak solutions is in general still an open problem–even for smooth data–, thereby motivating the study of renormalized solutions. The key ingredient of our result is a careful adjustment of the usual relative entropy functional, whose evolution cannot be controlled properly for weak solutions or renormalized solutions.

HIV Tat excites D1 receptor-like expressing neurons from rat nucleus accumbens - Brailoiu, Gabriela; Deliu, Elena; Barr, Jeffrey; Console Bram, Linda; Ciuciu, Alexandra; Abood, Mary; Unterwald, Ellen; Brǎiloiu, Eugen (Drug and Alcohol Dependence)
Background HIV-1 infection and drug abuse are frequently co-morbid and their association greatly increases the severity of HIV-1-induced neuropathology. While nucleus accumbens (NAcc) function is severely perturbed by drugs of abuse, little is known about how HIV-1 infection affects NAcc. Methods We used calcium and voltage imaging to investigate the effect of HIV-1 trans-activator of transcription (Tat) on rat NAcc. Based on previous neuronal studies, we hypothesized that Tat modulates intracellular Ca2+ homeostasis of NAcc neurons. Results We provide evidence that Tat triggers a Ca2+ signaling cascade in NAcc medium spiny neurons (MSN) expressing D1-like dopamine receptors leading to neuronal depolarization. Firstly, Tat induced inositol 1,4,5-trisphsophate (IP3) receptor-mediated Ca2+ release from endoplasmic reticulum, followed by Ca2+ and Na+ influx via transient receptor potential canonical channels. The influx of cations depolarizes the membrane promoting additional Ca2+ entry through voltage-gated P/Q-type Ca2+ channels and opening of tetrodotoxin-sensitive Na+ channels. By activating this mechanism, Tat elicits a feed-forward depolarization increasing the excitability of D1-phosphatidylinositol-linked NAcc MSN. We previously found that cocaine targets NAcc neurons directly (independent of the inhibition of dopamine transporter) only when IP3-generating mechanisms are concomitantly initiated. When tested here, cocaine produced a dose-dependent potentiation of the effect of Tat on cytosolic Ca2+. Conclusion We describe for the first time a HIV-1 Tat-triggered Ca2+ signaling in MSN of NAcc involving TRPC and depolarization and a potentiation of the effect of Tat by cocaine, which may be relevant for the reward axis in cocaine-abusing HIV-1-positive patients.

More excitation for Rett syndrome - Novarino, Gaia (Science Translational Medicine)
D-cycloserine ameliorates breathing abnormalities and survival rate in a mouse model of Rett syndrome.

The complexity of mean-payoff pushdown games - Chatterjee, Krishnendu; Velner, Yaron (Journal of the ACM)
Two-player games on graphs are central in many problems in formal verification and program analysis, such as synthesis and verification of open systems. In this work, we consider solving recursive game graphs (or pushdown game graphs) that model the control flow of sequential programs with recursion.While pushdown games have been studied before with qualitative objectives-such as reachability and ?-regular objectives- in this work, we study for the first time such games with the most well-studied quantitative objective, the mean-payoff objective. In pushdown games, two types of strategies are relevant: (1) global strategies, which depend on the entire global history; and (2) modular strategies, which have only local memory and thus do not depend on the context of invocation but rather only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two-player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP-hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity by showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games and memoryless modular strategies are sufficient in two-player pushdown games. Finally, we also show that all the problems have the same complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded.

Hyperplane separation technique for multidimensional mean-payoff games - Chatterjee, Krishnendu; Velner, Yaron (Journal of Computer and System Sciences)
We consider finite-state and recursive game graphs with multidimensional mean-payoff objectives. In recursive games two types of strategies are relevant: global strategies and modular strategies. Our contributions are: (1) We show that finite-state multidimensional mean-payoff games can be solved in polynomial time if the number of dimensions and the maximal absolute value of weights are fixed; whereas for arbitrary dimensions the problem is coNP-complete. (2) We show that one-player recursive games with multidimensional mean-payoff objectives can be solved in polynomial time. Both above algorithms are based on hyperplane separation technique. (3) For recursive games we show that under modular strategies the multidimensional problem is undecidable. We show that if the number of modules, exits, and the maximal absolute value of the weights are fixed, then one-dimensional recursive mean-payoff games under modular strategies can be solved in polynomial time, whereas for unbounded number of exits or modules the problem is NP-hard.

Special issue: Synthesis and SYNT 2014 - Chatterjee, Krishnendu; Ehlers, Rüdiger (Acta Informatica)
The ubiquity of computation in modern machines and devices imposes a need to assert the correctness of their behavior. Especially in the case of safety-critical systems, their designers need to take measures that enforce their safe operation. Formal methods has emerged as a research field that addresses this challenge: by rigorously proving that all system executions adhere to their specifications, the correctness of an implementation under concern can be assured. To achieve this goal, a plethora of techniques are nowadays available, all of which are optimized for different system types and application domains.

Probabilistic models for neural populations that naturally capture global coupling and criticality - Humplik, Jan; Tkacik, Gasper (PLoS Computational Biology)
Advances in multi-unit recordings pave the way for statistical modeling of activity patterns in large neural populations. Recent studies have shown that the summed activity of all neurons strongly shapes the population response. A separate recent finding has been that neural populations also exhibit criticality, an anomalously large dynamic range for the probabilities of different population activity patterns. Motivated by these two observations, we introduce a class of probabilistic models which takes into account the prior knowledge that the neural population could be globally coupled and close to critical. These models consist of an energy function which parametrizes interactions between small groups of neurons, and an arbitrary positive, strictly increasing, and twice differentiable function which maps the energy of a population pattern to its probability. We show that: 1) augmenting a pairwise Ising model with a nonlinearity yields an accurate description of the activity of retinal ganglion cells which outperforms previous models based on the summed activity of neurons; 2) prior knowledge that the population is critical translates to prior expectations about the shape of the nonlinearity; 3) the nonlinearity admits an interpretation in terms of a continuous latent variable globally coupling the system whose distribution we can infer from data. Our method is independent of the underlying system’s state space; hence, it can be applied to other systems such as natural scenes or amino acid sequences of proteins which are also known to exhibit criticality.

Singularities of solutions to quadratic vector equations on the complex upper half plane - Ajanki, Oskari H; Krüger, Torben H; Erdös, László (Communications on Pure and Applied Mathematics)
Let S be a positivity-preserving symmetric linear operator acting on bounded functions. The nonlinear equation -1/m=z+Sm with a parameter z in the complex upper half-plane ℍ has a unique solution m with values in ℍ. We show that the z-dependence of this solution can be represented as the Stieltjes transforms of a family of probability measures v on ℝ. Under suitable conditions on S, we show that v has a real analytic density apart from finitely many algebraic singularities of degree at most 3. Our motivation comes from large random matrices. The solution m determines the density of eigenvalues of two prominent matrix ensembles: (i) matrices with centered independent entries whose variances are given by S and (ii) matrices with correlated entries with a translation-invariant correlation structure. Our analysis shows that the limiting eigenvalue density has only square root singularities or cubic root cusps; no other singularities occur.

Shaping 3D root system architecture - Morris, Emily; Griffiths, Marcus; Golebiowska, Agata; Mairhofer, Stefan; Burr Hersey, Jasmine; Goh, Tatsuaki; Von Wangenheim, Daniel; Atkinson, Brian; Sturrock, Craig; Lynch, Jonathan; Vissenberg, Kris; Ritz, Karl; et al. (Current Biology)
Plants are sessile organisms rooted in one place. The soil resources that plants require are often distributed in a highly heterogeneous pattern. To aid foraging, plants have evolved roots whose growth and development are highly responsive to soil signals. As a result, 3D root architecture is shaped by myriad environmental signals to ensure resource capture is optimised and unfavourable environments are avoided. The first signals sensed by newly germinating seeds — gravity and light — direct root growth into the soil to aid seedling establishment. Heterogeneous soil resources, such as water, nitrogen and phosphate, also act as signals that shape 3D root growth to optimise uptake. Root architecture is also modified through biotic interactions that include soil fungi and neighbouring plants. This developmental plasticity results in a ‘custom-made’ 3D root system that is best adapted to forage for resources in each soil environment that a plant colonises.

Discrete modes of social information processing predict individual behavior of fish in a group - Harpaz, Roy; Tkacik, Gasper; Schneidman, Elad (PNAS)
Individual computations and social interactions underlying collective behavior in groups of animals are of great ethological, behavioral, and theoretical interest. While complex individual behaviors have successfully been parsed into small dictionaries of stereotyped behavioral modes, studies of collective behavior largely ignored these findings; instead, their focus was on inferring single, mode-independent social interaction rules that reproduced macroscopic and often qualitative features of group behavior. Here, we bring these two approaches together to predict individual swimming patterns of adult zebrafish in a group. We show that fish alternate between an “active” mode, in which they are sensitive to the swimming patterns of conspecifics, and a “passive” mode, where they ignore them. Using a model that accounts for these two modes explicitly, we predict behaviors of individual fish with high accuracy, outperforming previous approaches that assumed a single continuous computation by individuals and simple metric or topological weighing of neighbors’ behavior. At the group level, switching between active and passive modes is uncorrelated among fish, but correlated directional swimming behavior still emerges. Our quantitative approach for studying complex, multi-modal individual behavior jointly with emergent group behavior is readily extensible to additional behavioral modes and their neural correlates as well as to other species.

Noninteracting central site model localization and logarithmic entanglement growth - Hetterich, Daniel; Serbyn, Maksym; Domínguez, Fernando; Pollmann, Frank; Trauzettel, Björn (Physical Review B)
We investigate the stationary and dynamical behavior of an Anderson localized chain coupled to a single central bound state. Although this coupling partially dilutes the Anderson localized peaks towards nearly resonant sites, the most weight of the original peaks remains unchanged. This leads to multifractal wave functions with a frozen spectrum of fractal dimensions, which is characteristic for localized phases in models with power-law hopping. Using a perturbative approach we identify two different dynamical regimes. At weak couplings to the central site, the transport of particles and information is logarithmic in time, a feature usually attributed to many-body localization. We connect such transport to the persistence of the Poisson statistics of level spacings in parts of the spectrum. In contrast, at stronger couplings the level repulsion is established in the entire spectrum, the problem can be mapped to the Fano resonance, and the transport is ballistic.

Singlet oxygen during cycling of the aprotic sodium-O2 battery - Schafzahl, Lukas; Mahne, Nika; Schafzahl, Bettina; Wilkening, Martin; Slugovc, Christian; Borisov, Sergey M.; Freunberger, Stefan Alexander (Angewandte Chemie International Edition)
Aprotic sodium–O2 batteries require the reversible formation/dissolution of sodium superoxide (NaO2) on cycling. Poor cycle life has been associated with parasitic chemistry caused by the reactivity of electrolyte and electrode with NaO2, a strong nucleophile and base. Its reactivity can, however, not consistently explain the side reactions and irreversibility. Herein we show that singlet oxygen (1O2) forms at all stages of cycling and that it is a main driver for parasitic chemistry. It was detected in‐ and ex‐situ via a 1O2 trap that selectively and rapidly forms a stable adduct with 1O2. The 1O2 formation mechanism involves proton‐mediated superoxide disproportionation on discharge, rest, and charge below ca. 3.3 V, and direct electrochemical 1O2 evolution above ca. 3.3 V. Trace water, which is needed for high capacities also drives parasitic chemistry. Controlling the highly reactive singlet oxygen is thus crucial for achieving highly reversible cell operation.

Biredox ionic liquids: New opportunities toward high performance supercapacitors - Bodin, C.; Mourad, E.; Zigah, D.; Le Vot, S.; Freunberger, Stefan Alexander; Favier, F.; Fontaine, O. (Faraday Discussions)
Nowadays commercial supercapacitors are based on purely capacitive storage at the porous carbons that are used for the electrodes. However, the limits that capacitive storage imposes on energy density calls to investigate new materials to improve the capacitance of the device. This new type of electrodes (e.g., RuO2, MnO2…) involves pseudo-capacitive faradaic redox processes with the solid material. Ion exchange with solid materials is, however, much slower than the adsorption process in capacitive storage and inevitably leads to significant loss of power. Faradaic process in the liquid state, in contrast can be similarly fast as capacitive processes due to the fast ion transport. Designing new devices with liquid like dynamics and improved specific capacitance is challenging. We present a new approach to increase the specific capacitance using biredox ionic liquids, where redox moieties are tethered to the electrolyte ions, allowing high redox concentrations and significant pseudo-capacitive storage in the liquid state. Anions and cations are functionalized with anthraquinone (AQ) and 2,2,6,6-tetramethylpiperidinyl-1-oxyl (TEMPO) moieties, respectively. Glassy carbon, carbon-onion, and commercial activated carbon electrodes that exhibit different double layer structures and thus different diffusion dynamics were used to simultaneously study the electrochemical response of biredox ionic liquids at the positive and negative electrode.

Electron-deficient near-infrared Pt(II) and Pd(II) benzoporphyrins with dual phosphorescence and unusually efficient thermally activated delayed fluorescence: First demonstration of simultaneous oxygen and temperature sensing with a single emitter - Zach, Peter W.; Freunberger, Stefan Alexander; Klimant, Ingo; Borisov, Sergey M. (ACS Applied Materials & Interfaces)
We report a family of Pt and Pd benzoporphyrin dyes with versatile photophysical properties and easy access from cheap and abundant chemicals. Attaching 4 or 8 alkylsulfone groups onto a meso-tetraphenyltetrabenzoporphyrin (TPTBP) macrocylcle renders the dyes highly soluble in organic solvents, photostable, and electron-deficient with the redox potential raised up to 0.65 V versus the parent porphyrin. The new dyes intensively absorb in the blue (Soret band, 440–480 nm) and in the red (Q-band, 620–650 nm) parts of the electromagnetic spectrum and show bright phosphorescence at room-temperature in the NIR with quantum yields up to 30% in solution. The small singlet–triplet energy gap yields unusually efficient thermally activated delayed fluorescence (TADF) at elevated temperatures in solution and in polymeric matrices with quantum yields as high as 27% at 120 °C, which is remarkable for benzoporphyrins. Apart from oxygen sensing, these properties enable unprecedented simultaneous, self-referenced oxygen and temperature sensing with a single indicator dye: whereas oxygen can be determined either via the decay time of phosphorescence or TADF, the temperature is accessed via the ratio of the two emissions. Moreover, the dyes are efficient sensitizers for triplet–triplet annihilation (TTA)-based upconversion making possible longer sensitization wavelength than the conventional benzoporphyrin complexes. The Pt-octa-sulfone dye also features interesting semireversible transformation in basic media, which generates new NIR absorbing species.

Mechanism and performance of lithium–oxygen batteries – a perspective - Mahne, Nika; Fontaine, Olivier; Thotiyl, Musthafa Ottakam; Wilkening, Martin; Freunberger, Stefan Alexander (Chemical Science)
Rechargeable Li–O2 batteries have amongst the highest formal energy and could store significantly more energy than other rechargeable batteries in practice if at least a large part of their promise could be realized. Realization, however, still faces many challenges than can only be overcome by fundamental understanding of the processes taking place. Here, we review recent advances in understanding the chemistry of the Li–O2 cathode and provide a perspective on dominant research needs. We put particular emphasis on issues that are often grossly misunderstood: realistic performance metrics and their reporting as well as identifying reversibility and quantitative measures to do so. Parasitic reactions are the prime obstacle for reversible cell operation and have recently been identified to be predominantly caused by singlet oxygen and not by reduced oxygen species as thought before. We discuss the far reaching implications of this finding on electrolyte and cathode stability, electrocatalysis, and future research needs.

An electrolyte for reversible cycling of sodium metal and intercalation compounds - Schafzahl, Lukas; Hanzu, Ilie; Wilkening, Martin; Freunberger, Stefan Alexander (ChemSusChem)
Na battery chemistries show poor passivation behavior of low voltage Na storage compounds and Na metal with organic carbonate‐based electrolytes adopted from Li‐ion batteries. Therefore, a suitable electrolyte remains a major challenge for establishing Na batteries. Here we report highly concentrated sodium bis(fluorosulfonyl)imide (NaFSI) in dimethoxyethane (DME) electrolytes and investigate them for Na metal and hard carbon anodes and intercalation cathodes. For a DME/NaFSI ratio of 2, a stable passivation of anode materials was found owing to the formation of a stable solid electrolyte interface, which was characterized spectroscopically. This permitted non‐dentritic Na metal cycling with approximately 98 % coulombic efficiency as shown for up to 300 cycles. The NaFSI/DME electrolyte may enable Na‐metal anodes and allows for more reliable assessment of electrode materials in Na‐ion half‐cells, as is demonstrated by comparing half‐cell cycling of hard carbon anodes and Na3V2(PO4)3 cathodes with a widely used carbonate and the NaFSI/DME electrolyte.

The science of love in ASD and ADHD - Novarino, Gaia (Science Translational Medicine)
Genetic variations in the oxytocin receptor gene affect patients with ASD and ADHD differently.

A synthetic mammalian therapeutic gene circuit for sensing and suppressing inflammation - Smole, Anže; Lainšček, Duško; Bezeljak, Urban; Horvat, Simon; Jerala, Roman (Molecular Therapy)
Inflammation, which is a highly regulated host response against danger signals, may be harmful if it is excessive and deregulated. Ideally, anti-inflammatory therapy should autonomously commence as soon as possible after the onset of inflammation, should be controllable by a physician, and should not systemically block beneficial immune response in the long term. We describe a genetically encoded anti-inflammatory mammalian cell device based on a modular engineered genetic circuit comprising a sensor, an amplifier, a “thresholder” to restrict activation of a positive-feedback loop, a combination of advanced clinically used biopharmaceutical proteins, and orthogonal regulatory elements that linked modules into the functional device. This genetic circuit was autonomously activated by inflammatory signals, including endogenous cecal ligation and puncture (CLP)-induced inflammation in mice and serum from a systemic juvenile idiopathic arthritis (sIJA) patient, and could be reset externally by a chemical signal. The microencapsulated anti-inflammatory device significantly reduced the pathology in dextran sodium sulfate (DSS)-induced acute murine colitis, demonstrating a synthetic immunological approach for autonomous anti-inflammatory therapy.

'...beyond the invisible barrier at Portage and Main': Liminality in John Marlyn's Under the Ribs of Death - Bernhard Wenzl (In-Between - Liminal Spaces in Canadian Literature and Culture)
The essay focuses on individual and collective forms of liminality in John Marlyn’s Under the Ribs of Death. Set in early twentieth-century Winnipeg, the 1957 immigrant novel explores liminal experiences related to ethnic identity, male sexuality, social class, urban spaces and turbulent economic times. As the son of a poor working-class family from Hungary, Sandor Hunyadi makes every effort to become a true Canadian and a successful businessman, but, no matter how hard he tries to overcome contemporary ethnic prejudices and economic hardships, his personal and professional life remains in liminality. In other words, the protagonist undergoes separation, fails at incorporation, and becomes stuck in transition.

Optimal geospatial volunteer allocation needs realistic distances - Pielorz, Jasmin; Prandtstetter, Matthias; Straub, Markus; Lampert, Christoph (2017 IEEE International Conference on Big Data)
Modern communication technologies allow first responders to contact thousands of potential volunteers simultaneously for support during a crisis or disaster event. However, such volunteer efforts must be well coordinated and monitored, in order to offer an effective relief to the professionals. In this paper we extend earlier work on optimally assigning volunteers to selected landmark locations. In particular, we emphasize the aspect that obtaining good assignments requires not only advanced computational tools, but also a realistic measure of distance between volunteers and landmarks. Specifically, we propose the use of the Open Street Map (OSM) driving distance instead of he previously used flight distance. We find the OSM driving distance to be better aligned with the interests of volunteers and first responders. Furthermore, we show that relying on the flying distance leads to a substantial underestimation of the number of required volunteers, causing negative side effects in case of an actual crisis situation.

Hidden heritability due to heterogeneity across seven populations - Tropf, Felix C.; Lee, S. Hong; Verweij, Renske M.; Stulp, Gert; van der Most, Peter J.; de Vlaming, Ronald; Bakshi, Andrew; Briley, Daniel A.; Rahal, Charles; Hellpap, Robert; Iliadou, Anastasia N.; Esko, Tõnu; et al. (Nature Human Behaviour)
Meta-analyses of genome-wide association studies, which dominate genetic discovery, are based on data from diverse historical time periods and populations. Genetic scores derived from genome-wide association studies explain only a fraction of the heritability estimates obtained from whole-genome studies on single populations, known as the ‘hidden heritability’ puzzle. Using seven sampling populations (n = 35,062), we test whether hidden heritability is attributed to heterogeneity across sampling populations and time, showing that estimates are substantially smaller across populations compared with within populations. We show that the hidden heritability varies substantially: from zero for height to 20% for body mass index, 37% for education, 40% for age at first birth and up to 75% for number of children. Simulations demonstrate that our results are more likely to reflect heterogeneity in phenotypic measurement or gene–environment interactions than genetic heterogeneity. These findings have substantial implications for genetic discovery, suggesting that large homogenous datasets are required for behavioural phenotypes and that gene–environment interaction may be a central challenge for genetic discovery.

Major histocompatibility complex-linked social signalling affects female fertility - Burger, D.; Thomas, S.; Aepli, H.; Dreyer, M.; Fabre, G.; Marti, E.; Sieme, H.; Robinson, Matthew Richard; Wedekind, C. (Proceedings of the Royal Society B: Biological Sciences)
Genes of the major histocompatibility complex (MHC) have been shown to influence social signalling and mate preferences in many species, including humans. First observations suggest that MHC signalling may also affect female fertility. To test this hypothesis, we exposed 191 female horses (Equus caballus) to either an MHC-similar or an MHC-dissimilar stimulus male around the time of ovulation and conception. A within-subject experimental design controlled for non-MHC-linked male characteristics, and instrumental insemination with semen of other males (n = 106) controlled for potential confounding effects of semen or embryo characteristics. We found that females were more likely to become pregnant if exposed to an MHC-dissimilar than to an MHC-similar male, while overall genetic distance to the stimulus males (based on microsatellite markers on 20 chromosomes) had no effect. Our results demonstrate that early pregnancy failures can be due to maternal life-history decisions (cryptic female choice) influenced by MHC-linked social signalling.

Detection and quantification of inbreeding depression for complex traits from SNP data - Yengo, Loic; Zhu, Zhihong; Wray, Naomi R.; Weir, Bruce S.; Yang, Jian; Robinson, Matthew Richard; Visscher, Peter M. (Proceedings of the National Academy of Sciences)
Quantifying the effects of inbreeding is critical to characterizing the genetic architecture of complex traits. This study highlights through theory and simulations the strengths and shortcomings of three SNP-based inbreeding measures commonly used to estimate inbreeding depression (ID). We demonstrate that heterogeneity in linkage disequilibrium (LD) between causal variants and SNPs biases ID estimates, and we develop an approach to correct this bias using LD and minor allele frequency stratified inference (LDMS). We quantified ID in 25 traits measured in ∼140,000 participants of the UK Biobank, using LDMS, and confirmed previously published ID for 4 traits. We find unique evidence of ID for handgrip strength, waist/hip ratio, and visual and auditory acuity (ID between −2.3 and −5.2 phenotypic SDs for complete inbreeding; P<0.001). Our results illustrate that a careful choice of the measure of inbreeding combined with LDMS stratification improves both detection and quantification of ID using SNP data.

Predation drives local adaptation of phenotypic plasticity - Reger, Julia; Lind, Martin I.; Robinson, Matthew Richard; Beckerman, Andrew P. (Nature Ecology & Evolution)
Phenotypic plasticity is the ability of an individual genotype to alter aspects of its phenotype depending on the current environment. It is central to the persistence, resistance and resilience of populations facing variation in physical or biological factors. Genetic variation in plasticity is pervasive, which suggests its local adaptation is plausible. Existing studies on the adaptation of plasticity typically focus on single traits and a few populations, while theory about interactions among genes (for example, pleiotropy) suggests that a multi-trait, landscape scale (for example, multiple populations) perspective is required. We present data from a landscape scale, replicated, multi-trait experiment using a classic predator–prey system centred on the water flea Daphnia pulex. We find predator regime-driven differences in genetic variation of multivariate plasticity. These differences are associated with strong divergent selection linked to a predation regime. Our findings are evidence for local adaptation of plasticity, suggesting that responses of populations to environmental variation depend on the conditions in which they evolved in the past.

Whole exome sequencing and DNA methylation analysis in a clinical amyotrophic lateral sclerosis cohort - Garton, Fleur C.; Benyamin, Beben; Zhao, Qiongyi; Liu, Zhijun; Gratten, Jacob; Henders, Anjali K.; Zhang, Zong-Hong; Edson, Janette; Furlong, Sarah; Morgan, Sarah; Heggie, Susan; Thorpe, Kathryn; et al. (Molecular Genetics & Genomic Medicine)
Sections PDFPDF Tools Share Abstract Background: Gene discovery has provided remarkable biological insights into amyotrophic lateral sclerosis (ALS). One challenge for clinical application of genetic testing is critical evaluation of the significance of reported variants. Methods: We use whole exome sequencing (WES) to develop a clinically relevant approach to identify a subset of ALS patients harboring likely pathogenic mutations. In parallel, we assess if DNA methylation can be used to screen for pathogenicity of novel variants since a methylation signature has been shown to associate with the pathogenic C9orf72 expansion, but has not been explored for other ALS mutations. Australian patients identified with ALS‐relevant variants were cross‐checked with population databases and case reports to critically assess whether they were “likely causal,” “uncertain significance,” or “unlikely causal.” Results: Published ALS variants were identified in >10% of patients; however, in only 3% of patients (4/120) could these be confidently considered pathogenic (in SOD1 and TARDBP). We found no evidence for a differential DNA methylation signature in these mutation carriers. Conclusions: The use of WES in a typical ALS clinic demonstrates a critical approach to variant assessment with the capability to combine cohorts to enhance the largely unknown genetic basis of ALS.

Inference on the genetic basis of eye and skin color in an admixed population via Bayesian linear mixed models - Lloyd-Jones, Luke R.; Robinson, Matthew Richard; Moser, Gerhard; Zeng, Jian; Beleza, Sandra; Barsh, Gregory S.; Tang, Hua; Visscher, Peter M. (Genetics)
Genetic association studies in admixed populations are underrepresented in the genomics literature, with a key concern for researchers being the adequate control of spurious associations due to population structure. Linear mixed models (LMMs) are well suited for genome-wide association studies (GWAS) because they account for both population stratification and cryptic relatedness and achieve increased statistical power by jointly modeling all genotyped markers. Additionally, Bayesian LMMs allow for more flexible assumptions about the underlying distribution of genetic effects, and can concurrently estimate the proportion of phenotypic variance explained by genetic markers. Using three recently published Bayesian LMMs, Bayes R, BSLMM, and BOLT-LMM, we investigate an existing data set on eye (n = 625) and skin (n = 684) color from Cape Verde, an island nation off West Africa that is home to individuals with a broad range of phenotypic values for eye and skin color due to the mix of West African and European ancestry. We use simulations to demonstrate the utility of Bayesian LMMs for mapping loci and studying the genetic architecture of quantitative traits in admixed populations. The Bayesian LMMs provide evidence for two new pigmentation loci: one for eye color (AHRR) and one for skin color (DDB1).

Deformation of crystals: Connections with statistical physics - Sethna, James P.; Bierbaum, Matthew K.; Dahmen, Karin A.; Goodrich, Carl Peter; Greer, Julia R.; Hayden, Lorien X.; Kent-Dobias, Jaron P.; Lee, Edward D.; Liarte, Danilo B.; Ni, Xiaoyue; Quinn, Katherine N.; Raju, Archishman; et al. (Annual Review of Materials Research)
We give a bird's-eye view of the plastic deformation of crystals aimed at the statistical physics community, as well as a broad introduction to the statistical theories of forced rigid systems aimed at the plasticity community. Memory effects in magnets, spin glasses, charge density waves, and dilute colloidal suspensions are discussed in relation to the onset of plastic yielding in crystals. Dislocation avalanches and complex dislocation tangles are discussed via a brief introduction to the renormalization group and scaling. Analogies to emergent scale invariance in fracture, jamming, coarsening, and a variety of depinning transitions are explored. Dislocation dynamics in crystals challenge nonequilibrium statistical physics. Statistical physics provides both cautionary tales of subtle memory effects in nonequilibrium systems and systematic tools designed to address complex scale-invariant behavior on multiple length scales and timescales.

Designing allostery-inspired response in mechanical networks - Rocks, Jason W.; Pashine, Nidhi; Bischofberger, Irmgard; Goodrich, Carl Peter; Liu, Andrea J.; Nagel, Sidney R. (Proceedings of the National Academy of Sciences)
Recent advances in designing metamaterials have demonstrated that global mechanical properties of disordered spring networks can be tuned by selectively modifying only a small subset of bonds. Here, using a computationally efficient approach, we extend this idea to tune more general properties of networks. With nearly complete success, we are able to produce a strain between any two target nodes in a network in response to an applied source strain on any other pair of nodes by removing only ∼1% of the bonds. We are also able to control multiple pairs of target nodes, each with a different individual response, from a single source, and to tune multiple independent source/target responses simultaneously into a network. We have fabricated physical networks in macroscopic 2D and 3D systems that exhibit these responses. This work is inspired by the long-range coupled conformational changes that constitute allosteric function in proteins. The fact that allostery is a common means for regulation in biological molecules suggests that it is a relatively easy property to develop through evolution. In analogy, our results show that long-range coupled mechanical responses are similarly easy to achieve in disordered networks.

Using active colloids as machines to weave and braid on the micrometer scale - Goodrich, Carl Peter; Brenner, Michael P. (Proceedings of the National Academy of Sciences)
Controlling motion at the microscopic scale is a fundamental goal in the development of biologically inspired systems. We show that the motion of active, self-propelled colloids can be sufficiently controlled for use as a tool to assemble complex structures such as braids and weaves out of microscopic filaments. Unlike typical self-assembly paradigms, these structures are held together by geometric constraints rather than adhesive bonds. The out-of-equilibrium assembly that we propose involves precisely controlling the 2D motion of active colloids so that their path has a nontrivial topology. We demonstrate with proof-of-principle Brownian dynamics simulations that, when the colloids are attached to long semiflexible filaments, this motion causes the filaments to braid. The ability of the active particles to provide sufficient force necessary to bend the filaments into a braid depends on a number of factors, including the self-propulsion mechanism, the properties of the filament, and the maximum curvature in the braid. Our work demonstrates that nonequilibrium assembly pathways can be designed using active particles.

Emergent SO(3) symmetry of the frictionless shear jamming transition - Baity-Jesi, Marco; Goodrich, Carl Peter; Liu, Andrea J.; Nagel, Sidney R.; Sethna, James P. (Journal of Statistical Physics)
We study the shear jamming of athermal frictionless soft spheres, and find that in the thermodynamic limit, a shear-jammed state exists with different elastic properties from the isotropically-jammed state. For example, shear-jammed states can have a non-zero residual shear stress in the thermodynamic limit that arises from long-range stress-stress correlations. As a result, the ratio of the shear and bulk moduli, which in isotropically-jammed systems vanishes as the jamming transition is approached from above, instead approaches a constant. Despite these striking differences, we argue that in a deeper sense, the shear jamming and isotropic jamming transitions actually have the same symmetry, and that the differences can be fully understood by rotating the six-dimensional basis of the elastic modulus tensor.

Robust detection in leak-prone population protocols - Alistarh, Dan-Adrian; Dudek, Bartłomiej; Kosowski, Adrian; Soloveichik, David; Uznański, Przemysław
In contrast to electronic computation, chemical computation is noisy and susceptible to a variety of sources of error, which has prevented the construction of robust complex systems. To be effective, chemical algorithms must be designed with an appropriate error model in mind. Here we consider the model of chemical reaction networks that preserve molecular count (population protocols), and ask whether computation can be made robust to a natural model of unintended “leak” reactions. Our definition of leak is motivated by both the particular spurious behavior seen when implementing chemical reaction networks with DNA strand displacement cascades, as well as the unavoidable side reactions in any implementation due to the basic laws of chemistry. We develop a new “Robust Detection” algorithm for the problem of fast (logarithmic time) single molecule detection, and prove that it is robust to this general model of leaks. Besides potential applications in single molecule detection, the error-correction ideas developed here might enable a new class of robust-by-design chemical algorithms. Our analysis is based on a non-standard hybrid argument, combining ideas from discrete analysis of population protocols with classic Markov chain techniques.

Time-space trade-offs in population protocols - Alistarh, Dan-Adrian; Aspnes, James; Eisenstat, David; Rivest, Ronald; Gelashvili, Rati
Population protocols are a popular model of distributed computing, in which randomly-interacting agents with little computational power cooperate to jointly perform computational tasks. Inspired by developments in molecular computation, and in particular DNA computing, recent algorithmic work has focused on the complexity of solving simple yet fundamental tasks in the population model, such as leader election (which requires convergence to a single agent in a special "leader" state), and majority (in which agents must converge to a decision as to which of two possible initial states had higher initial count). Known results point towards an inherent trade-off between the time complexity of such algorithms, and the space complexity, i.e. size of the memory available to each agent. In this paper, we explore this trade-off and provide new upper and lower bounds for majority and leader election. First, we prove a unified lower bound, which relates the space available per node with the time complexity achievable by a protocol: for instance, our result implies that any protocol solving either of these tasks for n agents using O(log log n) states must take (n=polylogn) expected time. This is the first result to characterize time complexity for protocols which employ super-constant number of states per node, and proves that fast, poly-logarithmic running times require protocols to have relatively large space costs. On the positive side, we give algorithms showing that fast, poly-logarithmic convergence time can be achieved using O(log2 n) space per node, in the case of both tasks. Overall, our results highlight a time complexity separation between O(log log n) and (log2 n) state space size for both majority and leader election in population protocols, and introduce new techniques, which should be applicable more broadly.

Forkscan: Conservative memory reclamation for modern operating systems - Alistarh, Dan-Adrian; Leiserson, William; Matveev, Alexander; Shavit, Nir
The problem of efficient concurrent memory reclamation in unmanaged languages such as C or C++ is one of the major challenges facing the parallelization of billions of lines of legacy code. Garbage collectors for C/C++ can be inefficient; thus, programmers are often forced to use finely-crafted concurrent memory reclamation techniques. These techniques can provide good performance, but require considerable programming effort to deploy, and have strict requirements, allowing the programmer very little room for error. In this work, we present Forkscan, a new conservative concurrent memory reclamation scheme which is fully automatic and surprisingly scalable. Forkscan's semantics place it between automatic garbage collectors (it requires the programmer to explicitly retire nodes before they can be reclaimed), and concurrent memory reclamation techniques (as it does not assume that nodes are completely unlinked from the data structure for correctness). Forkscan's implementation exploits these new semantics for efficiency: we leverage parallelism and optimized implementations of signaling and copy-on-write in modern operating systems to efficiently obtain and process consistent snapshots of memory that can be scanned concurrently with the normal program operation. Empirical evaluation on a range of classical concurrent data structure microbenchmarks shows that Forkscan can preserve the scalability of the original code, while maintaining an order of magnitude lower latency than automatic garbage collection, and demonstrating competitive performance with finely crafted memory reclamation techniques.

FPGA-accelerated dense linear machine learning: A precision-convergence trade-off - Kara, Kaan; Alistarh, Dan-Adrian; Alonso, Gustavo; Mutlu, Onur; Zhang, Ce
Stochastic gradient descent (SGD) is a commonly used algorithm for training linear machine learning models. Based on vector algebra, it benefits from the inherent parallelism available in an FPGA. In this paper, we first present a single-precision floating-point SGD implementation on an FPGA that provides similar performance as a 10-core CPU. We then adapt the design to make it capable of processing low-precision data. The low-precision data is obtained from a novel compression scheme - called stochastic quantization, specifically designed for machine learning applications. We test both full-precision and low-precision designs on various regression and classification data sets. We achieve up to an order of magnitude training speedup when using low-precision data compared to a full-precision SGD on the same FPGA and a state-of-the-art multi-core solution, while maintaining the quality of training. We open source the designs presented in this paper.

Unified Hanani Tutte theorem - Fulek, Radoslav; Kynčl, Jan; Pálvölgyi, Dömötör (Electronic Journal of Combinatorics)
We introduce a common generalization of the strong Hanani–Tutte theorem and the weak Hanani–Tutte theorem: if a graph G has a drawing D in the plane where every pair of independent edges crosses an even number of times, then G has a planar drawing preserving the rotation of each vertex whose incident edges cross each other evenly in D. The theorem is implicit in the proof of the strong Hanani–Tutte theorem by Pelsmajer, Schaefer and Štefankovič. We give a new, somewhat simpler proof.

Singulett-Sauerstoff in der aprotischen Natrium-O2-Batterie - Schafzahl, Lukas; Mahne, Nika; Schafzahl, Bettina; Wilkening, Martin; Slugovc, Christian; Borisov, Sergey M.; Freunberger, Stefan Alexander (Angewandte Chemie)
Aprotische Natrium‐O2‐Batterien basieren auf der reversiblen Bildung und Auflösung von Natriumsuperoxid (NaO2) während des Zellbetriebs. Nebenreaktionen des Elektrolyten und der Elektrode mit dem stark nukleophilen und basischen NaO2 führen zu mangelhafter Zyklenstabilität. Seine Reaktivität allein kann die Nebenreaktionen und schlechte Reversibilität jedoch nicht schlüssig erklären. Hier wird gezeigt, dass Singulett‐Sauerstoff (1O2) in allen Phasen des Betriebs entsteht und eine Hauptursache für Nebenreaktionen ist. 1O2 wurde in situ und ex situ mit einem 1O2‐Fänger detektiert, der schnell und selektiv ein Addukt mit 1O2 bildet. Mechanistisch betrachtet entsteht 1O2 entweder durch protonenunterstützte Disproportionierung von Superoxid während des Entladens, Lagerns und Ladens unter ca. 3.3 V oder durch direkte elektrochemische 1O2‐Entwicklung über ca. 3.3 V. Spuren von Wasser ermöglichen hohe Kapazitäten, beschleunigen aber auch Nebenreaktionen. Daher muss das hochreaktive 1O2 unbedingt kontrolliert werden, um die Zelle reversibel zu betreiben.

Polysaccharides in supercapacitors - Yee Liew, Soon; Thielemans, Wim; Freunberger, Stefan Alexander; Spirk, Stefan (Polysaccharide Based Supercapacitors)
In this part, the use of polysaccharides, either directly through composite approaches, or by carbonization will be described. In many cases, materials are obtained which are competitive in terms of capacitance and cycle lifetime. In this part, the use of polysaccharides, either directly through composite approaches, or by carbonization will be described. In many cases, materials are obtained which are competitive in terms of capacitance and cycle lifetime. The following part will focus mainly on cellulosic composites with conductive polymers since cellulose is most abundant and therefore has attracted much more research interest in this field whereas in the second part also other polysaccharides, such as chitin, xylans, alginates, pectins, dextrans and caragenaans have been used in carbonization experiments.

True performance metrics in beyond-intercalation batteries - Freunberger, Stefan Alexander (Nature Energy)
Beyond-intercalation batteries promise a step-change in energy storage compared to intercalation-based lithium-ion and sodium-ion batteries. However, only performance metrics that include all cell components and operation parameters can tell whether a true advance over intercalation batteries has been achieved.

Singlet oxygen generation as a major cause for parasitic reactions during cycling of aprotic lithium–oxygen batteries - Mahne, Nika; Schafzahl, Bettina; Leypold, Christian; Leypold, Mario; Grumm, Sandra; Leitgeb, Anita; Strohmeier, Gernot A.; Wilkening, Martin; Fontaine, Olivier; Kramer, Denis; Slugovc, Christian; Borisov, Sergey M.; et al. (Nature Energy)