Science & Mathematics

We give a strongly polynomial time algorithm for submodular function minimization with overall running time $\widetilde{O}(n^{2}\mathsf{EO}+n^{3})$ time, where $\mathsf{EO}$ is the running time of a single evaluation of the function. Our algorithm improves upon the previously fastest strongly polynomial algorithms of Lee et al. (FOCS 2015), Dadush et al. (SODA 2018), and Jiang et al. (SODA 2024) that run in time $\widetilde{O}(n^{3}\mathsf{EO}+n^{4})$. Similarly to prior works, our work combines a cutting plane algorithm with the combinatorial arc-finding framework of Fleischer et al. (JACM 2001). We achieve our faster running time by developing an algorithm that runs the cutting plane method end to end, without restarting after discovering arcs and contracting strongly connected components.

Multi-turn image editing aims to modify an image according to a sequence of instructions, enabling more effective interactive visual content creation for users. However, existing methods often exhibit noticeable drift after only a few editing turns, manifesting in two aspects: 1) unstable visual quality, with accumulating artifacts and degraded details; and 2) inconsistent image content, with unintended changes to preserved regions and prior edits. To address these challenges, we propose MT Forcing, a novel training paradigm for multi-turn image editing with unified multimodal models (UMMs) based on autoregressive diffusion. Specifically, we propose Single-Turn Distribution Matching Distillation (Single-Turn DMD), which supervises student self-rollouts with a teacher that applies cumulative edits to the source image in a single turn, providing visual-quality guidance without recursive error accumulation. Additionally, we introduce Teacher-Forcing Guidance, which supervises history-dependent transitions on reference trajectories during warmup and as a regularizer during distillation, encouraging cross-turn content consistency beyond what per-turn distribution matching alone can ensure. Extensive experiments demonstrate that our approach significantly improves the multi-turn image editing capabilities of UMMs, yielding more stable visual quality and stronger cross-turn consistency.

Onboard inference latency creates a mismatch between the trajectories predicted by vision-language-action (VLA) policies and the ongoing motion of unmanned aerial vehicles (UAVs). We present AeroDASH, an asynchronous VLA framework for continuous language-conditioned flight. A B-spline policy is initialized through supervised fine-tuning on expert demonstrations, providing continuous trajectory references in position and yaw. During execution, trajectory fusion removes the expired prediction prefix and connects the remaining segment to the active reference with derivative continuity while limiting trajectory deformation. To account for deviations induced by asynchronous execution, execution-aware group relative policy optimization (GRPO) further adapts the policy using trajectory-level rewards. On the UAV-Flow test set, AeroDASH achieves a success rate of 76.56%, exceeding OpenVLA-UAV and AeroDASH w/o GRPO by 38.1 and 20.1 percentage points, respectively. Execution experiments show that AeroDASH sustains motion during inference and reduces acceleration, jerk, and speed fluctuations relative to asynchronous tracking of waypoint sequences. We further demonstrate language-conditioned flight with onboard inference and asynchronous trajectory execution. The code will be released upon acceptance.

Figurative language remains a major challenge for Machine Translation (MT) systems, as the intended meaning of such expressions often goes beyond literal translation. Although recent advances in Large Language Models (LLMs) improved the translation of Arabic dialects, benchmark resources for evaluating figurative language translation in Moroccan Darija remain scarce. To this end, we introduce the Moroccan Darija Figurative Language Corpus (MDFC), a benchmark dataset for MT and multiple-choice question (MCQ) selection covering idioms, metaphors, and proverbs. Using MDFC, we evaluate 19 open- and closed-weight language models and MT systems at both the expression and contextual levels under zero-shot and six-shot settings. We also conduct layer-wise similarity-based probing to determine how model representations distinguish figurative from literal meanings. Our findings reveal that closed-weight models achieve the strongest translation performance, while the benefits of contextual information vary across models and tasks. Differences between translation performance and MCQ accuracy highlight the distinction between generating an appropriate figurative translation and recognizing the intended meaning among candidate translations.

