跳到正文
研踪PaperTrail

版本更新

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

部分采集异常

全站更新概况

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

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

统计口径与数据新鲜度

统计 2026-11-18 12:11 — 2026-11-19 12:11(北京时间) · 点击数字查看对应简报;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.32721

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

Niels Inselmann Christiansen, Eva Rotenberg

原文摘要

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

cs.DS

版本更新 · v2arXiv:2608.22355

Recovery Beats Storage: Improved Space for Preprocessed 3SUM

Amir Carmel, Yakov Kosoburd, Robert Krauthgamer

原文摘要

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

cs.DS

版本更新 · v2arXiv:2610.06959

Nearly optimal Personalized PageRank computation

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

原文摘要

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

cs.DS · cs.CC

版本更新 · v2arXiv:2607.28610

Learning Arbitrary Lindbladians from Time Evolution

Zhili Chen, Zhan Yu

原文摘要

We study the problem of learning arbitrary $n$-qubit Lindbladians, the generators of Markovian open-system dynamics, from their time evolution. We give the first known efficient algorithm that learns arbitrary Lindbladians without any structural assumptions. For an $n$-qubit Lindbladian of dynamical strength at most $Λ$, the algorithm estimates every coefficient to error $\varepsilon$ using $\widetilde O(Λ^2/\varepsilon^2)$ experiments and $\widetilde O(Λ/\varepsilon^2)$ total evolution time, with classical running time polynomial in $n$ and $Λ/\varepsilon$. Both experimental costs match known lower bounds up to polylogarithmic factors. The algorithm identifies candidate labels through product Pauli experiments and estimates their coefficients using random stabilizer preparations and Clifford measurements. It requires no ancillas or control during the unknown evolution. For constant $k$, our algorithm learns generic $k$-local Lindbladians of local dynamical strength at most $Λ_{\mathrm{loc}}$ using $\widetilde O(n^2Λ_{\mathrm{loc}}^2/\varepsilon^2)$ experiments and $\widetilde O(nΛ_{\mathrm{loc}}/\varepsilon^2)$ total evolution time, improving the upper bounds of prior works in terms of the dependence on $n$. We further improve the lower bounds of Arad, Chen, Guo, Rebentrost, and Yu (SODA 2027) using a family of $3$-local Lindbladians. They already hold when the support is known, and only one Hamiltonian coefficient is requested, even for adaptive protocols with arbitrary ancillas and quantum memory. These lower bounds establish that our algorithm is optimal up to polylogarithmic factors in both experiment count and total evolution time for every fixed $k \geq 3$.

quant-ph · cs.DS

版本更新 · v2arXiv:2610.29817

Pfaffian Recognition is in $\mathsf{coRP}$

Priyanshu Pant, Ranveer Singh

原文摘要

An orientation of a graph is called Pfaffian if all perfect matchings occur with the same sign in its Pfaffian expansion. A graph is Pfaffian if it admits such an orientation. Given a Pfaffian orientation, the number of perfect matchings can be computed in polynomial time. In 1963, Kasteleyn showed that every planar graph is Pfaffian. In 1989, Vazirani and Yannakakis showed that deciding whether a graph is Pfaffian is polynomial time equivalent to testing whether a given orientation is Pfaffian. For bipartite graphs, polynomial time recognition algorithms were obtained by Robertson, Seymour, and Thomas in 1999, and independently by McCuaig in 2004. Whether a deterministic polynomial time algorithm exists for general graphs remains open. In this paper, we first construct a polynomial that is identically zero if and only if a given orientation is Pfaffian, and show that this polynomial can be evaluated in polynomial time. Combined with the reduction of Vazirani and Yannakakis, this gives a randomized polynomial time algorithm for deciding whether a general graph is Pfaffian, placing the problem in $\mathsf{coRP}$. We also prove that an orientation of a matching covered graph is non-Pfaffian if and only if reversing the edges of some cut makes it strongly connected. Although deciding whether such a cut exists is NP-complete for general digraphs, our characterization yields a randomized polynomial time algorithm for matching covered graphs and deterministic polynomial time algorithms for bipartite and planar matching covered graphs.

cs.CC · cs.DM

版本更新 · v4arXiv:2609.09940

NVV-Locator: From Transcript Tags to Acoustic Boundaries for Fine-Grained Nonverbal Vocalization Grounding

Yuang Cao, Bingshen Mu, Zhennan Lin, Guojian Li, Haoyue Zhan, Jie Liu, Chuan Xie, Qiang Zhang 等 10 位作者

原文摘要

Human speech includes nonverbal vocalizations (NVVs), such as laughter, sighs, breaths, and coughs, which convey affective and interactional information. Existing approaches typically represent NVVs as transcript-level tags, providing limited supervision for their waveform-time boundaries. We present NVV-Locator for fine-grained NVV temporal grounding. We first unify 26 NVV categories across public resources and construct large-scale timestamp-supervised training data through dual-LLM verification, transcript-guided forced alignment, and energy-based boundary refinement. We further introduce NVV-TimeBench, an expert-refined benchmark with 667 utterances and 1,094 events. NVV-Locator uses a non-autoregressive slot-filling architecture to jointly predict lexical timestamps, NVV categories, and event boundaries. On NVV-TimeBench, it achieves 71.0% Micro F1, 70.2% Macro F1, 80.4% Macro mIoU, and 59.6 ms Macro mMAE, outperforming the evaluated large audio model counterparts. Evaluation on an external corpus further demonstrates the cross-corpus generalization of NVV-Locator.

