计算复杂性

最近提交的作者和标题

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

查看今天的 新的 变化

2025年08月04日， 星期一 (继续， 展示 最后 3 之 1 条目 )

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

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

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

标题： The Complexity of Logarithmic Space Bounded Counting Classes

T. C. Vijayaraghavan

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

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

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

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