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.