A symmetric recursive algorithm for mean-payoff games
该论文提出了一种用于求解平均收益博弈的新确定性对称递归算法。
💻 Category
cs.DS
87 篇论文
Succinct QUBO formulations for permutation problems by sorting networks
该论文提出了一种基于排序网络的新型 QUBO 公式，通过仅需 个二进制变量和稀疏交互图，实现了对排列问题的更紧凑、无偏且支持多种代数运算的编码，显著优于传统的排列矩阵方法。
Structured Gossip: A Partition-Resilient DNS for Internet-Scale Dynamic Networks
本文提出了一种名为“结构化 gossip"的 DNS 方案，通过利用 DHT 手指表实现被动稳定化，在无需全局协调的情况下，将消息复杂度从降低至，从而有效解决了移动自组织网络和边缘计算中网络分区带来的分布式名称解析挑战。
The Theory and Practice of Computing the Bus-Factor
本文提出了一种基于二分图建模和组合优化理论的统一框架，通过形式化“冗余”与“关键性”两种视角并引入一种能同时捕捉覆盖度丧失与项目碎片化的新型鲁棒性指标，解决了现有巴士因子（Bus-Factor）度量方法缺乏通用性、可比性及稳定性的问题，并提供了高效的近似算法与实证验证。
The Li-Chao Tree: Algorithm Specification and Analysis
本文首次为在竞赛编程中广泛使用但缺乏正式文献记载的李超树提供了包含完整算法规范、正确性证明、复杂度分析及实证性能评估的权威形式化定义。
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
该论文研究了排列匹配拼图问题，完全刻画了基于行列升降约束的网格填数谜题的可解性条件（即约束图无环或标签切换不超过一次），给出了可解情况下的解数钩长公式及不可解情况下的最小修复算法，并证明了当约束推广为任意排列时，寻找最小修复方案是 NP 完全的。
Sampling Colorings with Fixed Color Class Sizes
本文利用多元多项式几何框架，提出了一个多项式时间算法，用于在 条件下对具有固定色类大小的均衡图着色进行均匀随机采样，并由此导出了着色类大小的多元局部中心极限定理。
Bayesian inference of planted matchings: Local posterior approximation and infinite-volume limit
本文研究了在一维空间下两个相关随机点集之间隐藏匹配的贝叶斯推断问题，证明了在部分匹配模型中后验分布可由局部算法近似且边际统计量存在热力学极限，而在精确匹配模型中则需先进行全局排序并引入“流”的概念来定义极限，同时指出将结果推广至高维仍是未解难题。
A note on approximating the average degree of bounded arboricity graphs
本文旨在完整呈现并优化 Eden 等人提出的算法，使其能在有界树宽图中以 的查询复杂度实现平均度的 近似，从而避免了原论文中因参数搜索导致的对数因子损失。
Faster shortest-path algorithms using the acyclic-connected tree
该论文提出了一种名为“无环连通树”的线性时间图分解方法，通过利用图的模块化结构递归优化单源最短路径算法，从而在嵌套宽度较小的图上实现了超越最坏情况的时间复杂度。
Computational Complexity in Property Testing
该论文系统研究了属性测试中查询复杂度与时间复杂度之间的相互关系，通过建立无条件及基于强指数时间假设的层级定理，并结合-SUM 猜想证明了半空间距离近似问题中查询与时间复杂度的可分离性，从而揭示了该领域计算硬度的基本界限。
Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing
该论文通过建立将事实记忆形式化为成员测试问题的率失真定理，从信息论角度证明在容量受限下，即使拥有完美数据，大语言模型为了追求最优记忆效率而不得不将高置信度赋予非事实，从而揭示了幻觉是空间最优性导致的必然结果。
DRESS and the WL Hierarchy: Climbing One Deletion at a Time
本文从理论上证明了-DRESS 框架不仅能无条件区分所有 CFI图对，还在特定结构猜想下被证明其区分能力至少等同于-WL 层次结构，从而确立了该框架在图同构判别中的强大理论地位。
Transposition is Nearly Optimal for IID List Update
本文证明了在请求独立同分布的列表更新问题中，无需记忆访问频率的“换位规则”（Transposition rule）其稳态下的期望访问成本最多比最优静态排序高 1，从而在加性常数范围内证实了 Rivest 长达 50 年的猜想。
Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
该论文提出了一种确定性算法，仅需 次最短路径距离查询，即可在最大度为 且树长为 的连通无向图中高效重构边集，从而将此类图的重建复杂度相比现有最优算法降低了 因子并达到了下界。
Density-Dependent Graph Orientation and Coloring in Scalable MPC
该论文提出了一种在强亚线性内存可扩展 MPC 模型中，仅用 轮即可完成基于子图密度的图定向与顶点着色的算法，成功打破了此前 轮复杂度的理论瓶颈。
Intermittent Cauchy walks enable optimal 3D search across target shapes and sizes
该论文通过数学证明揭示了三维空间中间歇性柯西行走（）具有独特的尺度不变性，能够针对广泛的目标尺寸和形状实现近最优检测，从而为莱维飞行觅食假说奠定了严谨基础。
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
本文证明了整数对称次模函数中所有值为 的割集族 admits 一个多项式大小的表示，并给出了构造该表示及在固定 下解决带基数约束的割集寻找问题的多项式时间算法。
Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements
该论文通过引入新的常数时间原语，证明了在联合移动模型下无需辅助假设即可实现可编程物质的亚线性时间通用重配置，具体给出了将任意结构在轮内重配置为规范线段结构的算法，并解决了 Padalkin 等人提出的开放性难题。
Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
本文提出了一种名为“采样与搜索”的高效算法，通过引入预测器预处理和高维采样策略，显著降低了学习增强型-均值聚类问题的计算复杂度并改善了聚类成本。