In-situ engineered highly crystalline polythiophene empowered electrochemical capacitor-I: Synthesis, characterization, and electrochemical charge storage - Mahato, Neelima; Singh, Saurabh; Sreekanth, T. V.M.; Yoo, Kisoo; Kim, Jonghoon (Materials Letters)
We report on synthesis of highly crystalline polythiophene and its application in supercapacitor electrodes. The material exhibits a remarkably stable electrochemical behavior and an excellent device performance. The device delivers an electrode specific capacitance (Csp) of 129.13F g−1, Cell Csp of 32.28F g−1 at 0.5 A/g; energy, and power densities of ∼ 3 Wh kg−1 and 250 W kg -1, respectively at 0.5 A/g. Also, it exhibits an excellent retention of Cell Csp and coulombic efficiency up to ∼ 95 % over 10,000 continuous galvanostatic charge discharge (GCD) cycles indicating a remarkable performance by a standalone, pristine and undoped polythiophene. Electrochemical impedance spectroscopy (EIS) studies further suggest material’s stable capacitive behavior. The material’s enhanced electrochemical properties, stable behavior and outstanding performance in device application are attributed to the crystalline phases present in the polymer matrix achievable via a slow rate of synthesis; overall, an edge over other conventional synthesis methods.

Limits to selection on standing variation in an asexual population - Barton, Nicholas H; Sachdeva, Himani (Theoretical Population Biology)
We consider how a population of N haploid individuals responds to directional selection on standing variation, with no new variation from recombination or mutation. Individuals have trait values z1,…,zN, which are drawn from a distribution ψ; the fitness of individual i is proportional to [Formula: see text] . For illustration, we consider the Laplace and Gaussian distributions, which are parametrised only by the variance V0, and show that for large N, there is a scaling limit which depends on a single parameter NV0. When selection is weak relative to drift (NV0≪1), the variance decreases exponentially at rate 1/N, and the expected ultimate gain in log fitness (scaled by V0), is just NV0, which is the same as Robertson's (1960) prediction for a sexual population. In contrast, when selection is strong relative to drift (NV0≫1), the ultimate gain can be found by approximating the establishment of alleles by a branching process in which each allele competes independently with the population mean and the fittest allele to establish is certain to fix. Then, if the probability of survival to time t∼1/V0 of an allele with value z is P(z), with mean P¯, the winning allele is the fittest of NP¯ survivors drawn from a distribution ψP/P¯. The expected ultimate change is ∼2log(1.15NV0) for a Gaussian distribution, and ∼-12log0.36NV0-log-log0.36NV0 for a Laplace distribution. This approach also predicts the variability of the process, and its dynamics; we show that in the strong selection regime, the expected genetic variance decreases as ∼t-3 at large times. We discuss how these results may be related to selection on standing variation that is spread along a linear chromosome.

Unraveling the mechanisms of PAMless DNA interrogation by SpRY-Cas9 - Hibshman, Grace N.; Bravo, Jack Peter Kelly; Hooper, Matthew M.; Dangerfield, Tyler L.; Zhang, Hongshan; Finkelstein, Ilya J.; Johnson, Kenneth A.; Taylor, David W. (Nature Communications)
CRISPR-Cas9 is a powerful tool for genome editing, but the strict requirement for an NGG protospacer-adjacent motif (PAM) sequence immediately next to the DNA target limits the number of editable genes. Recently developed Cas9 variants have been engineered with relaxed PAM requirements, including SpG-Cas9 (SpG) and the nearly PAM-less SpRY-Cas9 (SpRY). However, the molecular mechanisms of how SpRY recognizes all potential PAM sequences remains unclear. Here, we combine structural and biochemical approaches to determine how SpRY interrogates DNA and recognizes target sites. Divergent PAM sequences can be accommodated through conformational flexibility within the PAM-interacting region, which facilitates tight binding to off-target DNA sequences. Nuclease activation occurs ~1000-fold slower than for Streptococcus pyogenes Cas9, enabling us to directly visualize multiple on-pathway intermediate states. Experiments with SpG position it as an intermediate enzyme between Cas9 and SpRY. Our findings shed light on the molecular mechanisms of PAMless genome editing.

Single-cell sortChIC identifies hierarchical chromatin dynamics during hematopoiesis - Zeller, Peter; Yeung, Jake; Viñas Gaza, Helena; de Barbanson, Buys Anton; Bhardwaj, Vivek; Florescu, Maria; van der Linden, Reinier; van Oudenaarden, Alexander (Nature Genetics)
Post-translational histone modifications modulate chromatin activity to affect gene expression. How chromatin states underlie lineage choice in single cells is relatively unexplored. We develop sort-assisted single-cell chromatin immunocleavage (sortChIC) and map active (H3K4me1 and H3K4me3) and repressive (H3K27me3 and H3K9me3) histone modifications in the mouse bone marrow. During differentiation, hematopoietic stem and progenitor cells (HSPCs) acquire active chromatin states mediated by cell-type-specifying transcription factors, which are unique for each lineage. By contrast, most alterations in repressive marks during differentiation occur independent of the final cell type. Chromatin trajectory analysis shows that lineage choice at the chromatin level occurs at the progenitor stage. Joint profiling of H3K4me1 and H3K9me3 demonstrates that cell types within the myeloid lineage have distinct active chromatin but share similar myeloid-specific heterochromatin states. This implies a hierarchical regulation of chromatin during hematopoiesis: heterochromatin dynamics distinguish differentiation trajectories and lineages, while euchromatin dynamics reflect cell types within lineages.
Keywords: Genetics

Molecular Cloning Using In Vivo DNA Assembly - Arroyo-Urea, Sandra; Watson, Jake; García-Nafría, Javier (DNA Manipulation and Analysis)
Here we describe the in vivo DNA assembly approach, where molecular cloning procedures are performed using an E. coli recA-independent recombination pathway, which assembles linear fragments of DNA with short homologous termini. This pathway is present in all standard laboratory E. coli strains and, by bypassing the need for in vitro DNA assembly, allows simplified molecular cloning to be performed without the plasmid instability issues associated with specialized recombination-cloning bacterial strains. The methodology requires specific primer design and can perform all standard plasmid modifications (insertions, deletions, mutagenesis, and sub-cloning) in a rapid, simple, and cost-efficient manner, as it does not require commercial kits or specialized bacterial strains. Additionally, this approach can be used to perform complex procedures such as multiple modifications to a plasmid, as up to 6 linear fragments can be assembled in vivo by this recombination pathway. Procedures generally require less than 3 h, involving PCR amplification, DpnI digestion of template DNA, and transformation, upon which circular plasmids are assembled. In this chapter we describe the requirements, procedure, and potential pitfalls when using this technique, as well as protocol variations to overcome the most common issues.

Unexpected scaling in path copying trees - Aksenov, Vitaly; Brown, Trevor A; Fedorov, Alexander; Kokorin, Ilya (Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming)
Although a wide variety of handcrafted concurrent data structures have been proposed, there is considerable interest in universal approaches (Universal Constructions or UCs) for building concurrent data structures. UCs (semi-)automatically convert a sequential data structure into a concurrent one. The simplest approach uses locks [3, 6] that protect a sequential data structure and allow only one process to access it at a time. However, the resulting data structure is blocking. Most work on UCs instead focuses on obtaining non-blocking progress guarantees such as obstruction-freedom, lock-freedom or wait-freedom. Many non-blocking UCs have appeared. Key examples include the seminal wait-free UC [2] by Herlihy, a NUMA-aware UC [10] by Yi et al., and an efficient UC for large objects [1] by Fatourou et al.

Bubaak: Runtime monitoring of program verifiers - Chalupa, Marek; Henzinger, Thomas A (Tools and Algorithms for the Construction and Analysis of Systems)
The main idea behind BUBAAK is to run multiple program analyses in parallel and use runtime monitoring and enforcement to observe and control their progress in real time. The analyses send information about (un)explored states of the program and discovered invariants to a monitor. The monitor processes the received data and can force an analysis to stop the search of certain program parts (which have already been analyzed by other analyses), or to make it utilize a program invariant found by another analysis. At SV-COMP 2023, the implementation of data exchange between the monitor and the analyses was not yet completed, which is why BUBAAK only ran several analyses in parallel, without any coordination. Still, BUBAAK won the meta-category FalsificationOverall and placed very well in several other (sub)-categories of the competition.

Vamos: Middleware for best-effort third-party monitoring - Chalupa, Marek; Mühlböck, Fabian; Muroya Lei, Stefanie; Henzinger, Thomas A (Fundamental Approaches to Software Engineering)
As the complexity and criticality of software increase every year, so does the importance of run-time monitoring. Third-party monitoring, with limited knowledge of the monitored software, and best-effort monitoring, which keeps pace with the monitored software, are especially valuable, yet underexplored areas of run-time monitoring. Most existing monitoring frameworks do not support their combination because they either require access to the monitored code for instrumentation purposes or the processing of all observed events, or both. We present a middleware framework, VAMOS, for the run-time monitoring of software which is explicitly designed to support third-party and best-effort scenarios. The design goals of VAMOS are (i) efficiency (keeping pace at low overhead), (ii) flexibility (the ability to monitor black-box code through a variety of different event channels, and the connectability to monitors written in different specification languages), and (iii) ease-of-use. To achieve its goals, VAMOS combines aspects of event broker and event recognition systems with aspects of stream processing systems. We implemented a prototype toolchain for VAMOS and conducted experiments including a case study of monitoring for data races. The results indicate that VAMOS enables writing useful yet efficient monitors, is compatible with a variety of event sources and monitor specifications, and simplifies key aspects of setting up a monitoring system from scratch.

Certifying giant nonprimes - Hoffmann, Charlotte; Hubáček, Pavel; Kamath, Chethan; Pietrzak, Krzysztof Z (Public-Key Cryptography - PKC 2023)
GIMPS and PrimeGrid are large-scale distributed projects dedicated to searching giant prime numbers, usually of special forms like Mersenne and Proth primes. The numbers in the current search-space are millions of digits large and the participating volunteers need to run resource-consuming primality tests. Once a candidate prime N has been found, the only way for another party to independently verify the primality of N used to be by repeating the expensive primality test. To avoid the need for second recomputation of each primality test, these projects have recently adopted certifying mechanisms that enable efficient verification of performed tests. However, the mechanisms presently in place only detect benign errors and there is no guarantee against adversarial behavior: a malicious volunteer can mislead the project to reject a giant prime as being non-prime. In this paper, we propose a practical, cryptographically-sound mechanism for certifying the non-primality of Proth numbers. That is, a volunteer can – parallel to running the primality test for N – generate an efficiently verifiable proof at a little extra cost certifying that N is not prime. The interactive protocol has statistical soundness and can be made non-interactive using the Fiat-Shamir heuristic. Our approach is based on a cryptographic primitive called Proof of Exponentiation (PoE) which, for a group G, certifies that a tuple (x,y,T)∈G2×N satisfies x2T=y (Pietrzak, ITCS 2019 and Wesolowski, J. Cryptol. 2020). In particular, we show how to adapt Pietrzak’s PoE at a moderate additional cost to make it a cryptographically-sound certificate of non-primality.

A learner-verifier framework for neural network controllers and certificates of stochastic systems - Chatterjee, Krishnendu; Henzinger, Thomas A; Lechner, Mathias; Zikelic, Dorde (Tools and Algorithms for the Construction and Analysis of Systems)
Reinforcement learning has received much attention for learning controllers of deterministic systems. We consider a learner-verifier framework for stochastic control systems and survey recent methods that formally guarantee a conjunction of reachability and safety properties. Given a property and a lower bound on the probability of the property being satisfied, our framework jointly learns a control policy and a formal certificate to ensure the satisfaction of the property with a desired probability threshold. Both the control policy and the formal certificate are continuous functions from states to reals, which are learned as parameterized neural networks. While in the deterministic case, the certificates are invariant and barrier functions for safety, or Lyapunov and ranking functions for liveness, in the stochastic case the certificates are supermartingales. For certificate verification, we use interval arithmetic abstract interpretation to bound the expected values of neural network functions.

Computing adequately permissive assumptions for synthesis - Anand, Ashwani; Mallik, Kaushik; Nayak, Satya Prakash; Schmuck, Anne Kathrin (TACAS 2023: Tools and Algorithms for the Construction and Analysis of Systems)
We automatically compute a new class of environment assumptions in two-player turn-based finite graph games which characterize an “adequate cooperation” needed from the environment to allow the system player to win. Given an ω-regular winning condition Φ for the system player, we compute an ω-regular assumption Ψ for the environment player, such that (i) every environment strategy compliant with Ψ allows the system to fulfill Φ (sufficiency), (ii) Ψ can be fulfilled by the environment for every strategy of the system (implementability), and (iii) Ψ does not prevent any cooperative strategy choice (permissiveness). For parity games, which are canonical representations of ω-regular games, we present a polynomial-time algorithm for the symbolic computation of adequately permissive assumptions and show that our algorithm runs faster and produces better assumptions than existing approaches—both theoretically and empirically. To the best of our knowledge, for ω -regular games, we provide the first algorithm to compute sufficient and implementable environment assumptions that are also permissive.

A simple algorithm for higher-order Delaunay mosaics and alpha shapes - Edelsbrunner, Herbert; Osang, Georg F (Algorithmica)
We present a simple algorithm for computing higher-order Delaunay mosaics that works in Euclidean spaces of any finite dimensions. The algorithm selects the vertices of the order-k mosaic from incrementally constructed lower-order mosaics and uses an algorithm for weighted first-order Delaunay mosaics as a black-box to construct the order-k mosaic from its vertices. Beyond this black-box, the algorithm uses only combinatorial operations, thus facilitating easy implementation. We extend this algorithm to compute higher-order α-shapes and provide open-source implementations. We present experimental results for properties of higher-order Delaunay mosaics of random point sets.

Quantitative safety and liveness - Henzinger, Thomas A; Mazzocchi, Nicolas Adrien; Sarac, Naci E (26th International Conference Foundations of Software Science and Computation Structures)
Safety and liveness are elementary concepts of computation, and the foundation of many verification paradigms. The safety-liveness classification of boolean properties characterizes whether a given property can be falsified by observing a finite prefix of an infinite computation trace (always for safety, never for liveness). In quantitative specification and verification, properties assign not truth values, but quantitative values to infinite traces (e.g., a cost, or the distance to a boolean property). We introduce quantitative safety and liveness, and we prove that our definitions induce conservative quantitative generalizations of both (1)~the safety-progress hierarchy of boolean properties and (2)~the safety-liveness decomposition of boolean properties. In particular, we show that every quantitative property can be written as the pointwise minimum of a quantitative safety property and a quantitative liveness property. Consequently, like boolean properties, also quantitative properties can be min-decomposed into safety and liveness parts, or alternatively, max-decomposed into co-safety and co-liveness parts. Moreover, quantitative properties can be approximated naturally. We prove that every quantitative property that has both safe and co-safe approximations can be monitored arbitrarily precisely by a monitor that uses only a finite number of states.

