计算复杂性

2025年05月 的作者和标题

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

标题： UAP逆向工程的计算复杂性：自动机识别和数据复杂性的形式分析 显示英文标题

标题： Computational Complexity of UAP Reverse Engineering: A Formal Analysis of Automaton Identification and Data Complexity

Karim Daghbouche

评论： 具有永久非独家分发权以供arxiv.org使用

期刊参考： J. Acad. (N.Y.) 2025年, 第14卷, 1:3-15

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

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

标题： 一般图中最小顶点覆盖的一次通信复杂度 显示英文标题

标题： One-way Communication Complexity of Minimum Vertex Cover in General Graphs

Mahsa Derakhshan, Andisheh Ghasemi, Rajmohan Rajaraman

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

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

标题： 在线卷积的空间复杂度 显示英文标题

标题： On the Space Complexity of Online Convolution

Joel Daniel Andersson, Amir Yehudayoff

评论： 加强了模型以支持持续操作

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

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

标题： 植入正交向量问题 显示英文标题

标题： The Planted Orthogonal Vectors Problem

David Kühnemann, Adam Polak, Alon Rosen

主题： 计算复杂性 (cs.CC) ; 密码学与安全 (cs.CR) ; 数据结构与算法 (cs.DS)

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

标题： 带重新配置问题及其对支配集重新配置的影响 显示英文标题

标题： The tape reconfiguration problem and its consequences for dominating set reconfiguration

Nicolas Bousquet, Quentin Deschamps, Arnaud Mary, Amer E. Mouawad, Théo Pierron

主题： 计算复杂性 (cs.CC) ; 离散数学 (cs.DM) ; 数据结构与算法 (cs.DS) ; 组合数学 (math.CO)

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

标题： 更有效的网格范数筛选及其在多党通信复杂性中的应用 显示英文标题

标题： More efficient sifting for grid norms, and applications to multiparty communication complexity

Zander Kelley, Xin Lyu

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

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

标题： 关于植 clique 的最优区分器 显示英文标题

标题： On optimal distinguishers for Planted Clique

Ansh Nagda, Prasad Raghavendra

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

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

标题： 字符串排列的PLS完全性 显示英文标题

标题： PLS-completeness of string permutations

Dominik Scheder, Johannes Tantow

评论： 15页，4图；已被ESA 2025接受

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

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

标题： 对林的“关于$\text{NP}$与$\text{coNP}$及弗雷格系统”的批判 显示英文标题

标题： A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems"

Nicholas DeJesse, Spencer Lyudovyk, Dhruv Pai, Michael Reidy

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

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

标题： NGAC模型中的安全分析 显示英文标题

标题： Safety Analysis in the NGAC Model

Brian Tan, Ewan S. D. Davies, Indrakshi Ray, Mahmoud A. Abdelgawad

评论： 8页，将发表于SACMAT 2025

主题： 计算复杂性 (cs.CC) ; 密码学与安全 (cs.CR) ; 计算机科学与博弈论 (cs.GT)

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

标题： Battlesheep 是 PSPACE 完备的 显示英文标题

标题： Battle Sheep is PSPACE-complete

Kyle Burke, Hirotaka Ono

评论： 11页，11幅图

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

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

标题： 在任意图中寻找随机放置的团 显示英文标题

标题： On Finding Randomly Planted Cliques in Arbitrary Graphs

Francesco Agrimonti, Marco Bressan, Tommaso d'Orsi

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

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

标题： 聚类顶点删除问题在三次图上 显示英文标题

标题： Cluster Vertex Deletion Problems on Cubic Graphs

Irena Rusu

评论： 21页，6图

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

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

标题： 短而有用的量子证明用于子对数空间验证者 显示英文标题

标题： Short and useful quantum proofs for sublogarithmic-space verifiers

A. C. Cem Say

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

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

标题： BusOut 是 NP 完全的 显示英文标题

标题： BusOut is NP-complete

Takehiro Ishibashi, Ryo Yoshinaka, Ayumi Shinohara

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

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

