New Directions in Streaming Algorithms
, MIT CSAIL
Date: Friday, May 17, 2019
Time: 12:00 PM to 1:00 PM
Location: 32- G463 (Star)
Event Type: Thesis Defense
Host: Piotr Indyk, MIT CSAIL
Contact: Rebecca Yadegar, email@example.com
Speaker URL: None
TALK: Thesis Defense: Ali Vakilian:New Directions in Streaming Algorithms
Abstract: Large volumes of available data have led to the emergence of new computational models for data analysis. One such model is captured by the notion of streaming algorithms: given a sequence of N items, the goal is to compute the value of a given function of the input items by a small number of passes and using a sublinear amount of space in N. Streaming algorithms have applications in many areas such as networking and large scale machine learning. Despite a huge amount of work on this area over the last two decades, there are multiple aspects of streaming algorithms that remained poorly understood, such as (a) streaming algorithms for combinatorial optimization problems and (b) incorporating modern machine learning techniques in the design of streaming algorithms.
In this talk I will start by describing streaming algorithms for set cover and maximum coverage, two classic problems in combinatorial optimization. I will give (essentially) optimal algorithms for both of these problems. Next, I will show how to augment classic streaming algorithms (Count-Min and Count-Sketch) with a machine learning oracle in order to improve their space-accuracy tradeoffs. The new algorithms combine the benefits of machine learning with the formal guarantees available through algorithm design theory.
Thesis Committee: Erik D Demaine, Piotr Indyk and Ronitt Rubinfeld
Algorithms & Theory
Created by Rebecca Yadegar at Wednesday, May 08, 2019 at 6:06 PM.