Thursday, May 30, 2024, 3pm

Sketching refers to a wide variety of techniques to compress large datasets into much smaller forms that can be efficiently processed to answer questions about the original dataset. Over the past few decades, sketching has emerged as a key tool to efficiently handle large datasets in majorly three settings: (i) the Classic setting, in which the dataset is given to us and we want to solve a problem as quickly as possible, (ii) the Streaming setting, in which the underlying dataset is defined by a large stream of updates and we want to compute interesting properties of the dataset using a small amount of space, and (iii) the Distributed setting, in which the dataset of interest is split among multiple servers and we want protocols that use a small amount of communication among servers to solve problems of interest on the underlying dataset.

Each of the above settings presents a different challenge with regard to the measure of efficiency we are interested in. In this thesis, we study sketching algorithms in these three settings for a variety of problems. While the techniques required to obtain our algorithms differ across problems and settings, the underlying idea of (possibly randomized) data compression to convert the original large dataset into a much smaller form is a key ingredient behind all of the results in this thesis.

Thesis Committee:
David P. Woodruff (Chair)
Pravesh K. Kothari
Richard Peng
Rasmus Pagh (University of Copenhagen)

In Person and Zoom Participation.  See announcement.

Event Type: Thesis Orals
Room Number: In Person and Virtual - ET
Building: Reddy Conference Room, Gates HIllman 4405 and Zoom
Speaker's Name: PRANEETH KACHAM
Speaker Website: www.praneethkacham.com
Speaker's Professional Title: Ph.D. Candidate, Computer Science Department, Carnegie Mellon University
Talk Title: On Efficient Sketching Algorithms
Event Poster Title: Poster
Event Poster URL: www.cs.cmu.edu…
For More Information: matthewstewart@cmu.edu
Affiliations: Computer Science Department (CSD)
Organization(s): School of Computer Science