New Directions in Streaming Algorithms

Speaker: Ali Vakilian , MIT CSAIL

Date: Friday, May 17, 2019

Time: 12:00 PM to 1:00 PM

Public: Yes

Location: 32- G463 (Star)

Event Type: Thesis Defense

Room Description:

Host: Piotr Indyk, MIT CSAIL

Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: 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

Research Areas:
Algorithms & Theory

Impact Areas:

This event is not part of a series.

Created by Rebecca Yadegar Email at Wednesday, May 08, 2019 at 6:06 PM.