Dexterous grasping in cluttered scenes remains a central challenge in robotic manipulation, as it requires high-dimensional hand coordination under complex object-environment constraints. To address this problem, we introduce one of the largest simulation benchmarks to date, comprising around 0.5B grasp annotations across eight dexterous hands and approximately 50K objects. Furthermore, we propose T(R,O) Grasp++, a scalable diffusion-based framework for cross-embodiment dexterous grasp synthesis in cluttered environments. Extensive experiments demonstrate that our model significantly outperforms existing baselines, achieving an average success rate of 88% across eight dexterous embodiments. Meanwhile, our pipeline achieves only 0.3s inference latency while improving inference sample efficiency by over 10 times.

Modern maritime navigation depends on mandatory wireless inputs, most notably GNSS and AIS, whose reception can be spoofed or jammed. When groundings or collisions occur, liability and safety investigations often turn on whether RF interference corrupted bridge instruments, yet the artifacts typically available (VDR outputs, IBS logs, screenshots, decoded messages) are downstream, lossy, and easy to contest in adversarial proceedings. We introduce a forensically sound acquisition methodology that preserves upstream wireless evidence together with the minimal contemporaneous context needed to interpret it. Our system records coherent, multichannel IQ across relevant bands while simultaneously collecting time-aligned receiver and instrument-state metadata (e.g., decoded AIS/GNSS outputs and NMEA sentences), enabling later re-decoding and physical-layer reanalysis tied to what the onboard stack indicated at the time. To make the record independently auditable, we package samples and metadata into a single append-only forensic envelope that cryptographically binds per-stream hash chains with trusted-time anchors and periodic checkpoints, allowing third parties to detect tampering (modification, truncation, splicing, cross-case substitution) and to verify the claimed recording window. A prototype implementation shows the approach is practical: integrity mechanisms add negligible storage overhead and modest compute cost at operationally relevant multiband capture rates.

Scientific document embeddings such as SPECTER2 are optimized for retrieval over large, heterogeneous corpora. On a small specialized corpus their similarity distributions can become highly compressed, which limits their usefulness for exploratory literature mapping. We study whether weakly supervised in-domain adaptation, using only metadata already available in open citation databases, changes this geometry. On ArtCon, a curated corpus of 704 publications on artificial and machine consciousness, we adapt the SPECTER2 proximity model with a lightweight LoRA adapter trained on positive pairs derived from bibliographic coupling in OpenAlex, using no manually annotated similarity labels. We compare the adapted embeddings with lexical (TF-IDF), citation-based (bibliographic coupling) and generic semantic (SPECTER2) representations under thresholded, fixed-density and symmetric k-nearest-neighbour graph constructions. Adaptation substantially decompresses the similarity distribution (mean pairwise cosine similarity 0.9104 to 0.8663, standard deviation 0.0259 to 0.0594) and yields graphs with markedly higher Louvain modularity and better connectivity than the base encoder under matched edge and neighbourhood budgets. The effect is stable across all three graph constructions and is therefore not an artefact of a single sparsification choice. We report this as a case study on one corpus, and we are explicit about what it does not establish: the clustering indices used here are computed against community labels derived from each representation's own similarity graph, so they measure internal geometric self-consistency rather than agreement with an external topical ground truth, and adaptation and evaluation use the same documents. Evaluation against independent labels, on held-out documents, and against geometric controls is ongoing work.

World models offer increasingly rich environments for exploration, yet intervening in a world while observing the consequences from freely chosen viewpoints remains challenging. We tackle these challenges by introducing UniState, a framework for controllable world simulation built on a unified world-state representation. This representation unifies spatial memory and user interventions. Users specify object motion directly within spatial memory, while independently choosing the camera trajectory from which the resulting world state is observed. This unification makes the relationship between the scene and the requested changes explicit, removing ambiguity between object motion and viewpoint change from the control specification. Crucially, specifying an intervention does not require prescribing every resulting movement: the video model can synthesize additional motion within controlled objects and plausible interactions with their surroundings. We develop training and sampling strategies that help generated videos follow the specified object motion and camera trajectory while preserving this capacity to generate responses beyond the prescribed transformations. Experiments demonstrate more accurate joint object and camera control than the existing methods, alongside qualitative evidence that intervention-induced scene changes persist across rollouts.

