计算复杂性

最近提交的作者和标题

• 2025年08月05日， 星期二
• 2025年08月04日， 星期一
• 2025年08月01日， 星期五
• 2025年07月31日， 星期四
• 2025年07月30日， 星期三

查看今天的 新的 变化

2025年08月05日， 星期二 (展示 3 之 3 条目 )

[1] arXiv:2508.01649 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 迈向EXPTIME单向函数：布隆过滤器、简洁图、团与自屏蔽 显示英文标题

标题： Towards EXPTIME One Way Functions: Bloom Filters, Succinct Graphs, Cliques, & Self Masking

Shlomi Dolev

评论： 先前版本见 https://eccc.weizmann.ac.il/report/2025/043/ 提交到arxiv作为提交到《Theory of Computing》的要求

主题： 计算复杂性 (cs.CC) ; 密码学与安全 (cs.CR) ; 数据结构与算法 (cs.DS)

[2] arXiv:2508.02514 (交叉列表自 quant-ph) [中文pdf, pdf, html, 其他]

标题： Forrelation 是极端困难的 显示英文标题

标题： Forrelation is Extremally Hard

Uma Girish, Rocco Servedio

评论： 被接受为TQC 2025的演讲

主题： 量子物理 (quant-ph) ; 计算复杂性 (cs.CC)

[3] arXiv:2508.00983 (交叉列表自 quant-ph) [中文pdf, pdf, html, 其他]

标题： 高斯玻色子采样中的隐藏猜想证明 显示英文标题

标题： Proof of Hiding Conjecture in Gaussian Boson Sampling

Laura Shou, Sarah H. Miller, Victor Galitski

评论： 21页，4图

主题： 量子物理 (quant-ph) ; 计算复杂性 (cs.CC) ; 数学物理 (math-ph)

2025年08月04日， 星期一 (展示 3 之 3 条目 )

[4] arXiv:2508.00276 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 渐近最优的E$k$-SAT重配置不可近似性 显示英文标题

标题： Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration

Shuichi Hirahara, Naoto Ohsaka

评论： 将出现在第66届IEEE计算机科学基础研讨会（FOCS 2025）的论文集上

主题： 计算复杂性 (cs.CC) ; 离散数学 (cs.DM) ; 数据结构与算法 (cs.DS)

[5] arXiv:2508.00396 (交叉列表自 math.LO) [中文pdf, pdf, 其他]

标题： Mal'tsev CSP的证明复杂性 显示英文标题

标题： Proof complexity of Mal'tsev CSP

Azza Gaysin

主题： 逻辑 (math.LO) ; 计算复杂性 (cs.CC)

[6] arXiv:2508.00055 (交叉列表自 quant-ph) [中文pdf, pdf, 其他]

标题： 受控的酉操作是否有帮助？ 显示英文标题

标题： Are controlled unitaries helpful?

Ewin Tang, John Wright

评论： 18页

主题： 量子物理 (quant-ph) ; 计算复杂性 (cs.CC) ; 数据结构与算法 (cs.DS)

2025年08月01日， 星期五 (展示 4 之 4 条目 )

[7] arXiv:2507.23563 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 对数空间有界计数类的复杂性 显示英文标题

标题： The Complexity of Logarithmic Space Bounded Counting Classes

T. C. Vijayaraghavan

主题： 计算复杂性 (cs.CC)

[8] arXiv:2507.23345 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 关于Ward-Szabo定理的更好复杂度上界 显示英文标题

标题： On a better complexity upper bound of Ward-Szabo theorem

Takashi Ishizuka

主题： 计算复杂性 (cs.CC) ; 离散数学 (cs.DM)

[9] arXiv:2507.23008 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 指数下界对几乎二次深度的ResLin证明的大小 显示英文标题

标题： Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth

Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay

评论： 35页

主题： 计算复杂性 (cs.CC)

[10] arXiv:2507.23787 (交叉列表自 quant-ph) [中文pdf, pdf, 其他]

