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.

Polycrystalline phases grown in-situ engendering unique mechanism of charge storage in polyaniline-graphite composite - Mahato, Neelima; Singh, Saurabh; Faisal, Mohammad; Sreekanth, T. V.M.; Majumder, Sutripto; Yoo, Kisoo; Kim, Jonghoon (Synthetic Metals)
We report on a simple surfactant/template free chemical route for the synthesis of semi-polycrystalline polyaniline-graphite (SPani-graphite) composite and its application as an electroactive material in electrochemical charge storage. The synthesized material exhibits well-defined poly-crystallographic lattices in high resolution transmission electron micrographs and sharp peaks in x-ray diffraction spectra suggesting crystalline nature of the material. The specific capacitance computed from the galvanostatic charge-discharge (GCD) data obtained from 3-electrode cell configuration using 1 M aq. Na2SO4 as an electrolyte was 111.4 F g−1 at a current density of 0.1 A g−1 which rises to 269 F g−1 at an elevated current density of 1.0 A g−1. A similar pattern of increase in the specific capacitance values with an increase in the current density was observed in the results obtained from 2-electrode symmetric device configuration using polymer gel electrolyte (xanthan gum in 1 M aq. Na2SO4). The specific capacitance computed from the GCD data obtained from the device configuration was 20 F g−1 at the current density of 1.0 A g−1. The device delivers an energy density of 1.7 Wh kg−1 and a power density of 2.48 kWh kg−1 at an applied current density of 0.5 A g−1 suggesting an excellent rate capability and power management. In addition, the device exhibits ⁓92 % specific capacitance retention up to 8000 continuous GCD cycles and ⁓80 % coulombic efficiency up to 10,000 continuous GCD cycles indicating excellent cycling stability. The unique feature of increasing specific capacitance with respect to applied current density is attributed to the presence of semi-polycrystalline phases in the SPani-graphite matrix. The material behaves as a surface redox supercapacitor and its unique mechanism of charge storage is discussed in detail in the article.

BAX activation in mouse retinal ganglion cells occurs in two temporally and mechanistically distinct steps - Maes, Margaret E; Donahue, Ryan J.; Schlamp, Cassandra L.; Marola, Olivia J.; Libby, Richard T.; Nickells, Robert W. (Molecular Neurodegeneration)
Background: Pro-apoptotic BAX is a central mediator of retinal ganglion cell (RGC) death after optic nerve damage. BAX activation occurs in two stages including translocation of latent BAX to the mitochondrial outer membrane (MOM) and then permeabilization of the MOM to facilitate the release of apoptotic signaling molecules. As a critical component of RGC death, BAX is an attractive target for neuroprotective therapies and an understanding of the kinetics of BAX activation and the mechanisms controlling the two stages of this process in RGCs is potentially valuable in informing the development of a neuroprotective strategy. Methods: The kinetics of BAX translocation were assessed by both static and live-cell imaging of a GFP-BAX fusion protein introduced into RGCs using AAV2-mediated gene transfer in mice. Activation of BAX was achieved using an acute optic nerve crush (ONC) protocol. Live-cell imaging of GFP-BAX was achieved using explants of mouse retina harvested 7 days after ONC. Kinetics of translocation in RGCs were compared to GFP-BAX translocation in 661W tissue culture cells. Permeabilization of GFP-BAX was assessed by staining with the 6A7 monoclonal antibody, which recognizes a conformational change in this protein after MOM insertion. Assessment of individual kinases associated with both stages of activation was made using small molecule inhibitors injected into the vitreous either independently or in concert with ONC surgery. The contribution of the Dual Leucine Zipper-JUN-N-Terminal Kinase cascade was evaluated using mice with a double conditional knock-out of both Mkk4 and Mkk7. Results: ONC induces the translocation of GFP-BAX in RGCs at a slower rate and with less intracellular synchronicity than 661W cells, but exhibits less variability among mitochondrial foci within a single cell. GFP-BAX was also found to translocate in all compartments of an RGC including the dendritic arbor and axon. Approximately 6% of translocating RGCs exhibited retrotranslocation of BAX immediately following translocation. Unlike tissue culture cells, which exhibit simultaneous translocation and permeabilization, RGCs exhibited a significant delay between these two stages, similar to detached cells undergoing anoikis. Translocation, with minimal permeabilization could be induced in a subset of RGCs using an inhibitor of Focal Adhesion Kinase (PF573228). Permeabilization after ONC, in a majority of RGCs, could be inhibited with a broad spectrum kinase inhibitor (sunitinib) or a selective inhibitor for p38/MAPK14 (SB203580). Intervention of DLK-JNK axis signaling abrogated GFP-BAX translocation after ONC. Conclusions: A comparison between BAX activation kinetics in tissue culture cells and in cells of a complex tissue environment shows distinct differences indicating that caution should be used when translating findings from one condition to the other. RGCs exhibit both a delay between translocation and permeabilization and the ability for translocated BAX to be retrotranslocated, suggesting several stages at which intervention of the activation process could be exploited in the design of a therapeutic strategy.

Fast symbolic algorithms for mega-regular games under strong transition fairness - Banerjee, Tamajit; Majumdar, Rupak; Mallik, Kaushik; Schmuck, Anne-Kathrin; Soudjani, Sadegh (TheoretiCS)
We consider fixpoint algorithms for two-player games on graphs with $ω$-regular winning conditions, where the environment is constrained by a strong transition fairness assumption. Strong transition fairness is a widely occurring special case of strong fairness, which requires that any execution is strongly fair with respect to a specified set of live edges: whenever the source vertex of a live edge is visited infinitely often along a play, the edge itself is traversed infinitely often along the play as well. We show that, surprisingly, strong transition fairness retains the algorithmic characteristics of the fixpoint algorithms for $ω$-regular games -- the new algorithms have the same alternation depth as the classical algorithms but invoke a new type of predecessor operator. For Rabin games with $k$ pairs, the complexity of the new algorithm is $O(n^{k+2}k!)$ symbolic steps, which is independent of the number of live edges in the strong transition fairness assumption. Further, we show that GR(1) specifications with strong transition fairness assumptions can be solved with a 3-nested fixpoint algorithm, same as the usual algorithm. In contrast, strong fairness necessarily requires increasing the alternation depth depending on the number of fairness assumptions. We get symbolic algorithms for (generalized) Rabin, parity and GR(1) objectives under strong transition fairness assumptions as well as a direct symbolic algorithm for qualitative winning in stochastic $ω$-regular games that runs in $O(n^{k+2}k!)$ symbolic steps, improving the state of the art. Finally, we have implemented a BDD-based synthesis engine based on our algorithm. We show on a set of synthetic and real benchmarks that our algorithm is scalable, parallelizable, and outperforms previous algorithms by orders of magnitude.

Shortcuts for causal discovery of nonlinear models by score matching - Montagna, Francesco; Noceti, Nicoletta; Rosasco, Lorenzo; Locatello, Francesco (arXiv)
The use of simulated data in the field of causal discovery is ubiquitous due to the scarcity of annotated real data. Recently, Reisach et al., 2021 highlighted the emergence of patterns in simulated linear data, which displays increasing marginal variance in the casual direction. As an ablation in their experiments, Montagna et al., 2023 found that similar patterns may emerge in nonlinear models for the variance of the score vector $\nabla \log p_{X}$, and introduced the ScoreSort algorithm. In this work, we formally define and characterize this score-sortability pattern of nonlinear additive noise models. We find that it defines a class of identifiable (bivariate) causal models overlapping with nonlinear additive noise models. We theoretically demonstrate the advantages of ScoreSort in terms of statistical efficiency compared to prior state-of-the-art score matching-based methods and empirically show the score-sortability of the most common synthetic benchmarks in the literature. Our findings remark (1) the lack of diversity in the data as an important limitation in the evaluation of nonlinear causal discovery approaches, (2) the importance of thoroughly testing different settings within a problem class, and (3) the importance of analyzing statistical properties in causal discovery, where research is often limited to defining identifiability conditions of the model.

Phenotype control of partially specified boolean networks - Beneš, Nikola; Brim, Luboš; Pastva, Samuel; Šafránek, David; Šmijáková, Eva (21st International Conference on Computational Methods in Systems Biology)
Partially specified Boolean networks (PSBNs) represent a promising framework for the qualitative modelling of biological systems in which the logic of interactions is not completely known. Phenotype control aims to stabilise the network in states exhibiting specific traits. In this paper, we define the phenotype control problem in the context of asynchronous PSBNs and propose a novel semi-symbolic algorithm for solving this problem with permanent variable perturbations.

Universal Functionals in Density Functional Theory - Lewin, Mathieu; Lieb, Elliott H.; Seiringer, Robert (Density Functional Theory)
In this chapter we first review the Levy–Lieb functional, which gives the lowest kinetic and interaction energy that can be reached with all possible quantum states having a given density. We discuss two possible convex generalizations of this functional, corresponding to using mixed canonical and grand-canonical states, respectively. We present some recent works about the local density approximation, in which the functionals get replaced by purely local functionals constructed using the uniform electron gas energy per unit volume. We then review the known upper and lower bounds on the Levy–Lieb functionals. We start with the kinetic energy alone, then turn to the classical interaction alone, before we are able to put everything together. A later section is devoted to the Hohenberg–Kohn theorem and the role of many-body unique continuation in its proof.

