姚班本科生在计算机科学顶级会议STOC上发表论文

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

 
钟沛林参加STOC2016并作大会论文宣讲。

主成份分析（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多名学者、近百个科研机构参会。

论文链接：
http://delivery.acm.org/10.1145/2900000/2897646/p236-boutsidis.pdf?ip=167.160.170.206&id=2897646&acc=OPEN&key=4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E4D4702B0C3E38B35%2E6D218144511F3437&CFID=804126486&CFTOKEN=91182901&__acm__=1466569381_de5df6c108ebcfd9c32e74470fdfa71a

供稿：交叉信息研究院 编辑：李华山