eess.AS · cs.SD

版本更新 · v2arXiv:2611.03393

TaoMate-FVSR: Audio-Guided Facial Video Restoration

Xinyang Li, Zeran Xu, Jingna Sun, Qijun Gan, Chenwei Zhang, Meiguang Jin, Junfeng Ma

原文摘要

Low-quality facial videos suffer from missing fine details, while AI-generated videos may additionally contain implausible teeth and lip movements that do not match the speech. Restoring the mouth region is particularly challenging: enhancing existing details can preserve structural errors, whereas regenerating them risks changing facial identity and articulation. We propose an audio-guided facial video restoration framework that reconstructs unreliable mouth details and aligns lip movements with the speech while preserving facial identity and temporal consistency. Built on a video diffusion transformer, our framework mixes input video latents with noise to retain useful source information while allowing corrupted details to be regenerated. Audio guides lip movements, reference images constrain facial appearance, and previously generated frames promote temporal consistency. We train the model in two stages, first learning visual restoration from degraded images and videos, then learning audio-guided lip correction from degraded dubbed videos. The resulting model supports both restoration with the original audio and visual dubbing with replacement audio. On talking-head restoration benchmarks, our method achieves the lowest LPIPS and DISTS and the best lip synchronization scores among the evaluated restoration baselines. Qualitative results on AI-generated videos further show improvements in facial detail and mouth-region appearance, including clearer tooth boundaries and lip contours.

cs.CV

版本更新 · v5arXiv:2508.21380

The Algorithm Is Not the Behavior: Learned Priors Override Look-Ahead in a Chess-Playing Neural Network

Elias Sandmann, Sebastian Lapuschkin, Wojciech Samek

原文摘要

Recent mechanistic work has uncovered learned algorithms within neural networks, from modular arithmetic to search and planning in game-playing agents. But does algorithmic structure guarantee algorithmic behavior? We investigate this in Leela Chess Zero, the strongest neural chess engine, where prior work identified learned look-ahead. By extending the logit lens to its move-selecting policy network, we discover that correct puzzle solutions--including immediate checkmates--often appear in intermediate layers but are systematically overridden in the final output, a phenomenon we term "forgotten puzzles". Replicating prior analyses on these positions, we find that look-ahead operates normally--future moves of the correct continuation are represented, causally important, and linearly decodable--ruling out a failure of the algorithm. Instead, late layers increasingly shift toward safe play over aggression. To test whether this shift drives the override, we steer the model against these preferences and recover 71.7% of forgotten puzzles, providing causal evidence that safety priors override algorithmically computed solutions. These findings show that algorithmic structure does not guarantee algorithmic behavior: a model can internally solve a problem and still output the wrong answer.

cs.LG · cs.AI

版本更新 · v4arXiv:2601.21929

LoRIF: Pushing the Scalability Frontier of Training Data Attribution

Shuangqi Li, Hieu Le, Jingyi Xu, Mathieu Salzmann

原文摘要

Training data attribution (TDA) identifies which training examples most influenced a model's prediction. Influence function methods are a theoretically grounded family of TDA methods and exploit gradients. To overcome the scalability challenge arising from gradient computation, the most popular strategy is random projection (e.g., TRAK, LoGRA). However, this still faces two bottlenecks when scaling to large training sets and high-quality attribution: \emph{(i)} storing and loading projected per-example gradients for all $N$ training examples, where query latency is dominated by I/O; and \emph{(ii)} forming the $D \times D$ inverse Hessian approximation, which costs $O(D^2)$ memory. Both bottlenecks scale with the projection dimension $D$, yet increasing $D$ is necessary for attribution quality -- creating a quality--scalability tradeoff. We introduce \textbf{LoRIF} (\textbf{Lo}w-\textbf{R}ank \textbf{I}nfluence \textbf{F}unctions), which exploits low-rank structures of gradient to address both bottlenecks. First, we store rank-$c$ factors of projected per-example gradients rather than full matrices, reducing storage and query-time I/O from $O(D)$ to $O(c\sqrt{D})$ per layer per sample. Second, we use truncated SVD with the Woodbury identity to approximate the inverse Hessian term in an $r$-dimensional subspace, reducing memory from $O(D^2)$ to $O(Dr)$. On models from 0.1B to 70B parameters trained on datasets with millions of examples, LoRIF achieves up to 20$\times$ storage reduction and query-time speedup compared to LoGRA, while matching or exceeding its attribution quality. LoRIF makes gradient-based TDA practical at frontier scale. Code is available at https://github.com/doub7e/LoRIF.

cs.LG

版本更新 · v2arXiv:2601.20638

Supply Chain Insecurity: Exposing Vulnerabilities in iOS Dependency Management Systems

David Schmidt, Gabriel K. Gegenhuber, Edgar Weippl, Sebastian Schrittwieser

原文摘要

Dependency management systems are a critical component in software development, enabling the incorporation of existing functionality. However, misconfigurations and malicious actors in these systems pose security risks, leading to supply chain attacks. Despite the widespread use of smartphone apps, the security of dependency management systems in the iOS software supply chain has received limited attention. In this paper, we focus on CocoaPods, one of the most widely used dependency management systems for iOS app development, but also examine the security of Carthage and Swift Package Manager (SwiftPM). We demonstrate that iOS apps expose internal dependency names and versions. Attackers can exploit this information to register previously unclaimed dependencies in CocoaPods, enabling remote code execution (RCE) on developer machines and build servers. Additionally, we show that attackers can compromise dependencies by reclaiming abandoned domains and GitHub URLs. Analyzing 9,491 real-world iOS applications, we find that a significant fraction is vulnerable to these attacks, putting millions of users at risk, including applications from major organizations for which we confirmed exploitation via responsible disclosure. Finally, we compare iOS dependency management systems with Cargo, Go modules, npm, pip, and Maven, and discuss conceptual issues and practical mitigation strategies.