Spatiotemporal signaling during assembly of the bacterial divisome - Radler, Philipp
Cell division in Escherichia coli is performed by the divisome, a multi-protein complex composed of more than 30 proteins. The divisome spans from the cytoplasm through the inner membrane to the cell wall and the outer membrane. Divisome assembly is initiated by a cytoskeletal structure, the so-called Z-ring, which localizes at the center of the E. coli cell and determines the position of the future cell septum. The Z-ring is composed of the highly conserved bacterial tubulin homologue FtsZ, which forms treadmilling filaments. These filaments are recruited to the inner membrane by FtsA, a highly conserved bacterial actin homologue. FtsA interacts with other proteins in the periplasm and thus connects the cytoplasmic and periplasmic components of the divisome. A previous model postulated that FtsA regulates maturation of the divisome by switching from an oligomeric, inactive state to a monomeric and active state. This model was based mostly on in vivo studies, as a biochemical characterization of FtsA has been hampered by difficulties in purifying the protein. Here, we studied FtsA using an in vitro reconstitution approach and aimed to answer two questions: (i) How are dynamics from cytoplasmic, treadmilling FtsZ filaments coupled to proteins acting in the periplasmic space and (ii) How does FtsA regulate the maturation of the divisome? We found that the cytoplasmic peptides of the transmembrane proteins FtsN and FtsQ interact directly with FtsA and can follow the spatiotemporal signal of FtsA/Z filaments. When we investigated the underlying mechanism by imaging single molecules of FtsNcyto, we found the peptide to interact transiently with FtsA. An in depth analysis of the single molecule trajectories helped to postulate a model where PG synthases follow the dynamics of FtsZ by a diffusion and capture mechanism. Following up on these findings we were interested in how the self-interaction of FtsA changes when it encounters FtsNcyto and if we can confirm the proposed oligomer-monomer switch. For this, we compared the behavior of the previously identified, hyperactive mutant FtsA R286W with wildtype FtsA. The mutant outperforms WT in mirroring and transmitting the spatiotemporal signal of treadmilling FtsZ filaments. Surprisingly however, we found that this was not due to a difference in the self-interaction strength of the two variants, but a difference in their membrane residence time. Furthermore, in contrast to our expectations, upon binding of FtsNcyto the measured self-interaction of FtsA actually increased. We propose that FtsNcyto induces a rearrangement of the oligomeric architecture of FtsA. In further consequence this change leads to more persistent FtsZ filaments which results in a defined signalling zone, allowing formation of the mature divisome. The observed difference between FtsA WT and R286W is due to the vastly different membrane turnover of the proteins. R286W cycles 5-10x faster compared to WT which allows to sample FtsZ filaments at faster frequencies. These findings can explain the observed differences in toxicity for overexpression of FtsA WT and R286W and help to understand how FtsA regulates divisome maturation.
Keywords: Cell Division; Reconstitution; FtsZ; FtsA; Divisome; E.coli

A flexible toolchain for symbolic rabin games under fair and stochastic uncertainties - Majumdar, Rupak; Mallik, Kaushik; Rychlicki, Mateusz; Schmuck, Anne-Kathrin; Soudjani, Sadegh (35th International Conference on Computer Aided Verification)
We present a flexible and efficient toolchain to symbolically solve (standard) Rabin games, fair-adversarial Rabin games, and 2 1/2 license type-player Rabin games. To our best knowledge, our tools are the first ones to be able to solve these problems. Furthermore, using these flexible game solvers as a back-end, we implemented a tool for computing correct-by-construction controllers for stochastic dynamical systems under LTL specifications. Our implementations use the recent theoretical result that all of these games can be solved using the same symbolic fixpoint algorithm but utilizing different, domain specific calculations of the involved predecessor operators. The main feature of our toolchain is the utilization of two programming abstractions: one to separate the symbolic fixpoint computations from the predecessor calculations, and another one to allow the integration of different BDD libraries as back-ends. In particular, we employ a multi-threaded execution of the fixpoint algorithm by using the multi-threaded BDD library Sylvan, which leads to enormous computational savings.

Correct approximation of stationary distributions - Meggendorfer, Tobias (TACAS 2023: Tools and Algorithms for the Construction and Analysis of Systems)
A classical problem for Markov chains is determining their stationary (or steady-state) distribution. This problem has an equally classical solution based on eigenvectors and linear equation systems. However, this approach does not scale to large instances, and iterative solutions are desirable. It turns out that a naive approach, as used by current model checkers, may yield completely wrong results. We present a new approach, which utilizes recent advances in partial exploration and mean payoff computation to obtain a correct, converging approximation.

Lincheck: A practical framework for testing concurrent data structures on JVM - Koval, Nikita; Fedorov, Alexander; Sokolova, Maria; Tsitelov, Dmitry; Alistarh, Dan-Adrian (35th International Conference on Computer Aided Verification)
This paper presents Lincheck, a new practical and user-friendly framework for testing concurrent algorithms on the Java Virtual Machine (JVM). Lincheck provides a simple and declarative way to write concurrent tests: instead of describing how to perform the test, users specify what to test by declaring all the operations to examine; the framework automatically handles the rest. As a result, tests written with Lincheck are concise and easy to understand. The framework automatically generates a set of concurrent scenarios, examines them using stress-testing or bounded model checking, and verifies that the results of each invocation are correct. Notably, if an error is detected via model checking, Lincheck provides an easy-to-follow trace to reproduce it, significantly simplifying the bug investigation. To the best of our knowledge, Lincheck is the first production-ready tool on the JVM that offers such a simple way of writing concurrent tests, without requiring special skills or expertise. We successfully integrated Lincheck in the development process of several large projects, such as Kotlin Coroutines, and identified new bugs in popular concurrency libraries, such as a race in Java’s standard ConcurrentLinkedDeque and a liveliness bug in Java’s AbstractQueuedSynchronizer framework, which is used in most of the synchronization primitives. We believe that Lincheck can significantly improve the quality and productivity of concurrent algorithms research and development and become the state-of-the-art tool for checking their correctness.

Lincheck: A practical framework for testing concurrent data structures on JVM - Koval, Nikita; Fedorov, Alexander; Sokolova, Maria; Tsitelov, Dmitry; Alistarh, Dan-Adrian
Lincheck is a new practical and user-friendly framework for testing concurrent data structures on the Java Virtual Machine (JVM). It provides a simple and declarative way to write concurrent tests. Instead of describing how to perform the test, users specify what to test by declaring all the operations to examine; the framework automatically handles the rest. As a result, tests written with Lincheck are concise and easy to understand. The artifact presents a collection of Lincheck tests that discover new bugs in popular libraries and implementations from the concurrency literature -- they are listed in Table 1, Section 3. To evaluate the performance of Lincheck analysis, the collection of tests also includes those which check correct data structures and, thus, always succeed. Similarly to Table 2, Section 3, the experiments demonstrate the reasonable time to perform a test. Finally, Lincheck provides user-friendly output with an easy-to-follow trace to reproduce a detected error, significantly simplifying further investigation.

Monitoring hyperproperties with prefix transducers - Chalupa, Marek; Henzinger, Thomas A (23nd International Conference on Runtime Verification)
Hyperproperties are properties that relate multiple execution traces. Previous work on monitoring hyperproperties focused on synchronous hyperproperties, usually specified in HyperLTL. When monitoring synchronous hyperproperties, all traces are assumed to proceed at the same speed. We introduce (multi-trace) prefix transducers and show how to use them for monitoring synchronous as well as, for the first time, asynchronous hyperproperties. Prefix transducers map multiple input traces into one or more output traces by incrementally matching prefixes of the input traces against expressions similar to regular expressions. The prefixes of different traces which are consumed by a single matching step of the monitor may have different lengths. The deterministic and executable nature of prefix transducers makes them more suitable as an intermediate formalism for runtime verification than logical specifications, which tend to be highly non-deterministic, especially in the case of asynchronous hyperproperties. We report on a set of experiments about monitoring asynchronous version of observational determinism.

Individual and social immunity against viral infections in ants - Franschitz, Anna
Social insects fight disease using their individual immune systems and the cooperative sanitary behaviors of colony members. These social defenses are well explored against externally-infecting pathogens, but little is known about defense strategies against internally-infecting pathogens, such as viruses. Viruses are ubiquitous and in the last decades it has become evident that also many ant species harbor viruses. We present one of the first studies addressing transmission dynamics and collective disease defenses against viruses in ants on a mechanistic level. I successfully established an experimental ant host – viral pathogen system as a model for the defense strategies used by social insects against internal pathogen infections, as outlined in the third chapter. In particular, we studied how garden ants (Lasius neglectus) defend themselves and their colonies against the generalist insect virus CrPV (cricket paralysis virus). We chose microinjections of virus directly into the ants’ hemolymph because it allowed us to use a defined exposure dose. Here we show that this is a good model system, as the virus is replicating and thus infecting the host. The ants mount a clear individual immune response against the viral infection, which is characterized by a specific siRNA pattern, namely siRNAs mapping against the viral genome with a peak of 21 and 22 bp long fragments. The onset of this immune response is consistent with the timeline of viral replication that starts already within two days post injection. The disease manifests in decreased survival over a course of two to three weeks. Regarding group living, we find that infected ants show a strong individual immune response, but that their course of disease is little affected by nestmate presence, as described in chapter four. Hence, we do not find social immunity in the context of viral infections in ants. Nestmates, however, can contract the virus. Using Drosophila S2R+ cells in culture, we showed that 94 % of the nestmates contract active virus within four days of social contact to an infected individual. Virus is transmitted in low doses, thus not causing disease transmission within the colony. While virus can be transmitted during short direct contacts, we also assume transmission from deceased ants and show that the nestmates’ immune system gets activated after contracting a low viral dose. We find considerable potential for indirect transmission via the nest space. Virus is shed to the nest, where it stays viable for one week and is also picked up by other ants. Apart from that, we want to underline the potential of ant poison as antiviral agent. We determined that ant poison successfully inactivates CrPV in vitro. However, we found no evidence for effective poison use to sanitize the nest space. On the other hand, local application of ant poison by oral poison uptake, which is part of the ants prophylactic behavioral repertoire, probably contributes to keeping the gut of each individual sanitized. We hypothesize that oral poison uptake might be the reason why we did not find viable virus in the trophallactic fluid. The fifth chapter encompasses preliminary data on potential social immunization. However, our experiments do not confirm an actual survival benefit for the nestmates upon pathogen challenge under the given experimental settings. Nevertheless, we do not want to rule out the possibility for nestmate immunization, but rather emphasize that considering different experimental timelines and viral doses would provide a multitude of options for follow-up experiments. In conclusion, we find that prophylactic individual behaviors, such as oral poison uptake, might play a role in preventing viral disease transmission. Compared to colony defense against external pathogens, internal pathogen infections require a stronger component of individual physiological immunity than behavioral social immunity, yet could still lead to collective protection.

