跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+1085新增论文
+884其中 AI 相关
+130已有论文修订
+94新增 AI 导读

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

统计口径与数据新鲜度

统计 2026-11-18 06:59 — 2026-11-19 06: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 社区发现

浏览论文库

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

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

具有 O(n log n/ε²) 条弧的有向奇异值稀疏化器

Directed Singular-Value Sparsifiers with $O(n \log n/ε^2)$ Arcs

Emile Anand

AI 速读 基于摘要

作者证明每个 n 顶点无权有向图都存在至多 O(n log(2n)/ε²) 条弧的 ε-奇异值稀疏化器,改进了 Lau、Wang 和 Zhou 的 O(n log⁵ n/ε²) 支撑界,并给出随机构造算法。

cs.DS · cs.DM

查看原文摘要

Given an unweighted directed graph, a sparsifier is a nonnegative reweighting of original arcs that preserves every in-degree and out-degree exactly. In this work, we study singular-value sparsifiers, which are generalizations of spectral sparsifiers. Singular-value sparsifiers find a number of applications in theoretical computer science, such as maintaining directed cuts and flows, speeding up directed Laplacian solvers, and sparsifying dense weight matrices in neural networks. Strong singular-value (SV) approximation supports sparse representations of directed random walks with guarantees that remain stable under products, and controls bilinear error in the left and right Schur-complement metrics. We prove that every unweighted directed graph on $n$ vertices admits an $\varepsilon$-SV sparsifier with $O(n\log(2n)/\varepsilon^2)$ arcs, improving the $O(n\log^5 n/\varepsilon^2)$ support bound of Lau, Wang, and Zhou. The sparsifier is a nonnegative reweighting of original arcs and preserves every in-degree and out-degree exactly. We also give a randomized construction with $\tilde{O}(m+n)$ real-arithmetic running time, where $m$ is the input support size, and the output has the same support bound and rational weights of polynomial bit length.