Peer Revenue Past citations are no guarantee of future returns

Papers

Fresh from arXiv, typeset properly. Highlighted words trade on the market.

Computer Science

cs Watch Computer Science (sign in to use)

Wednesday 19 August

Machine Learning

Holtercare-Bench: A Multimodal Benchmark for Evaluating Long-Term Dynamic ECG Analysis

While multimodal large language models (MLLMs) excel in medical applications, most of them favor static images or short-term signals. In the critical field of dynamic electrocardiograms (ECG), models struggle with complex temporal reasoning and diagnostic report generation due to a lack of high-quality datasets and benchmarks. To address this, we introduce (i) Holtercare-23K, a large-scale multimodal dynamic ECG dataset comprising 22,980 QA pairs derived from 788 clinical Holter records and featuring a novel signal-video-text tri-modal alignment. Based on this dataset, we present (ii) Holtercare-Bench, a multimodal benchmark that evaluates models on temporal localization, clinical diagnosis, and global summarization. Zero-shot evaluations of leading MLLMs reveal a significant performance gap in processing ultra-long pathological sequences. However, fine-tuning representative models yields substantial improvements. This work illuminates the limitations of current MLLMs in electrophysiology and provides a foundational benchmark for long-term medical MLLMs. Our project is available at https://github.com/ZJU4HealthCare/Holtercare-Bench.
Read the full abstract

All authors Yihan Xie, Hanwen Cui, Runze Ye, Juekai Lin, Haoyang Wang, Jinhao Mao, Bo Zhang, Wenqiao Zhang, Xiaogang Guo, Jun Xiao, Lei Zhang

Hardware Architecture

HyperCut: Fast Inter-Layer Scheduling via Directed Hypergraph and Early Filtering

As deep neural networks (DNNs) continue to scale, inter-layer scheduling, which orchestrates the spatial allocation of compute resources and the temporal execution order across layers, has become a decisive factor in sustaining high utilization and energy efficiency on tiled accelerators. However, existing inter-layer schedulers defer cost feedback until a complete fine-grained intra-layer scheduling has been resolved. The resulting decoupled flow repeatedly explores sub-optimal or even infeasible inter-layer schedules, and the absence of early pruning during the inter-layer phase remains a critical bottleneck for design-space exploration (DSE) in DNN compilers. Our key observation is that the cost of an intra-layer scheduling can be tightly upper-bounded once the inter-layer cut fixes the sub-mesh shape, which lets us cost every inter-layer candidate without solving the intra-layer problem. Hence, we propose a hierarchical partitioning-and-mapping framework, HyperCut, that enables early filtering of inter-layer schedules based on hypergraph partitioning. Based on the directed hypergraph (DHG) abstraction of DNN, we introduce a unified representation, State, that jointly encodes the DHG partition, tile mesh allocation and tensor batch splitting. Thereby, partitioning and mapping are coupled into a union optimization object. For a DNN with N layers, the resulting theoretical design space is bounded by O(N), compared with O(9.899^N) for the state-of-the-art open-source scheduler SET. Across 10 evaluated cases, HyperCut achieves 2.0x performance improvement and 80.47% exploration time reduction over the SET baseline, measured by geometric mean.
Read the full abstract

All authors Ziang Wei, Zirui Xu, Sufeng Guo, Chuanchao Gao, Yiyang Gao, Arvind Easwaran, Yuxiang Fu

Computer Vision

Clustering and Token Denoising for Faster and More Robust VLMs

Recent Visual-Language Models (VLMs) have enhanced the capabilities of pre-trained LLMs by adding vision tokens alongside text, with approaches like LLaVA showing impressive results. However, the computational burden of processing up to 576 or 729 visual tokens makes edge deployment challenging. While various token pruning techniques require retraining, some are training-free and thus can easily adapt to architecture changes. We introduce ClustRS, a two-part, training-free algorithm for robust token pruning. Its first component is an attention-weighted, clustering algorithm that selects representative tokens from each semantic cluster. The second component, Residual Shrinkage, is a one-pass denoising step on the selected tokens. These training-free lightweight steps make LLaVA ready for real-world data, improving robustness to a wide range of image-noise types and intensities. Experimental results on the ScienceQA-IMG and MM-VET benchmarks show our method outperforms attention- and diversity-based methods by up to 20% under extreme noise and token conditions (reducing tokens by 97%, down to 16 tokens) on LLaVA 1.5 7b and achieves exceptional results on LLaVA-OneVision, where we match baseline performance with fewer than one-third of their tokens under mild noise conditions. Our study demonstrates a simple yet powerful alternative to both score-only and diversity-only pruning rules, paving the way for compute-efficient and noise-resilient VLM deployment.
Read the full abstract

All authors Baptiste Rossigneux, Inna Kucher, Vincent Lorrain, Emmanuel Casseau

Machine Learning · Cross-listed from stat.ME

Recovering Nonlinear Functions of Latent Variables: A Plausible-Value Neural Network Framework

