# 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.