跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

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

全站更新概况

+758新增论文
+578其中 AI 相关
+94已有论文修订
+95新增 AI 导读

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

统计口径与数据新鲜度

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

最近完成检查:2026-11-17 04:58最近发现新增版本:2026-11-17 04:58库内论文最新更新时间:2026-11-14 02:59

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

24,106 已收录论文20,158 AI 相关7,049 有修订112 HF 社区发现

浏览论文库

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

找到 24,106 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-17 04:57(北京时间)
版本更新 · v2arXiv:2609.23015

An exponential lower bound for the bit pigeonhole principle in resolution over parities

Kamil Braun

原文摘要

Resolution over parities, $\mathrm{Res}(\oplus)$, is the characteristic-two version of resolution over linear equations: clauses are disjunctions of affine equations over $\mathbb F_2$. Superpolynomial size lower bounds were previously known only for restricted refutations: tree-like, regular, or of bounded depth. We prove that every DAG-like $\mathrm{Res} (\oplus)$ refutation of the bit pigeonhole principle with $n+1$ pigeons and $n=2^\ell$ holes has more than $\exp(n/(32768\ell^2))=2^{Ω(n/\log^2 n)}$ clauses, for every $\ell\ge32$, with no restriction on regularity or depth. The proof translates an arbitrary refutation with $S$ clauses into a polynomial calculus refutation of degree $O(\log n)$ over $O(S+n^2)$ groups of extension variables in the style of Buss, Impagliazzo, Krajicek, Pudlak, Razborov, and Sgall. One substitution then removes all extension variables at once and leaves a nonzero low-degree polynomial derived from the pigeonhole axioms alone at degree at most $n/2$; a degree lower bound in the style of Razborov, proved through the homology of chessboard complexes, shows that no such derivation exists. The argument also yields a general sufficient condition for $\mathrm{Res}(\oplus)$ size lower bounds. The main theorem, this condition, and all their dependencies are formalized in Lean 4, and every statement links to its formal proof. The proof was developed with substantial AI assistance within an open research framework described in the final section.

cs.CC · cs.LO

版本更新 · v2arXiv:2610.40562

Nearly-Optimal Time-Sample Trade-off in Consensus Dynamics

Francesco d'Amore, Joel Rybicki, Nobutaka Shimizu, Takeharu Shiraga, Robin Vacus

原文摘要

How does the number of sampled opinions affect the time required to reach consensus in distributed consensus dynamics? We study the synchronous $h$-Majority, in which every node independently samples $h$ nodes uniformly at random with replacement in each round and adopts a most frequent sampled opinion, breaking ties uniformly at random. We show that $h$-Majority achieves the nearly-optimal trade-off between the sample size and the consensus time, among a broad class of consensus dynamics. In particular, we prove the following results. For every sample size $h \ge 3$ and for every initial configuration, we prove that the process reaches consensus with high probability within $$\widetilde{O}\left(1+\min\left\{\frac{1}{\min\{h^2p_{\max},1\}},\frac{\sqrt{n}}{h}\right\}\right)$$ rounds, where $n$ is the number of nodes and $p_{\max}$ is the largest initial fraction of nodes supporting any single opinion. This is the first bound on the consensus time for $h$-Majority that holds for every $h\ge3$ and every initial configuration. When the initially most popular opinion has a sufficiently large lead over every other opinion, we show that all nodes adopt this opinion with high probability within $O(\log n/\min\{h^2p_{\max},1\})$ rounds. We establish a matching lower bound up to polylogarithmic factors for any fixed update rule that treats all opinions symmetrically and that selects either a sampled opinion or the node's current opinion.

cs.DC · cs.DS · math.PR

版本更新 · v2arXiv:2610.38946

MAS-Loop: Beyond One-Shot Orchestration towards Self-Evolving Multi-Agent Systems

Hehai Lin, Qi Yang, Chengwei Qin

原文摘要