When factor scores replace true latent scores in nonlinear prediction, measurement error attenuates the recoverable variance of any $k$th-order component of the regression function by $\rho^k$ – the $k$th power of the score's coefficient of determination – for any linear score type. This study derives the bound via Hermite polynomial expansion and proposes PV-ANN – plausible values (posterior draws preserving latent variance) combined with artificial neural networks (learning functional form without prespecification). The bound governs recovery of the latent-scale function, not prediction of the outcome from observed indicators, for which factor scores are already sufficient; the two metrics are therefore predicted to dissociate. An 18-condition simulation supports both predictions: in the nonlinear low-reliability conditions PV-ANN closes about four fifths of the function-shape recovery gap between a factor-score learner and one given the true latent values, and the margin widens as reliability falls, while predictive accuracy is not improved, as the theory requires. A Big Five application illustrates the intended exploratory workflow and delineates boundary conditions under weak signal and measurement model misspecification.
Read the full abstract

Robotics

APPROVE: Visual End-User-in-the-Loop Robot Programming with LLMs

Programming robots remains challenging for non-experts, as traditional methods require expert knowledge and even block-based interfaces often lack flexibility. Recent work has explored Large Language Models (LLMs) to automatically generate robot programs from natural language, but these systems remain limited by a lack of transparency, missing mechanisms to ensure alignment with user intent, and little support for reuse. We present APPROVE (AI-Powered Programming for Robots with Visual End-User Feedback), an LLM-based multi-modal end-user programming framework that integrates natural language input with a block-based interface and an explicit user confirmation step. Generated programs are visualized using a block-based interface in Blockly, allowing users to confirm, modify, or reject them before execution. Confirmed functions are stored in a library for reuse, gradually building a set of reliable program components. Our approach contributes a human-centered design for LLM-based robot programming that emphasizes user trust, intent alignment, and reusability.
Read the full abstract

All authors Bijan Kavousian, Miray Özakkas, Josefine Monnet, Oliver Petrovic, Christian Brecher

Robotics · Cross-listed from cond-mat.mtrl-sci

Multi-Tool Robotics Enables In-Situ Sample Manipulation for Time-Resolved Synchrotron Measurements

The high photon flux at synchrotron beamlines allows for the measurement of fast dynamical processes. However, beamline radiation-safety protocols prohibit human intervention during X-ray experiments, limiting the ability to perform versatile real-time sample manipulations during continuous data acquisition. Here we present a robotic platform at an X-ray scattering beamline to enable real-time sample handling and processing in the experimental hutch, revealing previously inaccessible transient in-situ dynamics in perovskite thin films. This modular multi-tool robotic architecture enables in-hutch sample manipulation beyond human-access constraints, establishing a foundation for automated and autonomous synchrotron experimentation.
Read the full abstract

All authors Aditya Bondada, Elizabeth M. Wall, Eric Yuan Xiao, Quinn C. Burlingame, Yueh-Lin Loo, Esther H. R. Tsai, Ruipeng Li

Computation and Language

SPADE: Self-Play in Adaptive Synthetic Executable Environments

Continuous self-improvement requires an ever-expanding pool of self-generated, diverse, adaptive goals. For language agents, existing training environment pools (hand-curated, statically synthesized, or frozen-verifier) keep the goal distribution fixed as the learner scales. We introduce SPADE (Self-Play in Adaptive Synthetic Executable Environments), a self-play RL framework in which a single LLM plays two roles: an Environment Designer that writes complete, long-horizon training environments as executable code with an OpenAI Gym-style reset()/step() interface, and a Reasoning Agent that learns to act in them. Each is a stateful, multi-turn environment (state transitions, reward functions, and verification code), so one interface spans reasoning problems and multi-step agentic tool use. The Reasoning Agent's regret is estimated using the gap between its reward with and without privileged hints; in optimizing this regret signal the Environment Designer learns to target environments at the edge of the agent's capabilities while keeping them feasible. Through extensive experimentation, we find several components critical to success: grounding the Environment Designer on documents sampled from a large pretraining corpus, and giving it an accumulated environment memory. Scaling to 30B-parameter models, SPADE improves over the strongest fixed-environment baseline by +5.3 on average across eight held-out math, science, code, and reasoning benchmarks, and lifts the tool-use setting by +5.7 on BFCL-v4 multi-turn and +13.9 on ACEBench-Agent; on the games setting, the margin over the strongest baseline grows with model scale. By making environment design itself a learnable component, SPADE takes a concrete step toward open-ended self-improvement.
Read the full abstract

All authors Bo Liu, Simon Yu, Yiding Jiang, Ao Qu, Andrew Zhao, Zichen Liu, Junsu Kim, Zijian Zhou, Seungone Kim, Tongzheng Ren, Mickel Liu, Hanfei Yu, Zhaorun Chen, Weiyan Shi, Paul Pu Liang, Luke Zettlemoyer, Yejin Choi, Natasha Jaques

Computers and Society

Qualified Cross-References as a Verification Method: The Normative Environment of the EU AI Act

Legal cross-references are commonly represented as links between instruments or provisions. In a curated legal knowledge base, a link must also identify the legal character of the interaction, its supporting provisions and conditions, and remain consistent from either instrument. This paper presents a provision-level model and a protocol for qualified cross-references, developed through a bilingual corpus of fourteen instruments surrounding Regulation (EU) 2024/1689 (the AI Act). The model distinguishes direct textual reference, bounded presumption of conformity, substantive interaction without textual reference, mediated intersection, and institutional analogy; applicative interaction and definitional overlap are independent dimensions. Its methodological contribution is bidirectional inversion: a relationship documented from act A towards act B is reconstructed from B's perspective against both instruments. This verification tests provisions, qualification, direction, and conditions before deciding how to render the relationship from either side. Applied during construction, the protocol surfaced six incorrect article references, three inaccurate legal qualifications, and one divergence between two published descriptions of the same interaction. A reference to Regulation (EU) 2019/881 illustrates why qualification matters: the AI Act's bounded cybersecurity presumption differs from other product legislation's uses of the same certification framework. The contribution is a map of one regulatory environment and an explicitly specified method for making curated cross-reference knowledge bases inspectable and internally testable. A later, separately scoped corpus audit is discussed among the limitations, without pooling its findings with the original measurements; limited access to historical inputs constrains independent reproduction.
Read the full abstract