Highly adaptive nature of group 15 tris(quinolyl) ligands─studies with coinage metals - García-Romero, Álvaro; Waters, Jessica E.; Jethwa, Rajesh B; Bond, Andrew D.; Colebatch, Annie L.; García-Rodríguez, Raúl; Wright, Dominic S. (Inorganic Chemistry)
The substitution of heavier, more metallic atoms into classical organic ligand frameworks provides an important strategy for tuning ligand properties, such as ligand bite and donor character, and is the basis for the emerging area of main-group supramolecular chemistry. In this paper, we explore two new ligands [E(2-Me-8-qy)3] [E = Sb (1), Bi (2); qy = quinolyl], allowing a fundamental comparison of their coordination behavior with classical tris(2-pyridyl) ligands of the type [E′(2-py)3] (E = a range of bridgehead atoms and groups, py = pyridyl). A range of new coordination modes to Cu+, Ag+, and Au+ is seen for 1 and 2, in the absence of steric constraints at the bridgehead and with their more remote N-donor atoms. A particular feature is the adaptive nature of these new ligands, with the ability to adjust coordination mode in response to the hard–soft character of coordinated metal ions, influenced also by the character of the bridgehead atom (Sb or Bi). These features can be seen in a comparison between [Cu2{Sb(2-Me-8-qy)3}2](PF6)2 (1·CuPF6) and [Cu{Bi(2-Me-8-qy)3}](PF6) (2·CuPF6), the first containing a dimeric cation in which 1 adopts an unprecedented intramolecular N,N,Sb-coordination mode while in the second, 2 adopts an unusual N,N,(π-)C coordination mode. In contrast, the previously reported analogous ligands [E(6-Me-2-py)3] (E = Sb, Bi; 2-py = 2-pyridyl) show a tris-chelating mode in their complexes with CuPF6, which is typical for the extensive tris(2-pyridyl) family with a range of metals. The greater polarity of the Bi–C bond in 2 results in ligand transfer reactions with Au(I). Although this reactivity is not in itself unusual, the characterization of several products by single-crystal X-ray diffraction provides snapshots of the ligand transfer reaction involved, with one of the products (the bimetallic complex [(BiCl){ClAu2(2-Me-8-qy)3}] (8)) containing a Au2Bi core in which the shortest Au → Bi donor–acceptor bond to date is observed.

Topological charges of periodically kicked molecules - Karle, Volker; Ghazaryan, Areg; Lemeshko, Mikhail (Physical Review Letters)
We show that the simplest of existing molecules—closed-shell diatomics not interacting with one another—host topological charges when driven by periodic far-off-resonant laser pulses. A periodically kicked molecular rotor can be mapped onto a “crystalline” lattice in angular momentum space. This allows us to define quasimomenta and the band structure in the Floquet representation, by analogy with the Bloch waves of solid-state physics. Applying laser pulses spaced by 1/3 of the molecular rotational period creates a lattice with three atoms per unit cell with staggered hopping. Within the synthetic dimension of the laser strength, we discover Dirac cones with topological charges. These Dirac cones, topologically protected by reflection and time-reversal symmetry, are reminiscent of (although not equivalent to) that seen in graphene. They—and the corresponding edge states—are broadly tunable by adjusting the laser strength and can be observed in present-day experiments by measuring molecular alignment and populations of rotational levels. This paves the way to study controllable topological physics in gas-phase experiments with small molecules as well as to classify dynamical molecular states by their topological invariants.

Superdiffusive energy transport in kinetically constrained models - Ljubotina, Marko; Desaules, Jean Yves; Serbyn, Maksym; Papić, Zlatko (Physical Review X)
Universal nonequilibrium properties of isolated quantum systems are typically probed by studying transport of conserved quantities, such as charge or spin, while transport of energy has received considerably less attention. Here, we study infinite-temperature energy transport in the kinetically constrained PXP model describing Rydberg atom quantum simulators. Our state-of-the-art numerical simulations, including exact diagonalization and time-evolving block decimation methods, reveal the existence of two distinct transport regimes. At moderate times, the energy-energy correlation function displays periodic oscillations due to families of eigenstates forming different su(2) representations hidden within the spectrum. These families of eigenstates generalize the quantum many-body scarred states found in previous works and leave an imprint on the infinite-temperature energy transport. At later times, we observe a long-lived superdiffusive transport regime that we attribute to the proximity of a nearby integrable point. While generic strong deformations of the PXP model indeed restore diffusive transport, adding a strong chemical potential intriguingly gives rise to a well-converged superdiffusive exponent z≈3/2. Our results suggest constrained models to be potential hosts of novel transport regimes and call for developing an analytic understanding of their energy transport.

Directionality-aware design of embroidery patterns - Liu, Zhenyuan; Piovarci, Michael; Hafner, Christian; Charrondiere, Raphael; Bickel, Bernd (Computer Graphics Forum)
Embroidery is a long-standing and high-quality approach to making logos and images on textiles. Nowadays, it can also be performed via automated machines that weave threads with high spatial accuracy. A characteristic feature of the appearance of the threads is a high degree of anisotropy. The anisotropic behavior is caused by depositing thin but long strings of thread. As a result, the stitched patterns convey both color and direction. Artists leverage this anisotropic behavior to enhance pure color images with textures, illusions of motion, or depth cues. However, designing colorful embroidery patterns with prescribed directionality is a challenging task, one usually requiring an expert designer. In this work, we propose an interactive algorithm that generates machine-fabricable embroidery patterns from multi-chromatic images equipped with user-specified directionality fields.We cast the problem of finding a stitching pattern into vector theory. To find a suitable stitching pattern, we extract sources and sinks from the divergence field of the vector field extracted from the input and use them to trace streamlines. We further optimize the streamlines to guarantee a smooth and connected stitching pattern. The generated patterns approximate the color distribution constrained by the directionality field. To allow for further artistic control, the trade-off between color match and directionality match can be interactively explored via an intuitive slider. We showcase our approach by fabricating several embroidery paths.
Keywords: embroidery; design; directionality; density; image

Tunable directional photon scattering from a pair of superconducting qubits - Redchenko, Elena; Poshakinskiy, Alexander V.; Sett, Riya; Zemlicka, Martin; Poddubny, Alexander N.; Fink, Johannes M (Nature Communications)
The ability to control the direction of scattered light is crucial to provide flexibility and scalability for a wide range of on-chip applications, such as integrated photonics, quantum information processing, and nonlinear optics. Tunable directionality can be achieved by applying external magnetic fields that modify optical selection rules, by using nonlinear effects, or interactions with vibrations. However, these approaches are less suitable to control microwave photon propagation inside integrated superconducting quantum devices. Here, we demonstrate on-demand tunable directional scattering based on two periodically modulated transmon qubits coupled to a transmission line at a fixed distance. By changing the relative phase between the modulation tones, we realize unidirectional forward or backward photon scattering. Such an in-situ switchable mirror represents a versatile tool for intra- and inter-chip microwave photonic processors. In the future, a lattice of qubits can be used to realize topological circuits that exhibit strong nonreciprocity or chirality.

Bias in the representative volume element method: Periodize the ensemble instead of its realizations - Clozeau, Nicolas; Josien, Marc; Otto, Felix; Xu, Qiang (Foundations of Computational Mathematics)
We study the representative volume element (RVE) method, which is a method to approximately infer the effective behavior ahom of a stationary random medium. The latter is described by a coefficient field a(x) generated from a given ensemble ⟨⋅⟩ and the corresponding linear elliptic operator −∇⋅a∇. In line with the theory of homogenization, the method proceeds by computing d=3 correctors (d denoting the space dimension). To be numerically tractable, this computation has to be done on a finite domain: the so-called representative volume element, i.e., a large box with, say, periodic boundary conditions. The main message of this article is: Periodize the ensemble instead of its realizations. By this, we mean that it is better to sample from a suitably periodized ensemble than to periodically extend the restriction of a realization a(x) from the whole-space ensemble ⟨⋅⟩. We make this point by investigating the bias (or systematic error), i.e., the difference between ahom and the expected value of the RVE method, in terms of its scaling w.r.t. the lateral size L of the box. In case of periodizing a(x), we heuristically argue that this error is generically O(L−1). In case of a suitable periodization of ⟨⋅⟩ , we rigorously show that it is O(L−d). In fact, we give a characterization of the leading-order error term for both strategies and argue that even in the isotropic case it is generically non-degenerate. We carry out the rigorous analysis in the convenient setting of ensembles ⟨⋅⟩ of Gaussian type, which allow for a straightforward periodization, passing via the (integrable) covariance function. This setting has also the advantage of making the Price theorem and the Malliavin calculus available for optimal stochastic estimates of correctors. We actually need control of second-order correctors to capture the leading-order error term. This is due to inversion symmetry when applying the two-scale expansion to the Green function. As a bonus, we present a stream-lined strategy to estimate the error in a higher-order two-scale expansion of the Green function.

Visible-light-mediated oxidative debenzylation of 3-O-Benzyl-1,2:5,6-di-O-isopropylidene-α-D-glucofuranose - Madani, Amiera; Sletten, Eric T.; Cavedon, Cristian; Seeberger, Peter H.; Pieber, Bartholomäus (Organic Syntheses)

Highly irregular separated nets - Dymond, Michael; Kaluza, Vojtech (Israel Journal of Mathematics)
In 1998 Burago and Kleiner and (independently) McMullen gave examples of separated nets in Euclidean space which are non-bilipschitz equivalent to the integer lattice. We study weaker notions of equivalence of separated nets and demonstrate that such notions also give rise to distinct equivalence classes. Put differently, we find occurrences of particularly strong divergence of separated nets from the integer lattice. Our approach generalises that of Burago and Kleiner and McMullen which takes place largely in a continuous setting. Existence of irregular separated nets is verified via the existence of non-realisable density functions ρ:[0,1]d→(0,∞). In the present work we obtain stronger types of non-realisable densities.
Keywords: Lipschitz; bilipschitz; bounded displacement; modulus of continuity; separated net; non-realisable density; Burago--Kleiner construction

Fine tuning of defects enables high carrier mobility and enhanced thermoelectric performance of n-type PbTe - Wang, Siqi; Chang, Cheng; Bai, Shulin; Qin, Bingchao; Zhu, Yingcai; Zhan, Shaoping; Zheng, Junqing; Tang, Shuwei; Zhao, Li Dong (Chemistry of Materials)
High carrier mobility is critical to improving thermoelectric performance over a broad temperature range. However, traditional doping inevitably deteriorates carrier mobility. Herein, we develop a strategy for fine tuning of defects to improve carrier mobility. To begin, n-type PbTe is created by compensating for the intrinsic Pb vacancy in bare PbTe. Excess Pb2+ reduces vacancy scattering, resulting in a high carrier mobility of ∼3400 cm2 V–1 s–1. Then, excess Ag is introduced to compensate for the remaining intrinsic Pb vacancies. We find that excess Ag exhibits a dynamic doping process with increasing temperatures, increasing both the carrier concentration and carrier mobility throughout a wide temperature range; specifically, an ultrahigh carrier mobility ∼7300 cm2 V–1 s–1 is obtained for Pb1.01Te + 0.002Ag at 300 K. Moreover, the dynamic doping-induced high carrier concentration suppresses the bipolar thermal conductivity at high temperatures. The final step is using iodine to optimize the carrier concentration to ∼1019 cm–3. Ultimately, a maximum ZT value of ∼1.5 and a large average ZTave value of ∼1.0 at 300–773 K are obtained for Pb1.01Te0.998I0.002 + 0.002Ag. These findings demonstrate that fine tuning of defects with <0.5% impurities can remarkably enhance carrier mobility and improve thermoelectric performance.

scChIX-seq infers dynamic relationships between histone modifications in single cells - Yeung, Jake; Florescu, Maria; Zeller, Peter; De Barbanson, Buys Anton; Wellenstein, Max D.; Van Oudenaarden, Alexander (Nature Biotechnology)
Regulation of chromatin states involves the dynamic interplay between different histone modifications to control gene expression. Recent advances have enabled mapping of histone marks in single cells, but most methods are constrained to profile only one histone mark per cell. Here, we present an integrated experimental and computational framework, scChIX-seq (single-cell chromatin immunocleavage and unmixing sequencing), to map several histone marks in single cells. scChIX-seq multiplexes two histone marks together in single cells, then computationally deconvolves the signal using training data from respective histone mark profiles. This framework learns the cell-type-specific correlation structure between histone marks, and therefore does not require a priori assumptions of their genomic distributions. Using scChIX-seq, we demonstrate multimodal analysis of histone marks in single cells across a range of mark combinations. Modeling dynamics of in vitro macrophage differentiation enables integrated analysis of chromatin velocity. Overall, scChIX-seq unlocks systematic interrogation of the interplay between histone modifications in single cells.

The Bose Gas in a box with Neumann boundary conditions - Boccato, Chiara; Seiringer, Robert (Annales Henri Poincare)
We consider a gas of n bosonic particles confined in a box [−ℓ/2,ℓ/2]3 with Neumann boundary conditions. We prove Bose–Einstein condensation in the Gross–Pitaevskii regime, with an optimal bound on the condensate depletion. Moreover, our lower bound for the ground state energy in a small box [−ℓ/2,ℓ/2]3 implies (via Neumann bracketing) a lower bound for the ground state energy of N bosons in a large box [−L/2,L/2]3 with density ρ=N/L3 in the thermodynamic limit.

Pathogen evasion of social immunity - Stock, Miriam; Milutinovic, Barbara; Hönigsberger, Michaela; Grasse, Anna V; Wiesenhofer, Florian; Kampleitner, Niklas; Narasimhan, Madhumitha; Schmitt, Thomas; Cremer, Sylvia (Nature Ecology and Evolution)
Treating sick group members is a hallmark of collective disease defence in vertebrates and invertebrates alike. Despite substantial effects on pathogen fitness and epidemiology, it is still largely unknown how pathogens react to the selection pressure imposed by care intervention. Using social insects and pathogenic fungi, we here performed a serial passage experiment in the presence or absence of colony members, which provide social immunity by grooming off infectious spores from exposed individuals. We found specific effects on pathogen diversity, virulence and transmission. Under selection of social immunity, pathogens invested into higher spore production, but spores were less virulent. Notably, they also elicited a lower grooming response in colony members, compared with spores from the individual host selection lines. Chemical spore analysis suggested that the spores from social selection lines escaped the caregivers’ detection by containing lower levels of ergosterol, a key fungal membrane component. Experimental application of chemically pure ergosterol indeed induced sanitary grooming, supporting its role as a microbe-associated cue triggering host social immunity against fungal pathogens. By reducing this detection cue, pathogens were able to evade the otherwise very effective collective disease defences of their social hosts.

Witnessing light-driven entanglement using time-resolved resonant inelastic X-ray scattering - Hales, Jordyn; Bajpai, Utkarsh; Liu, Tongtong; Baykusheva, Denitsa Rangelova; Li, Mingda; Mitrano, Matteo; Wang, Yao (Nature Communications)
Characterizing and controlling entanglement in quantum materials is crucial for the development of next-generation quantum technologies. However, defining a quantifiable figure of merit for entanglement in macroscopic solids is theoretically and experimentally challenging. At equilibrium the presence of entanglement can be diagnosed by extracting entanglement witnesses from spectroscopic observables and a nonequilibrium extension of this method could lead to the discovery of novel dynamical phenomena. Here, we propose a systematic approach to quantify the time-dependent quantum Fisher information and entanglement depth of transient states of quantum materials with time-resolved resonant inelastic x-ray scattering. Using a quarter-filled extended Hubbard model as an example, we benchmark the efficiency of this approach and predict a light-enhanced many-body entanglement due to the proximity to a phase boundary. Our work sets the stage for experimentally witnessing and controlling entanglement in light-driven quantum materials via ultrafast spectroscopic measurements.
Keywords: General Physics and Astronomy; General Biochemistry; Genetics and Molecular Biology; General Chemistry; Multidisciplinary

