跳到正文
研踪PaperTrail

版本更新

查看已发布论文的最新修订,在详情页对照实际观测到的版本。

部分采集异常

全站更新概况

+907新增论文
+744其中 AI 相关
+108已有论文修订
+94新增 AI 导读

arXiv 最近完成扫描:2026-11-19 06:59 · 全站最近入库:2026-11-19 06:59各信源进度 →

统计口径与数据新鲜度

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

最近完成检查:2026-11-19 06:59最近发现新增版本:2026-11-19 06:59库内论文最新更新时间:2026-11-18 08:00

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

26,871 已收录论文22,375 AI 相关8,156 有修订112 HF 社区发现

论文修订列表

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

找到 8,156 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-19 06:57(北京时间)
版本更新 · v2arXiv:2610.35848

Exploring the Tractability Frontier of Hylland-Zeckhauser Models

Ioannis Panageas, Avi Shein, Shayan Taherijam, Vijay V. Vazirani

原文摘要

The Hylland-Zeckhauser (HZ) mechanism provides a market-based approach to one-sided matching, making efficient equilibrium computation central to its implementation. Under bi-valued utilities, it admits a strongly polynomial-time algorithm [VY], whereas with four values per buyer, the problem is PPAD-hard under inverse polynomial approximation [CCPY]. To understand the tractability boundary, we study two extensions of the bi-valued case: a third linear utility value and separable concave utilities with two common slopes. For every fixed rational $a\in(0,1)$, we prove that computing a normalized additive $\varepsilon_{*}(a)/N$-equilibrium in an $N$-buyer HZ market is PPAD-complete for some constant $\varepsilon_{*}(a)>0$, even when all utilities belong to the same prescribed set $\{0,a,1\}$. This resolves the main question left open by [VY, CCPY]: whether three utility values already suffice for PPAD-hardness. Assuming the PCP-for-PPAD conjecture, we strengthen the above-stated result to constant additive-error hardness. For the concave extension, we compute an exact equilibrium in strongly polynomial time with two marginal utility slopes common across goods for each buyer and arbitrary rational buyer-good breakpoints. With three common marginal slopes, suitable breakpoints encode the three valued linear case, yielding PPAD-hardness. Thus, our paper identifies two thresholds separating tractable and intractable cases of HZ models with utility functions specified by utility values or marginal slopes. In both cases, the tractability threshold lies between two and three.

cs.GT

版本更新 · v4arXiv:2510.01137

Re-examining low-rank adaptation for private LLM fine-tuning

Ali Dadsetan, Frank Rudzicz

原文摘要

Privacy is a central concern when fine-tuning large language models (LLMs) on sensitive data, and differentially private stochastic gradient descent (DP-SGD) provides formal privacy guarantees. When performance at a fixed privacy level largely saturates on established benchmarks such as GLUE, we ask whether the same performance can be reached with less computation. Both theory and practice show that lower-rank models are better suited to DP training, a property especially relevant for LLMs, whose fine-tuning gradients exhibit a strong low-rank structure. Methods such as DP-LoRA exploit this by expressing each layer's weight update as a sum of only a few non-zero rank-one components. However, we argue that while having few non-zero components is important, the isotropic noise injected by DP-SGD inflates the singular values of the gradient matrix, disrupting their naturally fast decay. We investigate whether this noise-induced spectral distortion slows optimization. Experiments on language classification (GLUE with RoBERTa) and table-to-text generation (E2E and DART with Qwen and Llama models up to 4B parameters) show that partially restoring the original singular-value profile significantly accelerates DP-SGD convergence without compromising privacy guarantees. Our code is available at https://github.com/alidadsetan/re-exam-private-low-rank.

cs.LG

版本更新 · v2arXiv:2610.21779

FuseAdapt: Parameter-Efficient Multimodal Fusion for Semantic Segmentation with Missing Modalities

Xin Zhang, Robby T. Tan

原文摘要

