Speaker: **Ali Vakilian, **

PhD student,

Department of Computer Science,

Massachusetts Institute of Technology (MIT)

Title: **Algorithm for Big Data (Streaming Algorithm for The Set Cover Problem)**

Local Organizer: Dr. Ghodsi

Time: Tuesday, Jan. 13, 3:00-4:00 PM

Location: Computer Engineering Department, Sharif University of Technology

Abstract:

I will begin the talk with a brief introduction to Big Data and its algorithmic challenges and opportunities. Next, I will focus on streaming algorithms and in particular designing efficient streaming algorithms for the Set Cover problem. In a recent work with Erik Demaine, Piotr Indyk and Sepideh Mahabadi, We developed the first streaming algorithm and the ?first two-party communication protocol that

uses a constant number of passes/rounds and sublinear space/communication for logarithmic approximation

to the classic Set Cover problem. Specially, for n elements and m sets, our algorithm/

protocol achieves a space bound of O(m \cdot n^\delta log^2 n \log m) (for any \delta > 0) using O(4^(1/\delta))

passes/rounds while achieving an approximation factor of O(4^(1/\delta) log n) in polynomial time. If we

allow the algorithm/protocol to spend exponential time per pass/round, we achieve an approximation

factor of O(4^(1/\delta)). Our approach uses randomization, which we show is necessary: no deterministic

constant approximation is possible (even given exponential time) using o(mn) space. These results

are some of the first on streaming algorithms and efficient two-party communication protocols for

approximation algorithms.

At the end, I will mention some recent follow-up results of this work.