A bacterial toxin-antitoxin system as a native defence element against RNA phages - Nikolic, Nela; Pleska, Maros; Bergmiller, Tobias; Guet, Calin C (Biology Letters)
Bacteria have evolved a wide range of defence strategies to protect themselves against bacterial viruses (phages). Most known bacterial antiphage defence systems target phages with DNA genomes, which raises the question of how bacteria defend against phages with RNA genomes. Bacterial toxin–antitoxin systems that cleave intracellular RNA could potentially protect bacteria against RNA phages, but this has not been explored experimentally. In this study, we investigated the role of a model toxin–antitoxin system, MazEF, in protecting Escherichia coli against two RNA phage species. When challenged with these phages, the native presence of mazEF moderately reduced population susceptibility and increased the survival of individual E. coli cells. Genomic analysis further revealed an underrepresentation of the MazF cleavage site in genomes of RNA phages infecting E. coli, indicating selection against cleavage. These results show that, in addition to other physiological roles, RNA-degrading toxin–antitoxin systems may also help defend against RNA phages.

Eight-partitioning points in 3D, and efficiently too - Aronov, Boris; Basit, Abdul; Ramesh, Indu; Tasinato, Gianluca; Wagner, Uli (Discrete & Computational Geometry)
An eight-partition of a finite set of points (respectively, of a continuous mass distribution) in R^3 consists of three planes that divide the space into 8 octants, such that each open octant contains at most 1/8 of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in R^3 admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: any mass distribution (or point set) in R^3 admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of n points in R^3 (with prescribed normal direction of one of the planes) in time O(n^7/3). A preliminary version of this work appeared in SoCG’24 (Aronov et al., 40th International Symposium on Computational Geometry, 2024).

Effect of assortative mating and sexual selection on polygenic barriers to gene flow - Surendranadh, Parvathy; Sachdeva, Himani (Evolution)
Assortative mating and sexual selection are widespread in nature and can play an important role in speciation by facilitating the buildup and maintenance of reproductive isolation (RI). However, their contribution to genome-wide suppression of gene flow during RI is rarely quantified. Here, we consider a polygenic “magic” trait that is divergently selected across two populations connected by migration, while also serving as the basis of assortative mating, thus generating sexual selection on one or both sexes. We obtain theoretical predictions for divergence at individual trait loci by assuming that the effect of all other loci on any locus can be encapsulated via an effective migration rate, which bears a simple relationship to measurable fitness components of migrants and various early-generation hybrids. Our analysis clarifies how “tipping points” (characterized by an abrupt collapse of adaptive divergence) arise, and when assortative mating can shift the critical level of migration beyond which divergence collapses. We quantify the relative contributions of viability and sexual selection to genome-wide barriers to gene flow and discuss how these depend on existing divergence levels. Our results suggest that effective migration rates provide a useful way of understanding genomic divergence, even in scenarios involving multiple, interacting mechanisms of RI.

MARLIN: Mixed-precision auto-regressive parallel inference on Large Language Models - Frantar, Elias; Castro, Roberto L.; Chen, Jiale; Hoefler, Torsten; Alistarh, Dan-Adrian (Proceedings of the 30th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming)
As inference on Large Language Models (LLMs) emerges as an important workload in machine learning applications, model weight quantization has become a standard technique for efficient GPU deployment. Quantization not only reduces model size, but has also been shown to yield substantial speedups for single-user inference, due to reduced memory movement, with low accuracy impact. Yet, it remains a key open question whether speedups are achievable also in batched settings with multiple parallel clients, which are highly relevant for practical serving. It is unclear whether GPU kernels can be designed to remain practically memory-bound, while supporting the substantially increased compute requirements of batched workloads. In this paper, we resolve this question positively by introducing a new design for Mixed-precision Auto-Regressive LINear kernels, called MARLIN. Concretely, given a model whose weights are compressed via quantization to, e.g., 4 bits per element, MARLIN shows that batchsizes up to 16-32 can be practically supported with close to maximum (4×) quantization speedup, and larger batchsizes up to 64-128 with gradually decreasing, but still significant, acceleration. MARLIN accomplishes this via a combination of techniques, such as asynchronous memory access, complex task scheduling and pipelining, and bespoke quantization support. Our experiments show that MARLIN's near-optimal performance on individual LLM layers across different scenarios can also lead to significant end-to-end LLM inference speedups (of up to 2.8×) when integrated with the popular vLLM open-source serving engine. Finally, we show that MARLIN is extensible to further compression techniques, like NVIDIA 2:4 sparsity, leading to additional speedups.