Training-time multi-agent system (MAS) design seeks to learn reusable orchestration policies, yet prevailing approaches remain largely one-shot: an Orchestrator generates a system but only observes and learns from its terminal outcome. This paradigm discards execution trajectories that expose system-level failures and contain fine-grained information beyond the terminal outcome, leaving no direct basis for revising the source MAS, evaluating the updated MAS, or learning from the resulting contrast. To this end, we introduce MAS-Loop, an execution-grounded framework that closes this feedback loop by coupling an Orchestrator with a trajectory-conditioned Refiner. For each task, the Orchestrator constructs and executes a source MAS to obtain an outcome score and an intermediate trajectory. Conditioned on the trajectory, the Refiner localizes an actionable failure, formulates a trajectory-grounded diagnosis, and proposes a bounded patch to the agents, information flow, or execution configuration. The executable updated MAS is re-executed on the same task to measure its realized outcome under stochastic execution. This pair-MAS comparison provides complementary learning signals: the Orchestrator learns to generate strong systems with fewer recoverable failures, whereas the Refiner learns to expose and repair observed weaknesses, thereby driving policy-level co-evolution across training iterations. Experiments show that MAS-Loop achieves the strongest overall performance among the evaluated baselines, with consistent gains from refinement across all evaluated benchmarks. The co-evolution process also yields MAS-JudgeCorpus, a dataset of execution-grounded source-updated pairs with orchestration- and trajectory-level supervision, which can provide the community with support for MAS reward modeling and trajectory-aware investigation.

cs.MA · cs.AI

版本更新 · v2arXiv:2607.12135

LQG solution for POMDP without estimating states: A minimum variance approach

Ranjan Sarkar, Prabhat K. Mishra

原文摘要

This paper investigates the control of discrete-time linear time-invariant (LTI) systems subject to incomplete and corrupted measurements. Specifically, we focus on designing a Linear Quadratic Gaussian (LQG) controller without relying on explicit state estimation. By leveraging minimum variance duality, our approach allows the current control input to be represented as a linear function of available measurements and previously applied inputs, successfully reducing the task to a tractable deterministic optimization problem. We provide theoretical justification for this framework and demonstrate its practical effectiveness through numerical experiments.

math.OC · cs.RO · eess.SY

版本更新 · v2arXiv:2606.08218

How Deep Are Deep GPs, Really? A Sharp Threshold and a Non-Gaussian Limit for Compositional GPs

Mark Kozdoba, Shie Mannor

原文摘要

Compositional priors describe the generic properties of layered functions in deep Bayesian models, where deep neural networks with random weights are a canonical example. In the wide-network limit, the prior is a Gaussian process (GP) with a depth-dependent kernel, and its behaviour as depth grows has been extensively studied through this kernel. Here, we study another case, where each layer itself is a vector valued Gaussian process, and our aim is similarly to understand the limiting behaviour of the prior as depth grows. Previous GP work has established that for the radial basis function (RBF) kernel and a certain range of bandwidths $r$, the prior degenerates in the limit, converging to the set of constant functions, which is not useful as a probabilistic model. In this paper we establish several new results. First, we identify a sharp bandwidth threshold $r_c(d) = Θ(\sqrt{d})$ above which the limit is degenerate, strengthening the earlier bounds. Second, and more importantly, we show that for $r$ below the threshold $r_c(d)$ the prior converges to a limit distribution $π_{\bar{Z}}$. We also prove that these distributions are non-degenerate and non-Gaussian, with non-vanishing dependence between coordinates. In contrast to the previously known degenerate regime, deep Gaussian process priors can therefore admit non-trivial limits. Empirically, we verify the threshold across a range of dimensions $d$, and demonstrate a complex multimodal behaviour of the limit distributions $π_{\bar{Z}}$, a regime that becomes increasingly narrow with $d$ and would be hard to identify without knowing the threshold.

cs.LG · cs.AI · math.ST · stat.ML

新论文 · v1arXiv:2611.04876

Leakage-Resilient Computation via Matrix Refreshing

Stefan Dziembowski, Sebastian Faust

原文摘要

