CS Colloquium Speaker Huacheng Yu, Princeton University Host: Zeev Dvir Date: Thursday, March 4 Time: 12:30pm EST Event page: [ https://www.cs.princeton.edu/events/26051 | https://www.cs.princeton.edu/events/26051 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_pNvnCKFHS_qoXLEEOSMOwA | https://princeton.zoom.us/webinar/register/WN_pNvnCKFHS_qoXLEEOSMOwA ] Title: Data Structures and Algorithms in Sublinear Computation Abstract: 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. 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.