Chakrabarti's research in complexity theory focused on the theory of lower bounds, which are provable limitations on our ability to minimize resources in solving computational problems. Typical resources of interest include computational time, space and inter-computer communication, the latter being a primary focus of Chakrabarti's work. A short while before joining Dartmouth he and others introduced the notion of information complexity which measures the cost of communication using information theoretic ideas originally developed by Shannon. The advantage is that this new measure is amenable to mathematical analysis and can often be related to the traditional measure of number of bits communicated.
Chakrabarti and others used the information complexity technique to show optimal communication lower bounds for the problem of multiparty SET-DISJOINTNESS [2]. This lower bound has a significant consequence in the field of memory-efficient data stream computations: it can be shown to imply optimal space lower bounds on single pass and multipass algorithms for computing frequency moments.
Chakrabarti, along with a coauthor, also gave the first nontrivial lower bound for high dimensional approximate nearest neighbour searching that works even in the case of randomized algorithms [3]. He also developed an algorithm to match the lower bound on the hypercube, thereby proving the optimality of both bounds. These results close a long line of research work spanning a decade and involving over two dozen researchers worldwide. Chakrabarti is now focusing on extending the results to more challenging metric spaces and computational models.
A secondary research activity has been developing approximation algorithms for NP-hard optimization problems. In this area, Chakrabarti has helped develop the first constant-factor approximation algorithms for the unsplittlable flow problem (a basic problem in network optimization) on line and ring networks [1]. The techniques developed there were subsequently used by other researchers to extend the result to trees. This work also addressed the unsplittable flow problem on expander graphs.