Leakage-resilient cryptography protects secrets against side-channel attacks, in which a physical implementation reveals partial information about its internal state. A fundamental primitive in this area is a leakage-resilient storage, which allows a secret to be stored in a way that remains secure even if an adversary learns some information about the storage's internal state. A popular approach represents a secret as the inner product of two $n$-bit vectors, called shares. The shares are stored and processed separately by two parts of the implementation, called the left and right parties. Because leakage accumulates over time, the shares must be refreshed repeatedly. We prove that a simple refresh, in which the left party multiplies its share by a uniform invertible matrix $M$ and the right party multiplies its share by $M^{-1}$, is secure under continual local leakage. After $T$ refreshes, each allowing at most $λ$ bits of leakage per party, the transcripts for two stored secrets are at statistical distance at most $C\cdot T\cdot 2^{6λ-n/9}$ for an absolute constant $C$. We also obtain a Boolean-circuit compiler with statistical privacy error at most $C\cdot S\cdot 2^{18λ-n/27}$ for $S$ operations and at most $λ$ bits of local leakage per party per operation. The guarantee covers repeated stateful evaluations with adaptively chosen public inputs, with $S$ counting all operations across invocations. Thus, for polynomial-size circuits, a constant leakage fraction is tolerated with share length depending only on the security parameter. We formalize the refreshing bound, the composition and compiler guarantees, and the expected-work bounds in Lean 4. Our results also provide efficient simulation: the leakage can be reproduced from the public inputs and the circuit outputs alone, with expected polynomial overhead.

cs.CR

版本更新 · v2arXiv:2609.02542

World-Model-Augmented Visual Locomotion for Humanoids on Foothold-Constrained Terrain

Yuxi Liu, Lijun Han, Ziming Wang, Ao Zhang, Cong Yang, Wei Sui

原文摘要

Foothold-constrained terrain limits feasible footholds to sparse, discontinuous, or narrow support regions, as in gaps, stepping stones, stairs, and balance beams. In such settings, a single misplaced step can cause a fall. Reliable traversal therefore requires precise foot placement and anticipation of upcoming terrain. To address this challenge, we present World-Model-Augmented Visual Locomotion (WM-LOCO), which augments a visual locomotion policy with predictive context from a jointly trained world model. Given onboard depth observations and proprioception, a recurrent state-space model (RSSM) learns action-conditioned latent dynamics that predict future proprioceptive states, egocentric observations, and task rewards. The resulting recurrent feature is then fed into the proximal policy optimization (PPO) actor-critic, providing predictive context for anticipatory foot placement on foothold-constrained terrain. WM-LOCO achieves average success rates of 96.0% on gaps, 96.9% on stepping stones, 94.0% on stairs, and 92.1% on balance beams, outperforming the evaluated baselines while improving gait efficiency and smoothness. Furthermore, WM-LOCO achieves zero-shot sim-to-real transfer to a Unitree G1, with 92.5% success across these four terrain classes.

cs.RO

新论文 · v1arXiv:2611.04874

OCR in the Foundation Model Era: From Specialist Models to Unified Models

Zhiheng Li, Zongyang Ma, Jiaxian Chen, Cheng Cui, Yi Liu, Ziqi Zhang, Chunfeng Yuan, Bing Li 等 10 位作者

原文摘要

Optical Character Recognition (OCR) is among the oldest and most widely deployed applications of artificial intelligence. This survey reviews its development, focusing on the Foundation Model Era. We define OCR through faithful transcription: within a specified visual scope, OCR should completely reconstruct the text, notation, and document structure observable in the source image, and every textual, notational, or structural element in the output must be verifiable from visual evidence in that image. We trace the development from specialist OCR models toward unified models, examining joint text detection and recognition, structured sequence generation, and the use of pretrained vision-language models (VLMs). We organize contemporary OCR systems into five coexisting families: modular toolkits and task-specific models, specialized document VLMs, hybrid workflows, general-purpose VLMs, and commercial products and managed services. We compare their architectures, data, and training, examining hallucination and omission, insufficient spatial grounding, and inference cost in generative OCR. We review evaluation from character and scene text recognition to parsing individual structural elements and full-page transcription, highlighting gaps in consistent output definitions, attribution of performance to individual components, and coverage of real capture conditions and visible content and structure. Finally, we summarize the challenges facing OCR and discuss directions for future research. We continuously track related work at https://github.com/zhihengli-casia/Awesome-OCR-in-the-Foundation-Model-Era.

cs.CV

新论文 · v1arXiv:2611.04873

Trusting Imagined Futures: Auditing Imagined Rewards for VLA Post-Training

Zicheng Kong, Zhenbo Xu, Haoyan Zhang, Jinghan Yang, Zhenzhen Li, Yiwei Ru, Liuyu Xiang, WanTing Xu 等 10 位作者

原文摘要

