Department of
Applied
Mathematics

Parameterized Streaming Algorithms

Rajesh Chitnis

Abstract

The classical approach for designing algorithms measures the time complexity only as a measure of the input size. In the 90's, Downey and Fellows proposed a fine-grained approach for NP-hard problems: one or more parameters of the input instance are defined, and we investigate the effect of these parameters on the running time. The goal is to design algorithms that work efficiently if the parameters of the input instance are small, even if the size of the input is large. Formally, a problem is said to be fixed-parameter tractable (FPT) with respect to a parameter k if the problem can be solved in time f(k)n^{O(1)}, where f is a computable function and n is the input size. This active area has seen many new developments over the last few years. In particular, I will describe some of my work which combines FPT algorithms with other areas of theoretical computer science such as (polytime) approximation algorithms, algorithmic game theory, social networks, etc.

Given that the paradigm of fine-grained analysis has worked out quite well for the TIME resource, it seems natural to also consider such a fine-grained approach for the SPACE resource. I will present some of my recent work which introduced the area of parameterized streaming algorithms. Through the examples of the Max Matching and Min Vertex Cover problems, I will describe optimal streaming algorithms in various streaming models such as insertion-only, promised and general insertion-deletion.

No prior background will be assumed.