Algorithms and Data Sciences

“Big Data” is currently an explosive phenomenon, triggered by proliferation of data in ever increasing volumes, rates, and variety. The Big Data revolution changes the perspective of many research areas in how they address both foundational questions and practical applications. In particular, this calls for a paradigm shift in Algorithms and the underlying mathematical techniques. While the impact of big data on the field of computing seems recent, foundations for algorithms on big data, especially based on random sampling on the fly, have been laid in the 90’s by theoretical computer scientists including those currently at MSR India. The goal for the research area of Algorithms and Data Sciences is to build on these foundational strengths and address the state of the art challenges in big data that could lead to practical impact. We see our efforts as a bridge between traditional Algorithms area, which focusses on well-structured problems and has a host of ideas and techniques to offer, and Statistics, Machine Learning and Optimization areas which have interesting and relevant models and problems.

Some research themes of our focus include

• Massive Matrix Computation, including randomized and distributed PCA-like problems
• Low rank approximations to Tensors
• Streaming Algorithms
• Property Testing
• Clustering
• Large Scale (distributed, stochastic) Optimization