近日，北京大学前沿计算研究中心姜少峰课题组论文 Streaming Euclidean Max-Cut: Dimension vs Data Reduction 获理论计算机领域国际顶级会议理论计算机年会（Symposium on Theory of Computing，STOC）接收。该论文由北京大学2021级图灵班本科生陈宇、北京大学前沿计算研究中心助理教授姜少峰和以色列魏茨曼科学研究所教授 Robert Krauthgamer 合作完成，提出了高维空间最大割的接近最优的数据流算法。

　　论文链接：https://arxiv.org/abs/2211.05293

　　在大数据时代，如何有效处理高维大数据成为算法设计的一大挑战。该论文在数据流这一重要大数据计算模型下，针对高维空间中的最大割这一算法研究的基本核心问题，给出了接近最优的数据流算法。此前，该问题仅在低维空间进行过研究。本文是自2005年 Frahling 等人提出最大割的的低维数据流算法以来，取得的根本性突破。

　　由于“维数诅咒”等限制，针对高维的算法设计技术相对匮乏。论文探索了两种处理高维数据的一般方法——降维和数据摘要，并证明了两个主要结果：一是 Johnson-Lindenstrauss 变换的目标维数只需要常数维就可以保证最大割的值近似不变；二是一个仅需要多项式对数空间的基于数据摘要的数据流算法。该算法使用重要性采样的思路，应用了基于随机偏移四分树的空间嵌入技术，创新性地避免了将空间嵌入的误差引入近似比，并仅影响空间复杂度。这为高维数据流算法提供了一种新的基本采样工具，在其它相关问题上有广阔应用前景。

　　姜少峰课题组近期聚焦于大数据算法理论方向，已在 STOC，FOCS，SODA 等理论计算机科学顶级会议上发表多篇论文。本文是收录于 FOCS 22的高维几何数据流算法结果的延伸。这些结果已对该领域形成重要影响。

作者简介

　　陈宇*，北京大学信息科学技术学院 “图灵班” 2021级本科生，对理论计算机科学有着广泛的研究兴趣，如算法分析与设计、量子计算和计算社会科学等。她高中曾参加信息学竞赛，并获得2019年全国青少年信息学奥林匹克竞赛金牌，进入国家集训队，保送北京大学。

　　*在正式发表的版本中将使用新名字：陈晓雨

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