2608.19194 · 19 Aug · Clarified the scope of validation, the status of the registry sample, and the limits of reproducibility. Added a concise discussion distinguishing source fidelity, technical functionality, and legal verification, informed by a separate local audit. Results of the original inversion study are unchanged

Numerical Analysis

A Localized Fourier Extension Method for Piecewise-Smooth Inverse Source Reconstruction

We reconstruct a piecewise-smooth source in a Poisson equation on a semi-infinite strip from noisy solution values measured along an interior line. Applying the one-dimensional Dirichlet Laplacian to the observation reduces the inverse problem to regularized second-order differentiation followed by a boundedly invertible correction. The differentiated trace and the source differ by an analytic smoothing term and therefore have the same interior singular support and jump data. This structure motivates a localized Fourier extension method that combines two staggered detection partitions, GTSVD-regularized local derivative coefficients, mollified conjugate Fourier sums, and structure-aligned numerical differentiation. The source is then recovered by an exponentially decaying spectral correction. For an exact partition, the reconstruction inherits the piecewise differentiation rate $\mathcal O(\delta^{(\bar s-2)/\bar s})$; local peak and partition perturbation estimates describe the additional effect of breakpoint errors. Comparisons with full-grid total-variation regularization and truncated Fourier inversion show competitive high-noise performance and a pronounced low-noise advantage of the localized method. Repeated Gaussian-noise tests confirm robustness in the moderate- and low-noise regimes.
Read the full abstract

Cryptography and Security

The Structured Totient Preimage Problem: Reconstruction, Collisions, and Cryptographic Implications

We define and study the Structured Totient Preimage (STP) problem as a restricted reconstruction relation with a direct cryptographic motivation. Let $p_1,\ldots,p_k$ be distinct primes of the same bit length and reveal only $x=\prod_{i=1}^k(p_i-1)$. Given $(x,\lambda,k)$, STP asks for any set of $k$ distinct $\lambda$-bit primes satisfying this product. The relation is efficiently verifiable, but its reconstruction complexity is not known. We establish three concrete results. First, for factored $x$ we derive the exact number of ordered exponent allocations and a bound showing that direct reconstruction is polynomial for fixed $k$ when $\Omega(x)=O(\log\lambda)$; this rules out that regime as a basis for a strong hardness claim. Second, we give exhaustive algorithms for reconstruction and collision analysis. Third, we exhaustively evaluate 28 parameter pairs, with $2\leq k\leq5$, up to $\lambda=16$ for pairs and 4,588,935 prime sets in the largest census. The data quantify non-injectivity through collision participation, maximum multiplicity, and conditional ambiguity in bits. These results isolate STP from general inverse-totient computation and motivate a Structured Totient Preimage Assumption for explicitly growing parameter families. Under such an assumption, STP becomes a candidate preimage-resistant relation whose implications for commitments, proofs of knowledge of multiplicative witnesses, and authentication can be stated precisely. The paper establishes the computational foundation and parameter constraints for those constructions; it does not claim a security reduction or post-quantum hardness.
Read the full abstract

Cryptography and Security

SiNMULI: Novel Signed Network Approach for Malicious URL Identification

In today's era of rapid advancements in artificial intelligence, computer security and online safeguarding measures have undergone significant improvements. However, malicious websites continue to facilitate the spread of phishing schemes, fraudulent activities and unsolicited communications. Conventional methodologies in machine learning, deep learning and counterfeit website detection predominantly depend on static data analysis, which frequently proves ineffective against the evolving nature of malicious online entities. In response to these challenges, in this work, we propose a signed network-based approach for malicious URL identification, SiNMULI. We introduce an innovative framework that conceptualises the identification of harmful URLs as a signed network-based binary classification problem strongly rooted in the fundamental principles of social network analysis and social balance theory. In this approach, a signed network is constructed based on the backlinks, i.e., external hyperlinks of URLs, wherein each node symbolises a URL and the hyperlinks function as signed edges. Utilising a balance-theoretic inference mechanism, our methodology propagates edge signs and classifies unlabeled domains by employing a 51% majority rule across incoming links. Experimental results on this real-world dataset demonstrate that SiNMULI achieves 99.89% accuracy, 99.62% precision, and 99.80% F1-score, outperforming traditional ML and deep learning baseline models. Beyond high accuracy, SiNMULI offers interpretability, resilience against adversarial obfuscation, and independence from training data, making it a lightweight and scalable solution for real-world cyber defence.
Read the full abstract

Numerical Analysis

Entry growth in Gaussian elimination