标题： 决策问题在奇数大小字母表中的相变 显示英文标题

标题： Phase Transitions in Decision Problems Over Odd-Sized Alphabets

Andrew Jackson

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

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

标题： 有限域上的规范乘积分解的新结果 显示英文标题

标题： New results in canonical polyadic decomposition over finite fields

Jason Yang

评论： 30页；内容与arXiv:2502.12390重叠；修正了第3.1节第10页，引理2之后的拼写错误

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

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

标题： 命题消解的细粒度复杂性视角——算法和下界 显示英文标题

标题： A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds

Victor Lagerkvist, Mohamed Maizia, Johannes Schmidt

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

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

标题： 代数伪随机性在$VNC^0$ 显示英文标题

标题： Algebraic Pseudorandomness in $VNC^0$

Robert Andrews

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

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

标题： 图上灭火问题的复杂性 显示英文标题

标题： Complexity of Firefighting on Graphs

Julius Althoetmar, Jamico Schade, Torben Schürenberg

评论： 包含对另一相关来源的引用和讨论

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

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

标题： 一个近似最优的二次Goldreich-Levin算法 显示英文标题

标题： A near-optimal Quadratic Goldreich-Levin algorithm

Jop Briët, Davi Castro-Silva

评论： 37页，1张图

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

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

标题： 具有不平衡合取的决策DNNFs不能有效地表示宽度有界的CNFs。 显示英文标题

标题： Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width

Igor Razgon

评论： 引言和结论部分扩展。新增图6。修正了排版错误。

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

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

标题： ReLU神经网络中计数线性区域的计算复杂性 显示英文标题

标题： The Computational Complexity of Counting Linear Regions in ReLU Neural Networks

Moritz Stargalla, Christoph Hertrich, Daniel Reichman

评论： 26页，6张图，论文被NeurIPS 2025接收

主题： 计算复杂性 (cs.CC) ; 离散数学 (cs.DM) ; 机器学习 (cs.LG) ; 神经与进化计算 (cs.NE) ; 组合数学 (math.CO)

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

标题： 正则性在（超）团检测中的作用及其对优化布尔CSP的影响 显示英文标题

标题： The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs

Nick Fischer, Marvin Künnemann, Mirza Redžić, Julian Stieß

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

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

标题： 准多项式低次数猜想是错误的 显示英文标题

标题： The Quasi-Polynomial Low-Degree Conjecture is False

Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain, Pravesh K. Kothari

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

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

标题： 计算线性顶点arboricity的参数化复杂性 显示英文标题

标题： The Parameterized Complexity of Computing the Linear Vertex Arboricity

Alexander Erhardt, Alexander Wolff

评论： 15页，9幅图

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

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

标题： 矩阵乘法在MPC模型中 显示英文标题

标题： Matrix Multiplication in the MPC Model

Lakshya Joshi, Arya Deshmukh, Atharv Chhabra, Chetan Gupta

主题： 计算复杂性 (cs.CC) ; 分布式、并行与集群计算 (cs.DC)

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

标题： 计算小诱导子图：蝎子是简单的但不平凡 显示英文标题

标题： Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial

Radu Curticapean, Simon Döring, Daniel Neuen

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

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

标题： 单调有界深度的同态多项式复杂性 显示英文标题

标题： Monotone Bounded-Depth Complexity of Homomorphism Polynomials

C. S. Bhargav, Shiteng Chen, Radu Curticapean, Prateek Dwivedi

评论： 22页，1幅图

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

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

标题： 快速压缩域N点离散傅里叶变换：“无旋转因子”快速傅里叶变换算法 显示英文标题

标题： Fast Compressed-Domain N-Point Discrete Fourier Transform: The "Twiddless" FFT Algorithm

Saulo Queiroz

主题： 计算复杂性 (cs.CC) ; 数据结构与算法 (cs.DS) ; 信号处理 (eess.SP)

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

