Hardness of the Binary Covering Radius Problem in Large Norms
该论文证明了对于大于约 35.31 的 范数，-近似格覆盖半径判定问题（-）是 NP 难的，其中逼近因子 大于 1 且当 趋于无穷大时收敛于 9/8。
💻 Category
cs.CC
45 篇论文
d-QBF with Few Existential Variables Revisited
本文证明了在命题部分为 CNF 且以存在变量数量 为参数的 d-QBF 问题中，双指数时间复杂度 $2^{2^k}\forall\exists$）的受限情形，提出了几乎最优的改进算法并给出了相应的下界。
Reinforced Generation of Combinatorial Structures: Ramsey Numbers
该论文介绍了基于大语言模型的代码变异代理 AlphaEvolve，通过单一元算法成功推导出五个经典拉姆齐数的改进下界，并复现了所有已知精确值及其他众多情况下的最佳下界。
A Simple Constructive Bound on Circuit Size Change Under Truth Table Perturbation
该论文明确给出了在任意固定有限完备基下，真值表单点扰动导致电路规模变化不超过 的构造性上界，并通过 telescoping 论证将其推广至一般汉明距离，同时利用 SAT 求解器在 时对 AIG 基的穷举验证确认了该上界的紧性。
The framework to unify all complexity dichotomy theorems for Boolean tensor networks
本文提出了一种统一所有布尔张量网络复杂性二分定理的框架，通过将未解决的计数问题按复数域上 2×2 矩阵构成的有限群分为九类，并分别利用矩阵转置闭包性质、克服涉及四元子群的实数化障碍、基于猜想推进一阶循环群情形以及解决高阶循环群情形，从而致力于构建涵盖整个问题类的最大统一定理。
Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
该论文将低维欧几里得空间中-中值和-均值问题的-近似算法运行时间从$2^{(1/\varepsilon)^{O(d^2)}}n2^{\tilde{O}(1/\varepsilon)^{d-1}}nd-1$的下界，从而确立了近乎紧致的复杂度界限。
Has quantum advantage been achieved?
本文针对量子计算优势是否真正实现这一争议，论证了该优势确实已经达成，并提出了理论与实验的后续发展方向。
Tetris is Hard with Just One Piece Type
该论文证明了在标准旋转系统下，除 O 型外所有四连方块（tetromino）的 Tetris 清除与生存问题均为 NP 难，从而推翻了关于仅使用 I 型方块的旧猜想，同时给出了仅使用多米诺骨牌或特定初始条件下 $1\times k$ 方块的清除与生存问题的多项式时间算法。
Quantum Automating -Frege Is LWE-Hard
该论文在标准格密码假设（LWE）下证明了不存在能弱自动化-Frege 证明系统的量子算法，从而首次建立了量子计算与命题证明搜索之间的困难性关联。
Privately Estimating Black-Box Statistics
本文提出了一种在统计效率与 oracle 效率之间进行权衡的差分隐私方案，用于估计任意黑盒函数的统计量，并证明了该方案近乎最优。
Polynomial-time isomorphism test for -generated extensions of abelian groups
该论文提出了一种多项式时间算法，用于测试由-生成群扩张的阿贝尔群（特别是阿贝尔-循环扩张和阿贝尔-单群扩张）的同构性，其核心创新在于设计了计算有限环单位群的多项式时间算法。
Three Fixed-Dimension Satisfiability Semantics for Quantum Logic: Implications and an Explicit Separator
本文比较了固定有限维希尔伯特空间上量子逻辑的三种可满足性语义，证明了标准语义蕴含局部偏布尔语义，后者又蕴含全局对易投影语义，并构造了一个显式公式作为标准语义可满足但后两者不可满足的分离实例，从而严格区分了这三种语义的可满足性类。
A base change framework for tensor functions
该论文建立了一个将张量函数结果从特定域推广到一般域的基础变换框架，并由此证明了任意域上 3 阶张量的切片秩被几何秩线性有界，且其切片秩具有准超乘性从而保证渐近切片秩的存在性。
Complexity Lower Bounds of Small Matrix Multiplication over Finite Fields via Backtracking and Substitution
该论文提出了一种结合代换法与系统回溯搜索的新方法，用于证明有限域上矩阵乘法的双线性复杂度下界，并成功将 上 $3 \times 3$ 矩阵乘法的双线性复杂度下界从 19 提升至 20。
On Factorization of Sparse Polynomials of Bounded Individual Degree
本文针对具有有界个体次数的稀疏多项式，提出了多项式时间的确定性算法以寻找其稀疏因子、从黑盒访问中恢复不可约稀疏多项式乘积的因子，并改进了现有稀疏多项式因式分解的复杂度界限，同时通过引入本原除数概念消除了对域特征的限制。
The Theory and Practice of Computing the Bus-Factor
本文提出了一种基于二分图建模和组合优化理论的统一框架，通过形式化“冗余”与“关键性”两种视角并引入一种能同时捕捉覆盖度丧失与项目碎片化的新型鲁棒性指标，解决了现有巴士因子（Bus-Factor）度量方法缺乏通用性、可比性及稳定性的问题，并提供了高效的近似算法与实证验证。
Quantum information advantage based on Bell inequalities
该论文提出了一种基于并行重复 CHSH 游戏推导关系的量子信息优势新方案，其采用信息论度量而非量子比特计数，并具备高效的验证器及比现有方案更鲁棒、更高效的量子证明者。
The Unit Gap: How Sharing Works in Boolean Circuits
该论文证明了在允许自由反演的与 - 非门基下，布尔电路与公式的最小规模之差恒为 0 或 1（单位间隙定理），并揭示了共享机制仅在变量数达到特定阈值时生效，且当差值为 1 时仅由单个扇出为 2 的门通过特定复用方式产生。
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
该论文研究了排列匹配拼图问题，完全刻画了基于行列升降约束的网格填数谜题的可解性条件（即约束图无环或标签切换不超过一次），给出了可解情况下的解数钩长公式及不可解情况下的最小修复算法，并证明了当约束推广为任意排列时，寻找最小修复方案是 NP 完全的。
Intrinsic Sequentiality in P: Causal Limits of Parallel Computation
该论文通过引入因果执行约束，证明了存在一类多项式时间决策问题，其信息传递受限于因果时间，导致任何尊重因果约束的执行方案都无法实现渐近并行加速，从而揭示了逻辑并行性与因果可执行性之间的根本差距。