Gaussian elimination is one of the oldest algorithms in mathematics, and the most popular method for solving an unstructured linear system. Its stability in finite precision is controlled by its growth factor, which measures how large the entries produced during elimination can become. Understanding the worst-case behavior of this quantity has been a central problem in numerical analysis since the 1940s. Here we make a significant leap in that understanding, settling several open problems. In particular, we determine the asymptotic behavior of the maximum growth factor under complete and rook pivoting, proving that both are quasi-polynomial in dimension. We also show that the exponential growth under partial pivoting persists for sparse matrices and that randomized partial pivoting suffers the same instability. In contrast, we show that every non-singular matrix has a row permutation with polynomial growth, though finding the optimal row permutation is NP-hard.
Read the full abstract

Robotics

PartialBiGrasp: Inferring Hidden Local Geometry for Bimanual Grasping from Partial Views

Dual-arm robotic grasping is essential for manipulating large, heavy, and geometrically complex objects that cannot be reliably handled using a single manipulator. These large objects often contain only sparse graspable regions determined by local geometric properties such as thickness, edge structure, and gripper clearance. Prior bimanual grasping methods assume access to a full point cloud of the object which inherently contains this geometric information, but may not be accessible in real scenarios. This work proposes PartialBiGrasp, a dual-arm grasp generation framework that operates directly on partial point cloud observations. Our model learns geometric features implicitly through convolutional occupancy networks, enabling local reasoning about graspability, collision-free contact regions, and object thickness. We leverage this understanding to generate force-closure compliant grasp pairs, which are further refined using a sampling-based optimization to correct for ambiguity caused by incomplete geometry. We evaluate our approach using analytical force-closure metrics, large-scale simulation experiments, and real-world robot evaluations on noisy partial point clouds of novel objects, demonstrating robust and physically stable dual-arm grasp generation.
Read the full abstract

All authors Ayush Kaura, Vignesh Vembar, Md Faizal Karim, Keshab Patra, K Madhava Krishna

Distributed Computing

A Fast Deterministic Algorithm for $(\Delta+1)$-edge coloring in CONGEST

Vizing's theorem states that any graph of maximum degree $\Delta$ can be properly edge-colored with $\Delta + 1$ colors (which is optimal in general). A recent breakthrough result by Bernshteyn showed that such a $(\Delta + 1)$-edge coloring can be found deterministically in $poly(\Delta,\log n)$ rounds in the LOCAL model of distributed computing, where $n$ denotes the number of vertices of the input graph [J. Comb. Theory 2022]. Since then, the exponent in the $poly(\log n)$-part of the runtime has been improved by Christiansen [STOC 2023] and Bernshteyn and Dhawan [J. Comb. Theory, Series B, 2025]. However, the algorithms used in all of these works use large messages, leaving open the question for efficient algorithms in the more restrictive CONGEST model. We answer this question by presenting the first $poly(\Delta,\log n)$-round algorithm for $(\Delta + 1)$-edge coloring in the CONGEST model. Our algorithm is deterministic and the $n$-dependency of its runtime, $\tilde{O}(\log^5 n)$, matches the best published dependency in the LOCAL model.
Read the full abstract

Robotics

ADEPT: Accelerating Dexterity via Pre-Training and Post-Training using Reinforcement Learning

We introduce Accelerating Dexterity via Pre-Training (ADEPT), a large-scale reinforcement learning (RL) framework for learning sim-to-real transferable dexterity across high degree-of-freedom (DoF) robot embodiments that can solve long-horizon tasks directly from raw visuo-tactile perception. ADEPT pretrains a dexterous policy on a generic object reposing task, then post-trains downstream policies with this pretrained behavior as a prior. ADEPT enables learning new behaviors that are otherwise difficult to discover from scratch on multi-fingered robots and avoids learning the same set of skills over again for every new downstream task. The pretrained policy zero-shots the reposing phase of downstream tasks, but naïve RL fine-tuning rapidly degrades this capability during transfer. We address this with a stable post-training recipe combining behavior-cloning distillation, critic warm-up, and conservative on-policy updates. To safely exploit the full kinematic dexterity, we introduce a joint-space Geometric Fabric that mediates between the RL policy and the robot. We distill post-trained teachers into perceptive students that zero-shot sim-to-real transfer on two embodiments: a 23 DoF Kuka-Allegro with two RGB cameras, and a 29 DoF Flexiv-Sharpa with two RGB cameras and five vision-based tactile sensors, and can solve long-horizon tasks from challenging initial states with dexterity at human-level speed.
Read the full abstract

All authors Jayjun Lee, Jessica Yin, Asif Rana, Nicholas Blauch, Octi Zhang, Sam Mady, Mohak Bhardwaj, Nima Fazeli, Nathan Ratliff, Karl Van Wyk, Ankur Handa

Machine Learning

Beyond Teacher Likelihood: Group-Calibrated On-Policy Distillation for Long-Context Reasoning

On-policy distillation (OPD) trains a student on its own responses using dense token-level guidance from a stronger teacher. In long-context tasks, however, token-level teacher support can favor locally plausible responses that omit evidence distributed across the input or violate global task constraints. Task-specific verifiers, in contrast, evaluate task completion at the response level and may return graded rewards that reflect partial success. We diagnose this mismatch on fixed responses from two representative long-context evidence-aggregation tasks. Across longer input ranges, trajectory-level OPD scores become progressively less aligned with verifier rewards, indicating teacher-verifier disagreement. Motivated by this observation, we introduce Group-Calibrated On-Policy Distillation (GC-OPD). GC-OPD separately normalizes verifier rewards and trajectory-level OPD scores within each rollout group and uses their difference as a signed teacher-verifier disagreement residual. Relative-advantage-based credit assignment (RACA) distributes this trajectory-level residual across tokens according to their relative OPD advantages while preserving the original OPD signal. Across five long-context benchmarks, post-training with GC-OPD raises the five-benchmark averages of the official Qwen3-4B and Qwen3-8B checkpoints from 29.08 to 40.47 and from 35.12 to 44.65, respectively. Vanilla OPD reaches 39.31 and 43.56 under the same setup. Controlled ablations show that the signed residual is more effective than either an additional OPD-derived term or direct group-normalized verifier reward addition, while RACA further improves over uniform token allocation. Together, these results demonstrate that group-relative residual calibration can incorporate verifier outcomes without discarding dense token-level guidance. Code is available at https://github.com/SolereZhang/GC-OPD.
Read the full abstract