Cavity quantum electrooptics - Sahu, Rishabh
About a 100 years ago, we discovered that our universe is inherently noisy, that is, measuring any physical quantity with a precision beyond a certain point is not possible because of an omnipresent inherent noise. We call this - the quantum noise. Certain physical processes allow this quantum noise to get correlated in conjugate physical variables. These quantum correlations can be used to go beyond the potential of our inherently noisy universe and obtain a quantum advantage over the classical applications. Quantum noise being inherent also means that, at the fundamental level, the physical quantities are not well defined and therefore, objects can stay in multiple states at the same time. For example, the position of a particle not being well defined means that the particle is in multiple positions at the same time. About 4 decades ago, we started exploring the possibility of using objects which can be in multiple states at the same time to increase the dimensionality in computation. Thus, the field of quantum computing was born. We discovered that using quantum entanglement, a property closely related to quantum correlations, can be used to speed up computation of certain problems, such as factorisation of large numbers, faster than any known classical algorithm. Thus began the pursuit to make quantum computers a reality. Till date, we have explored quantum control over many physical systems including photons, spins, atoms, ions and even simple circuits made up of superconducting material. However, there persists one ubiquitous theme. The more readily a system interacts with an external field or matter, the more easily we can control it. But this also means that such a system can easily interact with a noisy environment and quickly lose its coherence. Consequently, such systems like electron spins need to be protected from the environment to ensure the longevity of their coherence. Other systems like nuclear spins are naturally protected as they do not interact easily with the environment. But, due to the same reason, it is harder to interact with such systems. After decades of experimentation with various systems, we are convinced that no one type of quantum system would be the best for all the quantum applications. We would need hybrid systems which are all interconnected - much like the current internet where all sorts of devices can all talk to each other - but now for quantum devices. A quantum internet. Optical photons are the best contenders to carry information for the quantum internet. They can carry quantum information cheaply and without much loss - the same reasons which has made them the backbone of our current internet. Following this direction, many systems, like trapped ions, have already demonstrated successful quantum links over a large distances using optical photons. However, some of the most promising contenders for quantum computing which are based on microwave frequencies have been left behind. This is because high energy optical photons can adversely affect fragile low-energy microwave systems. In this thesis, we present substantial progress on this missing quantum link between microwave and optics using electrooptical nonlinearities in lithium niobate. The nonlinearities are enhanced by using resonant cavities for all the involved modes leading to observation of strong direct coupling between optical and microwave frequencies. With this strong coupling we are not only able to achieve almost 100% internal conversion efficiency with low added noise, thus presenting a quantum-enabled transducer, but also we are able to observe novel effects such as cooling of a microwave mode using optics. The strong coupling regime also leads to direct observation of dynamical backaction effect between microwave and optical frequencies which are studied in detail here. Finally, we also report first observation of microwave-optics entanglement in form of two-mode squeezed vacuum squeezed 0.7dB below vacuum level. With this new bridge between microwave and optics, the microwave-based quantum technologies can finally be a part of a quantum network which is based on optical photons - putting us one step closer to a future with quantum internet.
Keywords: quantum optics; electrooptics; quantum networks; quantum communication; transduction

Cavity quantum electrooptics - Sahu, Rishabh
About a 100 years ago, we discovered that our universe is inherently noisy, that is, measuring any physical quantity with a precision beyond a certain point is not possible because of an omnipresent inherent noise. We call this - the quantum noise. Certain physical processes allow this quantum noise to get correlated in conjugate physical variables. These quantum correlations can be used to go beyond the potential of our inherently noisy universe and obtain a quantum advantage over the classical applications. Quantum noise being inherent also means that, at the fundamental level, the physical quantities are not well defined and therefore, objects can stay in multiple states at the same time. For example, the position of a particle not being well defined means that the particle is in multiple positions at the same time. About 4 decades ago, we started exploring the possibility of using objects which can be in multiple states at the same time to increase the dimensionality in computation. Thus, the field of quantum computing was born. We discovered that using quantum entanglement, a property closely related to quantum correlations, can be used to speed up computation of certain problems, such as factorisation of large numbers, faster than any known classical algorithm. Thus began the pursuit to make quantum computers a reality. Till date, we have explored quantum control over many physical systems including photons, spins, atoms, ions and even simple circuits made up of superconducting material. However, there persists one ubiquitous theme. The more readily a system interacts with an external field or matter, the more easily we can control it. But this also means that such a system can easily interact with a noisy environment and quickly lose its coherence. Consequently, such systems like electron spins need to be protected from the environment to ensure the longevity of their coherence. Other systems like nuclear spins are naturally protected as they do not interact easily with the environment. But, due to the same reason, it is harder to interact with such systems. After decades of experimentation with various systems, we are convinced that no one type of quantum system would be the best for all the quantum applications. We would need hybrid systems which are all interconnected - much like the current internet where all sorts of devices can all talk to each other - but now for quantum devices. A quantum internet. Optical photons are the best contenders to carry information for the quantum internet. They can carry quantum information cheaply and without much loss - the same reasons which has made them the backbone of our current internet. Following this direction, many systems, like trapped ions, have already demonstrated successful quantum links over a large distances using optical photons. However, some of the most promising contenders for quantum computing which are based on microwave frequencies have been left behind. This is because high energy optical photons can adversely affect fragile low-energy microwave systems. In this thesis, we present substantial progress on this missing quantum link between microwave and optics using electrooptical nonlinearities in lithium niobate. The nonlinearities are enhanced by using resonant cavities for all the involved modes leading to observation of strong direct coupling between optical and microwave frequencies. With this strong coupling we are not only able to achieve almost 100% internal conversion efficiency with low added noise, thus presenting a quantum-enabled transducer, but also we are able to observe novel effects such as cooling of a microwave mode using optics. The strong coupling regime also leads to direct observation of dynamical backaction effect between microwave and optical frequencies which are studied in detail here. Finally, we also report first observation of microwave-optics entanglement in form of two-mode squeezed vacuum squeezed 0.7dB below vacuum level. With this new bridge between microwave and optics, the microwave-based quantum technologies can finally be a part of a quantum network which is based on optical photons - putting us one step closer to a future with quantum internet.
Keywords: quantum optics; electrooptics; quantum networks; quantum communication; transduction

Monitoring algorithmic fairness - Henzinger, Thomas A; Karimi, Mahyar; Kueffner, Konstantin; Mallik, Kaushik (Computer Aided Verification)
Machine-learned systems are in widespread use for making decisions about humans, and it is important that they are fair, i.e., not biased against individuals based on sensitive attributes. We present runtime verification of algorithmic fairness for systems whose models are unknown, but are assumed to have a Markov chain structure. We introduce a specification language that can model many common algorithmic fairness properties, such as demographic parity, equal opportunity, and social burden. We build monitors that observe a long sequence of events as generated by a given system, and output, after each observation, a quantitative estimate of how fair or biased the system was on that run until that point in time. The estimate is proven to be correct modulo a variable error bound and a given confidence level, where the error bound gets tighter as the observed sequence gets longer. Our monitors are of two types, and use, respectively, frequentist and Bayesian statistical inference techniques. While the frequentist monitors compute estimates that are objectively correct with respect to the ground truth, the Bayesian monitors compute estimates that are correct subject to a given prior belief about the system’s model. Using a prototype implementation, we show how we can monitor if a bank is fair in giving loans to applicants from different social backgrounds, and if a college is fair in admitting students while maintaining a reasonable financial burden on the society. Although they exhibit different theoretical complexities in certain cases, in our experiments, both frequentist and Bayesian monitors took less than a millisecond to update their verdicts after each observation.

Impact of BRCA mutation status on tumor dissemination pattern, surgical outcome and patient survival in primary and recurrent high-grade serous ovarian cancer: A multicenter retrospective study by the Ovarian Cancer Therapy-Innovative Models Prolong Survival (OCTIPS) consortium - Glajzer, Jacek; Castillo-Tong, Dan Cacsire; Richter, Rolf; Vergote, Ignace; Kulbe, Hagen; Vanderstichele, Adriaan; Ruscito, Ilary; Trillsch, Fabian; Mustea, Alexander; Kreuzinger, Caroline; Gourley, Charlie; Gabra, Hani; et al. (Annals of Surgical Oncology)
Background: This study seeks to evaluate the impact of breast cancer (BRCA) gene status on tumor dissemination pattern, surgical outcome and survival in a multicenter cohort of paired primary ovarian cancer (pOC) and recurrent ovarian cancer (rOC). Patients and Methods: Medical records and follow-up data from 190 patients were gathered retrospectively. All patients had surgery at pOC and at least one further rOC surgery at four European high-volume centers. Patients were divided into one cohort with confirmed mutation for BRCA1 and/or BRCA2 (BRCAmut) and a second cohort with BRCA wild type or unknown (BRCAwt). Patterns of tumor presentation, surgical outcome and survival data were analyzed between the two groups. Results: Patients with BRCAmut disease were on average 4 years younger and had significantly more tumor involvement upon diagnosis. Patients with BRCAmut disease showed higher debulking rates at all stages. Multivariate analysis showed that only patient age had significant predictive value for complete tumor resection in pOC. At rOC, however, only BRCAmut status significantly correlated with optimal debulking. Patients with BRCAmut disease showed significantly prolonged overall survival (OS) by 24.3 months. Progression-free survival (PFS) was prolonged in the BRCAmut group at all stages as well, reaching statistical significance during recurrence. Conclusions: Patients with BRCAmut disease showed a more aggressive course of disease with earlier onset and more extensive tumor dissemination at pOC. However, surgical outcome and OS were significantly better in patients with BRCAmut disease compared with patients with BRCAwt disease. We therefore propose to consider BRCAmut status in regard to patient selection for cytoreductive surgery, especially in rOC.
Keywords: Oncology; Surgery

Neuronal ER-plasma membrane junctions couple excitation to Ca2+-activated PKA signaling - Vierra, Nicholas C.; Ribeiro-Silva, Luisa; Kirmiz, Michael; Van Der List, Deborah; Bhandari, Pradeep; Mack, Olivia A.; Carroll, James; Le Monnier, Elodie; Aicher, Sue A.; Shigemoto, Ryuichi; Trimmer, James S. (Nature Communications)
Junctions between the endoplasmic reticulum (ER) and the plasma membrane (PM) are specialized membrane contacts ubiquitous in eukaryotic cells. Concentration of intracellular signaling machinery near ER-PM junctions allows these domains to serve critical roles in lipid and Ca2+ signaling and homeostasis. Subcellular compartmentalization of protein kinase A (PKA) signaling also regulates essential cellular functions, however, no specific association between PKA and ER-PM junctional domains is known. Here, we show that in brain neurons type I PKA is directed to Kv2.1 channel-dependent ER-PM junctional domains via SPHKAP, a type I PKA-specific anchoring protein. SPHKAP association with type I PKA regulatory subunit RI and ER-resident VAP proteins results in the concentration of type I PKA between stacked ER cisternae associated with ER-PM junctions. This ER-associated PKA signalosome enables reciprocal regulation between PKA and Ca2+ signaling machinery to support Ca2+ influx and excitation-transcription coupling. These data reveal that neuronal ER-PM junctions support a receptor-independent form of PKA signaling driven by membrane depolarization and intracellular Ca2+, allowing conversion of information encoded in electrical signals into biochemical changes universally recognized throughout the cell.

Guessing winning policies in LTL synthesis by semantic learning - Kretinsky, Jan; Meggendorfer, Tobias; Prokop, Maximilian; Rieder, Sabine (35th International Conference on Computer Aided Verification)
We provide a learning-based technique for guessing a winning strategy in a parity game originating from an LTL synthesis problem. A cheaply obtained guess can be useful in several applications. Not only can the guessed strategy be applied as best-effort in cases where the game’s huge size prohibits rigorous approaches, but it can also increase the scalability of rigorous LTL synthesis in several ways. Firstly, checking whether a guessed strategy is winning is easier than constructing one. Secondly, even if the guess is wrong in some places, it can be fixed by strategy iteration faster than constructing one from scratch. Thirdly, the guess can be used in on-the-fly approaches to prioritize exploration in the most fruitful directions. In contrast to previous works, we (i) reflect the highly structured logical information in game’s states, the so-called semantic labelling, coming from the recent LTL-to-automata translations, and (ii) learn to reflect it properly by learning from previously solved games, bringing the solving process closer to human-like reasoning.

Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets - Anastos, Michael; Fabian, David; Müyesser, Alp; Szabó, Tibor (Electronic Journal of Combinatorics)
We study multigraphs whose edge-sets are the union of three perfect matchings, M1, M2, and M3. Given such a graph G and any a1; a2; a3 2 N with a1 +a2 +a3 6 n - 2, we show there exists a matching M of G with jM \ Mij = ai for each i 2 f1; 2; 3g. The bound n - 2 in the theorem is best possible in general. We conjecture however that if G is bipartite, the same result holds with n - 2 replaced by n - 1. We give a construction that shows such a result would be tight. We also make a conjecture generalising the Ryser-Brualdi-Stein conjecture with colour multiplicities.

Automated tail bound analysis for probabilistic recurrence relations - Sun, Yican; Fu, Hongfei; Chatterjee, Krishnendu; Goharshady, Amir Kafshdar (Computer Aided Verification)
Probabilistic recurrence relations (PRRs) are a standard formalism for describing the runtime of a randomized algorithm. Given a PRR and a time limit κ, we consider the tail probability Pr[T≥κ], i.e., the probability that the randomized runtime T of the PRR exceeds κ. Our focus is the formal analysis of tail bounds that aims at finding a tight asymptotic upper bound u≥Pr[T≥κ]. To address this problem, the classical and most well-known approach is the cookbook method by Karp (JACM 1994), while other approaches are mostly limited to deriving tail bounds of specific PRRs via involved custom analysis. In this work, we propose a novel approach for deriving the common exponentially-decreasing tail bounds for PRRs whose preprocessing time and random passed sizes observe discrete or (piecewise) uniform distribution and whose recursive call is either a single procedure call or a divide-and-conquer. We first establish a theoretical approach via Markov’s inequality, and then instantiate the theoretical approach with a template-based algorithmic approach via a refined treatment of exponentiation. Experimental evaluation shows that our algorithmic approach is capable of deriving tail bounds that are (i) asymptotically tighter than Karp’s method, (ii) match the best-known manually-derived asymptotic tail bound for QuickSelect, and (iii) is only slightly worse (with a loglogn factor) than the manually-proven optimal asymptotic tail bound for QuickSort. Moreover, our algorithmic approach handles all examples (including realistic PRRs such as QuickSort, QuickSelect, DiameterComputation, etc.) in less than 0.1 s, showing that our approach is efficient in practice.

MDPs as distribution transformers: Affine invariant synthesis for safety objectives - Akshay, S.; Chatterjee, Krishnendu; Meggendorfer, Tobias; Zikelic, Dorde (International Conference on Computer Aided Verification)
Markov decision processes can be viewed as transformers of probability distributions. While this view is useful from a practical standpoint to reason about trajectories of distributions, basic reachability and safety problems are known to be computationally intractable (i.e., Skolem-hard) to solve in such models. Further, we show that even for simple examples of MDPs, strategies for safety objectives over distributions can require infinite memory and randomization. In light of this, we present a novel overapproximation approach to synthesize strategies in an MDP, such that a safety objective over the distributions is met. More precisely, we develop a new framework for template-based synthesis of certificates as affine distributional and inductive invariants for safety objectives in MDPs. We provide two algorithms within this framework. One can only synthesize memoryless strategies, but has relative completeness guarantees, while the other can synthesize general strategies. The runtime complexity of both algorithms is in PSPACE. We implement these algorithms and show that they can solve several non-trivial examples.

Closure properties of general grammars - formally verified - Dvorak, Martin; Blanchette, Jasmin (14th International Conference on Interactive Theorem Proving)
We formalized general (i.e., type-0) grammars using the Lean 3 proof assistant. We defined basic notions of rewrite rules and of words derived by a grammar, and used grammars to show closure of the class of type-0 languages under four operations: union, reversal, concatenation, and the Kleene star. The literature mostly focuses on Turing machine arguments, which are possibly more difficult to formalize. For the Kleene star, we could not follow the literature and came up with our own grammar-based construction.

