[Colloquium] CS Seminar on March 29: Xiaorui Sun, Simons Institute for the Theory of Computing

[Sandra Wallace via Colloquium]

Department of Computer Science Seminar

Wednesday, March 29, 2017
4:00 pm (Please note non-standard time)
Ryerson 251 

Xiaorui Sun
(Simons Institute for Theory of Computing at UC Berkeley)

Title: Algorithm design for massive data

Abstract: 
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.

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.

I will also briefly describe my recent work on algorithm design in massively parallel computing models.


-----
 
Bio:  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 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.


Host: Ketan Mulmuley


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20170324/d67000fd/attachment.html>