All authors Zhu Zhang, Jixun Wang, Xiaoang Xu, Xiaorong Wang, Zihan Zhou, Zhiyuan Wang, Shuo Wang, Chaojun Xiao, Yuezhi Zhou

Computer Vision

Image-Guided Pavement Defect Recognition in GPR Data with novel 3D Deep Learning Architecture

Ground Penetrating Radar (GPR) is a widely adopted non-destructive sensing technology for subsurface inspection in civil and transportation engineering. Despite its potential for pavement condition assessment, the large-scale application of GPR in automated inspection has two key challenges: the scarcity of annotated real-world datasets and the lack of deep learning models designed for the unique characteristics of 3-Dimensional (3D) GPR data. This study addresses these limitations by firstly introducing a cost-effective data preparation pipeline that integrates orthomosaic Red Green Blue (RGB) imagery with 3D GPR scans to generate annotated 3D GPR datasets. The proposed method uses the aligned segments of RGB and GPR data, using pavement surface images as a reference to transfer labels of surface-visible defects to corresponding GPR segments, enabling efficient large-scale annotation in a real-world dataset collected on a highway section under operation. In addition to the dataset contribution, we propose a specialised 3D Convolutional Neural Network (CNN) architecture incorporating residual connections, mixed convolutional kernel sizes, and both depthwise and channelwise attention mechanisms to enhance feature representation and defect classification. The model is evaluated on binary classification tasks for detecting patch and crack defects in pavement structures. Experimental results demonstrate that the proposed network outperforms baseline architectures across multiple evaluation metrics. Ablation studies further confirm the effectiveness of the designed architectural components. This work contributes a scalable and practical method for real-world dataset generation, along with a novel deep learning framework.
Read the full abstract

All authors Yuandong Pan, Linjun Lu, Mudan Wang, Florian Noichl, Fan Xue, Brian Sheil, Lavindra de Silva, André Borrmann, Ioannis Brilakis

Sound

Finetuning Strategies for Querying Sounds by Vocal Imitation

This technical report describes our winning submission to the AES AIMLA 2025 Challenge on querying sound effects by vocal imitation. We investigate two complementary fine-tuning strategies: contrastive learning with a frozen, pretrained CED encoder, and joint contrastive-triplet learning with semi-hard negatives using a MobileNetV3 encoder. This report has been updated for posterity to include details released after the challenge.
Read the full abstract

All authors Aditya Bhattacharjee, Christos Plachouras, Sungkyun Chang, Emmanouil Benetos

Data Structures and Algorithms

Cell-Probe Lower Bounds and Complexity-Preserving Reductions for Suffix Array Queries

For a text $T$ of length $n$ over an alphabet of size $\sigma$, its suffix array lists the starting positions of the suffixes of $T$ in lexicographic order, and its inverse suffix array gives the lexicographic rank of the suffix starting at each position. Since the introduction of the FM-index and the compressed suffix array in 2000, both queries have been supported in $O((\log_\sigma n)^\epsilon)$ time using $O(n\log\sigma)$ bits, for any constant $\epsilon>0$. Yet no nontrivial time-space lower bound for suffix-array queries in compact space was known. We give the first such lower bound: in the cell-probe model with $\Theta(\log n)$-bit words, every deterministic $S$-bit data structure with $S\ge n$ answering suffix-array queries on binary strings of length at most $n$ has worst-case query time $\Omega(\log\log n/\log((S/n)\log\log n))$. Hence, structures with $O(n(\log\log n)^{O(1)})$ bits need $\Omega(\log\log n/\log\log\log n)$ query time, while constant query time requires $\Omega(n\log^\epsilon n)$ bits for some constant $\epsilon>0$, matching known upper bounds. In particular, no such $O(n)$-bit structure supports constant-time queries, answering the 25-year-old question of Grossi and Vitter. We also give exact complexity-preserving equivalences between suffix-array access and simpler prefix queries on short strings. For every $2\leq\sigma\leq n$, suffix-array queries are equivalent to prefix-select queries, and inverse-suffix-array queries are equivalent to prefix-special-rank queries. The reductions in both directions preserve all four standard measures up to constant factors: space, query time, preprocessing time, and preprocessing space. Unlike previous reductions, they incur no additive $O(\log\log n)$ query-time term. Thus, the corresponding prefix-query problems capture suffix-array and inverse-suffix-array access without asymptotic loss in any of the four measures.
Read the full abstract

Machine Learning

Lévy Attention: Single-Pass Predictive Uncertainty for Continuous-Time Attention

