跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+479新增论文
+361其中 AI 相关
+63已有论文修订
+93新增 AI 导读

arXiv 最近完成扫描:2026-11-16 01:34 · 全站最近入库:2026-11-16 13:44各信源进度 →

统计口径与数据新鲜度

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

最近完成检查:2026-11-16 01:34最近发现新增版本:2026-11-16 13:44库内论文最新更新时间:2026-11-14 02:59

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

23,827 已收录论文19,941 AI 相关6,921 有修订112 HF 社区发现

浏览论文库

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

找到 1 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-16 01:33(北京时间)
新论文 · 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.