Multiplicative auction algorithm for approximate maximum weight bipartite matching - Zheng, Da Wei; Henzinger, Monika H (International Conference on Integer Programming and Combinatorial Optimization)
We present an auction algorithm using multiplicative instead of constant weight updates to compute a (1−ε)-approximate maximum weight matching (MWM) in a bipartite graph with n vertices and m edges in time O(mε−1log(ε−1)), matching the running time of the linear-time approximation algorithm of Duan and Pettie [JACM ’14]. Our algorithm is very simple and it can be extended to give a dynamic data structure that maintains a (1−ε)-approximate maximum weight matching under (1) one-sided vertex deletions (with incident edges) and (2) one-sided vertex insertions (with incident edges sorted by weight) to the other side. The total time time used is O(mε−1log(ε−1)), where m is the sum of the number of initially existing and inserted edges.

Enumerating matroids and linear spaces - Kwan, Matthew Alan; Sah, Ashwin; Sawhney, Mehtaab (Comptes Rendus Mathematique)
We show that the number of linear spaces on a set of n points and the number of rank-3 matroids on a ground set of size n are both of the form (cn+o(n))n2/6, where c=e3√/2−3(1+3–√)/2. This is the final piece of the puzzle for enumerating fixed-rank matroids at this level of accuracy: the numbers of rank-1 and rank-2 matroids on a ground set of size n have exact representations in terms of well-known combinatorial functions, and it was recently proved by van der Hofstad, Pendavingh, and van der Pol that for constant r≥4 there are (e1−rn+o(n))nr−1/r! rank-r matroids on a ground set of size n. In our proof, we introduce a new approach for bounding the number of clique decompositions of a complete graph, using quasirandomness instead of the so-called entropy method that is common in this area.

Cooperation between bHLH transcription factors and histones for DNA access - Michael, Alicia; Stoos, Lisa; Crosby, Priya; Eggers, Nikolas; Nie, Xinyu Y.; Makasheva, Kristina; Minnich, Martina; Healy, Kelly L.; Weiss, Joscha; Kempf, Georg; Cavadini, Simone; Kater, Lukas; et al. (Nature)
The basic helix–loop–helix (bHLH) family of transcription factors recognizes DNA motifs known as E-boxes (CANNTG) and includes 108 members 1 . Here we investigate how chromatinized E-boxes are engaged by two structurally diverse bHLH proteins: the proto-oncogene MYC-MAX and the circadian transcription factor CLOCK-BMAL1 (refs. 2,3 ). Both transcription factors bind to E-boxes preferentially near the nucleosomal entry–exit sites. Structural studies with engineered or native nucleosome sequences show that MYC-MAX or CLOCK-BMAL1 triggers the release of DNA from histones to gain access. Atop the H2A–H2B acidic patch 4 , the CLOCK-BMAL1 Per-Arnt-Sim (PAS) dimerization domains engage the histone octamer disc. Binding of tandem E-boxes 5–7 at endogenous DNA sequences occurs through direct interactions between two CLOCK-BMAL1 protomers and histones and is important for circadian cycling. At internal E-boxes, the MYC-MAX leucine zipper can also interact with histones H2B and H3, and its binding is indirectly enhanced by OCT4 elsewhere on the nucleosome. The nucleosomal E-box position and the type of bHLH dimerization domain jointly determine the histone contact, the affinity and the degree of competition and cooperativity with other nucleosome-bound factors.

Readout of histone methylation by Trim24 locally restricts chromatin opening by p53 - Isbel, Luke; Iskar, Murat; Durdu, Sevi; Weiss, Joscha; Grand, Ralph S.; Hietter-Pfeiffer, Eric; Kozicka, Zuzanna; Michael, Alicia; Burger, Lukas; Thomä, Nicolas H.; Schübeler, Dirk (Nature Structural & Molecular Biology)
The genomic binding sites of the transcription factor (TF) and tumor suppressor p53 are unusually diverse with regard to their chromatin features, including histone modifications, raising the possibility that the local chromatin environment can contextualize p53 regulation. Here, we show that epigenetic characteristics of closed chromatin, such as DNA methylation, do not influence the binding of p53 across the genome. Instead, the ability of p53 to open chromatin and activate its target genes is locally restricted by its cofactor Trim24. Trim24 binds to both p53 and unmethylated histone 3 lysine 4 (H3K4), thereby preferentially localizing to those p53 sites that reside in closed chromatin, whereas it is deterred from accessible chromatin by H3K4 methylation. The presence of Trim24 increases cell viability upon stress and enables p53 to affect gene expression as a function of the local chromatin state. These findings link H3K4 methylation to p53 function and illustrate how specificity in chromatin can be achieved, not by TF-intrinsic sensitivity to histone modifications, but by employing chromatin-sensitive cofactors that locally modulate TF function.
Keywords: Molecular Biology; Structural Biology

Orbital decay in an accreting and eclipsing 13.7 minute orbital period binary with a luminous donor - Burdge, Kevin B.; El-Badry, Kareem; Rappaport, Saul; Sunny Wong, Tin Long; Bauer, Evan B.; Bildsten, Lars; Caiazzo, Ilaria; Chakrabarty, Deepto; Chickles, Emma; Graham, Matthew J.; Kara, Erin; Kulkarni, S. R.; et al. (The Astrophysical Journal Letters)
We report the discovery of ZTF J0127+5258, a compact mass-transferring binary with an orbital period of 13.7 minutes. The system contains a white dwarf accretor, which likely originated as a post–common envelope carbon–oxygen (CO) white dwarf, and a warm donor (Teff,donor = 16,400 ± 1000 K). The donor probably formed during a common envelope phase between the CO white dwarf and an evolving giant that left behind a helium star or white dwarf in a close orbit with the CO white dwarf. We measure gravitational wave–driven orbital inspiral with ∼51σ significance, which yields a joint constraint on the component masses and mass transfer rate. While the accretion disk in the system is dominated by ionized helium emission, the donor exhibits a mixture of hydrogen and helium absorption lines. Phase-resolved spectroscopy yields a donor radial velocity semiamplitude of 771 ± 27 km s−1, and high-speed photometry reveals that the system is eclipsing. We detect a Chandra X-ray counterpart with LX ∼ 3 × 1031 erg s−1. Depending on the mass transfer rate, the system will likely either evolve into a stably mass-transferring helium cataclysmic variable, merge to become an R CrB star, or explode as a Type Ia supernova in the next million years. We predict that the Laser Space Interferometer Antenna (LISA) will detect the source with a signal-to-noise ratio of 24 ± 6 after 4 yr of observations. The system is the first LISA-loud mass-transferring binary with an intrinsically luminous donor, a class of sources that provide the opportunity to leverage the synergy between optical and infrared time domain surveys, X-ray facilities, and gravitational-wave observatories to probe general relativity, accretion physics, and binary evolution.
Keywords: Space and Planetary Science; Astronomy and Astrophysics

The origin of ultramassive white dwarfs: hints from Gaia EDR3 - Fleury, Leesa; Caiazzo, Ilaria; Heyl, Jeremy (Monthly Notices of the Royal Astronomical Society)
Gaia Data Release 2 revealed a population of ultramassive white dwarfs on the Q branch that are moving anomalously fast for a local disc population with their young photometric ages. As the velocity dispersion of stars in the local disc increases with age, a proposed explanation of these white dwarfs is that they experience a cooling delay that causes current cooling models to infer photometric ages much younger than their true ages. To explore this explanation, we investigate the kinematics of ultramassive white dwarfs within 200 pc of the Sun using the improved Gaia Early Data Release 3 observations. We analyse the transverse motions of 0.95–1.25 M⊙ white dwarfs, subdivided by mass and age, and determine the distributions of the three-dimensional components of the transverse velocities. The results are compared to expectations based on observed kinematics of local main-sequence stars. We find a population of photometrically young (∼0.5–1.5 Gyr) ultramassive (∼1.15–1.25 M⊙) white dwarfs for which the transverse velocity component in the direction of Galactic rotation is more dispersed than for local disc stars of any age; thus, it is too dispersed to be explained by any cooling delay in white dwarfs originating from the local disc. Furthermore, the dispersion ratio of the velocity components in the Galactic plane for this population is also inconsistent with a local disc origin. We discuss some possible explanations of this kinematically anomalous population, such as a halo origin or production through dynamical effects of stellar triple systems.
Keywords: Space and Planetary Science; Astronomy and Astrophysics