Where do mistakes lead? A survey of games with incompetent players - Graham, Thomas; Kleshnina, Maria; Filar, Jerzy A. (Dynamic Games and Applications)
Mathematical models often aim to describe a complicated mechanism in a cohesive and simple manner. However, reaching perfect balance between being simple enough or overly simplistic is a challenging task. Frequently, game-theoretic models have an underlying assumption that players, whenever they choose to execute a specific action, do so perfectly. In fact, it is rare that action execution perfectly coincides with intentions of individuals, giving rise to behavioural mistakes. The concept of incompetence of players was suggested to address this issue in game-theoretic settings. Under the assumption of incompetence, players have non-zero probabilities of executing a different strategy from the one they chose, leading to stochastic outcomes of the interactions. In this article, we survey results related to the concept of incompetence in classic as well as evolutionary game theory and provide several new results. We also suggest future extensions of the model and argue why it is important to take into account behavioural mistakes when analysing interactions among players in both economic and biological settings.

A comparison between common marmosets (Callithrix jacchus) and human infants sheds light on traits proposed to be at the root of human octave equivalence - Wagner, Bernhard; Šlipogor, Vedrana; Oh, Jinook; Varga, Marion; Hoeschele, Marisa (Developmental Science)
Two notes separated by a doubling in frequency sound similar to humans. This “octave equivalence” is critical to perception and production of music and speech and occurs early in human development. Because it also occurs cross-culturally, a biological basis of octave equivalence has been hypothesized. Members of our team previousy suggested four human traits are at the root of this phenomenon: (1) vocal learning, (2) clear octave information in vocal harmonics, (3) differing vocal ranges, and (4) vocalizing together. Using cross-species studies, we can test how relevant these respective traits are, while controlling for enculturation effects and addressing questions of phylogeny. Common marmosets possess forms of three of the four traits, lacking differing vocal ranges. We tested 11 common marmosets by adapting an established head-turning paradigm, creating a parallel test to an important infant study. Unlike human infants, marmosets responded similarly to tones shifted by an octave or other intervals. Because previous studies with the same head-turning paradigm produced differential results to discernable acoustic stimuli in common marmosets, our results suggest that marmosets do not perceive octave equivalence. Our work suggests differing vocal ranges between adults and children and men and women and the way they are used in singing together may be critical to the development of octave equivalence.

Erdős-Ko-Rado and Hilton-Milner theorems for two-forms - Ivanov, Grigory; Köse, Seyda (Discrete Mathematics)
The celebrated Erdős–Ko–Rado theorem about the maximal size of an intersecting family of r-element subsets of was extended to the setting of exterior algebra in [5, Theorem 2.3] and in [6, Theorem 1.4]. However, the equality case has not been settled yet. In this short note, we show that the extension of the Erdős–Ko–Rado theorem and the characterization of the equality case therein, as well as those of the Hilton–Milner theorem to the setting of exterior algebra in the simplest non-trivial case of two-forms follow from a folklore puzzle about possible arrangements of an intersecting family of lines.

Computing the multicover bifiltration - Corbet, René; Kerber, Michael; Lesnick, Michael; Osang, Georg F (Discrete and Computational Geometry)
Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.

The reach of subsets of manifolds - Boissonnat, Jean Daniel; Wintraecken, Mathijs (Journal of Applied and Computational Topology)
Kleinjohann (Archiv der Mathematik 35(1):574–582, 1980; Mathematische Zeitschrift 176(3), 327–344, 1981) and Bangert (Archiv der Mathematik 38(1):54–57, 1982) extended the reach rch(S) from subsets S of Euclidean space to the reach rchM(S) of subsets S of Riemannian manifolds M, where M is smooth (we’ll assume at least C3). Bangert showed that sets of positive reach in Euclidean space and Riemannian manifolds are very similar. In this paper we introduce a slight variant of Kleinjohann’s and Bangert’s extension and quantify the similarity between sets of positive reach in Euclidean space and Riemannian manifolds in a new way: Given p∈M and q∈S, we bound the local feature size (a local version of the reach) of its lifting to the tangent space via the inverse exponential map (exp−1p(S)) at q, assuming that rchM(S) and the geodesic distance dM(p,q) are bounded. These bounds are motivated by the importance of the reach and local feature size to manifold learning, topological inference, and triangulating manifolds and the fact that intrinsic approaches circumvent the curse of dimensionality.

On the implementation of baselines and lightweight conditional model extrapolation (LIMES) under class-prior shift - Tomaszewska, Paulina; Lampert, Christoph (International Workshop on Reproducible Research in Pattern Recognition)
This paper focuses on the implementation details of the baseline methods and a recent lightweight conditional model extrapolation algorithm LIMES [5] for streaming data under class-prior shift. LIMES achieves superior performance over the baseline methods, especially concerning the minimum-across-day accuracy, which is important for the users of the system. In this work, the key measures to facilitate reproducibility and enhance the credibility of the results are described.

Random oracle combiners: Breaking the concatenation barrier for collision-resistance - Dodis, Yevgeniy; Ferguson, Niels; Goldin, Eli; Hall, Peter; Pietrzak, Krzysztof Z (43rd Annual International Cryptology Conference)
Suppose we have two hash functions h1 and h2, but we trust the security of only one of them. To mitigate this worry, we wish to build a hash combiner Ch1,h2 which is secure so long as one of the underlying hash functions is. This question has been well-studied in the regime of collision resistance. In this case, concatenating the two hash function outputs clearly works. Unfortunately, a long series of works (Boneh and Boyen, CRYPTO’06; Pietrzak, Eurocrypt’07; Pietrzak, CRYPTO’08) showed no (noticeably) shorter combiner for collision resistance is possible. In this work, we revisit this pessimistic state of affairs, motivated by the observation that collision-resistance is insufficient for many interesting applications of cryptographic hash functions anyway. We argue the right formulation of the “hash combiner” is to build what we call random oracle (RO) combiners, utilizing stronger assumptions for stronger constructions. Indeed, we circumvent the previous lower bounds for collision resistance by constructing a simple length-preserving RO combiner C˜h1,h2Z1,Z2(M)=h1(M,Z1)⊕h2(M,Z2),where Z1,Z2 are random salts of appropriate length. We show that this extra randomness is necessary for RO combiners, and indeed our construction is somewhat tight with this lower bound. On the negative side, we show that one cannot generically apply the composition theorem to further replace “monolithic” hash functions h1 and h2 by some simpler indifferentiable construction (such as the Merkle-Damgård transformation) from smaller components, such as fixed-length compression functions. Finally, despite this issue, we directly prove collision resistance of the Merkle-Damgård variant of our combiner, where h1 and h2 are replaced by iterative Merkle-Damgård hashes applied to a fixed-length compression function. Thus, we can still subvert the concatenation barrier for collision-resistance combiners while utilizing practically small fixed-length components underneath.

Coherent optical control of a superconducting microwave cavity via electro-optical dynamical back-action - Qiu, Liu; Sahu, Rishabh; Hease, William J; Arnold, Georg M; Fink, Johannes M (Nature Communications)
Recent quantum technologies have established precise quantum control of various microscopic systems using electromagnetic waves. Interfaces based on cryogenic cavity electro-optic systems are particularly promising, due to the direct interaction between microwave and optical fields in the quantum regime. Quantum optical control of superconducting microwave circuits has been precluded so far due to the weak electro-optical coupling as well as quasi-particles induced by the pump laser. Here we report the coherent control of a superconducting microwave cavity using laser pulses in a multimode electro-optical device at millikelvin temperature with near-unity cooperativity. Both the stationary and instantaneous responses of the microwave and optical modes comply with the coherent electro-optical interaction, and reveal only minuscule amount of excess back-action with an unanticipated time delay. Our demonstration enables wide ranges of applications beyond quantum transductions, from squeezing and quantum non-demolition measurements of microwave fields, to entanglement generation and hybrid quantum networks.

Dynamics of a rank-one perturbation of a Hermitian matrix - Dubach, Guillaume; Erdös, László (Electronic Communications in Probability)
We study the eigenvalue trajectories of a time dependent matrix Gt=H+itvv∗ for t≥0, where H is an N×N Hermitian random matrix and v is a unit vector. In particular, we establish that with high probability, an outlier can be distinguished at all times t>1+N−1/3+ϵ, for any ϵ>0. The study of this natural process combines elements of Hermitian and non-Hermitian analysis, and illustrates some aspects of the intrinsic instability of (even weakly) non-Hermitian matrices.

The Hasse principle for random Fano hypersurfaces - Browning, Timothy D; Boudec, Pierre Le; Sawin, Will (Annals of Mathematics)
It is known that the Brauer--Manin obstruction to the Hasse principle is vacuous for smooth Fano hypersurfaces of dimension at least 3 over any number field. Moreover, for such varieties it follows from a general conjecture of Colliot-Thélène that the Brauer--Manin obstruction to the Hasse principle should be the only one, so that the Hasse principle is expected to hold. Working over the field of rational numbers and ordering Fano hypersurfaces of fixed degree and dimension by height, we prove that almost every such hypersurface satisfies the Hasse principle provided that the dimension is at least 3. This proves a conjecture of Poonen and Voloch in every case except for cubic surfaces.

Stronger lower bounds for leakage-resilient secret sharing - Hoffmann, Charlotte; Simkin, Mark (8th International Conference on Cryptology and Information Security in Latin America)
Threshold secret sharing allows a dealer to split a secret s into n shares, such that any t shares allow for reconstructing s, but no t-1 shares reveal any information about s. Leakage-resilient secret sharing requires that the secret remains hidden, even when an adversary additionally obtains a limited amount of leakage from every share. Benhamouda et al. (CRYPTO’18) proved that Shamir’s secret sharing scheme is one bit leakage-resilient for reconstruction threshold t≥0.85n and conjectured that the same holds for t = c.n for any constant 0≤c≤1. Nielsen and Simkin (EUROCRYPT’20) showed that this is the best one can hope for by proving that Shamir’s scheme is not secure against one-bit leakage when t0c.n/log(n). In this work, we strengthen the lower bound of Nielsen and Simkin. We consider noisy leakage-resilience, where a random subset of leakages is replaced by uniformly random noise. We prove a lower bound for Shamir’s secret sharing, similar to that of Nielsen and Simkin, which holds even when a constant fraction of leakages is replaced by random noise. To this end, we first prove a lower bound on the share size of any noisy-leakage-resilient sharing scheme. We then use this lower bound to show that there exist universal constants c1, c2, such that for sufficiently large n it holds that Shamir’s secret sharing scheme is not noisy-leakage-resilient for t≤c1.n/log(n), even when a c2 fraction of leakages are replaced by random noise.

Monitoring algorithmic fairness under partial observations - Henzinger, Thomas A; Kueffner, Konstantin; Mallik, Kaushik (23rd International Conference on Runtime Verification)
As AI and machine-learned software are used increasingly for making decisions that affect humans, it is imperative that they remain fair and unbiased in their decisions. To complement design-time bias mitigation measures, runtime verification techniques have been introduced recently to monitor the algorithmic fairness of deployed systems. Previous monitoring techniques assume full observability of the states of the (unknown) monitored system. Moreover, they can monitor only fairness properties that are specified as arithmetic expressions over the probabilities of different events. In this work, we extend fairness monitoring to systems modeled as partially observed Markov chains (POMC), and to specifications containing arithmetic expressions over the expected values of numerical functions on event sequences. The only assumptions we make are that the underlying POMC is aperiodic and starts in the stationary distribution, with a bound on its mixing time being known. These assumptions enable us to estimate a given property for the entire distribution of possible executions of the monitored POMC, by observing only a single execution. Our monitors observe a long run of the system and, after each new observation, output updated PAC-estimates of how fair or biased the system is. The monitors are computationally lightweight and, using a prototype implementation, we demonstrate their effectiveness on several real-world examples.

The Fröhlich Polaron at strong coupling: Part I - The quantum correction to the classical energy - Brooks, Morris; Seiringer, Robert (Communications in Mathematical Physics)
We study the Fröhlich polaron model in R3, and establish the subleading term in the strong coupling asymptotics of its ground state energy, corresponding to the quantum corrections to the classical energy determined by the Pekar approximation.

A deeper analysis of volumetric relightiable faces - Rao, Pramod; Mallikarjun, B. R.; Fox, Gereon; Weyrich, Tim; Bickel, Bernd; Pfister, Hanspeter; Matusik, Wojciech; Zhan, Fangneng; Tewari, Ayush; Theobalt, Christian; Elgharib, Mohamed (International Journal of Computer Vision)
Portrait viewpoint and illumination editing is an important problem with several applications in VR/AR, movies, and photography. Comprehensive knowledge of geometry and illumination is critical for obtaining photorealistic results. Current methods are unable to explicitly model in 3D while handling both viewpoint and illumination editing from a single image. In this paper, we propose VoRF, a novel approach that can take even a single portrait image as input and relight human heads under novel illuminations that can be viewed from arbitrary viewpoints. VoRF represents a human head as a continuous volumetric field and learns a prior model of human heads using a coordinate-based MLP with individual latent spaces for identity and illumination. The prior model is learned in an auto-decoder manner over a diverse class of head shapes and appearances, allowing VoRF to generalize to novel test identities from a single input image. Additionally, VoRF has a reflectance MLP that uses the intermediate features of the prior model for rendering One-Light-at-A-Time (OLAT) images under novel views. We synthesize novel illuminations by combining these OLAT images with target environment maps. Qualitative and quantitative evaluations demonstrate the effectiveness of VoRF for relighting and novel view synthesis, even when applied to unseen subjects under uncontrolled illumination. This work is an extension of Rao et al. (VoRF: Volumetric Relightable Faces 2022). We provide extensive evaluation and ablative studies of our model and also provide an application, where any face can be relighted using textual input.