cs.CR

版本更新 · v2arXiv:2605.28048

SAFEVPR: Patch-Based Verification with Empirical FDR Control for Cross-Condition Sequence Visual Place Recognition

Ha Sier, Jiaqiang Zhang, Zhuo Zou, Xianjia Yu, Tomi Westerlund

原文摘要

Sequence-based visual place recognition (VPR) for loop closure and robot relocalization must decide whether the retrieved top-1 candidate should be accepted. Conformal calibration can set this accept/reject threshold, but its finite-sample guarantees require exchangeability between calibration and deployment, a requirement that cross-condition deployment violates. We therefore claim no formal guarantee under condition shift: this paper instead asks which verification score and calibration design keep a target false-discovery rate (FDR) empirically satisfied across realistic appearance change. We present SAFEVPR, a non-trainable pipeline that replaces the backbone cosine similarity with a mutual-nearest-neighbour (MNN) patch score from frozen DINOv2 features, and flat Learn-Then-Test (LTT) calibration with per-bin Clopper-Pearson thresholds. Across 23 cross-condition ground-vehicle setups (Oxford RobotCar, NCLT, St Lucia; three frozen backbones), SAFEVPR meets the FDR target on 23/23 setups at alpha = 0.10 (mean accepted FDR 0.014, mean TPR 0.75) and on 22/23 at alpha = 0.05 with 22 retaining non-trivial coverage (best cosine variant, cosine+LTT: 22/23 valid but 17 non-trivial); under leave-one-dataset-out calibration, validity drops to 20/23 with 14 retaining useful coverage (strongest cosine baseline: 16/23 and 10), and on texture-poor scenery (Nordland) the verifier is uninformative and the system abstains entirely, as it does everywhere at alpha = 0.01; we report these as limitations. In a pose-graph relocalization study, gating loop-closure constraints reduces erroneous constraints by 29.6x and cuts the median trajectory error from 95.5 m to 9.7 m. Code is available at https://github.com/TIERS/SafeVPR.

cs.RO

版本更新 · v2arXiv:2605.18805

RecoAtlas: A Benchmark and RL Environment for LLM Recommendation Agents Optimizing Set-Level Utility

Imad Aouali, Flavian Vasile, Clijo Jose, Otmane Sakhi, Alexandre Gilotte, Benjamin Heymann

原文摘要

LLM recommender agents increasingly produce structured reports: sets of items accompanied by natural-language justifications. Yet existing benchmarks often focus on reranking small candidate sets or judging reports primarily by semantic plausibility, providing limited support for evaluating and training agents based on set-level utility. We introduce Recommender Atlas (Agentic Tasks for Learning and Assessment in Shopping), or RecoAtlas, a benchmark and reinforcement learning environment grounded in user behavior. RecoAtlas provides a shopping toolkit for product retrieval, complementarity, and diversity. Given a shopping query, an agent uses these tools to generate a structured recommendation report. Behavioral reference sets support exact-recovery evaluation and the training of a learned bundle-level reward that supplies feedback for policy optimization with RL. Its controlled tool environment exposes agents to semantic and behavior-aligned tools, enabling systematic analysis of how LLM reasoning, tool signals, and tool-use policies contribute to performance. Across controlled experiments, performance scales with model capacity and test-time compute, and improves with stronger tools, while semantic plausibility does not necessarily translate into behavior-grounded utility. RecoAtlas provides a foundation for training and evaluating shopping assistants to move beyond semantic plausibility toward coherent, behaviorally grounded recommendation sets.

cs.IR · cs.AI · cs.LG

版本更新 · v2arXiv:2604.11656

Scalable Exact Hierarchical Agglomerative Clustering via Sparse Geographic Distance Graphs

Victor Maus, Vinicius Pozzobon Borin

原文摘要

Exact hierarchical agglomerative clustering (HAC) of large spatial datasets is limited in practice by the $\mathcal{O}(n^2)$ time and memory required for the full pairwise distance matrix. We present GSHAC (Geographically Sparse Hierarchical Agglomerative Clustering), a system that makes exact HAC feasible at scales of millions of geographic features on a commodity workstation. GSHAC replaces the distance matrix with a sparse geographic distance graph containing only pairs within a user-specified geodesic bound $h_{\max}$, constructed in $\mathcal{O}(n \cdot k)$ time via spatial indexing, where $k$ is the mean number of neighbors within $h_{\max}$. Connected components of this graph define independent subproblems, and we prove that the resulting assignments are exact for all standard linkage methods at any cut height $h \le h_{\max}$. For single linkage, an MST-based path keeps memory at $\mathcal{O}(n_k + m_k)$ per component. Applied to a global mining inventory ($n = 261{,}073$), the system completes in 12 s (109 MiB peak HAC memory) versus $\approx 545$ GiB for the dense baseline. On a 2-million-point GeoNames sample, all tested thresholds completed in under 3 minutes with peak memory under 3 GiB. We provide a scikit-learn-compatible implementation for direct integration into GIS workflows.

cs.DS · cs.CG