Quantum transport in the presence of a chiral molecular potential - Al Hyder, Ragheed; Lemeshko, Mikhail; Cappellaro, Alberto (The Journal of Chemical Physics)
We investigate quantum transport in a two-dimensional electron system coupled to a chiral molecular potential, demonstrating how molecular chirality and orientation affect charge and spin transport properties. We propose a minimal model for realizing true chiral symmetry breaking on a magnetized surface, with a crucial role played by the tilt angle of the molecular dipole with respect to the surface. For non-zero tilting, we show that the Hall response exhibits clear signatures of chirality-induced effects, in both charge- and spin-resolved observables. Concerning the former, tilted enantiomers produce asymmetric Hall conductances and, even more remarkably, the persistence of this feature in the absence of spin–orbit coupling (SOC) signals how the enantiospecific charge response results from electron scattering off the molecular potential. Concerning spin-resolved observables where SOC plays a relevant role, we reveal that chiral symmetry breaking is crucial in enabling spin-flipping processes.

Automated All-RF Tuning for Spin Qubit Readout and Control - Saez Mollejo, Jaime
This .zip file contains the data to reproduce the figures and supplementary figures of "Automated All-RF Tuning for Spin Qubit Readout and Control" by Cornelius Carlsson and Jaime Saez-Mollejo et al.

Reciprocity and inequality in social dilemmas - Hübner, Valentin
Cooperation, that is, one person paying a cost for another's benefit, is a fundamental principle without which no form of society could exist. The extent to which humans cooperate with each other is also an essential feature that differentiates them from other animals. Cooperation occurs even in the absence of altruistic motivations, when it is selfishly incentivised by the expectation of a future reward. For example, many economic interactions are well described that way. This kind of cooperation requires that people exhibit reciprocal behaviour that acts as a mechanism that rewards cooperation. With game-theoretic models, it is possible to formally study potential such mechanisms and under what conditions they can exist. This thesis contributes to this effort by analysing recently introduced models of cooperation that advance on previous work by taking into account the potential for pre-existing inequality among cooperating individuals as well as the different forms that reciprocity can take. Individuals may differ both intrinsically, in their abilities, as well as extrinsically, in the amount of resources they have available. Allowing for such differences in a model of cooperation helps to understand how inequality affects the potential for, and outcomes of, cooperation among unequals. In this thesis, it is shown that in the presence of intrinsic inequality, a similar unequal distribution of resources can increase the potential for cooperation. This effect is stronger the smaller the group is in which cooperation takes place. It is also shown that under particular assumptions, if the unequal members of a group vary the size of their contributions to a cooperative effort over time, they can thereby increase their efficiency and improve the collective outcome. Cooperative behaviour in a two-person interaction can be rewarded either by direct reciprocation whenever the same two people interact again, or indirectly by a third party who observed the interaction. In the latter case of indirect reciprocity, individuals are proximally rewarded by a good reputation, which ultimately translates to being rewarded with cooperative behaviour by others. This mechanism can enable selfishly motivated cooperation even in circumstances where individuals are unlikely to meet again, akin to how money facilitates trade. While these two forms of reciprocity have mostly been studied in isolation, this thesis analyses both direct and indirect reciprocity in a general model in order to compare their relative effectiveness under different circumstances. The contribution of this thesis is an extension of previous work regarding a specific kind of interaction, whose parameters allow for convenient mathematical analysis, to the most general set of possible interactions.

Files for "Evolutionary repurposing of a DNA segregation machinery into a cytoskeletal system controlling cyanobacterial cell shape" - Springstein, Benjamin L