STROBE: Streaming Threshold Random Beacons - Beaver, Donald; Kelkar, Mahimna; Lewi, Kevin; Nikolaenko, Valeria; Sonnino, Alberto; Chalkias, Konstantinos; Kokoris Kogias, Eleftherios; Naurois, Ladi De; Roy, Arnab (5th Conference on Advances in Financial Technologies)
We revisit decentralized random beacons with a focus on practical distributed applications. Decentralized random beacons (Beaver and So, Eurocrypt'93) provide the functionality for n parties to generate an unpredictable sequence of bits in a way that cannot be biased, which is useful for any decentralized protocol requiring trusted randomness. Existing beacon constructions are highly inefficient in practical settings where protocol parties need to rejoin after crashes or disconnections, and more significantly where smart contracts may rely on arbitrary index points in high-volume streams. For this, we introduce a new notion of history-generating decentralized random beacons (HGDRBs). Roughly, the history-generation property of HGDRBs allows for previous beacon outputs to be efficiently generated knowing only the current value and the public key. At application layers, history-generation supports registering a sparser set of on-chain values if desired, so that apps like lotteries can utilize on-chain values without incurring high-frequency costs, enjoying all the benefits of DRBs implemented off-chain or with decoupled, special-purpose chains. Unlike rollups, HG is tailored specifically to recovering and verifying pseudorandom bit sequences and thus enjoys unique optimizations investigated in this work. We introduce STROBE: an efficient HGDRB construction which generalizes the original squaring-based RSA approach of Beaver and So. STROBE enjoys several useful properties that make it suited for practical applications that use beacons: 1) history-generating: it can regenerate and verify high-throughput beacon streams, supporting sparse (thus cost-effective) ledger entries; 2) concisely self-verifying: NIZK-free, with state and validation employing a single ring element; 3) eco-friendly: stake-based rather than work based; 4) unbounded: refresh-free, addressing limitations of Beaver and So; 5) delay-free: results are immediately available. 6) storage-efficient: the last beacon suffices to derive all past outputs, thus O(1) storage requirements for nodes serving the whole history.

Density-wave ordering in a unitary Fermi gas with photon-mediated interactions - Helson, Victor; Zwettler, Timo; Mivehvar, Farokh; Colella, Elvia; Roux, Kevin Etienne Robert; Konishi, Hideki; Ritsch, Helmut; Brantut, Jean Philippe (Nature)
A density wave (DW) is a fundamental type of long-range order in quantum matter tied to self-organization into a crystalline structure. The interplay of DW order with superfluidity can lead to complex scenarios that pose a great challenge to theoretical analysis. In the past decades, tunable quantum Fermi gases have served as model systems for exploring the physics of strongly interacting fermions, including most notably magnetic ordering1, pairing and superfluidity2, and the crossover from a Bardeen–Cooper–Schrieffer superfluid to a Bose–Einstein condensate3. Here, we realize a Fermi gas featuring both strong, tunable contact interactions and photon-mediated, spatially structured long-range interactions in a transversely driven high-finesse optical cavity. Above a critical long-range interaction strength, DW order is stabilized in the system, which we identify via its superradiant light-scattering properties. We quantitatively measure the variation of the onset of DW order as the contact interaction is varied across the Bardeen–Cooper–Schrieffer superfluid and Bose–Einstein condensate crossover, in qualitative agreement with a mean-field theory. The atomic DW susceptibility varies over an order of magnitude upon tuning the strength and the sign of the long-range interactions below the self-ordering threshold, demonstrating independent and simultaneous control over the contact and long-range interactions. Therefore, our experimental setup provides a fully tunable and microscopically controllable platform for the experimental study of the interplay of superfluidity and DW order.

Deterministic near-optimal approximation algorithms for dynamic set cover - Bhattacharya, Sayan; Henzinger, Monika H; Nanongkai, Danupon; Wu, Xiaowei (SIAM Journal on Computing)
n the dynamic minimum set cover problem, the challenge is to minimize the update time while guaranteeing a close-to-optimal min{O(log n), f} approximation factor. (Throughout, n, m, f , and C are parameters denoting the maximum number of elements, the number of sets, the frequency, and the cost range.) In the high-frequency range, when f = Ω(log n) , this was achieved by a deterministic O(log n) -approximation algorithm with O(f log n) amortized update time by Gupta et al. [Online and dynamic algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537–550]. In this paper we consider the low-frequency range, when f = O(log n) , and obtain deterministic algorithms with a (1 + ∈)f -approximation ratio and the following guarantees on the update time. (1) O ((f/∈)-log(Cn)) amortized update time: Prior to our work, the best approximation ratio guaranteed by deterministic algorithms was O(f2) of Bhattacharya, Henzinger, and Italiano [Design of dynamic algorithms via primal-dual method, in Proceedings ICALP 2015, Springer, pp. 206–218]. In contrast, the only result with O(f) -approximation was that of Abboud et al. [Dynamic set cover: Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114–125], who designed a randomized (1+∈)f -approximation algorithm with amortized update time. (2) O(f2/∈3 + (f/∈2).logC) amortized update time: This result improves the above update time bound for most values of f in the low-frequency range, i.e., f=o(log n) . It is also the first result that is independent of m and n. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [Deterministically maintaining a (2 + ∈) -approximate minimum vertex cover in O(1/∈2) amortized update time, in Proceedings SODA 2019, SIAM, pp. 1872–1885] for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1). (3) O((f/∈3).log2(Cn)) worst-case update time: No nontrivial worst-case update time was previously known for the dynamic set cover problem. Our bound subsumes and improves by a logarithmic factor the O(log3n/poly (∈)) worst-case update time for the unweighted dynamic vertex cover problem (i.e., when f = 2 and C =1) of Bhattacharya, Henzinger, and Nanongkai [Fully dynamic approximate maximum matching and minimum vertex cover in O(log3)n worst case update time, in Proceedings SODA 2017, SIAM, pp. 470–489]. We achieve our results via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. Prior work in dynamic algorithms that employs the primal-dual approach uses a local update scheme that maintains relaxed complementary slackness conditions for every set. For our first result we use instead a global update scheme that does not always maintain complementary slackness conditions. For our second result we combine the global and the local update schema. To achieve our third result we use a hierarchy of background schedulers. It is an interesting open question whether this background scheduler technique can also be used to transform algorithms with amortized running time bounds into algorithms with worst-case running time bounds.

Learning provably stabilizing neural controllers for discrete-time stochastic systems - Ansaripour, Matin; Chatterjee, Krishnendu; Henzinger, Thomas A; Lechner, Mathias; Zikelic, Dorde (21st International Symposium on Automated Technology for Verification and Analysis)
We consider the problem of learning control policies in discrete-time stochastic systems which guarantee that the system stabilizes within some specified stabilization region with probability 1. Our approach is based on the novel notion of stabilizing ranking supermartingales (sRSMs) that we introduce in this work. Our sRSMs overcome the limitation of methods proposed in previous works whose applicability is restricted to systems in which the stabilizing region cannot be left once entered under any control policy. We present a learning procedure that learns a control policy together with an sRSM that formally certifies probability 1 stability, both learned as neural networks. We show that this procedure can also be adapted to formally verifying that, under a given Lipschitz continuous control policy, the stochastic system stabilizes within some stabilizing region with probability 1. Our experimental evaluation shows that our learning procedure can successfully learn provably stabilizing policies in practice.

Bi-allelic ACBD6 variants lead to a neurodevelopmental syndrome with progressive and complex movement disorders - Kaiyrzhanov, Rauan; Rad, Aboulfazl; Lin, Sheng-Jia; Bertoli-Avella, Aida; Kallemeijn, Wouter W; Godwin, Annie; Zaki, Maha S; Huang, Kevin; Lau, Tracy; Petree, Cassidy; Efthymiou, Stephanie; Ghayoor Karimiani, Ehsan; et al. (Brain)
The acyl-CoA-binding domain-containing protein 6 (ACBD6) is ubiquitously expressed, plays a role in the acylation of lipids and proteins, and regulates the N-myristoylation of proteins via N-myristoyltransferase enzymes (NMTs). However, its precise function in cells is still unclear, as is the consequence of ACBD6 defects on human pathophysiology. Utilizing exome sequencing and extensive international data sharing efforts, we identified 45 affected individuals from 28 unrelated families (consanguinity 93%) with bi-allelic pathogenic, predominantly loss-of-function (18/20) variants in ACBD6. We generated zebrafish and Xenopus tropicalis acbd6 knockouts by CRISPR/Cas9 and characterized the role of ACBD6 on protein N-myristoylation with YnMyr chemical proteomics in the model organisms and human cells, with the latter also being subjected further to ACBD6 peroxisomal localization studies. The affected individuals (23 males and 22 females), with ages ranging from 1 to 50 years old, typically present with a complex and progressive disease involving moderate-to-severe global developmental delay/intellectual disability (100%) with significant expressive language impairment (98%), movement disorders (97%), facial dysmorphism (95%), and mild cerebellar ataxia (85%) associated with gait impairment (94%), limb spasticity/hypertonia (76%), oculomotor (71%) and behavioural abnormalities (65%), overweight (59%), microcephaly (39%) and epilepsy (33%). The most conspicuous and common movement disorder was dystonia (94%), frequently leading to early-onset progressive postural deformities (97%), limb dystonia (55%), and cervical dystonia (31%). A jerky tremor in the upper limbs (63%), a mild head tremor (59%), parkinsonism/hypokinesia developing with advancing age (32%), and simple motor and vocal tics were among other frequent movement disorders. Midline brain malformations including corpus callosum abnormalities (70%), hypoplasia/agenesis of the anterior commissure (66%), short midbrain and small inferior cerebellar vermis (38% each), as well as hypertrophy of the clava (24%) were common neuroimaging findings. acbd6-deficient zebrafish and Xenopus models effectively recapitulated many clinical phenotypes reported in patients including movement disorders, progressive neuromotor impairment, seizures, microcephaly, craniofacial dysmorphism, and midbrain defects accompanied by developmental delay with increased mortality over time. Unlike ACBD5, ACBD6 did not show a peroxisomal localisation and ACBD6-deficiency was not associated with altered peroxisomal parameters in patient fibroblasts. Significant differences in YnMyr-labelling were observed for 68 co- and 18 post-translationally N-myristoylated proteins in patient-derived fibroblasts. N-Myristoylation was similarly affected in acbd6-deficient zebrafish and Xenopus tropicalis models, including Fus, Marcks, and Chchd-related proteins implicated in neurological diseases. The present study provides evidence that bi-allelic pathogenic variants in ACBD6 lead to a distinct neurodevelopmental syndrome accompanied by complex and progressive cognitive and movement disorders.
Keywords: Neurology (clinical)

ArpC5 isoforms regulate Arp2/3 complex–dependent protrusion through differential Ena/VASP positioning - Fäßler, Florian; Javoor, Manjunath; Datler, Julia; Döring, Hermann; Hofer, Florian; Dimchev, Georgi A; Hodirnau, Victor-Valentin; Faix, Jan; Rottner, Klemens; Schur, Florian KM (Science Advances)
Regulation of the Arp2/3 complex is required for productive nucleation of branched actin networks. An emerging aspect of regulation is the incorporation of subunit isoforms into the Arp2/3 complex. Specifically, both ArpC5 subunit isoforms, ArpC5 and ArpC5L, have been reported to fine-tune nucleation activity and branch junction stability. We have combined reverse genetics and cellular structural biology to describe how ArpC5 and ArpC5L differentially affect cell migration. Both define the structural stability of ArpC1 in branch junctions and, in turn, by determining protrusion characteristics, affect protein dynamics and actin network ultrastructure. ArpC5 isoforms also affect the positioning of members of the Ena/Vasodilator-stimulated phosphoprotein (VASP) family of actin filament elongators, which mediate ArpC5 isoform–specific effects on the actin assembly level. Our results suggest that ArpC5 and Ena/VASP proteins are part of a signaling pathway enhancing cell migration.
Keywords: Multidisciplinary

Research data of the publication "ArpC5 isoforms regulate Arp2/3 complex-dependent protrusion through differential Ena/VASP positioning" - Schur, Florian KM
Regulation of the Arp2/3 complex is required for productive nucleation of branched actin networks. An emerging aspect of regulation is the incorporation of subunit isoforms into the Arp2/3 complex. Specifically, both ArpC5 subunit isoforms, ArpC5 and ArpC5L, have been reported to fine-tune nucleation activity and branch junction stability. We have combined reverse genetics and cellular structural biology to describe how ArpC5 and ArpC5L differentially affect cell migration. Both define the structural stability of ArpC1 in branch junctions and, in turn, by determining protrusion characteristics, affect protein dynamics and actin network ultrastructure. ArpC5 isoforms also affect the positioning of members of the Ena/Vasodilator-stimulated phosphoprotein (VASP) family of actin filament elongators, which mediate ArpC5 isoform–specific effects on the actin assembly level. Our results suggest that ArpC5 and Ena/VASP proteins are part of a signaling pathway enhancing cell migration.

Stress granules plug and stabilize damaged endolysosomal membranes - Bussi, Claudio; Mangiarotti, Agustín; Vanhille-Campos, Christian Eduardo; Aylan, Beren; Pellegrino, Enrica; Athanasiadi, Natalia; Fearns, Antony; Rodgers, Angela; Franzmann, Titus M.; Šarić, Anđela; Dimova, Rumiana; Gutierrez, Maximiliano G. (Nature)
Abstract Endomembrane damage represents a form of stress that is detrimental for eukaryotic cells 1,2 . To cope with this threat, cells possess mechanisms that repair the damage and restore cellular homeostasis 3–7 . Endomembrane damage also results in organelle instability and the mechanisms by which cells stabilize damaged endomembranes to enable membrane repair remains unknown. Here, by combining in vitro and in cellulo studies with computational modelling we uncover a biological function for stress granules whereby these biomolecular condensates form rapidly at endomembrane damage sites and act as a plug that stabilizes the ruptured membrane. Functionally, we demonstrate that stress granule formation and membrane stabilization enable efficient repair of damaged endolysosomes, through both ESCRT (endosomal sorting complex required for transport)-dependent and independent mechanisms. We also show that blocking stress granule formation in human macrophages creates a permissive environment for Mycobacterium tuberculosis , a human pathogen that exploits endomembrane damage to survive within the host.
Keywords: Multidisciplinary

Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation - Schmid, Stefan; Svoboda, Jakub; Yeo, Michelle X (SIROCCO 2023: Structural Information and Communication Complexity)
We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link (u, v) is determined by how much nodes u and v allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given (u, v) and a packet of weight x going from u to v, node u can either accept or reject the packet. If u accepts the packet, the capacity on link (u, v) decreases by x. Correspondingly, v’s capacity on (u, v) increases by x. If a node rejects the packet, this will entail a cost affinely linear in the weight of the packet. A link is “rechargeable” in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on the nodes’ decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of (1+ε)⋅(1+3–√) for some arbitrary ε>0. .

Criticality of neuronal avalanches in human sleep and their relationship with sleep macro- and micro-architecture - Scarpetta, Silvia; Morrisi, Niccolò; Mutti, Carlotta; Azzi, Nicoletta; Trippi, Irene; Ciliento, Rosario; Apicella, Ilenia; Messuti, Giovanni; Angiolelli, Marianna; Lombardi, Fabrizio; Parrino, Liborio; Vaudano, Anna Elisabetta (iScience)
Sleep plays a key role in preserving brain function, keeping the brain network in a state that ensures optimal computational capabilities. Empirical evidence indicates that such a state is consistent with criticality, where scale-free neuronal avalanches emerge. However, the relationship between sleep, emergent avalanches, and criticality remains poorly understood. Here we fully characterize the critical behavior of avalanches during sleep, and study their relationship with the sleep macro- and micro-architecture, in particular the cyclic alternating pattern (CAP). We show that avalanche size and duration distributions exhibit robust power laws with exponents approximately equal to −3/2 e −2, respectively. Importantly, we find that sizes scale as a power law of the durations, and that all critical exponents for neuronal avalanches obey robust scaling relations, which are consistent with the mean-field directed percolation universality class. Our analysis demonstrates that avalanche dynamics depends on the position within the NREM-REM cycles, with the avalanche density increasing in the descending phases and decreasing in the ascending phases of sleep cycles. Moreover, we show that, within NREM sleep, avalanche occurrence correlates with CAP activation phases, particularly A1, which are the expression of slow wave sleep propensity and have been proposed to be beneficial for cognitive processes. The results suggest that neuronal avalanches, and thus tuning to criticality, actively contribute to sleep development and play a role in preserving network function. Such findings, alongside characterization of the universality class for avalanches, open new avenues to the investigation of functional role of criticality during sleep with potential clinical application. Significance statement We fully characterize the critical behavior of neuronal avalanches during sleep, and show that avalanches follow precise scaling laws that are consistent with the mean-field directed percolation universality class. The analysis provides first evidence of a functional relationship between avalanche occurrence, slow-wave sleep dynamics, sleep stage transitions and occurrence of CAP phase A during NREM sleep. Because CAP is considered one of the major guardians of NREM sleep that allows the brain to dynamically react to external perturbation and contributes to the cognitive consolidation processes occurring in sleep, our observations suggest that neuronal avalanches at criticality are associated with flexible response to external inputs and to cognitive processes, a key assumption of the critical brain hypothesis.

Learning deposition policies for fused multi-material 3D printing - Liao, Kang; Tricard, Thibault; Piovarci, Michael; Seidel, Hans-Peter; Babaei, Vahid (2023 IEEE International Conference on Robotics and Automation)
3D printing based on continuous deposition of materials, such as filament-based 3D printing, has seen widespread adoption thanks to its versatility in working with a wide range of materials. An important shortcoming of this type of technology is its limited multi-material capabilities. While there are simple hardware designs that enable multi-material printing in principle, the required software is heavily underdeveloped. A typical hardware design fuses together individual materials fed into a single chamber from multiple inlets before they are deposited. This design, however, introduces a time delay between the intended material mixture and its actual deposition. In this work, inspired by diverse path planning research in robotics, we show that this mechanical challenge can be addressed via improved printer control. We propose to formulate the search for optimal multi-material printing policies in a reinforcement learning setup. We put forward a simple numerical deposition model that takes into account the non-linear material mixing and delayed material deposition. To validate our system we focus on color fabrication, a problem known for its strict requirements for varying material mixtures at a high spatial frequency. We demonstrate that our learned control policy outperforms state-of-the-art hand-crafted algorithms.
Keywords: reinforcement learning; deposition; control; color; multi-filament

