Computational Complexity

Authors and titles for June 2025

[1] arXiv:2506.01832 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Pseudorandom bits for non-commutative programs Show Chinese title

Title: 非交换程序的伪随机位

Chin Ho Lee, Emanuele Viola

Comments: Minor fixes

Subjects: Computational Complexity (cs.CC)

[2] arXiv:2506.03492 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Hive is PSPACE-Hard Show Chinese title

Title: Hive 是 PSPACE 难的

Daniël Andel, Benjamin Rin

Comments: 29 pages, 23 figures

Subjects: Computational Complexity (cs.CC)

[3] arXiv:2506.04127 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: The Line Traveling Salesman and Repairman Problem with Collaboration Show Chinese title

Title: 具有协作的线路旅行商和维修工问题

Julian Golak, Finn Sörensen, Malte Fliedner

Subjects: Computational Complexity (cs.CC)

[4] arXiv:2506.04529 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Identity Testing for Circuits with Exponentiation Gates Show Chinese title

Title: 带指数门的电路恒等性测试

Jiatu Li, Mengdi Wu

Subjects: Computational Complexity (cs.CC) ; Data Structures and Algorithms (cs.DS)

[5] arXiv:2506.05351 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Infinite Time Turing Machines and their Applications Show Chinese title

Title: 无穷时间图灵机及其应用

Rukmal Weerawarana, Maxwell Braun

Comments: Published by Ren XYZ Inc

Subjects: Computational Complexity (cs.CC) ; Artificial Intelligence (cs.AI) ; Formal Languages and Automata Theory (cs.FL) ; Machine Learning (cs.LG)

[6] arXiv:2506.05518 (cross-list from cs.CC) [cn-pdf, pdf, other]

Title: Sorting by pile shuffles on queue-like and stack-like piles can be hard Show Chinese title

Title: 按堆洗牌对队列型和堆栈型堆的排序可能很困难

Kyle B. Treleaven

Comments: 55 pages, 18 figures. arXiv admin note: text overlap with arXiv:2503.11463

Subjects: Computational Complexity (cs.CC)

[7] arXiv:2506.06044 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: On the Complexity of Claw-Free Vertex Splitting Show Chinese title

Title: 关于无爪顶点分裂的复杂性

Faisal N. Abu-Khzam, Sergio Thoumi

Subjects: Computational Complexity (cs.CC)

[8] arXiv:2506.06138 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem Show Chinese title

Title: 关于 0-1 背包问题的 Dembo-Hammer 减少算法的扩展

Yang Yang

Subjects: Computational Complexity (cs.CC) ; Data Structures and Algorithms (cs.DS)

[9] arXiv:2506.06590 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Robust predicate and function computation in continuous chemical reaction networks Show Chinese title

Title: 连续化学反应网络中的鲁棒谓词和函数计算

Kim Calabrese, David Doty, Mina Latifi

Subjects: Computational Complexity (cs.CC) ; Distributed, Parallel, and Cluster Computing (cs.DC) ; Emerging Technologies (cs.ET)

[10] arXiv:2506.06716 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: #P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought? Show Chinese title

Title: #P被一个和两个#2DNF查询夹住：减法比我们想象的更强吗？

Max Bannach, Erik D. Demaine, Timothy Gomez, Markus Hecher

Subjects: Computational Complexity (cs.CC) ; Discrete Mathematics (cs.DM) ; Data Structures and Algorithms (cs.DS) ; Logic in Computer Science (cs.LO) ; Combinatorics (math.CO)

[11] arXiv:2506.11210 (cross-list from cs.CC) [cn-pdf, pdf, other]

Title: Second-Order Parameterizations for the Complexity Theory of Integrable Functions Show Chinese title

Title: 可积函数复杂性理论的二阶参数化

Aras Bacho, Martin Ziegler

Subjects: Computational Complexity (cs.CC)

[12] arXiv:2506.12019 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Algorithmic Structure in Subset Sum: Deterministic In-Bound Navigation and the Counting Complexity Divide Show Chinese title

Title: 子集和问题中的算法结构：确定性内部导航与计数复杂性分割

Thami Nkosi

Comments: 50 pages, 8 figures. Substantially revised. Title updated. The new version removes explicit claims about resolving the P vs NP and instead presents a refined analysis of the algorithm structure, complexity implications, and its use in Subset Sum and SAT contexts. Core method unchanged; discussion and positioning significantly improved

Subjects: Computational Complexity (cs.CC)

[13] arXiv:2506.12020 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: The Limits of Tractable Marginalization Show Chinese title

