Colloquium Details
Sublinear Algorithms for Massive Datasets
Speaker: Erik Waingarten, Stanford University
Location: Online
Date: March 9, 2021, noon
Host: Richard Cole
Synopsis:
Erik Waingarten is an NSF Postdoctoral Fellow at Stanford University's Computer Science department. Prior to that, he was a research fellow at the Simons Institute for the Theory of Computing. He obtained his PhD from Columbia University, where he was advised by Xi Chen and Rocco Servedio. He is interested in the design and analysis of algorithms for massive datasets, with a particular focus on the interplay of high-dimensional geometry, sketching, and property testing.
Speaker Bio:
The proliferation of massive data systems poses a unique challenge for algorithms research. In this modern era, the classical theory of algorithms is often insufficient, and our goal is to develop the theory of sublinear computation.
This talk will cover various scenarios where the resources used by an algorithm (running time, memory, number of measurements, ... etc) should be significantly smaller than the input size. We will spend most of the time on sublinear time algorithms for similarity search in high-dimensional spaces and sublinear space algorithms for the optimal transport problem, where we will present new algorithmic and analytical techniques for tackling these questions. A central theme throughout the talk is the notion of randomized space partitions, and how they lead to algorithms which are simple, have provable guarantees, and are extremely useful.