Multimodal Large Language Models (MLLMs) face significant scalability challenges in long-video understanding due to quadratic attention complexity and context window constraints. Existing retrieval-based approaches typically rely on supervised learning from static keyframe annotations. However, these label priors often fail to align with the actual information required by downstream MLLMs for complex reasoning, creating a misalignment between the training target and inference needs. To bridge this gap, we propose a probabilistic framework that reformulates frame selection as latent-variable inference. We first initialize a lightweight policy using supervised learning to capture general visual saliency. Then, we treat a frozen MLLM as a task environment and use its answer likelihood as dense task evidence to refine the policy via Bayesian Group Relative Policy Optimization (GRPO). Within this formulation, the negative log-likelihood (NLL) over ground-truth answer tokens provides a principled dense reward, while a prior-matching KL term preserves semantic consistency with the elicited label prior. This process transitions the selection principle from static label priors to task evidence. Extensive experiments on Video-MME, MLVU, and LongVideoBench demonstrate that our selector achieves competitive accuracy with MLLM-based scorers while retaining the inference efficiency of lightweight methods. The selector is trained once with a frozen MLLM environment and transfers directly to multiple downstream MLLMs without retraining. Code is available at \url{github.com/Miraclecsc/Frame_Selection_GRPO}.

Pedestrians differ in whether they respond to a robot, yet many RL policies assume all are non-reactive to prioritize safety. Policies trained without conditioning on local pedestrians' reactivity may therefore be unnecessarily conservative or rely on cooperation that does not occur. We propose RCRA, an online adaptation framework that modulates a learned residual around a frozen conservative navigation policy according to estimated pedestrian reactivity. A Transformer-based estimator infers latent pedestrian reactivity from motion histories and robot context, providing a more accurate signal for navigation adaptation and improving scenario-averaged simulation accuracy by $12.62$ percentage points over the Bayesian baseline, which assumes known pedestrian goals. These estimates are spatially aggregated into an adaptation scale that gates LoRA modules, enabling cooperative behavior near reactive pedestrians and conservative behavior near non-reactive pedestrians. Among baselines achieving SR above $90\%$ in every scenario, RCRA reduces scenario-averaged path length by $16.7\%$ relative to the conservative backbone and by $7.3\%$ relative to randomized-training baselines. It improves mean SR by $14.88$ percentage points over the reactive-trained policy.

Autonomous cyber-defense agents trained using reinforcement learning (RL) are increasingly adopted for defending enterprise computer networks. However, existing approaches may become brittle as attacker capabilities evolve and enable new attack strategies. In this work, we study the problem of adapting defender policies learned in CAGE Challenge Scenario 2 (CC2), a benchmark enterprise network defense scenario, to an extended network scenario with new attacker capabilities represented by new attacker actions. Effective attack strategies that leverage new actions are initially unknown, and therefore attacker policies must be learned before defender adaptation can occur. To address this challenge, we develop adversarial RL (ARL) with behavior trees (ARLBT), which uses reward behavior trees (RBTs) to define progression-based reward functions and condition attacker policies on RBT execution. The proposed RBT incorporates the new attacker actions into structured attack strategies while leveraging parallel execution to generate rewards across multiple network nodes simultaneously. We evaluate ARLBT for learning attacker policies against two baseline defender policies across network scenarios with different sets of new attacker actions and compare against multiple attacker baselines. The results demonstrate that ARLBT improves attacker success compared to ARL using the original CC2 reward function and that conditioning policies on RBT execution can improve sample efficiency. We further show that defender policies can be adapted against the learned attackers, improving robustness to attacks that leverage new attacker actions.

Neural simulation is an essential methodology for studying biological nervous systems, but it remains limited by the computational costs of repeatedly updating neural and synaptic states over many timesteps. Neuromorphic hardware is a promising substrate for this class of workloads because such devices combine event-driven execution, localized memory, and spike-based communication. However, neuromorphic \textit{software} remains comparatively fragmented and difficult to integrate with the model-description standards used by the computational neuroscience community. This disconnect limits reproducible experimentation and makes direct comparison between conventional and neuromorphic simulation workflows difficult. This paper introduces ``NeuroML2Loihi'', an open-source framework for translating NeuroML model descriptions into Loihi~2-deployable Lava primitives, enabling standardized biological models to be executed on Intel's Loihi~2 neuromorphic chip. We evaluate our framework using c302-derived \textit{C. elegans} neural models across three connectome-scale configurations. Cross-platform similarity is assessed using spike-train and voltage-trace metrics, while latency, power, and energy consumption are benchmarked against the conventional reference workflow. Across the evaluated models, Loihi~2 execution enabled through NeuroML2Loihi achieves 514--1211$\times$ lower latency and a 1.8--1.9$\times$ reduction in mean wattage relative to the NEURON reference, producing substantially lower total energy consumption primarily through reduced execution time. These results demonstrate that standards-based neuromorphic neural simulation is feasible on Loihi~2 and can support meaningful comparison against established computational neuroscience workflows.

