Computational Complexity
$\ell_p$-Norm Maximization over Zonotopes Is W[1]-Hard
Yang Cao, Haoran Qi and Hanzhi Wang
We study $\ell_p$-norm maximization over zonotopes given by rational generators, with input length $L$. For fixed $p=a/b>1$, the exact Turing baseline runs in $n^{O(d)}b^{O(d)}\mathrm{poly}(L)$ time, but fixed-parameter tractability in the ambient dimension $d$ was open [FGHS25]. We prove W[1]-hardness and, under the Exponential Time Hypothesis (ETH), exclude $\rho_p(d)L^{o(d)}$ time, even for $5$-sparse generators, by encoding binary CSP constraints with normalized positive cap generators. We also give a deterministic $(1-\varepsilon)$-approximation with $\varepsilon^{-(d-1)/2}$ dependence and, among
algorithms with fixed-degree
polynomial dependence on $L$, rule out $(1/\varepsilon)^{o(d)}$ dependence under ETH. Support-function duality transfers the results to positive-output two-layer ReLU networks.
Read the full abstract ▾
Computation and Language
MicroVerse: An Instrument for Measuring Self-Authored Identity Drift in Long-Horizon Multi-Agent Language-Model Simulations
Sky Ng, Brihi Joshi, Ishan Gupta et al. (+43 more)
Long-horizon, multi-
agent language model (LM) simulations are widely proposed for studying social behavior, yet instruments to measure whether persona-conditioned
agents maintain identity fidelity under sustained pressure are lacking. We present MicroVerse, a behavioral-science instrument that measures identity drift in generative
agents.
Agents carry an immutable "soul file" (core values, moral boundaries, personality, goals) and inhabit a resource-scarce 50 x 50 environment where water is a non-respawning survival constraint. Scarcity is operationalized via a per-tick existence-cost gradient. The eight-verb action space maps directly to moral boundaries (trade, talk, attack, scavenge). Using a three-layer
memory architecture,
agents periodically revise a mutable current identity against their immutable original soul via importance-triggered reflection. To mitigate survivor bias, MicroVerse decouples measurement from behavior using uniform longitudinal engine snapshots every N ticks alongside a forced-end snapshot of all living and dead
agents. Identity drift is scored offline using a paraphrase-aware, value-anchored, multi-register diff rather than raw cosine similarity. We evaluate the instrument via a controlled seed run (n = 25) and a reflection-threshold sweep (thresholds {40, 80, 150}) to determine if drift dynamics are gate artifacts or threshold-robust properties. We report two primary findings: (1) Anti-self-deception emerges unprompted as the single largest semantic category of identity modification (27 of 111 added boundaries, 24%). (2) The system is threshold-robust; lower gates accelerate and increase revision frequency but preserve drift direction. All empirical results are strictly preliminary existence proofs and effect shapes (one model, one seed per arm, n = 25) rather than statistical significance claims.
Read the full abstract ▾
All authors Sky Ng, Brihi Joshi, Ishan Gupta, Shirley Huang, Zonglin Di, Yun Shen, Qianfeng Wen, Yifan Simon Liu, Ruoqi Gao, Yilan Fan, Zhiwei Zhang, Muhammad Ahmed Mohsin, Yucheng Lu, Xiaoyi Liu, Heming Liu, Qianyu Zhu, Hanwen Xing, Zhengyang Shan, My Chiffon Nguyen, Guanghui Min, Jianheng Hou, Yunze Xiao, Keyang Xuan, Hannah Collison, Jintao Huang, Jiatong Li, Sankalp Jajee, Yunhan Zhao, Bing Hu, Xupeng Chen, Binghang Lu, Weihang Xiao, Aravind Mohan, Bolun Sun, Yunshu Wu, Yuanda Xu, Runyu Zhang, Zheyuan Deng, Xinchen Tan, Dianzhuo Wang, Yijun Wang, Yixuan He, Koutian Wu, Cheng Cheng, Xiaomin Li, Yuexing Hao
Artificial Intelligence · Cross-listed from q-bio.QM
Characterising cardiac tissue properties with graph neural networks
Ching-En Chiu, Yoo Ri Kim, Magdi Saba et al. (+2 more)
Characterising electrophysiological properties of cardiac tissue efficiently and accurately from spatially sparse intracardiac measurements is clinically important for localising ablation targets and improving arrhythmia treatment. We developed a graph neural network-based framework trained on synthetic electrogram signals on 2D flat surfaces to identify areas of interest in the context of cardiac ablation for premature ventricular complexes (PVCs). Our method achieved an average precision of 0.96, 0.97, and 0.95 for the detection of single-patch fibrosis, rapid depolarisation and high excitability, respectively. The trained model can then be applied to 2D curved surfaces with few-shot fine-tuning, demonstrating its generalisation capability. Future work will develop this framework further for clinical use in PVC ablation.
Read the full abstract ▾
All authors Ching-En Chiu, Yoo Ri Kim, Magdi Saba, Danilo Mandic, Marta Varela
Computational Engineering
OmniRemesh: Adaptive and Quasi-differentiable Remeshing for Crystal Plasticity Simulation and Inverse Parameter Calibration under Large Deformation
Ningyu Yan, Yuntong Huang and Yang Xiang
Large-deformation
crystal plasticity finite element method (CPFEM) simulations are often limited by accumulated mesh distortion, which degrades accuracy and numerical stability, while adaptive remeshing introduces discrete
topology changes that impede gradient-based inverse analysis. We present OmniRemesh, a unified framework that addresses these forward and inverse challenges through two developments. First, a structure-driven remeshing method dynamically redistributes local mesh resolution according to both microstructural geometry and the evolving mechanical state. By refining grain boundaries and localized deformation regions while retaining a coarser mesh elsewhere, the method maintains mesh quality and physical consistency, improves the accuracy and robustness of large-deformation calculations, and resolves grain-scale heterogeneity without uniformly dense discretization. Second, a frozen-remeshing-branch strategy locally fixes the mesh sequence within a parameter trust region and periodically updates it as the parameters evolve. This treatment provides approximate automatic-differentiation sensitivities despite
topology changes, enabling efficient inverse calibration of constitutive parameters against both macroscopic and local observables. Numerical examples demonstrate accurate and stable CPFEM simulations up to 80% tensile deformation. The inverse calibration successfully recovers both macroscopic and local responses. OmniRemesh thus provides a practical framework for large-deformation CPFEM and remeshing-aware constitutive calibration.
Read the full abstract ▾
Machine Learning
Self-Supervised Auxiliary Task Discovery for Stable Reinforcement Learning in Stock Trading
Arishi Orra, Himanshu Choudhary and Manoj Thakur
Reinforcement learning has gained increasing
attention as a data-driven approach for stock trading. However, learning a policy that is both profitable and stable remains challenging due to non-stationary
market behaviour and noisy reward signals. Auxiliary tasks are often used to improve representation learning and stabilize training, yet they are usually designed manually and depend heavily on prior assumptions about targets and prediction horizons. Such fixed designs may not remain suitable across changing
market regimes. In this work, we propose a self-supervised framework that automatically discovers auxiliary tasks to support reinforcement learning for stock trading. The auxiliary tasks are formulated as General Value Functions so that their predictions enrich the learned state representation and assist policy optimization. The framework consists of two networks. The main network learns the trading policy along with the auxiliary predictions, while the secondary network generates the definitions of auxiliary tasks through learned cumulants and discount factors. These tasks are updated using a meta gradient mechanism that accounts for their long-term impact on trading performance and improves training stability. We evaluate the proposed approach across four major equity indices: DJI, FTSE, Sensex, and TAIEX. The empirical results demonstrate that automatically discovered auxiliary tasks lead to more robust learning and improved trading performance compared to existing baselines.
Read the full abstract ▾
Machine Learning · Cross-listed from math.ST
How Many Samples Are Needed to Determine Causal Direction? Sharp Minimax Bounds for Bivariate LiNGAM
Jikai Jin
We study how many observations are needed to determine the causal direction between two linearly related variables. Classical LiNGAM theory shows that independent non-Gaussian disturbances identify the direction, but does not quantify the difficulty when the causal effect is weak or the disturbances are nearly Gaussian. Let $\beta$ bound the absolute structural coefficient from below, let $\nu$ measure each standardized disturbance's distance from Gaussianity, and let the disturbance scales lie in $[\underline\sigma,\overline\sigma]$. We prove the sharp local minimax law \[ N_2^\star(\beta,\nu,\delta) \asymp \frac{\log(1/\delta)} {d_\beta^2+\beta^2\nu^2}, \qquad d_\beta= \left[\beta^2- \left(1-\frac{\underline\sigma^2}{\overline\sigma^2}\right)\right]_+. \] Previous theory established population identifiability or assumed a fixed separation between the two directions. By contrast, we establish the sharp sample complexity as a joint function of edge strength, distance from Gaussianity, and scale uncertainty, and characterize when identification comes from non-Gaussian dependence or from covariance alone. The proof was independently generated with GPT-5.6 Sol in Codex's Ultra mode during a two-hour session. The human author supplied the
prompt and was responsible only forchecking the proof and revising and polishing the manuscript.
Read the full abstract ▾
Human-Computer Interaction
PersonaEval: Persona-Based User Simulation for Evaluating Interactive Applications
Yifan Simon Liu, Qianfeng Wen, Yilan Fan et al. (+40 more)
Real user studies are important for understanding how people interact with systems under test or already deployed. In practice, however, they are often costly, time-consuming, and difficult to scale. To address these challenges, we introduce PersonaEval, a persona-based user simulation framework that approximates real-user behavior across diverse interactive settings. PersonaEval connects simulated users drawn from existing persona
datasets to task-specific application interfaces and collects the interaction trajectories and outcomes. PersonaEval provides a plug-and-play evaluation workflow in which the application being evaluated can be easily changed. In this demo, we present PersonaEval on three forms of interactive applications: surveys, chatbots, and web applications. Together, these examples show that PersonaEval can support repeatable, parallelizable, and scalable evaluation across different interaction settings, while producing user-oriented feedback and task-specific behavior.
Read the full abstract ▾
All authors Yifan Simon Liu, Qianfeng Wen, Yilan Fan, Shirley Huang, Ruoqi Gao, Jianheng Hou, Muhammad Ahmed Mohsin, Zonglin Di, Brihi Joshi, Xincheng Tan, Yucheng Lu, Xiaoyi Liu, Heming Liu, Hanwen Xing, Guanghui Min, Zhengyang Shan, My Chiffon Nguyen, Ishan Gupta, Yunze Xiao, Hannah Collison, Jintao Huang, Jiatong Li, Sankalp Jajee, Yunhan Zhao, Bing Hu, Sky Ng, Xupeng Chen, Binghang Lu, Weihang Xiao, Aravind Mohan, Bolun Sun, Yunshu Wu, Yuanda Xu, Yun Shen, Runyu Zhang, Zheyuan Deng, Zhiwei Zhang, Qianyu Zhu, Dianzhuo Wang, Yijun Wang, Yixuan He, Yuexing Hao, Xiaomin Li
Numerical Analysis
A Structure- and Pressure-Positivity-Preserving Semi-implicit IMEX Finite Volume Scheme for Ideal MHD at All Acoustic Mach and Alfvén Mach Numbers with Generic Equation of State
Zefeng Chen, Riccardo Demattè, Walter Boscheri et al. (+1 more)
We present a conservative, structure-preserving, finite-volume scheme for ideal MHD that ensures pressure positivity, remains applicable across all Mach and Alfven regimes, and handles general nonlinear equations of state. The scheme splits the MHD system into three sub-systems according to characteristic wave scales: an advective part for hydrodynamic transport, a
magnetic part for velocity-field coupling, and a pressure part for pressure-velocity coupling. Nonlinear advective terms are explicit, while the other two sub-systems are implicit, yielding a mild, velocity-based CFL condition that is supported by extensive numerical evidence. This makes the scheme suitable for gas-pressure or
magnetic-pressure dominated regimes and the incompressible limit. The implicit discretisation gives a pressure equation that reduces to an
elliptic form in the low-Mach limit for ideal gases and general thermodynamics. Pressure positivity is ensured via a local conservation-preserving modification of the pressure-internal-energy relation, avoiding a posteriori clipping while preserving conservation. The divergence-free constraint is enforced exactly via constrained transport. Second-order accuracy is achieved with an IMEX Runge-Kutta time integration, TVD reconstruction for explicit fluxes, and central discretisation for implicit terms. The scheme is validated against numerous
benchmarks, including high- and low-Mach regimes, strongly magnetised flows, and standard MHD shock problems in 1D and 2D, demonstrating accuracy, stability, and excellent shock-capturing.
Read the full abstract ▾
All authors Zefeng Chen, Riccardo Demattè, Walter Boscheri, Stephen Millmore
Data Structures and Algorithms
Recoverable robust representatives selection problem under interval continuous budgeted uncertainty
Marcel Jackiewicz, Adam Kasperski and Pawel Zielinski
In this paper, the recoverable robust representative selection problem is considered, where uncertain second-stage costs are modeled using interval uncertainty with a continuous budget. While the variant under a discrete uncertainty budget is known to be NP-hard, we show that transitioning to a continuous budget fundamentally alters the computational complexity landscape. Specifically, by exploiting the structural properties of the problem under the continuous budget model, we design a strongly
polynomial-time
algorithm for the general case. Furthermore, we propose an even more efficient strongly
polynomial-time
algorithm for an important special case.
Read the full abstract ▾
Artificial Intelligence
Schema-Agnostic Graph Reasoning Agent for Hybrid Knowledge Graphs
Marius Dragic, Ruben Ifrah and Alexandre Rio
Tool-calling LLM
agents navigate unfamiliar codebases with a handful of generic primitives for listing, reading and searching files (ls, cat, grep). A knowledge graph admits the same interface: listing neighbours, reading node content and searching descriptions are the same operations on a different substrate. Building on this correspondence, we present GRA, a Graph
Reasoning Agent that explores hybrid knowledge graphs, whose nodes are either textual concepts or relational tables, with seven generic tools, discovering everything domain-specific at run time. On UFK-M (Unified Factory Knowledge Model), an industrial
benchmark of 258 analytical questions whose gold answers are produced by executing validated SQL programs, GRA beats a full-context
agent by 5.1 pp (88.4% vs. 83.3%), while reading under a third of its input
tokens. A graph-free control shows the gain comes chiefly from selective agentic access rather than graph
topology, and that the effect depends on a model able to drive tools reliably. Seeing less, the
agent answers better: selective
navigation over a structured substrate beats exhaustive context.
Read the full abstract ▾
Information Theory · Cross-listed from quant-ph
Geodesic Quantum $f$-Divergences
Ángela Capel and Pablo Costa Rico
We introduce the geodesic
quantum $f$-divergences $D_f^t$, $0\leq t\leq1$, obtained from the affine-invariant geodesic between the standard and maximal relative modular operators. They reduce to the classical $f$-divergence for commuting states. The logarithmic generator yields geodesic relative
entropies joining the Umegaki and Belavkin-Staszewski
entropies, while the power generators yield $(t,\alpha)$-Rényi divergences joining the Petz and
geometric families. Our first main result is data processing of $D_f^t$ for every finite operator-convex generator $f$ and every $t\in[0,1]$. In particular, this gives DPI for the geodesic relative
entropies and for the $(t,\alpha)$-Rényi divergences when $0<\alpha<1$ or $1<\alpha\leq2$. Our second main result identifies equality in the DPI: for invertible states, every equality-determining operator-convex generator has, at each nonmaximal parameter $0\leq t<1$, exactly the Petz sufficiency class; at $t=1$, this changes to the generally larger maximal, or BS, class, which also coincides with the equality class of the divergences associated with the quadratic generator for every $t$. Our third main result is the corresponding collapse of invertible geodesic
quantum Markov chains: for each of the three ordered conditional-mutual-information constructions, the $t$-
quantum Markov chains are precisely the
quantum Markov chains for $0\leq t<1$, whereas at $t=1$ they are the invertible BS
quantum Markov chains, a class that can be strictly larger. We also determine parameter-monotonicity regimes and the intersections with the $(\alpha,z)$ family. We prove strengthened data-processing and reconstruction estimates; we compare the three conditional orientations; we establish continuity bounds under positive lower-
eigenvalue assumptions together with complementary discontinuity results; and we give a capacity-per-unit-cost interpretation.
Read the full abstract ▾
Artificial Intelligence
The Authority Resolution Framework: A Five-Domain Ontology for Governing Who and What Decides, at Scale
Parviz Shariff
As AI systems become increasingly capable of autonomous action, determining whether an
agent is technically capable of performing an action is insufficient: the system must also determine whether the action is authorised in its context. This paper introduces the Authority Resolution Framework (ARF), a five-domain ontology for representing and resolving authority across organisational roles and informal influence, business concepts, codified processes, machine-readable permissions and executable systems, and external real-world context. ARF defines the Authority Relation (AR) as a cross-domain primitive binding an actor, action, object, bounded context, justification chain, and a calibration measure termed the DNA-Coefficient, which captures divergence between documented authority structures and authority as practiced. The framework provides a machine-interpretable representation of authority provenance and scope, with JSON-LD representations and knowledge-graph query patterns for authority resolution. ARF is designed to support AI
agents in determining the provenance, scope and contextual validity of authority before executing consequential actions. The framework positions authority resolution as a knowledge-representation and
reasoning problem at the intersection of ontology engineering, semantic AI, agentic AI and AI governance.
Read the full abstract ▾
Computer Vision
CardiacMamba: Fair and Robust RGB-RF Fusion for Remote Heart Rate Estimation via State Space Modeling
Bo Zhao, Zheng Wu, Yiping Xie et al. (+1 more)
Remote photoplethysmography (rPPG) enables non-contact heart rate (HR) monitoring from facial
videos, but RGB-only methods are vulnerable to illumination changes, motion artifacts, and skin-tone-dependent optical reflectance. We propose CardiacMamba, a fair and robust RGB-RF fusion framework that integrates optical facial cues and
radio-frequency cardiac motion cues through state space modeling. CardiacMamba introduces a Temporal Difference Mamba Module (TDMM) to enhance subtle RF temporal variations, a bidirectional SSM-based interaction mechanism to align heterogeneous RGB-RF dynamics, and a Channel-wise Fast
Fourier Transform (CFFT) module for channel-domain spectral refinement. On the EquiPleth
dataset, CardiacMamba achieves state-of-the-art performance with 0.96 bpm MAE, 3.06 bpm RMSE, and 0.97 Pearson correlation, while reducing the observed light-dark skin-tone MAE gap to 0.26 bpm and maintaining robustness under RGB degradation and RF-missing conditions
Read the full abstract ▾
All authors Bo Zhao, Zheng Wu, Yiping Xie, Zitong YU
Computer Vision
MITE-Net: SWaP-Optimized 4K Video Tiny Target Perception for Embodied Edge SAR
Mingshuo Xu, Mu Hua, Jigen Peng et al. (+2 more)
Real-time tiny target perception in high-resolution imagery is critical for
embodied Search-and-Rescue (SAR) missions. However, strict Size, Weight, and Power (SWaP) constraints on edge devices like
UAVs create a bottleneck: traditional image downsampling causes severe feature loss, while slice-based processing incurs prohibitive latency. To address this gap, this paper introduces a comprehensive framework encompassing a novel architecture, specialized
datasets, and hardware-level
benchmarks. First, we propose MITE-Net, a SWaP-optimized cascaded architecture, which couples a bio-inspired, learning-free Tiny Target Motion-Based Region Proposal Network (TTM-RPN) with a sub-0.14M-parameter R-CNN-like head. Second, to standardize 4K tiny target evaluation, we construct the SAR-Tiny
Datasets by relabeling two challenging
UAV datasets: SeaDroneSee-Tiny (dynamic maritime scenes, tiny targets predominantly of 64-256 pixels ) and UAVID-Tiny (cluttered urban scenes, extremely tiny targets, less than 64 pixels). Third, we
benchmark against state-of-the-art YOLO models on an edge device, NVIDIA Jetson AGX Xavier, where MITE-Net directly processes 4K maritime imagery, achieving a 100% search success rate at 30.33 FPS. Consuming merely 3.19 W (9.51 FPS/W), MITE-Net vastly outperforms YOLO baselines in target recall and energy efficiency. Conversely, UAVID-Tiny evaluations expose a compound structural limitation: the learning-free bionic front-end struggles against urban backgrounds, while the ultra-lightweight head lacks representational capacity for complex features. Ultimately, this work delivers an efficient onboard perception paradigm and a rigorous baseline guiding future end-to-end SAR architectures.
Read the full abstract ▾
All authors Mingshuo Xu, Mu Hua, Jigen Peng, Qi Wang, Shigang Yue
Computation and Language
A Cognitively Motivated Multidimensional Framework for Evaluating Metaphor Explanations
Ana Naveriani, Jakob Suchan, Stefano Zoia et al. (+3 more)
Current evaluation of metaphor explanations relies mainly on holistic quality ratings, revealing little about how explanation quality is structured or where human judgments agree and diverge. We introduce a cognitively motivated framework that decomposes metaphor explanation quality into six theoretically grounded dimensions. In a dense annotation study (11,200 ratings), we find that: {\bfseries(i)} explanation quality is genuinely multidimensional; {\bfseries(ii)} annotator disagreement is systematic rather than random; and {\bfseries(iii)} the six dimensions collapse into a shared cluster and two independent axes of judgment. An exploratory feasibility study further shows that a standard automatic evaluation pipeline can recover parts of this structure, predicting the most discriminative dimensions well while its errors correlate human (dis)agreement. Together, these results suggest that multidimensional evaluation offers richer diagnostic insight than holistic ratings, and that automatic evaluators for open-ended generation tasks should be judged on how well they preserve the structure of human judgment.
Read the full abstract ▾
All authors Ana Naveriani, Jakob Suchan, Stefano Zoia, Mehul Bhatt, Antonio Lieto, Gian Luca Pozzato
Numerical Analysis · Cross-listed from quant-ph
Resource Analysis for Quantum Simulation of Spatially Varying Transport-Reaction Equations
Benjamin Jasperson, Krishna Garikipati and Siddhartha Srivastava
Spatially varying coefficients are the primary source of
circuit complexity in
quantum simulation of linear advection-
diffusion-reaction equations. This work presents a resource analysis of single-step
quantum propagators constructed using sparse FABLE block encodings,
Quantum Singular Value Transformation, and linear-combination-of-
unitaries. We derive theoretical estimates for
qubit count, gate complexity, and
circuit depth in terms of the spatial discretization, sparsity, and
polynomial degree, and compare these predictions with synthesized
quantum circuits for one- and two-dimensional variable-coefficient problems. The resulting analysis quantifies the cost of encoding realistic transport operators and provides practical resource estimates for near-term implementations.
Read the full abstract ▾
Numerical Analysis
Robust Block Preconditioning for 3D nonlinear steady-state radiation transport equations
Yunpan Ma, Lingxiao Li and Changhui Yao
In this work, based on the discrete ordinate method, we propose a robust block preconditioning strategy for the 3D nonlinear steady-state radiation transport equation with heat
diffusion term. The presence of the diffusive term of the temperature equation prevents its elimination into a single equation for the radiation intensity. To overcome this difficulty, all physical variables are assembled into a single monolithic linear system. The heat flux and temperature are treated as independent variables in a mixed $H(\mathrm{div})$-conforming finite element formulation. The equation for radiation intensity is discretised by a discontinuous Galerkin method with upwind flux, where a vectorial finite element space is used to couples the radiation intensity in different directions within each element. We then construct a Newton-Krylov iterative solver to solve the nonlinear equations, for which the core part is efficient preconditioning. To accelerate the convergence of Krylov's method, three block preconditioners are constructed, corresponding to different levels of approximation of the coupling between the temperature and radiation intensity. $P_{\mathrm{Schur}}$ retains the full coupling. $P_{\mathrm{Split}}$ drops the conductive contribution to the radiation block. $P_{\mathrm{BJ}}$ neglects the radiation-to-temperature coupling, retaining only the temperature-to-radiation coupling. Numerical experiments demonstrate the mesh independence and robustness of the proposed preconditioners.
Read the full abstract ▾
Machine Learning
Second-Moment Memory in Coordinatewise Adam
Jeonseong Kim
Adam retains a moving average of past squared gradients in its denominator, but the optimization cost of this
memory is not well understood. We show that second-moment
memory can itself suppress progress toward the optimum even under finite-variance
stochastic gradients. For a simple two-point oracle, the expected positive normalized update is $O(M_2^{-1/2})$ after an initialization transient, where $M_2=(1-\beta_2)^{-1}$ is the second-moment
memory length. We convert this directional bound, under the stated
memory and stepsize scaling, into an average-stationarity lower bound of the same order on a smooth convex problem with normalized gap, smoothness, and variance. Long second-moment
memory can slow optimization even when the gradient noise has finite variance.
Read the full abstract ▾
Game Theory
Exact MMS Allocations under Personalized Bivalued Valuations: Goods and Chores
Yuhao Zhang
The maximin share (MMS) is a central
fairness benchmark for allocating indivisible goods and chores. We study additive valuations in the personalized bivalued setting, where each
agent assigns one of two
agent-specific values to every item. Whether exact MMS allocations always exist in this setting has remained a major open question, as highlighted by Ebadian, Peters, and Shah and by Garg, Huang, and Segal-Halevi. We answer this question affirmatively: we prove that exact MMS allocations always exist for both goods and chores and can be computed in
polynomial time. Our proof combines a quota-based reformulation with an envelope relaxation, a sparse extreme-point construction, and flow-based rounding that controls the total rounding loss.
Read the full abstract ▾
Computation and Language
QuantumPhaseNet: A Gauge-Covariant Geometric and Quantum-Spectral Theory of Semantic Concept Hierarchies with Prototype Validation of a Classical Quantum-Inspired Model
Kiyotaka Kasubuchi and Kazuo Fukiya
We present QuantumPhaseNet, a gauge-covariant
geometric and
quantum-spectral extension of
Transformer representations. Context-dependent semantic states are modeled as complex amplitudes; a covariant phase rate induces a semantic wavelength used as a proxy for conceptual scale; and low-frequency graph modes define a document-level discourse direction. The theoretical part establishes local gauge invariance, unitarity of the
quantum block, boundedness and conditional stability of WavePhase
Attention, and a calibratable
hallucination-risk formulation. We also implemented a fully offline Validation Studio for the classical
quantum-inspired pipeline in Section 14.1 and evaluated the five research questions in Section 16.1 on its built-in synthetic setting (n=240, observation noise 0.22,
circuit noise 0.08, five seeds). RQ1 yielded a wavelength-hierarchy Spearman correlation of 0.852 versus 0.707 for the baseline, 87.3% direction accuracy, and AUC 0.953. RQ2 achieved discourse
alignment 0.933 versus 0.589 and 41.2 versus 16.2 paragraphs before drift. RQ3 achieved AUROC 0.881 versus cosine 0.765 and phase-shuffle 0.536. RQ4 achieved error-detection AUROC 0.854 versus
entropy 0.634, with Brier 0.150 and ECE 0.098. RQ5 did not show
quantum advantage: target probability and end-to-end cost efficiency were 25.5% and 0.107, compared with 70.7% and 0.707 for the Chebyshev classical approximation. These results provide initial synthetic evidence for the classical
quantum-inspired components, but not external validity or unconditional
quantum speedup.
Read the full abstract ▾
Computer Vision
FlowDance: Music-Driven Dance Video Generation with Parallel Pose and RGB Streams
Genying Li, Boda Lin, Jiachen Li et al. (+5 more)
Music-driven dance
video synthesis aims to animate a reference person according to a given music clip. The task is challenging because it requires a model to jointly learn music-to-motion correspondence, identity-preserving human animation, temporal coherence, and visually realistic
video generation. We present FlowDance, a music-driven dance
video generation framework that integrates explicit motion modeling with reference-preserving visual synthesis through parallel pose and RGB streams. We further introduce timestep-aware pose injection to adapt structural guidance across denoising steps and persistent identity injection to preserve the reference appearance over long
video. To support this task, we further build a popularity-curated, high-resolution in-the-wild dance
video dataset with synchronized music, RGB
videos, 3D body motion, camera parameters, and projected 2D pose annotations. Extensive experiments show that FlowDance achieves strong performance in both dance motion generation and music-driven dance
video synthesis.
Read the full abstract ▾
All authors Genying Li, Boda Lin, Jiachen Li, Zijian Jia, Haojie Zheng, Yiming Wang, Shuchen Weng, Si Li
Artificial Intelligence
RLCascadeRouter: Quality-Estimator-Free Cascade Routing via Reinforcement Learning
Shihong Huang, Shengjie Wang, Hong Ma et al. (+1 more)
The growing ecosystem of large
language models (LLMs) offers huge potential to optimize performance-cost trade-offs. However, their heterogeneous capabilities and inference costs make efficiently routing queries a significant challenge. Existing paradigms are inflexible: one-shot routers commit before observing responses, whereas conventional cascades stop adaptively but follow a fixed model order. Cascade routing removes both restrictions by reconsidering whether to stop or invoke another model after each response. Current methods use a predict-then-optimize pipeline estimating response quality and future model utility. However, prediction loss for quality or utility is not equivalent to routing-decision loss. A lower prediction error does not necessarily yield a better action; a small boundary-crossing error can reverse a “stop” or model-selection decision. Therefore, we propose RLCascadeRouter, a quality-
estimator-free framework that formulates cascade routing as a Markov decision process with actions comprising “stop” and model selection. It uses trajectory returns and advantages to directly optimize the performance-cost objective. Its Cascade Policy Network models candidate complementarity for model selection and remaining-action value for stopping, eliminating independent post-hoc response-quality
estimators. Evaluated across ten LLMRouterBench
benchmarks with thirteen LLMs, RLCascadeRouter outperforms strong baselines and achieves superior performance-cost trade-offs. It incorporates unseen models without retraining, and ablation studies validate both policy components.
Read the full abstract ▾
All authors Shihong Huang, Shengjie Wang, Hong Ma, Zhou Xu
Robotics
ViTaR: Visuo-Tactile Residual Adaptation for Foundation VLA Manipulation
Yi Wang, Renjun Wu, Jinyan Liu et al. (+1 more)
As
Vision-
Language-Action (VLA) models scale toward real-world deployment, contact-rich manipulation exposes a critical blind spot: these policies encode broad visual-semantic priors yet remain unaware of local contact events, producing identical actions whether contact is established, lost, or destabilized. Existing remedies either modify VLA internals, risking catastrophic forgetting, or demand online reinforcement under near-failure contact conditions. Both grant tactile unbounded influence over action generation, conflicting with the priors that make VLAs generalizable. We introduce ViTaR, which reframes tactile feedback from an action-generating perceptual input to an execution modulator that selects and scales bounded residual corrections atop a frozen VLA, preserving pretrained capabilities by construction. ViTaR decomposes adaptation into two stages: Effect-Guided Modeling determines whether and which correction is locally justified via outcome-grounded preference evidence, and Residual Action Modulation converts this evidence into a residual choice with continuously scaled gain from real-time visuotactile observations. On the UniVTAC
benchmark spanning seven contact-rich tasks, ViTaR achieves 61.3% average success, a 30.6 percentage-point improvement over its frozen VLA base that also surpasses purpose-built tactile baselines. Physical-
robot experiments confirm that bounded tactile modulation transfers to real sensor noise and dynamics.
Read the full abstract ▾
All authors Yi Wang, Renjun Wu, Jinyan Liu, Xuesong Li
Machine Learning
KOALA: Koopman Operator Learning for WiFi-Based Anticipatory Hum
Quang-Anh N. D., Duc Pham Minh, Thao Phuong Pham et al. (+3 more)
WiFi Channel State Information (CSI) has emerged as a
privacy-preserving alternative to cameras for human pose estimation. However, existing approaches treat pose inference as an instantaneous regression problem and do not model temporal dynamics, making future motion prediction infeasible. Naively applying
vision-based prediction methods compounds the estimation noise already present in CSI-derived poses, as autoregressive rollouts amplify errors at every step. We propose KOALA, the framework for human motion prediction directly from WiFi CSI, by lifting noisy CSI-derived pose sequences into a learned Koopman latent space where nonlinear dynamics become linear, enabling multi-horizon prediction via simple
matrix-vector products without autoregressive iteration or error accumulation. A residual CSI-conditioned operator resolves the identity attractor problem inherent from Koopman formulations, and an anchor-delta prediction head eliminates the degenerate shortcut of copying the current pose across all horizons. To regularise the lifting and operator jointly, we introduce a Koopman Anchored Latent (KAL) loss that operates in the temporal-encoder feature space, enforcing dynamical consistency across prediction horizons without requiring contrastive, spectral, or auxiliary losses. Experiments on MM-Fi and WiPose show that KOALA achieves robust, consistent performance across both short- and long-term prediction horizons, outperforming all baselines by a substantial margin.
Read the full abstract ▾
All authors Quang-Anh N. D., Duc Pham Minh, Thao Phuong Pham, Minh Anh Nguyen, Huan X. Nguyen, Tuan Dang
Cryptography and Security
Assessing Attack Surfaces in Generative Search Engines through Publisher Attributes: A Case Study in Political Domains
Riku Mochizuki, Shusuke Komatsu, Souta Noguchi et al. (+1 more)
We characterize the attack surface of generative search engines (GSEs) against poisoning attacks in the political domain, from the perspectives of citation selection and personalization. GSEs integrate web search and answer generation with user preferences and backgrounds using large
language models (LLMs). They play a crucial role in how users access information on the web. Because anyone can publish content on the web, GSEs are vulnerable to poisoning attacks that manipulate citations to undermine reliable information delivery. Existing studies on citation evaluation focus on how faithfully answers reflect cited content. However, they leave unexamined the two critical aspects to capture the attack surface of GSEs against poisoning attacks: which publishers GSEs prefer to cite, and how personalization affects citation behavior. To fill this gap, we introduce an evaluation framework that characterizes the attack surface of GSEs against poisoning attacks. Our contributions are twofold: (1) we propose a novel metric, content-injection barrier, which quantifies the difficulty of injecting arbitrary content onto the web with a given level of publisher authority; and (2) we reveal how personalization affects citation behavior by
embedding user profiles into GSEs. We conduct experiments on three major GSEs in the political domain of the United States and Japan. Our results show that (a) the attack surface differs across GSE models; (b) the web search functionality of GSEs shapes the attack surface; (c) ruling parties have a broader attack surface than opposition parties; and (d) user profiles have little influence on the attack surface.
Read the full abstract ▾
All authors Riku Mochizuki, Shusuke Komatsu, Souta Noguchi, Kazuto Ataka
Computer Vision
From Generation to Matching: A Development Report on Personalized Chinese Handwriting
Yiwei Liu
This paper documents a frozen engineering project on personalized Chinese handwriting. The project started from approximately 200 real handwriting images from one user, covering 197 unique Chinese characters, and was initially formulated as few-shot generation of unseen characters. A sequence of canonical-centered personalization routes repeatedly exposed the same conflict: increasing structural pressure made outputs more canonical, while increasing personalization could damage identity-defining strokes. The project was therefore reset around real-human character equivalence classes. A multi-writer CASIA candidate pool showed that a USER-compatible realization often already existed among valid human samples. The task consequently changed from synthesis to character-wise matching, followed by cross-writer composition into a virtual writer. The frozen system uses real-ink features, character-specific human population percentiles, top-20 candidate
pruning, and greedy hardest-first whole-row selection. On the covered target set, all 197 USER characters had real-human candidates, and the 100-character evaluation subset was covered 100/100. Knowncharacter held-out comparisons included a row judged visually almost indistinguishable from genuine USER handwriting. A 60- episode stability audit placed every episode in a predefined A-like machine-proxy region, but these were not independent human A-level judgments. The final evidence supports stable practical B-level quality, with many outputs approaching A-level under the USER-defined criterion. The report records why generation became unnecessary for this case without claiming unrestricted or universal handwriting synthesis.
Read the full abstract ▾
Artificial Intelligence
Pricing the Risk of Runtime Compression: Anytime-Valid Admission and a Served-Output Law for Compressed Serving State
Fanzhe Wei and Li Liu
Runtime compression of serving state trades quality for capacity with no priced guarantee: systems adapt precision on load signals with no soundness statement, and certified approaches budget request-level risk by a union bound over a pre-declared event count. We show the union budget exhausts on every long request in a production serving stack (100% of requests), and replace it with an anytime-valid, physically accounted ledger whose bound holds at every one of 352,333 admission calls on live traffic and which, in a pre-registered held-out confirmatory round, halves the exact-fallback rate at matched risk (0.30 -> 0.14) – coverage is bought at a price the account states. We then price the remaining distance from the certified witness to what a user experiences: a machine-checked design law (TV <= tanh(a_q w_thr)) turns the served-TV target into a threshold knob, and a three-layer audit of its instantiation – an operator-norm query envelope measured 1.5x from tight, a measured-ellipsoid replacement for the Cauchy-Schwarz ball that buys nothing (0.89x, held-out sound), and the gate's operating point (~700x) – localizes the entire 1064x gap to the operating point, a price the law now states rather than an unknown. A priced bound is worth nothing on a request one has not seen, so the third link is the quantifier: exchangeable extrapolation across 80 serving histories replaces binary conformal prediction's vacuous certificates with order-statistic bounds that discriminate (0.41 against 0.51 calibration risk). All probabilistic kernels are Lean 4-checked (228 exported
theorems, no sorry); which object deserves this machinery at all is settled empirically in a companion paper that adjudicates – and rejects – the natural alternative of certifying routing. What ships is an account: risk you can spend, a gap you can read off a law, and a bound that survives the request you have not seen.
Read the full abstract ▾
Machine Learning
A Pre-Specified Construction-Confirmation Test of Operation-Level Causal Transfer Across Finite Isomorphic Symbolic Domains
Xinyi Shan
Behavioral accuracy, linear decodability, and successful activation interventions do not by themselves show that a model carries an operation-level structure from one symbolic domain to another. We ask a narrower question in finite isomorphic state spaces: if the hidden-state difference between two operations is estimated separately for each source input, does adding that difference to a mapped recipient input move the model toward the corresponding recipient answer? The design compares this input-specific intervention with wrong-operation, norm-matched random, and no-op controls, and separates candidate construction from an independently isolated confirmation split. On a frozen Qwen2.5-7B-Instruct model at layers 20–21, one route–domain–operation candidate from a family pre-specified and frozen before confirmation access, transparent | integer_mod16–letters16 | successor->predecessor, passed both PyVene splits; its confirmation intersection–union p-value was 0.000198 and its 36-family Holm-adjusted p-value was 0.006943. A subsequent NNsight 0.7.0 experiment, pre-specified and frozen before its confirmation access, tested only this selected
prompt route, without candidate or layer reselection. It reproduced all 12 confirmation effect estimates, confidence intervals, and exact sign-flip p-values numerically; its 36-family Holm-adjusted p-value was 0.007141. The result is therefore limited to one
prompt route and one candidate, replicated across two intervention implementations on one model revision and one layer interval. It does not establish cross-model generalization, full-family backend independence, domain-general transfer, or algebraic invariance.
Read the full abstract ▾
Computation and Language
Miyu Yamada and Yuki Arase
Hallucinations remain a major obstacle to the reliable use of large
language models (LLMs) in conditional text generation. Existing methods primarily assess the factuality of an entire generated text, providing limited insight into which output spans are hallucinated or how they relate to the input. We introduce the task of
hallucination span detection with input-side evidence
alignment, which jointly identifies hallucinated spans and aligns output
tokens with the corresponding input evidence. Our approach is based on the observation that faithful output
tokens are predictable from the input, whereas hallucinated
tokens are not. We therefore train an encoder-based model to predict masked output
tokens from the input representation, using prediction confidence for
hallucination detection while naturally producing
alignments to the input. Experiments show that the proposed method effectively detects hallucinated spans and identifies meaningful input-side evidence. Human evaluation confirms the quality of the predicted
alignments.
Read the full abstract ▾
Software Engineering
Mind the Gap: An Empirical Study of Synchronization Gaps, Delays, and Missed Opportunities in Software Forks
Jiaying Zhu, Lyuye Zhang, Jiahui Wu et al. (+2 more)
Fork-based development enables parallel
evolution of software, but unsynchronized contributions create persistent divergence: security patches, bug fixes, and quality improvements often fail to propagate across fork families, leaving downstream users exposed to known vulnerabilities or bugs and missing massive opportunities to improve the other repositories in the family. We present the first large-scale empirical study of fork synchronization, analyzing popular GitHub fork families with 3,820 actively maintained forks, and developed a monitoring platform to mine the valuable commits and promote their swift merging. Our findings reveal a synchronization paradox: while 90% of submitted pull requests are merged, only 6.92% of fork commits ever appear in PRs, leaving massive fork development permanently unsynchronized across the families. Synchronization delay is pervasive and structurally uneven where fork propagation accounts for 72.9% of end-to-end commit lifecycle delay. Contrary to common assumptions, PR rejection is rarely caused by technical incorrectness; instead, 65% of rejections stem from superseded contributions, process violations, or maintainer policy decisions.
Read the full abstract ▾
All authors Jiaying Zhu, Lyuye Zhang, Jiahui Wu, Chengyue Liu, Yang Liu