Title: 可处理边缘化的极限

Oliver Broadrick, Sanyam Agarwal, Guy Van den Broeck, Markus Bläser

Subjects: Computational Complexity (cs.CC) ; Artificial Intelligence (cs.AI)

[14] arXiv:2506.12021 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Monitoring graph edges via shortest paths: computational complexity and approximation algorithms Show Chinese title

Title: 通过最短路径监控图边：计算复杂性和近似算法

Giordano Colli

Subjects: Computational Complexity (cs.CC)

[15] arXiv:2506.12022 (cross-list from cs.CC) [cn-pdf, pdf, other]

Title: Sign-Rank of $k$-Hamming Distance is Constant Show Chinese title

Title: $k$-汉明距离的符号秩是常数

Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov

Comments: 19 pages, 6 figures

Subjects: Computational Complexity (cs.CC)

[16] arXiv:2506.12027 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Constant Bit-size Transformers Are Turing Complete Show Chinese title

Title: 恒定位宽变换器是图灵完备的

Qian Li, Yuyi Wang

Comments: 12 pages

Subjects: Computational Complexity (cs.CC) ; Machine Learning (cs.LG)

[17] arXiv:2506.12246 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Arithmetic Circuits with Division Show Chinese title

Title: 带除法的算术电路

Silas Cato Sacher

Subjects: Computational Complexity (cs.CC)

[18] arXiv:2506.12255 (cross-list from cs.CC) [cn-pdf, pdf, other]

Title: A Compendium of Subset Search Problems and Reductions relating to the Parsimonious Property Show Chinese title

Title: 关于简约性质的子集搜索问题及约化综述

Celina Janet Bartlett

Comments: Bachelor's thesis

Subjects: Computational Complexity (cs.CC) ; Discrete Mathematics (cs.DM)

[19] arXiv:2506.12420 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication Show Chinese title

Title: 确定性提升定理的一维数在前通信

Guangxu Yang, Jiapeng Zhang

Comments: 16 pages

Subjects: Computational Complexity (cs.CC)

[20] arXiv:2506.12562 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators Show Chinese title

Title: 具有非单调布尔算子的QBF的多项式前缀化

Abdallah Saffidine, Andreas Herzig

Comments: 15 pages, 0 figures

Subjects: Computational Complexity (cs.CC)

[21] arXiv:2506.12595 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Leakage-Resilient Extractors against Number-on-Forehead Protocols Show Chinese title

Title: 抗泄漏提取器针对额头上的数字协议

Eshan Chattopadhyay, Jesse Goodman

Comments: 22 pages

Subjects: Computational Complexity (cs.CC) ; Cryptography and Security (cs.CR)

[22] arXiv:2506.13655 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: The Word Problem for Products of Symmetric Groups Show Chinese title

Title: 对称群乘积的字问题

Hans U. Simon

Comments: 24 pages, 3 figures

Subjects: Computational Complexity (cs.CC)

[23] arXiv:2506.14081 (cross-list from cs.CC) [cn-pdf, pdf, other]

Title: The Complexity of Counting Small Sub-Hypergraphs Show Chinese title

Title: 子超图计数的复杂性

Marco Bressan, Julian Brinkmann, Holger Dell, Marc Roth, Philip Wellnitz

Subjects: Computational Complexity (cs.CC) ; Data Structures and Algorithms (cs.DS)

[24] arXiv:2506.14713 (cross-list from cs.CC) [cn-pdf, pdf, other]

Title: Linear Planar 3-SAT and Its Applications in Planning Show Chinese title

Title: 线性平面3-SAT及其在规划中的应用

Victorien Desbois, Ocan Sankur, François Schwarzentruber

Subjects: Computational Complexity (cs.CC)

[25] arXiv:2506.14725 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Generating uniform linear extensions using few random bits Show Chinese title

Title: 生成使用少量随机位的均匀线性扩展

Mark Huber

Comments: 16 pages

Subjects: Computational Complexity (cs.CC) ; Probability (math.PR) ; Computation (stat.CO)

[26] arXiv:2506.16171 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Maximum Reachability Orientation of Mixed Graphs Show Chinese title

Title: 混合图的最大可达性方向

Florian Hörsch

Subjects: Computational Complexity (cs.CC) ; Discrete Mathematics (cs.DM)

[27] arXiv:2506.16397 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: New Bounds for the Ideal Proof System in Positive Characteristic Show Chinese title

Title: 特征为正的理想证明系统的新的界

