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

2016年06月21日 浏览次数: 0

近日,清华大学交叉信息院计算机科学实验班(姚班)计科20班本科生钟沛林以第一作者身份撰写的论文《分布式模型和流模型下最优的主成分分析算法》(“Optimal Principal Component Analysis in Distributed and Streaming Models”)被计算机科学领域顶级国际会议第48ACM计算理论年会(STOC 201648th Annual Symposium on the Theory of Computing,)接收,并于美国东部时间619日赴美作大会宣讲。这是首次有中国籍本科生在STOC会议上发表第一作者论文,即便在美国麻省理工学院、普林斯顿大学等国际一流高校本科生中也属相当难得。

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

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

钟沛林最初是在大三时姚班专业课《大数据算法与模型》上接触到分布式PCA问题,对此课题产生了浓厚的兴趣,决定将工作重心放在该项目上,并在David P. Woodruff研究员的进一步指导下完成相关论文。这也是姚班学生本科阶段参与科研工作的又一突出成果。截止到20166月,姚班学生在读期间在计算机领域国际顶级会议和期刊共发表论文132篇,如STOCSOSPCOLT RECOMBCCCCVPRAAAI等,其中计算机科学实验班学生为论文通讯作者或主要完成人的有99篇,并累计有31位学生出国参会并作论文宣讲。

ACM计算理论年会(STOC)是理论计算机科学领域最顶级的国际会议,在整个计算机科学领域享有崇高的声望,并被公认属于难度最高的会议之一。该会议由ACM中的算法和计算理论兴趣小组(Special Interest Group in Algorithms and Computation TheorySIGACT)提供资助,历年会议涵盖的领域十分广泛,包括算法和数据结构、计算复杂性、密码学、计算几何、算法图论与组合学、计算随机性、计算博弈论和量子计算等。理论计算机科学中最重要的奖项哥德尔奖(Gödel Prize)在ACM计算理论年会和自动机、语言与程序设计国际研讨会 International Colloquium on Automata,Languages and ProgrammingICALP)上交替颁布。本年度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