Recently, Peilin Zhong, undergraduate from Yao Class, had his paper “Optimal Principal Component Analysis in Distributed and Streaming Models” accepted at STOC 2016 (48th Annual Symposium on the Theory of Computing) and presented his research at this conference. His work is joint with Christos Boutsidis and David P. Woodruff. It’s the first time that an undergraduate from China has published a paper at STOC. This is even rare for the undergraduates in leading universities like MIT and Princeton.
This paper studies the Principal Component Analysis (PCA) problem in distributed and streaming models of computation. PCA can be used as one of the most important data analysis tools in machine learning and data mining. In his paper, near optimal communication-efficient PCA protocols in distributed models and near optimal low-space streaming PCA algorithms in streaming models are proposed. They separate the dependence of accuracy parameter from the highest order term of the computation complexity they mainly focused on. These algorithms have profound influences on high precision PCA in both theoretical and practical ways.
Peilin was enrolled into a course named “Algorithms and Models for Big Data” when he was junior. The course provided him with access to PCA and encouraged his deeper interest in this field, which later resulted in several papers supervised by Dr. David P. Woodruff. This represents another achievement made by Yao Class students. Until June, 2016, Yao Class students have published 132 papers at world-class conferences (e.g. STOC、SOSP、COLT 、RECOMB、CCC、CVPR、AAAI, etc.) and journals in computer science, among which, 99 papers were first-authored or correspondence-authored by Yao Class students. And 31 students in total presented their papers at the conferences abroad.
The Annual ACM Symposium on Theory of Computing (STOC) is a top and high-profile academic conference in the field of theoretical computer science, and is considered as the most difficult conference because of its paper qualities and acceptance rate. The Symposium is sponsored by SIGACT (the ACM Special Interest Group on Algorithms and Computation Theory) and covers a wide range of topics from algorithms and data structures, complexity theory, cryptography, computational geometry, algorithmic graph theory to random computing, computational game theory and quantum computing. The Gödel Prize for outstanding papers in theoretical computer science is presented alternately at STOC and at the International Colloquium on Automata, Languages and Programming (ICALP). STOC 2016 was held in Cambridge, MA, USA with 92 papers accepted, and brought together more than 200 scholars from 22 countries across the world.
(By Yuying Chang)
