March 15, 2017: Seminar - Rajesh Chitnis: "A Fine-Grained Approach for Designing (Time and Space) Efficient Algorithms"


A Fine-Grained Approach for Designing (Time and Space) Efficient Algorithms

Rajesh Chitnis
March 15, 2017
11:00 a.m., Room 1000 SEO


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.

In the first part of the talk, I will give a brief overview of the current state-of-the-art research in FPT algorithms. 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 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. In the second part of the talk, I will present my recent work which introduced the area of parameterized streaming algorithms. Through the examples of the Min Vertex Cover problem, I will describe optimal streaming algorithms in various streaming models such as insertion-only, promised and general insertion-deletion.


Rajesh Chitnis is a postdoctoral fellow in the Faculty of Mathematics and Computer Science at Weizmann Institute of Science, Israel. He obtained his PhD from the University of Maryland in 2014. He is interested in theoretical computer science, in particular on designing optimal fine-grained algorithms for graph problems. He has been a recipient of several honors including Simons Award for Graduate Students in Theoretical Computer Science (2013-15), Best Paper in European Symposium on Algorithms (ESA) 2013, Larry S. Davis Doctoral Dissertation Award from University of Maryland (2014), and Board of Visitor?s Award for Outstanding Graduate Student at University of Maryland (2014).

Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF