CS&E Colloquium: Designing Algorithms for Massive Graph

The computer science colloquium takes place on Mondays and Fridays from 11:15 a.m. - 12:15 p.m. This week's speaker, Yu Chen (EPFL), will be giving a talk titled, "Designing Algorithms for Massive Graph".

Abstract

As the scale of the problems we want to solve in real life becomes larger, it is difficult to store the whole input or take a very long time to read the entire input. In these cases, the classical algorithms, even when they run in linear time and linear space, may no longer be feasible options as the input size is too large. To deal with this situation, we need to design algorithms that use much smaller space or time than the input size. We call this kind of algorithm a sublinear algorithm.

My primary research interest is in designing sublinear algorithms for combinatorial problems and proving lower bounds to understand the limits of sublinear computation. I also study graph sparsification problems, which is an important technique for designing sublinear algorithms on graphs. It is usually used as a pre-processing step to speed up algorithms. 

In this talk, I’ll cover some of my work in sublinear algorithms and graph sparsifications. I’ll give more details on my recent works about vertex sparsifiers.

Biography

I'm a postdoc in the theory group at EPFL. I obtained my PhD from University of Pennsylvania, where I was advised by Sampath Kannan and Sanjeev Khanna. Before that, I did my undergraduate study at Shanghai Jiao Tong University. I’m a recipient of the Morris and Dorothy Rubinoff Award at University of Pennsylvania and the Best Paper award at SODA’19.