More about HKUST
Designing Algorithms for Massive Graphs
Speaker: Dr. Yu Chen EPFL Title: "Designing Algorithms for Massive Graphs" Date: Monday, 11 March 2024 Time: 4:00pm - 5:00pm Venue: Lecture Theater F (Leung Yat Sing Lecture Theater), near lift 25/26 HKUST 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 have a broad interest in various aspects of theoretical computer science and mathematics. Currently, I focus on graph algorithms, especially sublinear algorithms on graph and graph sparsification problems. I'm a recipient of the Morris and Dorothy Rubinoff Award at University of Pennsylvania and the Best Paper award at SODA'19.