Filamin A editing in myeloid cells reduces intestinal inflammation and protects from colitis - Gawish, Riem; Varada, Rajagopal; Deckert, Florian; Hladik, Anastasiya; Steinbichl, Linda; Cimatti, Laura; Milanovic, Katarina; Jain, Mamta; Torgasheva, Natalya; Tanzer, Andrea; De Paepe, Kim; Van De Wiele, Tom; et al. (Journal of Experimental Medicine)
Patho-mechanistic origins of ulcerative colitis are still poorly understood. The actin cross-linker filamin A (FLNA) impacts cellular responses through interaction with cytosolic proteins. Posttranscriptional A-to-I editing generates two forms of FLNA: genome-encoded FLNAQ and FLNAR. FLNA is edited in colon fibroblasts, smooth muscle cells, and endothelial cells. We found that the FLNA editing status determines colitis severity. Editing was highest in healthy colons and reduced during murine and human colitis. Mice that exclusively express FLNAR were highly resistant to DSS-induced colitis, whereas fully FLNAQ animals developed severe inflammation. While the genetic induction of FLNA editing influenced transcriptional states of structural cells and microbiome composition, we found that FLNAR exerts protection specifically via myeloid cells, which are physiologically unedited. Introducing fixed FLNAR did not hamper cell migration but reduced macrophage inflammation and rendered neutrophils less prone to NETosis. Thus, loss of FLNA editing correlates with colitis severity, and targeted editing of myeloid cells serves as a novel therapeutic approach in intestinal inflammation.

Unilateral incentive alignment in two-agent stochastic games - Mcavoy, Alex; Sehwag, Udari Madhushani; Hilbe, Christian; Chatterjee, Krishnendu; Barfuss, Wolfram; Su, Qi; Leonard, Naomi Ehrich; Plotkin, Joshua B. (Proceedings of the National Academy of Sciences)
Multiagent learning is challenging when agents face mixed-motivation interactions, where conflicts of interest arise as agents independently try to optimize their respective outcomes. Recent advancements in evolutionary game theory have identified a class of “zero-determinant” strategies, which confer an agent with significant unilateral control over outcomes in repeated games. Building on these insights, we present a comprehensive generalization of zero-determinant strategies to stochastic games, encompassing dynamic environments. We propose an algorithm that allows an agent to discover strategies enforcing predetermined linear (or approximately linear) payoff relationships. Of particular interest is the relationship in which both payoffs are equal, which serves as a proxy for fairness in symmetric games. We demonstrate that an agent can discover strategies enforcing such relationships through experience alone, without coordinating with an opponent. In finding and using such a strategy, an agent (“enforcer”) can incentivize optimal and equitable outcomes, circumventing potential exploitation. In particular, from the opponent’s viewpoint, the enforcer transforms a mixed-motivation problem into a cooperative problem, paving the way for more collaboration and fairness in multiagent systems.

Near-optimal leader election in population protocols on graphs - Alistarh, Dan-Adrian; Rybicki, Joel; Voitovych, Sasha (Distributed Computing)
In the stochastic population protocol model, we are given a connected graph with n nodes, and in every time step, a scheduler samples an edge of the graph uniformly at random and the nodes connected by this edge interact. A fundamental task in this model is stable leader election, in which all nodes start in an identical state and the aim is to reach a configuration in which (1) exactly one node is elected as leader and (2) this node remains as the unique leader no matter what sequence of interactions follows. On cliques, the complexity of this problem has recently been settled: time-optimal protocols stabilize in (n log n) expected steps using (log log n) states, whereas protocols that use O(1) states require (n2) expected steps. In this work, we investigate the complexity of stable leader election on graphs. We provide the first non-trivial time lower bounds on general graphs, showing that, when moving beyond cliques, the complexity of stable leader election can range from O(1) to (n3) expected steps. We describe a protocol that is time-optimal on many graph families, but uses polynomially-many states. In contrast, we give a near-time-optimal protocol that uses only O(log2 n) states that is at most a factor O(log n) slower. Finally, we observe that for many graphs the constant-state protocol of Beauquier et al. [OPODIS 2013] is at most a factor O(n log n) slower than the fast polynomial-state protocol, and among constant-state protocols, this protocol has near-optimal average case complexity on dense random graphs.