Correlation energy of a weakly interacting Fermi gas with large interaction potential - Benedikter, Niels P; Porta, Marcello; Schlein, Benjamin; Seiringer, Robert (Archive for Rational Mechanics and Analysis)
Recently the leading order of the correlation energy of a Fermi gas in a coupled mean-field and semiclassical scaling regime has been derived, under the assumption of an interaction potential with a small norm and with compact support in Fourier space. We generalize this result to large interaction potentials, requiring only |⋅|V^∈ℓ1(Z3). Our proof is based on approximate, collective bosonization in three dimensions. Significant improvements compared to recent work include stronger bounds on non-bosonizable terms and more efficient control on the bosonization of the kinetic energy.

Inductively shunted transmons exhibit noise insensitive plasmon states and a fluxon decay exceeding 3 hours - Hassani, Farid; Peruzzo, Matilda; Kapoor, Lucky; Trioni, Andrea; Zemlicka, Martin; Fink, Johannes M (Nature Communications)
Currently available quantum processors are dominated by noise, which severely limits their applicability and motivates the search for new physical qubit encodings. In this work, we introduce the inductively shunted transmon, a weakly flux-tunable superconducting qubit that offers charge offset protection for all levels and a 20-fold reduction in flux dispersion compared to the state-of-the-art resulting in a constant coherence over a full flux quantum. The parabolic confinement provided by the inductive shunt as well as the linearity of the geometric superinductor facilitates a high-power readout that resolves quantum jumps with a fidelity and QND-ness of >90% and without the need for a Josephson parametric amplifier. Moreover, the device reveals quantum tunneling physics between the two prepared fluxon ground states with a measured average decay time of up to 3.5 h. In the future, fast time-domain control of the transition matrix elements could offer a new path forward to also achieve full qubit control in the decay-protected fluxon basis.

Some convexity and monotonicity results of trace functionals - Zhang, Haonan (Annales Henri Poincare)
In this paper, we prove the convexity of trace functionals (A,B,C)↦Tr|BpACq|s, for parameters (p, q, s) that are best possible, where B and C are any n-by-n positive-definite matrices, and A is any n-by-n matrix. We also obtain the monotonicity versions of trace functionals of this type. As applications, we extend some results in Carlen et al. (Linear Algebra Appl 490:174–185, 2016), Hiai and Petz (Publ Res Inst Math Sci 48(3):525-542, 2012) and resolve a conjecture in Al-Rashed and Zegarliński (Infin Dimens Anal Quantum Probab Relat Top 17(4):1450029, 2014) in the matrix setting. Other conjectures in Al-Rashed and Zegarliński (Infin Dimens Anal Quantum Probab Relat Top 17(4):1450029, 2014) will also be discussed. We also show that some related trace functionals are not concave in general. Such concavity results were expected to hold in different problems.

Eigenstate thermalisation hypothesis for translation invariant spin systems - Sugimoto, Shoki; Henheik, Sven Joscha; Riabov, Volodymyr; Erdös, László (Journal of Statistical Physics)
We prove the Eigenstate Thermalisation Hypothesis (ETH) for local observables in a typical translation invariant system of quantum spins with L-body interactions, where L is the number of spins. This mathematically verifies the observation first made by Santos and Rigol (Phys Rev E 82(3):031130, 2010, https://doi.org/10.1103/PhysRevE.82.031130) that the ETH may hold for systems with additional translational symmetries for a naturally restricted class of observables. We also present numerical support for the same phenomenon for Hamiltonians with local interaction.

The crossing Tverberg theorem - Fulek, Radoslav; Gärtner, Bernd; Kupavskii, Andrey; Valtr, Pavel; Wagner, Uli (Discrete and Computational Geometry)
The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r−1)+1 points in Rd, one can find a partition X=X1∪⋯∪Xr of X, such that the convex hulls of the Xi, i=1,…,r, all share a common point. In this paper, we prove a trengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span ⌊n/3⌋ vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Álvarez-Rebollar et al. guarantees ⌊n/6⌋pairwise crossing triangles. Our result generalizes to a result about simplices in Rd, d≥2.

3D cell segregation geometry and dynamics are governed by tissue surface tension regulation - Méhes, Elod; Mones, Enys; Varga, Máté; Zsigmond, Áron; Biri-Kovács, Beáta; Nyitray, László; Barone, Vanessa; Krens, Gabriel; Heisenberg, Carl-Philipp J; Vicsek, Tamás (Communications Biology)
Tissue morphogenesis and patterning during development involve the segregation of cell types. Segregation is driven by differential tissue surface tensions generated by cell types through controlling cell-cell contact formation by regulating adhesion and actomyosin contractility-based cellular cortical tensions. We use vertebrate tissue cell types and zebrafish germ layer progenitors as in vitro models of 3-dimensional heterotypic segregation and developed a quantitative analysis of their dynamics based on 3D time-lapse microscopy. We show that general inhibition of actomyosin contractility by the Rho kinase inhibitor Y27632 delays segregation. Cell type-specific inhibition of non-muscle myosin2 activity by overexpression of myosin assembly inhibitor S100A4 reduces tissue surface tension, manifested in decreased compaction during aggregation and inverted geometry observed during segregation. The same is observed when we express a constitutively active Rho kinase isoform to ubiquitously keep actomyosin contractility high at cell-cell and cell-medium interfaces and thus overriding the interface-specific regulation of cortical tensions. Tissue surface tension regulation can become an effective tool in tissue engineering.

The Ycf48 accessory factor occupies the site of the oxygen-evolving manganese cluster during photosystem II biogenesis - Zhao, Ziyu; Vercellino, Irene; Knoppová, Jana; Sobotka, Roman; Murray, James W.; Nixon, Peter J.; Sazanov, Leonid A; Komenda, Josef (Nature Communications)
Robust oxygenic photosynthesis requires a suite of accessory factors to ensure efficient assembly and repair of the oxygen-evolving photosystem two (PSII) complex. The highly conserved Ycf48 assembly factor binds to the newly synthesized D1 reaction center polypeptide and promotes the initial steps of PSII assembly, but its binding site is unclear. Here we use cryo-electron microscopy to determine the structure of a cyanobacterial PSII D1/D2 reaction center assembly complex with Ycf48 attached. Ycf48, a 7-bladed beta propeller, binds to the amino-acid residues of D1 that ultimately ligate the water-oxidising Mn4CaO5 cluster, thereby preventing the premature binding of Mn2+ and Ca2+ ions and protecting the site from damage. Interactions with D2 help explain how Ycf48 promotes assembly of the D1/D2 complex. Overall, our work provides valuable insights into the early stages of PSII assembly and the structural changes that create the binding site for the Mn4CaO5 cluster.

The molecular basis of sexual dimorphism: Experimental and theoretical characterization of phenotypic, transcriptomic and genetic patterns of sex-specific adaptation - Puixeu Sala, Gemma
Females and males across species are subject to divergent selective pressures arising from di↵erent reproductive interests and ecological niches. This often translates into a intricate array of sex-specific natural and sexual selection on traits that have a shared genetic basis between both sexes, causing a genetic sexual conflict. The resolution of this conflict mostly relies on the evolution of sex-specific expression of the shared genes, leading to phenotypic sexual dimorphism. Such sex-specific gene expression is thought to evolve via modifications of the genetic networks ultimately linked to sex-determining transcription factors. Although much empirical and theoretical evidence supports this standard picture of the molecular basis of sexual conflict resolution, there still are a few open questions regarding the complex array of selective forces driving phenotypic di↵erentiation between the sexes, as well as the molecular mechanisms underlying sexspecific adaptation. I address some of these open questions in my PhD thesis. First, how do patterns of phenotypic sexual dimorphism vary within populations, as a response to the temporal and spatial changes in sex-specific selective forces? To tackle this question, I analyze the patterns of sex-specific phenotypic variation along three life stages and across populations spanning the whole geographical range of Rumex hastatulus, a wind-pollinated angiosperm, in the first Chapter of the thesis. Second, how do gene expression patterns lead to phenotypic dimorphism, and what are the molecular mechanisms underlying the observed transcriptomic variation? I address this question by examining the sex- and tissue-specific expression variation in newly-generated datasets of sex-specific expression in heads and gonads of Drosophila melanogaster. I additionally used two complementary approaches for the study of the genetic basis of sex di↵erences in gene expression in the second and third Chapters of the thesis. Third, how does intersex correlation, thought to be one of the main aspects constraining the ability for the two sexes to decouple, interact with the evolution of sexual dimorphism? I develop models of sex-specific stabilizing selection, mutation and drift to formalize common intuition regarding the patterns of covariation between intersex correlation and sexual dimorphism in the fourth Chapter of the thesis. Alltogether, the work described in this PhD thesis provides useful insights into the links between genetic, transcriptomic and phenotypic layers of sex-specific variation, and contributes to our general understanding of the dynamics of sexual dimorphism evolution.

Sex-specific estimation of cis and trans regulation of gene expression in heads and gonads of Drosophila melanogaster - Puixeu Sala, Gemma; Macon, Ariana; Vicoso, Beatriz (G3: Genes, Genomes, Genetics)
The regulatory architecture of gene expression is known to differ substantially between sexes in Drosophila, but most studies performed so far used whole-body data and only single crosses, which may have limited their scope to detect patterns that are robust across tissues and biological replicates. Here, we use allele-specific gene expression of parental and reciprocal hybrid crosses between 6 Drosophila melanogaster inbred lines to quantify cis- and trans-regulatory variation in heads and gonads of both sexes separately across 3 replicate crosses. Our results suggest that female and male heads, as well as ovaries, have a similar regulatory architecture. On the other hand, testes display more and substantially different cis-regulatory effects, suggesting that sex differences in the regulatory architecture that have been previously observed may largely derive from testis-specific effects. We also examine the difference in cis-regulatory variation of genes across different levels of sex bias in gonads and heads. Consistent with the idea that intersex correlations constrain expression and can lead to sexual antagonism, we find more cis variation in unbiased and moderately biased genes in heads. In ovaries, reduced cis variation is observed for male-biased genes, suggesting that cis variants acting on these genes in males do not lead to changes in ovary expression. Finally, we examine the dominance patterns of gene expression and find that sex- and tissue-specific patterns of inheritance as well as trans-regulatory variation are highly variable across biological crosses, although these were performed in highly controlled experimental conditions. This highlights the importance of using various genetic backgrounds to infer generalizable patterns.
Keywords: Genetics (clinical); Genetics; Molecular Biology

On angles in higher order Brillouin tessellations and related tilings in the plane - Edelsbrunner, Herbert; Garber, Alexey; Ghafari, Mohadese; Heiss, Teresa; Saghafian, Morteza (Discrete and Computational Geometry)
For a locally finite set in R2, the order-k Brillouin tessellations form an infinite sequence of convex face-to-face tilings of the plane. If the set is coarsely dense and generic, then the corresponding infinite sequences of minimum and maximum angles are both monotonic in k. As an example, a stationary Poisson point process in R2 is locally finite, coarsely dense, and generic with probability one. For such a set, the distributions of angles in the Voronoi tessellations, Delaunay mosaics, and Brillouin tessellations are independent of the order and can be derived from the formula for angles in order-1 Delaunay mosaics given by Miles (Math. Biosci. 6, 85–127 (1970)).

A layered Bi2Te3@PPy cathode for aqueous zinc ion batteries: Mechanism and application in printed flexible batteries - Zeng, Guifang; Sun, Qing; Horta, Sharona; Wang, Shang; Lu, Xuan; Zhang, Chaoyue; Li, Jing; Li, Junshan; Ci, Lijie; Tian, Yanhong; Ibáñez, Maria; Cabot, Andreu (Advanced Materials)
Low‐cost, safe, and environmental‐friendly rechargeable aqueous zinc‐ion batteries (ZIBs) are promising as next‐generation energy storage devices for wearable electronics among other applications. However, sluggish ionic transport kinetics and the unstable electrode structure during ionic insertion/extraction hampers their deployment. Herein, we propose a new cathode material based on a layered metal chalcogenide (LMC), bismuth telluride (Bi 2 Te 3 ), coated with polypyrrole (PPy). Taking advantage of the PPy coating, the Bi 2 Te 3 @PPy composite presents strong ionic absorption affinity, high oxidation resistance, and high structural stability. The ZIBs based on Bi 2 Te 3 @PPy cathodes exhibit high capacities and ultra‐long lifespans of over 5000 cycles. They also present outstanding stability even under bending. In addition, we analyze here the reaction mechanism using in situ X‐ray diffraction, X‐ray photoelectron spectroscopy, and computational tools and demonstrate that, in the aqueous system, Zn 2+ is not inserted into the cathode as previously assumed. In contrast, proton charge storage dominates the process. Overall, this work not only shows the great potential of LMCs as ZIBs cathode materials and the advantages of PPy coating, but also clarifies the charge/discharge mechanism in rechargeable ZIBs based on LMCs.
Keywords: Mechanical Engineering; Mechanics of Materials; General Materials Science

(Verifiable) delay functions from Lucas sequences - Hoffmann, Charlotte; Hubáček, Pavel; Kamath, Chethan; Krňák, Tomáš (21st International Conference on Theory of Cryptography)
Lucas sequences are constant-recursive integer sequences with a long history of applications in cryptography, both in the design of cryptographic schemes and cryptanalysis. In this work, we study the sequential hardness of computing Lucas sequences over an RSA modulus. First, we show that modular Lucas sequences are at least as sequentially hard as the classical delay function given by iterated modular squaring proposed by Rivest, Shamir, and Wagner (MIT Tech. Rep. 1996) in the context of time-lock puzzles. Moreover, there is no obvious reduction in the other direction, which suggests that the assumption of sequential hardness of modular Lucas sequences is strictly weaker than that of iterated modular squaring. In other words, the sequential hardness of modular Lucas sequences might hold even in the case of an algorithmic improvement violating the sequential hardness of iterated modular squaring. Second, we demonstrate the feasibility of constructing practically-efficient verifiable delay functions based on the sequential hardness of modular Lucas sequences. Our construction builds on the work of Pietrzak (ITCS 2019) by leveraging the intrinsic connection between the problem of computing modular Lucas sequences and exponentiation in an appropriate extension field.

