A note on approximating the average degree of bounded arboricity graphs
本文旨在完整呈现并优化 Eden 等人提出的算法，使其能在有界树宽图中以 的查询复杂度实现平均度的 近似，从而避免了原论文中因参数搜索导致的对数因子损失。
💻 Category
cs.CC
45 篇论文
The Power of Shallow-depth Toffoli and Qudit Quantum Circuits
该论文证明了浅层量子电路（特别是包含 Toffoli 门或量子建议的电路）在计算能力上超越特定经典常数深度电路，并揭示了在无限门集情形下，高维量子系统并未提供比标准量子比特更多的优势。
Computational Complexity in Property Testing
该论文系统研究了属性测试中查询复杂度与时间复杂度之间的相互关系，通过建立无条件及基于强指数时间假设的层级定理，并结合-SUM 猜想证明了半空间距离近似问题中查询与时间复杂度的可分离性，从而揭示了该领域计算硬度的基本界限。
Deciding winning strategies in Yu-Gi-Oh! TCG is hard
该论文证明了在《游戏王》集换式卡牌游戏中，判定给定可计算策略是否为必胜策略的问题是 -完全的（即不可判定），并构造了符合当前禁限卡表的合法卡组，通过归约可计算策略的判定问题至可计算停机问题以及可数良序集问题来证实这一结论。
The Generation-Recognition Asymmetry: Six Dimensions of a Fundamental Divide in Formal Language Theory
本文首次将形式语言理论中生成与识别的不对称性统一为一个包含计算复杂度、歧义性、方向性、信息可用性、语法推断和时间性六个维度的多维现象，并指出这种不对称性源于识别始终受限于给定输入而生成未必受限，进而探讨了其在自然语言处理及大语言模型中的意义。
Fast polynomial computations with space constraints
这篇论文探讨了在空间受限条件下多项式算法的优化，一方面提出了兼顾时间与空间效率的多项式基本运算算法，另一方面针对稀疏多项式开发了首个准线性插值算法并研究了其整除与因式分解等计算难题。
Classical simulability of quantum circuits followed by sparse classical post-processing
该论文研究了多项式规模量子电路后接稀疏经典后处理的经典可模拟性，不仅给出了任意稀疏后处理下电路可模拟的充要条件，还证明了常数深度电路在该设置下可通过访问特定交换量子电路的随机算法进行模拟。
Intrinsic Information Flow in Structureless NP Search
该论文通过信息论视角重新诠释 NP 问题中的见证者发现，指出在完全无结构的“伪随机”探测模型下，由于多项式次探测所能获取的互信息量远不足以消除不确定性，从而揭示了指数级搜索复杂性的信息论根源。
Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
本文证明了对于任意固定图，最大部分列表-着色问题在-自由图上可在多项式时间内求解，从而解决了 Agrawal 等人提出的开放问题，并将 Chudnovsky 等人之前的算法复杂度从改进为多项式时间。
On complexity of restricted fragments of Decision DNNF
本文深入研究了决策 DNNF 的受限片段，提出了证明-OBDD 下界的新方法并重新确立了其在有界入射树宽 CNF 表示上的 XP 复杂度，同时揭示了该模型与其他 OBDD 变体间的指数级分离，并发现了一个能高效执行 Apply 操作的受限情形及一种对入射树宽 CNF 表示更强大的结构化-FBDD 模型。
No exponential quantum speedup for anymore
本文针对 Chen、Liu 和 Zhandry 于 2021 年提出的平均情况 -短整数解（）问题的量子加速算法，提出了针对该问题及更广义约束整数解问题的有效经典算法，从而证明不再存在指数级量子加速。
A $4/3$ ratio approximation algorithm for the Tree Augmentation Problem by deferred local-ratio and climbing
本文提出了一种基于“延迟局部比率”和“爬升”技术的算法，在 时间内为树增强问题（TAP）提供了 $4/3$ 的近似比，且无需枚举指数级结构或进行线性规划缩放。
Classification of Local Optimization Problems in Directed Cycles
该论文针对有向环上的局部优化问题，在确定性和本地随机化 LOCAL 模型中给出了完整的分布式计算复杂度分类，证明了其复杂度必然属于 、 或 中的某一类，并提出了能够自动判定复杂度类别及合成最优分布式算法的高效元算法。
Why Are Linear RNNs More Parallelizable?
该论文通过建立线性 RNN 与非线性 RNN 与标准复杂度类（如、和）之间的紧密联系，从理论层面揭示了线性 RNN 之所以能像 Transformer 一样高效并行化，是因为其可被建模为对数深度算术电路，而非线性 RNN 因能解决或完全问题而存在根本性的并行化障碍。
Generalizing Fair Top- Selection: An Integrative Approach
本文针对多保护组下的公平 Top- 选择问题，揭示了现有假设下的计算不可行性并提出了针对小规模 的高效算法，同时引入效用损失作为新的差异度量以增强评分函数的稳定性，最终通过工程权衡在真实数据集上实现了优异性能。
Quantum Algorithms for Network Signal Coordination
本文提出并验证了用于解决 NP 完全网络信号协调（NSC）问题及其鲁棒变体的量子算法，通过格罗弗搜索实现了二次加速，并证明了该算法在多项式精度鲁棒性下仍能保持与搜索空间规模无关的二次量子加速优势。
Attacking the Polynomials in the Maze of Finite Fields problem
本文针对 GMV 在 2025 年 4 月提出的有限域多项式系统求解竞赛，提出了一种利用系统结构化稀疏性、通过连续计算结式生成单变量多项式从而显著快于暴力穷举和标准 Gröbner 基方法的"ResultantSolver"算法，并提供了伪代码、实验对比及并行化改进建议。
Recurrent Graph Neural Networks and Arithmetic Circuits
该论文通过引入具有记忆门机制的递归算术电路，建立了在实数域上运行的递归图神经网络与递归算术电路在表达能力上的精确对应关系。
ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
该论文提出了一种针对有界树宽复形上最优莫尔斯匹配问题的 $2^{O(k \log k)} n2^{o(k \log k)} n^{O(1)}$ 时间的算法，从而确定了该问题关于树宽参数的紧确复杂度。
Aaronson-Ambainis Conjecture Is True For Random Restrictions
本文证明了 Aaronson-Ambainis 猜想对于方差非低的任意多项式在随机限制下是成立的，即存在一个非可忽略的概率使得限制后的多项式具有足够大的坐标影响力。