版本更新 · v2arXiv:2611.01517

VLMs Read Aloud: The Gap Between Recognizing and Using Visual Text

Zhiyun Shi

原文摘要

Visual-text compression renders long contexts as images and is engineered around how much of the text a vision-language model (VLM) can recover. Yet recovered text is not usable text. VLMs can transcribe the text in an image word for word and still fail to answer from it; given back their own transcript, they answer nearly as well as from the original text. We call this difference the read-use gap. Recognizing and using visual text have different resolution requirements: Qwen3-VL-8B's recognition saturates at 15-pixel characters while use catches up only at 24 pixels, and scaling from 2B to 32B raises recognition without narrowing the gap. Putting the evidence into words closes it: thinking VLMs recite the evidence in their thinking, and their own transcript, written without seeing the question, recovers most of what thinking adds. In a preregistered held-out test, the gap ranks how much eight VLMs gain from their own words over pixels (Spearman $ρ$ = 0.86), which recognition rates do not. We propose ALOUD, which spends visual resolution on finding and recognizing evidence and language tokens on using it. Without keeping the source text, it doubles the accuracy of a frozen Qwen3-VL-8B on long documents compressed 5x and 10x: at 5x, from 27.7% to 54.8%, near the original text's 58.5%, with a context smaller than the compressed pages themselves. For less than the cost of reading the original text, it leads at equal budget every method that does without it, at every level, and beats AGAR and VERA, which paste the original text back; at 5x it also beats LensVLM-9B, which is trained and keeps the original text. Visual-text compression is limited not by how much text a model can recover, but by how much it can use.

cs.CV · cs.CL

版本更新 · v2arXiv:2605.31275

Personalized to Persuade: The Effects of Contextualization and Warmth on Trust and Reliance in Conversational AI

Mert Yazan, Suzan Verberne, Frederik Bungaran Ishak Situmeang

原文摘要

Contextualization is a form of personalization in which the message is framed in a context meaningful to the recipient, using their interests and background. Personalization is a known persuasive strategy of artificial intelligence (AI) systems in politics and marketing. However, the persuasive effect of contextualization in everyday tasks, where users often lack prior knowledge, remains unclear. We ran a $2\times2$ between-subjects experiment ($N = 407$) in a fictional scenario where participants had no prior opinions or knowledge. We examined how contextualization, combined with conversational warmth, shapes the persuasive power of an AI assistant arguing against expert recommendations and users' reliance on it. Our findings show that the neutral, non-contextualized assistant was the most persuasive. Contextualization and warmth each reduced persuasiveness on their own, but their interaction increased it. Reliance was present in all conditions, and neither cue changed it detectably. Trust predicted persuasion and reliance, yet neither contextualization nor warmth had an indirect effect through trust. Participants with higher self-reported AI literacy relied more on the assistant without trusting it more. Our study extends AI personalization research from political opinions to everyday decisions made without prior knowledge. The results suggest that users are more likely to be persuaded by, and defer to, an AI assistant than an expert, even without personalization. AI persuasion experiments should therefore include untailored assistants and measure decisions; the cues that changed persuasion did not detectably change reliance.

cs.HC · cs.AI

版本更新 · v2arXiv:2610.29595

Near Minimax Rates for Quantile Distributional Reinforcement Learning

Zijie Cheng, Zhihua Zhang

原文摘要

In this paper, we study quantile distributional policy evaluation, where the return distribution under a given policy is approximated by the quantile Bellman fixed point $\bmη_m$. We investigate the statistical accuracy of estimating $\bmη_m$ across quantile resolutions under Wasserstein distances. Assuming access to a generative model, we construct a quantile fixed point estimator $\bmη_m^{(n)}$ from an empirical Markov decision process of $n$ observations per state-action pair and establish non-asymptotic error bounds under Wasserstein distances. When reward densities are uniformly bounded away from zero, we obtain a root-$n$ high-probability bound simultaneously over all resolutions $m$ and all Wasserstein orders $1\le p\le\infty$. When reward densities vanish at the support endpoints, we show that continuity and endpoint monotonicity suffice to preserve the same resolution-independent rate for $1\le p\le2$. For $p>2$, we establish a root-$n$ bound with coefficient $m^{1/2-1/p}$, together with a slower, resolution-independent $n^{-1/p}$ bound for every finite $p>2$. We further obtain resolution-independent $W_\infty$ consistency governed by the continuity modulus of reward quantile functions. To investigate the sharpness of these bounds, we characterize the exact local asymptotic minimax risk at each fixed resolution as the expected Wasserstein-coordinate norm of the efficient Gaussian limit and prove that our estimator attains it. We then examine the resolution dependence of this optimal local risk. A regular one-state instance has resolution-independent local risk constants, whereas a single endpoint-vanishing two-state instance exhibits growth of order $m^{1/2-1/p}$, up to logarithmic factors along a resolution subsequence, for every $p>2$.

stat.ML · cs.LG

版本更新 · v3arXiv:2609.22377

Forecasting Brain Tracer Distribution from Pre-Contrast MRI: A Comparison of Direct Regression and Flow Matching

Qinghui Liu, Jon André Ottesen, Thu Nguyen, Geir Ringstad, Ingrid Mossige, Siri Fløgstad Svensson, Sissel Riis Kalstad, Atle Bjørnerud 等 10 位作者

原文摘要