Video world models enable candidate actions to be evaluated through imagined outcomes, but high predicted rewards can favor trajectories with poor execution quality. We introduce Trusting Imagined Futures (TIF), an offline supervision selection method for vision-language-action (VLA) post-training that audits predicted rewards using execution feedback. A multidimensional reward model predicts a utility score for candidate ranking and five dimensions of execution quality. An auditor uses reward predictions and uncertainty to identify overestimation patterns learned from paired imagined videos and real executions. TIF accepts the candidate with the highest predicted utility when its advantage over the existing trajectory exceeds a margin and its audit risk passes a threshold; otherwise, it retains the existing supervision. The retained real trajectories then supervise behavior cloning. Across four LIBERO suites and three training seeds, TIF achieves a mean success rate of 76.25%, improving over training on the existing trajectories by 3.00 percentage points with the same trajectory count and training budget. Adding audit gating yields 1.47 percentage points with the reward model and advantage margin held fixed. The gains persist against advantage ranking and logistic regression risk selection at matched replacement counts. On recorded videos from three real robot tasks, TIF increases clean completion among selected trajectories from 58.33% to 70.00% across 60 candidate pools.

cs.RO · cs.CV

新论文 · v1arXiv:2611.04871

Physics-Based Plausibility Assessment of AI-Predicted Vehicle Parameters for Automotive Radar in Pre-Crash Scenarios

Rainer Engert, Patrick Zaumseil, Thomas Brandmeier

原文摘要

Automotive radar is a key sensing modality for safety-critical vehicle functions due to its robustness under adverse weather and lighting conditions. Recent advances in AI-based radar perception enable the direct estimation of object parameters from a single radar measurement cycle. However, the internal decision process of data-driven models is typically not explicitly linked to the underlying radar sensing physics. Consequently, object estimates may achieve high statistical accuracy while remaining physically inconsistent with the measured radar signature, particularly in previously unseen scenarios. Such inconsistencies are especially critical for heading estimation, as they directly affect trajectory prediction and collision assessment in pre-crash scenarios. This paper presents a physics-based consistency assessment framework for validating AI-derived vehicle hypotheses in automotive radar perception. The proposed approach generates an expected radar signature from AI-estimated object parameters using a physics-based reference model that incorporates occlusion-dependent edge visibility, aspect- and angle-dependent RCS modeling, and characteristic wheel-induced MD signatures. The expected signature is compared with the observed radar point cloud using a Wasserstein-distance-based consistency metric computed from three complementary features: the spatial distribution of detections along object edges, the local detection count, and the radar reflection intensity. In this way, physically implausible object hypotheses can be identified and corrected independently of the underlying neural network architecture and without model retraining or architectural modifications. The proposed consistency module is integrated as a cascaded post-processing stage for vehicle heading estimation.

cs.RO

新论文 · v1arXiv:2611.04870

PrimeSim: A Generalist World Model Simulator from Large-Scale Cross-Embodiment Demonstrations

Travis Davies, Wentao Ma, Lihao Guo, Tengfei Ma, Xiaowen Chang, Jiafeng Xu, Shilong Wang, Yiqi Deng 等 13 位作者

原文摘要

A robot world model that serves as a simulator must do more than generate plausible videos: it must faithfully follow commanded actions, maintain consistency across camera views, and sustain coherent long-horizon rollouts. We present PrimeSim, an action-conditioned, multiview world model simulator that addresses these challenges through progressive midtraining and posttraining. Starting from a pretrained video generator, we midtrain on 30,110 hours of robot demonstrations spanning 22 platforms. To improve action following, we introduce a unified cross-embodiment action representation and frame-aligned dual-path conditioning to strengthen action-frame correspondence. To maintain multiview consistency, we develop view-aware interleaved attention with explicit camera identities, enabling cross-view information exchange while preserving view-specific representations. We further introduce a fast-video, slow-memory posttraining framework that transforms the bidirectional video generator into an efficient autoregressive simulator. By combining fast causal generation, self-rollout training, and hierarchical temporal memory, PrimeSim mitigates error accumulation from self-generated histories and supports coherent long-horizon simulation. PrimeSim runs at 10.1 FPS, remains stable over long-horizon rollouts on rigid and deformable manipulation tasks, and transfers to held-out platforms within 100 to 200 gradient steps where the pretrained backbone does not. Against five open-source action-conditioned world models it leads four of the five WorldSimProbe suites and posts the best overall EWMBench score, while fine-grained local calibration still trails the field; its rollouts are faithful enough to support GRPO-based policy optimization. We release the model weights, inference code, and training code.

