FOCS 2022 | 姜少峰课题组针对亚线性算法的研究取得重要进展

大家好，欢迎来到IT知识分享网。

编者按

近期，理论计算机领域国际顶级会议第63届 IEEE 计算机科学基础年度研讨会（the 63rd IEEE Symposium on Foundations of Computer Science, FOCS 2022）公布了论文接收名单，北京大学前沿计算研究中心姜少峰课题组有两篇关于亚线性算法的论文入选。这是北京大学首次同一个课题组有2篇论文入选 FOCS 会议，同时也是中心连续第二年有成果被该会议接收。

现今，以大数据为基础的机器学习等技术得到了广泛的应用。伴随而来的，如何在大数据上进行高效计算成为了算法研究的挑战。传统的针对图灵机模型设计的算法已经不能适应大数据，亟需以数据流、并行计算等“亚线性”计算模型下的算法理论的突破。亚线性算法的研究也已经成为了算法理论研究的一个热点方向。

北京大学前沿计算研究中心姜少峰课题组聚焦于亚线性算法研究，近期在针对大数据的一般数据摘要方法以及高维数据计算等方向取得了重要进展。

在 The Power of Uniform Sampling for Coresets 一文中，姜少峰课题组考虑了针对聚类这一基本数据分析问题的核心集。核心集是大数据的摘要，旨在系统地、保证精度地将大数据转化为小数据，从而进行高效数据分析，是处理大数据的重要方法。本文给出了一个全新的、主要基于均匀采样的、针对聚类问题的构造核心集的框架。相比先前的基于重要性采样的方法，这种均匀采样方法能处理带容量的聚类、公平聚类等聚类问题的重要变种，得到了第一个不依赖于数据大小 n 和数据维数的针对公平聚类的核心集。另外，该框架第一次将数据所在度量空间的 VC 维与核心集大小联系了起来，放宽了先前重要性采样对于带权 VC 维的要求，因此简化、加强了所有已知的非欧式空间上的核心集结果，并首次得到在 Wasserstein distance 度量上不依赖于数据大小的核心集。最后，算法框架实现简单，具有较大应用潜力。

在 Streaming Facility Location in High Dimension via Geometric Hashing 一文中，姜少峰课题组针对设施选址这一运筹学、计算机科学中的经典问题，考虑其在高维几何数据流上的近似算法。高维几何数据流模型自2004年由 Indyk 提出以来，已经得到了广泛的研究。然而，已有结果均基于自90年代业已成熟的 tree embedding 和 randomly-shifted quadtree 等技术，只能得到

量级的近似比。本文创新性地提出一种称为 consistent hashing 的新几何哈希方法，并将其与重要性采样方法结合，在两轮和随机顺序数据流模型上均得到了常数近似比，本质上优于基于 tree embedding 的传统方法；另外还得到针对单轮动态数据流模型的 –近似的算法，优于已知最好结果（ 是维数）。上述所有算法都仅使用

的空间。这种新的算法框架为高维几何问题的研究提供了崭新的思路，有望用来解决其他重要的高维几何问题。

以上两项成果与来自美国、以色列、英国、捷克、瑞士、丹麦等各地的学者合作完成，得到了科技部国家重点研发计划青年科学家项目、北京大学引进人才启动经费和北京大学信息技术高等研究院的经费支持。

文字 | 姜少峰课题组

作者简介

姜少峰博士，现任北京大学前沿计算研究中心助理教授、北京大学博雅青年学者，于2021年正式加入中心。他于2017年在香港大学获得博士学位，曾在以色列魏茨曼科学研究学院进行博士后研究，并曾在芬兰阿尔托大学任助理教授。他的研究方向为理论计算机科学，近期侧重于大数据算法及其在机器学习中的应用，并已在包括 FOCS，SICOMP，SODA，ICML，NeurIPS 等主流国际期刊和会议上发表论文多篇。