A strong x-ray polarization signal from the magnetar 1RXS J170849.0-400910 - Zane, Silvia; Taverna, Roberto; González–Caniulef, Denis; Muleri, Fabio; Turolla, Roberto; Heyl, Jeremy; Uchiyama, Keisuke; Ng, Mason; Tamagawa, Toru; Caiazzo, Ilaria; Di Lalla, Niccolò; Marshall, Herman L.; et al. (The Astrophysical Journal Letters)
Magnetars are the most strongly magnetized neutron stars, and one of the most promising targets for X-ray polarimetric measurements. We present here the first Imaging X-ray Polarimetry Explorer observation of the magnetar 1RXS J170849.0-400910, jointly analyzed with a new Swift observation and archival NICER data. The total (energy- and phase-integrated) emission in the 2–8 keV energy range is linerarly polarized, at a ∼35% level. The phase-averaged polarization signal shows a marked increase with energy, ranging from ∼20% at 2–3 keV up to ∼80% at 6–8 keV, while the polarization angle remains constant. This indicates that radiation is mostly polarized in a single direction. The spectrum is well reproduced by a combination of either two thermal (blackbody) components or a blackbody and a power law. Both the polarization degree and angle also show a variation with the spin phase, and the former is almost anticorrelated with the source counts in the 2–8 and 2–4 keV bands. We discuss the possible implications and interpretations, based on a joint analysis of the spectral, polarization, and pulsation properties of the source. A scenario in which the surface temperature is not homogeneous, with a hotter cap covered by a gaseous atmosphere and a warmer region in a condensed state, provides a satisfactory description of both the phase- and energy-dependent spectro-polarimetric data. The (comparatively) small size of the two emitting regions, required to explain the observed pulsations, does not allow to reach a robust conclusion about the presence of vacuum birefringence effects.
Keywords: Space and Planetary Science; Astronomy and Astrophysics

Provably-efficient and internally-deterministic parallel Union-Find - Fedorov, Alexander; Hashemi, Diba; Nadiradze, Giorgi; Alistarh, Dan-Adrian (Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures)
Determining the degree of inherent parallelism in classical sequential algorithms and leveraging it for fast parallel execution is a key topic in parallel computing, and detailed analyses are known for a wide range of classical algorithms. In this paper, we perform the first such analysis for the fundamental Union-Find problem, in which we are given a graph as a sequence of edges, and must maintain its connectivity structure under edge additions. We prove that classic sequential algorithms for this problem are well-parallelizable under reasonable assumptions, addressing a conjecture by [Blelloch, 2017]. More precisely, we show via a new potential argument that, under uniform random edge ordering, parallel union-find operations are unlikely to interfere: T concurrent threads processing the graph in parallel will encounter memory contention O(T2 · log |V| · log |E|) times in expectation, where |E| and |V| are the number of edges and nodes in the graph, respectively. We leverage this result to design a new parallel Union-Find algorithm that is both internally deterministic, i.e., its results are guaranteed to match those of a sequential execution, but also work-efficient and scalable, as long as the number of threads T is O(|E|1 over 3 - ε), for an arbitrarily small constant ε > 0, which holds for most large real-world graphs. We present lower bounds which show that our analysis is close to optimal, and experimental results suggesting that the performance cost of internal determinism is limited.

Gloss-aware color correction for 3D printing - Condor, Jorge; Piovarci, Michael; Bickel, Bernd; Didyk, Piotr (SIGGRAPH ’23 Conference Proceedings)
Color and gloss are fundamental aspects of surface appearance. State-of-the-art fabrication techniques can manipulate both properties of the printed 3D objects. However, in the context of appearance reproduction, perceptual aspects of color and gloss are usually handled separately, even though previous perceptual studies suggest their interaction. Our work is motivated by previous studies demonstrating a perceived color shift due to a change in the object's gloss, i.e., two samples with the same color but different surface gloss appear as they have different colors. In this paper, we conduct new experiments which support this observation and provide insights into the magnitude and direction of the perceived color change. We use the observations as guidance to design a new method that estimates and corrects the color shift enabling the fabrication of objects with the same perceived color but different surface gloss. We formulate the problem as an optimization procedure solved using differentiable rendering. We evaluate the effectiveness of our method in perceptual experiments with 3D objects fabricated using a multi-material 3D printer and demonstrate potential applications.
Keywords: color; gloss; perception; color compensation; color management

Skin-Screen: A computational fabrication framework for color tattoos - Piovarci, Michael; Chapiro, Alexandre; Bickel, Bernd (ACM Transactions on Graphics)
Tattoos are a highly popular medium, with both artistic and medical applications. Although the mechanical process of tattoo application has evolved historically, the results are reliant on the artisanal skill of the artist. This can be especially challenging for some skin tones, or in cases where artists lack experience. We provide the first systematic overview of tattooing as a computational fabrication technique. We built an automated tattooing rig and a recipe for the creation of silicone sheets mimicking realistic skin tones, which allowed us to create an accurate model predicting tattoo appearance. This enables several exciting applications including tattoo previewing, color retargeting, novel ink spectra optimization, color-accurate prosthetics, and more.
Keywords: appearance; modeling; reproduction; tattoo; skin color; gamut mapping; ink-optimization; prosthetic

Nanoparticle-based semiconductor solids: From synthesis to consolidation - Calcabrini, Mariano
High-performance semiconductors rely upon precise control of heat and charge transport. This can be achieved by precisely engineering defects in polycrystalline solids. There are multiple approaches to preparing such polycrystalline semiconductors, and the transformation of solution-processed colloidal nanoparticles is appealing because colloidal nanoparticles combine low cost with structural and compositional tunability along with rich surface chemistry. However, the multiple processes from nanoparticle synthesis to the final bulk nanocomposites are very complex. They involve nanoparticle purification, post-synthetic modifications, and finally consolidation (thermal treatments and densification). All these properties dictate the final material’s composition and microstructure, ultimately affecting its functional properties. This thesis explores the synthesis, surface chemistry and consolidation of colloidal semiconductor nanoparticles into dense solids. In particular, the transformations that take place during these processes, and their effect on the material’s transport properties are evaluated.

Ultrastructural characterization of natively preserved extracellular matrix by cryo-electron tomography - Zens, Bettina
The extracellular matrix (ECM) is a hydrated and complex three-dimensional network consisting of proteins, polysaccharides, and water. It provides structural scaffolding for the cells embedded within it and is essential in regulating numerous physiological processes, including cell migration and proliferation, wound healing, and stem cell fate. Despite extensive study, detailed structural knowledge of ECM components in physiologically relevant conditions is still rudimentary. This is due to methodological limitations in specimen preparation protocols which are incompatible with keeping large samples, such as the ECM, in their native state for subsequent imaging. Conventional electron microscopy (EM) techniques rely on fixation, dehydration, contrasting, and sectioning. This results in the alteration of a highly hydrated environment and the potential introduction of artifacts. Other structural biology techniques, such as nuclear magnetic resonance (NMR) spectroscopy and X-ray crystallography, allow high-resolution analysis of protein structures but only work on homogenous and purified samples, hence lacking contextual information. Currently, no approach exists for the ultrastructural and structural study of extracellular components under native conditions in a physiological, 3D environment. In this thesis, I have developed a workflow that allows for the ultrastructural analysis of the ECM in near-native conditions at molecular resolution. The developments I introduced include implementing a novel specimen preparation workflow for cell-derived matrices (CDMs) to render them compatible with ion-beam milling and subsequent high-resolution cryo-electron tomography (ET). To this end, I have established protocols to generate CDMs grown over several weeks on EM grids that are compatible with downstream cryo-EM sample preparation and imaging techniques. Characterization of these ECMs confirmed that they contain essential ECM components such as collagen I, collagen VI, and fibronectin I in high abundance and hence represent a bona fide biologically-relevant sample. I successfully optimized vitrification of these specimens by testing various vitrification techniques and cryoprotectants. In order to obtain high-resolution molecular insights into the ultrastructure and organization of CDMs, I established cryo-focused ion beam scanning electron microscopy (FIBSEM) on these challenging and complex specimens. I explored different approaches for the creation of thin cryo-lamellae by FIB milling and succeeded in optimizing the cryo-lift-out technique, resulting in high-quality lamellae of approximately 200 nm thickness. High-resolution Cryo-ET of these lamellae revealed for the first time the architecture of native CDM in the context of matrix-secreting cells. This allowed for the in situ visualization of fibrillar matrix proteins such as collagen, laying the foundation for future structural and ultrastructural characterization of these proteins in their near-native environment. In summary, in this thesis, I present a novel workflow that combines state-of-the-art cryo-EM specimen preparation and imaging technologies to permit characterization of the ECM, an important tissue component in higher organisms. This innovative and highly versatile workflow will enable addressing far-reaching questions on ECM architecture, composition, and reciprocal ECM-cell interactions.
Keywords: cryo-EM; cryo-ET; FIB milling; method development; FIBSEM; extracellular matrix; ECM; cell-derived matrices; CDMs; cell culture; high pressure freezing; HPF; structural biology; tomography; collagen