The brain fluid clearance system can be studied with intrathecal contrast-enhanced magnetic resonance imaging (MRI). By injecting a tracer into the spinal canal and performing MRI over 24--48\,h, one can measure how a tracer injected into the cerebrospinal fluid spreads through the brain. As this is an invasive procedure requiring several MRI scans, we ask how much of the later tracer distribution can be predicted from the pre-contrast scan and elapsed time alone. Using 104 training patients (878 MRI volumes), we compared a direct image-to-image regression model with a more complex generative model based on conditional flow matching, and tested both on 23 held-out patients and on 51 patients from a separate cohort with idiopathic normal pressure hydrocephalus (iNPH). Relative to simply copying the pre-contrast scan, the direct model reduced the mean absolute error (intensities normalized to $[0,1]$) from 0.089 to 0.036, about 60\%, in held-out patients and from 0.075 to 0.056, about 25\%, in the iNPH cohort. The reduction held in every sampled elapsed-time interval and brain compartment, and errors remained largest at 20--30\,h and in the ventricles, where enhancement is strongest. Its predicted change maps agreed with the observed tracer enhancement rather than only reproducing anatomy. The generative model was less accurate in both cohorts. A substantial part of the later tracer distribution is therefore predictable from the patient's brain anatomy as seen on pre-contrast MRI, and the added model complexity gave no benefit at this data scale. Whether this accuracy suffices for a given clinical use remains to be established; with prospective validation, such forecasts could help simplify the MRI protocol used to assess brain clearance.

eess.IV · cs.AI · cs.CV · cs.LG

版本更新 · v2arXiv:2611.00769

DramaVQA: Probing Detailed Understanding of Ultra-Long TV Dramas

Xinyue Huo, Pengfei Chen, Jiannan Ge, Kaiwen Duan, Jiacheng Shao, Yunning Cao, Lingxi Xie, Qi Tian

原文摘要

Despite recent progress in long-form video understanding, current benchmarks mostly focus on short clips or hour-scale videos. This leaves a major gap in evaluating ultra-long video understanding, where videos often last tens of hours. To bridge this gap, we introduce DramaVQA, a large-scale benchmark built upon long-form TV dramas. Containing approximately 20K question-answering (QA) pairs, the scale of DramaVQA exceeds previous long-video datasets, such as Video-MME and LVBench, by an order of magnitude. Our benchmark has two main features that make it stand out from existing datasets. First, we establish a scalable, LLM-assisted annotation pipeline that uses multimodal large language models (MLLMs) to generate complex questions, followed by strict human checking to ensure high data quality. Second, DramaVQA introduces a multi-level time structure; queries are designed across different video lengths, with the hardest questions requiring overall understanding across the entire drama. Extensive evaluations show that state-of-the-art MLLMs face major challenges when tested on these very long videos, highlighting the need for agentic AI algorithms capable of managing long-term memory. The project is available at https://github.com/xinyuehuo/DramaVQA

cs.CV

版本更新 · v2arXiv:2610.34373

Tight Coreset Bounds for $(k,z)$-Clustering in Euclidean and Doubling Metrics

Junqiu Hu, Lingxiao Huang, Jian Li, Baoduo Xu

原文摘要

We determine the optimal worst-case size of strong coresets for $(k,z)$-clustering in Euclidean spaces and doubling metrics, up to polylogarithmic factors. In Euclidean space, previous lower bounds matched the best upper bounds only for $\varepsilon\gtrsim k^{-1/(z+2)}$. We close the gap for arbitrarily small $\varepsilon$, establishing the optimal size $\widetildeΘ(\min\{k^{(2z+2)/(z+2)}\varepsilon^{-2},\,k\varepsilon^{-z-2}\})$ for every fixed $z\ge1$, all $k\ge1$, and $0<\varepsilon<1$. Our lower bound replaces each offset in a previous hard instance by a group of distinct offsets. A fixed family of $k$-center queries and four-wise independent signs force a large relative cost error for every sufficiently small subset with arbitrary nonnegative weights. For doubling metrics of dimension $D$, we resolve the previously unmatched bounds for $z>2$. We prove an upper bound of $\widetilde O(k^{2-2/z}D\varepsilon^{-2})$ and a lower bound that, together with known upper bounds, establishes the optimal size $\widetildeΘ(kD\min\{k^{1-2/z}\varepsilon^{-2},\,\varepsilon^{-z}\})$ for fixed $z>2$, $0<\varepsilon\le\varepsilon_z$, and $D\ge C_z\log(2/\varepsilon)$, where $C_z>0$ and $\varepsilon_z\in(0,1)$ depend only on $z$. The lower bound exploits the ability to encode $Θ(D)$ independent signs per center without diluting relative cost discrepancy. For the upper bound, we use independent, unbiased two-point summaries that exactly preserve cluster mass and anchor cost, combined with iterative size reduction.

cs.DS · cs.CG

版本更新 · v2arXiv:2609.11912

Existence of the Core in Approval-Based Committee Elections

Patrick Becker, Matthias Greger, Dominik Peters

原文摘要

We resolve the central open question in the theory of approval-based committee elections: we prove that the core is always non-empty. This means that there always exists a committee for which no coalition of voters can deviate to an alternative committee of proportional size that every member strictly prefers. This property was introduced by Aziz et al. (2017) to capture proportional representation and coalitional stability, but no known algorithm achieved it except up to a constant approximation factor or in special cases. Our approach begins by strengthening the core to core+, which requires the committee to be robust even to fractional deviations. Using LP duality, this property can equivalently be defined in terms of a payment-based certificate under which no losing candidate gathers too much support. We then define a voting rule that chooses a committee admitting a certificate that maximizes a novel harmonic entropy objective function, which rewards balanced payment distributions. We show that the payment system associated with an optimal committee certifies that the committee satisfies core+, establishing existence. The same is true for local optima, which allows us to design a polynomial-time algorithm computing a core+ committee.