Deep models for irregularly-sampled time series answer queries at arbitrary continuous timestamps, yet report nothing about how far each answer should be trusted. We show the attention layer itself can close that gap: with the right stochastic formulation, the pass that makes each prediction also reports, in closed form and at no extra cost, how far it should be trusted. We introduce Lévy Attention, a cross-attention operator whose output is a stochastic integral against an inhomogeneous Poisson random measure: query-key compatibilities assemble an intensity over a continuous (time x channel) index space, the measure scatters atoms under it, and the output averages an interpolated value field at those atoms. In expectation it reduces to a mollified cosine-kernel attention, so it replaces a softmax layer and trains with exact gradients. What softmax discards, the Poisson construction preserves in closed form: the evidence $\Lambda_q$ (total compatibility mass) and the disagreement $\mathrm{tr}\,\Sigma_V(q)$ (value spread). An exact variance identity makes their combination $\hat\sigma(q)=\sqrt{\mathrm{tr}\,\Sigma_V(q)\,\varphi(\Lambda_q)}$ the root-mean-square deviation of the sampled operator, emitted by the deterministic pass with no trained head. Empirically, disagreement carries the signal, while the evidence factor swings from uninformative on dense data to strongly informative on sparse. On t-PatchGNN the operator swap costs at most 5.6% accuracy against a matched control and nothing on the sparsest dataset. The free disagreement signal improves on 20-pass MC dropout across matched five-seed suites, and $\hat\sigma$ scales a calibrated Gaussian whose zero-sample CRPS beats a fifty-draw sampler; a split-conformal wrapper reaches nominal coverage at every level, and one pass ranks 3,383 unseen patients by trust in 1.4 seconds.
Read the full abstract

Systems and Control · Cross-listed from math.OC

Constrained minmax density transportation for linear parabolic PDEs: a numerical optimal control perspective

This article introduces a numerical optimal control framework for minmax constrained density control for a class of noisy linear parabolic partial differential equations (PDEs), in particular the noisy heat equation. The goal is to transport an initial density to a target density while minimizing a specified cost with respect to control actions and maximizing it with respect to disturbances, all within a fixed time horizon while satisfying given convex path constraints. To address this, the spatial derivatives in the PDE are discretized using finite-difference approximations, transforming the problem into a system of ordinary differential equations in time. The admissible space of control and disturbance trajectories is then finitely parametrized, and the resulting optimal control problem is formulated as a convex semi-infinite program (SIP) under mild assumptions. By leveraging new numerical tools from convex SIP theory, we establish guarantees for exact solutions that account for constraint satisfaction under an infinite family of disturbance realizations, and we establish an optimization-based computationally efficient algorithm to recover these solutions. Comprehensive numerical examples to demonstrate and validate our findings are included.
Read the full abstract

All authors Siddhartha Ganguly, Vaibhav Upadhyay, Kenji Kashima, Debasish Chatterjee

Machine Learning

Learned, Then Lost: A Measured Single-Example Counterfactual in Pre-training

A single training example's contribution to a finished model is normally estimated rather than measured, because measuring it takes two expensive full pre-training runs that differ in one row of one batch. We ran that counterfactual 24 times at a small scale. We trained 32 GPT-2 models at 124M parameters from scratch on OpenWebText, over four conditions and eight seeds. At step 200 of 9,536, at peak learning rate, we replaced one row of a 256-row batch with a fixed context injection carrying a 194-token passage. The three injected conditions are: 1. fluent prose with a corpus-attested subject, 2. fluent prose with a fabricated subject matched to it within 0.14% on full-batch gradient delta, and 3. random keyboard characters. The fourth condition is an uninjected twin. The passage is learned from one exposure and then decays. Fifty steps after injection, the arm that saw a passage predicts it better than the arm that did not by 0.039 and 0.044 nats of cross-entropy on the passage, at eight of eight seeds with p < 0.0001. At the final step we do not detect that difference for either passage, at p = 0.25 and p = 0.71, against minimum detectable effects of 0.025 and 0.079 nats, nor between the two passages, at p = 0.54. Every geometric measure we report is taken after that decay. Our pre-registered contrast on interpolation loss barrier is +0.0068 with p = 0.509, against a minimum detectable effect of 0.032 barrier units. Held-out cross-entropy is -0.00044 with p = 0.310. Per-layer centered kernel alignment does not detectably separate any condition at any layer. Weight displacement reaches 44.1% of the seed-to-seed Euclidean distance and is 92% settled by the midpoint of training, while the barrier reaches 3.0% of the seed-to-seed barrier. Those two figures sit roughly 15 times apart, and that is a lower bound. The injection relocates the model within its basin without moving it out.
Read the full abstract

Distributed Computing

Upper and Lower Bounds on the Space Complexity of Multi-word Single-Writer Registers