Mechanochemical pattern formation across biological scales - Boocock, Daniel R
Pattern formation is of great importance for its contribution across different biological behaviours. During developmental processes for example, patterns of chemical gradients are established to determine cell fate and complex tissue patterns emerge to define structures such as limbs and vascular networks. Patterns are also seen in collectively migrating groups, for instance traveling waves of density emerging in moving animal flocks as well as collectively migrating cells and tissues. To what extent these biological patterns arise spontaneously through the local interaction of individual constituents or are dictated by higher level instructions is still an open question however there is evidence for the involvement of both types of process. Where patterns arise spontaneously there is a long standing interest in how far the interplay of mechanics, e.g. force generation and deformation, and chemistry, e.g. gene regulation and signaling, contributes to the behaviour. This is because many systems are able to both chemically regulate mechanical force production and chemically sense mechanical deformation, forming mechano-chemical feedback loops which can potentially become unstable towards spatio and/or temporal patterning. We work with experimental collaborators to investigate the possibility that this type of interaction drives pattern formation in biological systems at different scales. We focus first on tissue-level ERK-density waves observed during the wound healing response across different systems where many previous studies have proposed that patterns depend on polarized cell migration and arise from a mechanical flocking-like mechanism. By combining theory with mechanical and optogenetic perturbation experiments on in vitro monolayers we instead find evidence for mechanochemical pattern formation involving only scalar bilateral feedbacks between ERK signaling and cell contraction. We perform further modeling and experiment to study how this instability couples with polar cell migration in order to produce a robust and efficient wound healing response. In a following chapter we implement ERK-density coupling and cell migration in a 2D active vertex model to investigate the interaction of ERK-density patterning with different tissue rheologies and find that the spatio-temporal dynamics are able to both locally and globally fluidize a tissue across the solid-fluid glass transition. In a last chapter we move towards lower spatial scales in the context of subcellular patterning of the cell cytoskeleton where we investigate the transition between phases of spatially homogeneous temporal oscillations and chaotic spatio-temporal patterning in the dynamics of myosin and ROCK activities (a motor component of the actomyosin cytoskeleton and its activator). Experimental evidence supports an intrinsic chemical oscillator which we encode in a reaction model and couple to a contractile active gel description of the cell cortex. The model exhibits phases of chemical oscillations and contractile spatial patterning which reproduce many features of the dynamics seen in Drosophila oocyte epithelia in vivo. However, additional pharmacological perturbations to inhibit myosin contractility leaves the role of contractile instability unclear. We discuss alternative hypotheses and investigate the possibility of reaction-diffusion instability.

Plasticity in the cerebellum: What molecular mechanisms are behind physiological learning - Alcarva, Catarina
Understanding the mechanisms of learning and memory formation has always been one of the main goals in neuroscience. Already Pavlov (1927) in his early days has used his classic conditioning experiments to study the neural mechanisms governing behavioral adaptation. What was not known back then was that the part of the brain that is largely responsible for this type of associative learning is the cerebellum. Since then, plenty of theories on cerebellar learning have emerged. Despite their differences, one thing they all have in common is that learning relies on synaptic and intrinsic plasticity. The goal of my PhD project was to unravel the molecular mechanisms underlying synaptic plasticity in two synapses that have been shown to be implicated in motor learning, in an effort to understand how learning and memory formation are processed in the cerebellum. One of the earliest and most well-known cerebellar theories postulates that motor learning largely depends on long-term depression at the parallel fiber-Purkinje cell (PC-PC) synapse. However, the discovery of other types of plasticity in the cerebellar circuitry, like long-term potentiation (LTP) at the PC-PC synapse, potentiation of molecular layer interneurons (MLIs), and plasticity transfer from the cortex to the cerebellar/ vestibular nuclei has increased the popularity of the idea that multiple sites of plasticity might be involved in learning. Still a lot remains unknown about the molecular mechanisms responsible for these types of plasticity and whether they occur during physiological learning. In the first part of this thesis we have analyzed the variation and nanodistribution of voltagegated calcium channels (VGCCs) and α-amino-3-hydroxy-5-methyl-4-isoxazolepropionic acid type glutamate receptors (AMPARs) on the parallel fiber-Purkinje cell synapse after vestibuloocular reflex phase reversal adaptation, a behavior that has been suggested to rely on PF-PC LTP. We have found that on the last day of adaptation there is no learning trace in form of VGCCs nor AMPARs variation at the PF-PC synapse, but instead a decrease in the number of PF-PC synapses. These data seem to support the view that learning is only stored in the cerebellar cortex in an initial learning phase, being transferred later to the vestibular nuclei. Next, we have studied the role of MLIs in motor learning using a relatively simple and well characterized behavioral paradigm – horizontal optokinetic reflex (HOKR) adaptation. We have found behavior-induced MLI potentiation in form of release probability increase that could be explained by the increase of VGCCs at the presynaptic side. Our results strengthen the idea of distributed cerebellar plasticity contributing to learning and provide a novel mechanism for release probability increase.

Structural and mechanistic study of bacterial complex I and its cyanobacterial ortholog - Kravchuk, Vladyslav
Most energy in humans is produced in form of ATP by the mitochondrial respiratory chain consisting of several protein assemblies embedded into lipid membrane (complexes I-V). Complex I is the first and the largest enzyme of the respiratory chain which is essential for energy production. It couples the transfer of two electrons from NADH to ubiquinone with proton translocation across bacterial or inner mitochondrial membrane. The coupling mechanism between electron transfer and proton translocation is one of the biggest enigma in bioenergetics and structural biology. Even though the enzyme has been studied for decades, only recent technological advances in cryo-EM allowed its extensive structural investigation. Complex I from E.coli appears to be of special importance because it is a perfect model system with a rich mutant library, however the structure of the entire complex was unknown. In this thesis I have resolved structures of the minimal complex I version from E. coli in different states including reduced, inhibited, under reaction turnover and several others. Extensive structural analyses of these structures and comparison to structures from other species allowed to derive general features of conformational dynamics and propose a universal coupling mechanism. The mechanism is straightforward, robust and consistent with decades of experimental data available for complex I from different species. Cyanobacterial NDH (cyanobacterial complex I) is a part of broad complex I superfamily and was studied as well in this thesis. It plays an important role in cyclic electron transfer (CET), during which electrons are cycled within PSI through ferredoxin and plastoquinone to generate proton gradient without NADPH production. Here, I solved structure of NDH and revealed additional state, which was not observed before. The novel “resting” state allowed to propose the mechanism of CET regulation. Moreover, conformational dynamics of NDH resembles one in complex I which suggest more broad universality of the proposed coupling mechanism. In summary, results presented here helped to interpret decades of experimental data for complex I and contributed to fundamental mechanistic understanding of protein function.

Mechanism of clathrin-coated vesicle formation during endocytosis in plants - Gnyliukh, Nataliia
Keywords: Clathrin-Mediated Endocytosis; vesicle scission; Dynamin-Related Protein 2; SH3P2; TPLATE complex; Total internal reflection fluorescence microscopy; Arabidopsis thaliana

Inverse shape design with parametric representations: Kirchhoff Rods and parametric surface models - Hafner, Christian
Inverse design problems in fabrication-aware shape optimization are typically solved on discrete representations such as polygonal meshes. This thesis argues that there are benefits to treating these problems in the same domain as human designers, namely, the parametric one. One reason is that discretizing a parametric model usually removes the capability of making further manual changes to the design, because the human intent is captured by the shape parameters. Beyond this, knowledge about a design problem can sometimes reveal a structure that is present in a smooth representation, but is fundamentally altered by discretizing. In this case, working in the parametric domain may even simplify the optimization task. We present two lines of research that explore both of these aspects of fabrication-aware shape optimization on parametric representations. The first project studies the design of plane elastic curves and Kirchhoff rods, which are common mathematical models for describing the deformation of thin elastic rods such as beams, ribbons, cables, and hair. Our main contribution is a characterization of all curved shapes that can be attained by bending and twisting elastic rods having a stiffness that is allowed to vary across the length. Elements like these can be manufactured using digital fabrication devices such as 3d printers and digital cutters, and have applications in free-form architecture and soft robotics. We show that the family of curved shapes that can be produced this way admits geometric description that is concise and computationally convenient. In the case of plane curves, the geometric description is intuitive enough to allow a designer to determine whether a curved shape is physically achievable by visual inspection alone. We also present shape optimization algorithms that convert a user-defined curve in the plane or in three dimensions into the geometry of an elastic rod that will naturally deform to follow this curve when its endpoints are attached to a support structure. Implemented in an interactive software design tool, the rod geometry is generated in real time as the user edits a curve and enables fast prototyping. The second project tackles the problem of general-purpose shape optimization on CAD models using a novel variant of the extended finite element method (XFEM). Our goal is the decoupling between the simulation mesh and the CAD model, so no geometry-dependent meshing or remeshing needs to be performed when the CAD parameters change during optimization. This is achieved by discretizing the embedding space of the CAD model, and using a new high-accuracy numerical integration method to enable XFEM on free-form elements bounded by the parametric surface patches of the model. Our simulation is differentiable from the CAD parameters to the simulation output, which enables us to use off-the-shelf gradient-based optimization procedures. The result is a method that fits seamlessly into the CAD workflow because it works on the same representation as the designer, enabling the alternation of manual editing and fabrication-aware optimization at will.

