Colloquium Details
Data Structures and Algorithms in Sublinear Computation
Speaker: Huacheng Yu, Princeton University
Location: Online
Date: March 16, 2021, 11:30 a.m.
Host: Oded Regev
Synopsis:
Sublinear algorithms are sustainable under the exponential increase
of data volume and processing speed. Such algorithms use a sublinear amount of
resources, e.g., spending time, space, or communication that is asymptotically
smaller than the input data size. Typical examples include data structures,
which compute query functions of the data in sublinear time, and streaming
algorithms, which make one pass over massive data streams while maintaining a
sublinear-sized memory.
In this talk, I will give an overview of my work in sublinear computation,
focusing on succinct data structures and distributed graph sketching
algorithms. I will first discuss my work on a nearly optimal data structure
for the dictionary problem, for which the textbook solution uses hash tables.
Then, I will talk about detecting the connectivity of graphs using distributed
sketching, and my recent work showing the optimality of a well-known sketching
algorithm (the AGM sketch). I will conclude the talk with discussion on future
directions and my other work in theoretical computer science.
Speaker Bio:
Huacheng Yu is an associate research scholar in the Department of
Computer Science at Princeton University. His research interests include data
structures and streaming algorithms, and other directions in theoretical
computer science such as communication complexity and graph algorithms. Prior
to Princeton, Huacheng was a postdoctoral researcher at Harvard University
hosted by Jelani Nelson and Madhu Sudan. He received his Ph.D. from Stanford
University (advised by Ryan Williams and Omer Reingold) and B.Eng from
Tsinghua University, both in Computer Science.