Amik Raj Behera, Nutan Limaye, Varun Ramanathan, Srikanth Srinivasan

Comments: 57 pages, To appear in the 52nd EATCS International Colloquium on Automata, Languages, and Programming (ICALP) 2025

Subjects: Computational Complexity (cs.CC) ; Logic in Computer Science (cs.LO) ; Logic (math.LO)

[28] arXiv:2506.16662 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Bounded Distance Decoding for Random Lattices Show Chinese title

Title: 随机格的有界距离解码

Shuhong Gao

Subjects: Computational Complexity (cs.CC)

[29] arXiv:2506.16956 (cross-list from cs.CC) [cn-pdf, pdf, other]

Title: The Proof Analysis Problem Show Chinese title

Title: 证明分析问题

Noel Arteche, Albert Atserias, Susanna F. de Rezende, Erfan Khaniki

Subjects: Computational Complexity (cs.CC) ; Logic in Computer Science (cs.LO) ; Logic (math.LO)

[30] arXiv:2506.17066 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Quantum k-SAT Related Hypergraph Problems Show Chinese title

Title: 量子 k-SAT 相关的超图问题

Simon-Luca Kremer, Dorian Rudolph, Sevag Gharibian

Subjects: Computational Complexity (cs.CC)

[31] arXiv:2506.17210 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Lower Bounds against the Ideal Proof System in Finite Fields Show Chinese title

Title: 有限域上针对理想证明系统的下界

Tal Elbaz, Nashlen Govindasamy, Jiaqi Lu, Iddo Tzameret

Subjects: Computational Complexity (cs.CC)

[32] arXiv:2506.17485 (cross-list from cs.CC) [cn-pdf, pdf, other]

Title: On the Parameterized Complexity of Semitotal Domination on Graph Classes Show Chinese title

Title: 关于图类上半总支配问题的参数化复杂性

Lukas Retschmeier

Comments: Master Thesis in Computer Science

Subjects: Computational Complexity (cs.CC)

[33] arXiv:2506.18440 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: New Hardness Results for Low-Rank Matrix Completion Show Chinese title

Title: 新的低秩矩阵补全的难解性结果

Dror Chawin, Ishay Haviv

Comments: 27 pages

Subjects: Computational Complexity (cs.CC) ; Machine Learning (cs.LG)

[34] arXiv:2506.18755 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Universal Solvability for Robot Motion Planning on Graphs Show Chinese title

Title: 图上的机器人运动规划的普遍可解性

Anubhav Dhar, Ashlesha Hota, Sudeshna Kolay, Pranav Nyati, Tanishq Prasad

Subjects: Computational Complexity (cs.CC) ; Computational Geometry (cs.CG) ; Data Structures and Algorithms (cs.DS)

[35] arXiv:2506.18921 (cross-list from cs.CC) [cn-pdf, pdf, other]

Title: Transcendental Encoding conjecture Show Chinese title

Title: 超越编码猜想

Anand Kumar Keshavan, Sunu Engineer

Comments: A counterexample to the conjecture has been found, negating the conjecture proposed in the paper

Subjects: Computational Complexity (cs.CC)

[36] arXiv:2506.19604 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: A primer on the closure of algebraic complexity classes under factoring Show Chinese title

Title: 代数复杂性类在因式分解下的闭包简介

C. S. Bhargav, Prateek Dwivedi, Nitin Saxena

Comments: 63 pages, 6 figures, The preprint is under review in the special issue of the workshop RTCA'23 Paris

Subjects: Computational Complexity (cs.CC)

[37] arXiv:2506.19756 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Algorithmic hardness of the partition function for nucleic acid strands Show Chinese title

Title: 核酸链的分划函数的算法难解性

Gwendal Ducloz, Ahmed Shalaby, Damien Woods

Comments: 29 pages, 4 figures, 1 appendix

Subjects: Computational Complexity (cs.CC)

[38] arXiv:2506.20221 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: On $NP \cap coNP$ proof complexity generators Show Chinese title

Title: 关于$NP \cap coNP$证明复杂性生成器

Jan Krajicek

Subjects: Computational Complexity (cs.CC) ; Logic (math.LO)

[39] arXiv:2506.21084 (cross-list from cs.CC) [cn-pdf, pdf, other]

Title: Timed Prediction Problem for Sandpile Models Show Chinese title

Title: 沙堆模型的定时预测问题

Pablo Concha-Vega (AMU, LIS), Kévin Perrot (AMU, LIS)

Subjects: Computational Complexity (cs.CC) ; Cellular Automata and Lattice Gases (nlin.CG)

