Interactive clustering. Manuscript.
This paper studies the clustering framework proposed in [Balcan, Blum'08]. In this framework we assume that a given set of m points belongs to k target clusters and each cluster is defined by some concept in a concept class C. The goal of the clustering algorithm is to interact with the user and figure out the target clustering. This paper gives a simple query-efficient algorithm to cluster any concept class in this model. We also study two natural generalizations of the original model.

Online stochastic optimization in the large: Application to kidney exchange. With Tuomas Sandholm. IJCAI 2009.
This paper studies trajectory-based online algorithms for solving large stochastic programs. We apply these algorithms to match patients in large kidney exchanges.

Decision trees for entity identification: Approximation algorithms and hardness results. With Venkatesan Chakaravarthy, Vinayaka Pandit, Sambuddha Roy and Mukesh Mohania. PODS 2007.
Consider the following problem: Given an input table containing information about a set of entities over a fixed set of attributes and a probability distribution over the entities, construct a decision tree that identifies each entity unambiguously by testing the attribute values such that the average number of tests is minimized. Building on prior work ([Adler, Heeringa'05]) we study the general version of the problem involving arbitrary input tables and arbitrary probability distribution over the set of entities. We consider a natural greedy algorithm and prove an approximation guarantee of O(r_K log(N)), where N is the number of entities, K is the maximum number of distinct values of an attribute, and r_K is a suitably defined Ramsey number. In addition, our analysis indicates a possible way of resolving a Ramsey theoretic conjecture by Erdos.

Image modeling using tree structured conditional random fields. With Aakanksha Gagrani and Balaraman Ravindran. IJCAI 2007.