标题： 最小 envy 房屋分配图的复杂性 显示英文标题

标题： The Complexity of Minimum-Envy House Allocation Over Graphs

Palash Dey, Anubhav Dhar, Ashlesha Hota, Sudeshna Kolay

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

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

标题： 在估计量子$\ell_α$距离 显示英文标题

标题： On estimating the quantum $\ell_α$ distance

Yupan Liu, Qisheng Wang

评论： 34页，1张表格，1个算法。v2：小幅修改；定理4.5和A.1的证明中的参数已更正。arXiv管理员注释：与arXiv:2410.13559文本重叠

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

[33] arXiv:2505.00477 (交叉列表自 math.GR) [中文pdf, pdf, html, 其他]

标题： 自由群中的轨道阻塞词 显示英文标题

标题： Orbit-blocking words in free groups

Lucy Koch-Hyde, Siobhan O'Connor, Eamonn Olive, Vladimir Shpilrain

评论： 11页

主题： 群论 (math.GR) ; 计算复杂性 (cs.CC)

[34] arXiv:2505.02384 (交叉列表自 cs.IT) [中文pdf, pdf, html, 其他]

标题： 关于定义在完全二分图上的高斯图模型的等价性 显示英文标题

标题： On the Equivalence of Gaussian Graphical Models Defined on Complete Bipartite Graphs

Mehdi Molkaraie

评论： IEEE信息理论国际研讨会（ISIT），美国安阿伯市，2025年6月

主题： 信息论 (cs.IT) ; 计算复杂性 (cs.CC) ; 计算 (stat.CO)

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

标题： 证明复杂性和可行插值 显示英文标题

标题： Proof Complexity and Feasible Interpolation

Amirhossein Akbar Tabatabai

评论： 这是《Craig内插理论与应用》一书中的一章，该书由Balder ten Cate、Jean Christoph Jung、Patrick Koopmann、Christoph Wernhard和Frank Wolter编辑。

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

[36] arXiv:2505.04604 (交叉列表自 cs.LG) [中文pdf, pdf, html, 其他]

标题： 特征选择和集测试在统计上等价 显示英文标题

标题： Feature Selection and Junta Testing are Statistically Equivalent

Lorenzo Beretta, Nathaniel Harms, Caleb Koch

评论： 32页

主题： 机器学习 (cs.LG) ; 计算复杂性 (cs.CC) ; 数据结构与算法 (cs.DS) ; 机器学习 (stat.ML)

[37] arXiv:2505.04646 (交叉列表自 cs.AI) [中文pdf, pdf, html, 其他]

标题： 计算不可约性作为能动性的基础：连接复杂系统中不可判定性与自主行为的形式模型 显示英文标题

标题： Computational Irreducibility as the Foundation of Agency: A Formal Model Connecting Undecidability to Autonomous Behavior in Complex Systems

Poria Azadi

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

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

标题： 间隙保持归约和独立集博弈的RE完全性 显示英文标题

标题： Gap-preserving reductions and RE-completeness of independent set games

Laura Mančinska, Pieter Spaas, Taro Spirig, Matthijs Vernooij

评论： 29页。版本2：新增第4节，包含改进的稳定性定理，取代原来的第4节和附录；第5节及主结果中的界限相应调整；新增第6节

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

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

标题： 带有完全分配和度约束的第二价格匹配 显示英文标题

标题： Second Price Matching with Complete Allocation and Degree Constraints

Rom Pinchasi, Neta Singer, Lukas Vogl, Jiaye Wei

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

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

标题： 基于学习增强的布尔可满足性算法 显示英文标题

标题： Learning-Augmented Algorithms for Boolean Satisfiability

Idan Attias, Xing Gao, Lev Reyzin

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

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

标题： 基于Trotter化后选择的哈密顿局部性测试 显示英文标题

标题： Hamiltonian Locality Testing via Trotterized Postselection

John Kallaugher, Daniel Liang

评论： 将出现在TQC 2025的论文集上

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

