计算复杂性

最近提交的作者和标题

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

查看今天的 新的 变化

2025年07月09日， 星期三 (继续， 展示 最后 7 之 2 条目 )

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

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

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

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

标题： Low sets for counting functions

Yaroslav Ivanashev

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

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

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

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

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

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

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

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

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

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

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

标题： 对称转运/反向转运膜系统与膜分离表征 P^(#P) 显示英文标题

标题： Symport/Antiport P Systems with Membrane Separation Characterize P^(#P)

Vivien Ducros, Claudio Zandron

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

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

标题： 基于PCPP的重新配置不可近似性：查询复杂性与可靠性间隙的权衡 显示英文标题

标题： PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs

Venkatesan Guruswami, Xuandi Ren, Kewen Wu

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

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

标题： 量子分布学习和量子密码学的难度 显示英文标题

标题： Hardness of Quantum Distribution Learning and Quantum Cryptography

Taiga Hiroka, Min-Hsiu Hsieh, Tomoyuki Morimae

评论： 59页，1图

主题： 量子物理 (quant-ph) ; 计算复杂性 (cs.CC) ; 密码学与安全 (cs.CR)