[40] arXiv:2506.22344 (cross-list from cs.CC) [cn-pdf, pdf, other]

Title: Nets-within-Nets through the Lens of Data Nets Show Chinese title

Title: 网中网通过数据网的视角

Francesco Di Cosmo, Soumodev Mal, Tephilla Prince

Comments: 34 pages, 19 figures; fixed typos; corrected lemma 4

Subjects: Computational Complexity (cs.CC) ; Formal Languages and Automata Theory (cs.FL) ; Logic in Computer Science (cs.LO)

[41] arXiv:2506.23214 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Closure under factorization from a result of Furstenberg Show Chinese title

Title: 从Furstenberg的一个结果中的因子封闭性

Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

Subjects: Computational Complexity (cs.CC)

[42] arXiv:2506.23220 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Constant-depth circuits for polynomial GCD over any characteristic Show Chinese title

Title: 任意特征上的多项式GCD的常数深度电路

Somnath Bhattacharjee, Mrinal Kumar, Shanthanu Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

Subjects: Computational Complexity (cs.CC)

[43] arXiv:2506.23404 (cross-list from cs.CC) [cn-pdf, pdf, html, other]

Title: Characterizing Small Circuit Classes from FAC^0 to FAC^1 via Discrete Ordinary Differential Equations Show Chinese title

Title: 通过离散常微分方程表征从 FAC^0 到 FAC^1 的小电路类

Melissa Antonelli, Arnaud Durand, Juha Kontinen

Comments: 39 pages

Subjects: Computational Complexity (cs.CC) ; Logic in Computer Science (cs.LO)

[44] arXiv:2506.01003 (cross-list from cs.AI) [cn-pdf, pdf, html, other]

Title: Higher-Order Responsibility Show Chinese title

Title: 高阶责任

Junli Jiang, Pavel Naumov

Subjects: Artificial Intelligence (cs.AI) ; Computational Complexity (cs.CC) ; Computer Science and Game Theory (cs.GT)

[45] arXiv:2506.01432 (cross-list from quant-ph) [cn-pdf, pdf, html, other]

Title: New aspects of quantum topological data analysis: Betti number estimation, and testing and tracking of homology and cohomology classes Show Chinese title

Title: 量子拓扑数据分析的新方面：贝蒂数估计，以及同调和上同调类的检验与跟踪

Junseo Lee, Nhat A. Nghiem

Comments: 53 pages, 10 figures

Subjects: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC) ; Computational Geometry (cs.CG) ; Data Structures and Algorithms (cs.DS) ; Algebraic Topology (math.AT)

[46] arXiv:2506.01645 (cross-list from cs.DS) [cn-pdf, pdf, html, other]

Title: The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs Show Chinese title

Title: 部分性的代价：有界树宽图上部分广义支配集问题的复杂性

Jakob Greilhuber, Dániel Marx

Comments: Abstract shortened

Subjects: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC)

[47] arXiv:2506.01854 (cross-list from cs.CR) [cn-pdf, pdf, html, other]

Title: Black-Box Crypto is Useless for Pseudorandom Codes Show Chinese title

Title: 黑盒加密对于伪随机码是没有用的

Sanjam Garg, Sam Gunn, Mingyuan Wang

Subjects: Cryptography and Security (cs.CR) ; Computational Complexity (cs.CC)

[48] arXiv:2506.02031 (cross-list from math.LO) [cn-pdf, pdf, html, other]

Title: Effective Versions of Strong Measure Zero Show Chinese title

Title: 强测度零的有效版本

Matthew Rayman

Subjects: Logic (math.LO) ; Computational Complexity (cs.CC)

[49] arXiv:2506.03014 (cross-list from quant-ph) [cn-pdf, pdf, html, other]

Title: Convergence and efficiency proof of quantum imaginary time evolution for bounded order systems Show Chinese title

Title: 有界阶系统量子虚时演化的收敛性和效率证明

Tobias Hartung, Karl Jansen

Comments: 16 pages

Subjects: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC) ; Computational Physics (physics.comp-ph)

[50] arXiv:2506.03319 (cross-list from math.CO) [cn-pdf, pdf, html, other]

Title: A Linear Kernel for Independent Set Reconfiguration in Planar Graphs Show Chinese title

Title: 平面图中独立集重配置的线性核

Nicolas Bousquet, Daniel W. Cranston

Comments: 20 pages, 8 figures

Subjects: Combinatorics (math.CO) ; Computational Complexity (cs.CC)