Algorithms | India

Algorithms research

Since its inception, Microsoft Research India has had a strong focus on theoretical computer science, with the objectives of deepening our understanding of basic computational problems as well as facilitating these scientific advances (when possible) into real-world systems. Our researchers’ work spans and has led to seminal contributions in a broad spectrum of areas such as discrepancy theory (Kadison-Singer Conjecture Proof Leads to Pólya Prize), number theory (AKS primality test), and high-dimensional geometry (Ravindran Kannan wins Knuth Prize for pioneering work on estimating of the volumes of arbitrary high-dimensional convex set), to name a few. Our research has also had substantial impact in enabling new technologies such as EzPC and improving the quality of real-world systems. For instance, our work in Topic Modelling is inspired by the need to cluster entities with no signals for supervision, such as tail queries in advertisement systems, and our work on algorithms for Approximate Nearest Neighbour Search is inspired by the need to build and search through vector indices consisting of trillions of vectors in order to enable semantic search.

Our current focus areas are:

• Our current focus areas are:
• Theory and Foundations of Machine Learning
• Fairness in Machine Learning
• Efficient Real-World Algorithms for Similarity Search
• Cryptography: Theory and Practice

We also actively collaborate with academic institutions in India such as IISc, IIT Madras, IIT Delhi, etc. where our staff offer courses and co-advise students on topics related to the lab’s focus areas.