Dynamic Kernel Graph Sparsifiers
本文提出了一种完全动态的数据结构，能够在点集位置发生单点更新时，以 的更新时间和 的初始化时间高效维护几何图的光谱稀疏子图，并支持对抗性环境及相关的矩阵向量运算。
💻 Category
cs.DS
91 篇论文
An Objective Improvement Approach to Solving Discounted Payoff Games
该论文提出了一种全新的对称方法，通过构建包含所有边的约束系统并最小化不等式误差之和，以逐步改进的方式求解折扣收益博弈，从而打破了此类问题求解仅依赖策略改进或值迭代方法的传统认知。
A computational transition for detecting correlated stochastic block models by low-degree polynomials
本文研究了从具有 个对称社区的稀疏随机块模型中采样得到的成对相关图与独立 Erdős-Rényi 图之间的相关性检测问题，确定了基于邻接矩阵低阶多项式的检测阈值，证明当且仅当子采样概率 超过 Otter 常数 与 Kesten-Stigum 阈值 中的较小值时，该类检测才是可行的。
Highway Dimension: a Metric View
本文通过放宽高速公路维度的定义以涵盖所有倍增空间（如网格图和欧几里得平面），构建了相应的度量工具包，并在此新定义下为旅行商问题（TSP）设计了多项式时间近似方案（PTAS）。
On the Inversion Modulo a Power of an Integer
本文提出了两种通用算法：一种基于小学乘法思想，适用于计算任意互质整数 对 的模逆，并能利用计算机架构特性（如 ）显著提升效率；另一种则是对 Dumas 和 Hurchalla 针对 模数的 Hensel 提升方法的推广，使其适用于任意整数 的 模数情形。
Even Faster Kernel Matrix Linear Algebra via Density Estimation
该论文提出利用核密度估计（KDE）查询来加速核矩阵的线性代数运算，显著降低了矩阵向量积、矩阵乘积、谱范数及元素求和等任务在误差参数和样本量上的计算复杂度，并辅以条件二次时间下界以揭示该方法的理论极限。
Deterministic Coreset for Lp Subspace
该论文提出了一种首个确定性迭代算法，用于构建任意 的 子空间嵌入 -核心集，在消除核心集规模对数因子的同时实现了紧致的最优大小，并保证了确定性的损失上下界。
Submodular Maximization over a Matroid -Intersection: Multiplicative Improvement over Greedy
本文提出了一种针对受 个任意拟阵交约束的非负单调子模函数最大化问题的新算法，该算法实现了优于传统贪心算法的 $0.819k+O(\sqrt{k})kk$ 无关。
Skirting Additive Error Barriers for Private Turnstile Streams
本文提出了一种在差分隐私下针对转门流（turnstile stream）的连续发布算法，通过同时允许加性和乘性误差，成功绕过了先前仅考虑加性误差时的下界，实现了仅需对数空间即可达到对数级误差的统计量估计。
Bounding the Average Move Structure Query for Faster and Smaller RLBWT Permutations
本文提出了一种通过截断长区间来限制平均移动结构查询时间的简化方法，该方法不仅将 RLBWT 排列的构建时间和空间复杂度优化至线性，还显著减少了存储开销并提升了查询效率，同时提供了相应的 RunPerm 库以支持实际应用。
DRESS: A Continuous Framework for Structural Graph Refinement
本文提出了 DRESS 框架，这是一种确定性的无参数图结构细化方法，通过迭代收敛生成同构不变且数值稳定的边向量指纹，其计算效率远超 2-WL 测试，并可通过扩展至 motif 聚合及顶点删除子图（-DRESS）进一步提升表达力，成功区分强正则图基准并达到任意深度的 WL 表达水平。