A versatile toolbox for the comprehensive analysis of nervous tissue organization with light microscopy - Michalska, Julia M
The brain is an exceptionally sophisticated organ consisting of billions of cells and trillions of connections that orchestrate our cognition and behavior. To decode its complex connectivity, it is pivotal to disentangle its intricate architecture spanning from cm-sized circuits down to tens of nm-small synapses. To achieve this goal, I developed CATS – Comprehensive Analysis of nervous Tissue across Scales, a versatile toolbox for obtaining a holistic view of nervous tissue context with (superresolution) fluorescence microscopy. CATS combines comprehensive labeling of the extracellular space, that is compatible with chemical fixation, with information on molecular markers, superresolved data acquisition and machine-learning based data analysis for segmentation and synapse identification. I used CATS to analyze key features of nervous tissue connectivity, ranging from whole tissue architecture, neuronal in- and output-fields, down to synapse morphology. Focusing on the hippocampal circuitry, I quantified synaptic transmission properties of mossy fiber boutons and analyzed the connectivity pattern of dentate gyrus granule cells with CA3 pyramidal neurons. This shows that CATS is a viable tool to study hallmarks of neuronal connectivity with light microscopy.

Flavors of sequential information flow - Bartocci, Ezio; Ferrere, Thomas; Henzinger, Thomas A; Nickovic, Dejan; Da Costa, Ana Oliveira (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics))
We study the problem of specifying sequential information-flow properties of systems. Information-flow properties are hyperproperties, as they compare different traces of a system. Sequential information-flow properties can express changes, over time, in the information-flow constraints. For example, information-flow constraints during an initialization phase of a system may be different from information-flow constraints that are required during the operation phase. We formalize several variants of interpreting sequential information-flow constraints, which arise from different assumptions about what can be observed of the system. For this purpose, we introduce a first-order logic, called Hypertrace Logic, with both trace and time quantifiers for specifying linear-time hyperproperties. We prove that HyperLTL, which corresponds to a fragment of Hypertrace Logic with restricted quantifier prefixes, cannot specify the majority of the studied variants of sequential information flow, including all variants in which the transition between sequential phases (such as initialization and operation) happens asynchronously. Our results rely on new equivalences between sets of traces that cannot be distinguished by certain classes of formulas from Hypertrace Logic. This presents a new approach to proving inexpressiveness results for HyperLTL.

Quantifying the probing and selection of microenvironmental pores by motile immune cells - Kroll, Janina; Ruiz-Fernandez, Mauricio J.A.; Braun, Malte B.; Merrin, Jack; Renkawitz, Jörg (Current Protocols)
Immune cells are constantly on the move through multicellular organisms to explore and respond to pathogens and other harmful insults. While moving, immune cells efficiently traverse microenvironments composed of tissue cells and extracellular fibers, which together form complex environments of various porosity, stiffness, topography, and chemical composition. In this protocol we describe experimental procedures to investigate immune cell migration through microenvironments of heterogeneous porosity. In particular, we describe micro-channels, micro-pillars, and collagen networks as cell migration paths with alternative pore size choices. Employing micro-channels or micro-pillars that divide at junctions into alternative paths with initially differentially sized pores allows us to precisely (1) measure the cellular translocation time through these porous path junctions, (2) quantify the cellular preference for individual pore sizes, and (3) image cellular components like the nucleus and the cytoskeleton. This reductionistic experimental setup thus can elucidate how immune cells perform decisions in complex microenvironments of various porosity like the interstitium. The setup further allows investigation of the underlying forces of cellular squeezing and the consequences of cellular deformation on the integrity of the cell and its organelles. As a complementary approach that does not require any micro-engineering expertise, we describe the usage of three-dimensional collagen networks with different pore sizes. Whereas we here focus on dendritic cells as a model for motile immune cells, the described protocols are versatile as they are also applicable for other immune cell types like neutrophils and non-immune cell types such as mesenchymal and cancer cells. In summary, we here describe protocols to identify the mechanisms and principles of cellular probing, decision making, and squeezing during cellular movement through microenvironments of heterogeneous porosity.

A cautionary tale: Burning the medial axis is unstable - Chambers, Erin; Fillmore, Christopher D; Stephenson, Elizabeth R; Wintraecken, Mathijs (38th International Symposium on Computational Geometry)
The medial axis of a set consists of the points in the ambient space without a unique closest point on the original set. Since its introduction, the medial axis has been used extensively in many applications as a method of computing a topologically equivalent skeleton. Unfortunately, one limiting factor in the use of the medial axis of a smooth manifold is that it is not necessarily topologically stable under small perturbations of the manifold. To counter these instabilities various prunings of the medial axis have been proposed. Here, we examine one type of pruning, called burning. Because of the good experimental results, it was hoped that the burning method of simplifying the medial axis would be stable. In this work we show a simple example that dashes such hopes based on Bing’s house with two rooms, demonstrating an isotopy of a shape where the medial axis goes from collapsible to non-collapsible.

Web and Wireless Geographical Information Systems
This book constitutes the refereed proceedings of the 18th International Symposium on Web and Wireless Geographical Information Systems, W2GIS 2022, held in Konstanz, Germany, in April 2022. The 7 full papers presented together with 6 short papers in the volume were carefully reviewed and selected from 16 submissions. The papers cover topics that range from mobile GIS and Location-Based Services to Spatial Information Retrieval and Wireless Sensor Networks.

The persistent homology of dual digital image constructions - Bleile, Bea; Garin, Adélie; Heiss, Teresa; Maggs, Kelly; Robins, Vanessa (Research in Computational Topology 2)
To compute the persistent homology of a grayscale digital image one needs to build a simplicial or cubical complex from it. For cubical complexes, the two commonly used constructions (corresponding to direct and indirect digital adjacencies) can give different results for the same image. The two constructions are almost dual to each other, and we use this relationship to extend and modify the cubical complexes to become dual filtered cell complexes. We derive a general relationship between the persistent homology of two dual filtered cell complexes, and also establish how various modifications to a filtered complex change the persistence diagram. Applying these results to images, we derive a method to transform the persistence diagram computed using one type of cubical complex into a persistence diagram for the other construction. This means software for computing persistent homology from images can now be easily adapted to produce results for either of the two cubical complex constructions without additional low-level code implementation.

The MUSE eXtremely Deep Field: Individual detections of Lyα haloes around rest-frame UV-selected galaxies at z ≃ 2.9–4.4 - Kusakabe, Haruka; Verhamme, Anne; Blaizot, Jérémy; Garel, Thibault; Wisotzki, Lutz; Leclercq, Floriane; Bacon, Roland; Schaye, Joop; Gallego, Sofia G.; Kerutt, Josephine; Matthee, Jorryt J; Maseda, Michael; et al. (Astronomy & Astrophysics)
Hydrogen Lyα haloes (LAHs) are commonly used as a tracer of the circumgalactic medium (CGM) at high redshifts. In this work, we aim to explore the existence of Lyα haloes around individual UV-selected galaxies, rather than around Lyα emitters (LAEs), at high redshifts. Our sample was continuum-selected with F775W ≤ 27.5, and spectroscopic redshifts were assigned or constrained for all the sources thanks to the deepest (100- to 140-h) existing Very Large Telescope (VLT)/Multi-Unit Spectroscopic Explorer (MUSE) data with adaptive optics. The final sample includes 21 galaxies that are purely F775W-magnitude selected within the redshift range z ≈ 2.9 − 4.4 and within a UV magnitude range −20 ≤ M1500 ≤ −18, thus avoiding any bias toward LAEs. We tested whether galaxy’s Lyα emission is significantly more extended than the MUSE PSF-convolved continuum component. We find 17 LAHs and four non-LAHs. We report the first individual detections of extended Lyα emission around non-LAEs. The Lyα halo fraction is thus as high as 81.0−11.2+10.3%, which is close to that for LAEs at z = 3 − 6 in the literature. This implies that UV-selected galaxies generally have a large amount of hydrogen in their CGM. We derived the mean surface brightness (SB) profile for our LAHs with cosmic dimming corrections and find that Lyα emission extends to 5.4 arcsec (≃40 physical kpc at the midpoint redshift z = 3.6) above the typical 1σ SB limit. The incidence rate of surrounding gas detected in Lyα per one-dimensional line of sight per unit redshift, dn/dz, is estimated to be 0.76−0.09+0.09 for galaxies with M1500 ≤ −18 mag at z ≃ 3.7. Assuming that Lyα emission and absorption arise in the same gas, this suggests, based on abundance matching, that LAHs trace the same gas as damped Lyα systems (DLAs) and sub-DLAs.
Keywords: Space and Planetary Science; Astronomy and Astrophysics; galaxies: high-redshift / galaxies: formation / galaxies: evolution / cosmology: observations