We prove matching upper and lower bounds on the space complexity of simulating a large shared register using smaller shared registers. We focus on the case where both the simulated and base registers are single-writer, which means they can be accessed concurrently by multiple readers but only by a single writer. To strengthen our lower bounds, we prove that they hold even when the base registers are atomic and the simulated register is regular. Furthermore, the lower bounds hold for obstruction-free implementations, which means they also hold for lock-free and wait-free implementations. If $m$ is the number of values representable by the large register and $b$ is the number of values representable by each base register, our first lower bound says that any obstruction-free implementation that has an invisible reader requires at least $\lceil \frac{m-1}{b-1} \rceil$ base registers. A reader is considered invisible if it never writes to base registers. This lower bound is asymptotically tight for the invisible-reader case and represents an exponential improvement over the previous best known lower bound. For the general case, which allows any combination of visible and invisible readers, we prove a $\lceil \min(\frac{m-1}{b-1}, r+\frac{\log{m}}{\log{b}}) \rceil$ space lower bound, where $r$ is the number of readers. To show that this lower bound is asymptotically tight, we develop a wait-free algorithm for simulating a multi-word atomic register from atomic base registers using $\Theta(r + \frac{\log{m}}{\log{b}})$ space. Combining this algorithm with known invisible-reader constructions gives a $\Theta(\min(\frac{m}{b}, r + \frac{\log{m}}{\log{b}}))$ space upper bound. This improves upon the previously known space upper bound of $\Theta(\min(\frac{m}{b}, r\frac{\log{m}}{\log{b}}))$.
Read the full abstract

Computation and Language

ChildSafeAds Shared Task 2026: Commercial Content in Child-Facing YouTube Videos

ChildSafeAds is a shared task on commercial content in YouTube videos likely to reach children and teenagers. The dataset contains 3,360 videos from 939 channels, each starting with a sponsor segment submitted to SponsorBlock. We pair each segment with its transcript, video, and channel information, plus a sales or service page linked from the video description. Systems determine the type of offer being promoted (ST1), assign product categories (ST2), and identify potential legal risks (ST3). Evidence is divided into four cumulative access levels, from the transcript to the linked page, so performance can be compared against the cost of collecting additional data. YouTube's "Includes paid promotion" label was absent from 45.5% of the videos. GPT-5.4 produced the labels after the organiser team, including a legal expert, reviewed samples and iterated on the taxonomy, prompts and model choices. GPT-5.6-luna independently labelled the development set to measure cross-model agreement. The evaluation received 21 entries; the highest mean macro-F1 was 0.735, while the best transcript-only entry reached 0.652. Across four system papers, the linked promotional page mainly helped identify what was being sold and added little to compliance-risk classification. The competition also exposed sensitivity to rare labels, advertiser overlap across splits and substantial variation in the ST3 labels.
Read the full abstract

All authors Thales Bertaglia, Catalina Goanta, Gerasimos Spanakis, Gunes Acar

Computers and Society

LearnAI: Just-in-Time AI Co-Creation Across Disciplines at a University

As generative AI reshapes professional and educational practice, institutions face a challenge: how to support diverse learners, from non-coders to advanced students, in building confidence and practice with AI-supported problem solving. Most institutional responses bifurcate into conceptual workshops for general audiences or technical courses for computer science majors, leaving few spaces where mixed-ability learners can engage common AI tasks at levels matched to their prior experience. This experience report presents the LearnAI Framework, a two-layer model for just-in-time AI co-creation piloted at a comprehensive teaching university. The Wide-Exposure Layer embeds short presentations in existing courses to build AI awareness at scale, reaching students and faculty across 18 courses in five disciplines. The Customized Co-Creation Layer provides opt-in, one-on-one sessions where clients work with trained undergraduate tutors through a 5-Stage Pedagogical Script: Problem Framing, Tool-Task Mapping, Iterative Co-Prompting, Deployment and Verification, and Ethical Reflection. Over two semesters, 35 clients co-created 36 portfolio websites and over 20 deployed web applications. Interviews with five clients and two tutors suggest a recurring change in how clients described AI use, shifting from treating AI as a passive answer machine to engaging it as a collaborative tool under human direction. A small paired pre/post AI readiness dataset (N = 7) provides preliminary descriptive context, and tutor accounts document how the pedagogical script was enacted and adapted across client types. We report on boundary cases including clients who felt overwhelmed and respondents who deliberately rejected AI use. This paper contributes a practical, adoptable framework with initial evidence from a single institution.
Read the full abstract

All authors Weihao Qu, Ling Zheng, Chris Buzaid, Daniel Crawford

Artificial Intelligence · Cross-listed from physics.ao-ph

Interpretable AI predicts a 2026 summer dry anomaly in central China

Seasonal precipitation anomalies are largely regulated by atmospheric circulation, which dynamical models predict with greater reliability than precipitation itself. Here, we employ a deep learning model that translates dynamical circulation predictions into precipitation estimates. Predictions initialized from March to May consistently indicate a dry anomaly over central China in summer 2026. Retrospective evaluations revealed higher predictive skill in the analogue years, which also tended to feature central equatorial Pacific warming persisting from the preceding winter into summer. This warming favors an anomalous cyclonic circulation over the western North Pacific-South China Sea-South China region, which induces northerly winds and moisture divergence that jointly suppress rainfall over central China. Supporting this mechanism, layer-wise relevance propagation (LRP) independently identifies these northerly winds as the dominant driver of the prediction among all model inputs. Perturbation tests supported this attribution: removing LRP-identified features effectively eliminates the dry anomaly. Our framework thus provides physically interpretable explanations for AI-derived regional climate projections, facilitating evidence-based assessment before observational data become available.
Read the full abstract

All authors Anran Wang, Wen Shi, Yong Luo, Jianbin Huang, Lijuan Chen, Junhu Zhao, Weixin Jin, Huihui Yuan

Artificial Intelligence

Beyond the Transcript: Detecting Covert Co ordination in Latent Multi-Agent Communication

