跳到正文
研踪PaperTrail

YOUR RESEARCH, IN SIGHT

让下一篇重要论文,不再错过。

覆盖计算机全学科,以 AI 为快捷入口。关注方向、作者和关键词,把发现变成持续的研究积累。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+0新增论文
+0其中 AI 相关
+1已有论文修订
+100新增 AI 导读

arXiv 最近完成扫描:2026-11-08 04:03 · 全站最近入库:2026-11-07 17:43各信源进度 →

统计口径与数据新鲜度

统计 2026-11-07 04:12 — 2026-11-08 04:12(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-08 04:03最近发现新增版本:2026-11-07 17:43库内论文最新更新时间:2026-11-06 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

17,100 已收录论文14,661 AI 相关4,056 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 17,100 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-08 04:02(北京时间)
新论文 · v1arXiv:2611.04859

Bankruptcy Rules for Strategic Agents

Yosef Zumer, Erel Segal-Halevi, David Sarne

原文摘要

Bankruptcy rules are rules for dividing an insufficient estate among people with different claims. Existing rules assume that the claims are publicly known. When this is not the case, claimants have a strong incentive to claim more than they are due, as bankruptcy rules give larger allocations to claimants with larger claims. A remedy often used by legal systems is to make over-reporting costly by requiring evidence and imposing penalties. But this remedy also increases the legal expenses of proving true claims, which might result in under-reporting. Encouraging true reporting requires fine-tuning of the legal costs. This paper incorporates the costs of supporting both true and false claims into the bankruptcy model. Claimants incur costs for the true and false parts of their claims, with false claims costing at least as much per unit as true claims. The goal is to set cost rates that induce claimants to report their true entitlements, neither more nor less. Whether this is possible depends on the allocation rule. The proportional and constrained equal awards rules cannot guarantee truthfulness at any positive true-claim cost rate; the same holds for constrained equal losses with at least three claimants. For $N\ge2$ claimants, the rule TAL-1/N from the parameterized Talmud family induces truthfulness exactly when the true-claim cost rate is at most 1/N and the false-claim cost rate is at least 1-1/N. This rule is optimal in the sense that its truthful cost region contains that of every piecewise smooth allocation rule: it gives the legal system the maximum possible flexibility in setting the legal costs. For two claimants, TAL-1/2 (aka Contested Garment rule) uniquely attains this optimal region.

econ.TH · cs.GT

版本更新 · v2arXiv:2610.25837

Exact minimum Birkhoff decompositions of doubly stochastic matrices with finite precision

András Czégel

原文摘要

The minimum Birkhoff decomposition problem asks for a representation of a doubly stochastic matrix as a convex combination of as few permutation matrices as possible. This NP-hard problem arises in the scheduling of switches in data centers and satellite systems, in random assignments in economics and in the statistics of rankings. We consider doubly stochastic matrices whose entries are given with a fixed number of decimal digits and look for exact decompositions whose weights have the same precision. We propose a parallel method with three parts. For matrices built from few permutation matrices, the first part reads the weights from the frequencies of the entries and places them on the matrix positions by a rule that, given the correct weights, never fixes a position wrongly. The second part computes lower bounds from pairs of rows or columns, which remain valid for real weights, and from certificates of a satisfiability solver. For matrices built from many permutation matrices, the third part runs a beam search over steps that each make at least one entry zero. On 375 test instances with up to 100 rows, the method proves optimality for 208 instances, and 197 of these proofs also hold for real weights. Of the 190 instances built from few permutation matrices, 187 are solved to proven optimality, 180 of them within one second. Compared with the best exact decompositions known before, the new decompositions are shorter for 278 instances and never longer.

cs.DS

版本更新 · v3arXiv:2607.27829

Approximate Dual Separation for the Cluster LP: a 1.387-approximation for Correlation Clustering

David García-Soriano, Antoine Schohn

原文摘要

We give a $(1.3865+ε)$-approximation for correlation clustering on complete graphs, improving the previous best factor of $1.485+ε$ of Cao et al. (STOC'24). Our first main contribution is an efficient weak separation oracle for the cluster-LP dual. Given signed vertex weights $q$, it either finds a set $S$ with $q(S)>cost(S)$ or certifies that $q/(1+ε)$ is dual feasible, where $cost(S)$ measures the correlation clustering disagreements attributed to $S$ in any clustering in which $S$ is a cluster. Via the ellipsoid method, this yields $(1+ε)$-approximate primal and dual solutions for the fractional cluster LP in deterministic time $2^{poly(1/ε)}n^{O(1)}$ . The separator works directly on the original instance, without global preclustering: a novel localization argument restricts the search to a small universe, where weak regularity handles the resulting dense quadratic minimization. Complementing this result, we prove that exact dual separation and cluster-LP optimization are NP-hard, even for complete unweighted instances. Our second main contribution is a new rounding of the cluster LP. It combines cluster-based rounding with a continuous conditional pivot rule, and its analysis relies on single variance inequality with explicit weights. This bounds the cluster-LP integrality gap by $1.3865$, near its known lower bound of $4/3$, and gives a per-instance primal--dual certificate of approximation. Finally, we extend our separator to obtain a $(1.92+ε)$-approximation for seeded correlation clustering (where each cluster may contain at most one seed from a prescribed seed set), and to bounded-weight instances, yielding a deterministic polynomial-time approximate implementation of the cluster-insertion primitive used in combinatorial correlation clustering.

cs.DS

版本更新 · v5arXiv:2609.31328

A Constructive FPT Algorithm for Integer Cone Optimization with Convex Costs

Klaus Jansen, Felix Ohnesorge, Björn Schumacher

原文摘要

We give a deterministic fixed-parameter algorithm for integer cone optimization with convex costs. Given $τ$ rational polytopes in $\R^{d+k}$, we combine generators whose first $d$ coordinates are integral and whose remaining $k$ coordinates may be fractional. Each generator has a convex cost depending only on its integer coordinates. We minimize the total cost of nonnegative integer combinations subject to arbitrary rational linear constraints on the full typewise aggregates and generator counts. Our algorithm runs in time \[ 2^{τ\log(τ+1)\,2^{O(d)}}\cdot |I|^{O(1)}, \] where $|I|$ is the total binary input length. It constructs an optimal representation using at most $2^{2d+1}$ distinct generators per type. The number $k$ of continuous coordinates contributes only to the polynomial input factor. For a single generator type, the running time becomes $2^{2^{O(d)}}\cdot |I|^{O(1)}$. Applications include constructive FPT algorithms for Cone and Polytope Intersection, high-multiplicity bin packing, vector bin packing, and makespan minimization on uniform and unrelated machines. The double-exponential dependence on $d$ is tight for Point-in-Cone and both bin-packing problems assuming $\mathrm{NP}\nsubseteq\mathrm{SUBEXP}$. The mixed-integer formulation also yields additive EPTASs for makespan minimization, machine covering, and envy minimization on identical machines, and additive schemes fixed-parameter tractable in $1/\varepsilon+τ$ on uniform machines.

cs.DS

版本更新 · v2arXiv:2610.13447

Oído: Real-Time Open-Vocabulary Speech Recognition on a $5 Microcontroller without a Neural Accelerator

Daniel Varela Sánchez, Guillermo Martín-Coello Juárez

原文摘要

Speech recognition on low-cost microcontrollers is, in practice, limited to keyword spotting or a fixed list of commands. We present Oído, an inference engine and a family of models that run open-vocabulary English speech recognition entirely on an ESP32-S3 (240 MHz Xtensa LX7, 8 MB of PSRAM, 16 MB of flash, no neural accelerator) faster than real time on one core. Version 1 of this work ran a 13 M-parameter Conformer-CTC at 1.97x the duration of the audio. We measured on the board that the bound was memory traffic and per-frame cost, not arithmetic: external memory reads at 89 MB/s (PSRAM) and 32 MB/s (flash), and a streaming recognizer re-reads every weight for every chunk. Version 2 combines a model built for that memory system (80 ms frame stacking, a 64-channel front end, 12 or 16 blocks, int4 weights that mostly fit in PSRAM, fine-tuned from the version 1 model) with engine changes that overlap the weight stream with compute (an asynchronous data-cache preload), keep work buffers in SRAM and make the decoder cheap. On a physical board the streaming real-time factor falls from 1.77 to 0.54 (variant B) and 0.72 (variant A), the final text appears 259 ms (B) or 431 ms (A) after the end of speech with audio fed at real-time speed, and the host build and the firmware produce identical transcripts. Variant A reaches 7.1%/16.4% word error rate on LibriSpeech test-clean/test-other in streaming mode with 0.64 s chunks and the on-chip language model (4.6%/10.7% with full context). Code, models and the raw board measurements are released.

cs.SD · cs.CL · eess.AS

版本更新 · v3arXiv:2502.10353

Matching with Choice: Menu Design for Patient--Provider Assignment

Naveen Raman, Holly Wiberg

原文摘要

High-quality matches between patients and primary care providers improve downstream health outcomes, yet provider turnover breaks these matches and forces patients to be reassigned. Health systems facing this problem must decide not only which providers to recommend, but how much choice to offer. Direct assignment avoids competition for scarce provider capacity but relies on noisy estimates of patient preferences; broader choice allows patients to correct these estimates using private information but can create costly coordination failures. We study this tradeoff through the design of fixed, personalized menus from which patients choose providers. We show that constructing the optimal menu is NP-hard and establish an information-theoretic lower bound. We find that offering each patient a single provider matches this bound up to a constant factor, while unrestricted choice can perform arbitrarily poorly. However, we show that additional choice improves on single-provider assignment when the system cannot reliably distinguish among a patient's alternatives. We formalize this tradeoff through two forms of loss: menu loss, which arises when menus offer too few options, and coordination loss, which arises when scarce capacity is exposed to too much choice. Motivated by this decomposition, we develop the Scenario-Averaged Marginals (SAM) algorithm, which tailors menus based on provider shadow prices so choice is offered only when utility exceeds the capacity cost. We identify sufficient conditions which SAM's regret matches the lower bound, namely when patients have valuable alternatives and offered menus don't create competition for scarce capacity. In a semi-synthetic environment calibrated to a provider network using Medicare data, SAM improves total utility by up to 19% over single-provider assignment as preference uncertainty grows, while improving utility for the least-served ZIP codes.

cs.CY · cs.LG · math.OC

版本更新 · v2arXiv:2611.02476

GigaSpeech 3: Scaling Multi-Dialect Arabic Speech Recognition with Weakly Labeled Data

Junzhe Liu, Yujie Tu, Yifan Yang, Peng Wang, Haoran Wang, Guodong Lin, Leyan Liao, Chengquan Zhang 等 16 位作者

原文摘要

Dialectal Arabic speech recognition remains constrained by the scarcity of dialect-resolved transcribed speech despite the abundance of web audio. We introduce GigaSpeech 3, a corpus of 39,000 hours and 10 million weakly transcribed speech segments covering Algerian, Egyptian, Iraqi, Saudi, and Syrian Arabic. Starting from 60 hours of manual transcription per dialect, we train labeling models using speech-recognition-biased self-supervised learning and apply them to dialect-matched web audio. Data selection and four rounds of noisy-student refinement for Saudi and Syrian Arabic yield the final corpus. We validate its utility through dialect-specific and multi-dialect speech recognition training and cross-domain evaluation. On GigaSpeechBench, the final dialect-specific models outperform their labeling models across all five dialects and achieve a macro-average word error rate of 23.86%, a 16.6% relative reduction from the strongest third-party system covering all five dialects, while outperforming the best third-party result on three dialects. A multi-dialect model using self-predicted dialect identities achieves a macro-average word error rate of 25.51% while also supporting Modern Standard Arabic. Across eight conditions from three external corpora, a GigaSpeech 3-trained Zipformer achieves the lowest word error rate among six evaluated models in every condition, while adapting the Qwen3 speech recognizer on GigaSpeech 3 improves performance across all eight conditions. We release the corpus and recipes as a foundation for dialect-aware Arabic speech processing.

cs.CL

新论文 · v1arXiv:2611.04852

Faster Regular Expression Matching via Two-Dimensional Tabulation

Philip Bille, Inge Li Gørtz

原文摘要

Regular expression matching asks whether a string of length $n$ belongs to the language described by a regular expression of length $m$. We give an algorithm that solves this problem in linear space and $O(nm \log \log n/\log^2 n + n + m)$ time. This improves the leading term of the previous best worst-case constant-alphabet time bound by a factor of $\sqrt{\log n}$. The key new technique is a two-dimensional tabulation specialized to the regular expression.

cs.DS

版本更新 · v2arXiv:2610.34534

Multimodal Socially Aware Framework for Human-Robot Interaction in Virtual Reality

Richard Xu, Dakarai Crowder, Alexis E. Block, Wenzhen Yuan

原文摘要

Social robots must coordinate speech and movement while interpreting multimodal human input. We present a multimodal framework that integrates speech, vision, and touch to generate contextually appropriate robot speech and movement. We evaluated the framework in virtual reality with 18 participants across five social interaction scenarios, comparing its performance against a human-teleoperated baseline. Although participants rated the autonomous system above the neutral midpoint for both naturalness and social appropriateness, the teleoperated baseline received significantly higher ratings on both measures. Behavioral coding and qualitative feedback revealed that conversational timing, clarification of ambiguous requests, and spatial coordination were important factors contributing to this performance gap. These findings highlight key challenges in developing autonomous robots capable of natural, multimodal social interaction.

cs.RO

版本更新 · v2arXiv:2611.03301

An Axiomatic Framework for Reinforcement Learning in Open Multi-Agent Systems

Jianhong Wang, Yang Li, Samuel Kaski, Jonathan Lawry

原文摘要

Open multi-agent systems, where only a subset of agents are controllable, are central to real-world domains such as smart grids, yet lack a principled foundation for reinforcement learning algorithm design. We study this setting through n-agent ad hoc teamwork (NAHT), a recent framework for learning in open multi-agent environments. We propose an axiomatic framework that derives value function learning from the Shapley axioms (Efficiency, Symmetry and Linearity), treating them as structural constraints rather than heuristic design choices. This formulation builds on a novel NAHT decomposition, which characterises the fundamental difference between open and fully controllable multi-agent systems, and establishes a cooperative game-theoretic foundation for learning. We further show that enforcing these axioms on learning individual value functions recovers the Shapley value for Dec-POMDPs, providing a principled bridge between reinforcement learning and classical cooperative game theory. Building on this framework, we introduce Shapley Machines and Banzhaf Machines, two generic algorithmic templates that can be instantiated with standard reinforcement learning methods. When applied to strong base algorithms such as IPPO and POAM, our methods consistently improve learning efficiency and generalisation to unseen agent types and conventions across NAHT benchmark tasks. The code of experiments is published on https://github.com/hsvgbkhgbv/axiomatic-rl-naht.

cs.LG · cs.AI · cs.MA

新论文 · v1arXiv:2611.04848

Amortized Nonlinear Variable Selection with Prior-Data Fitted Networks

Jin Zhu, Junxian Zhu

原文摘要

Variable selection is an important task for interpreting potentially complex systems in fields such as biology, business, and sociology. The importance of variable selection has attracted considerable attention in statistics and machine learning. In this paper, we are mainly interested in model-agnostic variable selection for identifying variables that have general nonlinear dependence on the response. We propose MambaPFN, short for Model-Agnostic Markov BlAnket selection with Prior-data Fitted Networks, which is built upon the Transformer, a building block of many popular large language models. Specifically, we consider a functional-mapping perspective on variable-selection learning, in which the Transformer is treated as a learnable mapping from a dataset to its relevant variables. To learn this mapping, MambaPFN introduces three new components: (i) a faithful, rich, and scalable scheme for generating pretraining data, (ii) an objective that targets each variable's posterior inclusion probability, and (iii) a modified Transformer architecture tailored to variable selection. Once pretrained, MambaPFN is applied to new datasets without parameter updates. Empirically, MambaPFN achieves desirable variable-selection performance in simulation studies and exhibits a scaling law---more pretraining datasets and larger models can continuously improve its performance. Applied to a Facebook comments dataset, MambaPFN selects the fewest variables and achieves the highest computational efficiency and predictive performance, improving upon the best baselines by about 20%.

cs.AI · stat.ME · stat.ML

版本更新 · v3arXiv:2609.03628

Random Garbage Creates Exponential Quantum Query Separations

Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray

原文摘要

We prove an exponential separation between standard (XOR) quantum queries and forward-erasing queries for a Boolean property of injective functions, answering a question of Aaronson~\cite{Aaronson2021Open}. We also obtain an exponential separation for a Boolean promise problem on permutations, where forward in-place queries are unitary but inverse queries are not supplied. Our construction follows Aaronson's suggestion of appending fixed random garbage to a Simon function. Let $X=\{0,1\}^n$ and $N=2^n$. We use the injection $f_{h,r}(x)=(h(x),x,r_x)$, where $h:X\to X$ is promised to be either a permutation or a Simon function, and $r:X\to X$ is an arbitrary tag table that is reused on every query. The resulting problem is solvable with at most $n+2$ standard queries, but requires $Θ(\sqrt N)$ forward-erasing queries, matching classical collision sampling. Embedding these instances into permutations, with the copy of $x$ replaced by a single bit that keeps the embedding injective, gives a promise problem on permutations of $L=4N^2$ elements that requires $O(\log L)$ standard queries versus $Θ(L^{1/4})$ forward in-place queries. The lower bounds use the recording method. We replace each query by a nearby contraction that records cells of a purified tag table. After $T$ queries, tracing out the purified tag table yields a sum of positive-semidefinite contributions, each depending on $h$ at no more than $T$ addresses. A query-by-query hybrid bounds the trace-norm difference between the actual and auxiliary final operators by $O(T/\sqrt N)$. Random permutations and random Simon functions have the same restriction distribution on such a set unless it contains a hidden Simon pair, an event of probability $O(T^2/N)$. Consequently, the actual final states in the two cases remain close unless $T=Ω(\sqrt N)$, giving the required lower bounds.

cs.CC · quant-ph

新论文 · v1arXiv:2611.04847

Real-to-Integer Reduction for All-Pairs Shortest Paths

Nick Fischer, Adam Polak, Jonas Schmidt

原文摘要

Efficient graph algorithms often use techniques that are specific to integer-valued inputs and do not work for real-valued versions of the problems. Is it a limitation of current techniques, or are the real-valued variants inherently harder? One way to study this question is through real-to-integer reductions. We give (randomized, combinatorial) subcubic real-to-integer reductions for two central graph problems in fine-grained complexity: All-Pairs Shortest Paths and Exact Triangle. That is, we show that if the integer variants of these problems can be solved in truly subcubic time, then the real variants can also be solved in truly subcubic time. Our work extends and combines techniques from three previous works: (1) our real-to-integer reduction for the 3SUM problem (Fischer, Polak, Schmidt, FOCS 2026), which itself combines the Frank--Tardos theorem from optimization with Freiman's theorem from additive combinatorics; (2) universe reduction for APSP (Fischer, STOC 2026), which we generalize to reals and use to reduce the doubling of the set of edge weights; and (3) the ``Fredman's trick meets dominance product'' technique (Chan, Vassilevska Williams, Xu, STOC 2023), which is needed to adapt the prior real-to-integer framework from equality constraints to inequalities. As a corollary, our reduction combined with Yuval's fast Integer APSP algorithm in the real RAM model with multiplication (IPL 1976) shows that the Real APSP Hypothesis is false in this model, which also follows from the very recent breakthrough by Alman and Vassilevska Williams using a very different approach.

cs.DS

版本更新 · v2arXiv:2609.20267

CleanVideo: Adaptive Concept Erasure for Text-to-Video Diffusion Models

Junchi Liao, Hongji Li, Wenrui Zhou, Lijie Hu

原文摘要

Concept erasure aims to selectively eliminate undesired visual semantics from pre-trained generative models without compromising their general utility. Extending concept erasure from images to video is nontrivial. Target concepts emerge gradually and vary across frames and denoising steps. As a result, fixed interventions may miss the target or introduce blurring, jitter, and content distortion. We propose CleanVideo, a selective erasure framework that performs low-dimensional subspace intervention controlled by a tri-modal gating mechanism. By jointly processing spatiotemporal visual features, timestep signals, and textual semantics, CleanVideo determines where, when, and whether to intervene, steering erased content toward natural surrogate concepts when such surrogates can be clearly defined while preserving non-target content. Experiments on three video diffusion models show that CleanVideo effectively erases target concepts while maintaining visual fidelity and temporal coherence, outperforming existing baselines under frame-level and video-level evaluations and under concept-recovery attacks when the protected pipeline remains intact.

cs.CV · cs.AI

版本更新 · v2arXiv:2607.20827

Auditing Provenance Sensitivity in LLM Agent Action Selection

Junchi Liao, Qiang Huang, Rui Qian, Xutao Mao, Juntao Cheng, Kangning Cui, Yu Li, Jingyu Sun 等 9 位作者

原文摘要

LLM agents choose tools and arguments from context that mixes user requests, tool outputs, retrieved records, memory, and untrusted text. Evidence can be relevant without being authorized to determine a decision, so a correct action need not be grounded only in permitted evidence. We introduce a target-specific authorization audit that labels context factors separately for each tool and argument target. Its primary test holds the task, proposition, position, and policy fixed while changing only the proposition's source authority. We then test behavior when valid evidence is weakened and use context-subset interactions as a secondary localization diagnostic. Across 450 controlled next-action tasks and multiple open-weight LLM families, trusted and untrusted variants produce different actions in 5.4 percent of competing cases versus 1.7 percent of supporting cases. Under controlled degradation, unauthorized competition is retained in a full-correct, mixed-error, clean-correct pattern in 2.4 percent of comparisons, with a 95 percent confidence interval from 2.1 to 3.0 percent. These are controlled stress-set rates, not deployment prevalence. The models respond to textual source-authority cues, but this does not prevent untrusted evidence from influencing their actions.

cs.AI

版本更新 · v3arXiv:2609.07974

A $(3+ε)$-Approximation for Fair $k$-Means and a Matching Lower Bound

Kangke Cheng, Guanlin Mo, Shihong Song, Hu Ding

原文摘要

Fair clustering aims to prevent algorithmic bias against protected groups. We study Euclidean fair $k$-means, in which the proportion of each protected group in every cluster lies between prescribed lower and upper bounds. Because these constraints violate the nearest-center assignment property, center selection is coupled with point assignment. We introduce the drift-regularized relaxation, a new convex relaxation solved by a modified Frank-Wolfe method with linear-programming iterations, whose optimality condition controls the cost of converting its solution into $k$ fair clusters. Combined with any $ρ$-approximation algorithm for weighted $k$-means, the relaxation yields an exactly fair fractional solution of cost at most $2ρ+1+ε$ times the fractional optimum, improving the previous ratio $1+4ρ+ε$. In fixed dimension, this improves the best known ratio from $5+O(ε)$ to $3+O(ε)$. The fractional solution can be rounded to an integral one without changing the centers or increasing the cost, at a bounded additive violation of the fairness bounds. We also show that a $(3-δ)$-approximation is NP-hard for every fixed $δ>0$, even on the line with fractional assignments, so $3$ is the exact approximation threshold for fractional fair $k$-means in fixed dimension. The same guarantees hold for $k$-sparse Wasserstein barycenters, a special case of fractional fair $k$-means. More generally, they hold whenever every cluster must satisfy given homogeneous linear inequalities in the fractions of its points, such as a bound on the ratio between two groups or on the average of a numerical attribute in every cluster.

cs.CG · cs.LG

新论文 · v1arXiv:2611.04841

DGC-Net: Cross-Modal Dynamic Routing with Global-Guided Compensation in Multimodal Sentiment Analysis

Linan Zhu, Huaijing Wu, Xiao Han, Yuhao Wang

原文摘要

User-generated videos, including opinion vlogs and video reviews, provide a rich source of people's attitudes toward products, services, and social topics. Understanding the sentiment expressed by speakers is important for analyzing online opinions, as transcripts alone may not capture the attitude and intensity conveyed through vocal tone and facial expressions. Multimodal sentiment analysis (MSA) addresses this need by integrating textual, acoustic, and visual cues. However, these cues are often subtle, noisy, and inconsistent across modalities. Existing local affective cue modeling methods typically operate within individual modalities and overlook global contexts from other modalities. This may cause cross-modal affective cue inconsistency. Hierarchical global-local fusion methods integrate global semantics with fine-grained local affective cues. However, they commonly determine the relative contributions of the two representations implicitly, preventing the global-local contributions from adapting to the sample-dependent reliability of local cues and resulting in either insufficient use of informative local cues or excessive interference from unreliable ones. To address these issues, we propose DGC-Net, a Dynamic Gating and Global-Guided Compensation Network for MSA. DGC-Net mitigates cross-modal affective cue inconsistency through cross-modal contribution-aware dynamic expert routing. This mechanism uses auxiliary global contexts to guide local expert selection. Moreover, global-guided dynamic compensation fusion alleviates sample-dependent global-local contribution imbalance while preserving global semantic as the primary anchor and adaptively incorporating expert-refined local cues. Experiments on five multimodal benchmark datasets demonstrate the effectiveness and general applicability of DGC-Net, and ablation studies verify the contribution of each proposed component.

cs.AI · cs.MM

新论文 · v1arXiv:2611.04839

Coordinating Humanoid Loco-Manipulation through Action-Conditioned Latent Foresight

Ju Dong, Xinyu Xiao, Yiming Zhou, Tianshuo Yang, Xuerong Liu, Lei Zhang, Jian Chen, Haocheng Zhao 等 15 位作者

原文摘要

Humanoid loco-manipulation requires coordinated body motion and hand interaction over time, and a plausible-looking command sequence can still drop a held object or leave an interaction incomplete. We present action-conditioned latent foresight, a latent world-action model (WAM) that evaluates proposed command sequences before execution. An action generator proposes joint motion-hand command sequences from vision, language, and the robot state. An action-conditioned endpoint predictor estimates the visual features each sequence prefix reaches and measures progress toward a demonstration-derived subgoal, while a joint temporal prior scores temporal consistency given the robot state and preceding commands. The robot executes the first commands of the best-scoring sequence and replans from the next observation. During training, action consistency regularization reconstructs the first demonstrated command from observed and predicted feature changes, encouraging the predictor to retain action-relevant information. On ten tasks in the humanoid loco-manipulation simulation benchmark SIMPLE, our method achieves 89.7% average success, compared with 73.7% for Psi-Zero and 82.0% for DiT4DiT. On seven real-robot tasks, it achieves 85.7% under standard conditions and 65.7% under unseen object configurations, while GR00T N1.7 achieves 70.0% and 48.6%, respectively. Project page: https://ju6276.github.io/Action-Grounded-Foresight/

cs.RO

版本更新 · v2arXiv:2606.03994

SimuScene: Simulation-Ready Compositional 3D Scene Reconstruction from a Single Image

Inhee Lee, Sangwon Baik, Sungjoo Kim, Hyeonwoo Kim, Hyunsoo Cha, Hanbyul Joo

原文摘要

Reconstructing interactive, simulation-ready 3D scenes from a single image is a critical bottleneck for robotic manipulation. While recent single-image lifters recover plausible per-object shapes, composing them yields scenes that collapse under physical simulation due to interpenetrating, hovering, or sinking objects. Existing physics-aware compositional reconstruction methods mainly address this as a post-hoc layout correction, leaving the underlying geometric errors unresolved. To address this, we introduce SimuScene, a compositional 3D reconstruction pipeline that puts physics in the loop of shape and layout estimation. Rather than using physics merely for layout cleanup, we utilize the physics engine as a diagnostic measurement tool during the generative process itself. By diagnostically simulating reconstructed objects under gravity, we convert penetration and support failures into quantitative correction signals that drive amodal shape resampling, with gravity-axis stretching as a lightweight correction for minor errors. This physics-informed feedback loop mitigates accumulated reconstruction errors and produces a stable, simulation-ready compositional 3D scene. Extensive experiments demonstrate state-of-the-art performance on physical stability and geometric alignment benchmarks. We further highlight SimuScene's utility by deploying reconstructed environments in humanoid control and robot-arm manipulation tasks.

cs.CV · cs.RO

新论文 · v1arXiv:2611.04838

Found by Search, Broken by a Shortcut: Transfer and Tampering of Searched Intrinsic Rewards

Chase J. Metoyer

原文摘要

Can a search over innate drives find intrinsic rewards that help a reinforcement-learning agent learn, transfer to a task it never saw, and resist an exploit that was absent during the search? Each candidate reward combines four generic events (a new view, a pickup, a drop and a toggle), each with a weight, a relief and a refill rate. We ran three pre-registered stages; the search protocol was locked in a public, timestamped commit before any search result existed. CMA-ES and an equal-budget random search used 1,560 PPO training runs, and the final evaluation and tamper test used 340. On the held-out task, KeyCorridorS3R2, the CMA-ES-selected reward (E) beat task-only PPO, episodic novelty and the random-search-selected reward (R) in all 3 registered comparisons, all of them meaningful by the registered size rule. Among these generic rewards E transferred best; the earlier paper's satiation reward, which on this task is given hand-wired key and locked-door events, did better (20 of 20 seeds solved against 4 of 20; descriptive). On UnlockPickup, where that reward uses generic events, E's mean area exceeded it by 0.276 (descriptive). On the training tasks there was no registered difference between E and R: both E-over-R tests missed. A free reset action, absent during the search, collapsed E's learning on DoorKey-8x8 (mean area 0.829 without it, 0.136 with it; registered) to below task-only PPO (descriptive). The searched drives helped on every task tested, but a reward given task-specific events did better on the held-out task, and selection gave E no protection against an exploit absent from the search.

cs.LG · cs.AI

版本更新 · v2arXiv:2610.39004

How Architecture, Typology, and Adaptation Strategies Shape ASR for Low-Resource African Languages: A Controlled Empirical Study

Mercy Muchai, Kevin Chege, Nick Mumero Mwangi, Samuel Chege Maina, Felermino Ali, Elizabeth Ankrah, Ignatius Ezeani

原文摘要

Despite recent advancements in ASR, identifying effective architectures, fine-tuning approaches, and data adaptation strategies for low-resource languages remains challenging. We present a systematic comparison across five low-resource African languages and Swahili as a mid-resource contrast, fine-tuning three models from distinct architectures: Phi-4-multimodal-instruct, Whisper-large-v3-turbo, and MMS-1B-all. We analyze data sufficiency, monolingual versus multilingual adaptation, domain fine-tuning, and language-adapter transfer. Phi-4 achieves the best overall accuracy, MMS shows comparable CER, while Whisper exhibits high CER, consistent with known hallucinations and repetition loops. Performance saturates at different data scales, offering practical data-efficiency targets, while typological complexity consistently shapes error rates. Domain fine-tuning benefits Phi-4 and Whisper but degrades MMS, revealing limitations of adapter-based adaptation. Proxy language adapters outperform training MMS adapters from scratch.

cs.CL · cs.SD · eess.AS

新论文 · v1arXiv:2611.04836

HTCE: Homeomorphism-inspired Topological Cross-Scene Experience Canonicalization and Reuse for Object Navigation

Xiaoran Xu, Yupeng Wu, Tianyu Xue, Xuanran Dong, Yifan Xu, Xiaoshan Yang, Changsheng Xu

原文摘要

As embodied agents perform object-goal navigation across residential environments, they accumulate successful experiences whose semantic structure recurs across scenes even when geometric trajectories do not. Reusing such experience is challenging because differences in region naming and observation granularity produce distinct graph representations of similar approaches, while meaningful differences in anchors, branches, and endpoints must stay distinguishable. We introduce HTCE, a homeomorphism-inspired topological framework that canonicalizes and reuses navigation experience. Feature and topology subdivisions characterize representational variations, and their semantically constrained reductions produce comparable semantic sequences and structural signatures while preserving semantic anchors, branching relations, and navigation endpoints. HTCE then retrieves historical successful approaches through subdivision-aware matching as guidance for a frozen vision-language policy. Canonicalization compresses the experience index losslessly, merging 17.7--23.6\% of distinct stored route descriptions while retaining full task performance. Under a single frozen vision-language backbone shared by all compared systems, HTCE attains the best SR and SPL in every setting---59.9\%/31.8\% on HM3D v0.1, 71.0\%/31.5\% on HM3D v0.2, and 46.6\%/16.6\% on MP3D---with SR gains of up to 4.9 points and structured retrieval contributing up to 2.8 SPL points. The code is available in https://github.com/startracker0/htce.git

cs.AI

版本更新 · v3arXiv:2610.40625

Constant-Factor Approximation for Capacitated Clustering in Low Dimension with $(1+ε)k$ Centers

Kangke Cheng, Guanlin Mo, Hu Ding

原文摘要

In many applications of $k$-median and $k$-means, including load balancing and redistricting, each center can serve only a bounded number of clients. This leads to capacitated clustering, in which a client may be forced to use a distant center because all nearby ones are full. This loss of locality defeats the techniques behind approximation schemes, and no constant-factor approximation is known in general metrics even for capacitated $k$-median. A long line of work therefore opens $K=k+\lfloorεk\rfloor$ centers for a fixed $ε\in(0,1]$, while respecting the capacities exactly. We give a deterministic polynomial-time algorithm for uniform soft capacities in low dimension, that is, when the clients or the center locations have bounded doubling dimension. With $K$ centers, its ratio is $3-2ε$ for $k$-median and $9-8ε$ for $k$-means, or $5-4ε$ in $\mathbb{R}^d$. Apart from $k$-median in the plane, these are the first polynomial-time ratios bounded by a constant independent of $ε$; previously, the best ratio was $O(ε^{-2}\log(1/ε))$, even for $k$-median. We also obtain ratios that stay bounded as $ε\to0$ for non-uniform and hard capacities in low dimension, and ratios polylogarithmic in $1/ε$ in general metrics. Our approach starts from a simple structural observation: a near-optimal uncapacitated solution can be split into fewer than $2k$ capacity-respecting blocks, so $2k$ centers already suffice, one per block. Our main tool, the rescue lemma, shows that once every block that sends clients to a center of the optimal solution is rescued (given a private center), that center can be closed, so each extra center effectively rescues about two blocks. This lets $\lfloorεk\rfloor$ extra centers rescue nearly an $ε$-fraction of the blocks, yielding the linear dependence on $ε$ in our ratios.

cs.CG · cs.DS

新论文 · v1arXiv:2611.04835

Anomaly Detection on Resource-Constrained Devices with Reservoir Computing

Marco Angioli, Mathias Persson, Hiroto Tamura, Hadi Banaee, Amy Loutfi, Gouhei Tanaka, Alberto Giaretta, Denis Kleyko

原文摘要

Anomaly detection at the edge requires the deployment of models that achieve competitive performance, while minimizing computational cost and memory footprint. In this article, we investigate the suitability of the Mahalanobis Distance of Reservoir States (MDRS), an unsupervised time-series anomaly detection method, for resource-constrained devices and propose two optimizations to reduce its computational requirements. Specifically, we replace random reservoir connectivity (MDRS-Rand) with a circular shift (MDRS-Circ) and show that the anomaly score for an entire time series can be computed from the final reservoir state alone. Furthermore, we show that exploiting the reservoir's temporal memory enables more efficient input preprocessing, further reducing computational cost. We evaluate the MDRS variants on the MLPerf Tiny anomaly detection benchmark against the reference autoencoder and other anomaly detection methods, and deploy their inference kernels on a NUCLEO-F401RE microcontroller to assess latency, estimate energy consumption, and measure memory footprint. Among the evaluated methods, only MDRS and the autoencoder meet the benchmark's performance target, with MDRS requiring fewer operations and smaller models. With optimized preprocessing, MDRS achieves an ROC AUC of 0.869, a model size of 24 KB, an estimated energy consumption of 24 uJ per inference, and a latency of 0.32 ms, corresponding to a 75.9x speedup over the autoencoder with standard preprocessing.

cs.LG

新论文 · v1arXiv:2611.04834

Feeling of Knowing in Large Language Models

Zichuan Fu, Xian Wu, Jingtong Gao, Wenlin Zhang, Jiaxuan Li, Binhao Wang, Yimin Deng, Guojing Li 等 12 位作者

原文摘要

Post-training updates change what large language models (LLMs) can answer, but may leave their answerability judgments misaligned. We study this knowledge-judgment desynchronization through functional feeling of knowing (FoK), which supports selective generation, retrieval triggering, and model routing without implying subjective experience. We propose two trainable channels: a knowledge channel that changes answerability and a FoK channel that judges the current knowledge state. Three stages train them: on-policy supervised fine-tuning (OP-SFT) updates knowledge from corrected on-policy answers; knowledge-delta FoK training (K$Δ$-FT) adapts judgments across intermediate knowledge states; and FoK-guided policy optimization (FGPO) trains the subsequent answer or explanation. Factual-QA experiments, cross-dataset evaluation, and three sequential updates show that explicit FoK alignment improves judgment quality on updated knowledge. MMLU and ARC-Easy separately assess capability preservation.

cs.AI · cs.CL · cs.LG

版本更新 · v3arXiv:2610.05066

Salvation Lies Within: Eliciting Inherent Style Transfer in Step-Distilled Diffusion Models

Shengyin Sun, Yiming Li, Yingzhao Lian, Xing Li, Xingzhi Zhou, Anxin Tian, Zhili Wang, Haoyang Li 等 10 位作者

原文摘要

Adapting step-distilled text-to-image (T2I) models through post-training incurs additional computational costs and affects native few-step generation behavior. This motivates a complementary route beyond style-specific adaptation: drawing on the visual knowledge already encoded in step-distilled T2I models to elicit stylistic capabilities through language. Pursuing this direction requires textual guidance that captures how visual attributes jointly define a style and remain applicable as the depicted content changes. To explore this approach, we introduce StyleForge, a fully automatic, training-free framework that expresses reference styles as reusable rendering instructions. By integrating overall rendering characteristics with local color and lighting behavior, StyleForge organizes visual evidence from reference images into a coherent specification of how the target style should be expressed. The specification is then compiled into textual guidance that can be reused across content prompts, enabling frozen step-distilled T2I models to render different subjects and scenes in the reference style while retaining native few-step generation. Extensive experiments show relative gains of up to 29.47\% in generation quality scores over the strongest baseline, while Pareto analysis indicates that improved stylization is accompanied by strong adherence to the requested content. Code is available at https://github.com/sunshy-1/StyleForge.

cs.CV

版本更新 · v2arXiv:2610.32721

Deterministic Incremental Triconnectivity in $O(\log^2 n)$ Worst-Case Time

Niels Inselmann Christiansen, Eva Rotenberg

原文摘要

We consider the problem of maintaining the triconnectivity in a graph $G$ in the incremental dynamic setting. We consider updates in the form of edge insertions and edge subdivisions, and triconnectivity queries, i.e. queries that take as input variables the vertices $a$ and $b$ and are of the form ''are there at least three vertex disjoint paths between $a$ and $b$?''. All algorithms presented in this paper are deterministic. When starting from a biconnected graph, all updates take worst-case $O(\log n)$ time, and all queries are answered in $O(\log n)$ time. By combining this result for biconnected graphs with a result of Holm and Rotenberg [SODA'20] we get a deterministic algorithm for general graphs with a worst-case update and query time of $O(\log^2 n)$. Both algorithms represent an improvement of the state-of-the-art by a factor of $O(\log n)$.

cs.DS

版本更新 · v2arXiv:2608.22355

Recovery Beats Storage: Improved Space for Preprocessed 3SUM

Amir Carmel, Yakov Kosoburd, Robert Krauthgamer

原文摘要

The 3SUM problem asks, given sets $A,B,C$ of integers, whether there exist $a\in A$ and $b\in B$ whose sum belongs to $C$. In the preprocessed variant with unknown $C$, one preprocesses sets $A$ and $B$, each of size $n$, and subsequently answers a query specified by subsets $A'\subseteq A$, $B'\subseteq B$ and a target set $C'$ of size $O(n)$, by solving the 3SUM instance $(A',B',C')$. Kirkpatrick, Kuszmaul, Mathialagan, and Vassilevska Williams [ICALP 2026] gave the first algorithm with subquadratic space for this problem, achieving $\widetilde{O}(n^{3/2+ε})$ query time using $\widetilde{O}(n^{2-2ε/3})$ space, for every $ε\in[0,1/2]$. Their algorithm employs separate mechanisms for heavy and light targets, and for each heavy target it stores explicitly the list of pairs $(a,b)$ whose sum is congruent to it modulo a random prime $p$ but differs from it. These lists dominate the space bound. We present a unified construction that uses a single mechanism for all queries. Instead of storing these lists of pairs, our algorithm recovers on demand the residue class of the target modulo a random prime by inverting the function $(a,b)\mapsto (a+b\bmod p)$. Additionally, instead of storing the heavy targets, it recomputes at query time a set that covers them. This leads to an improved space bound of $\widetilde{O}(n^{2-ε})$, while maintaining the same query time. Moreover, our construction is the first to achieve subquadratic space while supporting adaptively chosen queries.

cs.DS

版本更新 · v2arXiv:2610.06959

Nearly optimal Personalized PageRank computation

Rong-Hua Li, Quanqing Xu, Yichun Yang, Junjie Zhou

原文摘要

We study the fundamental problem of computing Personalized PageRank (PPR) on an undirected and unweighted graph $G$. We focus on the $\eps$-error guarantee introduced by Andersen, Chung, and Lang [ACL; FOCS 2006 $\&$ Internet Math 2007]. Their classic local push method computes an approximate PPR vector satisfying the ACL $\eps$-error guarantee in $O((α\eps)^{-1})$ time, where $α$ is the teleportation parameter. This problem has a lower bound $Ω(\eps^{-1})$. Working with idealized SDDM solves, we eliminate the dependence on $α$ and present an algorithm that achieves the same error guarantee in $O(\eps^{-1-o(1)})$ time. Consequently, we obtain a nearly optimal algorithm for PPR computation under the ACL error guarantee, and a nearly linear algorithm for local graph clustering with complexity independent of $φ$.

cs.DS · cs.CC

新论文 · v1arXiv:2611.04829

Geometric Bin Packing Beyond Convexity: Approximation Schemes without Augmentation

Lucas de Oliveira Silva, Elisa Dell'Arriva, Flávio Keidi Miyazawa

原文摘要

We study the geometric bin packing problem for simple polygonal regions, i.e., non-degenerate, connected, rational regions, in the minimum number of unit-square bins, allowing only translations. We even consider packing general non-convex objects, possibly with holes, where we can then pack smaller objects. Previous schemes cover squares (MOR'06), circles and other $L_p$-balls (Algorithmica'16), sufficiently skewed rectangles (Algorithmica'23), and convex fat objects with a constant number of distinct shapes under resource augmentation (arXiv'24, WAOA'23). The result for circles and other $L_p$-balls needs bin augmentation to obtain rational packing realizations. For restricted classes of $L$-shaped polygons, Gerlach et al. (SoCG'26) give constant worst-case guarantees, while for general non-convex objects, bounding-box reductions give just approximation factors that depend on fatness. Against this background, we present a general framework that provides asymptotic polynomial-time approximation schemes (APTAS) for bin packing of any fixed class of simple polygonal regions satisfying just two assumptions. First, covering any object by the grid cells intersecting its interior in any sufficiently fine square grid, relative to the object's bounding box, increases its area by at most a small fraction. Second, the class can be partitioned into a constant number of sequences such that each object in a sequence can be translated to fit inside every preceding object. In particular, certain classes of star-shaped polygons and more general polygonal regions, including some with simple holes, satisfy both assumptions. In addition, our framework does not require a bound on the objects' boundary complexity. We emphasize that our results require no bin augmentation whatsoever and yield explicit, exact rational packings of polynomial encoding length for all input objects.

cs.CG · cs.DS