Large language models store substantial factual knowledge in their parameters, yet this knowledge is difficult to control, update, and reliably elicit at inference time. Existing memory-augmented approaches typically rely on a single auxiliary mechanism, such as retrieval, parameter updates, or neural memory, and therefore apply the same form of correction to tokens with very different knowledge demands. We propose Mixture-of-Memories (MoM), a memory-augmented language modeling framework that separates routed neural memory from writable factual memory. MoM combines a frozen base LM with two neural memory experts: a latent memory that provides low-latency hidden-state corrections and a lexical memory that provides a token-space knowledge pathway. A lightweight Budget Router sets per-token mixture weights from uncertainty and disagreement features, replacing the fixed interpolation of prior memory modules. For post-hoc updates, an external explicit memory stays outside the router, because a router trained before facts are written learns to down-weight it; new facts are appended without retraining any component and used only when an answer-level gate accepts the retrieved fact. Experiments across language modeling, factual QA, update analysis, and efficiency show that MoM improves both predictive accuracy and updateability while retaining low inference overhead.

The assessment of surgical skills in robotic surgery training has traditionally relied on subjective evaluations by human experts, creating bottlenecks in surgical education and limiting scalability. We present a novel foundation model that automatically analyzes robotic surgical videos to provide comprehensive skill assessment and gesture understanding. Combining a visual encoder with a transformer architecture, the model performs three key tasks simultaneously: 1) surgical task classification (knot tying, needle passing, suturing), 2) skill level assessment on a standardized scale, and 3) natural language generation of surgical gesture descriptions. The model processes video sequences from the da Vinci surgical robot and generates human-readable text descriptions of surgical actions, similar to how language models generate text from prompts, using a multi-task learning framework with adaptive uncertainty weighting to optimize performance across all objectives. Our transformer-based architecture incorporates positional encoding for temporal understanding and attention mechanisms for spatiotemporal feature integration. Evaluated on the da Vinci Skills Simulator dataset, the proposed framework demonstrates state-of-the-art performance in surgical task recognition and provides interpretable skill assessments that correlate with expert evaluations, with the model's ability to generate natural language descriptions of surgical gestures opening new possibilities for automated surgical education, real-time feedback systems, and objective skill assessment in surgical training and certification programs.

Cross-modal alignment of synthetic aperture radar (SAR) imagery to natural language is constrained by two distinct failures. The first is modality mismatch: text encoders pre-trained on optical imagery, such as CLIP, cannot be efficiently fine-tuned on SAR, because active microwave backscatter is physically incompatible with passive optical reflectance and the available SAR caption datasets are orders of magnitude too small to bridge this gap without substantially degrading the learned semantic manifold. The second is physical forgetting: SAR encoders pre-trained on large-scale self-supervised objectives encode radar physics that are progressively erased when the encoder is fine-tuned for text alignment on limited caption data. A single design principle addresses both failures: keep both encoders frozen and learn only a constrained, structure-preserving bridge. Our Frozen Expert framework aligns a frozen CROMA SAR encoder with a frozen CLIP text encoder via a lightweight constrained residual bridge. We formally define physical forgetting via Procrustes disparity and show our bridge preserves SAR geometry significantly better than fine-tuning (disparity: 0.210 vs. 0.351). We validate generality across multiple SAR backbones and text encoders. On zero-shot SAR scene classification, our approach outperforms fine-tuned baselines using up to 8x less training data: DFC2020 (+10.3% R@1, +15.5% mAP), EuroSAT-SAR (+15.7% R@1, +12.2% mAP), BigEarthNet-MM (+14.7% R@1). These results establish frozen manifold alignment as a principled, data-efficient alternative to fine-tuning in high-disparity cross-modal settings.