February 2, 2017: Seminar - Xiaorui Sun: "Algorithmic Design for Massive Data"


Algorithmic Design for Massive Data

Xiaorui Sun
Simons Institute for Theory of Computing
February 2, 2017
11:00 a.m., Room 1000 SEO


The modern era is undergoing an explosive growth in the amount of available data, 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 first talk about algorithm design in massively parallel computing models. I will describe new algorithmic techniques to solve inherently sequential dynamic programming problems under this models. The new parallel algorithms are near-optimal for a variety of classic dynamic programming problems, including longest increasing subsequence, optimal binary search tree, and weighted interval scheduling.

Secondly, I will talk about algorithms for reconstructing underlying structure by sampling from large data. I will describe a density estimation framework based on piecewise polynomial approximation of probability distributions. The framework yields efficient density estimation algorithms for a wide range of structured distributions that achieve the required estimation accuracy with near-optimal data usage.


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.

Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
Helping Women Faculty Advance
Funded by NSF