Levels in arrangements: Linear relations, the g-matrix, and applications to crossing numbers - Streltsova, Elizaveta; Wagner, Uli (41st International Symposium on Computational Geometry)
A long-standing conjecture of Eckhoff, Linhart, and Welzl, which would generalize McMullen’s Upper Bound Theorem for polytopes and refine asymptotic bounds due to Clarkson, asserts that for k ⩽ ⌊(n-d-2)/2⌋, the complexity of the (⩽ k)-level in a simple arrangement of n hemispheres in S^d is maximized for arrangements that are polar duals of neighborly d-polytopes. We prove this conjecture in the case n = d+4. By Gale duality, this implies the following result about crossing numbers: In every spherical arc drawing of K_n in S² (given by a set V ⊂ S² of n unit vectors connected by spherical arcs), the number of crossings is at least 1/4 ⌊n/2⌋ ⌊(n-1)/2⌋ ⌊(n-2)/2⌋ ⌊(n-3)/2⌋. This lower bound is attained if every open linear halfspace contains at least ⌊(n-2)/2⌋ of the vectors in V. Moreover, we determine the space of all linear and affine relations that hold between the face numbers of levels in simple arrangements of n hemispheres in S^d. This completes a long line of research on such relations, answers a question posed by Andrzejak and Welzl in 2003, and generalizes the classical fact that the Dehn-Sommerville relations generate all linear relations between the face numbers of simple polytopes (which correspond to the 0-level). To prove these results, we introduce the notion of the g-matrix, which encodes the face numbers of levels in an arrangement and generalizes the classical g-vector of a polytope.

On spheres with k points inside - Edelsbrunner, Herbert; Garber, Alexey; Saghafian, Morteza (41st International Symposium on Computational Geometry)
We generalize a classical result by Boris Delaunay that introduced Delaunay triangulations. In particular, we prove that for a locally finite and coarsely dense generic point set A in ℝ^d, every generic point of ℝ^d belongs to exactly binom(d+k,d) simplices whose vertices belong to A and whose circumspheres enclose exactly k points of A. We extend this result to the cases in which the points are weighted, and when A contains only finitely many points in ℝ^d or in 𝕊^d. Furthermore, we use the result to give a new geometric proof for the fact that volumes of hypersimplices are Eulerian numbers.

Banana trees for the persistence in time series experimentally - Ost, Lara; Cultrera di Montesano, Sebastiano; Edelsbrunner, Herbert (41st International Symposium on Computational Geometry)
In numerous fields, dynamic time series data require continuous updates, necessitating efficient data processing techniques for accurate analysis. This paper examines the banana tree data structure, specifically designed to efficiently maintain the multi-scale topological descriptor commonly known as persistent homology for dynamically changing time series data. We implement this data structure and conduct an experimental study to assess its properties and runtime for update operations. Our findings indicate that banana trees are highly effective with unbiased random data, outperforming state-of-the-art static algorithms in these scenarios. Additionally, our results show that real-world time series share structural properties with unbiased random walks, suggesting potential practical utility for our implementation.

Hardness of 4-colouring G-colourable graphs - Avvakumov, Sergey; Filakovský, Marek; Opršal, Jakub; Tasinato, Gianluca; Wagner, Uli (Proceedings of the 57th Annual ACM Symposium on Theory of Computing)
We study the complexity of a class of promise graph homomorphism problems. For a fixed graph H, the H-colouring problem is to decide whether a given graph has a homomorphism to H. By a result of Hell and Nešetřil, this problem is NP-hard for any non-bipartite loop-less graph H. Brakensiek and Guruswami [SODA 2018] conjectured the hardness extends to promise graph homomorphism problems as follows: fix a pair of non-bipartite loop-less graphs G, H such that there is a homomorphism from G to H, it is NP-hard to distinguish between graphs that are G-colourable and those that are not H-colourable. We confirm this conjecture in the cases when both G and H are 4-colourable. This is a common generalisation of previous results of Khanna, Linial, and Safra [Comb. 20(3): 393-415 (2000)] and of Krokhin and Opršal [FOCS 2019]. The result is obtained by combining the algebraic approach to promise constraint satisfaction with methods of topological combinatorics and equivariant obstruction theory.

Sex chromosome evolution in action in fourspine sticklebacks - Vicoso, Beatriz (Trends in Ecology and Evolution)
The suppression of recombination between young X and Y chromosomes is a crucial step in their evolution, but why it occurs is not known. The detailed characterization of the polymorphic sex chromosomes of the fourspine stickleback by Liu et al. promises to shed new light on this longstanding question.