Multi-modal semantic segmentation benefits from complementary sensors, but this benefit is fragile when some modalities are degraded or missing at test time. Many existing methods rely on dedicated fusion modules or multi-branch cross-modal encoders, and the fusion often becomes unreliable when modalities are absent, leading to substantial performance drops. We propose FuseAdapt, a parameter-efficient framework that performs fusion within the adaptation space of a frozen vision foundation model (VFM), exploring whether VFM priors can serve as an effective shared backbone for multi-modal segmentation. Instead of attaching a standalone fusion network, FuseAdapt assigns each modality a lightweight adaptation branch and performs adaptation-space fusion by keeping Q/V low-rank adaptation private to each modality and routing only FFN low-rank residual activations across modalities inside the frozen backbone. The pretrained VFM remains fixed while modality-specific corrections and explicit cross-modal interaction are learned through the adaptation paths. To handle missing modalities, we further introduce Predictive Modality Modeling (PMM), a direct representation-level objective for cross-modal redundancy. During training, PMM masks a target modality and predicts its embedding from the visible ones, supervised by a teacher target computed under full-modality input. PMM is used only during training and adds no inference-time overhead. Across three multi-modal segmentation benchmarks (MCubeS, DELIVER, MUSES), FuseAdapt consistently improves both modality-complete and modality-incomplete segmentation with a small trainable budget, yielding up to +3.01 mIoU under full modalities and +11.25 mIoU under missing modalities over prior state-of-the-art. Project page: https://devinxzhang.github.io/FuseAdapt-Page/

cs.CV

版本更新 · v2arXiv:2610.41970

When Does Test-Time Search Help World Action Models? An Empirical Audit of Candidate Selection and Simulator Integrity

Jun Liu, Dajie Sun, Zhenglun Kong, Zhenjiang Fan, Peiyan Dong, Fan Yang, Wenbin Zhang, Geng Yuan 等 11 位作者

原文摘要

World-action models increasingly apply test-time scaling, spending extra inference computation on candidate selection and adaptive allocation to improve control. Such gains are credible only when candidates carry exploitable signal, nominal compute savings become real speedup, and evaluation stays reliable. We audit all three on Cosmos Policy and RoboCasa with a premise-first, pre-registered methodology. On clean data, a learned value selector is 1.66 pp worse than random; a hindsight oracle gains only 1.40 pp, with an episode-level interval spanning zero; and 82% of states show identical candidate outcomes, leaving little selection headroom. Token pruning cuts per-forward FLOPs by up to 47% but yields at most a measured 1.15$\times$ end-to-end speedup on the deployed path (1.25$\times$ on a decode-excluded path), short of a 1.5$\times$ target, and our adaptive-allocation experiment is inconclusive under a power gate. We further identify and fix a silent rendering corruption whose rate rises sharply along compute-heavy planning paths while leaving the official direct-policy result unaffected, and release a detector, fix, and scripts. These findings show why test-time scaling should be audited as a chain of premises (decision signal, realized efficiency, evaluationintegrity) rather than by success rate alone. Conclusions are scoped to the tested configuration.

cs.AI

版本更新 · v3arXiv:2610.01421

Robust and leakage-resilient device-independent oblivious transfer in MiniQCrypt

Rishabh Batra, Zhili Chen, Rahul Jain, YaoNan Zhang

原文摘要

Assuming post-quantum one-way functions, we construct device-independent oblivious transfer and bit commitment that tolerate independent honest faults at a constant rate and adaptive, bidirectional quantum leakage between the laboratories at a constant rate. Honest parties use trusted classical computation to operate untrusted quantum devices, which may share arbitrary entanglement and perform joint measurements without assumptions of independence or identical distribution. Security is simulation-based against quantum polynomial-time adversaries and composes sequentially with efficient simulators. For security parameter $λ$ and a prescribed total leakage budget $\ell$, one complete one-bit oblivious transfer uses $Θ(\ell+\log^2λ)$ device coordinates in at most three single-use device windows, including preprocessing, and polynomial classical computation and communication. The leakage budget is shared across these windows. The commitment has efficient simulators against both parties and yields device-independent coin tossing with abort; each uses one window. Completeness of oblivious transfer gives device-independent secure computation with abort for every efficiently computable classical functionality on a fixed number of parties, against static corruption of any proper subset, provided each reached call to oblivious transfer satisfies the device and budget conditions. The construction combines short selectors with code-based choice masking, a global audit, and error correction across field symbols. The commitment extractor changes a classical code coset while leaving the device execution and its leakage unchanged. Sender security uses a global Fourier analysis and a selector-aware Magic Square repetition bound derived from the two-round threshold theorem of Kundu and Tan (2023).

