跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+979新增论文
+781其中 AI 相关
+119已有论文修订
+95新增 AI 导读

arXiv 最近完成扫描:2026-11-20 08:48 · 全站最近入库:2026-11-20 19:58各信源进度 →

统计口径与数据新鲜度

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

最近完成检查:2026-11-20 08:48最近发现新增版本:2026-11-20 19:58库内论文最新更新时间:2026-11-20 02:59

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

28,961 已收录论文24,030 AI 相关8,912 有修订112 HF 社区发现

浏览论文库

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

找到 2 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-20 08:46(北京时间)
新论文 · v1arXiv:2611.26273

Deterministic Parameterized Inapproximability of the Shortest Vector and Minimum Distance Problems

Shuichi Hirahara, Bingkai Lin, Yuwei Liu, Kazuki Ogitsuka

原文摘要

The Shortest Vector Problem (SVP) and the Minimum Distance Problem (MDP) are central computational problems on lattices and linear codes, respectively. For every computable real $p\ge1$ and any constant factor, we prove that the parameterized SVP in the $\ell_p$ norm, with the distance threshold as the parameter, is W[1]-hard to approximate within factor $γ$ under deterministic reductions. The same method shows that, for every finite field, the parameterized MDP is W[1]-hard to approximate within any constant factor under deterministic reductions.

cs.CC

版本更新 · v2arXiv:2609.19623

Near-Logarithmic Inapproximability of Parameterized Set Cover

Bingkai Lin, Xin Zheng

原文摘要

In the $γ$-gap $k$-SetCover problem, we are given a family $\mathcal{S}$ over a universe $U$, and the goal is to distinguish between the case where $\mathcal{S}$ contains $k$ sets covering $U$, and the case where at least $γk$ sets in $\mathcal{S}$ are needed to cover $U$. We show that, for every $k^{Ω(k^2)}\leρ\le n^{O(1)}$, it is W[1]-hard to approximate $k$-SetCover within ratio $Ω\big(\frac{\logρ}{k^2\log\logρ}\big)$ on instances with $n$ sets and universe size at most $ρ\log n$. We also show that under the randomized $k$-OV Hypothesis, there is no bounded-error randomized $f(k)n^{o(k)}$-time $o\big(\frac{\log N}{\log\log N}\big)$-approximation algorithm for $k$-SetCover. These results improve on the previous $(\log n)^{1/O(k)}$-inapproximability. For fixed $k$, this matches the polynomial-time $(\lnρ+O(1))$-approximation up to a $\log\logρ$ factor. We further establish a connection between small universes and large approximation gaps. We show that for every $1\leγ\le\min\big\{\frac{\log u}{\log\log N},\frac{\log u}{k^2\log\log u}\big\}$, exact $k$-SetCover with universe size $u^{Θ(1/γ)}$ is equivalent to $γ$-gap $k$-SetCover with universe size $u$ under randomized Turing reductions. This suggests a barrier to proving superconstant-gap W[2]-hardness: such a result would also make exact $k$-SetCover with universe size $n^{o(1)}$ W[2]-hard under randomized FPT Turing reductions. Finally, we analyze the VC dimensions of the set systems produced by our reduction. Write $d$ and $d^*$ for the primal and dual VC dimensions respectively. We show that for $γ=o(\frac{\log N}{\log\log N})$, $γ$-gap $k$-SetCover is W[1]-hard even when $d=O(k^{2}γ\log(kγ))$ and $d^*=O(kγ)$. The bound for $d^*$ matches the $O(d^*\log k)$-approximation algorithm up to a $k\log k$ factor.

cs.CC