Parameterized Streaming Algorithms

In today's age of Big Data, we have to deal with inputs so massive that storing them completely in memory is prohibitive. The paradigm of streaming algorithms attempts to deal with this issue by aiming to store a (small) sketch/summary of the input which (approximately) solves the problem at hand. However, even for several simple graph problems, it can be shown that any algorithm which solves these problems exactly needs to store the whole graph in memory. How can we attempt to cope with this intractability? 

Parameterized (time) complexity attempts to give a more fine-grained analysis of the complexity of problems: instead of measuring the running time as a function of only the input size, we analyze the running time with respect to additional parameters. This approach has proven to be highly successful in delineating our understanding of NP-hard problems. Given this success with the TIME resource, it seems but natural to use this approach for dealing with the SPACE resource. Taking inspiration from parameterized (time) complexity, along with my co-authors we have introduced the paradigm of parameterized streaming algorithms.

In this talk, I will describe my ongoing work towards building a theory of parameterized streaming algorithms by two-way flow of ideas between the (seemingly unrelated) areas of parameterized (FPT) algorithms and streaming algorithms. No prior background will be assumed in either streaming algorithms or parameterized (FPT) algorithms.