姚班本科生在計(jì)算機(jī)科學(xué)頂級(jí)會(huì)議STOC上發(fā)表論文

清華新聞網(wǎng)6月22日電 近日，清華大學(xué)交叉信息院計(jì)算機(jī)科學(xué)實(shí)驗(yàn)班（姚班）計(jì)科20班本科生鐘沛林以第一作者身份撰寫(xiě)的論文《分布流模型中的最優(yōu)主成分分析》（“Optimal Principal Component Analysis in Distributed and Streaming Models”）被計(jì)算機(jī)科學(xué)領(lǐng)域頂級(jí)國(guó)際會(huì)議第48屆ACM計(jì)算理論年會(huì)（STOC 2016，48th Annual Symposium on the Theory of Computing）接收，并于美國(guó)東部時(shí)間6月19日赴美作大會(huì)宣講。這是首次有中國(guó)籍本科生在STOC會(huì)議上發(fā)表第一作者論文，即便在美國(guó)麻省理工學(xué)院、普林斯頓大學(xué)等國(guó)際一流高校本科生中也極為罕見(jiàn)。

 
鐘沛林參加STOC2016并作大會(huì)論文宣講。

主成份分析（Principal Components Analysis，PCA）是在機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘中最重要的數(shù)據(jù)分析方法之一。在上述論文工作中，鐘沛林提出了在通信復(fù)雜度上近乎最優(yōu)的分布式PCA算法以及在空間復(fù)雜度上接近最優(yōu)的PCA流算法。該算法在通信復(fù)雜度和流算法的空間復(fù)雜度方面可以做到與所需精確度參數(shù)無(wú)關(guān)，因此比之前的算法更有效，適用性更寬泛，對(duì)于精度要求高的場(chǎng)合具有重要的理論和實(shí)際意義。該工作是鐘沛林與IBM研究院戴維·沃道夫（David P. Woodruff）研究員合作完成的。

鐘沛林最初是在大三時(shí)姚班專(zhuān)業(yè)課《大數(shù)據(jù)算法與模型》上接觸到分布式PCA問(wèn)題，對(duì)此課題產(chǎn)生了濃厚的興趣，決定將工作重心放在該項(xiàng)目上，并在戴維·沃道夫研究員的進(jìn)一步指導(dǎo)下完成相關(guān)論文。這也是姚班學(xué)生本科階段參與科研工作的又一突出成果。

截止到2016年6月，姚班學(xué)生在讀期間在計(jì)算機(jī)領(lǐng)域國(guó)際頂級(jí)會(huì)議和期刊共發(fā)表論文132篇，如ACM計(jì)算理論國(guó)際年會(huì)（STOC）、ACM操作系統(tǒng)原理會(huì)議（SOSP）、IEEE計(jì)算復(fù)雜性國(guó)際會(huì)議（CCC）、IEEE國(guó)際計(jì)算機(jī)視覺(jué)與模式識(shí)別會(huì)議（CVPR）、美國(guó)人工智能協(xié)會(huì)國(guó)際年會(huì)（AAAI）等，其中計(jì)算機(jī)科學(xué)實(shí)驗(yàn)班學(xué)生為論文通訊作者或主要完成人的有99篇，并累計(jì)有31位學(xué)生出國(guó)參會(huì)并作論文宣講。

ACM計(jì)算理論年會(huì)（STOC）是理論計(jì)算機(jī)科學(xué)領(lǐng)域最頂級(jí)的國(guó)際會(huì)議，在整個(gè)計(jì)算機(jī)科學(xué)領(lǐng)域享有崇高的聲望，屬于公認(rèn)難度最高的會(huì)議之一。該會(huì)議由ACM中的算法和計(jì)算理論興趣小組（Special Interest Group in Algorithms and Computation Theory，SIGACT）提供資助，歷年會(huì)議涵蓋的領(lǐng)域十分廣泛，包括算法和數(shù)據(jù)結(jié)構(gòu)、計(jì)算復(fù)雜性、密碼學(xué)、計(jì)算幾何、算法圖論與組合學(xué)、計(jì)算隨機(jī)性、計(jì)算博弈論和量子計(jì)算等。理論計(jì)算機(jī)科學(xué)中最重要的獎(jiǎng)項(xiàng)哥德?tīng)柂?jiǎng)（Goedel Prize）在A(yíng)CM計(jì)算理論年會(huì)和自動(dòng)機(jī)、語(yǔ)言與程序設(shè)計(jì)國(guó)際研討會(huì) （International Colloquium on Automata, Languages and Programming，ICALP）上交替頒布。本年度STOC 2016在美國(guó)馬薩諸塞州劍橋市舉辦，共接收論文92篇，吸引來(lái)自全球22個(gè)國(guó)家和地區(qū)的200多名學(xué)者、近百個(gè)科研機(jī)構(gòu)參會(huì)。

論文鏈接：
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

供稿：交叉信息研究院 編輯：李華山