arXiv:2510.25354v3 Announce Type: replace
Abstract: Hypergraphs provide a natural framework for modeling multiway interactions. We analyze a class of variational semi-supervised learning problems posed on random geometric hypergraphs and establish asymptotic consistency in the large-data limit. In particular, we identify scaling regimes that ensure well-posedness--yielding nontrivial label propagation rather than collapse to a constant labeling--and show that discrete minimizers converge, in the continuum, to solutions of a density-weighted p-Laplacian equation. We also propose Higher-Order Hypergraph Learning (HOHL), a multiscale regularization scheme based on powers of Laplacians associated with hypergraph-induced subgraphs. For geometric point clouds, we analyze an efficient multiscale Laplacian surrogate for HOHL and prove convergence to a higher-order Sobolev-type seminorm. Numerical experiments on standard benchmarks support the practical utility of the resulting higher-order regularization.
Science Journals
arXiv:2607.15989v1 Announce Type: new
Abstract: Understanding how cooperation persists despite the advantage of selfish behavior remains a central challenge in evolutionary dynamics. Classical models of public goods dilemmas predict dominance of defectors, yet natural and social systems often sustain cooperation. We study an eco-evolutionary public goods game on complex networks where cooperators and defectors diffuse at different rates. When the isolated system is in a defector-dominated coexistence regime, faster dispersal of defectors than cooperators leads to a symmetry-breaking transition that produces localized clusters of cooperators. In heterogeneous networks, nodes with higher connectivity become significantly more likely to exhibit cooperative dominance. A degree-based mean-field reduction supports this result by showing that network connectivity controls an effective coupling strength proportional to node degree, thereby producing a bifurcation that separates defector-dominated and cooperative states. We also address why not all hubs become cooperative by means of a multistability analysis. These results reveal how asymmetric mobility and heterogeneous connectivity jointly promote cooperation in structured populations.
arXiv:2607.15631v1 Announce Type: cross
Abstract: The primate visual system is typically divided into two streams - the ventral stream, responsible for object recognition, and the dorsal stream, responsible for encoding spatial relations and motion. Recent studies have shown that convolutional neural networks (CNNs) pretrained on object recognition tasks are remarkably effective at predicting neuronal responses in the ventral stream, shedding light on the neural mechanisms underlying object recognition. However, similar models of the dorsal stream remain underdeveloped due to the lack of large scale datasets encompassing dorsal stream areas. To address this gap, we present STSBench, a dataset of large-scale, single neuron recordings from over 2,000 neurons in the superior temporal sulcus (STS), a nearly 50-fold increase over existing dorsal stream datasets, collected while Rhesus macaques viewed thousands of unique, natural videos. We show that our dataset can be used for benchmarking encoding models of dorsal stream neuronal responses and reconstructing visual input from neural activity.
arXiv:2510.25369v3 Announce Type: replace
Abstract: Neither the classical nor intuitionistic logic traditions are perfectly aligned with the purpose of reasoning about computation, as neither can permit unconstrained recursive definitions without inconsistency: recursive definitions must normally be proven terminating before admission and use. Grounded arithmetic or GA is a formal-reasoning foundation allowing direct expression of arbitrary recursive definitions. GA adjusts traditional inference rules so that terms that express nonterminating computations harmlessly denote no semantic value ($\bot$) instead of yielding inconsistency. Recursive functions are proven terminating in GA essentially by "dynamically typing" terms, or equivalently, symbolically reverse-executing the computations they denote via inference rules. Once recursive functions have been proven terminating, logical reasoning about them reduces to familiar classical rules. We summarize the development and lessons learned from two mechanically-checked formulations of GA, finding both syntactically consistent and semantically sound with respect to an underlying computable model. Propositional grounded arithmetic or PGA is a quantifier-free system for inductive grounded reasoning about open formulas. PGA has logical expressiveness comparable to Skolem's PRA, but has general-recursive (Turing-complete) functional expressiveness. PGA builds upon a simpler system of basic grounded arithmetic or BGA, which omits logical operators entirely. BGA and PGA are not only sound but semantically complete, a combination impossible for powerful classical systems with arithmetic, due to G\"odel's incompleteness theorems. These results suggest that powerful and consistent formal reasoning with unconstrained recursive definitions is possible, potentially enabling new computation-centric formal languages, proof assistants, and type systems in the future.
arXiv:2510.26147v2 Announce Type: replace
Abstract: In this paper, we investigate the beamforming design problem in an integrated sensing and communication (ISAC) system, where a multi-antenna base station simultaneously serves multiple communication users while performing radar sensing. We formulate the problem as the minimization of the total transmit power, subject to signal-to-interference-plus-noise ratio (SINR) constraints for communication users and mean-squared-error (MSE) constraints for radar sensing. The core challenge arises from the complex coupling between communication SINR requirements and sensing performance metrics. To efficiently address this challenge, we first establish the equivalence between the original ISAC beamforming problem and its semidefinite relaxation (SDR), derive its Lagrangian dual formulation, and further reformulate it as a generalized downlink beamforming (GDB) problem with potentially indefinite weighting matrices. Compared to the classical DB problem, the presence of indefinite weighting matrices in the GDB problem introduces substantial analytical and computational challenges. Our key technical contributions include (i) a necessary and sufficient condition for the boundedness of the GDB problem, and (ii) a tailored efficient fixed point iteration (FPI) algorithm with a provable convergence guarantee for solving the GDB problem. Building upon these results, we develop a duality-based fixed point iteration (Dual-FPI) algorithm, which integrates an outer subgradient ascent loop with an inner FPI loop. Simulation results demonstrate that the proposed Dual-FPI algorithm achieves globally optimal solutions while significantly reducing computational complexity compared with existing baseline approaches.
Global Kilometer-Scale Simulations with ARP-GEM2: Effect of Parameterized Convection and Calibration
arXiv:2511.00829v2 Announce Type: replace
Abstract: The objective of this paper is twofold. First, it documents the second version of the global atmospheric model ARP-GEM and its calibration at kilometer-scale resolution. The model is currently able to run simulations at a resolution of up to 1.3 km. Second, this paper focus on multi-year global atmospheric simulations at a 2.6 km resolution with and without parameterized convection and associated calibration. Simulations without deep convection tend to be similar to those with infinite, or at least large, entrainment values. Consistently, entrainment and detrainment are used as primary drivers for the gradual reduction of convection as resolution increases. The results indicate that, with this hydrostatic model, parameterized convection still plays a significant role in the correct representation of the mean state at the kilometer scale. Additionally, they suggest some added value of high resolution in representing climate variability. However, a compromise between the adequate representation of the mean state and variability is necessary, as both are differently favored by the degree of parameterized convection. Finally, it is likely that even higher resolutions are necessary to achieve an unequivocal added value.
arXiv:2511.08208v2 Announce Type: replace
Abstract: In this article, we study word equations in free semigroups and the conjecture that the existence of infinitely many solutions entails the existence of solutions with arbitrarily large exponent of periodicity. We examine this question in the broader framework of word equations with regular constraints and establish new positive results: the conjecture holds for all quadratic word equations with constraints in finite semigroups from the variety $\mathbf{DLG}$ and its left-right dual $\mathbf{DRG}$, encompassing, in particular, all finite groups, commutative semigroups, and $\mathcal{J}$-trivial semigroups.
arXiv:2511.12974v3 Announce Type: replace
Abstract: We introduce Controlled Stochastic Activity Networks (Controlled SANs), a formal extension of classical Stochastic Activity Networks that integrates explicit control actions into a unified semantic framework for modeling distributed real-time systems. Controlled SANs systematically capture dynamic behavior involving nondeterminism, probabilistic branching, and stochastic timing, while enabling policy-driven decision-making within a rigorous mathematical framework.
We develop a hierarchical, automata-theoretic semantics for Controlled SANs that encompasses nondeterministic, probabilistic, and stochastic models in a uniform manner. A structured taxonomy of control policies, ranging from memoryless and finite-memory strategies to computationally augmented policies, is formalized, and their expressive power is characterized through associated language classes. To support model abstraction and compositional reasoning, we introduce behavioral equivalences, including bisimulation and stochastic isomorphism.
Controlled SANs generalize classical frameworks such as continuous-time Markov decision processes (CTMDPs), providing a rigorous foundation for the specification, verification, and synthesis of dependable systems operating under uncertainty. This framework enables both quantitative and qualitative analysis, advancing the design of safety-critical systems where control, timing, and stochasticity are tightly coupled.
arXiv:2511.14159v4 Announce Type: replace
Abstract: Evaluating the robustness of Large Vision-Language Models (LVLMs) is essential for their continued development and responsible deployment in real-world applications. However, existing robustness benchmarks typically focus on hallucination or misleading textual inputs, while largely overlooking the equally critical challenge posed by misleading visual inputs in assessing visual understanding. To fill this important gap, we introduce MVI-Bench, the first comprehensive benchmark specially designed for evaluating how Misleading Visual Inputs undermine the robustness of LVLMs. Grounded in fundamental visual primitives, the design of MVI-Bench centers on three hierarchical levels of misleading visual inputs: Visual Concept, Visual Attribute, and Visual Relationship. Using this taxonomy, we curate six representative categories and compile 1,248 expertly annotated VQA instances. To facilitate fine-grained robustness evaluation, we further introduce MVI-Sensitivity, a novel metric that characterizes LVLM robustness at a granular level. Empirical results across 18 state-of-the-art LVLMs uncover pronounced vulnerabilities to misleading visual inputs, and our in-depth analyses on MVI-Bench provide actionable insights that can guide the development of more reliable and robust LVLMs. The benchmark and codebase can be accessed at https://github.com/chenyil6/MVI-Bench.
arXiv:2511.15927v4 Announce Type: replace
Abstract: Diffusion language models (DLMs) have emerged as a promising alternative to autoregressive (AR) generation, yet their reliance on Transformer backbones limits inference efficiency due to quadratic attention or KV-cache overhead. We introduce DiffuMamba, a masked diffusion language model built on a bidirectional Mamba backbone that combines the diffusion objective with linear-time sequence modeling, and DiffuMamba-H, a hybrid variant with interleaved attention. Across scales up to 1.3B parameters, our models match Transformer-based diffusion in downstream performance while achieving up to 8.2x and 4.3x higher inference throughput, respectively, on long sequences. We further present a systematic analysis of inference efficiency across modern DLM variants combining asymptotic complexity with empirical measurements. Notably, cache-efficient block diffusion with Mamba mixers emerges as the only strategy that scales linearly with sequence length and achieves the strongest performance across all baselines, suggesting a promising direction for future diffusion-based generation systems.
arXiv:2511.16235v3 Announce Type: replace
Abstract: The describing function (DF) and phase response curve (PRC) are classical tools for the analysis of feedback oscillations and rhythmic behaviors, widely used across control engineering, biology, and neuroscience. These tools are known to have limitations in networks of relaxation oscillators and excitable systems. For this reason, the paper proposes a novel approach tailored to excitable systems. Our analysis focuses on the discrete-event operator mapping input trains of events to output trains of events. The methodology is illustrated on the excitability model of Hodgkin-Huxley. The proposed framework provides a basis for designing and analyzing central pattern generators in networks of excitable neurons, with direct relevance to neuromorphic control and neurophysiology.
arXiv:2511.18468v2 Announce Type: replace
Abstract: Continual Test-Time Adaptation (CTTA) is crucial for deploying models in real-world applications with unseen, evolving target domains. Existing CTTA methods, however, often rely on source data or prototypes, limiting their applicability in privacy-sensitive and resource-constrained settings. Although several methods attempt to mitigate catastrophic forgetting, they often fail to preserve long-term domain-specific knowledge across many domain shifts. Moreover, their relatively slow adaptation rates during domain transitions can cause error accumulation, allowing mistakes to propagate before effective adaptation occurs. To address these challenges, we propose SloMo-Fast, a source-free, dual-teacher CTTA framework designed for enhanced quick adaptability and generalization. It includes two complementary teachers: the Slow-Teacher, which exhibits slow forgetting and retains long-term knowledge of previously encountered domains to ensure robust generalization, and the Fast-Teacher rapidly adapts to new domains while accumulating and integrating knowledge across them. This framework preserves knowledge of past domains and adapts efficiently to new ones. Our extensive experiments show that SloMo-Fast consistently outperforms state-of-the-art methods across Cyclic Test-Time Adaptation (Cyclic-TTA), a CTTA benchmark that simulates recurring domain shifts, along with ten other CTTA settings, highlighting its ability to both adapt and generalize across evolving, revisited domains.
arXiv:2511.20332v3 Announce Type: replace
Abstract: This article trained a network for perceiving three-dimensional motion information of binocular vision target, which can provide real-time three-dimensional coordinate, velocity, and acceleration, and has a basic spatiotemporal perception capability. Understood the ability of neural networks to fit nonlinear problems from the perspective of PID. Considered a single-layer neural network as using a second-order difference equation and a nonlinearity to describe a local problem. Multilayer networks gradually transform the raw representation to the desired representation through multiple such combinations. Analysed some reference principles for designing neural networks. Designed a relatively small PID convolutional neural network, with a total of 17 layers and 413 thousand parameters. Implemented a simple but practical feature reuse method by concatenation and pooling. The network was trained and tested using the simulated randomly moving ball datasets, and the experimental results showed that the prediction accuracy was close to the upper limit that the input image resolution can represent. Analysed the experimental results and errors, as well as the existing shortcomings and possible directions for improvement. Finally, discussed the advantages of high-dimensional convolution in improving computational efficiency and feature space utilization. As well as the potential advantages of using PID information to implement memory and attention mechanisms.
arXiv:2511.20687v4 Announce Type: replace
Abstract: This paper presents a novel hybrid approach for coupling subdomain-local non-intrusive Operator Inference (OpInf) reduced order models (ROMs) with each other and with subdomain-local high-fidelity full order models (FOMs) with using the overlapping Schwarz alternating method (O-SAM). The proposed methodology addresses significant challenges in multiscale modeling and simulation, particularly the long runtime and complex mesh generation requirements associated with traditional high-fidelity simulations. By leveraging the flexibility of O-SAM, we enable the seamless integration of disparate models, meshes, and time integration schemes, enhancing computational efficiency while maintaining high accuracy. Our approach is demonstrated through a series of numerical experiments on complex three-dimensional (3D) solid dynamics problems, showcasing speedups of up to 106x compared to conventional FOM-FOM couplings. This work paves the way for more efficient simulation workflows in engineering applications, with potential extensions to a wide range of partial differential equations.
arXiv:2511.23213v3 Announce Type: replace
Abstract: Targeted execution of Android applications (apps) remains a longstanding challenge for software testing and analysis. Although recent advances in GUI testing have substantially improved app exploration, existing approaches remain largely coverage-driven and struggle to steer execution reliably toward specific methods of interest. This limitation hinders important downstream tasks, such as vulnerability detection, program comprehension, and dynamic analysis.
We present GAPS (Graph-based Automated Path Synthesizer), the first approach to bridge static program analysis and dynamic GUI exploration, enabling targeted execution in Android apps. Given a target method, GAPS performs a lightweight static backward traversal of the call graph, enriched with data-flow reasoning, to identify feasible execution paths that lead to the target. It then translates these paths into actionable execution strategies that guide dynamic interactions with the app.
We evaluate GAPS on the AndroTest benchmark and show that it reconstructs paths toward 88.24% of the target methods, requiring only 12.67 seconds per app on average. During dynamic execution, GAPS reaches 56.93% of the target methods, outperforming state-of-the-art alternatives. In comparison, the model-based GUI testing tool APE reaches only 11.12%, the hybrid exploration framework GoalExplorer reaches 4.75%, and the recent LLM-driven approach Guardian reaches 34%. To assess scalability in real-world settings, we further evaluate GAPS across the 50 most-downloaded apps on the Google Play Store. GAPS reconstructs execution paths toward 62.03% of the target methods, averaging 278.9 seconds per app, and dynamically reaches 54.80% of them. These results show that combining static path synthesis with guided dynamic exploration provides an effective and scalable solution for targeted method execution in Android apps.
arXiv:2512.00319v3 Announce Type: replace
Abstract: The Structure Gap between probabilistic LLM generation and deterministic schema requirements hinders automated workflows. We propose RL-Struct, a lightweight framework using Gradient Regularized Policy Optimization (GRPO) with a hierarchical reward function to align LLMs with structural constraints. This approach eliminates the critic network, reducing peak VRAM by 38% compared to PPO. On complex JSON tasks, RL-Struct achieves 89.7% structural accuracy and 92.1% validity, significantly outperforming SFT and zero-shot baselines. We also report an emergent curriculum--a self-organized learning process where the model prioritizes syntax before semantics. Our model is publicly available at https://huggingface.co/Freakz3z/Qwen-JSON.
arXiv:2512.02384v3 Announce Type: replace
Abstract: Markov chain Monte Carlo algorithms have long been observed to obtain near-optimal performance in various Bayesian inference settings. However, developing a supporting theory that makes these studies rigorous has proved challenging.
In this paper, we study the classical spiked Wigner inference problem, where one aims to recover a planted Boolean spike from a noisy matrix measurement. We relate the recovery performance of Glauber dynamics on the annealed posterior to the performance of Approximate Message Passing (AMP), which is known to achieve Bayes-optimal performance. Our main results rely on the analysis of an auxiliary Markov chain called restricted Gaussian dynamics (RGD). Concretely, we establish the following results:
1. RGD can be reduced to an effective one-dimensional recursion which mirrors the evolution of the AMP iterates.
2. From a warm start, RGD rapidly converges to a fixed point in correlation space, which recovers Bayes-optimal performance when run on the posterior.
3. Conditioned on widely believed mixing results for the SK model, we recover the phase transition for non-trivial inference.
arXiv:2512.02851v4 Announce Type: replace
Abstract: Visual traversability estimation is central to autonomous navigation, yet most approaches either rely on prompt-driven Vision-Language Model (VLM) or decouple traversability from trajectory planning, requiring separate planners with heavy mapping, manual tuning, and extended deployment time. We propose EmbodiedDiffusion, a diffusion-based framework that simultaneously predicts traversability maps and generates feasible trajectories from RGB images using planner-free synthetic supervision and embodiment conditioning for cross-platform transfer. The framework distills category-level traversability semantics from a VLM teacher into a lightweight student model during training, enabling prompt-free, real-time inference at deployment. A modular FiLM-based conditioning mechanism isolates embodiment-specific reasoning into a compact trainable subset of the network, allowing rapid adaptation to new robot platforms without retraining the visual backbone or the trajectory diffusion model. Across indoor environments with quadruped and aerial robots, EmbodiedDiffusion achieves 80-100% navigation success in the full-data regime with real-time inference (90 ms) and adapts to new platforms using only 10 min of visual data collection, demonstrating scalable, unified traversability reasoning and trajectory generation for heterogeneous robots.
arXiv:2512.03054v3 Announce Type: replace
Abstract: Federated Learning (FL) holds the potential to advance equality in health by enabling diverse institutions to collaboratively train deep learning (DL) models, even with limited data. However, the significant resource requirements of FL often exclude centres with limited computational infrastructure, further widening existing healthcare disparities. To address this issue, we propose a Green AI-oriented adaptive layer-freezing strategy designed to reduce energy consumption and computational load while maintaining model performance. We tested our approach using different federated architectures for Magnetic Resonance Imaging (MRI)-to-Computed Tomography (CT) conversion. The proposed adaptive strategy optimises the federated training by selectively freezing the encoder weights based on the monitored relative difference of the encoder weights from round to round. A patience-based mechanism ensures that freezing only occurs when updates remain consistently minimal. The energy consumption and CO2eq emissions of the federation were tracked using the CodeCarbon library. Compared to equivalent non-frozen counterparts, our approach reduced training time, total energy consumption and CO2eq emissions by up to 23%. At the same time, the MRI-to-CT conversion performance was maintained, with only small variations in the Mean Absolute Error (MAE). Notably, for three out of the five evaluated architectures, no statistically significant differences were observed, while two architectures exhibited statistically significant improvements. Our work aligns with a research paradigm that promotes DL-based frameworks meeting clinical requirements while ensuring climatic, social, and economic sustainability. It lays the groundwork for novel FL evaluation frameworks, advancing privacy, equity and, more broadly, justice in AI-driven healthcare.
arXiv:2512.03594v2 Announce Type: replace
Abstract: Detailed routing remains one of the most complex and time-consuming steps in modern physical design due to the challenges posed by shrinking feature sizes and stricter design rules. Prior detailed routers achieve state-of-the-art results by leveraging iterative pathfinding algorithms to route each net. However, runtimes are a major issue in detailed routers, as converging to a solution with zero design rule violations (DRVs) can be prohibitively expensive.
In this paper, we propose leveraging reinforcement learning (RL) to enable rapid convergence in detailed routing by learning from previous designs. We make the key observation that prior detailed routers statically schedule the cost weights used in their routing algorithms, meaning they do not change in response to the design or technology. By training a conservative Q-learning (CQL) model to dynamically select the routing cost weights which minimize the number of algorithm iterations, we find that our work completes the ISPD19 benchmarks with 1.56x average and up to 3.01x faster runtime than the baseline router while maintaining or improving the DRV count in all cases. We also find that this learning shows signs of generalization across technologies, meaning that learning designs in one technology can translate to improved outcomes in other technologies.
arXiv:2512.03829v2 Announce Type: replace
Abstract: Reliable operation of high-power proton cyclotrons is a critical requirement for Accelerator Driven Systems (ADS) and other large-scale applications. Beam tuning in such machines is traditionally performed manually, a process that can be slow, non-optimal, and difficult to execute in the presence of faults or changing conditions. To address this, we developed and deployed a machine learning (ML) based tuning framework on the Injector 2 cyclotron at PSI, chosen as an ideal testbed for high-power operation. The system combined a tailored reinforcement learning (RL) algorithm with real-time diagnostics and control, and incorporated accelerator-physics inspired adaptations such as an overshoot strategy that reduced magnetic field settling times by nearly a factor of six. Over an extensive 12-day operational test campaign, relatively long in the context of real-time ML experiments, the RL agent successfully tuned the machine across multiple operating points. For each investigated configuration, stable policies were obtained within a few hours of online training and subsequently demonstrated reliable low-loss operation during overnight evaluation runs. Crucially, the learned policy remained effective when transferred from low-current training to operation at beam currents up to 800 {\mu}A, demonstrating robust generalization under appropriately adapted operational constraints. These results constitute the first demonstration of RL-assisted tuning on a high-power cyclotron, with direct relevance to ADS-class drivers.
arXiv:2512.05673v2 Announce Type: replace
Abstract: Residual minimization in dual norms is central to Weak Adversarial Neural Network (WAN) approaches for solving partial differential equations (PDEs). This framework naturally leads to saddle-point problems whose numerical solutions can be highly unstable depending on the underlying iterative scheme. Motivated by this structure, we propose and analyze the Uzawa Double Deep Ritz Method, a deep PDE solver that integrates neural network approximations with the classical Uzawa iteration. The proposed method is built around two coupled update rules performed at each iteration: a residual update, obtained by minimizing a Ritz functional associated with the dual problem, and a solution update, obtained by minimizing a Ritz functional driven by the current residual. Both variables are represented by neural networks, mirroring the classical Uzawa architecture for saddle-point problems. By replacing the adversarial min-max optimization of WAN with a sequence of Deep Ritz minimization problems, our study theoretically proves that the proposed method acts as an iterative scheme for solving the WAN formulation. Furthermore, we establish a comprehensive convergence theory for an inexact Uzawa scheme where both subproblems are solved approximately. This analysis extends to practical gradient-based implementations, providing rigorous stability and convergence guarantees for both single and multiple-gradient step update strategies. Numerical experiments validate our theoretical findings and demonstrate the robustness of the proposed approach.
arXiv:2512.07588v3 Announce Type: replace
Abstract: Analysing learning in Multi-Agent Reinforcement Learning (MARL) environments is challenging, in particular with respect to \textit{individual} decision-making. Practitioners frequently struggle to compare training runs due to the inherent stochasticity in algorithms arising from random dithering exploration, environment transition noise, and stochastic gradient updates to name a few. Traditional analytical approaches, such as replicator dynamics, oft rely on mean-field approximations to remove stochastic effects, but this simplification, whilst able to provide general overall trends, can lead to dissonance between analytical predictions and actual agent realisations. We propose modelling MARL training as a \textit{coupled stochastic dynamical systems}, capturing both agent interactions and environmental characteristics. Leveraging tools from dynamical systems theory, we pragmatically analyse the stability and sensitivity of agent behaviour, which are key dimensions for their practical deployments, for example, in presence of strict safety requirements. This framework allows us to rigorously study the inherent stochasticity of MARL, providing a deeper understanding of system behaviour.
arXiv:2607.15876v1 Announce Type: new
Abstract: We present a new ML-like programming language Yarrow with algebraic effects and region-based memory management. Reconciling these programming language features into one language is challenging: the non-local control flow of algebraic effects break the stack discipline of function calls and returns that region-based memory management relies on, and multi-shot effect handlers break the invariant that regions can be exited at most once. We present a program logic, called Yarrow Logic (YL), that supports safe and modular reasoning about regions in the presence of one-shot and multi-shot effect handlers. We prove the logic sound w.r.t. the operational semantics of Yarrow which is inspired by the runtime of OCaml but refined for regions. We use YL to prove correctness of a number of case studies with algebraic effects, including checkpointing, asynchronous computation and a LIFO data structure implementation. Since all memory locations used in these case studies are allocated in regions, these case studies avoid using the less efficient garbage collected heap memory. We have formalized Yarrow's operational semantics, the Yarrow program logic, and all our case studies using the Iris separation logic framework on top of the Rocq Prover.
arXiv:2607.16037v1 Announce Type: new
Abstract: For an explicitly represented finite empirical model, deciding whether the contextual fraction is strictly below one is NP-complete, while the standard exact linear program has one column for every global assignment. We identify a permutation-transport class in which this global problem collapses to a fixed-point calculation. Let a connected permutation gain graph act on a finite state set $O$, let $H \leq{ \rm Sym}(O)$ be its holonomy subgroup, let $F = {\rm Fix}(H)$, and let $p$ be an $H$-invariant root distribution. For the induced empirical model, \[ {\rm NCF}(e)=p(F),\qquad {\rm CF}(e)=1-p(F). \] Consequently, compatibility, $F$, and ${\rm CF}(e)$ are computable in $O(|O|(|V|+|E|))$ arithmetic and table operations. For every finite simple $2$-edge-connected graph, any deterministic exact algorithm in the explicit permutation-table query model requires at least $(|O|-1)|E|$ probes in the worst case, making the dependence on the input tables optimal up to constant factors. With a fixed spanning tree, chord insertions and deletions require $O(|O|)$ worst-case time, or time proportional to the moved-set representation, while compatibility and contextual-fraction queries take $O(1)$ time. Finally, for common-marginal realizable binary constraint languages, the support threshold ${\rm CF} < 1$ is polynomial-time equivalent to the associated finite-domain constraint-satisfaction problem and therefore inherits the Bulatov--Zhuk dichotomy. The results identify a query-optimal and dynamically maintainable tractability island inside the general contextual-fraction problem.