跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

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

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

统计口径与数据新鲜度

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

最近完成检查:2026-11-18 04:28最近发现新增版本:2026-11-18 19:45库内论文最新更新时间:2026-11-18 08:00

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

26,870 已收录论文22,374 AI 相关8,156 有修订112 HF 社区发现

浏览论文库

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

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

Sensitivity and Locality Lower Bounds via Low-Soundness Label Cover

Noah Fleming, Max Hopkins, Yuichi Yoshida

原文摘要

We study the sensitivity of approximation algorithms, which measures how much their output distributions change under a single input edit. We show that, for Set Cover, Dominating Set, Min-Rep, and minimum unweighted directed 3-spanner, even a $\log^βn$ approximation requires sensitivity $n^{Ω(1)}$, for some absolute constant $β>0$ and all sufficiently large $n$. The lower bounds hold even for randomized algorithms with unrestricted computation. Here $n$ is the universe size for Set Cover and the number of vertices for the graph problems. On bounded-degree graphs, our sensitivity lower bounds imply logarithmic locality lower bounds in the randomized LOCAL model and its non-signaling generalization. For Dominating Set, fix $\varepsilon\in(0,1)$ and a sufficiently large constant maximum-degree bound $Δ$. A $(1+\varepsilon)\lnΔ$ approximation can be achieved with sensitivity and LOCAL round complexity independent of $n$. We show that improving the ratio to $(1-\varepsilon)\lnΔ$ requires sensitivity $n^{Ω_{\varepsilon,Δ}(1)}$, and hence locality $Ω_{\varepsilon,Δ}(\log n)$. For minimum unweighted directed 3-spanner, every constant approximation factor requires logarithmic locality, even on DAGs of constant maximum total degree. The key ingredient is a polynomial sensitivity lower bound for a variant of low-soundness Label Cover. Fleming and Yoshida established such a lower bound when the required fraction of satisfied constraints on satisfiable instances is close to one. We extend this to inverse-polylogarithmic fractions, enabling the reductions to the problems above. We adapt the Impagliazzo--Kabanets--Wigderson direct-product construction and Dinur--Harsha iterated composition to control the propagation of input edits, and design recovery procedures that are stable under changes to both the supplied labeling and the source instance.

cs.DS

新论文 · v1arXiv:2611.05308

随机预言机模型中的 TFNP

TFNP in the Random Oracle Model

Noah Fleming, Mika Göös, Ziyi Guan, Oliver Korten, Daniel Mitropolsky, Toniann Pitassi, Artur Riazanov, Dmitry Sokolov 等 10 位作者

AI 速读 基于摘要

作者在随机预言机模型(Romantica)中刻画了主要 TFNP 类的平均情形困难性,并给出 PPAD 困难、EoPL 与 UEoPL 可解性分离等结果。

cs.CC

查看原文摘要

We determine which major $\TFNP$ classes are hard in the random oracle model (ROM). Prior work establishes average-case hardness of highly structured subclasses of $\TFNP$ from strong cryptographic assumptions such as LWE and indistinguishability obfuscation. It is not known whether weaker assumptions such as one-way functions imply hardness of any of the standard $\TFNP$ subclasses, even in the worst case. The ROM, where all parties have query access to a random function, lies, morally, between these two regimes: a random function is one-way, but public-key cryptography cannot be built from it in a black-box way. We refer to this setting as \emph{Romantica}. Our first result settles a long-standing open problem: $\PPAD$, the class of total search problems reducible to finding a Nash equilibrium, is hard on average in Romantica. Combined with the known hardness of PLS (local search), this gives average-case hardness of $\EoPL = \PPAD \cap \PLS$. In contrast, we show that $\UEoPL$ can be solved in Romantica with polynomially many oracle queries by a computationally unbounded solver, a sharp distinction between $\EoPL$ and $\UEoPL$. This resolves the black-box hardness landscape of all major $\TFNP$ classes in Romantica. Finally, we initiate the study of separations between $\TFNP$ subclasses in Romantica: $\PWPP$ and $\PPA$ do not reduce to $\PLS$ under \emph{public-coin} reductions.