Deciphering stellar metallicities in the early universe: Case study of a young galaxy at z = 4.77 in the MUSE eXtremely Deep Field - Matthee, Jorryt J; Feltre, Anna; Maseda, Michael; Nanayakkara, Themiya; Boogaard, Leindert; Bacon, Roland; Verhamme, Anne; Leclercq, Floriane; Kusakabe, Haruka; Urrutia, Tanya; Wisotzki, Lutz (Astronomy & Astrophysics)
Directly characterising the first generations of stars in distant galaxies is a key quest of observational cosmology. We present a case study of ID53 at z = 4.77, the UV-brightest (but L⋆) star-forming galaxy at z > 3 in the MUSE eXtremely Deep Field with a mass of ≈109 M⊙. In addition to very strong Lyman-α (Lyα) emission, we clearly detect the (stellar) continuum and an N V P Cygni feature, interstellar absorption, fine-structure emission and nebular C IV emission lines in the 140 h spectrum. Continuum emission from two spatially resolved components in Hubble Space Telescope data are blended in the MUSE data, but we show that the nebular C IV emission originates from a subcomponent of the galaxy. The UV spectrum can be fit with recent BPASS stellar population models combined with single-burst or continuous star formation histories (SFHs), a standard initial mass function, and an attenuation law. Models with a young age and low metallicity (log10(age/yr) = 6.5–7.6 and [Z/H] = −2.15 to −1.15) are preferred, but the details depend on the assumed SFH. The intrinsic Hα luminosity of the best-fit models is an order of magnitude higher than the Hα luminosity inferred from Spitzer/IRAC data, which either suggests a high escape fraction of ionising photons, a high relative attenuation of nebular to stellar dust, or a complex SFH. The metallicity appears lower than the metallicity in more massive galaxies at z = 3 − 5, consistent with the scenario according to which younger galaxies have lower metallicities. This chemical immaturity likely facilitates Lyα escape, explaining why the Lyα equivalent width is anti-correlated with stellar metallicity. Finally, we stress that uncertainties in SFHs impose a challenge for future inferences of the stellar metallicity of young galaxies. This highlights the need for joint (spatially resolved) analyses of stellar spectra and photo-ionisation models.
Keywords: Space and Planetary Science; Astronomy and Astrophysics; galaxies: high-redshift / techniques: spectroscopic / galaxies: stellar content / galaxies: formation

EMPRESS. IV. Extremely metal-poor galaxies including very low-mass primordial systems with M∗= 10⁴-10⁵⊙ and 2%–3% (O/H): High (Fe/O) suggestive of metal enrichment by hypernovae/pair-instability supernovae - Isobe, Yuki; Ouchi, Masami; Suzuki, Akihiro; Moriya, Takashi J.; Nakajima, Kimihiko; Nomoto, Ken’ichi; Rauch, Michael; Harikane, Yuichi; Kojima, Takashi; Ono, Yoshiaki; Fujimoto, Seiji; Inoue, Akio K.; et al. (The Astrophysical Journal)
We present Keck/LRIS follow-up spectroscopy for 13 photometric candidates of extremely metal-poor galaxies (EMPGs) selected by a machine-learning technique applied to the deep (∼26 AB mag) optical and wide-area (∼500 deg2) Subaru imaging data in the EMPRESS survey. Nine out of the 13 candidates are EMPGs with an oxygen abundance (O/H) less than ∼10% solar value (O/H)⊙, and four sources are contaminants of moderately metal-rich galaxies or no emission-line objects. Notably, two out of the nine EMPGs have extremely low stellar masses and oxygen abundances of 5 × 10⁴x–7 × -10⁵ M⊙ and 2%–3% (O/H)⊙, respectively. With a sample of five EMPGs with (Fe/O) measurements, two (three) of which are taken from this study (the literature), we confirm that two EMPGs with the lowest (O/H) ratios of ∼2% (O/H)⊙ show high (Fe/O) ratios of ∼0.1, close to the solar abundance ratio. Comparing galaxy chemical enrichment models, we find that the two EMPGs cannot be explained by a scenario of metal-poor gas accretion/episodic star formation history due to their low (N/O) ratios. We conclude that the two EMPGs can be reproduced by the inclusion of bright hypernovae and/or hypothetical pair-instability supernovae (SNe) preferentially produced in a metal-poor environment. This conclusion implies that primordial galaxies at z ∼ 10 could have a high abundance of Fe that did not originate from Type Ia SNe with delays and that Fe may not serve as a cosmic clock for primordial galaxies.
Keywords: Space and Planetary Science; Astronomy and Astrophysics

(Re)Solving reionization with Lyα: How bright Lyα emitters account for the z ≈ 2 − 8 cosmic ionizing background - Matthee, Jorryt J; Naidu, Rohan P.; Pezzulli, Gabriele; Gronke, Max; Sobral, David; Oesch, Pascal A.; Hayes, Matthew; Erb, Dawn; Schaerer, Daniel; Amorín, Ricardo; Tacchella, Sandro; Ana Paulino-Afonso, Ana Paulino-Afonso; et al. (Monthly Notices of the Royal Astronomical Society)
The cosmic ionizing emissivity from star-forming galaxies has long been anchored to UV luminosity functions. Here, we introduce an emissivity framework based on Lyα emitters (LAEs), which naturally hones in on the subset of galaxies responsible for the ionizing background due to the intimate connection between production and escape of Lyα and LyC photons. Using constraints on the escape fractions of bright LAEs (LLyα > 0.2L*) at z ≈ 2 obtained from resolved Lyα profiles, and arguing for their redshift-invariance, we show that: (i) quasars and LAEs together reproduce the relatively flat emissivity at z ≈ 2–6, which is non-trivial given the strong evolution in both the star formation density and quasar number density at these epochs and (ii) LAEs produce late and rapid reionization between z ≈ 6−9 under plausible assumptions. Within this framework, the >10 × rise in the UV population-averaged fesc between z ≈ 3–7 naturally arises due to the same phenomena that drive the growing LAE fraction with redshift. Generally, a LAE dominated emissivity yields a peak in the distribution of the ionizing budget with UV luminosity as reported in latest simulations. Using our adopted parameters (⁠fesc=50 per cent⁠, ξion = 1025.9 Hz erg−1 for half the bright LAEs), a highly ionizing minority of galaxies with MUV < −17 accounts for the entire ionizing budget from star-forming galaxies. Rapid flashes of LyC from such rare galaxies produce a ‘disco’ ionizing background. We conclude proposing tests to further develop our suggested Lyα-anchored formalism.
Keywords: galaxies: high-redshift; intergalactic medium; cosmology: observations; dark ages; reionization; first stars; ultraviolet: galaxies

The dynamics of complex box mappings - Clark, Trevor; Drach, Kostiantyn; Kozlovski, Oleg; Strien, Sebastian Van (Arnold Mathematical Journal)
In holomorphic dynamics, complex box mappings arise as first return maps to wellchosen domains. They are a generalization of polynomial-like mapping, where the domain of the return map can have infinitely many components. They turned out to be extremely useful in tackling diverse problems. The purpose of this paper is: • To illustrate some pathologies that can occur when a complex box mapping is not induced by a globally defined map and when its domain has infinitely many components, and to give conditions to avoid these issues. • To show that once one has a box mapping for a rational map, these conditions can be assumed to hold in a very natural setting. Thus, we call such complex box mappings dynamically natural. Having such box mappings is the first step in tackling many problems in one-dimensional dynamics. • Many results in holomorphic dynamics rely on an interplay between combinatorial and analytic techniques. In this setting, some of these tools are: • the Enhanced Nest (a nest of puzzle pieces around critical points) from Kozlovski, Shen, van Strien (AnnMath 165:749–841, 2007), referred to below as KSS; • the Covering Lemma (which controls the moduli of pullbacks of annuli) from Kahn and Lyubich (Ann Math 169(2):561–593, 2009); • the QC-Criterion and the Spreading Principle from KSS. The purpose of this paper is to make these tools more accessible so that they can be used as a ‘black box’, so one does not have to redo the proofs in new settings. • To give an intuitive, but also rather detailed, outline of the proof from KSS and Kozlovski and van Strien (Proc Lond Math Soc (3) 99:275–296, 2009) of the following results for non-renormalizable dynamically natural complex box mappings: • puzzle pieces shrink to points, • (under some assumptions) topologically conjugate non-renormalizable polynomials and box mappings are quasiconformally conjugate. • We prove the fundamental ergodic properties for dynamically natural box mappings. This leads to some necessary conditions for when such a box mapping supports a measurable invariant line field on its filled Julia set. These mappings are the analogues of Lattès maps in this setting. • We prove a version of Mañé’s Theorem for complex box mappings concerning expansion along orbits of points that avoid a neighborhood of the set of critical points.

The K2 Galactic Archaeology Program data release 3: Age-abundance patterns in C1–C8 and C10–C18 - Zinn, Joel C.; Stello, Dennis; Elsworth, Yvonne; García, Rafael A.; Kallinger, Thomas; Mathur, Savita; Mosser, Benoît; Hon, Marc; Bugnet, Lisa Annabelle; Jones, Caitlin; Reyes, Claudia; Sharma, Sanjib; et al. (The Astrophysical Journal)
We present the third and final data release of the K2 Galactic Archaeology Program (K2 GAP) for Campaigns C1–C8 and C10–C18. We provide asteroseismic radius and mass coefficients, κR and κM, for ∼19,000 red giant stars, which translate directly to radius and mass given a temperature. As such, K2 GAP DR3 represents the largest asteroseismic sample in the literature to date. K2 GAP DR3 stellar parameters are calibrated to be on an absolute parallactic scale based on Gaia DR2, with red giant branch and red clump evolutionary state classifications provided via a machine-learning approach. Combining these stellar parameters with GALAH DR3 spectroscopy, we determine asteroseismic ages with precisions of ∼20%–30% and compare age-abundance relations to Galactic chemical evolution models among both low- and high-α populations for α, light, iron-peak, and neutron-capture elements. We confirm recent indications in the literature of both increased Ba production at late Galactic times as well as significant contributions to r-process enrichment from prompt sources associated with, e.g., core-collapse supernovae. With an eye toward other Galactic archeology applications, we characterize K2 GAP DR3 uncertainties and completeness using injection tests, suggesting that K2 GAP DR3 is largely unbiased in mass/age, with uncertainties of 2.9% (stat.) ± 0.1% (syst.) and 6.7% (stat.) ± 0.3% (syst.) in κR and κM for red giant branch stars and 4.7% (stat.) ± 0.3% (syst.) and 11% (stat.) ± 0.9% (syst.) for red clump stars. We also identify percent-level asteroseismic systematics, which are likely related to the time baseline of the underlying data, and which therefore should be considered in TESS asteroseismic analysis.
Keywords: Space and Planetary Science; Astronomy and Astrophysics

