计算复杂性

2025年07月 的作者和标题

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

标题： 不确定性下的敏感性和查询复杂性 显示英文标题

标题： Sensitivity and Query Complexity under Uncertainty

Deepu Benson, Balagopal Komarath, Nikhil Mande, Sai Soumya Nalli, Jayalal Sarma, Karteek Sreenivasaiah

评论： 43页，技术报告的合并和改进版本 - arxiv:2501.00831 和 arxiv:2412.06395

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

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

标题： 哈密顿性参数化为模仿宽度是（确实）参数化NP难的 显示英文标题

标题： Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard

Benjamin Bergougnoux, Lars Jaffke

评论： 11页，6图

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

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

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

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

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

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

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

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

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

标题： Low sets for counting functions

Yaroslav Ivanashev

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

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

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

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

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

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

标题： Complexity Results of Persuasion

Alban Grastien

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

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

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

标题： Generalized and Unified Equivalences between Hardness and Pseudoentropy

Lunjia Hu, Salil Vadhan

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

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

标题： 某些图类上的最小选择子集 显示英文标题

标题： Minimum Selective Subset on Some Graph Classes

Bubai Manna

评论： 这项工作已被接受于CCCG 2025

主题： 计算几何 (cs.CG) ; 计算复杂性 (cs.CC)

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

标题： 无辅助量子比特的近似多控制单量子比特门的对数深度分解 显示英文标题

标题： Logarithmic Depth Decomposition of Approximate Multi-Controlled Single-Qubit Gates Without Ancilla Qubits

Jefferson D. S. Silva, Adenilton J. da Silva

评论： 6页，10图

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

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

标题： 关于监测边测地集问题的（不）可近似性 显示英文标题

标题： On the (In)Approximability of the Monitoring Edge Geodetic Set Problem

Davide Bilò, Giodano Colli, Luca Forlizzi, Stefano Leucci

评论： arXiv管理员注：与arXiv:2405.13875文本重叠

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

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

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

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

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

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