cs.RO

新论文 · v1arXiv:2611.04863

Geometric Obstructions and Sharp Genus Dependence in LCD Scalings

Rahim Rahmati-Asghar

原文摘要

We study the least pole order of a rational function whose nonzero evaluations scale a prescribed code to a Euclidean LCD code. A residue-one differential yields an obstruction for odd-dimensional one-point AG codes in characteristic two: for $C=C_L(D,aQ)$ with $0\le a<n$ and odd dimension, the threshold is at least $n+2g-a-1$. The obstruction uses alternating Gram matrices and does not require the scaled code to be self-orthogonal. For the dimension-three codes $C_L(D,(r+1)Q)$ on Hermitian curves over $\F_{r^2}$, $r=2^e\ge4$, we obtain \[ n+2g-r-2\leτ_D(C;Q)\le n+2g-3. \] Consequently the leading genus contribution is asymptotically sharp even in dimension three. On the elliptic curve $y^2+y=x^3$ over $\F_4$, we prove the exact dimension-three threshold $6$ by an explicit multiplier. For repetition codes on the Hermitian family, the threshold equals the general interpolation bound $n+2g-1$. The upper bounds use information sets and hold for $q>3k$, and for $q>2k$ in characteristic two.

math.AG · cs.IT

版本更新 · v3arXiv:2605.10379

Not All Proofs Are Equal: Evaluating LLM Proof Quality Beyond Correctness

Ivo Petrov, Jasper Dekoninck, Dimitar I. Dimitrov, Martin Vechev

原文摘要

Large language models (LLMs) have become capable mathematical problem-solvers, often producing correct proofs for challenging problems. However, correctness alone is not sufficient: mathematical proofs should also be clear, insightful, contain transferable knowledge, and be generally useful to the reader. While proof quality is subjective and depends on the reader and context, many of its components can be made concrete. In this work, we identify such components and introduce ProofRank, a benchmark curated from challenging competitions that measures several scalable proxies of proof quality: (i) conciseness - quantifying whether proofs avoid unnecessary steps; (ii) computational ease - the extent to which a proof relies on tedious calculations; (iii) cognitive simplicity - how accessible the used proof techniques are; (iv) diversity - how varied a model's proofs for a single problem are; and (v) adaptivity - how well a model can follow a specified technique. We find proof quality varies substantially across models along dimensions that correctness largely fails to capture. Every proof-level proxy can be steered through prompting, but often at a moderate correctness cost. ProofRank thus captures important aspects of mathematical proofs beyond correctness, and indicates the need for models that produce proofs which are not only correct but also valuable.

cs.CL

新论文 · v1arXiv:2611.04860

Robust Aggregation of Quantile Statistics: from Median to Interval

Mingyu Song, Yizhou Wang, Yuqing Kong

原文摘要

Quantile-based summaries, such as prediction intervals and medians, are commonly used in economic forecasting, climate science, and public health. For highly skewed samples, experimental evidence suggests that estimates of the mean can be biased toward the median, whereas estimates of the median are relatively accurate. This motivates aggregating explicitly elicited quantiles rather than reported means. We study robust aggregation of quantile reports for bounded outcomes under squared loss, minimizing worst-case regret relative to an omniscient Bayesian aggregator who knows the information structure and observes all private signals. Without restrictions on the information structure, no rule improves on the constant forecast at the range midpoint in worst-case regret. We therefore consider weak substitutes, a diminishing-returns condition on the value of information, and characterize optimal aggregation rules under this condition. For central prediction intervals with common nominal coverage $α$, the optimal rule, which we call regularized simple average for prediction intervals, shrinks the average reported interval midpoint toward the range midpoint, with a weight determined by $α$ and the number $n$ of experts. This optimal rule strictly improves on the constant baseline in worst-case regret when $α<1/\sqrt{n}$; at or above this threshold, the constant rule is optimal. The optimal worst-case regret is minimized at a unique interior coverage level, revealing a nonmonotonic relationship between coverage and aggregation performance. For median reports, regularized simple average for medians similarly shrinks the average reported median toward the range midpoint, assigning weight $1/n$ to the reported average and strictly improving on the constant baseline in worst-case regret for every finite $n\ge2$.

cs.GT

新论文 · 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

版本更新 · 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

新论文 · 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