@article{19066, abstract = {We present a sample of 1956 individual stellar clumps at redshift 0.7 < z < 10, detected with JWST/NIRCam in 476 galaxies lensed by the galaxy cluster Abell2744. The lensed clumps present magnifications ranging between μ = 1.8 and μ = 300. We perform simultaneous size-photometry estimates in 20 JWST/NIRCam median and broad-band filters from 0.7 to 5 μm. Spectral energy distribution (SED) fitting analyses enable us to recover the physical properties of the clumps. The majority of the clumps are spatially resolved and have effective radii in the range Reff = 10–700 pc. We restrict this first study to the 1751 post-reionization era clumps with redshift < 5.5. We find a significant evolution of the average clump ages, star formation rates (SFRs), SFR surface densities, and metallicity with increasing redshift, while median stellar mass and stellar mass surface densities are similar in the probed redshift range. We observe a strong correlation between the clump properties and the properties of their host galaxies, with more massive galaxies hosting more massive and older clumps. We find that clumps closer to their host galactic centre are on average more massive, while their ages do not show clear sign of migration. We find that clumps at cosmic noon sample the upper-mass end of the mass function to higher masses than at z > 3, reflecting the rapid increase towards the peak of the cosmic star formation history. We conclude that the results achieved over the studied redshift range are in agreement with expectation of in situ clump formation scenario from large-scale disc fragmentation. }, author = {Claeyssens, Adélaïde and Adamo, Angela and Messa, Matteo and Dessauges-Zavadsky, Miroslava and Richard, Johan and Kramarenko, Ivan and Matthee, Jorryt J and Naidu, Rohan P.}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, number = {3}, pages = {2535--2558}, publisher = {Oxford University Press}, title = {{Tracing star formation across cosmic time at tens of parsec-scales in the lensing cluster field Abell 2744}}, doi = {10.1093/mnras/staf058}, volume = {537}, year = {2025}, } @article{19067, abstract = {Modern experimental methods enable the creation of self-assembly building blocks with tunable interactions, but optimally exploiting this tunability for the self-assembly of desired structures remains an important challenge. Many studies of this inverse problem start with the so-called fully addressable limit, where every particle in a target structure is different. This leads to clear design principles that often result in high assembly yield, but it is not a scalable approach—at some point, one must grapple with “reusing” building blocks, which lowers the degree of addressability and may cause a multitude of off-target structures to form, complicating the design process. Here, we solve a key obstacle preventing robust inverse design in the “semiaddressable regime” by developing a highly efficient algorithm that enumerates all structures that can be formed from a given set of building blocks. By combining this with established partition-function-based yield calculations, we show that it is almost always possible to find economical semiaddressable designs where the entropic gain from reusing building blocks outweighs the presence of off-target structures and even increases the yield of the target. Thus, not only does our enumeration algorithm enable robust and scalable inverse design in the semiaddressable regime, our results demonstrate that it is possible to operate in this regime while maintaining the level of control often associated with full addressability.}, author = {Hübl, Maximilian and Goodrich, Carl Peter}, issn = {1079-7114}, journal = {Physical Review Letters}, number = {5}, publisher = {American Physical Society}, title = {{Accessing semiaddressable self-assembly with efficient structure enumeration}}, doi = {10.1103/PhysRevLett.134.058204}, volume = {134}, year = {2025}, } @misc{19409, abstract = {This .zip file contains the data to reproduce the figures and supplementary figures of "Exchange anisotropies in microwave-driven singlet-triplet qubits" by Jaime Saez-Mollejo et al. }, author = {Saez Mollejo, Jaime}, publisher = {Institute of Science and Technology Austria}, title = {{Exchange anisotropies in microwave-driven singlet-triplet qubits}}, doi = {10.15479/AT:ISTA:19409}, year = {2025}, } @article{19531, abstract = {In standard quantum electrodynamics (QED), the so-called non-minimal (Pauli) coupling is suppressed for elementary particles and has no physical implications. Here, we show that the Pauli term naturally appears in a known family of Dirac materials—the lead-halide perovskites, suggesting a novel playground for the study of analog QED effects. We outline measurable manifestations of the Pauli term in the phenomena pertaining to (i) relativistic corrections to bound states (ii) the Klein paradox, and (iii) spin effects in scattering. In particular, we demonstrate that (a) the binding energy of an electron in the vicinity of a positively charged defect is noticeably decreased due to the polarizability of lead ions and the appearance of a Darwin-like term, (b) strong spin-orbit coupling due to the Pauli term affects the exciton states, and (c) scattering of an electron off an energy barrier with broken mirror symmetry produces spin polarization in the outgoing current. Our study adds to the understanding of quantum phenomena in lead-halide perovskites and paves the way for tabletop simulations of analog Dirac-Pauli equations.}, author = {Shiva Kumar, Abhishek and Maslov, Mikhail and Lemeshko, Mikhail and Volosniev, Artem and Alpichshev, Zhanybek}, issn = {2397-4648}, journal = {npj Quantum Materials}, publisher = {Springer Nature}, title = {{Massive Dirac-Pauli physics in lead-halide perovskites}}, doi = {10.1038/s41535-025-00754-7}, volume = {10}, year = {2025}, } @article{19617, abstract = {In this article, we propose a method for generating single microwave photons in superconducting circuits. We theoretically show that pure single microwave photons can be generated on demand and tuned over a large frequency band by making use of Landau-Zener transitions under a rapid sweep of a control parameter. We devise a protocol that enables fast control of the frequency of the emitted photon over two octaves, without requiring extensive calibration. Additionally, we make theoretical estimates of the generation efficiency, tunability, purity, and linewidth of the photons emitted using this method for both charge- and flux-qubit-based architectures. We also provide estimates of the optimal device parameters required for these architectures to realize the device.}, author = {Hawaldar, Samarth and Khaire, Siddhi Satish and Delsing, Per and Suri, Baladitya}, issn = {2331-7019}, journal = {Physical Review Applied}, number = {4}, publisher = {American Physical Society}, title = {{On-demand single-microwave-photon source in a superconducting circuit with wideband frequency tunability}}, doi = {10.1103/physrevapplied.23.044042}, volume = {23}, year = {2025}, } @article{19621, abstract = {In this paper we obtain a complete description of all indecomposable characters (central positive-definite functions) of inductive limits of the symmetric groups under block diagonal embedding. As a corollary we obtain the full classification of the isomorphism classes of these inductive limits.}, author = {Nessonov, Nikolay and Ngo, Nhok T}, issn = {1088-4165}, journal = {Representation Theory}, number = {8}, pages = {256--288}, publisher = {American Mathematical Society}, title = {{Indecomposable characters of inductive limits of symmetric groups}}, doi = {10.1090/ert/689}, volume = {29}, year = {2025}, } @article{19702, abstract = {Moran Birth-death process is a standard stochastic process that is used to model natural selection in spatially structured populations. A newly occurring mutation that invades a population of residents can either fixate on the whole population or it can go extinct due to random drift. The duration of the process depends not only on the total population size n, but also on the spatial structure of the population. In this work, we consider the Moran process with a single type of individuals who invade and colonize an otherwise empty environment. Mathematically, this corresponds to the setting where the residents have zero reproduction rate, thus they never reproduce. The spatial structure is represented by a graph. We present two main contributions. First, in contrast to the Moran process in which residents do reproduce, we show that the colonization time is always at most a polynomial function of the population size n. Namely, we show that colonization always takes at most 1/2n^3 - 1/2n^2 expected steps, and for each n, we identify the slowest graph where it takes exactly that many steps. Moreover, we establish a stronger bound of roughly n^2.5 steps for undirected graphs and an even stronger bound of roughly n^2 steps for so-called regular graphs. Second, we discuss various complications that one faces when attempting to measure fixation times and colonization times in spatially structured populations, and we propose to measure the real duration of the process, rather than counting the steps of the classic Moran process.}, author = {Kopfová, Lenka and Tkadlec, Josef}, issn = {1553-7358}, journal = {PLoS computational biology}, number = {5}, pages = {e1012868}, publisher = {Public Library of Science}, title = {{Colonization times in Moran process on graphs}}, doi = {10.1371/journal.pcbi.1012868}, volume = {21}, year = {2025}, } @article{19704, abstract = {The information-processing capability of the brain’s cellular network depends on the physical wiring pattern between neurons and their molecular and functional characteristics. Mapping neurons and resolving their individual synaptic connections can be achieved by volumetric imaging at nanoscale resolution1,2 with dense cellular labelling. Light microscopy is uniquely positioned to visualize specific molecules, but dense, synapse-level circuit reconstruction by light microscopy has been out of reach, owing to limitations in resolution, contrast and volumetric imaging capability. Here we describe light-microscopy-based connectomics (LICONN). We integrated specifically engineered hydrogel embedding and expansion with comprehensive deep-learning-based segmentation and analysis of connectivity, thereby directly incorporating molecular information into synapse-level reconstructions of brain tissue. LICONN will allow synapse-level phenotyping of brain tissue in biological experiments in a readily adoptable manner.}, author = {Tavakoli, Mojtaba and Lyudchik, Julia and Januszewski, Michał and Vistunou, Vitali and Agudelo Duenas, Nathalie and Vorlaufer, Jakob and Sommer, Christoph M and Kreuzinger, Caroline and Oliveira, Bárbara and Cenameri, Alban and Novarino, Gaia and Jain, Viren and Danzl, Johann G}, issn = {1476-4687}, journal = {Nature}, pages = {398--410}, publisher = {Springer Nature}, title = {{Light-microscopy-based connectomic reconstruction of mammalian brain tissue}}, doi = {10.1038/s41586-025-08985-1}, volume = {642}, year = {2025}, } @inproceedings{19738, abstract = {Garbling is a fundamental cryptographic primitive, with numerous theoretical and practical applications. Since the first construction by Yao (FOCS’82, ’86), a line of work has concerned itself with reducing the communication and computational complexity of that construction. One of the most efficient garbling schemes presently is the ‘Half Gates’ scheme by Zahur, Rosulek, and Evans (Eurocrypt’15). Despite its widespread adoption, the provable security of this scheme has been based on assumptions whose only instantiations are in idealized models. For example, in their original paper, Zahur, Rosulek, and Evans showed that hash functions satisfying a notion called circular correlation robustness (CCR) suffice for this task, and then proved that CCR secure hash functions can be instantiated in the random permutation model. In this work, we show how to securely instantiate the Half Gates scheme in the standard model. To this end, we first show how this scheme can be securely instantiated given a (family of) weak CCR hash function, a notion that we introduce. Furthermore, we show how a weak CCR hash function can be used to securely instantiate other efficient garbling schemes, namely the ones by Rosulek and Roy (Crypto’21) and Heath (Eurocrypt’24). Thus we believe this notion to be of independent interest. Finally, we construct such weak CCR hash functions using indistinguishability obfuscation and one-way functions. The security proof of this construction constitutes our main technical contribution. While our construction is not practical, it serves as a proof of concept supporting the soundness of these garbling schemes, which we regard to be particularly important given the recent initiative by NIST to standardize garbling, and the optimizations in Half Gates being potentially adopted.}, author = {Acharya, Anasuya and Azari, Karen and Baig, Mirza Ahad and Hofheinz, Dennis and Kamath, Chethan}, booktitle = {28th IACR International Conference on Practice and Theory of Public-Key Cryptography}, isbn = {9783031918285}, issn = {1611-3349}, location = {Roros, Norway}, pages = {37--75}, publisher = {Springer Nature}, title = {{Securely instantiating ‘Half Gates’ garbling in the standard model}}, doi = {10.1007/978-3-031-91829-2_2}, volume = {15677}, year = {2025}, } @article{15128, abstract = {We prove a universal mesoscopic central limit theorem for linear eigenvalue statistics of a Wigner-type matrix inside the bulk of the spectrum with compactly supported twice continuously differentiable test functions. The main novel ingredient is an optimal local law for the two-point function $T(z,\zeta)$ and a general class of related quantities involving two resolvents at nearby spectral parameters.}, author = {Riabov, Volodymyr}, issn = {0246-0203}, journal = {Annales de l'institut Henri Poincare (B) Probability and Statistics}, number = {1}, pages = {129--154}, publisher = {Institute of Mathematical Statistics}, title = {{Mesoscopic eigenvalue statistics for Wigner-type matrices}}, doi = {10.1214/23-AIHP1438}, volume = {61}, year = {2025}, } @article{10045, abstract = {Given a fixed finite metric space (V,μ), the {\em minimum 0-extension problem}, denoted as 0-Ext[μ], is equivalent to the following optimization problem: minimize function of the form minx∈Vn∑ifi(xi)+∑ijcijμ(xi,xj) where cij,cvi are given nonnegative costs and fi:V→R are functions given by fi(xi)=∑v∈Vcviμ(xi,v). The computational complexity of 0-Ext[μ] has been recently established by Karzanov and by Hirai: if metric μ is {\em orientable modular} then 0-Ext[μ] can be solved in polynomial time, otherwise 0-Ext[μ] is NP-hard. To prove the tractability part, Hirai developed a theory of discrete convex functions on orientable modular graphs generalizing several known classes of functions in discrete convex analysis, such as L♮-convex functions. We consider a more general version of the problem in which unary functions fi(xi) can additionally have terms of the form cuv;iμ(xi,{u,v}) for {u,v}∈F, where set F⊆(V2) is fixed. We extend the complexity classification above by providing an explicit condition on (μ,F) for the problem to be tractable. In order to prove the tractability part, we generalize Hirai's theory and define a larger class of discrete convex functions. It covers, in particular, another well-known class of functions, namely submodular functions on an integer lattice. Finally, we improve the complexity of Hirai's algorithm for solving 0-Ext on orientable modular graphs. }, author = {Dvorak, Martin and Kolmogorov, Vladimir}, issn = {1436-4646}, journal = {Mathematical Programming}, keywords = {minimum 0-extension problem, metric labeling problem, discrete metric spaces, metric extensions, computational complexity, valued constraint satisfaction problems, discrete convex analysis, L-convex functions}, pages = {279--322}, publisher = {Springer Nature}, title = {{Generalized minimum 0-extension problem and discrete convexity}}, doi = {10.1007/s10107-024-02064-5}, volume = {209}, year = {2025}, } @misc{20883, abstract = {Evading imminent predator threat is critical for survival. Effective defensive strategies can vary, even between closely related species. However, the neural basis of such species-specific behaviours is still poorly understood. Here we find that two sister species of deer mice (genus Peromyscus) show different responses to the same looming stimulus: P. maniculatus, which occupies densely vegetated habitats, predominantly escapes, while the open field specialist, P. polionotus, briefly freezes. This difference arises from species-specific escape thresholds, is largely context-independent, and can be triggered by both visual and auditory threat stimuli. Using immunohistochemistry and electrophysiological recordings, we find that although visual threat activates the superior colliculus in both species, the role of the dorsal periaqueductal gray (dPAG) in driving behaviour differs. While dPAG activity scales with running speed in P. maniculatus, neural activity in the dPAG of P. polionotus correlates poorly with movement, including during visually triggered escape. Moreover, optogenetic activation of dPAG neurons elicits acceleration in P. maniculatus but not P. polionotus, while their chemogenetic inhibition during a looming stimulus delays escape onset in P. maniculatus to match that of P. polionotus. Together, we trace species-specific escape thresholds to a central circuit node, downstream of peripheral sensory neurons, localizing an ecologically relevant behavioural difference to a specific region of the mammalian brain.}, author = {Felix, Baier and Reinhard, Katja and Nuttin, Bram and Sans Dublanc, Arnau and Liu, Chen and Tong, Victoria and Murmann, Julie Stefanie and Wierda, Keimpe and Farrow, Karl and Hoekstra, Hopi}, publisher = {Dryad}, title = {{The neural basis of species-specific defensive behaviour in Peromyscus mice}}, doi = {10.5061/DRYAD.Q2BVQ83XC}, year = {2025}, } @article{20926, abstract = {Most current machine learning interatomic potentials (MLIPs) rely on short-range approximations, without explicit treatment of long-range electrostatics. To address this, we recently developed the Latent Ewald Summation (LES) method, which infers electrostatic interactions, polarization, and Born effective charges (BECs), just by learning from energy and force training data. Here, we present LES as a standalone library, compatible with any short-range MLIP, and demonstrate its integration with methods such as MACE, NequIP, Allegro, CACE, CHGNet, and UMA. We benchmark LES-enhanced models on distinct systems, including bulk water, polar dipeptides, and gold dimer adsorption on defective substrates, and show that LES not only captures correct electrostatics but also improves accuracy. Additionally, we scale LES to large and chemically diverse data by training MACELES-OFF on the SPICE set containing molecules and clusters, making a universal MLIP with electrostatics for organic systems, including biomolecules. MACELES-OFF is more accurate than its short-range counterpart (MACE-OFF) trained on the same data set, predicts dipoles and BECs reliably, and has better descriptions of bulk liquids. By enabling efficient long-range electrostatics without directly training on electrical properties, LES paves the way for electrostatic foundation MLIPs.}, author = {Kim, Dongjin and Wang, Xiaoyu and Vargas, Santiago and Zhong, Peichen and King, Daniel S. and Inizan, Theo Jaffrelot and Cheng, Bingqing}, issn = {1549-9626}, journal = {Journal of Chemical Theory and Computation}, number = {24}, pages = {12709--12724}, publisher = {American Chemical Society}, title = {{A universal augmentation framework for long-range electrostatics in machine learning interatomic potentials}}, doi = {10.1021/acs.jctc.5c01400}, volume = {21}, year = {2025}, } @article{21136, abstract = {The plant hormone auxin regulates growth and development through at least two distinct signaling pathways. The nuclear pathway, involving TIR1/AFB receptors, mediates transcription; whereas the cell surface ABP1-TMK1 auxin perception triggers global ultrafast phosphorylation response. Here, we revisit the rich history of the disputed ABP1 auxin receptor, highlighting recent findings of the involvement of TMKs and other molecular components and focusing on their role in auxin canalization-mediated development.}, author = {Monzer, Aline and Friml, Jiří}, issn = {3005-1401}, journal = {npj Science of Plants}, number = {1}, pages = {2}, publisher = {Springer Nature}, title = {{Historical and mechanistic perspective on ABP1-TMK1-mediated cell surface auxin signaling.}}, doi = {10.1038/s44383-025-00002-8}, volume = {1}, year = {2025}, } @article{21144, abstract = {This paper deals with the algorithmic aspects of solving feasibility problems of semidefinite programming (SDP), aka linear matrix inequalities (LMIs). Since in some SDP instances all feasible solutions have irrational entries, numerical solvers that work with rational numbers can only find an approximate solution. We study the following question: Is it possible to certify feasibility of a given SDP using an approximate solution that is sufficiently close to some exact solution? Existing approaches make the assumption that there exist rational feasible solutions (and use techniques such as rounding and lattice reduction algorithms). We propose an alternative approach that does not need this assumption. More specifically, we show how to construct a system of polynomial equations whose set of real solutions is guaranteed to have an isolated correct solution (assuming that the target exact solution is maximum-rank). This allows, in particular, for us to use algorithms from real algebraic geometry for solving systems of polynomial equations, yielding a hybrid (or symbolic-numerical) method for SDPs. We experimentally compare it with a pure symbolic method in [D. Henrion, S. Naldi, and M. Safey El Din, SIAM J. Optim., 26 (2016), pp. 2512–2539]; the hybrid method was able to certify feasibility of many SDP instances on which the aforementioned paper failed. Our approach may have further applications, such as refining an approximate solution using methods of numerical algebraic geometry for systems of polynomial equations.}, author = {Kolmogorov, Vladimir and Naldi, Simone and Zapata, Jeferson}, issn = {1095-7189}, journal = {SIAM Journal on Optimization}, number = {3}, pages = {1630--1654}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Certifying solutions of degenerate semidefinite programs}}, doi = {10.1137/24m1664691}, volume = {35}, year = {2025}, } @article{21248, abstract = {Camera-type eyes in vertebrates and cephalopods are striking examples of parallel evolution of a complex structure. While comparisons have focused on these two groups, camera-type eyes with likely high functionality are also found in other invertebrate phyla with simpler brains. Employing single-cell RNA sequencing, we identify neurogenic cells in the adult eyes and brain of the marine annelid worm Platynereis dumerilii. Distinct neural stem cells in the camera-type adult eyes, located at the edge of the cup-shaped retina, and adjacent to the glass body/lens, produce radial lines of cells, reminiscent of stem cells in ciliary marginal zones of vertebrate eyes exhibiting life-long growth. Normal proliferation in the eye depends on ambient light, a phenomenon that depends on the integrity of the photoreceptor gene c-opsin1, which is present in emerging rhabdomeric photoreceptors, and impacts on their differentiation. During reproductive maturation, proliferation in the eye as well as the entire brain sharply declines, while cells upregulate molecular characteristics of mammalian adult neural stem cell quiescence. Our data provide insights into the development and modulation of annelid head and brain cells, revealing similarities and differences to vertebrate eye development, neurogenesis and brain plasticity.}, author = {Milivojev, Nadja and Scaramuzza, Federico and Brum, Pedro Ozório and Velastegui Gamboa, Camila L and Andreatta, Gabriele and Raible, Florian and Tessmar-Raible, Kristin}, issn = {2041-1723}, journal = {Nature Communications}, publisher = {Springer Nature}, title = {{Light-modulated stem cells in the camera-type eye of an annelid model for adult brain plasticity}}, doi = {10.1038/s41467-025-65631-0}, volume = {16}, year = {2025}, } @inproceedings{21250, abstract = {We investigate the step complexity of the Leader Election problem (and implementing the corresponding test-and-set object) in asynchronous shared memory, where processes communicate through registers supporting atomic read and write and must coordinate so that a single process becomes the leader. Determining tight step complexity bounds for solving this problem is one of the key open problems in the theory of shared memory distributed computing. The best known algorithm is a randomized tournament-tree, which has worst-case expected step complexity O(log N) for N processes. There are provably no deterministic wait-free algorithms, and only restricted lower bounds are known for obstruction-free and randomized wait-free algorithms. We introduce a new lower bound that establishes an Ω((log N)/(log log N + log Q)) step complexity for any obstruction-free Leader Election algorithm, where N is the number of processes, and 2 ≤ Q ≤ N is a bound on the value contention, which we define as the maximum number of different values that processes can be simultaneously poised to write to the same register in any execution of the algorithm. Our result is strictly stronger than previous bounds based on write contention. In particular, it implies new lower bounds on step complexity that depend on register size.}, author = {Alistarh, Dan-Adrian and Ellen, Faith and Fedorov, Alexander}, booktitle = {39th International Symposium on Distributed Computing}, location = {Berlin, Germany}, pages = {3:1--3:16}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{An almost-logarithmic lower bound for leader election with bounded value contention}}, doi = {10.4230/LIPIcs.DISC.2025.3}, volume = {356}, year = {2025}, } @inbook{21257, abstract = {We investigate the problem of accurate sparse fine-tuning of large language models (LLMs), that is, fine-tuning pre-trained LLMs on specialized tasks, while inducing sparsity in their weights. Our work is motivated by experiments showing that standard loss-based fine-tuning methods are not able to achieve high accuracy in this setting, especially at high sparsity targets. To address this issue, we perform a detailed study of knowledge distillation losses for fine-tuning of sparse models. We determine an L2-based distillation approach that we term ‘SquareHead’, which enables accurate recovery even at higher sparsities. Investigating the question of efficient inference, we show that sparse LLMs can be executed faster by taking advantage of sparsity. Specifically, we exhibit end-to-end results showing speedups enabled by sparsity, while recovering accuracy, on the following models and tasks, respectively: T5 for language translation, Whisper for speech translation, and open GPT-type models such as the Mosaic Pre-Trained Transformer (MPT) and Llama-2 models for text generation. In particular, for popular generative tasks, we show for the first time that sparse fine-tuning can reach 75% sparsity without drops in accuracy, and provide notable end-to-end speedups for inference on CPUs. Moreover, we also highlight that sparsity is compatible with other compression approaches, such as quantization.}, author = {Kurtic, Eldar and Kuznedelev, Denis and Frantar, Elias and Goinv, Michael and Pandit, Shubhra and Agarwalla, Abhinav and Nguyen, Tuan and Marques, Alexandre and Kurtz, Mark and Alistarh, Dan-Adrian}, booktitle = {Enhancing LLM Performance. Efficacy, Fine-Tuning, and Inference Techniques}, editor = {Passban, Peyman and Way, Andy and Rezagholizadeh, Mehdi}, isbn = {9783031857461}, issn = {2522-803X}, pages = {83--97}, publisher = {Springer Nature}, title = {{Sparse Fine-Tuning for Inference Acceleration of Large Language Models}}, doi = {10.1007/978-3-031-85747-8_6}, year = {2025}, } @inproceedings{21281, abstract = {A strategy profile in a multi-player game is a Nash equilibrium if no player can unilaterally deviate to achieve a strictly better payoff. A profile is an ε-Nash equilibrium if no player can gain more than ε by unilaterally deviating from their strategy. In this work, we use ε-Nash equilibria to approximate the computation of Nash equilibria. Specifically, we focus on turn-based, multiplayer stochastic games played on graphs, where players are restricted to stationary strategies - strategies that use randomness but not memory. The problem of deciding the constrained existence of stationary Nash equilibria - where each player’s payoff must lie within a given interval - is known to be ∃ℝ-complete in such a setting (Hansen and Sølvsten, 2020). We extend this line of work to stationary ε-Nash equilibria and present an algorithm that solves the following promise problem: given a game with a Nash equilibrium satisfying the constraints, compute an ε-Nash equilibrium that ε-satisfies those same constraints - satisfies the constraints up to an ε additive error. Our algorithm runs in FNP^NP time. To achieve this, we first show that if a constrained Nash equilibrium exists, then one exists where the non-zero probabilities are at least an inverse of a double-exponential in the input. We further prove that such a strategy can be encoded using floating-point representations, as in the work of Frederiksen and Miltersen (2013), which finally gives us our FNP^NP algorithm. We further show that the decision version of the promise problem is NP-hard. Finally, we show a partial tightness result by proving a lower bound for such techniques: if a constrained Nash equilibrium exists, then there must be one where the probabilities in the strategies are double-exponentially small.}, author = {Asadi, Ali and Brice, Leonard and Chatterjee, Krishnendu and Thejaswini, K. S.}, booktitle = {45th Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, isbn = {9783959774062}, location = {Pilani, India}, pages = {9:1--9:17}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{ε-stationary Nash equilibria in multi-player stochastic graph games}}, doi = {10.4230/lipics.fsttcs.2025.9}, volume = {360}, year = {2025}, } @inproceedings{21327, abstract = {Proteins exist as a dynamic ensemble of multiple conformations, and these motions are often crucial for their functions. However, current structure prediction methods predominantly yield a single conformation, overlooking the conformational heterogeneity revealed by diverse experimental modalities. Here, we present a framework for building experiment-grounded protein structure generative models that infer conformational ensembles consistent with measured experimental data. The key idea is to treat stateof-the-art protein structure predictors (e.g., AlphaFold3) as sequence-conditioned structural priors, and cast ensemble modeling as posterior inference of protein structures given experimental measurements. Through extensive real-data experiments, we demonstrate the generality of our method to incorporate a variety of experimental measurements. In particular, our framework uncovers previously unmodeled conformational heterogeneity from crystallographic densities, and generates high-accuracy NMR ensembles orders of magnitude faster than the status quo. Notably, we demonstrate that our ensembles outperform AlphaFold3 (Abramson et al., 2024) and sometimes better fit experimental data than publicly deposited structures to the Protein Data Bank (PDB, Burley et al. (2017)). We believe that this approach will unlock building predictive models that fully embrace experimentally observed conformational diversity.}, author = {Maddipatla, Sai A and Sellam, Nadav E and Bojan, Meital I and Vedula, Sanketh and Schanda, Paul and Marx, Ailie and Bronstein, Alexander}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, issn = {2640-3498}, location = {Vancouver, Canada}, pages = {42366 -- 42393}, publisher = {ML Research Press}, title = {{Inverse problems with experiment-guided AlphaFold}}, volume = {267}, year = {2025}, }