ICE-TCS Lectures Series - Magnús Már Halldórsson - Streaming algorithms and communication complexity

ICE-TCS-logo-vertical-basic-100pxThe next ICE-TCS  talk will be delivered on Friday, 17 December, by Magnús Már Halldórsson (Reykjavik University). The talk, which is entitled Streaming algorithms and communication complexity, will be held at 14:00 in room M1.05 at the new premises of Reykjavik University in Nauthólsvík.

Everyone is welcome.



We introduce in this talk two models of computations that have received increased attention in recent years. No prior knowledge of
these or other complexity/algorithmic concepts is assumed. In the streaming model of computation for graph problems, edges are
presented sequentially in the form of a data stream, and the (algorithmic) objective is to compute a good near-optimal solution
using working space significantly less than the size of the data stream.  The motivation for streaming comes from practical
applications of managing massive data sets such as, e.g., real-time network traffic, on-line auctions, and telephone call records.  These data sets are huge and arrive at very high rate, making it impossible to store more than a small part of the input.

Communication complexity, which was introduced by Yao in 1979, powerful tool to solve a variety of problems in areas as disparate as
VLSI design, decision trees, data structures, and circuit complexity. It is a game between two parties, Alice and Bob, with unlimited
computing power, that want to compute the value of a function, where Alice knows only one half of the input and Bob the remaining half.  To perform the computation, they are allowed to send messages to each other in order to converge on a shared output. With randomization it suffices that the probability that they output the correct value be at least $2/3$ on any instance.  Their objective is to use as few bits of communication as possible.

As time allows, we will discuss recent results on streaming algorithms for the maximum clique problem. In particular, we show how results from communication complexity imply lower bounds on the space complexity of approximate clique computation in the streaming model.

This is joint work with Mario Szegedy (Rutgers), Xiaoming Sun and Chengu Wang (Tsinghua University).