[42] arXiv:2505.06769 (交叉列表自 cs.AI) [中文pdf, pdf, 其他]

标题： 带有猜测的价值迭代算法对于马尔可夫链和马尔可夫决策过程 显示英文标题

标题： Value Iteration with Guessing for Markov Chains and Markov Decision Processes

Krishnendu Chatterjee, Mahdi JafariRaviz, Raimundo Saona, Jakub Svoboda

评论： 出现在第31届工具与算法国际会议（用于系统构造与分析）（TACAS 2025）上

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

[43] arXiv:2505.07378 (交叉列表自 math.CO) [中文pdf, pdf, html, 其他]

标题： 多项式不等式的不可判定性在子集密度和加性能量中的应用 显示英文标题

标题： Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies

Yaqiao Li

评论： 被接受在COCOON2025

主题： 组合数学 (math.CO) ; 计算复杂性 (cs.CC) ; 逻辑 (math.LO)

[44] arXiv:2505.07501 (交叉列表自 cs.GT) [中文pdf, pdf, 其他]

标题： 并发游戏中纯策略相关均衡的复杂性 显示英文标题

标题： The Complexity of Pure Strategy Relevant Equilibria in Concurrent Games

Purandar Bhaduri (IIT Guwahati)

评论： 在GandALF 2025会议论文集，arXiv:2509.13258

期刊参考： EPTCS 428，2025，第62-75页

主题： 计算机科学与博弈论 (cs.GT) ; 计算复杂性 (cs.CC) ; 形式语言与自动机理论 (cs.FL) ; 计算机科学中的逻辑 (cs.LO) ; 多智能体系统 (cs.MA)

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

标题： 量子经典模拟：统一克利福德、匹配门和纠缠 显示英文标题

标题： Quon Classical Simulation: Unifying Cliffords, Matchgates and Entanglement

Zixuan Feng, Zhengwei Liu, Fan Lu, Ningfeng Wang

评论： 44页，许多图表

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

[46] arXiv:2505.08951 (交叉列表自 math.CO) [中文pdf, pdf, html, 其他]

标题： 灵敏度与汉明图 显示英文标题

标题： Sensitivity and Hamming graphs

Sara Asensio, Yuval Filmus, Ignacio García-Marco, Kolja Knauer

评论： 8页，1幅图

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

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

标题： 寻找平衡点的自适应复杂度 显示英文标题

标题： The Adaptive Complexity of Finding a Stationary Point

Huanjian Zhou, Andi Han, Akiko Takeda, Masashi Sugiyama

评论： 被COLT2025接收

主题： 优化与控制 (math.OC) ; 计算复杂性 (cs.CC) ; 分布式、并行与集群计算 (cs.DC)

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

标题： 一种无损的先验分割规则用于分送配送路径问题 显示英文标题

标题： A lossless a priori splitting rule for split-delivery routing problems

Bo Jones, Julien Yu, John Gunnar Carlsson

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

[49] arXiv:2505.09628 (交叉列表自 cs.DM) [中文pdf, pdf, html, 其他]

标题： 超排列的$\mathcal{O}(n)$空间构造 显示英文标题

标题： An $\mathcal{O}(n)$ Space Construction of Superpermutations

Dhruv Ajmera

评论： 29页，5个图。附带文件包括源代码和README。GitHub仓库：https://github.com/dajmera-24/Superpermutation-Algorithm

主题： 离散数学 (cs.DM) ; 计算复杂性 (cs.CC) ; 数据结构与算法 (cs.DS) ; 组合数学 (math.CO)

[50] arXiv:2505.10387 (交叉列表自 cs.MA) [中文pdf, pdf, html, 其他]

标题： 多智能体路径搜索对于大规模智能体是难以处理的 显示英文标题

标题： Multi-Agent Path Finding For Large Agents Is Intractable

Artem Agafonov, Konstantin Yakovlev

主题： 多智能体系统 (cs.MA) ; 人工智能 (cs.AI) ; 计算复杂性 (cs.CC)