{"id":144938,"date":"2015-04-09T00:14:21","date_gmt":"2015-04-09T00:14:21","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/group\/foundations\/"},"modified":"2023-10-31T02:50:12","modified_gmt":"2023-10-31T09:50:12","slug":"foundations","status":"publish","type":"msr-group","link":"https:\/\/www.microsoft.com\/en-us\/research\/theme\/foundations\/","title":{"rendered":"Algorithms | India"},"content":{"rendered":"<section class=\"mb-3 moray-highlight\">\n\t<div class=\"card-img-overlay mx-lg-0\">\n\t\t<div class=\"card-background  has-background- card-background--full-bleed\">\n\t\t\t<img loading=\"lazy\" decoding=\"async\" width=\"2560\" height=\"960\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2019\/12\/Theme_ltblue_AlgorithmDataSci_12_2019_1920x720-scaled.jpg\" class=\"attachment-full size-full\" alt=\"Theme: Algorithms and Data Science\" style=\"object-position: 79% 51%\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2019\/12\/Theme_ltblue_AlgorithmDataSci_12_2019_1920x720-scaled.jpg 2560w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2019\/12\/Theme_ltblue_AlgorithmDataSci_12_2019_1920x720-300x113.jpg 300w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2019\/12\/Theme_ltblue_AlgorithmDataSci_12_2019_1920x720-1024x384.jpg 1024w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2019\/12\/Theme_ltblue_AlgorithmDataSci_12_2019_1920x720-768x288.jpg 768w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2019\/12\/Theme_ltblue_AlgorithmDataSci_12_2019_1920x720-1536x576.jpg 1536w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2019\/12\/Theme_ltblue_AlgorithmDataSci_12_2019_1920x720-2048x768.jpg 2048w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2019\/12\/Theme_ltblue_AlgorithmDataSci_12_2019_1920x720-1920x720.jpg 1920w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2019\/12\/Theme_ltblue_AlgorithmDataSci_12_2019_1920x720-1600x600.jpg 1600w\" sizes=\"(max-width: 2560px) 100vw, 2560px\" \/>\t\t<\/div>\n\t\t<!-- Foreground -->\n\t\t<div class=\"card-foreground d-flex mt-md-n5 my-lg-5 px-g px-lg-0\">\n\t\t\t<!-- Container -->\n\t\t\t<div class=\"container d-flex mt-md-n5 my-lg-5 \">\n\t\t\t\t<!-- Card wrapper -->\n\t\t\t\t<div class=\"w-100 w-lg-col-5\">\n\t\t\t\t\t<!-- Card -->\n\t\t\t\t\t<div class=\"card material-md-card py-5 px-md-5\">\n\t\t\t\t\t\t<div class=\"card-body \">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/lab\/microsoft-research-india\/\" class=\"icon-link icon-link--reverse mb-2\" data-bi-cN=\"Return to Microsoft Research Lab - India\">\n\t\t\t\t\t\t\t\t\t<span class=\"c-glyph glyph-chevron-left\" aria-hidden=\"true\"><\/span>\n\t\t\t\t\t\t\t\t\tReturn to Microsoft Research Lab &#8211; India\t\t\t\t\t\t\t\t<\/a>\n\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\n\n<h1 class=\"wp-block-heading h2\" id=\"algorithms-india\">Algorithms | India<\/h1>\n\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/div>\n<\/section>\n\n\n\n\n\n<h2 class=\"wp-block-heading\" id=\"algorithms-research\">Algorithms research<\/h2>\n\n\n\n<p>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\u2019 work spans and has led to seminal contributions in a broad spectrum of areas such as discrepancy theory (Kadison-Singer <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/blog\/conjecture-proof-leads-to-plya-prize\/\" target=\"_blank\" rel=\"noreferrer noopener\">Conjecture Proof Leads to P\u00f3lya Prize<\/a>), number theory (<a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/en.wikipedia.org\/wiki\/AKS_primality_test\" target=\"_blank\" rel=\"noreferrer noopener\">AKS primality test<\/a>), and high-dimensional geometry (<a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/www.sigact.org\/prizes\/knuth.html\" target=\"_blank\" rel=\"noreferrer noopener\">Ravindran Kannan wins Knuth Prize<\/a> 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 <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/project\/ezpc-easy-secure-multi-party-computation\/\">EzPC<\/a> 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.<\/p>\n\n\n\n<p>Our current focus areas are:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Our current focus areas are:<\/li>\n\n\n\n<li>Theory and Foundations of Machine Learning<\/li>\n\n\n\n<li>Fairness in Machine Learning<\/li>\n\n\n\n<li>Efficient Real-World Algorithms for Similarity Search<\/li>\n\n\n\n<li>Cryptography: Theory and Practice<\/li>\n<\/ul>\n\n\n\n<p>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\u2019s focus areas.<\/p>\n\n\n","protected":false},"excerpt":{"rendered":"<p>The Algorithms and Data Science research at MSR India is focused on developing mathematical models under which simple algorithms (often ones used widely in practice) have provable guarantees of time and space.<\/p>\n","protected":false},"featured_media":629109,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_group_start":"","footnotes":""},"research-area":[13561,13556,13546],"msr-group-type":[243688],"msr-locale":[268875],"msr-impact-theme":[],"class_list":["post-144938","msr-group","type-msr-group","status-publish","has-post-thumbnail","hentry","msr-research-area-algorithms","msr-research-area-artificial-intelligence","msr-research-area-computational-sciences-mathematics","msr-group-type-theme","msr-locale-en_us"],"msr_group_start":"","msr_detailed_description":"","msr_further_details":"","msr_hero_images":[],"msr_research_lab":[199562],"related-researchers":[{"type":"user_nicename","display_name":"Nishanth Chandran","user_id":33084,"people_section":"FTEs","alias":"nichandr"},{"type":"user_nicename","display_name":"Amit Deshpande","user_id":30988,"people_section":"FTEs","alias":"amitdesh"},{"type":"user_nicename","display_name":"Ankit Garg","user_id":36107,"people_section":"FTEs","alias":"garga"},{"type":"user_nicename","display_name":"Navin Goyal","user_id":33063,"people_section":"FTEs","alias":"navingo"},{"type":"user_nicename","display_name":"Divya Gupta","user_id":37766,"people_section":"FTEs","alias":"digup"},{"type":"user_nicename","display_name":"Neeraj Kayal","user_id":33076,"people_section":"FTEs","alias":"neeraka"},{"type":"user_nicename","display_name":"Ravishankar Krishnaswamy","user_id":33330,"people_section":"FTEs","alias":"rakri"},{"type":"user_nicename","display_name":"Satya Lokam","user_id":33532,"people_section":"FTEs","alias":"satya"},{"type":"user_nicename","display_name":"Harsha Simhadri","user_id":36146,"people_section":"FTEs","alias":"harshasi"},{"type":"guest","display_name":"Prashanth Reddy  Amireddy","user_id":800605,"people_section":"Currrent Research Fellows ","alias":""},{"type":"guest","display_name":"Shikhar Jaiswal","user_id":800608,"people_section":"Currrent Research Fellows ","alias":""},{"type":"guest","display_name":"Neel Karia","user_id":800611,"people_section":"Currrent Research Fellows ","alias":""},{"type":"guest","display_name":"Shivam Garg","user_id":800653,"people_section":"RF Alumni","alias":""},{"type":"guest","display_name":"Prachi Goyal","user_id":800650,"people_section":"RF Alumni","alias":""},{"type":"guest","display_name":"Deep Karkhanis","user_id":800659,"people_section":"RF Alumni","alias":""},{"type":"guest","display_name":"Tarun Kathuria","user_id":800662,"people_section":"RF Alumni","alias":""},{"type":"guest","display_name":"Sai Sandeep","user_id":800656,"people_section":"RF Alumni","alias":""},{"type":"guest","display_name":"Kulin Shah","user_id":800665,"people_section":"RF Alumni","alias":""},{"type":"guest","display_name":"Abhishek Shetty","user_id":800668,"people_section":"RF Alumni","alias":""},{"type":"guest","display_name":"Kiran Shiragur","user_id":800671,"people_section":"RF Alumni","alias":""}],"related-publications":[418814,479862,352991,317237,356456,356459,255654,324395,168200,255615,255606,255639,255522,255549,255558,324209,255669,167763,168434,168435,255567,168057,255576,168322,167501,168199,168290,168204,168321,167491,167492,168840,168055,168201,167757,167758,167760,168208,167759,168052,168291,168206,168205,168207,167756,168202,168292,167764,168222,167761,167762,164485,164627,164716,167765,165462,168209,168210,168236,168287,168211,168213,168212,168214,168215,168216,168217,168218,168219,168220,168221,747766,800590,800596,972993],"related-downloads":[],"related-videos":[],"related-projects":[],"related-events":[],"related-opportunities":[],"related-posts":[],"tab-content":[],"msr_impact_theme":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-group\/144938"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-group"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-group"}],"version-history":[{"count":20,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-group\/144938\/revisions"}],"predecessor-version":[{"id":1004205,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-group\/144938\/revisions\/1004205"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/629109"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=144938"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=144938"},{"taxonomy":"msr-group-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-group-type?post=144938"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=144938"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=144938"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}