科研成果合辑 | SODA 2025顶会成果速览

- SODA 2025论文发布合辑- 

科研成果速览

在即将举行的计算机算法领域顶级学术会议 2025 ACM-SIAM Symposium on Discrete Algorithm（SODA）中，清华大学交叉信息院师生共计发布6项科研成果：从“k-计数器近似计数”问题在数据流模型下的复杂度，到提出了第一个在切割查询模型下使用次二次查询次数计算简单图全局最小割的确定性算法，到改进矩阵乘法的计算复杂度，到设计有效的核心集构造算法，到提出了一种全新的先知秘书问题的算法框架，研究人员为计算机算法领域的研究提供了新思路。

该成果研究了“k-计数器近似计数”问题在数据流模型下的复杂度。在数据流计算模型中，只能按顺序读取输入字符串一次，无法重复读取，并且存储空间有限。这意味着无法保存所有输入数据。数据流模型是一个基本的计算模型，已经得到了广泛的研究。

“k-计数器近似计数”问题的输入是一个来自k的n次方的字符串，需要估计字符串中每个j(j∈[k])的出现次数。一个典型的设定是，要求每个j∈[k]的估计加性误差不超过n/(3(k-1))，并且主要关注n>>K>>1的数据范围。

研究组证明了一个下界结果：在数据流模型中，确定性的最坏情况下，k-计数器近似计数问题需要Ω(klog(n/k))个比特的空间，而之前对此并没有已知的非平凡下界。相比之下，简单地统计每个j∈[k]的确切数量需要O(klogn)个比特的空间。

研究组的下界结果还可以用于证明一些其他数据流算法的最优性。例如，研究组证明了著名的 Misra-Gries 算法[MG82] 达到了最佳空间复杂度。

该论文独立作者为清华大学交叉信息院2021级本科生王一川。

项目论文：

Tight Streaming Lower Bounds for Deterministic Approximate Counting, Yichuan Wang, https://arxiv.org/abs/2406.12149, SODA 2025. 

该研究提出了第一个在切割查询模型下使用次二次查询次数计算简单图全局最小割的确定性算法。对于包含 $n$ 个顶点的图 $G$，研究组的算法通过 $\Otil(n^{\frac{5}{3}})$ 次查询计算出全局最小割。这在切割查询模型中是首次实现的突破。研究组还展示了一种可以在 $\Otil(n^{\frac{5}{3}})$ 次查询内找到大小为 $\Otil(n)$ 的 $s$-$t$ 最大流的算法。

作为方法中的关键步骤，研究组提出了扩展分解和隔离切割的高效实现。这些技术不仅在研究组研究的全局最小割问题中发挥了重要作用，可能也在其他图算法和网络优化领域有独立的应用价值。

该论文共同第一作者（按姓氏字母顺序排序）为密歇根大学安娜堡分校博士研究生Aditya Anand、助理教授Thatchaphol Saranurak, 清华大学交叉信息院2020级本科生王云帆，通讯作者为Thatchaphol Saranurak。

项目论文：

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries, Aditya Anand, Thatchaphol Saranurak, Yunfan Wang, SODA 2025. 

交叉信息院段然副教授与姚班校友周任飞以及国外的研究者合作改进了矩阵乘法的计算复杂度，新的时间复杂度为O(n^{2.371339})。这个成果在[Duan, Wu, Zhou FOCS 2023]和[Vassilevska Williams, Xu, Xu, Zhou SODA 2024]两篇论文的基础上提出了三维均非对称的哈希方法，进一步弥补了CW方法中的组合损失。论文还改进了长方形矩阵乘法的复杂度。

该论文共同第一作者（按姓氏字母顺序排序）为哥伦比亚大学助理教授Josh Alman、清华大学交叉信息院副教授段然、麻省理工学院教授Virginia Vassilevska Williams、加利福尼亚大学圣迭戈分校博士后徐寅展、麻省理工学院博士生徐梓萱，以及交叉信息院2024届姚班校友、卡内基梅隆大学博士生周任飞。

项目论文：

More Asymmetry Yields Faster Matrix Multiplication, Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou, SODA 2025. 

核心集技术（coresets）是处理超大规模数据的一项重要技术，能够将大数据集转化为较小的数据集，同时保证小数据集上的解与原数据集基本相同。在过去十年中，核心集技术得到了快速发展，并已广泛应用于聚类、回归、矩阵运算、机器学习和大模型训练等多个领域。本研究针对一系列具有通用约束的聚类问题，首次引入了包括聚类中心容量约束和数据点分配结构约束的分配约束类别，并设计了有效的核心集构造算法。这些算法显著改进并推广了现有结果，并为若干新问题提供了核心集构造的有效算法。研究组设计了新的自适应采样算法，并引入了处理分配结构约束的新数学技术，将采样复杂度与某个凸体B中的运输问题的Lipschitz常数Lip(B)相关联，并为matroid polytope的最优分配运输问题证明了Lip(B)的非平凡上界。

该论文共同第一作者（按姓氏字母顺序排序）为交叉信息院2012届本科、2017届研究生校友黄棱潇，交叉信息院教授李建、上海财经大学教授陆品燕，以及华为研究人员吴旋。

项目论文：

Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds, Lingxiao Huang, Jian Li, Pinyan Lu, Xuan Wu, SODA 2025.

检索数据结构（retrieval data structures）是一类能够在不显式存储键（key）的情况下，回答键值查询（key-value queries）的数据结构。它有四种常见规则（静态、值可变、增量、动态），每种规则为用户提供不同程度的动态性。在这篇工作中，研究组求出了后两种规则（增量和动态）的最优空间效率。这一成果为跨越二十多年的一系列研究工作画上了句号，并带来了一个意外的发现：增量规则长期以来被认为与动态规则基本等价，但研究组证明，增量规则的最优空间效率存在“相变现象”——当值大小接近 log n 时，最优空间冗余量急剧减少，显示出比动态规则更好的空间效率。

该论文共同第一作者（按姓氏字母顺序排序）为卡内基梅隆大学助理教授 William Kuszmaul、哈佛大学博士生 Aaron Putterman、清华大学交叉信息院2023级本科生许庭强、周航锐，以及交叉信息院2024届姚班校友、卡内基梅隆大学博士生周任飞。

项目论文：

Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval, William Kuszmaul, Aaron Putterman, Tingqiang Xu, Hangrui Zhou, Renfei Zhou, SODA 2025.

先知秘书是在线算法领域中经典的先知模型和秘书模型的结合问题，且与拍卖问题的简单机制设计相关。本文提出了一种全新的针对该问题的算法框架，对各个物品设计多阶段的激活概率，且对最大物品有特殊设计。此算法框架将该问题的最优近似比改进到0.688。对于更一般的匹配意义下的先知秘书，研究组给出了0.641近似比的算法，是该问题下的首个近似比超越1-1/e的算法。

该论文共同第一作者（按姓氏字母顺序排序）为清华大学交叉信息院2020级本科生陈子云，2008届姚班校友、香港大学副教授黄志毅、博士生李东晨，上海财经大学副教授唐志皓。

项目论文：

Prophet Secretary and Matching: the Significance of the Largest Item，Ziyun Chen，Zhiyi Huang, Dongchen Li，Zhihao Gavin Tang，SODA 2025.