Fully dynamic four-vertex subgraph counting - Hanauer, Kathrin; Henzinger, Monika H; Hua, Qi Cheng (1st Symposium on Algorithmic Foundations of Dynamic Networks)
This paper presents a comprehensive study of algorithms for maintaining the number of all connected four-vertex subgraphs in a dynamic graph. Specifically, our algorithms maintain the number of paths of length three in deterministic amortized O(m^{1/2}) update time, and any other connected four-vertex subgraph which is not a clique in deterministic amortized update time O(m^{2/3}). Queries can be answered in constant time. We also study the query times for subgraphs containing an arbitrary edge that is supplied only with the query as well as the case where only subgraphs containing a vertex s that is fixed beforehand are considered. For length-3 paths, paws, 4-cycles, and diamonds our bounds match or are not far from (conditional) lower bounds: Based on the OMv conjecture we show that any dynamic algorithm that detects the existence of paws, diamonds, or 4-cycles or that counts length-3 paths takes update time Ω(m^{1/2-δ}). Additionally, for 4-cliques and all connected induced subgraphs, we show a lower bound of Ω(m^{1-δ}) for any small constant δ > 0 for the amortized update time, assuming the static combinatorial 4-clique conjecture holds. This shows that the O(m) algorithm by Eppstein et al. [David Eppstein et al., 2012] for these subgraphs cannot be improved by a polynomial factor.

The complexity of average-case dynamic subgraph counting - Henzinger, Monika H; Lincoln, Andrea; Saha, Barna (33rd Annual ACM-SIAM Symposium on Discrete Algorithms)
Statistics of small subgraph counts such as triangles, four-cycles, and s-t paths of short lengths reveal important structural properties of the underlying graph. These problems have been widely studied in social network analysis. In most relevant applications, the graphs are not only massive but also change dynamically over time. Most of these problems become hard in the dynamic setting when considering the worst case. In this paper, we ask whether the question of small subgraph counting over dynamic graphs is hard also in the average case. We consider the simplest possible average case model where the updates follow an Erdős-Rényi graph: each update selects a pair of vertices (u, v) uniformly at random and flips the existence of the edge (u, v). We develop new lower bounds and matching algorithms in this model for counting four-cycles, counting triangles through a specified point s, or a random queried point, and st paths of length 3, 4 and 5. Our results indicate while computing st paths of length 3, and 4 are easy in the average case with O(1) update time (note that they are hard in the worst case), it becomes hard when considering st paths of length 5. We introduce new techniques which allow us to get average-case hardness for these graph problems from the worst-case hardness of the Online Matrix vector problem (OMv). Our techniques rely on recent advances in fine-grained average-case complexity. Our techniques advance this literature, giving the ability to prove new lower bounds on average-case dynamic algorithms.

List-decodable zero-rate codes for the Z-channel - Polyanskii, Nikita; Zhang, Yihan (2022 IEEE International Symposium on Information Theory)
This paper studies 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 (in n) size if τ is less than a critical value that we call the Plotkin point and has constant size if τ is larger than the threshold. The (L−1)-list-decoding Plotkin point is known to be L−1L−1−L−LL−1. In this paper, we show that the largest (L−1)-list-decodable code ε-above the Plotkin point has size Θ L (ε −3/2 ) for any L − 1 ≥ 1.

Existence and density problems in Diophantine geometry: From norm forms to Campana points - Shute, Alec L
In this thesis, we study two of the most important questions in Arithmetic geometry: that of the existence and density of solutions to Diophantine equations. In order for a Diophantine equation to have any solutions over the rational numbers, it must have solutions everywhere locally, i.e., over R and over Qp for every prime p. The converse, called the Hasse principle, is known to fail in general. However, it is still a central question in Arithmetic geometry to determine for which varieties the Hasse principle does hold. In this work, we establish the Hasse principle for a wide new family of varieties of the form f(t) = NK/Q(x) ̸= 0, where f is a polynomial with integer coefficients and NK/Q denotes the norm form associated to a number field K. Our results cover products of arbitrarily many linear, quadratic or cubic factors, and generalise an argument of Irving [69], which makes use of the beta sieve of Rosser and Iwaniec. We also demonstrate how our main sieve results can be applied to treat new cases of a conjecture of Harpaz and Wittenberg on locally split values of polynomials over number fields, and discuss consequences for rational points in fibrations. In the second question, about the density of solutions, one defines a height function and seeks to estimate asymptotically the number of points of height bounded by B as B → ∞. Traditionally, one either counts rational points, or integral points with respect to a suitable model. However, in this thesis, we study an emerging area of interest in Arithmetic geometry known as Campana points, which in some sense interpolate between rational and integral points. More precisely, we count the number of nonzero integers z1, z2, z3 such that gcd(z1, z2, z3) = 1, and z1, z2, z3, z1 + z2 + z3 are all squareful and bounded by B. Using the circle method, we obtain an asymptotic formula which agrees in the power of B and log B with a bold new generalisation of Manin’s conjecture to the setting of Campana points, recently formulated by Pieropan, Smeets, Tanimoto and Várilly-Alvarado [96]. However, in this thesis we also provide the first known counterexamples to leading constant predicted by their conjecture.

Synthesis of parametric hybrid automata from time series - Garcia Soto, Miriam; Henzinger, Thomas A; Schilling, Christian (20th International Symposium on Automated Technology for Verification and Analysis)
We propose an algorithmic approach for synthesizing linear hybrid automata from time-series data. Unlike existing approaches, our approach provides a whole family of models with the same discrete structure but different dynamics. Each model in the family is guaranteed to capture the input data up to a precision error ε, in the following sense: For each time series, the model contains an execution that is ε-close to the data points. Our construction allows to effectively choose a model from this family with minimal precision error ε. We demonstrate the algorithm’s efficiency and its ability to find precise models in two case studies.

Practical asynchronous distributed key generation - Das, Sourav; Yurek, Thomas; Xiang, Zhuolun; Miller, Andrew; Kokoris Kogias, Eleftherios; Ren, Ling (2022 IEEE Symposium on Security and Privacy)
Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted third party and is a building block to decentralized protocols such as randomness beacons, threshold signatures, and general multiparty computation. Until recently, DKG protocols have assumed the synchronous model and thus are vulnerable when their underlying network assumptions do not hold. The recent advancements in asynchronous DKG protocols are insufficient as they either have poor efficiency or limited functionality, resulting in a lack of concrete implementations. In this paper, we present a simple and concretely efficient asynchronous DKG (ADKG) protocol. In a network of n nodes, our ADKG protocol can tolerate up to t<n/3 malicious nodes and have an expected O(κn3) communication cost, where κ is the security parameter. Our ADKG protocol produces a field element as the secret and is thus compatible with off-the-shelf threshold cryptosystems. We implement our ADKG protocol and evaluate it using a network of up to 128 nodes in geographically distributed AWS instances. Our evaluation shows that our protocol takes as low as 3 and 9.5 seconds to terminate for 32 and 64 nodes, respectively. Also, each node sends only 0.7 Megabytes and 2.9 Megabytes of data during the two experiments, respectively.

Loop Grassmannians of Quivers and Affine Quantum Groups - Mirković, Ivan; Yang, Yaping; Zhao, Gufang (Representation Theory and Algebraic Geometry)
We construct for each choice of a quiver Q, a cohomology theory A, and a poset P a “loop Grassmannian” GP(Q,A). This generalizes loop Grassmannians of semisimple groups and the loop Grassmannians of based quadratic forms. The addition of a “dilation” torus D⊆G2m gives a quantization GPD(Q,A). This construction is motivated by the program of introducing an inner cohomology theory in algebraic geometry adequate for the Geometric Langlands program (Mirković, Some extensions of the notion of loop Grassmannians. Rad Hrvat. Akad. Znan. Umjet. Mat. Znan., the Mardešić issue. No. 532, 53–74, 2017) and on the construction of affine quantum groups from generalized cohomology theories (Yang and Zhao, Quiver varieties and elliptic quantum groups, preprint. arxiv1708.01418).

A direct symbolic algorithm for solving stochastic rabin games - Banerjee, Tamajit; Majumdar, Rupak; Mallik, Kaushik; Schmuck, Anne-Kathrin; Soudjani, Sadegh (28th International Conference on Tools and Algorithms for the Construction and Analysis of Systems)
We consider turn-based stochastic 2-player games on graphs with ω-regular winning conditions. We provide a direct symbolic algorithm for solving such games when the winning condition is formulated as a Rabin condition. For a stochastic Rabin game with k pairs over a game graph with n vertices, our algorithm runs in O(nk+2k!) symbolic steps, which improves the state of the art. We have implemented our symbolic algorithm, along with performance optimizations including parallellization and acceleration, in a BDD-based synthesis tool called Fairsyn. We demonstrate the superiority of Fairsyn compared to the state of the art on a set of synthetic benchmarks derived from the VLTS benchmark suite and on a control system benchmark from the literature. In our experiments, Fairsyn performed significantly faster with up to two orders of magnitude improvement in computation time.