计算机科学实验班本科生在计算机科学会议STOC上发表论文

　　近日，大学交叉信息院计算机科学实验班本科生钟沛林以第一作者身份撰写的论文《分布流模型中的最优主成分分析》（“Optimal Principal Component Analysis in Distributed and Streaming Models”）被计算机科学领域国际会议第48届ACM计算理论年会（STOC 2016，48th Annual Symposium on the Theory of Computing）接收，并于美国东部时间6月19日赴美作大会宣讲。这是首次有中国籍本科生在STOC会议上发表第一作者论文，即便在美国麻省理工学院、普林斯顿大学等国际一流高校本科生中也极为罕见。

　　主成份分析（Principal Components Analysis，PCA）是在机器学习与数据挖掘中最重要的数据分析方法之一。在上述论文工作中，钟沛林提出了在通信复杂度上近乎最优的分布式PCA算法以及在空间复杂度上接近最优的PCA流算法。该算法在通信复杂度和流算法的空间复杂度方面可以做到与所需精确度参数无关，因此比之前的算法更有效，适用性更宽泛，对于精度要求高的场合具有重要的理论和实际意义。该工作是钟沛林与IBM研究院戴维·沃道夫（David P. Woodruff）研究员合作完成的。

　　钟沛林最初是在大三时计算机科学实验班专业课《大数据算法与模型》上接触到分布式PCA问题，对此课题产生了浓厚的兴趣，决定将工作重心放在该项目上，并在戴维·沃道夫研究员的进一步指导下完成相关论文。这也是计算机科学实验班学生本科阶段参与科研工作的又一突出。

　　截止到2016年6月，计算机科学实验班学生在读期间在计算机领域国际会议和期刊表论文132篇，如ACM计算理论国际年会（STOC）、ACM操作系统原理会议（SOSP）、IEEE计算复杂性国际会议（CCC）、IEEE国际计算机视觉与模式识别会议（CVPR）、美国人工智能协会国际年会（AAAI）等，其中计算机科学实验班学生为论文通讯作者或主要完的有99篇，并累计有31位学生出国参会并作论文宣讲。

　　ACM计算理论年会（STOC）是理论计算机科学领域最的国际会议，在整个计算机科学领域享有崇高的声望，属于难度最高的会议之一。该会议由ACM中的算法和计算理论兴趣小组（Special Interest Group in Algorithms and Computation Theory，SIGACT）提供资助，历年会议涵盖的领域十分广泛，包括算法和数据结构、计算复杂性、密码学、计算几何、算法图论与组合学、计算随机性、计算博弈论和量子计算等。理论计算机科学中最重要的项哥德尔（Goedel Prize）在ACM计算理论年会和自动机、语言与程序设计国际研讨会 （International Colloquium on Automata, Languages and Programming，ICALP）替颁布。本年度STOC 2016在美国州剑桥市举办，共接收论文92篇，吸引来自全球22个国家和地区的200多名学者、近百个科研机构参会。卧铺车上的冲动

　　本文由 325游戏（m.325games.com）整理发布