标题： 振幅放大和估计需要逆运算 显示英文标题

标题： Amplitude amplification and estimation require inverses

Ewin Tang, John Wright

评论： 20页

主题： 量子物理 (quant-ph) ; 计算复杂性 (cs.CC) ; 数据结构与算法 (cs.DS)

2025年07月31日， 星期四 (展示 3 之 3 条目 )

[11] arXiv:2507.22444 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 近似LCS游戏的量子值是RE难的 显示英文标题

标题： Approximating the quantum value of an LCS game is RE-hard

Aviv Taller, Thomas Vidick

主题： 计算复杂性 (cs.CC) ; 数学物理 (math-ph) ; 量子物理 (quant-ph)

[12] arXiv:2507.22265 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： 通过半随机CSP反驳的单元探测下界：简化和奇局部性情况 显示英文标题

标题： Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case

Venkatesan Guruswami, Xin Lyu, Weiqiang Yuan

评论： 欢迎评论

主题： 计算复杂性 (cs.CC) ; 密码学与安全 (cs.CR) ; 数据结构与算法 (cs.DS)

[13] arXiv:2507.22819 (交叉列表自 cs.GT) [中文pdf, pdf, 其他]

标题： 降低计算纳什均衡值的复杂度 显示英文标题

标题： Reducing the complexity of computing the values of a Nash equilibrium

Debtoru Chatterjee, Girish Tiwari, Niladri Chatterjee

评论： 第36届石溪国际博弈论会议于2025年7月14日至17日在美国纽约石溪举行

主题： 计算机科学与博弈论 (cs.GT) ; 计算复杂性 (cs.CC)

2025年07月30日， 星期三 (展示 5 之 5 条目 )

[14] arXiv:2507.21550 (交叉列表自 cs.CC) [中文pdf, pdf, html, 其他]

标题： TFNP中的层次结构：构建块和坍缩 显示英文标题

标题： Hierarchies within TFNP: building blocks and collapses

Surendra Ghentiyala, Zeyong Li

主题： 计算复杂性 (cs.CC)

[15] arXiv:2507.22001 (交叉列表自 quant-ph) [中文pdf, pdf, html, 其他]

标题： 保罗测量对于单量子比特层析术是近似最优的 显示英文标题

标题： Pauli Measurements Are Near-Optimal for Single-Qubit Tomography

Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu, Nengkun Yu

评论： 22页

主题： 量子物理 (quant-ph) ; 计算复杂性 (cs.CC)

[16] arXiv:2507.21445 (交叉列表自 cs.DS) [中文pdf, pdf, html, 其他]

标题： Steiner定向的结构参数 显示英文标题

标题： Structural Parameters for Steiner Orientation

Tesshu Hanaka, Michael Lampis, Nikolaos Melissinos, Edouard Nemery, Hirotaka Ono, Manolis Vasilakis

主题： 数据结构与算法 (cs.DS) ; 计算复杂性 (cs.CC)

[17] arXiv:2507.21342 (交叉列表自 math.DS) [中文pdf, pdf, html, 其他]

标题： 同胚移位的块粘合类的不可判定性 显示英文标题

标题： Undecidability of the block gluing classes of homshifts

Nishant Chandgotia, Silvère Gangloff, Benjamin Hellouin de Menibus, Piotr Oprocha

主题： 动力系统 (math.DS) ; 计算复杂性 (cs.CC) ; 离散数学 (cs.DM)

[18] arXiv:2507.21258 (交叉列表自 cs.CR) [中文pdf, pdf, html, 其他]

标题： 认知战争中的验证成本不对称性：一个复杂性理论框架 显示英文标题

标题： Verification Cost Asymmetry in Cognitive Warfare: A Complexity-Theoretic Framework

Joshua Luberisse

主题： 密码学与安全 (cs.CR) ; 计算复杂性 (cs.CC) ; 计算机与社会 (cs.CY) ; 计算机科学与博弈论 (cs.GT)