Language-model agents can communicate through continuous hidden states that are invisible in public transcripts, creating opportunities for covert harmful coordination. We introduce Verifiable Latent Alignments (VLA), an activation-aware framework for monitoring and steering these private communication channels. For every monitored decision, VLA links the private latent-state record and channel status to the resulting public action using a shared event identifier, enabling matched causal analysis. Our first contribution is a neutral-only three-layer monitor combining representation anomaly detection, counterfactual action-distribution influence, and sparse-autoencoder interpretation support. Our second contribution is a steerability framework spanning black-box behavioral instructions and white-box matched-neutral counterfactuals. Our third contribution is an evaluation on a controlled multi-agent auction benchmark covering homogeneous and heterogeneous model pairs, many-agent scalability, and intervention effectiveness. The sequential monitor achieves mean area under the receiver operating characteristic curve (AUROC) of 0.993 for homogeneous agents and 0.854 for heterogeneous pairs when text- and latent-collusion rows are pooled as positives. In Qwen3-0.6B auctions with 25-100 bidders, monitoring requires only a small normalized load relative to all possible directed pairs, while full white-box steering achieves 100% bid-distribution recovery and reduces collusive low-bid behavior by 47.3 percentage points. Because full white-box steering replays the matched neutral counterfactual, its exact recovery is a sanity check by construction. Overall, the controlled study shows that the evaluated private channel attacks can be monitored without training the primary monitor on attack examples and mitigated when matched counterfactual access is available.
Read the full abstract

All authors Ramneet Kaur, Pradyumna Chari, Ramesh Raskar, Jugad Singh, Sumit Kumar Jha, Anirban Roy

Computational Complexity · Cross-listed from quant-ph

Quantum Speedups Require Structure or Depth

One of the most basic conjectures in quantum complexity theory states that every $t$-query quantum algorithm can be simulated on most inputs by a $\mathrm{poly}(t)$-query classical algorithm. If true, this would provide broad justification for the need for structure in quantum speedups. We settle this conjecture for parallel quantum algorithms, showing that every $t$-query $d$-round quantum algorithm can be simulated on most inputs with $t^{O(d^2)}$ classical queries. This suggests that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and exponential speedups would further require polynomial depth. In contrast, most known speedups for structured problems are achieved by highly parallel, low-depth algorithms. Our techniques also carry new implications for the status of $\mathsf{BPP}$ vs. $\mathsf{BQP}$ relative to a random oracle, a similarly longstanding problem.
Read the full abstract

All authors Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan

Numerical Analysis

An Exact-Moment Local Legendre Frame Method with Block Convolution for Caputo Fractional Differentiation

We propose a local Legendre frame method for the accurate computation of Caputo fractional derivatives of order \(0<\alpha<1\). On each local subinterval, the function is represented by a restricted Legendre frame obtained from scaled Legendre polynomials on an extended interval. The local coefficients are computed from equispaced samples by an exponentially weighted GTSVD regularization. The Caputo derivative is then evaluated by applying the weakly singular fractional integral to the derivatives of the local frame basis functions. Since these derivatives are polynomials, the corresponding Caputo weights can be written in terms of finite weighted moments, so that the singular kernel is treated analytically rather than by a low-order quadrature rule. For uniform partitions, the history weights have a block-dependent structure and can be reused efficiently. The error analysis separates the local frame reconstruction from the Caputo integration. In particular, the Caputo error is bounded by the derivative reconstruction error, while the latter is obtained from the \(L^2\) reconstruction error and a weighted smoothness bound of the GTSVD approximation through an interpolation argument. For analytic local functions with exponential coefficient decay, this leads to exponential-type convergence of the derivative and hence of the Caputo approximation. Numerical experiments confirm the accuracy of the exact moment weights, the effectiveness of the local weighted reconstruction, and the efficiency of the block implementation.
Read the full abstract

All authors Zhenyu Zhao, Benxue Gong, Tinggang Zhao, Xianzheng Jia

Cryptography and Security

FedGuard-DC: Privacy-Preserving Federated Load Forecasting and Cyber-Attack Detection for Data-Center Loads in Transmission Systems

The rapid growth of large data-center (DC) loads is creating new challenges for power-system visibility, privacy, and cyber-physical security. System operators need accurate short-term information about these fast-varying loads, while DC operators may avoid sharing raw megawatt measurements because they can reveal sensitive workload and utilization patterns. This paper presents FedGuard-DC, a federated learning (FL) framework for privacy-preserving DC load forecasting and local false-data-injection attack (FDIA) detection. Each DC trains a dual-head model on its own measurements, where a shared encoder supports both a forecasting head and a reconstruction head. A calibrated anomaly score combines forecast residual and reconstruction error to detect corrupted measurements locally. Raw measurements and absolute MW demand remain at each DC, while only model updates, normalized forecast outputs, and scalar attack flags are shared with the global controller. Optional differential privacy and robust trimmed-mean aggregation are included to evaluate privacy-utility behavior and poisoned-client resilience. The framework is validated using phasor-domain simulation data from four large DC loads rated between 150 and 350 MW integrated into the IEEE 39-bus New England system. Results show a 0.5 s-ahead normalized forecast RMSE of 0.023-0.038 pu, compared with 0.32-0.34 pu for persistence. FedGuard-DC detects FDIA with ROC-AUC of 0.979, F1 = 0.930, and precision of 0.988, while robust aggregation reduces the poisoned-client RMSE impact from 0.042 to 0.035 pu.
Read the full abstract