On the cost of post-compromise security in concurrent Continuous Group-Key Agreement - Auerbach, Benedikt; Cueto Noval, Miguel; Pascual Perez, Guillermo; Pietrzak, Krzysztof Z (21st International Conference on Theory of Cryptography)
Continuous Group-Key Agreement (CGKA) allows a group of users to maintain a shared key. It is the fundamental cryptographic primitive underlying group messaging schemes and related protocols, most notably TreeKEM, the underlying key agreement protocol of the Messaging Layer Security (MLS) protocol, a standard for group messaging by the IETF. CKGA works in an asynchronous setting where parties only occasionally must come online, and their messages are relayed by an untrusted server. The most expensive operation provided by CKGA is that which allows for a user to refresh their key material in order to achieve forward secrecy (old messages are secure when a user is compromised) and post-compromise security (users can heal from compromise). One caveat of early CGKA protocols is that these update operations had to be performed sequentially, with any user wanting to update their key material having had to receive and process all previous updates. Late versions of TreeKEM do allow for concurrent updates at the cost of a communication overhead per update message that is linear in the number of updating parties. This was shown to be indeed necessary when achieving PCS in just two rounds of communication by [Bienstock et al. TCC’20]. The recently proposed protocol CoCoA [Alwen et al. Eurocrypt’22], however, shows that this overhead can be reduced if PCS requirements are relaxed, and only a logarithmic number of rounds is required. The natural question, thus, is whether CoCoA is optimal in this setting. In this work we answer this question, providing a lower bound on the cost (concretely, the amount of data to be uploaded to the server) for CGKA protocols that heal in an arbitrary k number of rounds, that shows that CoCoA is very close to optimal. Additionally, we extend CoCoA to heal in an arbitrary number of rounds, and propose a modification of it, with a reduced communication cost for certain k. We prove our bound in a combinatorial setting where the state of the protocol progresses in rounds, and the state of the protocol in each round is captured by a set system, each set specifying a set of users who share a secret key. We show this combinatorial model is equivalent to a symbolic model capturing building blocks including PRFs and public-key encryption, related to the one used by Bienstock et al. Our lower bound is of order k•n1+1/(k-1)/log(k), where 2≤k≤log(n) is the number of updates per user the protocol requires to heal. This generalizes the n2 bound for k=2 from Bienstock et al.. This bound almost matches the k⋅n1+2/(k-1) or k2⋅n1+1/(k-1) efficiency we get for the variants of the CoCoA protocol also introduced in this paper.

Generic-group lower bounds via reductions between geometric-search problems: With and without preprocessing - Auerbach, Benedikt; Hoffmann, Charlotte; Pascual Perez, Guillermo (21st International Conference on Theory of Cryptography)
The generic-group model (GGM) aims to capture algorithms working over groups of prime order that only rely on the group operation, but do not exploit any additional structure given by the concrete implementation of the group. In it, it is possible to prove information-theoretic lower bounds on the hardness of problems like the discrete logarithm (DL) or computational Diffie-Hellman (CDH). Thus, since its introduction, it has served as a valuable tool to assess the concrete security provided by cryptographic schemes based on such problems. A work on the related algebraic-group model (AGM) introduced a method, used by many subsequent works, to adapt GGM lower bounds for one problem to another, by means of conceptually simple reductions. In this work, we propose an alternative approach to extend GGM bounds from one problem to another. Following an idea by Yun [EC15], we show that, in the GGM, the security of a large class of problems can be reduced to that of geometric search-problems. By reducing the security of the resulting geometric-search problems to variants of the search-by-hypersurface problem, for which information theoretic lower bounds exist, we give alternative proofs of several results that used the AGM approach. The main advantage of our approach is that our reduction from geometric search-problems works, as well, for the GGM with preprocessing (more precisely the bit-fixing GGM introduced by Coretti, Dodis and Guo [Crypto18]). As a consequence, this opens up the possibility of transferring preprocessing GGM bounds from one problem to another, also by means of simple reductions. Concretely, we prove novel preprocessing bounds on the hardness of the d-strong discrete logarithm, the d-strong Diffie-Hellman inversion, and multi-instance CDH problems, as well as a large class of Uber assumptions. Additionally, our approach applies to Shoup’s GGM without additional restrictions on the query behavior of the adversary, while the recent works of Zhang, Zhou, and Katz [AC22] and Zhandry [Crypto22] highlight that this is not the case for the AGM approach.

Neutrophils on the hunt: Migratory strategies employed by neutrophils to fulfill their effector function - Stopp, Julian A

Binary decision diagrams on modern hardware - Pastva, Samuel; Henzinger, Thomas A (Proceedings of the 23rd Conference on Formal Methods in Computer-Aided Design)
Binary decision diagrams (BDDs) are one of the fundamental data structures in formal methods and computer science in general. However, the performance of BDD-based algorithms greatly depends on memory latency due to the reliance on large hash tables and thus, by extension, on the speed of random memory access. This hinders the full utilisation of resources available on modern CPUs, since the absolute memory latency has not improved significantly for at least a decade. In this paper, we explore several implementation techniques that improve the performance of BDD manipulation either through enhanced memory locality or by partially eliminating random memory access. On a benchmark suite of 600+ BDDs derived from real-world applications, we demonstrate runtime that is comparable or better than parallelising the same operations on eight CPU cores.

The RALF signaling pathway regulates cell wall integrity during pollen tube growth in maize - Zhou, Liang-Zi; Wang, Lele; Chen, Xia; Ge, Zengxiang; Mergner, Julia; Li, Xingli; Küster, Bernhard; Längst, Gernot; Qu, Li-Jia; Dresselhaus, Thomas (The Plant Cell)
Autocrine signaling pathways regulated by RAPID ALKALINIZATION FACTORs (RALFs) control cell wall integrity during pollen tube germination and growth in Arabidopsis (Arabidopsis thaliana). To investigate the role of pollen-specific RALFs in another plant species, we combined gene expression data with phylogenetic and biochemical studies to identify candidate orthologs in maize (Zea mays). We show that Clade IB ZmRALF2/3 mutations, but not Clade III ZmRALF1/5 mutations, cause cell wall instability in the sub-apical region of the growing pollen tube. ZmRALF2/3 are mainly located in the cell wall and are partially able to complement the pollen germination defect of their Arabidopsis orthologs AtRALF4/19. Mutations in ZmRALF2/3 compromise pectin distribution patterns leading to altered cell wall organization and thickness culminating in pollen tube burst. Clade IB, but not Clade III ZmRALFs, strongly interact as ligands with the pollen-specific Catharanthus roseus RLK1-like (CrRLK1L) receptor kinases Zea mays FERONIA-like (ZmFERL) 4/7/9, LORELEI-like glycosylphosphatidylinositol-anchor (LLG) proteins Zea mays LLG 1 and 2 (ZmLLG1/2) and Zea mays pollen extension-like (PEX) cell wall proteins ZmPEX2/4. Notably, ZmFERL4 outcompetes ZmLLG2 and ZmPEX2 outcompetes ZmFERL4 for ZmRALF2 binding. Based on these data, we suggest that Clade IB RALFs act in a dual role as cell wall components and extracellular sensors to regulate cell wall integrity and thickness during pollen tube growth in maize and probably other plants.
Keywords: Cell Biology; Plant Science

Token swapping on trees - Biniaz, Ahmad; Jain, Kshitij; Lubiw, Anna; Masárová, Zuzana; Miltzow, Tillmann; Mondal, Debajyoti; Naredla, Anurag Murty; Tkadlec, Josef; Turcotte, Alexi (Discrete Mathematics and Theoretical Computer Science)
The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete. We present some partial results: 1. An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan. 2. Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3. Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2. 3. A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars. In this version, tokens and vertices have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.

Executing and proving over dirty ledgers - Stefo, Christos; Xiang, Zhuolun; Kokoris Kogias, Eleftherios (27th International Conference on Financial Cryptography and Data Security)
Scaling blockchain protocols to perform on par with the expected needs of Web3.0 has been proven to be a challenging task with almost a decade of research. In the forefront of the current solution is the idea of separating the execution of the updates encoded in a block from the ordering of blocks. In order to achieve this, a new class of protocols called rollups has emerged. Rollups have as input a total ordering of valid and invalid transactions and as output a new valid state-transition. If we study rollups from a distributed computing perspective, we uncover that rollups take as input the output of a Byzantine Atomic Broadcast (BAB) protocol and convert it to a State Machine Replication (SMR) protocol. BAB and SMR, however, are considered equivalent as far as distributed computing is concerned and a solution to one can easily be retrofitted to solve the other simply by adding/removing an execution step before the validation of the input. This “easy” step of retrofitting an atomic broadcast solution to implement an SMR has, however, been overlooked in practice. In this paper, we formalize the problem and show that after BAB is solved, traditional impossibility results for consensus no longer apply towards an SMR. Leveraging this we propose a distributed execution protocol that allows reduced execution and storage cost per executor (O(log2n/n)) without relaxing the network assumptions of the underlying BAB protocol and providing censorship-resistance. Finally, we propose efficient non-interactive light client constructions that leverage our efficient execution protocols and do not require any synchrony assumptions or expensive ZK-proofs.

R2: Boosting liquidity in payment channel networks with online admission control - Bastankhah, Mahsa; Chatterjee, Krishnendu; Maddah-Ali, Mohammad Ali; Schmid, Stefan; Svoboda, Jakub; Yeo, Michelle X (27th International Conference on Financial Cryptography and Data Security)
Payment channel networks (PCNs) are a promising technology to improve the scalability of cryptocurrencies. PCNs, however, face the challenge that the frequent usage of certain routes may deplete channels in one direction, and hence prevent further transactions. In order to reap the full potential of PCNs, recharging and rebalancing mechanisms are required to provision channels, as well as an admission control logic to decide which transactions to reject in case capacity is insufficient. This paper presents a formal model of this optimisation problem. In particular, we consider an online algorithms perspective, where transactions arrive over time in an unpredictable manner. Our main contributions are competitive online algorithms which come with provable guarantees over time. We empirically evaluate our algorithms on randomly generated transactions to compare the average performance of our algorithms to our theoretical bounds. We also show how this model and approach differs from related problems in classic communication networks.

Divide & Scale: Formalization and roadmap to robust sharding - Avarikioti, Zeta; Desjardins, Antoine; Kokoris Kogias, Eleftherios; Wattenhofer, Roger (30th International Colloquium on Structural Information and Communication Complexity)
Sharding distributed ledgers is a promising on-chain solution for scaling blockchains but lacks formal grounds, nurturing skepticism on whether such complex systems can scale blockchains securely. We fill this gap by introducing the first formal framework as well as a roadmap to robust sharding. In particular, we first define the properties sharded distributed ledgers should fulfill. We build upon and extend the Bitcoin backbone protocol by defining consistency and scalability. Consistency encompasses the need for atomic execution of cross-shard transactions to preserve safety, whereas scalability encapsulates the speedup a sharded system can gain in comparison to a non-sharded system. Using our model, we explore the limitations of sharding. We show that a sharded ledger with n participants cannot scale under a fully adaptive adversary, but it can scale up to m shards where n=c'm log m, under an epoch-adaptive adversary; the constant c' encompasses the trade-off between security and scalability. This is possible only if the sharded ledgers create succinct proofs of the valid state updates at every epoch. We leverage our results to identify the sufficient components for robust sharding, which we incorporate in a protocol abstraction termed Divide & Scale. To demonstrate the power of our framework, we analyze the most prominent sharded blockchains (Elastico, Monoxide, OmniLedger, RapidChain) and pinpoint where they fail to meet the desired properties.

Zero-error communication over adversarial MACs - Zhang, Yihan (IEEE Transactions on Information Theory)
We consider zero-error communication over a two-transmitter deterministic adversarial multiple access channel (MAC) governed by an adversary who has access to the transmissions of both senders (hence called omniscient ) and aims to maliciously corrupt the communication. None of the encoders, jammer and decoder is allowed to randomize using private or public randomness. This enforces a combinatorial nature of the problem. Our model covers a large family of channels studied in the literature, including all deterministic discrete memoryless noisy or noiseless MACs. In this work, given an arbitrary two-transmitter deterministic omniscient adversarial MAC, we characterize when the capacity region: 1) has nonempty interior (in particular, is two-dimensional); 2) consists of two line segments (in particular, has empty interior); 3) consists of one line segment (in particular, is one-dimensional); 4) or only contains (0,0) (in particular, is zero-dimensional). This extends a recent result by Wang et al. (201 9) from the point-to-point setting to the multiple access setting. Indeed, our converse arguments build upon their generalized Plotkin bound and involve delicate case analysis. One of the technical challenges is to take care of both “joint confusability” and “marginal confusability”. In particular, the treatment of marginal confusability does not follow from the point-to-point results by Wang et al. Our achievability results follow from random coding with expurgation.
Keywords: Computer Science Applications; Information Systems

Dense 4D nanoscale reconstruction of living brain tissue - Velicky, Philipp; Miguel Villalba, Eder; Michalska, Julia M; Lyudchik, Julia; Wei, Donglai; Lin, Zudi; Watson, Jake; Troidl, Jakob; Beyer, Johanna; Ben Simon, Yoav; Sommer, Christoph M; Jahr, Wiebke; et al. (Nature Methods)
Three-dimensional (3D) reconstruction of living brain tissue down to an individual synapse level would create opportunities for decoding the dynamics and structure–function relationships of the brain’s complex and dense information processing network; however, this has been hindered by insufficient 3D resolution, inadequate signal-to-noise ratio and prohibitive light burden in optical imaging, whereas electron microscopy is inherently static. Here we solved these challenges by developing an integrated optical/machine-learning technology, LIONESS (live information-optimized nanoscopy enabling saturated segmentation). This leverages optical modifications to stimulated emission depletion microscopy in comprehensively, extracellularly labeled tissue and previous information on sample structure via machine learning to simultaneously achieve isotropic super-resolution, high signal-to-noise ratio and compatibility with living tissue. This allows dense deep-learning-based instance segmentation and 3D reconstruction at a synapse level, incorporating molecular, activity and morphodynamic information. LIONESS opens up avenues for studying the dynamic functional (nano-)architecture of living brain tissue.

Phytaspase Is capable of detaching the endoplasmic reticulum retrieval signal from tobacco calreticulin-3 - Teplova, Anastasiia; Pigidanov, Artemii A.; Serebryakova, Marina V.; Golyshev, Sergei A.; Galiullina, Raisa A.; Chichkova, Nina V.; Vartapetian, Andrey B. (International Journal of Molecular Sciences)
Soluble chaperones residing in the endoplasmic reticulum (ER) play vitally important roles in folding and quality control of newly synthesized proteins that transiently pass through the ER en route to their final destinations. These soluble residents of the ER are themselves endowed with an ER retrieval signal that enables the cell to bring the escaped residents back from the Golgi. Here, by using purified proteins, we showed that Nicotiana tabacum phytaspase, a plant aspartate-specific protease, introduces two breaks at the C-terminus of the N. tabacum ER resident calreticulin-3. These cleavages resulted in removal of either a dipeptide or a hexapeptide from the C-terminus of calreticulin-3 encompassing part or all of the ER retrieval signal. Consistently, expression of the calreticulin-3 derivative mimicking the phytaspase cleavage product in Nicotiana benthamiana cells demonstrated loss of the ER accumulation of the protein. Notably, upon its escape from the ER, calreticulin-3 was further processed by an unknown protease(s) to generate the free N-terminal (N) domain of calreticulin-3, which was ultimately secreted into the apoplast. Our study thus identified a specific proteolytic enzyme capable of precise detachment of the ER retrieval signal from a plant ER resident protein, with implications for the further fate of the escaped resident.
Keywords: Inorganic Chemistry; Organic Chemistry; Physical and Theoretical Chemistry; Computer Science Applications; Spectroscopy; Molecular Biology; General Medicine; Catalysis

Convergence rate to the Tracy–Widom laws for the largest eigenvalue of sample covariance matrices - Schnelli, Kevin; Xu, Yuanyuan (The Annals of Applied Probability)
We establish a quantitative version of the Tracy–Widom law for the largest eigenvalue of high-dimensional sample covariance matrices. To be precise, we show that the fluctuations of the largest eigenvalue of a sample covariance matrix X∗X converge to its Tracy–Widom limit at a rate nearly N−1/3, where X is an M×N random matrix whose entries are independent real or complex random variables, assuming that both M and N tend to infinity at a constant rate. This result improves the previous estimate N−2/9 obtained by Wang (2019). Our proof relies on a Green function comparison method (Adv. Math. 229 (2012) 1435–1515) using iterative cumulant expansions, the local laws for the Green function and asymptotic properties of the correlation kernel of the white Wishart ensemble.
Keywords: Statistics; Probability and Uncertainty; Statistics and Probability

