计算复杂性

最近提交的作者和标题

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

查看今天的 新的 变化

2025年08月07日， 星期四 (继续， 展示 最后 3 之 2 条目 )

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

标题： 量子电路复杂度与拓扑序的无监督机器学习 显示英文标题

标题： Quantum circuit complexity and unsupervised machine learning of topological order

Yanming Che, Clemens Gneiting, Xiaoguang Wang, Franco Nori

评论： 17页，附录；4张图表。代码在合理请求后可获得，并将在出版时开源。欢迎提出意见

主题： 量子物理 (quant-ph) ; 无序系统与神经网络 (cond-mat.dis-nn) ; 计算复杂性 (cs.CC) ; 信息论 (cs.IT) ; 机器学习 (cs.LG)

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

标题： 一种用于精确3x3矩阵乘法的60加法，秩23方案 显示英文标题

标题： A 60-Addition, Rank-23 Scheme for Exact 3x3 Matrix Multiplication

Joshua Stapleton

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

2025年08月06日， 星期三 (展示 1 之 1 条目 )

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

标题： 量子电路中逻辑深度的热力学特征 显示英文标题

标题： Thermodynamic Signature of Logical Depth in Quantum Circuits

Issam Ibnouhsein

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

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

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

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

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

标题： Forrelation is Extremally Hard

Uma Girish, Rocco Servedio

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

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

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

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

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

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

标题： Proof complexity of Mal'tsev CSP

Azza Gaysin

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

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

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

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

标题： The Complexity of Logarithmic Space Bounded Counting Classes

T. C. Vijayaraghavan

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

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

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

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

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

标题： Amplitude amplification and estimation require inverses

Ewin Tang, John Wright

评论： 20页

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