cs.GT

版本更新 · v2arXiv:2604.07233

How Does Machine Learning Manage Complexity?

Lance Fortnow

原文摘要

We provide a computational complexity lens to understand the power of machine learning models, particularly their ability to model complex systems. Machine learning models are often trained on data drawn from sampleable or more complex distributions, a far wider range of distributions than just computable ones. By focusing on computable distributions, machine learning models can better manage complexity via probability. We abstract away from specific learning mechanisms, modeling machine learning as producing P/poly-computable distributions with polynomially-bounded max-entropy. We illustrate how learning computable distributions models complexity by showing that if a machine learning model produces a distribution $μ$ that models the distribution generated by a cryptographic pseudorandom generator at least as well as the uniform distribution does, then $μ$ must be close to uniform. We view training as compression that removes the randomness from the data, keeping only its structure, and inference as adding randomness back to generate new outputs. A computationally bounded model cannot distinguish pseudorandomness from true randomness, so training removes both, treating anything it cannot efficiently predict as noise. The same holds at inference, where the randomness added back can be, and in practice is, pseudorandom. In the appendix, we make the connection to compression precise and, using a characterization of pseudoentropy by Vadhan and Zheng, show that the best loss achievable by an efficient model is the next-bit pseudoentropy of the data.

cs.LG · cs.CC

版本更新 · v3arXiv:2607.13284

Tight Bounds for $(1+ε)$-Approximation for Minimum Spanning Trees in Doubling Metrics

Jan Höckendorff, Felix Hommelsheim, Christian Sohler, Di Yue

原文摘要

