计算复杂性

最近提交的作者和标题

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

查看今天的 新的 变化

2025年08月01日， 星期五 (继续， 展示 最后 4 之 1 条目 )

[11] 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 条目 )

[12] 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)

[13] 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)

[14] 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)