Home Research Publications Teaching

Research
I am broadly interested in theoretical computer science and machine learning. Most of my research is in one of the following directions
• Representation Learning: Modern machine learning algorithms such as deep learning try to automatically learn useful hidden representations of documents, images or other forms of data. We try to find out what structures are useful, and how to design provable algorithms for these hidden structures.
• Non-convex Optimization: Most of the machine learning problems can be formalized as non-convex optimization problems. However, in the worst case non-convex optimization is NP-hard. We try to identify properties of the problems that make them easy'' to solve, and design more efficient algorithms.
• Tensor Decompositions: Tensors are high order generalizations of matrices. Tensor decomposition is a powerful algebraic tool that can be used to learn many latent variable models. We try to design faster, more robust algorithms for tensor decomposition, and apply them to new problems.
I have also worked on other topics such as approximation algorithms and complexity of financial derivatives.
Representation Learning
In representation learning, we have worked on algorithms for problems such as topic models, sparse coding, social networks and noisy-or networks. I hope to work on representation learning for more applications, including deep representations.

 Online Service with Delay with Yossi Azar, Arun Ganesh and Debmalya Panigrahi. In STOC 2017. In this paper, we introduce the online service with delay problem. In this problem, there are $n$ points in a metric space that issue service requests over time, and a server that serves these requests. The goal is to minimize the sum of distance traveled by the server and the total delay in serving the requests. This problem models the fundamental tradeoff between batching requests to improve locality and reducing delay to improve response time, that has many applications in operations management, operating systems, logistics, supply chain management, and scheduling. Our main result is to show a poly-logarithmic competitive ratio for the online service with delay problem. This result is obtained by an algorithm that we call the preemptive service algorithm. The salient feature of this algorithm is a process called preemptive service, which uses a novel combination of (recursive) time forwarding and spatial exploration on a metric space. We hope this technique will be useful for related problems such as reordering buffer management, online TSP, vehicle routing, etc. We also generalize our results to k >1 servers. Towards a better approximation for sparsest cut? with Sanjeev Arora and Ali Kemal Sinop. In FOCS 2013 We give a new (1+eps)-approximation for sparsest cut problem on graphs where small sets expand significantly more than the sparsest cut (sets of size n/r expand by a factor \sqrt{\log n\log r} bigger, for some small r; this condition holds for many natural graph families). We give two different algorithms. One involves Guruswami-Sinop rounding on the level-r Lasserre relaxation. The other is combinatorial and involves a new notion called Small Set Expander Flows (inspired by the expander flows of ARV) which we show exists in the input graph. Both algorithms run in time 2^{O(r)} poly(n). We also show similar approximation algorithms in graphs with genus g with an analogous local expansion condition. This is the first algorithm we know of that achieves (1+eps)-approximation on such general family of graphs. Computational Complexity and Information Asymmetry in Financial Products with Sanjeev Arora, Boaz Barak and Markus Brunnermeier. In ICS 2010 A short version appeared in Communications of the ACM, 2011 Issue 5. Full text PDF See some blog comments on this paper: Intractability Center, Freedom to Tinker, Boing Boing, Daily Kos, In Theory, Healthy Algorithms, Lipton's blog We put forward the issue of Computational Complexity in the analysis of Financial Derivatives, and show that there is a fundamental difficulty in pricing financial derivatives even in very simple settings. This is still a working paper. The latest version (updated Jan. 2012) can be found here: Computational Complexity and Information Asymmetry in Financial Products New Tools for Graph Coloring with Sanjeev Arora, In APPROX 2011 We explore the possibility of better coloring algorithm using the new concept threshold rank. We are able to analyze high level Lasserre Relaxations for low threshold rank graphs and distance transitive graphs, and our algorithm makes significantly better progress (towards O(log n) coloring) in these cases compared to previous algorithms (where the number of colors is polynomial). We also purpose a plausible conjecture, that if true would yield good sub-exponential time algorithm for graph coloring. New Algorithms for Learning in Presence of Errors with Sanjeev Arora, In ICALP 2011 We give new algorithms for a variety of randomly-generated instances of computational problems using a linearization technique that reduces to solving a system of linear equations. Our techniques can be applied to the low noise case of the well-known LWE (Learning With Errors) problem, giving a slightly subexponential time algorithm which suggests known hardness results are almost tight. New Results on Simple Stochastic Games with Decheng Dai. In ISAAC 2009 We give a new algorithm for Simple Stochastic Games when the number of RANDOM vertices is small. We also show that coarse approximation is as hard as fine approximation for Simple Stochastic Games.