@inproceedings{21091, abstract = {Neural certificates have emerged as a powerful tool in cyber-physical systems control, providing witnesses of correctness. These certificates, such as barrier functions, often learned alongside control policies, once verified, serve as mathematical proofs of system safety. However, traditional formal verification of their defining conditions typically faces scalability challenges due to exhaustive state-space exploration. To address this challenge, we propose a lightweight runtime monitoring framework that integrates real-time verification and does not require access to the underlying control policy. Our monitor observes the system during deployment and performs on-the-fly verification of the certificate over a lookahead region to ensure safety within a finite prediction horizon. We instantiate this framework for ReLU-based control barrier functions and demonstrate its practical effectiveness in a case study. Our approach enables timely detection of safety violations and incorrect certificates with minimal overhead, providing an effective but lightweight alternative to the static verification of the certificates.}, author = {Henzinger, Thomas A and Kueffner, Konstantin and Yu, Zhengqi}, booktitle = {25th International Conference on Runtime Verification}, issn = {1611-3349}, location = {Graz, Austria}, pages = {54--72}, publisher = {Springer Nature}, title = {{Formal verification of neural certificates done dynamically}}, doi = {10.1007/978-3-032-05435-7_4}, volume = {16087}, year = {2025}, } @inproceedings{21092, abstract = {Formal verification provides assurances that a probabilistic system satisfies its specification—conditioned on the system model being aligned with reality. We propose alignment monitoring to watch that this assumption is justified. We consider a probabilistic model well aligned if it accurately predicts the behaviour of an uncertain system in advance. An alignment score measures this by quantifying the similarity between the model’s predicted and the system’s (unknown) actual distributions. An alignment monitor observes the system at runtime; at each point in time it uses the current state and the model to predict the next state. After the next state is observed, the monitor updates the verdict, which is a high-probability interval estimate for the true alignment score. We utilize tools from sequential forecasting to construct our alignment monitors. Besides a monitor for measuring the expected alignment score, we introduce a differential alignment monitor, designed for comparing two models, and a weighted alignment monitor, which permits task-specific alignment monitoring. We evaluate our monitors experimentally on the PRISM benchmark suite. They are fast, memory-efficient, and detect misalignment early.}, author = {Henzinger, Thomas A and Kueffner, Konstantin and Singh, Vasu and Sun, I}, booktitle = {25th International Conference on Runtime Verification}, issn = {1611-3349}, location = {Graz, Austria}, pages = {140--159}, publisher = {Springer Nature}, title = {{Alignment monitoring}}, doi = {10.1007/978-3-032-05435-7_9}, volume = {16087}, year = {2025}, } @inproceedings{21093, abstract = {We propose a monitoring approach for hyperproperties where the system’s observations range over infinite domains. The specifications are given as formulas of symbolic hypernode logic, an extension of earlier versions of hypernode logic that supports events with data. We demonstrate how to translate terms of symbolic hypernode logic into multi-tape symbolic transducers and we present a monitoring algorithm for universally quantified formulas that is based on this translation. We evaluate our approach against the previous approach for monitoring hypernode logic, and we also compare it to other monitors for hyperproperties.}, author = {Chalupa, Marek and Henzinger, Thomas A and Oliveira da Costa, Ana A}, booktitle = {25th International Conference on Runtime Verification}, issn = {1611-3349}, location = {Graz, Austria}, pages = {417--437}, publisher = {Springer Nature}, title = {{Monitoring hypernode logic over infinite domains}}, doi = {10.1007/978-3-032-05435-7_23}, volume = {16087}, year = {2025}, } @article{21121, abstract = {The relation between the masses of supermassive black holes (SMBHs) and their host galaxies encodes information on their mode of growth, especially at the earliest epochs. The James Webb Space Telescope (JWST) has opened such investigations by detecting the host galaxies of active galactic nuclei (AGN) and more luminous quasars within the first billion years of the Universe (z ≳ 6). Here, we evaluate the relation between the mass of SMBHs and the total stellar mass of their host galaxies using a sample of nine quasars at 6.18 ≤ z ≤ 6.4 from the Subaru High-z Exploration of Low-luminosity Quasars survey with NIRCam and NIRSpec observations. We find that the observed location of these quasars in the SMBH–galaxy mass plane (logMBH/M 8–9; logM*/M 9.5–11) is consistent with a nonevolving intrinsic mass relation with dispersion (0.80 +0.23 -0.28 dex) higher than the local value (∼0.3–0.4 dex) of their more massive descendants. Our analysis is based on a forward model of systematics and includes a consideration of the impact of selection effects and measurement uncertainties with an assumption on the slope of the mass relation. While degeneracies between parameters persist, the best-fit solution has a reasonable AGN fraction (2.3%) of galaxies at z ∼ 6 with an actively growing UV-unobscured black hole. In particular, models with a substantially higher normalisation in MBH would require an unrealistically low intrinsic dispersion (∼0.22 dex). Consequently, our results predict a large population of AGN at lower black hole masses, as are now just starting to be discovered in focused efforts with JWST.}, author = {Silverman, John David and Li, Junyao and Ding, Xuheng and Onoue, Masafusa and Strauss, Michael A. and Matsuoka, Yoshiki and Izumi, Takuma and Jahnke, Knud and Treu, Tommaso and Volonteri, Marta and Phillips, Camryn L. and Andika, Irham T. and Aoki, Kentaro and Arita, Junya and Baba, Shunsuke and Bosman, Sarah E. I. and Eilers, Anna-Christina and Fan, Xiaohui and Fujimoto, Seiji and Habouzit, Melanie and Haiman, Zoltán and Imanishi, Masatoshi and Inayoshi, Kohei and Iwasawa, Kazushi and Kashikawa, Nobunari and Kawaguchi, Toshihiro and Lee, Chien-Hsiu and Lupi, Alessandro and Nagao, Tohru and Schindler, Jan-Torge and Schramm, Malte and Shimasaku, Kazuhiro and Toba, Yoshiki and Trakhtenbrot, Benny and Umehata, Hideki and Vestergaard, Marianne and Walter, Fabian and Wang, Feige and Yang, Jinyi}, issn = {2041-8213}, journal = {The Astrophysical Journal Letters}, number = {2}, publisher = {IOP Publishing}, title = {{SHELLQs–JWST perspective on the intrinsic mass relation between supermassive black holes and their host galaxies at z > 6}}, doi = {10.3847/2041-8213/ae279c}, volume = {995}, year = {2025}, } @article{21122, abstract = {The multimessenger combination of gravitational waves (GWs) from merging massive black hole binaries (MBHBs) and the electromagnetic (EM) counterpart from the surrounding circumbinary disc (CBD) will open avenues to new scientific pursuits. In order to realize this science, we need to correctly localize the host galaxy of the merging MBHB. Multiwavelength, time-dependent EM signatures can greatly facilitate the identification of the unique EM counterpart among many sources in LISA’s localization volume. To this end, we studied merging unequal-mass MBHBs embedded in a CBD using high-resolution 2D simulations, with a $\Gamma$-law equation of state, incorporating viscous heating, shock heating, and radiative cooling. We simulate each binary starting from before it decouples from the CBD until just after the merger. We compute EM signatures and identify distinct features before, during, and after the merger. We corroborate previous findings of a several orders of magnitude drop in the thermal X-ray luminosity near the time of merger, but with delayed timing compared to an equal-mass system. The source remains X-ray dark for hours post-merger. Our main results are a potential new signature of a sharp spike in the thermal X-ray emission just before the tell-tale steep drop occurs. This feature may further help to identify EM counterparts of LISA’s unequal MBHBs before merger without the need for extensive pre-merger monitoring. Additionally, we find a role-reversal in which the primary out-accretes the secondary during late inspiral, which may diminish signatures originating from Doppler modulation.}, author = {Krauth, Luke Major and Davelaar, Jordy and Haiman, Zoltán and Westernacher-Schneider, John Ryan and Zrake, Jonathan and MacFadyen, Andrew}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, number = {3}, pages = {2670--2685}, publisher = {Oxford University Press}, title = {{Thermal X-ray signatures in late-stage unequal-mass massive black hole binary mergers}}, doi = {10.1093/mnras/staf1583}, volume = {543}, year = {2025}, } @article{21123, abstract = {We present a study of the late-time interaction between supermassive black hole binaries and retrograde circumbinary disks during the period of gravitational wave-driven inspiral. While mergers in prograde disks have received extensive study, retrograde disks offer distinct dynamics that could promote mergers and produce unique observational signatures. Through 2D numerical hydrodynamical simulations, we explore the process of binary-disk decoupling, where the binary’s orbital decay rate is faster than the disk’s viscous response rate. We find the point of decoupling to be comparable in prograde and retrograde disks, suggesting that any associated electromagnetic (EM) signatures will be produced at comparable times preceding the merger. However, we find smaller central cavities for retrograde disks, likely leading to higher-frequency EM emissions and shorter postmerger rebrightening timescales compared to their prograde counterparts. Retrograde disks form intrabinary bridges, which are prone to instabilities when the viscosity is low. These instabilities manifest as quasiperiodic flares in the accretion rate, which may produce distinctive EM signatures for retrograde disks.}, author = {O’Neill, David and Tiede, Christopher and D’Orazio, Daniel J. and Haiman, Zoltán and MacFadyen, Andrew}, issn = {1538-4357}, journal = {The Astrophysical Journal}, number = {2}, publisher = {IOP Publishing}, title = {{Gravitational wave decoupling in retrograde circumbinary disks}}, doi = {10.3847/1538-4357/ae0ca8}, volume = {993}, year = {2025}, } @article{21124, abstract = {The advent of the James Webb Space Telescope (JWST) has opened new horizons in the study of quasar host galaxies during the reionization epoch (z > 6). Building upon our previous initial measurements of stellar light from two quasar host galaxies at these redshifts, we now report the detection of the stellar light from the full Cycle 1 sample of 12 distant moderate-luminosity quasar (M1450 > −24 mag) host galaxies at z > 6 from the Hyper Suprime-Cam Subaru Strategic Program. Using JWST/NIRCam observations at 1.5 and 3.6 μm combined with 2D image decomposition analysis, we successfully detect the host galaxies in 11 of the 12 targets, underscoring the high detection rates achievable with moderate-luminosity quasars. Based on two-band photometry and spectral energy distribution fitting, we find that our host galaxies are massive, with log M*/M⊙ = 9.5–11.0. The effective radii range from 0.6 to 3.2 kpc, comparable to the sizes of inactive galaxies with similar masses at z ∼ 6 as measured with imaging from COSMOS-Web. Intriguingly, the two quasar hosts with post-starburst features, which reside at the high-mass end of our sample and exhibit relatively compact morphologies, have similar size and stellar mass surface densities to quiescent galaxies at z ∼ 4–5. These findings suggest that the so-called galaxy compaction scenario is already in place at the reionization epoch, in which gas inflows during starburst phases drive centrally concentrated star formation followed by rapid quenching, bridging the structural transition of massive galaxies from relatively extended star-forming disks to compact quiescent systems.}, author = {Ding, Xuheng and Onoue, Masafusa and Silverman, John D. and Matsuoka, Yoshiki and Izumi, Takuma and Strauss, Michael A. and Yang, Lilan and Jahnke, Knud and Phillips, Camryn L. and Treu, Tommaso and Andika, Irham T. and Aoki, Kentaro and Arita, Junya and Baba, Shunsuke and Bosman, Sarah E. I. and Eilers, Anna-Christina and Fujimoto, Seiji and Haiman, Zoltán and Imanishi, Masatoshi and Inayoshi, Kohei and Iwasawa, Kazushi and Kartaltepe, Jeyhan and Kashikawa, Nobunari and Kawaguchi, Toshihiro and Li, Junyao and Lee, Chien-Hsiu and Lupi, Alessandro and Schindler, Jan-Torge and Schramm, Malte and Shimasaku, Kazuhiro and Shuntov, Marko and Tanaka, Takumi S. and Toba, Yoshiki and Trakhtenbrot, Benny and Umehata, Hideki and Vestergaard, Marianne and Wang, Feige and Yang, Jinyi}, issn = {1538-4357}, journal = {The Astrophysical Journal}, number = {1}, publisher = {IOP Publishing}, title = {{SHELLQs-JWST unveils the host galaxies of 12 quasars at z > 6}}, doi = {10.3847/1538-4357/ae045b}, volume = {993}, year = {2025}, } @article{21125, abstract = {The thermal Sunyaev-Zel’dovich effect (tSZ) is a sensitive probe of cosmology, as it traces the abundance of galaxy clusters and groups in the late-time Universe. Upcoming cosmic microwave background experiments such as the Simons Observatory (SO) and CMB-S4 will provide low-noise and high-resolution component-separated tSZ maps covering a large sky fraction. The tSZ signal is highly non-Gaussian; therefore, higher-order statistics are needed to optimally extract information from these maps. In this work, we study the cosmological constraining power of several tSZ statistics—Minkowski functionals (MFs), peaks, minima, and moments—that have yielded promising results in capturing non-Gaussian information from other cosmological data. Using a large suite of halo-model-based tSZ simulations with varying Ω𝑐 and 𝜎8 (154 cosmologies and over 800,000 maps, each 10.5×10.5  deg2), we show that by combining these observables, we can achieve ≈29 × tighter constraints compared to using the tSZ power spectrum alone in an idealized noiseless case, with the MFs dominating the constraints. We show that much of the MF constraining power arises from halos below the detection threshold of cluster surveys, suggesting promising synergies with cluster-count analyses. Finally, we demonstrate that these statistics have the potential to deliver tight constraints even in the presence of noise. For example, using post-component-separation tSZ noise expected for SO, we obtain ≈1.6 × and ≈1.8 × tighter constraints than the power spectrum with MFs and all statistics combined, respectively. We show that the constraints from MFs approach the noiseless case for white-noise levels ≲1  𝜇⁢K−arcmin.}, author = {Sabyr, Alina and Hill, J. Colin and Haiman, Zoltán}, issn = {2470-0029}, journal = {Physical Review D}, number = {10}, publisher = {American Physical Society}, title = {{Constraining cosmology with thermal Sunyaev-Zel’dovich maps: Minkowski functionals, peaks, minima, and moments}}, doi = {10.1103/physrevd.111.103536}, volume = {111}, year = {2025}, } @article{21126, abstract = {Subparsec supermassive black hole (SMBH) binaries are expected to be common in active galactic nuclei as a result of the hierarchical buildup of galaxies via mergers. While direct evidence for these compact binaries is lacking, a few hundred candidates have been identified, most based on the apparent periodicities of their optical light curves. Since these signatures can be mimicked by active galactic nuclei red noise, additional evidence is needed to confirm their binary nature. Recurring self-lensing flares, occurring whenever the two BHs are aligned with the line of sight within their Einstein radii, have been suggested as additional binary signatures. Furthermore, in many cases, lensing flares are also predicted to contain a “dip,” whenever the lensed SMBH’s shadow is comparable in angular size to the binary’s Einstein radius. This feature would unambiguously confirm binaries and additionally identify SMBH shadows that are spatially unresolvable by high-resolution Very Long Baseline Interferometry (VLBI). Here we estimate the number of quasars for which these dips may be detectable by Legacy Survey of Space and Time (LSST) by extrapolating the quasar luminosity function to faint magnitudes and assuming that SMBH binaries are randomly oriented and have mass ratios following those in the Illustris simulations. Under plausible assumptions about quasar lifetimes, binary fractions, and Eddington ratios, we expect tens of thousands of detectable flares, of which several dozen contain measurable dips.}, author = {Park, Kevin and Xin, Chengcheng and Davelaar, Jordy and Haiman, Zoltán}, issn = {2470-0029}, journal = {Physical Review D}, number = {6}, publisher = {American Physical Society}, title = {{Self-lensing flares from black hole binaries. IV. The number of detectable shadows}}, doi = {10.1103/physrevd.111.063011}, volume = {111}, year = {2025}, } @article{21127, abstract = {The early growth of black holes (BHs) in atomic-cooling haloes is likely influenced by feedback on the surrounding gas. While the effects of radiative feedback are well-documented, mechanical feedback, particularly from active galactic nucleus (AGN) jets, has been comparatively less explored. Building on our previous work that examined the growth of a 100 M BH in a constant density environment regulated by AGN jets, we expand the initial BH mass range from 1 to 104 M and adopt a more realistic density profile for atomic-cooling haloes. We reaffirm the validity of our analytic models for jet cocoon propagation and feedback regulation. We identify several critical radii – namely, the terminal radius of jet cocoon propagation, the isotropization radius of the jet cocoon, and the core radius of the atomic-cooling halo – that are crucial in determining BH growth given specific gas properties and jet feedback parameters. In a significant portion of the parameter space, our findings show that jet feedback substantially disrupts the halo’s core during the initial feedback episode, preventing BH growth beyond 104 M. Conversely, conditions characterized by low jet velocities and high gas densities enable sustained BH growth over extended periods. We provide a prediction for the BH mass growth as a function of time and feedback parameters. We found that, to form a supermassive BH (> 106 M) within 1 Gyr entirely by accreting gas from an atomic-cooling halo, the jet energy feedback efficiency must be 10−4M˙ BHc2 even if the seed BH mass is 104 M.}, author = {Su, Kung-Yi and Bryan, Greg L and Haiman, Zoltán}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, number = {1}, pages = {11--30}, publisher = {Oxford University Press}, title = {{Self-regulation of high-redshift black hole accretion via jets: Challenges for SMBH formation}}, doi = {10.1093/mnras/staf228}, volume = {538}, year = {2025}, } @article{21128, abstract = {The brightest steady sources of radiation in the universe, active galactic nuclei (AGNs), are powered by gas accretion on to a central supermassive black hole (SMBH). The large sizes and accretion rates implicated in AGN accretion discs are expected to lead to gravitational instability and fragmentation, effectively cutting off mass inflow to the SMBH. Radiative feedback from disc-embedded stars has been invoked to yield marginally stable, steady-state solutions in the outer discs. Here, we examine the consequences of this star formation with a semi-analytical model in which stellar-mass black hole (sBH) remnants in the disc provide an additional source of stabilizing radiative feedback. Assuming star formation seeds the embedded sBH population, we model the time-evolving feedback from both stars and the growing population of accreting sBHs. We find that in the outer disc, the luminosity of the sBHs quickly dominates that of their parent stars. However, because sBHs consume less gas than stars to stabilize the disc, the presence of the sBHs enhances the mass flux to the inner disc. As a result, star formation persists over the lifetime of the AGN, damped in the outer disc, but amplified in a narrow ring in the inner disc. Heating from the embedded sBHs significantly modifies the disc’s temperature profile and hardens its spectral energy distribution, and direct emission from the sBHs adds a new hard X-ray component.}, author = {Epstein-Martin, Marguerite and Tagawa, Hiromichi and Haiman, Zoltán and Perna, Rosalba}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, number = {4}, pages = {3396--3420}, publisher = {Oxford University Press}, title = {{Time-dependent models of AGN discs with radiation from embedded stellar-mass black holes}}, doi = {10.1093/mnras/staf237}, volume = {537}, year = {2025}, } @article{21129, abstract = {Recent hydrodynamical simulations have shown that circumbinary gas disks drive the orbits of massive binary black holes (BHs) to become eccentric, even when general relativistic (GR) corrections to the orbit are significant. Here, we study the GR apsidal precession of eccentric equal-mass massive binary BHs in circumbinary disks via two-dimensional hydrodynamical simulations. We perform a suite of simulations comparing precessing and nonprecessing binaries across a range of eccentricities, semimajor axes, and precession rates. We find that the GR precession of the binary’s semimajor axis can introduce a dominant modulation in the binary’s accretion rate and the corresponding high-energy electromagnetic light curves. We discuss the conditions under which this occurs and its detailed characteristics and mechanism. Finally, we discuss the potential to observe these precession signatures in electromagnetic- and gravitational-wave observations, as well as the precession signal’s unique importance as a potential tool to constrain the mass, eccentricity, and semimajor axis of binary merger events.}, author = {DeLaurentiis, Stanislav and Haiman, Zoltán and Westernacher-Schneider, John Ryan and Krauth, Luke Major and Davelaar, Jordy and Zrake, Jonathan and MacFadyen, Andrew}, issn = {1538-4357}, journal = {The Astrophysical Journal}, number = {1}, publisher = {IOP Publishing}, title = {{Relativistic binary precession: Impact on eccentric massive binary black hole accretion and hydrodynamics}}, doi = {10.3847/1538-4357/ada612}, volume = {980}, year = {2025}, } @article{21131, abstract = {Introduction: Parkinson’s disease (PD) impairs motor preparation due to basal ganglia dysfunction, contributing to motor deficits. Galvanic Vestibular Stimulation (GVS), a non-invasive neuromodulation technique, shows promise in enhancing motor function in PD, but its underlying neural mechanisms are poorly understood. This study employs a Deep Koopman model to linearize and analyze preparatory EEG dynamics in PD, hypothesizing that GVS restores cortical activity patterns critical for motor planning. Methods: EEG data from 18 PD participants (on/off medication) and 18 healthy controls were collected during a preparatory phase of a motor task under three conditions: sham, GVS1 (50–100 Hz multi-sine), and GVS2 (100–150 Hz multi-sine). A Deep Koopman framework mapped EEG signals into a three-dimensional latent space for linear dynamical analysis. Temporal dynamics were assessed via eigenvalue analysis, spatial contributions via regression-based scalp mapping, and motor performance correlations via Pearson’s coefficients. A Linear Quadratic Regulator (LQR) simulated control of PD dynamics toward healthy patterns. Results: The Deep Koopman model accurately captured EEG dynamics, with eigenvalue analysis showing no significant temporal dynamic differences across groups. Spatial contribution analysis revealed that PD-Off sham conditions deviated most from healthy control EEG patterns, while GVS and medication significantly reduced these deviations, aligning PD patterns closer to controls. Closer alignment correlated with improved motor performance metrics, including reduced reaction and squeeze times. LQR control effectively guided PD neural dynamics toward healthy trajectories in the latent space. Discussion: GVS enhances motor preparation in PD by restoring healthy cortical EEG patterns, with additive benefits from dopaminergic medication. The Deep Koopman framework offers a powerful approach for dissecting complex EEG dynamics and designing targeted neuromodulation strategies. These findings elucidate GVS’s therapeutic mechanisms and highlight its potential for personalized PD interventions, warranting further exploration in larger cohorts and varied stimulation protocols.}, author = {Kia, Maryam and Mirian, Maryam S. and Soori, Saeed and Saedi, Saeed and Arasteh, Emad and Faramarzi, Mohamadhosein and Chinchani, Abhijit and Lee, Soojin and Luczak, Artur and McKeown, Martin J.}, issn = {1662-5161}, journal = {Frontiers in Human Neuroscience}, publisher = {Frontiers Media}, title = {{Koopman-based linearization of preparatory EEG dynamics in Parkinson’s disease during galvanic vestibular stimulation}}, doi = {10.3389/fnhum.2025.1566566}, volume = {19}, 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{21143, abstract = {The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combinatorics which can be used to establish the existence of objects with certain properties. The breakthrough paper by Moser & Tardos (STOC’09 and JACM 2010) and follow-up work revealed that the LLL has intimate connections with a class of stochastic local search algorithms for finding such desirable objects. Besides conditions for convergence, many other natural questions can be asked about algorithms; for instance, “are they parallelizable?”, “how many solutions can they output?”, “what is the expected ‘weight’ of a solution?”. These questions and more have been answered for a class of LLL-inspired algorithms called commutative. In this paper we introduce a new, very natural and more general notion of commutativity (essentially matrix commutativity) which allows us to show a number of new refined properties of LLL-inspired local search algorithms with significantly simpler proofs.}, author = {Harris, David G. and Iliopoulos, Fotios and Kolmogorov, Vladimir}, issn = {1557-2862}, journal = {Theory of Computing}, number = {5}, pages = {1 -- 34}, publisher = {University of Chicago Press}, title = {{A new notion of commutativity for the algorithmic Lovász Local Lemma}}, doi = {10.4086/toc.2025.v021a005}, volume = {21}, 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}, } @unpublished{21207, abstract = {Personalized federated learning has emerged as a popular approach to training on devices holding statistically heterogeneous data, known as clients. However, most existing approaches require a client to have labeled data for training or finetuning in order to obtain their own personalized model. In this paper we address this by proposing FLowDUP, a novel method that is able to generate a personalized model using only a forward pass with unlabeled data. The generated model parameters reside in a low-dimensional subspace, enabling efficient communication and computation. FLowDUP's learning objective is theoretically motivated by our new transductive multi-task PAC-Bayesian generalization bound, that provides performance guarantees for unlabeled clients. The objective is structured in such a way that it allows both clients with labeled data and clients with only unlabeled data to contribute to the training process. To supplement our theoretical results we carry out a thorough experimental evaluation of FLowDUP, demonstrating strong empirical performance on a range of datasets with differing sorts of statistically heterogeneous clients. Through numerous ablation studies, we test the efficacy of the individual components of the method.}, author = {Zakerinia, Hossein and Scott, Jonathan A and Lampert, Christoph}, booktitle = {arXiv}, title = {{Federated learning with unlabeled clients: Personalization can happen in low dimensions}}, doi = {10.48550/ARXIV.2505.15579}, year = {2025}, } @unpublished{21211, abstract = {We show that, for any graph F and η > 0, there exists a d0 = d0(F, η) such that every nvertex d-regular graph with d ≥ d0 has a collection of vertex-disjoint F-subdivisions covering at least (1 − η)n vertices. This verifies a conjecture of Verstraëte from 2002 and improves a recent result of Letzter, Methuku and Sudakov which additionally required d to be at least polylogarithmic in n. }, author = {Montgomery, Richard and Petrova, Kalina H and Ranganathan, Arjun and Tan, Jane}, booktitle = {arXiv}, title = {{Packing subdivisions into regular graphs}}, doi = {10.48550/arXiv.2508.00480}, year = {2025}, } @article{21235, abstract = {The condensation of charged polymers is an important driver for the formation of biomolecular condensates. Recent experiments suggest that this mechanism also controls the clustering of eukaryotic chromosomes during the late stages of cell division. In this process, interchromosome attraction is driven by the condensation of cytoplasmic RNA and Ki-67, a charged intrinsically disordered protein that coats the chromosomes as a brush. Attraction between chromosomes has been shown to be specifically promoted by a localized charged patch on Ki-67, although the physical mechanism remains unclear. To elucidate this process, we combine coarse-grained simulations and analytical theory to study the RNA-mediated interaction between charged polymer brushes on the chromosome surfaces. We show that the charged patch on Ki-67 leads to interchromosome attraction via RNA bridging between the two brushes, whereby the RNA preferentially interacts with the charged patches, leading to stable, long-range forces. By contrast, if the brush is uniformly charged, bridging is basically absent due to complete adsorption of RNA onto the brush. Moreover, the RNA dynamics becomes caged in presence of the charged patch while remaining diffusive with uniform charge. Our work sheds light on the physical origin of chromosome clustering, while also suggesting a general mechanism for cells to tune work production by biomolecular condensates via different charge distributions.}, author = {Sorichetti, Valerio and Robin, Paul and Palaia, Ivan and Hernandez-Armendariz, Alberto and Cuylen-Haering, Sara and Šarić, Anđela}, issn = {2835-8279}, journal = {PRX Life}, number = {3}, publisher = {American Physical Society}, title = {{Charge distribution of the coating brush drives interchromosome attraction}}, doi = {10.1103/41fd-r847}, volume = {3}, year = {2025}, } @article{21236, abstract = {The migration behavior of colliding cells is critically determined by transient contact interactions. During these interactions, the motility machinery, including the front-rear polarization of the cell, dynamically responds to surface protein-mediated transmission of forces and biochemical signals between cells. While biomolecular details of such contact interactions are increasingly well understood, it remains unclear what biophysical interaction mechanisms govern the cell-level dynamics of colliding cells and how these mechanisms vary across cell types. Here we develop a phenomenological theory based on 14 candidate contact-interaction mechanisms coupling cell position, protrusion, and polarity. Using high-throughput micropattern experiments, we detect which of these phenomenological contact interactions captures the interaction behaviors of cells. We find that various cell types—ranging from mesenchymal to epithelial cells—are accurately captured by a single model with only two interaction mechanisms: polarity-protrusion coupling and polarity-polarity coupling. Remarkably, the qualitatively different interaction behaviors of distinct cells, as well as cells subject to molecular perturbations of surface protein-mediated signaling, can all be quantitatively captured by varying the strength and sign of the polarity-polarity coupling mechanism. Altogether, our data-driven phenomenological theory of cell-cell interactions reveals polarity-polarity coupling as a versatile and general contact-interaction mechanism, which may underlie diverse collective migration behaviors of motile cells.}, author = {Brandstätter, Tom and Brieger, Emily and Brückner, David and Ladurner, Georg and Rädler, Joachim O. and Broedersz, Chase P.}, issn = {2835-8279}, journal = {PRX Life}, number = {3}, publisher = {American Physical Society}, title = {{Data-driven theory reveals protrusion and polarity interactions governing collision behavior of distinct motile cells}}, doi = {10.1103/3hhj-rt1n}, volume = {3}, year = {2025}, }