计算复杂性

最近提交的作者和标题

• 2025年07月11日， 星期五
• 2025年07月10日， 星期四
• 2025年07月09日， 星期三
• 2025年07月08日， 星期二
• 2025年07月04日， 星期五

查看今天的 新的 变化

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

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

标题： 量子哈希的高效算法 显示英文标题

标题： Efficient Algorithms for Quantum Hashing

Ilnar Zinnatullin, Kamil Khadiev

评论： 被UCNC2025接受

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

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

标题： 量子模型的可训练性超越已知的经典可模拟性 显示英文标题

标题： Trainability of Quantum Models Beyond Known Classical Simulability

Sabri Meyer, Francesco Scala, Francesco Tacchino, Aurelien Lucchi

评论： 11页，7图，52页的补充材料

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

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

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

标题： 硬度与伪熵之间的广义和统一等价性 显示英文标题

标题： Generalized and Unified Equivalences between Hardness and Pseudoentropy

Lunjia Hu, Salil Vadhan

主题： 计算复杂性 (cs.CC) ; 机器学习 (cs.LG)

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

标题： 说服的复杂性结果 显示英文标题

标题： Complexity Results of Persuasion

Alban Grastien

主题： 计算复杂性 (cs.CC) ; 人工智能 (cs.AI)

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

标题： 关于在群上定义的图的问题的复杂性 显示英文标题

标题： On the Complexity of Problems on Graphs Defined on Groups

Bireswar Das, Dipan Dey, Jinia Ghosh

评论： 22页，这是对应论文的完整版本，已被第25届国际计算理论基础研讨会（FCT 2025）接受

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

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

标题： 一种对区块链三难困境的形式反驳 显示英文标题

标题： A Formal Refutation of the Blockchain Trilemma

Craig Wright

评论： 12页

主题： 计算复杂性 (cs.CC) ; 密码学与安全 (cs.CR) ; 分布式、并行与集群计算 (cs.DC) ; 数据结构与算法 (cs.DS)

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

标题： 参数化无休止时间路径 显示英文标题

标题： Parameterized Restless Temporal Path

Justine Cauvi (DI-ENS, ARGO, ENS de Lyon), Laurent Viennot (DI-ENS, ARGO)

期刊参考： 第25届国际计算理论基础研讨会，FCT 2025，2025年9月，弗罗茨瓦夫，波兰，法国

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

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

标题： Kakeya 集的线性扩展缺失每个 ee-随机点 显示英文标题

标题： Lineal Extensions of Kakeya Sets Missing Every ee-Random Point

Neil Lutz, Spencer Park Martin, Rain White

主题： 计算复杂性 (cs.CC) ; 概率 (math.PR)

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

标题： 几乎最优深度的酉设计 显示英文标题

标题： Unitary designs in nearly optimal depth

Laura Cui, Thomas Schuster, Fernando Brandao, Hsin-Yuan Huang

评论： 8+31页，3+1图

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

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

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

标题： 计数函数的低集 显示英文标题

标题： Low sets for counting functions

Yaroslav Ivanashev

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

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

标题： 量子计算中的相关测量：对复杂性景观的影响 显示英文标题

标题： Quantum Computation with Correlated Measurements: Implications for the Complexity Landscape

David Miloschewsky, Supartha Podder

评论： 19页，1图

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

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

标题： 深度-2正则表达式难以相交吗？ 显示英文标题

标题： Are Depth-2 Regular Expressions Hard to Intersect?

Rocco Ascone, Giulia Bernardini, Alessio Conte, Veronica Guerrini, Giulia Punzi

评论： 24页，10图

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

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

标题： 一个布尔切片上的近似最优多项式距离引理 显示英文标题

标题： A Near-Optimal Polynomial Distance Lemma Over Boolean Slices

Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan

评论： 42页，被接受至ICALP 2025

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

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

标题： 通过边查询学习匹配和半图的复杂度 显示英文标题

标题： Complexity of learning matchings and half graphs via edge queries

Nikhil S. Mande, Swagato Sanyal, Viktor Zamaraev

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

[21] arXiv:2507.05044 (交叉列表自 cs.LO) [中文pdf, pdf, html, 其他]

标题： 可重命名性测试到子句集类 显示英文标题

标题： Testing for Renamability to Classes of Clause Sets

Albert Brandl, Christian G. Fermüller, Gernot Salzer

期刊参考： 在《第一阶定理证明国际研讨会论文集（FTP'97）》中，Maria Paola Bonacina和Ulrich Fuhrbach主编。RISC-Linz报告系列第97-50号，第34--39页。奥地利林茨约翰内斯·开普勒大学，1997年。

主题： 计算机科学中的逻辑 (cs.LO) ; 计算复杂性 (cs.CC)

[22] arXiv:2507.03919 (交叉列表自 cs.DB) [中文pdf, pdf, html, 其他]

标题： PFCS：用于确定性数据关系发现的素因数缓存系统 显示英文标题

标题： PFCS: Prime Factorization Cache System for Deterministic Data Relationship Discovery

Duy Le

评论： 6页，3图，3算法

主题： 数据库 (cs.DB) ; 计算复杂性 (cs.CC)

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

标题： 关于列车路由的可近似性和最小最大不相交路径问题 显示英文标题

标题： On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem

Umang Bhaskar, Katharina Eickhoff, Lennart Kauther, Jannik Matuschke, Britta Peis, Laura Vargas Koch

评论： 已被欧洲算法研讨会（ESA）2025接受

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

2025年07月04日， 星期五 (展示 1 之 1 条目 )

[24] arXiv:2507.02839 (交叉列表自 math.OC) [中文pdf, pdf, 其他]

标题： Stiefel优化是NP难的 显示英文标题

标题： Stiefel optimization is NP-hard

Zehua Lai, Lek-Heng Lim, Tianyun Tang

评论： 9页

主题： 优化与控制 (math.OC) ; 计算复杂性 (cs.CC)