Data Structures and Algorithms
Move-rb: Faster Bi-Directional r-indexes and Approximate Pattern Matching
Johannes Fischer and Lukas Nalbach
Approximate pattern matching (APM) on highly repetitive texts is a central task in bioinformatics. Bi-directional r-indexes support left- and right-extension of a pattern and thereby accelerate APM
algorithms based on search schemes, but existing variants – br-index and b-move – suffer from two bottlenecks: $O(\sigma)$ character-predecessor/-successor queries on the run-length-encoded BWT per extension, and predecessor queries on sparse bit vectors to maintain a value in the suffix array interval and to access the PLCP array while locating. We present Move-rb, a bi-directional r-index built on the optimized r-index Move-r. Although Move-rb is 2x larger than br-index, it is up to 24% smaller than b-move, answers APM queries 1-4 orders of magnitude faster than br-index, 1.9-10x faster than b-move and up to 5.5x faster than the state-of-the-art bi-directional (uncompressed) FM-index columba, which is 36-42x larger.
Memory usage (including index size) during APM locate queries is reduced by 1.5x (up to 6.5x) for Hamming distance and 2.5x (up to 7.4x) for edit distance. Move-rb can be constructed 3-14x faster while using 19-141x less
memory than br-index, b-move and columba. A variant using a relative Lempel-Ziv-encoded suffix array locates up to 10x faster while being 1.2-2.4x larger. We achieve these speedups by optimizing index operations and search scheme APM
algorithms: Without a direction switch, Move-rb computes an all-$k$-character extension in output-optimal $O(k)$ time and a single-character extension in the same time. Augmenting Move-rb with $O((r+\overleftarrow{r})\log(n/r_{\min})\log\sigma)$ bits reduces a single-character extension to $O(\log\sigma)$ time, where $r$ and $\overleftarrow{r}$ are the numbers of runs in the BWT of the text and its reverse, and $r_{\min}=\min(r,\overleftarrow{r})$. A direction switch incurs only $O(\log\log_\omega(n/r_{\min}))$ additional time.
Read the full abstract ▾
Machine Learning
AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphs
Xiaochen Zhang, Haoyu Zhu, Yao Zhang et al. (+1 more)
Graph-structured optimization with linear constraints is fundamental to critical infrastructure but faces scalability limits due to massive strict hard constraints and high dimensionality. While recent projection-based methods such as Trainable Sampling Kaczmarz-Motzkin Net (T-SKM-Net) guarantee feasibility, they face high computational costs in dynamic environments by processing the entire constraint set and requiring expensive
matrix factorizations. To bridge this gap, we propose the Accelerated Trainable-SKM (AT-SKM) Net framework. To concentrate computation on the active constraints and eliminate redundant calculations, we introduce a hybrid sampling strategy guided by a
topology-aware heterogeneous GNN model. To efficiently handle topological shifts in graph-based constraints, we employ a Cholesky Update mechanism that theoretically reduces the equality projection complexity from O(N^3) to O(N^2) under low-rank perturbations. Experiments on random
geometric graphs, N-1 Security-Constrained DC-OPF, and minimum-cost gas transport problem demonstrate that AT-SKM reduces iteration counts by up to 85% and achieves 2.95x-7.29x SKM layer speedups, while maintaining zero constraint violations.
Read the full abstract ▾
All authors Xiaochen Zhang, Haoyu Zhu, Yao Zhang, Qingchun Hou
Computation and Language
Return or Revise? Learning When Revision Helps Retrieval-Augmented QA
Nicholas Kashani Motlagh, Tim Anderson, Jeremy Gwinnup et al. (+1 more)
We consider the decision of whether to return an existing draft answer or revise it using retrieved evidence, as in answer-revision systems. Draft confidence estimates whether the current answer is correct, but the decision requires estimating the effect of a specified revision. For offline training and evaluation, we grade both the returned draft and its candidate revision under the same correctness judge, which makes repair, harm, and the gap to an oracle observable. We call this paired effect its recoverability, and we train policies to predict it before revision. On 25,870 held-out open-domain questions across three revision setups, a scorer trained on the paired outcome has greater area under the accuracy–revision-rate curve than a matched draft-correctness scorer in all nine Llama setup–seed fits, and gains 0.23–0.68 accuracy points on average at development-selected thresholds, a difference significant across training runs only for dense
retrieval. The resulting policy improves on always revising and on average closes more than a third of the oracle gap, although it still applies 38–46% of the harmful revisions. When a draft-free standard-RAG answer is also available, however, choosing between the draft and that answer is stronger by about two points for Llama and four for OLMo, and adding candidate revision as a third option yields no significant gain. Recoverability describes one revision; its value as an available action also depends on the alternatives.
Read the full abstract ▾
All authors Nicholas Kashani Motlagh, Tim Anderson, Jeremy Gwinnup, Grant Erdmann
Machine Learning
Residual Correlation as a Diagnostic for Joint-Uncertainty Gains from GP Coregionalisation
Fangqin Zhou and Joaquin Vanschoren
In multi-target regression, correlated targets are often coupled through multi-output Gaussian processes with an intrinsic model of coregionalisation (GP-ICM), assuming that sharing statistical strength improves overall performance. In practice, the benefits are inconsistent. Across the settings studied, we find that the main benefit of coregionalisation is joint uncertainty quantification rather than point prediction. Raw target correlation does not predict when coupling helps; in the separable GP-ICM settings studied here, residual correlation, the cross-target dependence left unexplained by independent per-target predictors, is the strongest predictor of joint-uncertainty gains. We introduce a lightweight diagnostic, $D_{\rm logdet}=-\frac{1}{2}\log\det R_{\rm res}$, which represents the idealised joint negative log-likelihood (NLL) gain from modelling a full rather than diagonal residual covariance and is computable from independent GPs alone. Across a controlled synthetic study, 16 multi-target
benchmarks, and frozen
transformer and convolutional neural network representations for keypoint regression, point prediction remains largely unchanged ($\Delta R^2\approx 0$). In contrast, $D_{\rm logdet}$ strongly predicts observed ICM NLL improvements ($\rho_s=-0.83$, $p<0.001$), outperforming heuristics such as the feature-to-sample ratio. We also propose Residual-ICM, which preserves independent marginal variances while adding residual-correlation structure to the joint covariance. Residual-ICM achieves the best average joint NLL among the compared methods, while the diagnostic indicates when covariance coupling is likely to be useful. The diagnostic is specific to global Gaussian residual dependence, the structure captured by separable coregionalisation.
Read the full abstract ▾
Robotics
Real-Time Force Regulation for Whole-Hand Dexterous Grasping
Sang Min Kim, Alexander Alexiev, Tzu-Yuan Lin et al. (+3 more)
Robust dexterous grasping requires maintaining physical stability despite contacts interactively evolving across the entire hand. A precomputed force distribution can easily fail under object motion, modeling errors, or external disturbances. In this paper, we present a framework for real-time force regulation over dynamically changing whole-hand contacts. Our method geometrically estimates contacts across all hand links using a tracked object model and proprioception, without requiring tactile sensing at those contacts. It repeatedly recomputes the desired contact-force distribution subject to friction constraints, actuator limits, and an actuation-consistency constraint motivated by classical whole-limb force analysis. We integrate this force-regulation controller with reactive reaching, enabling the hand to acquire a grasp, maintain it under disturbances, and regrasp after losing the object. Simulation experiments without
gravity demonstrate improved grasp retention over fixed-allocation and fingertip-only execution under controlled perturbations, while real-world experiments on a 27-DoF arm-hand system demonstrate grasp maintenance and recovery under human-applied disturbances as contacts evolve across the whole hand. Project page: https://sangminkim-99.github.io/reactive-grasp-whole-hand/
Read the full abstract ▾
All authors Sang Min Kim, Alexander Alexiev, Tzu-Yuan Lin, Sangbae Kim, Young Min Kim, Yonghyeon Lee
Computer Vision
Can Frozen Hyperspherical Features Guide the Selection of Pseudo Masks?
Xinge Guo, Fengyang Xiao, Dingming Zhang et al. (+6 more)
Foundation segmenters such as SAM return several plausible masks for an unlabeled image, and a student trained on the wrong one inherits its errors. Choosing among them means querying a second large model or fitting a quality head to annotated masks. We show that a candidate can be judged by what it does to a frozen self-supervised backbone's features. Normalized DINOv2 patch features lie on a hypersphere, and a candidate mask splits that sphere in two. Based on this reading, we introduce SphereTrust, which scores each candidate by three properties of the split, the angular contrast between the two sides, the coverage of the foreground's appearance modes, and contact with the image frame, one for each of three common ways a mask fails, and ranks a pool in 0.55 s per image from the frozen features alone. On eight SAM and SAM3 candidate pools spanning camouflaged, salient, and dichotomous
segmentation and camouflage under low light, SphereTrust exceeds the strongest evaluated external baseline on six pools by 1.7 to 9.3 percentage points in mean selected Dice. These comparisons include published selection rules and explicitly labeled adaptations of DSS and UCOD-MKD. On the two prompted camouflage pools, its mean selected Dice is within 0.1 percentage points of the candidate-derived DSS adaptation, with a lower catastrophic-error rate. Which cue carries the signal depends on the candidate pool. The same sphere also supports training. The leading candidates enter as a candidate set with their scores as priors, prototypes reorder them, and a cross-fitted second round completes the labels, raising weighted F by 4.5, 2.3, and 5.5 points over fixed-label training on the three MLLM anchor pools, with students competitive with published unsupervised methods on nineteen test sets.
Read the full abstract ▾
All authors Xinge Guo, Fengyang Xiao, Dingming Zhang, Yuhan Chen, Rihan Zhang, Xingjian Li, Tianyang Wang, Chunming He, Sina Farsiu
Machine Learning
Reachability-Based Formal Verification of Graph Neural Networks with Node and Edge Features
Anne M. Tumlin, Ben Wooding, Zhenxuan Shao et al. (+3 more)
Graph neural networks (GNNs) have become a prominent approach for developing fast,
topology-aware surrogates in electric power systems, supporting tasks such as power flow (PF) analysis, optimal power flow (OPF) estimation, and cascading failure analysis (CFA). Despite this growing use, formally verifying GNN-based models remains challenging, with existing methods limited in scope. We extend the neural network verification (NNV) framework to graph-structured inputs through GraphStar sets, a generalization of
Star sets that captures uncertainty over both node and edge features. This extension enables the propagation of linear message-passing operations and the sound approximation of ReLU nonlinearities for GNN architectures, including graph convolutional network (GCN) and graph isomorphism network with edge features (GINE) layers. We evaluate GNNV across three power system tasks, PF, OPF, and CFA, on the IEEE-24, IEEE-39, and IEEE-118 test cases, as well as two standard graph classification
benchmarks, ENZYMES and
PROTEINS. Our results show that GNNV provides tighter robustness guarantees than CORA on graph classification models with ReLU-based activations and, for the first time, delivers edge-aware robustness guarantees for GINE-based PF and OPF models under joint node and edge perturbations.
Read the full abstract ▾
All authors Anne M. Tumlin, Ben Wooding, Zhenxuan Shao, Diego Manzanas Lopez, Tyler Derr, Taylor T. Johnson
Machine Learning · Cross-listed from stat.ML
Calvin Tolbert
Nuclear-norm-regularized least squares is a standard approach to
matrix completion, but it yields only a point estimate. Its
Bayesian counterpart, a prior combining the
nuclear norm with a Frobenius-norm term, gives a strongly log-concave though nonsmooth posterior when the noise precision is known. In practice the precision is unknown, and placing a truncated Jeffreys prior on it makes the joint posterior neither log-concave nor smooth. To our knowledge, we give the first sampler for this model with an explicit non-asymptotic guarantee: its output is within a prescribed total-variation or Wasserstein distance of the posterior on the
matrix after a number of steps
polynomial in the
matrix dimensions and the reciprocal of the target accuracy. The sampler never targets a continuous distribution that is not strongly log-concave. It discretizes the precision onto a grid, estimates its posterior by thermodynamic integration along the tilted conditional posteriors of the
matrix, and bounds the error this propagates to the posterior on the
matrix. The approach applies whenever non-log-concavity is confined to a bounded scalar hyperparameter and the conditional distributions are strongly log-concave with smooth-plus-Lipschitz potentials. Our result establishes feasibility; the
polynomial complexity is not intended as a practical
algorithm at current problem scales.
Read the full abstract ▾
Human-Computer Interaction
Beyond Driving: Envisioning Activities in Future Autonomous Vehicles through Experience-Centered Design
Keqi Chen, Xiao Xue, Xinyi Liu et al. (+4 more)
Autonomous vehicles (AVs) are poised to fundamentally alter personal transportation, offering occupants the freedom to engage in various non-driving-related activities (NDRAs). However, our current understanding of how people might actually use this time in fully autonomous vehicles (FAVs) is limited. Traditional research methods often struggle to capture the influence of diverse travel circumstances and purposes when exploring future scenarios. This paper introduces experience-centered design (ECD) as an approach to investigate potential NDRAs within FAVs by examining the intricate connections between individuals' daily routines, specific travel contexts, and the activities they might undertake in transit. Through a multi-phase study employing participatory techniques that facilitated narrative construction and exploration, including diary studies, scenario scripting, and mixed reality (MR) enactments, we enabled participants to ground speculative future scenarios in their own lived experiences. This process yielded nuanced insights into preferences and behaviors concerning potential NDRAs, alongside the underlying subjective meanings and sociotechnical considerations. Our findings lead us to conceptualize NDRAs not as isolated instances of "travel time use," but as dynamic sequences of interrelated activities deeply shaped by pre- and post-journey contexts. The effectiveness of our ECD approach in bridging current lived experiences with future scenarios was crucial for uncovering these insights. Ultimately, this study reconceptualizes AVs as complex sociotechnical systems that actively mediate human activity and interaction, suggesting a fundamental shift in their role within the urban fabric.
Read the full abstract ▾
All authors Keqi Chen, Xiao Xue, Xinyi Liu, Runjia Tan, Chris Speed, Lee Kwan Min, Chen Lv
Computation and Language
A Native-Reference Phone-Class Geometry for Second-Language Pronunciation Analysis
Tina Raissi, Nhan Phan, Chenxiao Wang et al. (+1 more)
Automatic speaking assessment systems can provide holistic proficiency scores, but often lack interpretable measures that characterize pronunciation quality. We propose a native-reference phone-class geometry for measuring second
language (L2) pronunciation deviation without requiring pronunciation labels, read-aloud
prompts, or matched recordings of the same text from native and L2 speakers. Given a native
speech corpus, we average frame-level self-supervised representations for each context-dependent phone-class and use singular value decomposition (SVD) to derive a compact native-reference coordinate system. For each L2 utterance, we compute the corresponding averages and project them into the native-reference space. We then demonstrate that the distances between L2 and native-reference coordinates for matched phone-classes show consistent negative correlations with holistic speaking proficiency on the Dev subset of the Speak and Improve Corpus 2025 (Spearman's $\rho\!=\!-0.53$) and with pronunciation quality on the learner subset of the English Read by Japanese Students
dataset ($\rho\!=\!-0.34$). These findings suggest that the proposed geometry captures acoustic-phonetic information relevant for proficiency rating while remaining applicable to spontaneous L2
speech without matched native recordings.
Read the full abstract ▾
All authors Tina Raissi, Nhan Phan, Chenxiao Wang, Mikko Kurimo
Computation and Language
How Reproducible Are Evaluation Conclusions? A Self-Audit of LLM-Inferred Prompt Structure
Dipankar Sarkar
Evaluations of LLM systems routinely average over small
prompt sets and report models as a ranked table. We ask how much confidence such a table deserves, using LLM-based
prompt-structure inference as the case study: eight open model variants across five families and 8B to 675B parameters, caching disabled, 293 raw intermediate representations persisted. The measured phenomenon is unstable to begin with. Identical calls do not reliably recover identical structure, with mean node-set Jaccard from 0.39 to 0.96 and 72% of
prompt-model
cells never node-set-perfect.
Auditing the evaluation weakens its conclusions further, and this is our main contribution. Under a joint cluster bootstrap over
prompts, only the bottom of the ranking is firm: the two least reproducible models hold rank in 99% and 86% of replicates, the middle four in 27% to 48%, and the top two in 68% each, so the table identifies the worst model reliably but does not reliably identify the best. Two equally defensible rules for merging repeated campaigns change four of eight rows and move the study-wide headline by 7 percentage points. Checking the inferred structure against ground-truth annotations shows reproducibility cannot be read as accuracy. And four of the eight endpoints were withdrawn within ten weeks of measurement, so the study as specified can no longer be run. Small-sample LLM evaluations can therefore look far more definitive than their evidence supports. We recommend reporting rank stability, per-
cell provenance, executed sensitivity comparisons, raw per-run outputs, and a measurement date alongside any ranking.
Read the full abstract ▾
Computation and Language
Scoring Both Directions: LLMs realize the MRS they cannot reliably parse
Soham Dan
The English Resource Grammar (ERG) is a hand-written computational grammar of English. Given a sentence, its processor, ACE, produces a formal meaning representation called Minimal Recursion Semantics (MRS): a graph of the sentence's predicates and their arguments. The grammar is bidirectional and can also turn an MRS back into an English sentence. \citet{hajdik2019} used the ERG's treebank to build a
benchmark for that generation task, MRS to text, and trained sequence-to-sequence models to solve it. The parsing task, text to MRS, can be tested on the same sentences. We reconstruct their 10K-sentence test split, and score two large
language models, Claude Sonnet~4.5 and Claude Opus~5, in both directions against their trained systems and against ACE, with no task-specific training. Given an MRS and three examples, Opus writes the sentence at 76.3 BLEU, ten points above their system trained on 72k pairs (66.1 BLEU), and comparable to their system trained on a million extra pairs (77.2 BLEU). Sonnet scores 65.7 BLEU, and letting it choose among ACE's own candidate sentences lifts it to 69.6, while a pooled judge that keeps Opus's own sentence among the candidates adds 0.6 points (77.0 BLEU). In the parsing direction, however, the models fall far behind ACE: asked for the MRS of the same sentences, they reach 57.2 (Sonnet) and 65.5 (Opus) F$_1$ on the graph's predicates and arguments against 91.0 for ACE, and exact-match the gold on about 1% of sentences. We characterize the failure modes for the parsing tasks, and conclude that a generation score alone does not show that models understand formal semantic representations.
Read the full abstract ▾
Cryptography and Security
A Data-Driven Analysis of Infostealer Malware Victims
Arttu Paju, Juha Nurmi, David Arroyo et al. (+7 more)
Infostealer malware infects devices worldwide and harvests their most sensitive contents: credentials, browser sessions, private keys, and access certificates. Yet its impact on victims remains difficult to study without an ethical, legal, and curated research
dataset. To close this gap, we build a
privacy-preserving pipeline that turns illicitly sourced infostealer logs into a reproducible research artifact, minimizing sensitive data while preserving measurement utility, and use it to construct a
dataset of 170,298 victims from logs of multiple infostealer families. Analyzing these victims, we find that the most compromised services mirror the world's most popular platforms, with gaming and entertainment services strongly overrepresented. Within the sample we identify compromised credentials for high-value organizations, including law-enforcement domains, government and military services, and all eight Ivy League universities, as well as substantial exposure of security-critical infrastructure and of financial, remote-access, and development platforms. Victims also show widespread credential reuse and significant revictimization risk, overlapping with phishing and ransomware victim populations. We release the first anonymized victim-level infostealer
dataset under controlled access to enable ethical,
privacy-preserving, and reproducible research on information security and victim behavior.
Read the full abstract ▾
All authors Arttu Paju, Juha Nurmi, David Arroyo, Sergio Chica Manjarrez, Fran Casino, Mikko Niemelä, Juuso Itkonen, Joel Scanlan, Constantinos Patsakis, Georgios Smaragdakis
Computational Complexity
Sharp Lovasz-Theta Bounds on Random Graphs
Aaron Potechin and Jeff Xu
It is well known that the \Lovasz-Theta function of a random graph $G(n,\tfrac{1}{2})$ is $\Theta(\sqrt{n})$. More precisely, it is tightly concentrated in the interval \( [\sqrt{n},\, 2\sqrt{n}], \) where the upper bound follows from an explicit dual witness for the associated semidefinite program. Numerical evidence and heuristic arguments suggest that the true value is $(1+o(1))\sqrt{n}$. However, closing this gap has remained a longstanding challenge, resisting existing techniques even in light of recent progress on sharp algorithmic thresholds and non-asymptotic free probability. In this work, we resolve this question by proving that the \Lovasz-Theta function of $G(n,\tfrac{1}{2})$ is $(1+o_n(1))\sqrt{n}$ with high probability, determining its asymptotic value up to vanishing relative error.
Read the full abstract ▾
Artificial Intelligence
Self-Play Pretraining with Zero Data
Aditya Cowsik, Kfir Dolev, Michael Y. Li et al. (+4 more)
Advances in
language modeling have been driven by scaling pretraining on ever more data. Yet, the training data is still largely curated on the model's behalf. A more general approach to pretraining would let the model learn to generate the data most useful for its own improvement. This would provide an effectively unbounded source of training data, limited by compute rather than human knowledge. We introduce Self-Play Pretraining with Zero Data, an initial proof-of-concept towards realizing this
vision. Our procedure casts synthetic data generation as a search over the space of all computable structure, taking inspiration from Solomonoff induction. Starting from random initialization, two models learn in tandem: a generator proposes programs interpreted by a universal Turing machine, generating byte sequences, while a learner autoregressively predicts these byte sequences. The learner is trained with standard cross-
entropy, while the generator is trained with reinforcement learning to produce sequences at the frontier of the learner's capabilities, yielding an adaptive curriculum. A universal Turing machine gives us a search space over all computable data-generating processes, imposing little domain-specific structure, and self-play searches over this space for useful training data. We test whether zero-shot performance on natural data improves predictably with self-play compute; this is a clean test of transfer since neither generator nor learner is trained on natural data. Across several natural
datasets, zero-shot loss exhibits predictable scaling in compute. The models also exhibit in-context learning, and discover recognizable mathematical sequences during training.
Read the full abstract ▾
All authors Aditya Cowsik, Kfir Dolev, Michael Y. Li, G. Bruno De Luca, Nourya Cohen, Noah D. Goodman, Yoav Levine
Programming Languages
Lifting the Preprocessor with Oxidize: Structure-Preserving C-to-Rust Translation (Technical Report)
Robbe De Greef, Théo Engels, Felix Van den Broucke et al. (+2 more)
This technical report accompanies our EuroSys 2027 paper "Lifting the Preprocessor with Oxidize: Structure-Preserving C-to-Rust Translation" (DOI 10.1145/3842654.3848533). Oxidize is a C-to-Rust translator that retains C macros as Rust macros instead of expanding them away, so that the translated code keeps the abstractions its developers wrote. The report collects material the paper cites but has no room for: the translator's intermediate representation, pass structure and back-end emission; the details of macro typing through helper traits and the generic cast macro; the sources and pinned revisions of the nine evaluated C codebases; the per-codebase macro population and how macros are attributed to classes; a roadmap from structure-preserving translation toward safe Rust; the performance overhead study and its methodology; and the configuration and
prompt used for the LLM-based baselines.
Read the full abstract ▾
All authors Robbe De Greef, Théo Engels, Felix Van den Broucke, Ken Hasselmann, Antonio Paolillo
Distributed Computing
KernelOPT: Dispatch-Aware Agentic Search for GPU Kernel Optimization
Aheli Poddar, Sanskar Prasad, Arindam Samanta et al. (+3 more)
Deep learning inference and training performance depends critically on GPU kernel efficiency. Modern compilers such as PyTorch Inductor automatically generate GPU kernels from high-level model code, but frequently underperform expert-written implementations by wide margins. Recent LLM-assisted kernel optimizers can close this gap for standalone kernels, yet treat compiled models as black boxes, generally optimizing individual standalone kernels without respecting the compiler's structural decisions or verifying the model end-to-end. We present KernelOPT, a multi-
agent system that treats compiled models as structured artifacts. It preserves vendor library calls (cuBLAS, cuDNN) and exclusively targets generated Triton sub-kernels using five profiling-guided LLM
agents. A four-gate verification cascade applies static validation, multi-seed correctness checking, model-level float64-fallback verification, and performance gating ($\gamma{=}1.03$) to filter candidates and verify the re-stitched model end-to-end. When candidates fail verification, the system preserves the compiler baseline. The system accepts PyTorch nn Modules, standalone Triton kernels, and Helion kernels. Evaluated on 250 KernelBench problems (100 Level 1, 100 Level 2 and 50 Level 3) on NVIDIA H200, KernelOPT achieves
geometric mean speedups over torch compile of 1.40$\times$ (L1), 1.15$\times$ (L2), and 1.07$\times$ (L3) across all kernels, including fallback cases. Optimized-only geomeans (excluding cases where verification gates preserve the compiler baseline) are substantially higher: 2.54$\times$ (L1: 36/100), 1.84$\times$ (L2: 23/100), and 1.37$\times$ (L3: 11/50), reflecting where the optimizer achieves meaningful leverage.
Read the full abstract ▾
All authors Aheli Poddar, Sanskar Prasad, Arindam Samanta, Subha Chakraborty, Vishal Goyal, Rohit Singh Rathaur
Game Theory
Can Labor Markets Function in the Age of AI? The Evaluation Bottleneck in Hiring
Itai Ashlagi, Ramesh Johari, Jon Kleinberg et al. (+1 more)
AI-assisted job-search tools have become increasingly popular by making it easier to find and apply to jobs. But by making it easier for applicants to generate and tailor application materials, they can also reduce how informative those materials are about applicant fit. We study this tradeoff in a hiring
market where applicants differ in experience and latent match quality and firms use noisy application materials to decide whom to screen. We ask how AI affects downstream screening and hiring, and which applicants are most adversely affected. As application materials become less informative, a
Bayesian firm rationally relies more heavily on coarse observables such as prior experience. Among the four applicant types defined by experience and compatibility for the job, inexperienced-compatible applicants are the most exposed: they lack observable experience and lose the individualized information that could distinguish them from other inexperienced candidates. When screening is costly, these changes can also generate inefficient screening failures in which firms screen no applicants or screen only experienced applicants. We then show that multistage hiring can arise as an endogenous firm response: a relatively inexpensive intermediate assessment allows firms to acquire new evidence of fit before costly full screening. This can restore screening opportunities that disappear under one-stage hiring and give inexperienced-compatible applicants a path to screening. Our results show how AI can shift the central friction in hiring from submitting applications to obtaining credible evaluation, creating entry barriers for high-fit workers without prior experience. Multistage hiring can endogenously arise in response, restoring evaluation opportunities that would otherwise disappear and helping preserve
market functioning.
Read the full abstract ▾
All authors Itai Ashlagi, Ramesh Johari, Jon Kleinberg, Anushka Murthy
Distributed Computing
KREX: Concurrent Kernel Benchmarking on Shared GPUs via Region-Granular Exclusivity
Tianyu Feng, Haoxuan Yu, Tianyuan Wu et al. (+8 more)
LLM
agents automate GPU kernel optimization by repeatedly composing candidates and measuring their duration on real GPUs. Existing systems preserve measurement fidelity by reserving a GPU for an entire
agent session or benchmarking command. However, this results in poor utilization because only a small fraction of command execution requires exclusive GPU access. Sharing GPUs could recover this idle capacity, but introduces contention that compromises measurement fidelity and misdirects the
agent's search. We present KREX, a runtime for concurrent kernel
agent benchmarking with region-granular exclusivity. KREX lets
agents mark critical regions involving timing-sensitive operations within a benchmarking command. The runtime then enforces exclusivity within marked regions and allows concurrent execution outside them, achieving high throughput while preserving measurement fidelity. To enforce in-region exclusivity, KREX blocks new competing GPU submissions and drains outstanding work before freezing sibling processes and isolating CPU cores, protecting both GPU execution and the host threads that drive measurements. To maximize off-region concurrency, KREX reuses GPU contexts in persistent context processes to avoid repeated, node-wide serialized context creation. We evaluate KREX on NVIDIA and AMD GPUs. Compared with command-granular exclusivity baselines, KREX delivers up to $3.4\times$ the benchmarking throughput with a negligible p95 timing inflation of $0.30\%$, $1.58\%$, and $3.90\%$ for kernels longer than 10 ms, 1 ms, and 0.1 ms, respectively.
Read the full abstract ▾
All authors Tianyu Feng, Haoxuan Yu, Tianyuan Wu, Lingyun Yang, Daocheng Ying, Yuxiao Wang, Ruibo Fan, Yinghao Yu, Guodong Yang, Liping Zhang, Wei Wang
Robotics
M3GD: Multi-Modal Multi-View Geometric Diffusion for Camera–LiDAR Novel View Synthesis
Yang Zhou, Jiuhong Xiao, Shizhao Ye et al. (+3 more)
Robotic novel view synthesis (NVS) must recover both visual appearance and metric 3D structure, yet most generative NVS methods rely only on images, overlooking
LiDAR, a complementary sensor common on robotic platforms. We present M3GD, a Camera–
LiDAR multimodal representation for generative NVS that composes independently pretrained 2D image and 3D point-cloud foundation models without separately pretraining a cross-modal translator. We show that, after camera projection, frozen
LiDAR and image features exhibit substantial shared spatial structure, providing a natural cross-modal representation. M3GD conditions generation on
LiDAR through this structure: it combines explicit geometry statistics with learned point-cloud descriptors into view-aligned packets on the image-latent grid, injected through a lightweight residual adapter into a multi-view flow-matching generator whose latent space, decoders, and training objective remain intact. On the GrandTour
dataset, M3GD improves target-view RGB and depth synthesis over an image-only version of the same backbone. Ablations show that the gains come from pixel-aligned
LiDAR content and that target-view
LiDAR acts as a
geometric query linking the requested view to source observations. Deployment on a ground
robot demonstrates practical real-world operation, with a configurable quality–cost trade-off controlled by the number of Euler integration steps.
Read the full abstract ▾
All authors Yang Zhou, Jiuhong Xiao, Shizhao Ye, Long Quang, Carlos Nieto-Granda, Giuseppe Loianno
Software Engineering
Era by Eon: Benchmarking Enterprise Agents on Hidden Knowledge
Benjamin Gruenbaum, Doron Porat, Assaf Natanzon et al. (+3 more)
In the Era by Eon
benchmark, each question states the rules for its answer, and code computes the answer from a generated company's data. When
agents can run code, the four strongest models each answer 22 to 25 of 27 such questions, so the
benchmark barely separates them. We add eight question templates that depend on hidden facts. No question or document states a hidden fact, and the records that seem to hold it show something else. Other data implies it. For example, the sales system says a customer dropped a purchase because of timing. On a recorded call, the customer blames an outage. For each generated company, code fills each template and computes an exact answer without a
language model. We evaluate 12
agents. Each pairs a model with an
agent program, which connects it to the company's systems. The best
agent answers 18 of its 24 attempts, three per question, correctly. Four of the six models answer at most 6 of 24 with any program. The hardest questions require picking one of several similar records, such as which of three renewal offers a customer signed. All
agents together answered two such questions correctly in only 1 of 84 attempts.
Read the full abstract ▾
All authors Benjamin Gruenbaum, Doron Porat, Assaf Natanzon, Roy Zavida, Chen Dinachi, Or Itzahary
Artificial Intelligence
SciWalker: Synthesizing Scientific Coding Problems with Operator Graphs and Execution Feedback
Chenxi Li, Wenxuan Zeng, Yun Luo et al. (+4 more)
Improving the scientific coding capabilities of large
language models (LLMs) requires high-quality training data. However, such data remain scarce because manually authoring realistic problems is costly and time-consuming, while systematically covering diverse scientific domains and algorithmic combinations remains challenging. To address this, we introduce SciWalker, a framework for synthesizing scientific coding problems through operator-chain sampling and execution feedback. The framework combines scientific library interfaces with operation modes to instantiate operators, organizes them into operator graphs, and samples operator chains as computational workflow cues. Guided by these cues, we adopt LLMs to generate scientifically grounded problem statements, reference solutions, and tests, with failed generations iteratively repaired using execution feedback. By combining structured workflow composition with verification and quality review, SciWalker enables scalable task generation while promoting scientific grounding, computational diversity, and executability. Using this framework, we construct 8,178 high-quality problems spanning 5 scientific domains and 32 subdomains. To evaluate their training utility, we conduct reinforcement learning on Qwen3.5-9B using the GSPO
algorithm. This training improves SciCode subproblem accuracy by 9.9 percentage points, from 29.3% to 39.2%, with gains across scientific code generation, code repair, and
reasoning benchmarks. The code for SciWalker is available at https://github.com/lichenx1/SciWalker.
Read the full abstract ▾
All authors Chenxi Li, Wenxuan Zeng, Yun Luo, Fangchen Yu, Peng Ye, Yu Cheng, Jun Zhang
Data Structures and Algorithms
Strongly Refuting Semirandom Linear Systems in Subexponential Time
Pravesh K. Kothari, Andrew D. Lin and Peter Manohar
In this paper, we consider the problem of refuting $\mathbb{F}_2$-linear equations with random right-hand sides. Formally, we give a sub-exponential $2^{O(n/\log n)}$-time randomized
algorithm that takes as input an arbitrary $m \times n$
matrix $A$ and a uniformly random vector $b \in \mathbb{F}_2^m$, and outputs a witness showing that no assignment satisfies more than a $\frac{1}{2}+\epsilon$ fraction of the equations provided that $m \geq 2^{O(n/\log n)}$. The setting above is the semirandom refutation variant of the famous work [BKW03] that gives a $2^{O(n/\log n)}$-time search
algorithm for the learning parity with noise (LPN) problem with $m \geq 2^{O(n/\log n)}$ equations. Building on the search
algorithm of [Lyub05], we also give a $2^{O(n/\log \log n)}$-time refutation
algorithm that succeeds with only $m \geq n^{1 + \gamma}$ equations, for a small constant $\gamma$. Finally, we prove that our
algorithm is not captured by the sum-of-squares hierarchy by proving a degree-$\Omega(n)$ sum-of-squares lower bound, showing that ”[BKW03]-style”
algorithms achieve better runtime than can be done under sum-of-squares. We thus obtain a natural example of a noise-tolerant signal recovery problem that exhibits a nontrivial gap between the performance of efficient
algorithms and that of those based on the sum-of-squares hierarchy.
Read the full abstract ▾
Artificial Intelligence
NNV3: Expanding Neural Network Verification to New Architectures and Domains
Anne M. Tumlin, Samuel Sasaki, Ben Wooding et al. (+8 more)
We present NNV3, the latest version of the Neural Network Verification (NNV) tool, a MATLAB framework for formal verification of deep learning models and learning-enabled cyber-physical systems. Building on the set-based reachability foundation of NNV 1.0 (FFNNs, CNNs, NNCS) and NNV 2.0 (RNNs, SSNNs, neural ODEs), NNV3 introduces new members of the
Star-set family: ModelStar for verifying networks under weight perturbation, VolumeStar for
video and 3D volumetric inputs, and GraphStar for graph neural networks. A conformal-inference-based probabilistic reachability mode complements sound analysis for problems where deterministic verification is intractable, while FairNNV certifies counterfactual and individual
fairness properties over continuous input regions. NNV3 introduces new
benchmarks for malware detection, graph-based power-system models, medical imaging, variable-length time series data, and action recognition. NNV3 also incorporates tutorials and developer guides through a unified documentation site. This paper details these major updates, demonstrating NNV's maturation into a comprehensive, robust, and accessible verification tool for a diverse range of AI systems.
Read the full abstract ▾
All authors Anne M. Tumlin, Samuel Sasaki, Ben Wooding, Diego Manzanas Lopez, Muhammad Usama Zubair, Navid Hashemi, Hongchao Zhang, Waseem Abbas, Ipek Oguz, Meiyi Ma, Taylor T. Johnson
Numerical Analysis
Optimal Recovery for Solving Variational Problems
Ting Wang, Gideon Simpson and Jaroslaw Knap
In science and engineering, many physical laws and scientific principles naturally arise as variational problems of minimizing an energy functional over an appropriate functional space. In many cases, it is more advantageous to directly discover the minimizer of the energy functional than to solve the associated Euler-Lagrange equations. Conventional numerical solvers, such as the finite-element method (FEM), often lack the flexibility to incorporate prior knowledge or noisy observational data. In recent years, machine learning approaches, particularly kernel-based methods, have attracted growing
attention in scientific computing. Unlike FEM, which requires domain discretization and mesh generation, kernel-based methods construct solutions from scattered nodes, thereby avoiding the complexity of meshing, especially in high-dimensional or geometrically complex domains. This works presents a two-step procedure for variational energy minimization based on the optimal recovery formulation in a reproducing kernel
Hilbert space (RKHS), providing a unified framework for seamlessly incorporating both physical constraints and noisy data. On the computational side, we employ the sparse Cholesky decomposition for Matérn kernels to alleviate the well-known cubic complexity bottleneck of kernel methods. On the theoretical side, we rigorously establish the existence and convergence theory of the proposed method using $\Gamma$-convergence theory. Numerical experiments on
benchmark problems demonstrate the efficiency, robustness and accuracy of the approach.
Read the full abstract ▾
Artificial Intelligence
Style, Not Self: Surface Cues Explain Zero-Shot Code Attribution by Large Language Models
Ehsan Barkhordar and Surendrabikram Thapa
If a
language model can recognize code it wrote, it may favor that code as a judge, and instances of one model monitoring each other could collude. We test this zero-shot on current commercial models. Five LLMs generate solutions to MBPP, HumanEval, and DS-1000, seven more to MBPP, and models act as evaluators in four tasks: picking their own solution from a pair, judging whether a single solution is their own, identifying which of two solutions a named model wrote, and judging quality blind. In the single-solution task, balanced accuracy is 49-58% for all 15 model-
benchmark combinations, while raw accuracy (38-67%) mostly reflects how readily a model claims authorship. In the pairwise task, accuracy across 14 evaluator-opponent combinations correlates at r=0.93 with how often the evaluator's solution is longer. Attribution to a named model succeeds on some pairs and is consistently inverted on others. A rule-based normalization that strips docstrings, comments, type hints, and local names preserves Pass@1 and leaves ten of twelve re-tested results at chance; the other two follow a length difference it leaves, although a trained classifier still separates most normalized pairs. Claude Haiku's self-preference also disappears. We recommend reporting balanced accuracy, heuristic baselines, and label consistency.
Read the full abstract ▾
Machine Learning · Cross-listed from cond-mat.mtrl-sci
From Processing to Functionality: Engineering Accessible Material States in Cu-Embedded SiO$_x$ Memristive Devices
Tobias Gergs, Rouven Lamprecht, Sahitya Yarragolla et al. (+5 more)
Resistive switching in
oxide-based devices is widely governed by
stochastic defect processes, yet a predictive link between fabrication conditions and functional behavior remains elusive. Here, we establish a multiscale framework connecting
plasma-defined deposition conditions to macroscopic device functionality in sputtered SiO$_x$/Cu/SiO$_x$-based systems. By combining large-scale statistical analysis of more than 50,000 experimentally characterized devices with physics-based
plasma and atomistic simulations, we show that device behavior does not emerge from deterministic process-to-performance mappings, but from a probabilistic cascade spanning defect formation, defect-state
evolution, and functional-regime emergence. Data-driven clustering reveals a continuous functional state space composed of operational switching types, while inverse modeling identifies the reconstructed oxygen-vacancy density as an effective latent descriptor capturing the combined influence of structural disorder and defect
topology. This latent descriptor is strongly coupled to both Cu redistribution and electrical response, linking otherwise hidden material properties to observable device characteristics. Furthermore, macroscopic switching behavior is argued to arise from ensemble integration across spatially heterogeneous subdomains, providing a physical explanation for the pronounced variability of large-area devices. These findings shift the perspective from deterministic defect engineering toward probabilistic defect-state design and establish a physically grounded framework for understanding and controlling functional variability in such
oxide-based systems, such as memristive or resistive-switching devices.
Read the full abstract ▾
All authors Tobias Gergs, Rouven Lamprecht, Sahitya Yarragolla, Ole Gronenberg, Luca Vialetto, Hermann Kohlstedt, Thomas Mussenbrock, Jan Trieschmann
Data Structures and Algorithms
Fast Spectral Signing for Vector Balancing
Xiaoyu Li
The Komlós
conjecture, now a
theorem, asserts that whenever the columns of a
matrix $A\in\mathbb{R}^{m\times n}$ have Euclidean norm at most one, some signs $\varepsilon\in\{-1,1\}^n$ make every coordinate of $A\varepsilon$ bounded by an absolute constant. Guo, Fang, and Lu gave the first
polynomial-time
algorithm for finding such signs, a deterministic spectral signing procedure with discrepancy $8272$ and running time $O((mn^9+n^{10})\log(m+n))$. We give a deterministic
algorithm that finds signs with $\|A\varepsilon\|_\infty<99$ using $O(mn+n^{\omega+2}\log^3 n)$ arithmetic operations, where $\omega>2$ is any fixed attainable
matrix-multiplication exponent; with the current bounds on $\omega$ this is $\widetilde O(mn+n^{4.372})$. Our
algorithm uses the same framework: it rounds a single fractional coloring and watches all rows through the top
eigenvalue of a Gram
matrix of energy-corrected barriers. Steps follow flat directions, rescaled so that no barrier near its threshold moves faster than a constant, and the regularizer grows as coordinates freeze; together these bound the number of updates by $O(n^2\log n)$. A weak quadratic charge on the tracked row sums leaves $O(n\log^2 n)$ rows to evaluate at any time, and a motion clock bounds when any other row could approach its barrier. Each update is a short sequence of
matrix products. Its direction is read off by conditional expectations from a
polynomial soft projector, its small constraint residual is repaired in affine row representations, and one identity accounts for every change of representation. For rational input the
algorithm has
polynomial bit complexity.
Read the full abstract ▾
Computer Vision
ConPro: Contrast Projection Pretraining for Label-Efficient Vessel Segmentation in DSA Sequences
Xinge Guo, Yuanhao Wang, Liqi Shu et al. (+2 more)
Dense vessel annotation in digital subtraction angiography (DSA) is labor-intensive, yet every unlabeled sequence records how contrast passes through the vessels. Semi-supervised methods take their targets from the current model, and generic self-supervised pretexts reconstruct static appearance, so this signal goes unused. We propose ConPro, a self-supervised pretraining scheme whose target is a contrast projection, the normalized drop of every pixel below its temporal median over the sequence. On DIAS and DSCA, with 10%, 20% and 50% of the training cases labeled, ConPro improves on training from scratch at every label fraction and is the best of the compared methods on DSCA at 20% and 50% labels. Controlled comparisons show that the gain comes from the target. A temporal-median target with the same input, loss and budget stays at scratch level, and using the projection directly instead of learning it, as an input channel or a pseudo-label, helps little or hurts. ConPro provides pretrained weights without changing the
segmentation architecture, so it combines with semi-supervised training, and UniMatch, the strongest baseline, gains 0.5 to 2.0 Dice and 0.9 to 2.3 clDice at every label fraction when started from ConPro weights, reaching 75.4 Dice on DIAS and 81.3 on DSCA.
Read the full abstract ▾
All authors Xinge Guo, Yuanhao Wang, Liqi Shu, Yang Liu, Min Xu
Computational Complexity · Cross-listed from math.OC
A Polynomial-Time Test for Peak-Oriented Rationalizability
Taotao He and Runfa Hu
We study the computational complexity of peak-oriented rationalizability, a survey based revealed-preference test introduced by Seror (2026). We provide a
polynomial-time
algorithm for testing rationalizability and recovering a utility function, establishing that peak-oriented preference elicitation is computationally tractable. In contrast, we show that computing the peak-oriented Houtman-Maks index is NP-hard. These results delineate the precise computational boundaries of peak-oriented revealed-preference analysis.
Read the full abstract ▾