跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

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

arXiv 最近完成扫描：2026-11-15 05:41 · 全站最近入库：2026-11-14 15:09各信源进度 →

统计口径与数据新鲜度

统计 2026-11-14 05:47 — 2026-11-15 05:47（北京时间） · 点击数字查看对应简报；AI 相关包含在新增论文内。

最近完成检查：2026-11-15 05:41最近发现新增版本：2026-11-14 15:09库内论文最新更新时间：2026-11-13 02:59

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

23,348 已收录论文19,580 AI 相关6,729 有修订112 HF 社区发现

浏览论文库

研究日报 / 周报 →按信源浏览 →

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

找到 4 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-15 05:40（北京时间）
版本更新 · v3arXiv:2609.12021

Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles

Boxuan Chen, Bin Cui, Hanqing Li, Xupeng Miao, Haoze Wang

原文摘要

For an $n\times n$ matrix over a field of characteristic two, let $Φ$ denote the sum of the odd permutation monomials. We give a deterministic algorithm that evaluates $Φ$ and all its first partial derivatives using $O(n^ω)$ field operations, where $2<ω\le3$ is any fixed admissible exponent for square matrix multiplication. As an application, we obtain faster randomized algorithms for shortest even directed cycles. Given an $n$-vertex directed graph whose shortest even cycle has length $\ell$, with high probability we compute $\ell$ and the union of the arcs of all shortest even cycles in $\widetilde O(n^ω\ell)$ time, and find one such cycle in $\widetilde O(n^ω\ell+n^2\ell^2)$ time. The resulting general bounds are $\widetilde O(n^{ω+1})$ and $\widetilde O(n^4)$, respectively, improving on the $\widetilde O(n^{ω+3})$ and $\widetilde O(n^{ω+4})$ bounds of Björklund, Husfeldt, and Kaski [BHK24].

cs.DS

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2610.07468

Partially Dynamic Single-Source Shortest Paths in Almost-Linear Time

Bin Cui, Hanqing Li, Xupeng Miao, Haoze Wang

原文摘要

We study $(1+ε)$-approximate single-source distances in directed graphs with positive integer edge weights in $[1,W]$. For every $0<ε\le1$, we give deterministic data structures for either edge insertions or edge deletions with total update time $m^{1+o(1)}ε^{-1}\log W$, where $m\ge n$ bounds the total number of initially present and inserted edges. Both structures explicitly maintain approximate distance estimates, answer distance queries in constant time, and identify unreachable vertices exactly. The incremental structure additionally reports a simple $(1+ε)$-approximate source path $P$ in $O(|P|)$ time. Our decremental structure gives the first almost-linear-time algorithm. It improves the previous best randomized expected bound of $\widetilde O(\min\{n^2,mn^{2/3}\})$ against an oblivious adversary [BPW20]. Our incremental bound improves the $ε^{-B}$ dependence of the $B$-level recursive algorithm of [Liu26] to an explicit $ε^{-1}$ factor while retaining almost-linear dependence on $m$. Our algorithms use modified interior point methods. For edge deletions, we extend the single-pair distance framework of [vBCKLMPSS24] to all targets simultaneously. A shared potential and one dynamic minimum-ratio cut instance support global updates to the distance labels. Our main insight is that constant relative cut balance certifies approximate distances at every target. For edge insertions, we develop an analogous circulation-based formulation implemented through the dynamic minimum-ratio cycle structure of [CKLMP24]. We also give a black-box reduction from distance estimates to path reporting in incremental graphs, with $m^{1+o(1)}ε^{-1}\log W$ additional maintenance time. This reduction may be of independent interest.

cs.DS

查看论文
arXiv ↗PDF ↗
版本更新 · v5arXiv:2605.06152

Grokking or Glitching? How Low-Precision Drives Slingshot Loss Spikes

Hanqing Liu, Jianjun Cao, Yuanze Li, Zijian Zhou

原文摘要

Deep neural networks exhibit periodic loss spikes during unregularized long-term training, a phenomenon known as the "Slingshot Mechanism." Existing work usually attributes this to intrinsic optimization dynamics, but its triggering mechanism remains unclear. This paper proves that this phenomenon is a result of floating-point arithmetic precision limits. As training enters a high-confidence stage, the difference between the correct-class logit and the other logits may exceed the absorption-error threshold. Then during backpropagation, the gradient of the correct class is rounded exactly to zero, while the gradients of the incorrect classes remain nonzero. This breaks the zero-sum constraint of gradients across classes and introduces a systematic drift in the parameter update of the classifier layer. We prove that this drift forms a positive feedback loop with the feature, causing the global classifier mean and the global feature mean to grow exponentially. We call this mechanism Numerical Feature Inflation (NFI). This mechanism explains the rapid norm growth before a Slingshot spike, the subsequent reappearance of gradients, and the resulting loss spike. We further show that NFI is not equivalent to an observed loss spike: in more practical tasks, partial absorption may not produce visible spikes, but it can still break the zero-sum constraint and drive rapid growth of parameter norms. Our results reinterpret Slingshot as a numerical dynamic of finite-precision training, and provide a testable explanation for abnormal parameter growth and logit divergence in late-stage training.

cs.LG · cs.CL · math.OC · stat.ML

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2610.07465

Extending Tardos's Theorem to Separable Convex Quadratic Programming

Bin Cui, Hanqing Li, Xupeng Miao

原文摘要

For an integer equality matrix $A\in\mathbb{Z}^{r\times m}$ of binary encoding length $\langle A\rangle$, Tardos's theorem solves linear programs using $\operatorname{poly}(r,m,\langle A\rangle)$ rational arithmetic operations and comparisons, independently of the right-hand side and objective coefficients. We extend this guarantee to continuous separable convex quadratic programming over $Ax=b$, $x\ge0$: the operation count is independent of the right-hand side, linear costs, and all nonnegative quadratic weights. The algorithm returns an exact optimal primal-dual pair or a certificate of infeasibility or unboundedness. All intermediate rational numbers have encoding lengths polynomial in the total input length. As an application, we obtain a strongly polynomial algorithm for continuous multicommodity flow with shared capacities and quadratic costs of aggregate arc flow, independently of demands, capacities, and cost coefficients. Objective compression and continuous-integer proximity yield a local solver returning a point close to an optimum. We relax nonnegativity on coordinates with zero optimal dual slack, minimize the largest remaining coordinate, and optimize over the relaxed coordinates. A descent LP over the recession cone provides a complementary bound. Circuit decomposition combines these bounds into a scale ensuring that each local call reveals a new coordinate. At most $m$ calls, followed by two LPs, recover an exact optimum and its dual certificate.

cs.DS

查看论文
arXiv ↗PDF ↗