跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+1680新增论文
+1333其中 AI 相关
+187已有论文修订
+59新增 AI 导读

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

统计口径与数据新鲜度

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

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

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

25,786 已收录论文21,491 AI 相关7,725 有修订112 HF 社区发现

浏览论文库

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

找到 2 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-18 04:27(北京时间)
新论文 · v1arXiv:2611.09764

k-Clique 假设已死,且是彻底地死了

The k-Clique hypothesis is dead, for good

Virginia Vassilevska Williams, Or Zamir

AI 速读 基于摘要

作者提出一个对足够大的 k 在 n^{(ω/3−c)k} 时间内求解(并计数加权)k-Clique 的算法,据此声称推翻了长期存在的 k-Clique 猜想。

cs.DS · cs.CC

查看原文摘要

We present an algorithm that solves the $k$-Clique problem for any large enough $k$ and any $n$-vertex graph in $n^{\left(\fracω{3}-c\right)k}$ time, where $ω\geq 2$ is the matrix multiplication exponent and $c>0$ is a positive constant independent of both $ω$ and $k$. This refutes the long-standing $k$-Clique conjecture, regardless of the value of the matrix multiplication constant, even if $ω=2$. In fact, our algorithm solves the more general problem of counting weighted $k$-Cliques.

新论文 · v1arXiv:2611.08351

一种新的有界空间动态模型中的连通性

Connectivity in a New Bounded-Space Dynamic Model

Bardiya Aryanfard, Monika Henzinger, John Kuszmaul, Jakob Nogler, Virginia Vassilevska Williams

AI 速读 基于摘要

论文提出一种有界工作空间的动态算法模型,并研究动态无向 s-t 连通性在该模型下的时间-空间权衡。

cs.DS

查看原文摘要

We introduce a new model for dynamic algorithms in which the algorithm has read-only oracle access to a dynamically changing input and random access to its own bounded workspace. It is a dynamic analogue of the time-space tradeoffs for static inputs studied in complexity theory, where only writable memory counts as space. We study dynamic undirected $s$-$t$ connectivity: after every edge update to an $n$-vertex graph, an algorithm with $S$ words of workspace must report whether $s$ and $t$ are connected. The graph is accessed via adjacency list queries (degree, $j$-th neighbor) or adjacency matrix queries. Our algorithms are randomized; our lower bounds hold for randomized algorithms with $cn$ bits of workspace, $c>0$ a small constant ($cn/\log n$ for the worst-case matrix bound). We prove: (1) With adjacency lists, worst-case time $\tildeΘ(n^2/S^2)$ per insertion is necessary and sufficient for incremental algorithms. (2) With an adjacency matrix, worst-case time $\tildeΩ(n^2/S)$ per insertion is necessary for incremental algorithms, and sufficient for $S\ge\sqrt{n}$. (3) With amortization, incremental algorithms achieve $\tilde O(n/S)$ time per insertion with adjacency lists and $\tilde O(n^2/S)$ with an adjacency matrix, while $\tildeΩ(\sqrt{n/S})$ and $\tildeΩ(n\sqrt{n/S})$, respectively, are necessary. (4) Fully dynamic algorithms need amortized time $\tildeΩ(n/S)$ per update with adjacency lists and $\tildeΩ(n^2/S)$ with an adjacency matrix, even on forests, where both bounds are tight (lists: under bounded degree). Conventional dynamic connectivity admits polylogarithmic update time with $Ω(n)$ words of space. In contrast, our lower bounds show that polynomial update time is necessary whenever $S\le n^{1-\varepsilon}$, even for a single pair of vertices and even for incremental algorithms with amortized guarantees.