<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><div class=""><span class="" style="font-size: 14px;"><b class="" style="font-family: LucidaGrande; background-color: rgba(255, 255, 255, 0);"><u class="">Department of Computer Science </u></b><b class="" style="background-color: rgba(255, 255, 255, 0); font-family: LucidaGrande;"><u class="">Seminar</u></b></span></div></div><div class="" style="font-family: LucidaGrande;"><span class="" style="background-color: rgba(255, 255, 255, 0);"><br class=""></span></div><div class=""><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">Wednesday, March 29, 2017</span></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">4:00 pm <font color="#e32400" class="">(Please note non-standard time)</font></span></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">Ryerson 251 </span></div><div class="" style="font-family: LucidaGrande;"><br class=""></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">Xiaorui Sun</span></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">(Simons Institute for the Theory of Computing at UC Berkeley)</span></div><div class="" style="font-family: LucidaGrande;"><br class=""></div><div class=""><span class="" style="font-size: 14px;"><span class="" style="font-family: LucidaGrande;">Title: </span><span class="" style="font-family: LucidaGrande;">Algorithm design for massive data</span><br class="gmail-m_4827095062818533991gmail_msg"><br class="gmail-m_4827095062818533991gmail_msg"><span class="" style="font-family: LucidaGrande;">Abstract: </span></span></div><div class=""><font face="LucidaGrande" class=""><span class="" style="font-size: 14px;">The modern era is undergoing an explosive growth in the amount of data available, and quadratic or even linear-time algorithms can fall short of efficiency. Solving problems in this new scenario has become a major challenge for the computer science community. In this talk, I will highlight how the algorithmic perspective brings novel insights and leads to efficient methods for important problems in the big data environment.<br class=""><br class="">I will talk about new algorithms for learning and property testing of large data using random samples. First, I will present a density estimation framework based on the piecewise polynomial approximation of probability distributions. The framework yields efficient density estimation algorithms for a wide range of structured distributions with near-optimal data usage. Second, I will show a new property testing algorithm for the graph isomorphism problem with a near-optimal number of edge queries. A primary tool that enables our result is a new algorithm for testing the closeness of two unknown distributions using probability-revealing samples.<br class=""><br class="">I will also briefly describe my recent work on algorithm design in massively parallel computing models.<br class=""><br class=""></span></font></div><div class=""><font face="LucidaGrande" class=""><span class=""><span class=""><br class=""><span class="" style="font-size: 14px;">-----</span><br class=""></span><span class="" style="font-size: 14px;"> </span><span class="" style="font-size: 14px;"><br class=""></span></span></font><span class="" style="font-size: 14px;"><span class="" style="font-family: 'Lucida Grande';">Bio: </span></span><span class="" style="font-family: LucidaGrande; font-size: 14px;">Xiaorui Sun is a computer scientist focused on algorithmic foundations of massive data. His research interest lies in massively parallel computing, sublinear algorithms, algorithmic graph theory and machine</span><span class="" style="font-family: LucidaGrande; font-size: 14px;"> learning. Xiaorui graduated from Columbia University in 2016, under the supervision of Xi Chen. Currently, he is a Google Research Fellow at the Simons Institute for the Theory of Computing at UC Berkeley.</span></div><div class=""><div class=""><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;"><br class=""></span></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;"><br class=""></span></div></div><div class="" style="font-family: LucidaGrande;"><span class="" style="font-size: 14px;">Host: Ketan Mulmuley</span></div></div></div></body></html>