The minimum spanning tree (MST) problem is one of the most basic optimization problems on metric spaces and graphs. We study the problem of computing a $(1+ε)$-approximation to the MST of an $n$-point metric space of doubling dimension $\mathrm{ddim}$. In doubling metrics, previous deterministic algorithms incur a running time with dependence $ε^{-O(\mathrm{ddim})}$. We give a deterministic algorithm that computes a $(1+ε)$-approximate MST in time $$ O_{\mathrm{ddim}}\left(n\log n+ \min\left\{n^2,\frac{n}ε\log(1/ε)\right\}\right) $$ in the standard real RAM model with a unit-cost exact-distance oracle. For bounded doubling dimension, this improves the previous dependence on $ε$ to essentially linear in $ε^{-1}$. We complement this algorithm with a lower bound of $$ Ω\!\left(n\log n+ \min\left\{n^2,\frac{n}ε\log(1/ε)\right\}\right) $$ on running time in the same model, already for metrics of doubling dimension at most seven, showing that our running time is essentially tight. For points in $\mathbb R^d$ with $d = O(1)$, exploiting Euclidean geometry allows us to further improve the dependence on $ε$. We obtain a $(1+ε)$-approximate MST in expected time $$ O_d\left( n \log n + \min\left\{n^2, \frac{n}{ε^{1 - β_d}} \log^{1-β_d}(1/ε) \right\} \right) $$ for some $β_d=Θ(1/d)$, improving the accuracy-dependent term $nε^{-2}\log^2(1/ε)$ of Arya and Mount [SODA'16].

cs.DS

版本更新 · v2arXiv:2610.42147

Latent Sparse Attention: Towards Subquadratic Ultra-Long Context Attention

Ales Kubicek, Andrea Caciolai, Liangzu Peng, Sukrit Sumant, Benjamin Hoover, Fraser Greenlee, Ruairidh M. Battleday, Radim Urban 等 10 位作者

原文摘要

Agentic workflows are increasingly shifting towards long-horizon tasks, such as open-ended scientific work, where models benefit from long context windows. However, at ultra-long context (above 1M tokens), full attention is prohibitively expensive. A promising approach is sparse attention, in which a dedicated indexer selects a subset of keys for the attention. Yet current methods of indexing either still have quadratic cost in context size or lose accuracy at ultra-long context scale. We address this with Latent Sparse Attention (LSA), an efficient attention method that maintains accuracy at ultra-long context. In LSA, keys are hierarchically clustered in a learned latent space, and queries score the hierarchy of clusters instead of scoring every key, making prefill, decode and training faster at long context. We propose two variants, Distilled-LSA (D-LSA), which can be applied to pre-trained models via distillation, and Native-LSA (N-LSA), which is trained natively on the next-token loss alone. On GLM-5.3-FLASH (QWEN-3.8-27B) at 10M tokens, D-LSA speeds up one attention layer by 22.7x (72.4x) in prefill and 4.6x (42.5x) in decode over its original sparse attention (full attention), while keeping similar accuracy across a variety of tasks. N-LSA matches the accuracy of full attention with a training speedup of 1.6x per layer at 128k tokens. LSA offers practical and efficient attention for models to benefit from ultra-long context.

cs.AI

版本更新 · v2arXiv:2606.31585

DPPE: Rethinking Camera-Based Positional Encoding for Scaling Multi-View Transformers

Shun Kenney, Teppei Suzuki

原文摘要

The remarkable scalability of Transformers has expanded their application to 3D computer vision, where camera-aware positional encoding is crucial for providing spatial cues in multi-view geometry. Recent advancements have established the practice of using camera parameters---such as extrinsics or projection matrices---as relative positional encoding into the query, key, and value vectors of the attention mechanism. However, when scaling up the training recipe of novel view synthesis (NVS) models with the camera-based positional encoding, we observe a significant issue: model performance stagnates in the late stages of training. In this paper, we investigate the cause of the performance bottleneck when scaling up and demonstrate that storing rotation and translation given by the positional encoding in the same dimensions of the value vector causes indeterminacy in their independent identification, hindering training scalability. To address this, we propose Decoupled Pose Positional Encoding (DPPE), a novel camera-based positional encoding that explicitly decouples rotation and translation. Extensive evaluations on NVS tasks demonstrate that DPPE enables stable long-term training even in scaled-up training setup. Furthermore, it exhibits superior generalization performance in extrapolation settings, such as handling an increased number of viewpoints and zoom-in scenarios. Code is available at https://github.com/sbintuitions/dppe.

cs.CV · cs.AI

版本更新 · v3arXiv:2610.40982

Strong Lower Bounds for Weak Epsilon-Nets

Sujoy Bhore, Reilly Browne, Da Wei Zheng

原文摘要

Let $P$ be a finite point set in $\mathbb{R}^d$. A weak $\varepsilon$-net for $P$ with respect to convex sets is a finite set $X\subset\mathbb{R}^d$ intersecting every convex set containing at least $\varepsilon|P|$ points of $P$. Determining their optimal worst-case size was described by Alon, Kalai, Matousek, and Meshulam [Adv. Appl. Math., 2002] as "one of the truly important open problems in combinatorial geometry." We give elementary constructions which establish the first polynomially superlinear lower bounds in fixed dimension. Already in $\mathbb{R}^3$, we construct point sets for which every weak $\varepsilon$-net has size $Ω(\varepsilon^{-3/2})$. More generally, for every fixed $d\ge3$, we obtain a lower bound of $Ω_d(\varepsilon^{-γ_d})$, where $γ_d=\sqrt{d/2}+O(1)$. Consequently, no upper bound of the form $O_d(\varepsilon^{-C})$ can hold with an absolute constant $C$ which is independent of the dimension. Despite the recent progress on upper bounds, the strongest previous general lower bound remained $Ω_d(\varepsilon^{-1}\log^{d-1}(1/\varepsilon))$, due to Bukh, Matousek, and Nivasch [Israel J. Math., 2011]. To obtain our results, we apply a quadratic lift to grid-based configurations with many point-line incidences. The bounds also yield polynomial separations between fractional and integral piercing numbers of convex families, and lower bounds for Hadwiger-Debrunner numbers.

cs.CG

版本更新 · v2arXiv:2605.03830

Identity-Consistent Multi-Pose Generation of Contactless Fingerprints

Zhiyu Pan, Zhaoliang Xu, Xiongjun Guan, Jianjiang Feng, Jie Zhou

原文摘要

Contactless fingerprint recognition has gained increasing attention due to its advantages in hygiene and acquisition flexibility. However, the absence of physical contact constraints introduces severe nonlinear geometric distortions caused by free finger poses in 3D space, resulting in a substantial cross-modal domain gap between contactless and conventional contact-based fingerprints. Existing solutions largely rely on explicit geometric correction or image enhancement, which are fragile under extreme pose variations. In this paper, we propose Identity-Consistent Multi-Pose Generation of Contactless Fingerprints (IMPOSE), a physics-inspired framework that synthesizes identity-preserving, multi-pose contactless fingerprint samples to empower recognition models. IMPOSE consists of three stages: (1) rolled fingerprint identity generation via latent diffusion with discrete codebook representations, (2) cross-modal translation from rolled to contactless modality guided by Sauvola-based local adaptive binarization as an identity anchor, and (3) physics-based multi-pose simulation through 3D finger model texture mapping and projection. The generated samples maintain strict identity consistency at the ridge topology level and spatial alignment with standard fingerprint coordinate space. Extensive experiments on the UWA and PolyU CL2CB databases demonstrate that fine-tuning fixed-length dense descriptors (FDD) with IMPOSE-synthesized data achieves state-of-the-art cross-modal matching, reducing EER to 8.74% on UWA and 2.26% on PolyU CL2CB. Synthetic data also yields consistent gains across mainstream representations including DeepPrint and AFRNet, and the hybrid strategy combining synthetic and real data achieves the best overall results. The code and generated samples are available at https://github.com/Yu-Yy/IMPOSE.

cs.CV

版本更新 · v2arXiv:2609.02977

Learning Fourier-Sparse Signals and Multiband Signals

Dongrun Cai, Xue Chen, Xiaowei Shao, Yile Wang

原文摘要

A classical problem in continuous sparse Fourier transforms, which dates back to Prony's work in 1795, is to learn a $k$-Fourier-sparse signal $x(t):=\sum_{j=1}^k α_j e^{2 π\mathbf{i} f_j t}$ with arbitrary $k$ frequencies $f_1,\ldots,f_k \in \mathbb{R}$. We consider this learning problem within a fixed time window $t \in [-1,1]$ in the presence of bounded $L_2$ adversarial noise. Because the frequencies $f_1,\ldots,f_k$ can be arbitrarily close, accurately recovering individual frequencies is information-theoretically impossible even under exponentially small noise from Moitra (STOC 2015). This work therefore examines two fundamental questions: If an algorithm uses $\tilde{O}(k)$ frequencies to approximate $f_1,\ldots,f_k$ of $x$, what is the optimal covering error? And how can we efficiently learn the continuous signal $x(t)$ as a whole over the time window? Our main result is an algorithm running in time $\tilde{O}(k)$ that outputs a list $L$ of $\tilde{O}(k)$ frequencies with covering error $O(k)$ --- meaning that for most frequencies $f_j$ of $x$, $L$ guarantees $\min_{\tilde{f} \in L} |f_j-\tilde{f}| = O(k)$ --- and an reconstruction $\tilde{x}(t) \approx x(t)$ over $[-1,1]$. When constrained to outputting $\tilde{O}(k)$ frequencies, this $O(k)$ covering error is nearly optimal: Chen and Price (ICALP 2019) demonstrated two indistinguishable $k$-Fourier-sparse signals separated by distance $\tildeΩ(k^2)$ in the frequency domain, which implies an amortized lower bound of $\tildeΩ(k)$ per frequency. Furthermore, our sample and time complexities are nearly optimal, dramatically improving upon the previous best algorithm by Song, Sun, Weinstein, and Zhang (FOCS 2023), which required $\tilde{O}(k^4)$ samples and $\tilde{O}(k^{4ω})$ running time.

cs.DS

版本更新 · v2arXiv:2610.15044

PAT: A Personality-Driven Augmentation and Transfer Learning Framework for Depression Detection on Social Media

Shengwu Zheng, Yuzhe Ding, Xiaohui Liang, Fei Li, Chong Teng, Donghong Ji

原文摘要

Depression is a prevalent mental disorder that affects millions worldwide, with early detection crucial for effective intervention. While exist?ing methods have achieved promising results in automated depression detection, they face two key limitations: (1) noise in post screening: symptom-based semantic screening is easily misled by superficial lexical patterns, thereby introducing false-positive posts; (2) weak op?timization of the post encoder: relying solely on coarse user-level supervision signals pre?vents models from capturing depressive cues within individual posts. To address these limita?tions, we propose PAT, a Personality-driven Augmentation and Transfer learning frame?work. In the first phase, PAT optimizes a post?level encoder via a fine-grained contrastive learning objective, utilizing LLM-based data augmentation driven by classic personality the?ories to alleviate data scarcity. In the second phase, the trained post-level scorer is deployed for high-quality post filtering, while its en?coder parameters are seamlessly transferred for user-level tasks. Extensive experiments demon?strate that PAT significantly outperforms exist?ing methods. Furthermore, PAT delivers multi?granular interpretability by tracing post-level mental-state trajectories and highlighting key symptoms, thereby offering reliable diagnostic evidence for clinical practice.

cs.CL

版本更新 · v3arXiv:2606.11420

Context-Aware Multimodal Claim Verification in Spoken Dialogues

Chaewan Chun, Delvin Ce Zhang, Dongwon Lee

原文摘要

Spoken factual claims often occur within multi-turn conversations, where surrounding dialogue can provide context unavailable from the claim alone. Yet most fact-checking research evaluates isolated text, leaving conversational audio under-studied. We introduce MAD2, a synthetic Multi-turn Audio Dialogues benchmark for spoken claim verification with 1,000 two-speaker dialogues, 1,230 sentence-level check-worthy candidate annotations, and approximately 10 hours of audio. We also propose calibrated multimodal fusion of a context-aware audio encoder and a dialogue-aware text model. Adding dialogue context improves verification across settings, although the gains vary by scenario. Past-only context often approaches local offline performance, suggesting its usefulness when future context is unavailable. Fusion achieves its highest mean advantage over text with full-dialogue context, but does not consistently or significantly outperform text across settings. Under full-dialogue context, exploratory subgroup results show greater performance variation across dialogue scenarios for text and fusion, but across spread styles for audio.

cs.CL · cs.SI

版本更新 · v4arXiv:2603.14358

A Unified Pulse-Shaped OFDM Framework for Chirp-Domain Waveforms: Continuous-Time Modeling and Practical I/O Analysis

Yating Jiang, Hai Lin, Yi-Han Chiang, Jun Tong

原文摘要

A unified framework for chirp-domain waveforms, including orthogonal chirp division multiplexing (OCDM) and affine frequency division multiplexing (AFDM), is developed. Their continuous-time representations are shown to fall within the conventional Weyl-Heisenberg (WH) framework for multicarrier waveforms, with the root chirp as the prototype pulse. Since the root chirp has constant envelope and is transparent to subcarrier orthogonality, these waveforms can be further interpreted as pulse-shaped (PS) orthogonal frequency division multiplexing (OFDM) signals, whose power spectral density is derived analytically. The derived spectrum reveals that implementations based on the discrete affine Fourier transform rely on sub-Nyquist samples and exhibit frequency aliasing. We prove that the corresponding aliased chirps are only conditionally orthogonal, whereas sample-wise root-Nyquist pulse shaping of the discrete-time AFDM (DT-AFDM) sequence produces mutually orthogonal pulse-shaped chirps, resulting in the pulse-shaped AFDM (PS-AFDM) waveform. We then derive an exact waveform-level input-output (I/O) relation for PS-AFDM over delay-Doppler (DD) channels, showing that the effective channel at a practical receiver is generally not a superposition of pure path-wise DD components. Waveform simulations verify the derived relation to machine precision, while the conventional sequence-level I/O relation for DT-AFDM exhibits a substantial mismatch with waveform behavior for practical channels with continuous-valued delays.

cs.IT · eess.SP