quant-ph · cs.CR

版本更新 · v2arXiv:2510.23316

Efficient Repair of (k+2, k) Degraded Read Friendly MDS Array Codes With Sub-packetization 2

Jie Li, Xiaohu Tang

原文摘要

In this paper, we present two constructions of degraded read friendly (DRF) MDS array codes with two parity nodes and a sub-packetization level of 2 over small finite fields, applicable for any arbitrary code length. The first construction achieves the smallest repair bandwidth among all existing constructions with the same parameters, and is asymptotically optimal with respect to the lower bound on the average repair bandwidth characterized by Zhang et al. The second construction supports two repair mechanisms, depending on whether computation within the helper nodes is permitted or not during the node repair process, thereby optimizing either the repair bandwidth or the rebuilding access.

cs.IT

版本更新 · v2arXiv:2606.01275

Domination-Avoiding Learning Agents Cannot Collude

Noam Nisan, Emmanuel Zerah

原文摘要

An influential paper of Calvano et al. empirically demonstrated that Q-learning agents spontaneously collude when placed as sellers that compete on prices in a natural market model. More recent results of Fish et al. empirically demonstrated that similar collusion happens with commercial LLMs. We formally prove that such collusion can also happen with external-regret-minimizing agents. We identify a very general class of agents, which we term Domination-Avoiding agents, that provably do not collude in such markets. This class contains all Mean-Based agents and all internal-regret-minimizing agents, as well as others such as Multiplicative-Weight agents with variable learning rate and contextual variants thereof. More generally we show that, in any game, this class of agents is guaranteed to jointly learn to almost never play strategies that are eliminated by repeated elimination of purely dominated strategies.

cs.GT

版本更新 · v2arXiv:2610.17613

MAS-Gate: Unlocking Multi-Agent System Lifecycle via Node-Centric Quantification

Hehai Lin, Zixuan Wang, Ming Yan, Peidong Wang, Shilei Cao, Minzhi Li, Bosheng Ding, Juepeng Zheng 等 9 位作者

原文摘要

Large language model (LLM)-based multi-agent systems (MAS) can solve complex problems beyond the reach of a single agent by decomposing tasks and coordinating complementary capabilities. Despite extensive research on MAS, existing work largely focuses on specific aspects or individual phases of their development and operation, resulting in fragmented perspectives with objectives and signals that are difficult to reconcile across these different settings. To bridge these disconnected perspectives, we conceptualize MAS development and operation as a three-phase lifecycle spanning design-time orchestration before execution, runtime intervention during execution, and post-hoc attribution after execution, and introduce MAS-Gate, a unified node-centric quantification applicable across these phases. Modeling each execution as a directed acyclic graph, MAS-Gate combines within-node utility, which estimates a node's contribution through changes in reference-answer likelihood, with inter-node strength, which approximates semantic uptake and potential downstream reach. We adapt this shared quantification to three objectives: providing a structure-aware dense reward for Orchestrator training, training an Editor to act on execution prefixes using paired rewards from completed edited and unedited trajectories, and supplying risk-ranked nodes as auxiliary evidence for LLM-based post-hoc attribution. Experiments spanning interaction environments, knowledge-intensive multi-hop question answering, general reasoning, and post-hoc attribution demonstrate that MAS-Gate improves workflow construction, targeted runtime editing, and LLM-assisted error localization over corresponding phase-specific baselines. Together, these results establish MAS-Gate as a unified structural interface for improving MAS generation, dynamic editing, and error attribution throughout the lifecycle.

cs.AI · cs.MA

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

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

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

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

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

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

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

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

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

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