Divergence of separated nets with respect to displacement equivalence - Dymond, Michael; Kaluza, Vojtech (Geometriae Dedicata)
We introduce a hierachy of equivalence relations on the set of separated nets of a given Euclidean space, indexed by concave increasing functions ϕ:(0,∞)→(0,∞). Two separated nets are called ϕ-displacement equivalent if, roughly speaking, there is a bijection between them which, for large radii R, displaces points of norm at most R by something of order at most ϕ(R). We show that the spectrum of ϕ-displacement equivalence spans from the established notion of bounded displacement equivalence, which corresponds to bounded ϕ, to the indiscrete equivalence relation, coresponding to ϕ(R)∈Ω(R), in which all separated nets are equivalent. In between the two ends of this spectrum, the notions of ϕ-displacement equivalence are shown to be pairwise distinct with respect to the asymptotic classes of ϕ(R) for R→∞. We further undertake a comparison of our notion of ϕ-displacement equivalence with previously studied relations on separated nets. Particular attention is given to the interaction of the notions of ϕ-displacement equivalence with that of bilipschitz equivalence.

Deterministic clustering in high dimensional spaces: Sketches and approximation - Cohen-Addad, Vincent; Saulpic, David; Schwiegelshohn, Chris (2023 IEEE 64th Annual Symposium on Foundations of Computer Science)
In all state-of-the-art sketching and coreset techniques for clustering, as well as in the best known fixed-parameter tractable approximation algorithms, randomness plays a key role. For the classic k-median and k-means problems, there are no known deterministic dimensionality reduction procedure or coreset construction that avoid an exponential dependency on the input dimension d, the precision parameter $ε^{-1}$ or k. Furthermore, there is no coreset construction that succeeds with probability $1-1/n$ and whose size does not depend on the number of input points, n. This has led researchers in the area to ask what is the power of randomness for clustering sketches [Feldman WIREs Data Mining Knowl. Discov’20].Similarly, the best approximation ratio achievable deterministically without a complexity exponential in the dimension are $1+\sqrt{2}$ for k-median [Cohen-Addad, Esfandiari, Mirrokni, Narayanan, STOC’22] and 6.12903 for k-means [Grandoni, Ostrovsky, Rabani, Schulman, Venkat, Inf. Process. Lett.’22]. Those are the best results, even when allowing a complexity FPT in the number of clusters k: this stands in sharp contrast with the $(1+ε)$-approximation achievable in that case, when allowing randomization.In this paper, we provide deterministic sketches constructions for clustering, whose size bounds are close to the best-known randomized ones. We show how to compute a dimension reduction onto $ε^{-O(1)} \log k$ dimensions in time $k^{O\left(ε^{-O(1)}+\log \log k\right)}$ poly $(n d)$, and how to build a coreset of size $O\left(k^{2} \log ^{3} k ε^{-O(1)}\right)$ in time $2^{ε^{O(1)} k \log ^{3} k}+k^{O\left(ε^{-O(1)}+\log \log k\right)}$ poly $(n d)$. In the case where k is small, this answers an open question of [Feldman WIDM’20] and [Munteanu and Schwiegelshohn, Künstliche Intell. ’18] on whether it is possible to efficiently compute coresets deterministically.We also construct a deterministic algorithm for computing $(1+$ $ε)$-approximation to k-median and k-means in high dimensional Euclidean spaces in time $2^{k^{2} \log ^{3} k / ε^{O(1)}}$ poly $(n d)$, close to the best randomized complexity of $2^{(k / ε)^{O(1)}}$ nd (see [Kumar, Sabharwal, Sen, JACM 10] and [Bhattacharya, Jaiswal, Kumar, TCS’18]).Furthermore, our new insights on sketches also yield a randomized coreset construction that uses uniform sampling, that immediately improves over the recent results of [Braverman et al. FOCS ’22] by a factor k.

Branched actin cortices reconstituted in vesicles sense membrane curvature - Baldauf, Lucia; Frey, Felix F; Arribas Perez, Marcos; Idema, Timon; Koenderink, Gijsje H. (Biophysical Journal)
The actin cortex is a complex cytoskeletal machinery that drives and responds to changes in cell shape. It must generate or adapt to plasma membrane curvature to facilitate diverse functions such as cell division, migration, and phagocytosis. Due to the complex molecular makeup of the actin cortex, it remains unclear whether actin networks are inherently able to sense and generate membrane curvature, or whether they rely on their diverse binding partners to accomplish this. Here, we show that curvature sensing is an inherent capability of branched actin networks nucleated by Arp2/3 and VCA. We develop a robust method to encapsulate actin inside giant unilamellar vesicles (GUVs) and assemble an actin cortex at the inner surface of the GUV membrane. We show that actin forms a uniform and thin cortical layer when present at high concentration and distinct patches associated with negative membrane curvature at low concentration. Serendipitously, we find that the GUV production method also produces dumbbell-shaped GUVs, which we explain using mathematical modeling in terms of membrane hemifusion of nested GUVs. We find that branched actin networks preferentially assemble at the neck of the dumbbells, which possess a micrometer-range convex curvature comparable with the curvature of the actin patches found in spherical GUVs. Minimal branched actin networks can thus sense membrane curvature, which may help mammalian cells to robustly recruit actin to curved membranes to facilitate diverse cellular functions such as cytokinesis and migration.
Keywords: Biophysics

Automated verification and control of infinite state stochastic systems - Zikelic, Dorde
Stochastic systems provide a formal framework for modelling and quantifying uncertainty in systems and have been widely adopted in many application domains. Formal verification and control of finite state stochastic systems, a subfield of formal methods also known as probabilistic model checking, is well studied. In contrast, formal verification and control of infinite state stochastic systems have received comparatively less attention. However, infinite state stochastic systems commonly arise in practice. For instance, probabilistic models that contain continuous probability distributions such as normal or uniform, or stochastic dynamical systems which are a classical model for control under uncertainty, both give rise to infinite state systems. The goal of this thesis is to contribute to laying theoretical and algorithmic foundations of fully automated formal verification and control of infinite state stochastic systems, with a particular focus on systems that may be executed over a long or infinite time. We consider formal verification of infinite state stochastic systems in the setting of static analysis of probabilistic programs and formal control in the setting of controller synthesis in stochastic dynamical systems. For both problems, we present some of the first fully automated methods for probabilistic (a.k.a. quantitative) reachability and safety analysis applicable to infinite time horizon systems. We also advance the state of the art of probability 1 (a.k.a. qualitative) reachability analysis for both problems. Finally, for formal controller synthesis in stochastic dynamical systems, we present a novel framework for learning neural network control policies in stochastic dynamical systems with formal guarantees on correctness with respect to quantitative reachability, safety or reach-avoid specifications.

Shortest dominating set reconfiguration under token sliding - Křišťan, Jan Matyáš; Svoboda, Jakub (24th International Symposium on Fundamentals of Computation Theory)
In this paper, we present novel algorithms that efficiently compute a shortest reconfiguration sequence between two given dominating sets in trees and interval graphs under the TOKEN SLIDING model. In this problem, a graph is provided along with its two dominating sets, which can be imagined as tokens placed on vertices. The objective is to find a shortest sequence of dominating sets that transforms one set into the other, with each set in the sequence resulting from sliding a single token in the previous set. While identifying any sequence has been well studied, our work presents the first polynomial algorithms for this optimization variant in the context of dominating sets.

Proof of availability and retrieval in a modular blockchain architecture - Cohen, Shir; Goren, Guy; Kokoris Kogias, Eleftherios; Sonnino, Alberto; Spiegelman, Alexander (27th International Conference on Financial Cryptography and Data Security)
This paper explores a modular design architecture aimed at helping blockchains (and other SMR implementation) to scale to a very large number of processes. This comes in contrast to existing monolithic architectures that interleave transaction dissemination, ordering, and execution in a single functionality. To achieve this we first split the monolith to multiple layers which can use existing distributed computing primitives. The exact specifications of the data dissemination part are formally defined by the Proof of Availability & Retrieval (PoA &R) abstraction. Solutions to the PoA &R problem contain two related sub-protocols: one that “pushes” information into the network and another that “pulls” this information. Regarding the latter, there is a dearth of research literature which is rectified in this paper. We present a family of pulling sub-protocols and rigorously analyze them. Extensive simulations support the theoretical claims of efficiency and robustness in case of a very large number of players. Finally, actual implementation and deployment on a small number of machines (roughly the size of several industrial systems) demonstrates the viability of the architecture’s paradigm.

Learning control policies for stochastic systems with reach-avoid guarantees - Zikelic, Dorde; Lechner, Mathias; Henzinger, Thomas A; Chatterjee, Krishnendu (Proceedings of the 37th AAAI Conference on Artificial Intelligence)
We study the problem of learning controllers for discrete-time non-linear stochastic dynamical systems with formal reach-avoid guarantees. This work presents the first method for providing formal reach-avoid guarantees, which combine and generalize stability and safety guarantees, with a tolerable probability threshold p in [0,1] over the infinite time horizon. Our method leverages advances in machine learning literature and it represents formal certificates as neural networks. In particular, we learn a certificate in the form of a reach-avoid supermartingale (RASM), a novel notion that we introduce in this work. Our RASMs provide reachability and avoidance guarantees by imposing constraints on what can be viewed as a stochastic extension of level sets of Lyapunov functions for deterministic systems. Our approach solves several important problems -- it can be used to learn a control policy from scratch, to verify a reach-avoid specification for a fixed control policy, or to fine-tune a pre-trained policy if it does not satisfy the reach-avoid specification. We validate our approach on 3 stochastic non-linear reinforcement learning tasks.
Keywords: General Medicine

Entangling microwaves and telecom wavelength light - Sahu, Rishabh; Qiu, Liu; Hease, William J; Arnold, Georg M; Minoguchi, Yuri; Rabl, Peter; Fink, Johannes M (Frontiers in Optics + Laser Science 2023)
We entangled microwave and optical photons for the first time as verified by a measured two-mode vacuum squeezing of 0.7 dB. This electro-optic entanglement is the key resource needed to connect cryogenic quantum circuits.

Tale of cAMP as a second messenger in auxin signaling and beyond - Qi, Linlin; Friml, Jiří (New Phytologist)
The 3′,5′-cyclic adenosine monophosphate (cAMP) is a versatile second messenger in many mammalian signaling pathways. However, its role in plants remains not well-recognized. Recent discovery of adenylate cyclase (AC) activity for transport inhibitor response 1/auxin-signaling F-box proteins (TIR1/AFB) auxin receptors and the demonstration of its importance for canonical auxin signaling put plant cAMP research back into spotlight. This insight briefly summarizes the well-established cAMP signaling pathways in mammalian cells and describes the turbulent and controversial history of plant cAMP research highlighting the major progress and the unresolved points. We also briefly review the current paradigm of auxin signaling to provide a background for the discussion on the AC activity of TIR1/AFB auxin receptors and its potential role in transcriptional auxin signaling as well as impact of these discoveries on plant cAMP research in general.

Codes for the Z-channel - Polyanskii, Nikita; Zhang, Yihan (IEEE Transactions on Information Theory)
This paper is a collection of results on combinatorial properties of codes for the Z-channel . A Z-channel with error fraction τ takes as input a length- n binary codeword and injects in an adversarial manner up to n τ asymmetric errors, i.e., errors that only zero out bits but do not flip 0’s to 1’s. It is known that the largest ( L - 1)-list-decodable code for the Z-channel with error fraction τ has exponential size (in n ) if τ is less than a critical value that we call the ( L - 1)- list-decoding Plotkin point and has constant size if τ is larger than the threshold. The ( L -1)-list-decoding Plotkin point is known to be L -1/L-1 – L -L/ L-1 , which equals 1/4 for unique-decoding with L -1 = 1. In this paper, we derive various results for the size of the largest codes above and below the list-decoding Plotkin point. In particular, we show that the largest ( L -1)-list-decodable code ε-above the Plotkin point, for any given sufficiently small positive constant ε > 0, has size Θ L (ε -3/2 ) for any L - 1 ≥ 1. We also devise upper and lower bounds on the exponential size of codes below the list-decoding Plotkin point.

An energy decomposition theorem for matrices and related questions - Mohammadi, Ali; Pham, Thang; Wang, Yiting (Canadian Mathematical Bulletin)
Given A⊆GL2(Fq), we prove that there exist disjoint subsets B,C⊆A such that A=B⊔C and their additive and multiplicative energies satisfying max{E+(B),E×(C)}≪|A|3/M(|A|), where M(|A|)=min{q4/3/|A|1/3(log|A|)2/3,|A|4/5/q13/5(log|A|)27/10}. We also study some related questions on moderate expanders over matrix rings, namely, for A,B,C⊆GL2(Fq), we have |AB+C|, |(A+B)C|≫q4, whenever |A||B||C|≫q10+1/2. These improve earlier results due to Karabulut, Koh, Pham, Shen, and Vinh ([2019], Expanding phenomena over matrix rings, ForumMath., 31, 951–970).

Chemical inhibition of Arabidopsis PIN-FORMED auxin transporters by the anti-inflammatory drug naproxen - Xia, Jing; Kong, Mengjuan; Yang, Zhisen; Sun, Lianghanxiao; Peng, Yakun; Mao, Yanbo; Wei, Hong; Ying, Wei; Gao, Yongxiao; Friml, Jiří; Weng, Jianping; Liu, Xin; et al. (Plant Communications)
The phytohormone auxin plays central roles in many growth and developmental processes in plants. Development of chemical tools targeting the auxin pathway is useful for both plant biology and agriculture. Here we reveal that naproxen, a synthetic compound with anti-inflammatory activity in humans, acts as an auxin transport inhibitor targeting PIN-FORMED (PIN) transporters in plants. Physiological experiments indicate that exogenous naproxen treatment affects pleiotropic auxin-regulated developmental processes. Additional cellular and biochemical evidence indicates that naproxen suppresses auxin transport, specifically PIN-mediated auxin efflux. Moreover, biochemical and structural analyses confirm that naproxen binds directly to PIN1 protein via the same binding cavity as the indole-3-acetic acid substrate. Thus, by combining cellular, biochemical, and structural approaches, this study clearly establishes that naproxen is a PIN inhibitor and elucidates the underlying mechanisms. Further use of this compound may advance our understanding of the molecular mechanisms of PIN-mediated auxin transport and expand our toolkit in auxin biology and agriculture.

Derivations and KMS-symmetric quantum Markov semigroups - Vernooij, Matthijs; Wirth, Melchior (Communications in Mathematical Physics)
We prove that the generator of the L2 implementation of a KMS-symmetric quantum Markov semigroup can be expressed as the square of a derivation with values in a Hilbert bimodule, extending earlier results by Cipriani and Sauvageot for tracially symmetric semigroups and the second-named author for GNS-symmetric semigroups. This result hinges on the introduction of a new completely positive map on the algebra of bounded operators on the GNS Hilbert space. This transformation maps symmetric Markov operators to symmetric Markov operators and is essential to obtain the required inner product on the Hilbert bimodule.

Successive vertex orderings of fully regular graphs - Fang, Lixing; Huang, Hao; Pach, János; Tardos, Gábor; Zuo, Junchi (Journal of Combinatorial Theory. Series A)
A graph G=(V, E) is called fully regular if for every independent set I c V, the number of vertices in V\I that are not connected to any element of I depends only on the size of I. A linear ordering of the vertices of G is called successive if for every i, the first i vertices induce a connected subgraph of G. We give an explicit formula for the number of successive vertex orderings of a fully regular graph. As an application of our results, we give alternative proofs of two theorems of Stanley and Gao & Peng, determining the number of linear edge orderings of complete graphs and complete bipartite graphs, respectively, with the property that the first i edges induce a connected subgraph. As another application, we give a simple product formula for the number of linear orderings of the hyperedges of a complete 3-partite 3-uniform hypergraph such that, for every i, the first i hyperedges induce a connected subgraph. We found similar formulas for complete (non-partite) 3-uniform hypergraphs and in another closely related case, but we managed to verify them only when the number of vertices is small.