@article{13261, abstract = {Chromosomes in the eukaryotic nucleus are highly compacted. However, for many functional processes, including transcription initiation, the pairwise motion of distal chromosomal elements such as enhancers and promoters is essential and necessitates dynamic fluidity. Here, we used a live-imaging assay to simultaneously measure the positions of pairs of enhancers and promoters and their transcriptional output while systematically varying the genomic separation between these two DNA loci. Our analysis reveals the coexistence of a compact globular organization and fast subdiffusive dynamics. These combined features cause an anomalous scaling of polymer relaxation times with genomic separation leading to long-ranged correlations. Thus, encounter times of DNA loci are much less dependent on genomic distance than predicted by existing polymer models, with potential consequences for eukaryotic gene expression.}, author = {Brückner, David and Chen, Hongtao and Barinov, Lev and Zoller, Benjamin and Gregor, Thomas}, issn = {1095-9203}, journal = {Science}, number = {6652}, pages = {1357--1362}, publisher = {American Association for the Advancement of Science}, title = {{Stochastic motion and transcriptional dynamics of pairs of distal DNA loci on a compacted chromosome}}, doi = {10.1126/science.adf5568}, volume = {380}, year = {2023}, } @inproceedings{13262, abstract = {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.}, author = {Fedorov, Alexander and Hashemi, Diba and Nadiradze, Giorgi and Alistarh, Dan-Adrian}, booktitle = {Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures}, isbn = {9781450395458}, location = {Orlando, FL, United States}, pages = {261--271}, publisher = {Association for Computing Machinery}, title = {{Provably-efficient and internally-deterministic parallel Union-Find}}, doi = {10.1145/3558481.3591082}, year = {2023}, } @article{13263, abstract = {Motivation: Boolean networks are simple but efficient mathematical formalism for modelling complex biological systems. However, having only two levels of activation is sometimes not enough to fully capture the dynamics of real-world biological systems. Hence, the need for multi-valued networks (MVNs), a generalization of Boolean networks. Despite the importance of MVNs for modelling biological systems, only limited progress has been made on developing theories, analysis methods, and tools that can support them. In particular, the recent use of trap spaces in Boolean networks made a great impact on the field of systems biology, but there has been no similar concept defined and studied for MVNs to date. Results: In this work, we generalize the concept of trap spaces in Boolean networks to that in MVNs. We then develop the theory and the analysis methods for trap spaces in MVNs. In particular, we implement all proposed methods in a Python package called trapmvn. Not only showing the applicability of our approach via a realistic case study, we also evaluate the time efficiency of the method on a large collection of real-world models. The experimental results confirm the time efficiency, which we believe enables more accurate analysis on larger and more complex multi-valued models.}, author = {Trinh, Van Giang and Benhamou, Belaid and Henzinger, Thomas A and Pastva, Samuel}, issn = {1367-4811}, journal = {Bioinformatics}, number = {Supplement_1}, pages = {i513--i522}, publisher = {Oxford University Press}, title = {{Trap spaces of multi-valued networks: Definition, computation, and applications}}, doi = {10.1093/bioinformatics/btad262}, volume = {39}, year = {2023}, } @article{13265, abstract = {In this study, we propose a computational framework for optimizing the continuity of the toolpath in fabricating surface models on an extrusion-based 3D printer. Toolpath continuity is a critical issue that influences both the quality and the efficiency of extrusion-based fabrication. Transfer moves lead to rough and bumpy surfaces, where this phenomenon worsens for materials with large viscosity, like clay. The effects of continuity on the surface models are even more severe in terms of the quality of the surface and the stability of the model. We introduce a criterion called the one–path patch (OPP) to represent a patch on the surface of the shell that can be traversed along one path by considering the constraints on fabrication. We study the properties of the OPPs and their merging operations to propose a bottom-up OPP merging procedure to decompose the given shell surface into a minimal number of OPPs, and to generate the “as-continuous-as-possible” (ACAP) toolpath. Furthermore, we augment the path planning algorithm with a curved-layer printing scheme that reduces staircase defects and improves the continuity of the toolpath by connecting multiple segments. We evaluated the ACAP algorithm on ceramic and thermoplastic materials, and the results showed that it improves the fabrication of surface models in terms of both efficiency and surface quality.}, author = {Zhong, Fanchao and Xu, Yonglai and Zhao, Haisen and Lu, Lin}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, number = {3}, publisher = {Association for Computing Machinery}, title = {{As-Continuous-As-Possible extrusion-based fabrication of surface models}}, doi = {10.1145/3575859}, volume = {42}, year = {2023}, } @article{13266, abstract = {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.}, author = {Qi, Linlin and Friml, Jiří}, issn = {1469-8137}, journal = {New Phytologist}, number = {2}, pages = {489--495}, publisher = {Wiley}, title = {{Tale of cAMP as a second messenger in auxin signaling and beyond}}, doi = {10.1111/nph.19123}, volume = {240}, year = {2023}, } @article{13268, abstract = {We give a simple argument to prove Nagai’s conjecture for type II degenerations of compact hyperkähler manifolds and cohomology classes of middle degree. Under an additional assumption, the techniques yield the conjecture in arbitrary degree. This would complete the proof of Nagai’s conjecture in general, as it was proved already for type I degenerations by Kollár, Laza, Saccà, and Voisin [10] and independently by Soldatenkov [18], while it is immediate for type III degenerations. Our arguments are close in spirit to a recent paper by Harder [8] proving similar results for the restrictive class of good degenerations.}, author = {Huybrechts, D. and Mauri, Mirko}, issn = {1945-001X}, journal = {Mathematical Research Letters}, number = {1}, pages = {125--141}, publisher = {International Press}, title = {{On type II degenerations of hyperkähler manifolds}}, doi = {10.4310/mrl.2023.v30.n1.a6}, volume = {30}, year = {2023}, } @article{13269, abstract = {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.}, author = {Polyanskii, Nikita and Zhang, Yihan}, issn = {1557-9654}, journal = {IEEE Transactions on Information Theory}, number = {10}, pages = {6340--6357}, publisher = {Institute of Electrical and Electronics Engineers}, title = {{Codes for the Z-channel}}, doi = {10.1109/TIT.2023.3292219}, volume = {69}, year = {2023}, } @article{13270, abstract = {Consider a geodesic triangle on a surface of constant curvature and subdivide it recursively into four triangles by joining the midpoints of its edges. We show the existence of a uniform δ>0 such that, at any step of the subdivision, all the triangle angles lie in the interval (δ,π−δ) . Additionally, we exhibit stabilising behaviours for both angles and lengths as this subdivision progresses.}, author = {Brunck, Florestan R}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, number = {3}, pages = {1059--1089}, publisher = {Springer Nature}, title = {{Iterated medial triangle subdivision in surfaces of constant curvature}}, doi = {10.1007/s00454-023-00500-5}, volume = {70}, year = {2023}, } @misc{13275, abstract = {We introduce a generic and accessible implementation of an exact diagonalization method for studying few-fermion models. Our aim is to provide a testbed for the newcomers to the field as well as a stepping stone for trying out novel optimizations and approximations. This userguide consists of a description of the algorithm, and several examples in varying orders of sophistication. In particular, we exemplify our routine using an effective-interaction approach that fixes the low-energy physics. We benchmark this approach against the existing data, and show that it is able to deliver state-of-the-art numerical results at a significantly reduced computational cost.}, author = {Rammelmüller, Lukas and Huber, David and Volosniev, Artem}, publisher = {SciPost Foundation}, title = {{Codebase release 1.0 for FermiFCI}}, doi = {10.21468/scipostphyscodeb.12-r1.0}, year = {2023}, } @article{13276, abstract = {We introduce a generic and accessible implementation of an exact diagonalization method for studying few-fermion models. Our aim is to provide a testbed for the newcomers to the field as well as a stepping stone for trying out novel optimizations and approximations. This userguide consists of a description of the algorithm, and several examples in varying orders of sophistication. In particular, we exemplify our routine using an effective-interaction approach that fixes the low-energy physics. We benchmark this approach against the existing data, and show that it is able to deliver state-of-the-art numerical results at a significantly reduced computational cost.}, author = {Rammelmüller, Lukas and Huber, David and Volosniev, Artem}, issn = {2949-804X}, journal = {SciPost Physics Codebases}, publisher = {SciPost Foundation}, title = {{A modular implementation of an effective interaction approach for harmonically trapped fermions in 1D}}, doi = {10.21468/scipostphyscodeb.12}, year = {2023}, } @article{13277, abstract = {Recent experimental advances have inspired the development of theoretical tools to describe the non-equilibrium dynamics of quantum systems. Among them an exact representation of quantum spin systems in terms of classical stochastic processes has been proposed. Here we provide first steps towards the extension of this stochastic approach to bosonic systems by considering the one-dimensional quantum quartic oscillator. We show how to exactly parameterize the time evolution of this prototypical model via the dynamics of a set of classical variables. We interpret these variables as stochastic processes, which allows us to propose a novel way to numerically simulate the time evolution of the system. We benchmark our findings by considering analytically solvable limits and providing alternative derivations of known results.}, author = {Tucci, Gennaro and De Nicola, Stefano and Wald, Sascha and Gambassi, Andrea}, issn = {2666-9366}, journal = {SciPost Physics Core}, keywords = {Statistical and Nonlinear Physics, Atomic and Molecular Physics, and Optics, Nuclear and High Energy Physics, Condensed Matter Physics}, number = {2}, publisher = {SciPost Foundation}, title = {{Stochastic representation of the quantum quartic oscillator}}, doi = {10.21468/scipostphyscore.6.2.029}, volume = {6}, year = {2023}, } @article{13278, abstract = {We present a numerical analysis of spin-1/2 fermions in a one-dimensional harmonic potential in the presence of a magnetic point-like impurity at the center of the trap. The model represents a few-body analogue of a magnetic impurity in the vicinity of an s-wave superconductor. Already for a few particles we find a ground-state level crossing between sectors with different fermion parities. We interpret this crossing as a few-body precursor of a quantum phase transition, which occurs when the impurity "breaks" a Cooper pair. This picture is further corroborated by analyzing density-density correlations in momentum space. Finally, we discuss how the system may be realized with existing cold-atoms platforms.}, author = {Rammelmüller, Lukas and Huber, David and Čufar, Matija and Brand, Joachim and Hammer, Hans-Werner and Volosniev, Artem}, issn = {2542-4653}, journal = {SciPost Physics}, keywords = {General Physics and Astronomy}, number = {1}, publisher = {SciPost Foundation}, title = {{Magnetic impurity in a one-dimensional few-fermion system}}, doi = {10.21468/scipostphys.14.1.006}, volume = {14}, year = {2023}, } @inproceedings{13292, abstract = {The operator precedence languages (OPLs) represent the largest known subclass of the context-free languages which enjoys all desirable closure and decidability properties. This includes the decidability of language inclusion, which is the ultimate verification problem. Operator precedence grammars, automata, and logics have been investigated and used, for example, to verify programs with arithmetic expressions and exceptions (both of which are deterministic pushdown but lie outside the scope of the visibly pushdown languages). In this paper, we complete the picture and give, for the first time, an algebraic characterization of the class of OPLs in the form of a syntactic congruence that has finitely many equivalence classes exactly for the operator precedence languages. This is a generalization of the celebrated Myhill-Nerode theorem for the regular languages to OPLs. As one of the consequences, we show that universality and language inclusion for nondeterministic operator precedence automata can be solved by an antichain algorithm. Antichain algorithms avoid determinization and complementation through an explicit subset construction, by leveraging a quasi-order on words, which allows the pruning of the search space for counterexample words without sacrificing completeness. Antichain algorithms can be implemented symbolically, and these implementations are today the best-performing algorithms in practice for the inclusion of finite automata. We give a generic construction of the quasi-order needed for antichain algorithms from a finite syntactic congruence. This yields the first antichain algorithm for OPLs, an algorithm that solves the ExpTime-hard language inclusion problem for OPLs in exponential time.}, author = {Henzinger, Thomas A and Kebis, Pavol and Mazzocchi, Nicolas Adrien and Sarac, Naci E}, booktitle = {50th International Colloquium on Automata, Languages, and Programming}, isbn = {9783959772785}, issn = {1868-8969}, location = {Paderborn, Germany}, pages = {129:1----129:20}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Regular methods for operator precedence languages}}, doi = {10.4230/LIPIcs.ICALP.2023.129}, volume = {261}, year = {2023}, } @inproceedings{13310, abstract = {Machine-learned systems are in widespread use for making decisions about humans, and it is important that they are fair, i.e., not biased against individuals based on sensitive attributes. We present runtime verification of algorithmic fairness for systems whose models are unknown, but are assumed to have a Markov chain structure. We introduce a specification language that can model many common algorithmic fairness properties, such as demographic parity, equal opportunity, and social burden. We build monitors that observe a long sequence of events as generated by a given system, and output, after each observation, a quantitative estimate of how fair or biased the system was on that run until that point in time. The estimate is proven to be correct modulo a variable error bound and a given confidence level, where the error bound gets tighter as the observed sequence gets longer. Our monitors are of two types, and use, respectively, frequentist and Bayesian statistical inference techniques. While the frequentist monitors compute estimates that are objectively correct with respect to the ground truth, the Bayesian monitors compute estimates that are correct subject to a given prior belief about the system’s model. Using a prototype implementation, we show how we can monitor if a bank is fair in giving loans to applicants from different social backgrounds, and if a college is fair in admitting students while maintaining a reasonable financial burden on the society. Although they exhibit different theoretical complexities in certain cases, in our experiments, both frequentist and Bayesian monitors took less than a millisecond to update their verdicts after each observation.}, author = {Henzinger, Thomas A and Karimi, Mahyar and Kueffner, Konstantin and Mallik, Kaushik}, booktitle = {Computer Aided Verification}, isbn = {9783031377020}, issn = {1611-3349}, location = {Paris, France}, pages = {358–382}, publisher = {Springer Nature}, title = {{Monitoring algorithmic fairness}}, doi = {10.1007/978-3-031-37703-7_17}, volume = {13965}, year = {2023}, } @article{13315, abstract = {How do statistical dependencies in measurement noise influence high-dimensional inference? To answer this, we study the paradigmatic spiked matrix model of principal components analysis (PCA), where a rank-one matrix is corrupted by additive noise. We go beyond the usual independence assumption on the noise entries, by drawing the noise from a low-order polynomial orthogonal matrix ensemble. The resulting noise correlations make the setting relevant for applications but analytically challenging. We provide characterization of the Bayes optimal limits of inference in this model. If the spike is rotation invariant, we show that standard spectral PCA is optimal. However, for more general priors, both PCA and the existing approximate message-passing algorithm (AMP) fall short of achieving the information-theoretic limits, which we compute using the replica method from statistical physics. We thus propose an AMP, inspired by the theory of adaptive Thouless–Anderson–Palmer equations, which is empirically observed to saturate the conjectured theoretical limit. This AMP comes with a rigorous state evolution analysis tracking its performance. Although we focus on specific noise distributions, our methodology can be generalized to a wide class of trace matrix ensembles at the cost of more involved expressions. Finally, despite the seemingly strong assumption of rotation-invariant noise, our theory empirically predicts algorithmic performance on real data, pointing at strong universality properties.}, author = {Barbier, Jean and Camilli, Francesco and Mondelli, Marco and Sáenz, Manuel}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences of the United States of America}, number = {30}, publisher = {National Academy of Sciences}, title = {{Fundamental limits in structured principal component analysis and how to reach them}}, doi = {10.1073/pnas.2302028120}, volume = {120}, year = {2023}, } @article{13316, abstract = {Although budding yeast has been extensively used as a model organism for studying organelle functions and intracellular vesicle trafficking, whether it possesses an independent endocytic early/sorting compartment that sorts endocytic cargos to the endo-lysosomal pathway or the recycling pathway has long been unclear. The structure and properties of the endocytic early/sorting compartment differ significantly between organisms; in plant cells, the trans-Golgi network (TGN) serves this role, whereas in mammalian cells a separate intracellular structure performs this function. The yeast syntaxin homolog Tlg2p, widely localizing to the TGN and endosomal compartments, is presumed to act as a Q-SNARE for endocytic vesicles, but which compartment is the direct target for endocytic vesicles remained unanswered. Here we demonstrate by high-speed and high-resolution 4D imaging of fluorescently labeled endocytic cargos that the Tlg2p-residing compartment within the TGN functions as the early/sorting compartment. After arriving here, endocytic cargos are recycled to the plasma membrane or transported to the yeast Rab5-residing endosomal compartment through the pathway requiring the clathrin adaptors GGAs. Interestingly, Gga2p predominantly localizes at the Tlg2p-residing compartment, and the deletion of GGAs has little effect on another TGN region where Sec7p is present but suppresses dynamics of the Tlg2-residing early/sorting compartment, indicating that the Tlg2p- and Sec7p-residing regions are discrete entities in the mutant. Thus, the Tlg2p-residing region seems to serve as an early/sorting compartment and function independently of the Sec7p-residing region within the TGN.}, author = {Toshima, Junko Y. and Tsukahara, Ayana and Nagano, Makoto and Tojima, Takuro and Siekhaus, Daria E and Nakano, Akihiko and Toshima, Jiro}, issn = {2050-084X}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{The yeast endocytic early/sorting compartment exists as an independent sub-compartment within the trans-Golgi network}}, doi = {10.7554/eLife.84850}, volume = {12}, year = {2023}, } @article{13319, abstract = {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.}, author = {Vernooij, Matthijs and Wirth, Melchior}, issn = {1432-0916}, journal = {Communications in Mathematical Physics}, pages = {381--416}, publisher = {Springer Nature}, title = {{Derivations and KMS-symmetric quantum Markov semigroups}}, doi = {10.1007/s00220-023-04795-6}, volume = {403}, year = {2023}, } @inproceedings{13321, abstract = {We consider the problem of reconstructing the signal and the hidden variables from observations coming from a multi-layer network with rotationally invariant weight matrices. The multi-layer structure models inference from deep generative priors, and the rotational invariance imposed on the weights generalizes the i.i.d. Gaussian assumption by allowing for a complex correlation structure, which is typical in applications. In this work, we present a new class of approximate message passing (AMP) algorithms and give a state evolution recursion which precisely characterizes their performance in the large system limit. In contrast with the existing multi-layer VAMP (ML-VAMP) approach, our proposed AMP – dubbed multilayer rotationally invariant generalized AMP (ML-RI-GAMP) – provides a natural generalization beyond Gaussian designs, in the sense that it recovers the existing Gaussian AMP as a special case. Furthermore, ML-RI-GAMP exhibits a significantly lower complexity than ML-VAMP, as the computationally intensive singular value decomposition is replaced by an estimation of the moments of the design matrices. Finally, our numerical results show that this complexity gain comes at little to no cost in the performance of the algorithm.}, author = {Xu, Yizhou and Hou, Tian Qi and Liang, Shan Suo and Mondelli, Marco}, booktitle = {2023 IEEE Information Theory Workshop}, isbn = {9798350301496}, issn = {2475-4218}, location = {Saint-Malo, France}, pages = {294--298}, publisher = {Institute of Electrical and Electronics Engineers}, title = {{Approximate message passing for multi-layer estimation in rotationally invariant models}}, doi = {10.1109/ITW55543.2023.10160238}, year = {2023}, } @misc{13336, author = {Kleshnina, Maria}, publisher = {Zenodo}, title = {{kleshnina/stochgames_info: The effect of environmental information on evolution of cooperation in stochastic games}}, doi = {10.5281/ZENODO.8059564}, year = {2023}, } @article{13340, abstract = {Photoisomerization of azobenzenes from their stable E isomer to the metastable Z state is the basis of numerous applications of these molecules. However, this reaction typically requires ultraviolet light, which limits applicability. In this study, we introduce disequilibration by sensitization under confinement (DESC), a supramolecular approach to induce the E-to-Z isomerization by using light of a desired color, including red. DESC relies on a combination of a macrocyclic host and a photosensitizer, which act together to selectively bind and sensitize E-azobenzenes for isomerization. The Z isomer lacks strong affinity for and is expelled from the host, which can then convert additional E-azobenzenes to the Z state. In this way, the host–photosensitizer complex converts photon energy into chemical energy in the form of out-of-equilibrium photostationary states, including ones that cannot be accessed through direct photoexcitation.}, author = {Gemen, Julius and Church, Jonathan R. and Ruoko, Tero-Petri and Durandin, Nikita and Białek, Michał J. and Weissenfels, Maren and Feller, Moran and Kazes, Miri and Borin, Veniamin A. and Odaybat, Magdalena and Kalepu, Rishir and Diskin-Posner, Yael and Oron, Dan and Fuchter, Matthew J. and Priimagi, Arri and Schapiro, Igor and Klajn, Rafal}, issn = {1095-9203}, journal = {Science}, number = {6664}, pages = {1357--1363}, publisher = {American Association for the Advancement of Science}, title = {{Disequilibrating azoarenes by visible-light sensitization under confinement}}, doi = {10.1126/science.adh9059}, volume = {381}, year = {2023}, }