Arabidopsis phospholipase Dζ2 facilitates vacuolar acidification and autophagy under phosphorus starvation by interacting with VATD - Guan, Bin; Xie, Ke Xuan; Du, Xin Qiao; Bai, Yu Xuan; Hao, Peng Chao; Lin, Wen Hui; Friml, Jiří; Xue, Hong Wei (Cell Reports)
Vacuolar acidification is crucial for the homeostasis of intracellular pH and the recycling of proteins and nutrients in cells, thereby playing important roles in various physiological processes related to vacuolar function. The key factors regulating vacuolar acidification and underlying mechanisms remain unclear. Here, we report that Arabidopsis phospholipase Dζ2 (PLDζ2) promotes the acidification of the vacuolar lumen to stimulate autophagic degradation under phosphorus deficiency. The pldζ2 mutant massively accumulates autophagic structures while exhibiting premature leaf senescence under nutrient starvation. Impaired autophagic flux, lytic vacuole morphology, and lytic degradation in pldζ2 indicate that PLDζ2 regulates autophagy by affecting the vacuolar function. PLDζ2 locates in both tonoplast and cytoplasm. Genetic, structural, and biochemical studies demonstrate that PLDζ2 directly interacts with vacuolar-type ATPase (V-ATPase) subunit D (VATD) to promote vacuolar acidification and autophagy under phosphorus starvation. These findings reveal the importance of V-ATPase and vacuolar pH in autophagic activity and provide clues in elucidating the regulatory mechanism of vacuolar acidification.

The configuration of the vacuole is driven by clathrin-mediated trafficking in root cells of Arabidopsis thaliana - Osorio-Navarro, Claudio; Neira-Valenzuela, Gabriel; Sierra, Paula; Adamowski, Maciek; Toledo, Jorge; Norambuena, Lorena (Journal of Experimental Botany)
The central vacuole is a multifunctional organelle with the most significant occupancy in a differentiated plant cell. Plants depend on the function of the vacuole for critical development, growth, and environmental responses. As the cell expands, the vacuole changes shape and size, increasing its membrane and luminal content. The set of these events is called the vacuolar configuration process, which has not been well described. Our research highlights the impact of plasma membrane internalization on vacuole morphology during the vacuolar configuration process. We observed a direct correlation between differential endocytosis rates and the enrichment of vacuolar membranous structures. Chemical and genetic interference with clathrin-mediated endocytosis (CME) revealed that it is required for the vacuolar configuration of growing root cells. The contribution of CME to the vacuole configuration process co-occurs with the induction of post-trans-Golgi network (TGN)/early endosome (EE) trafficking with the participation of the Rab GTPases ARA6 and ARA7. Our results show that the CME plays an active role during vacuole configuration, most probably carrying the material that allows the establishment of the vacuole in elongating cells. Since membrane trafficking through the EE/TGN is required to reach the vacuole, additional players must be defined.

Scalable mechanistic neural networks - Chen, Jiale; Yao, Dingling; Pervez, Adeel A; Alistarh, Dan-Adrian; Locatello, Francesco (13th International Conference on Learning Representations)
We propose Scalable Mechanistic Neural Network (S-MNN), an enhanced neural network framework designed for scientific machine learning applications involving long temporal sequences. By reformulating the original Mechanistic Neural Network (MNN) (Pervez et al., 2024), we reduce the computational time and space complexities from cubic and quadratic with respect to the sequence length, respectively, to linear. This significant improvement enables efficient modeling of long-term dynamics without sacrificing accuracy or interpretability. Extensive experiments demonstrate that S-MNN matches the original MNN in precision while substantially reducing computational resources. Consequently, S-MNN can drop-in replace the original MNN in applications, providing a practical and efficient tool for integrating mechanistic bottlenecks into neural network models of complex dynamical systems. Source code is available at https://github.com/IST-DASLab/ScalableMNN.

LDAdam: Adaptive optimization from low-dimensional gradient statistics - Robert, Thomas; Safaryan, Mher; Modoranu, Ionut-Vlad; Alistarh, Dan-Adrian (13th International Conference on Learning Representations)
We introduce LDAdam, a memory-efficient optimizer for training large models, that performs adaptive optimization steps within lower dimensional subspaces, while consistently exploring the full parameter space during training. This strategy keeps the optimizer's memory footprint to a fraction of the model size. LDAdam relies on a new projection-aware update rule for the optimizer states that allows for transitioning between subspaces, i.e., estimation of the statistics of the projected gradients. To mitigate the errors due to low-rank projection, LDAdam integrates a new generalized error feedback mechanism, which explicitly accounts for both gradient and optimizer state compression. We prove the convergence of LDAdam under standard assumptions, and provide empirical evidence that LDAdam allows for efficient fine-tuning and pre-training of language models.