{"id":199806,"date":"2012-07-10T11:41:07","date_gmt":"2012-07-10T18:41:07","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/events\/msr-india-winter-school-2012\/"},"modified":"2025-08-06T12:02:29","modified_gmt":"2025-08-06T19:02:29","slug":"msr-india-winter-school-2012","status":"publish","type":"msr-event","link":"https:\/\/www.microsoft.com\/en-us\/research\/event\/msr-india-winter-school-2012\/","title":{"rendered":"MSR India Winter School 2012"},"content":{"rendered":"\n\n<p><strong>Venue:<\/strong> International Institute of Information Technology Hyderabad<\/p>\n<p><b>Organizing Committee:<\/b><\/p>\n<ul>\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/kannan\/\" target=\"_new\">Ravi Kannan<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>, Microsoft Research India<\/li>\n<li>Satya Lokam, Microsoft Research India<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/www.cs.cmu.edu\/afs\/cs\/user\/pjn\/www\/pjn.html\" target=\"_blank\">P J Narayanan<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>, International Institute of Information Technology Hyderabad<\/li>\n<\/ul>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n<p>The MSR India Winter School 2012 on Theoretical Computer Science was jointly organized by Microsoft Research India and the International Institute of Information Technology Hyderabad (IITH). The School comprised lectures by eminent researchers and exposed the audience to recent research advances in the area. The School hopefully stimulated new directions of research in Theoretical Computer Science.<\/p>\n<p>The School\u00a0was held on 18-22 December 2012 on the <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/www.iiit.ac.in\/\" target=\"_blank\">IIIT-H<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> campus, Hyderabad, India, following the conference <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/fsttcs.org\/\" target=\"_blank\"><em>Foundations of Software Technology and Theoretical Computer Science (FSTTCS)<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a>. The agenda included talks by eminent speakers like <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" title=\"\" href=\"http:\/\/www.cs.princeton.edu\/~arora\/\" target=\"_blank\">Sanjeev Arora<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>, <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\" target=\"_new\">Cynthia Dwork<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>, <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/www2.tepper.cmu.edu\/andrew\/ravi\/\" target=\"_blank\">R Ravi<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>, and <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/www.cse.iitm.ac.in\/~rangan\/\" target=\"_blank\">C. Pandu\u00a0Rangan<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>.<span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n<p>\t<div data-wp-context='{\"items\":[]}' data-wp-interactive=\"msr\/accordion\">\n\t\t\t\t\t<div class=\"clearfix\">\n\t\t\t\t<div\n\t\t\t\t\tclass=\"btn-group align-items-center mb-g float-sm-right\"\n\t\t\t\t\tdata-bi-aN=\"accordion-collapse-controls\"\n\t\t\t\t>\n\t\t\t\t\t<button\n\t\t\t\t\t\tclass=\"btn btn-link m-0\"\n\t\t\t\t\t\tdata-bi-cN=\"Expand all\"\n\t\t\t\t\t\tdata-wp-bind--aria-controls=\"state.ariaControls\"\n\t\t\t\t\t\tdata-wp-bind--aria-expanded=\"state.ariaExpanded\"\n\t\t\t\t\t\tdata-wp-bind--disabled=\"state.isAllExpanded\"\n\t\t\t\t\t\tdata-wp-class--inactive=\"state.isAllExpanded\"\n\t\t\t\t\t\tdata-wp-on--click=\"actions.onExpandAll\"\n\t\t\t\t\t\ttype=\"button\"\n\t\t\t\t\t>\n\t\t\t\t\t\tExpand all\t\t\t\t\t<\/button>\n\t\t\t\t\t<span aria-hidden=\"true\"> | <\/span>\n\t\t\t\t\t<button\n\t\t\t\t\t\tclass=\"btn btn-link m-0\"\n\t\t\t\t\t\tdata-bi-cN=\"Collapse all\"\n\t\t\t\t\t\tdata-wp-bind--aria-controls=\"state.ariaControls\"\n\t\t\t\t\t\tdata-wp-bind--aria-expanded=\"state.ariaExpanded\"\n\t\t\t\t\t\tdata-wp-bind--disabled=\"state.isAllCollapsed\"\n\t\t\t\t\t\tdata-wp-class--inactive=\"state.isAllCollapsed\"\n\t\t\t\t\t\tdata-wp-on--click=\"actions.onCollapseAll\"\n\t\t\t\t\t\ttype=\"button\"\n\t\t\t\t\t>\n\t\t\t\t\t\tCollapse all\t\t\t\t\t<\/button>\n\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t\t\t<ul class=\"msr-accordion\">\n\t\t\t\t\t\t\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6972\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6972\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6971\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tDifferential Privacy &#8211; Lecture 1\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6971\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6972\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\">Cynthia Dwork<\/a> | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/differential-privacy-lecture-1\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6974\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6974\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6973\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tHow to Approximate it? Introduction and Greedy Algorithms &#8211; Part 1\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6973\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6974\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>R. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/how-to-approximate-it-introduction-and-greedy-algorithms-part-1\/\">Video<\/a><\/p>\n<p>The lecture starts with an outline of the topics proposed to be covered, followed by an introduction to greedy algorithms illustrated using the set cover problem (logarithmic ratio approximation). The homework assigned was to analyze the greedy method applied to Uncapacitated Facility Location, and the Generalized Steiner Forest problems.<\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6976\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6976\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6975\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tGreedy Algorithms &#8211; Part 2\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6975\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6976\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>R. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/greedy-algorithms-part-2\/\">Video<\/a><\/p>\n<p>The lecture starts with an outline of the topics proposed to be covered, followed by an introduction to greedy algorithms illustrated using the set cover problem (logarithmic ratio approximation). The homework assigned was to analyze the greedy method applied to Uncapacitated Facility Location, and the Generalized Steiner Forest problems.<\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6978\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6978\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6977\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tTowards Provable Bounds for Machine Learning &#8211; Lecture 1\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6977\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6978\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>Sanjeev Arora | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/towards-provable-bounds-for-machine-learning-lecture-1\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6980\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6980\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6979\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tDifferential Privacy &#8211; Lecture 2\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6979\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6980\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\">Cynthia Dwork<\/a> | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/differential-privacy-lecture-2\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6982\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6982\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6981\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tTowards Provable Bounds for Machine Learning &#8211; Lecture 2 Part 1\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6981\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6982\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>Sanjeev Arora | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/towards-provable-bounds-for-machine-learning-lecture-2-part-1\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6984\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6984\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6983\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tTowards Provable Bounds for Machine Learning &#8211; Lecture 2 Part 2\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6983\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6984\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>Sanjeev Arora | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/towards-provable-bounds-for-machine-learning-lecture-2-part-2\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6986\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6986\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6985\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tLocal Search\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6985\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6986\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>R. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/local-search\/\">Video<\/a><\/p>\n<p>The Local Search method was illustrated using three problems: Maximum cut (2-approximation), Maximum leaf spanning trees (10-approximation) and the metric k-median problem (3-approximation).<\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6988\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6988\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6987\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tDifferential Privacy &#8211; Lecture 3\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6987\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6988\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\">Cynthia Dwork<\/a> | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/differential-privacy-lecture-3\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6990\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6990\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6989\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tTowards Provable Bounds for Machine Learning &#8211; Lecture 3\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6989\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6990\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>Sanjeev Arora | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/towards-provable-bounds-for-machine-learning-lecture-3\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6992\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6992\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6991\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tLinear Programs and Deterministic Rounding\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6991\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6992\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>R. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/linear-programs-and-deterministic-rounding\/\">Video<\/a><\/p>\n<p>Linear and integer programs were introduced and simple deterministic rounding was demonstrated for the vertex cover problem (2-approximation). The homework assigned was to design a deterministic rounding algorithm for the prize-collecting vertex cover problem.<\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6994\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6994\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6993\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tDifferential Privacy &#8211; Lecture 4\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6993\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6994\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\">Cynthia Dwork<\/a> | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/differential-privacy-lecture-4\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6996\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6996\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6995\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tTowards Provable Bounds for Machine Learning &#8211; Lecture 4\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6995\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6996\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>Sanjeev Arora | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/towards-provable-bounds-for-machine-learning-lecture-4\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6998\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6998\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6997\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tFiltering and the Primal-Dual Method &#8211; Part 1\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6997\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6998\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>R. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/filtering-and-the-primal-dual-method-part-1\/\">Video<\/a><\/p>\n<p>Two LP-based methods were covered. Filtering the optimal LP solution was illustrated to design a constant factor approximation for the metric uncapacitated facility location problem. The primal-dual method was illustrated by designing a 2-approximation algorithm for the generalized Steiner forest problem.<\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-7000\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-7000\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6999\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tFiltering and the Primal-Dual Method &#8211; Part 2\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6999\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-7000\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>R. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/filtering-and-the-primal-dual-method-part-2\/\">Video<\/a><\/p>\n<p>Two LP-based methods were covered. Filtering the optimal LP solution was illustrated to design a constant factor approximation for the metric uncapacitated facility location problem. The primal-dual method was illustrated by designing a 2-approximation algorithm for the generalized Steiner forest problem.<\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-7002\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-7002\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-7001\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tDifferential Privacy &#8211; Lecture 5\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-7001\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-7002\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\">Cynthia Dwork<\/a> | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/differential-privacy-lecture-5\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-7004\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-7004\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-7003\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tMetric Rounding of LP Relaxations\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-7003\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-7004\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>R. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/metric-rounding-of-lp-relaxations\/\">Video<\/a><\/p>\n<p>LP relaxations interpreted as metrics (or distance functions in graphs) are useful in designing approximation algorithms for cut problems. This was illustrated by designing an exact algorithm for minimum s-t cut, a 2-approximation for multiway cut in graphs, a 2-approximation for the multicut problem in trees and finally a logarithmic approximation for the multicut problem in general graphs.<\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-7006\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-7006\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-7005\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tIdentity-Based Deterministic Signature Scheme Without Forking-Lemma\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-7005\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-7006\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>Prof. Pandu Rangan | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/identity-based-deterministic-signature-scheme-without-forking-lemma\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t\t\t\t\t<\/ul>\n\t<\/div>\n\t<span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Venue: International Institute of Information Technology Hyderabad Organizing Committee: Ravi Kannan (opens in new tab), Microsoft Research India Satya Lokam, Microsoft Research India P J Narayanan (opens in new tab), International Institute of Information Technology Hyderabad Opens in a new tab The MSR India Winter School 2012 on Theoretical Computer Science was jointly organized by [&hellip;]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_startdate":"2012-12-18","msr_enddate":"2012-12-22","msr_location":"Hyderabad, India","msr_expirationdate":"","msr_event_recording_link":"","msr_event_link":"","msr_event_link_redirect":false,"msr_event_time":"","msr_hide_region":false,"msr_private_event":true,"msr_hide_image_in_river":0,"footnotes":""},"research-area":[13561],"msr-region":[197903],"msr-event-type":[197947],"msr-video-type":[],"msr-locale":[268875],"msr-program-audience":[],"msr-post-option":[],"msr-impact-theme":[],"class_list":["post-199806","msr-event","type-msr-event","status-publish","hentry","msr-research-area-algorithms","msr-region-asia-pacific","msr-event-type-universities","msr-locale-en_us"],"msr_about":"<!-- wp:msr\/event-details {\"title\":\"MSR India Winter School 2012\",\"backgroundColor\":\"grey\"} \/-->\n\n<!-- wp:msr\/content-tabs --><!-- wp:msr\/content-tab {\"title\":\"Summary\"} --><!-- wp:freeform --><p><strong>Venue:<\/strong> International Institute of Information Technology Hyderabad<\/p>\n<p><b>Organizing Committee:<\/b><\/p>\n<ul>\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/kannan\/\" target=\"_new\">Ravi Kannan<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>, Microsoft Research India<\/li>\n<li>Satya Lokam, Microsoft Research India<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/www.cs.cmu.edu\/afs\/cs\/user\/pjn\/www\/pjn.html\" target=\"_blank\">P J Narayanan<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>, International Institute of Information Technology Hyderabad<\/li>\n<\/ul>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n<p>The MSR India Winter School 2012 on Theoretical Computer Science was jointly organized by Microsoft Research India and the International Institute of Information Technology Hyderabad (IITH). The School comprised lectures by eminent researchers and exposed the audience to recent research advances in the area. The School hopefully stimulated new directions of research in Theoretical Computer Science.<\/p>\n<p>The School\u00a0was held on 18-22 December 2012 on the <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/www.iiit.ac.in\/\" target=\"_blank\">IIIT-H<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> campus, Hyderabad, India, following the conference <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/fsttcs.org\/\" target=\"_blank\"><em>Foundations of Software Technology and Theoretical Computer Science (FSTTCS)<\/em><span class=\"sr-only\"> (opens in new tab)<\/span><\/a>. The agenda included talks by eminent speakers like <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" title=\"\" href=\"http:\/\/www.cs.princeton.edu\/~arora\/\" target=\"_blank\">Sanjeev Arora<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>, <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\" target=\"_new\">Cynthia Dwork<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>, <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/www2.tepper.cmu.edu\/andrew\/ravi\/\" target=\"_blank\">R Ravi<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>, and <a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"http:\/\/www.cse.iitm.ac.in\/~rangan\/\" target=\"_blank\">C. Pandu\u00a0Rangan<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>.<span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n<!-- \/wp:freeform --><!-- \/wp:msr\/content-tab --><!-- wp:msr\/content-tab {\"title\":\"Videos\"} --><!-- wp:freeform --><p>\t<div data-wp-context='{\"items\":[]}' data-wp-interactive=\"msr\/accordion\">\n\t\t\t\t\t<div class=\"clearfix\">\n\t\t\t\t<div\n\t\t\t\t\tclass=\"btn-group align-items-center mb-g float-sm-right\"\n\t\t\t\t\tdata-bi-aN=\"accordion-collapse-controls\"\n\t\t\t\t>\n\t\t\t\t\t<button\n\t\t\t\t\t\tclass=\"btn btn-link m-0\"\n\t\t\t\t\t\tdata-bi-cN=\"Expand all\"\n\t\t\t\t\t\tdata-wp-bind--aria-controls=\"state.ariaControls\"\n\t\t\t\t\t\tdata-wp-bind--aria-expanded=\"state.ariaExpanded\"\n\t\t\t\t\t\tdata-wp-bind--disabled=\"state.isAllExpanded\"\n\t\t\t\t\t\tdata-wp-class--inactive=\"state.isAllExpanded\"\n\t\t\t\t\t\tdata-wp-on--click=\"actions.onExpandAll\"\n\t\t\t\t\t\ttype=\"button\"\n\t\t\t\t\t>\n\t\t\t\t\t\tExpand all\t\t\t\t\t<\/button>\n\t\t\t\t\t<span aria-hidden=\"true\"> | <\/span>\n\t\t\t\t\t<button\n\t\t\t\t\t\tclass=\"btn btn-link m-0\"\n\t\t\t\t\t\tdata-bi-cN=\"Collapse all\"\n\t\t\t\t\t\tdata-wp-bind--aria-controls=\"state.ariaControls\"\n\t\t\t\t\t\tdata-wp-bind--aria-expanded=\"state.ariaExpanded\"\n\t\t\t\t\t\tdata-wp-bind--disabled=\"state.isAllCollapsed\"\n\t\t\t\t\t\tdata-wp-class--inactive=\"state.isAllCollapsed\"\n\t\t\t\t\t\tdata-wp-on--click=\"actions.onCollapseAll\"\n\t\t\t\t\t\ttype=\"button\"\n\t\t\t\t\t>\n\t\t\t\t\t\tCollapse all\t\t\t\t\t<\/button>\n\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t\t\t<ul class=\"msr-accordion\">\n\t\t\t\t\t\t\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6972\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6972\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6971\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tDifferential Privacy - Lecture 1\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6971\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6972\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\">Cynthia Dwork<\/a> | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/differential-privacy-lecture-1\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6974\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6974\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6973\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tHow to Approximate it? Introduction and Greedy Algorithms - Part 1\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6973\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6974\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>R. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/how-to-approximate-it-introduction-and-greedy-algorithms-part-1\/\">Video<\/a><\/p>\n<p>The lecture starts with an outline of the topics proposed to be covered, followed by an introduction to greedy algorithms illustrated using the set cover problem (logarithmic ratio approximation). The homework assigned was to analyze the greedy method applied to Uncapacitated Facility Location, and the Generalized Steiner Forest problems.<\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6976\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6976\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6975\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tGreedy Algorithms - Part 2\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6975\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6976\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>R. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/greedy-algorithms-part-2\/\">Video<\/a><\/p>\n<p>The lecture starts with an outline of the topics proposed to be covered, followed by an introduction to greedy algorithms illustrated using the set cover problem (logarithmic ratio approximation). The homework assigned was to analyze the greedy method applied to Uncapacitated Facility Location, and the Generalized Steiner Forest problems.<\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6978\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6978\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6977\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tTowards Provable Bounds for Machine Learning - Lecture 1\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6977\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6978\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>Sanjeev Arora | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/towards-provable-bounds-for-machine-learning-lecture-1\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6980\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6980\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6979\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tDifferential Privacy - Lecture 2\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6979\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6980\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\">Cynthia Dwork<\/a> | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/differential-privacy-lecture-2\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6982\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6982\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6981\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tTowards Provable Bounds for Machine Learning - Lecture 2 Part 1\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6981\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6982\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>Sanjeev Arora | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/towards-provable-bounds-for-machine-learning-lecture-2-part-1\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6984\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6984\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6983\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tTowards Provable Bounds for Machine Learning - Lecture 2 Part 2\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6983\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6984\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>Sanjeev Arora | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/towards-provable-bounds-for-machine-learning-lecture-2-part-2\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6986\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6986\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6985\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tLocal Search\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6985\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6986\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>R. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/local-search\/\">Video<\/a><\/p>\n<p>The Local Search method was illustrated using three problems: Maximum cut (2-approximation), Maximum leaf spanning trees (10-approximation) and the metric k-median problem (3-approximation).<\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6988\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6988\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6987\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tDifferential Privacy - Lecture 3\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6987\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6988\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\">Cynthia Dwork<\/a> | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/differential-privacy-lecture-3\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6990\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6990\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6989\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tTowards Provable Bounds for Machine Learning - Lecture 3\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6989\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6990\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>Sanjeev Arora | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/towards-provable-bounds-for-machine-learning-lecture-3\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6992\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6992\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6991\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tLinear Programs and Deterministic Rounding\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6991\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6992\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>R. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/linear-programs-and-deterministic-rounding\/\">Video<\/a><\/p>\n<p>Linear and integer programs were introduced and simple deterministic rounding was demonstrated for the vertex cover problem (2-approximation). The homework assigned was to design a deterministic rounding algorithm for the prize-collecting vertex cover problem.<\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6994\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6994\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6993\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tDifferential Privacy - Lecture 4\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6993\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6994\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\">Cynthia Dwork<\/a> | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/differential-privacy-lecture-4\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6996\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6996\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6995\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tTowards Provable Bounds for Machine Learning - Lecture 4\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6995\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6996\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>Sanjeev Arora | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/towards-provable-bounds-for-machine-learning-lecture-4\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-6998\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-6998\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6997\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tFiltering and the Primal-Dual Method - Part 1\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6997\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-6998\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>R. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/filtering-and-the-primal-dual-method-part-1\/\">Video<\/a><\/p>\n<p>Two LP-based methods were covered. Filtering the optimal LP solution was illustrated to design a constant factor approximation for the metric uncapacitated facility location problem. The primal-dual method was illustrated by designing a 2-approximation algorithm for the generalized Steiner forest problem.<\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-7000\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-7000\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-6999\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tFiltering and the Primal-Dual Method - Part 2\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-6999\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-7000\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>R. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/filtering-and-the-primal-dual-method-part-2\/\">Video<\/a><\/p>\n<p>Two LP-based methods were covered. Filtering the optimal LP solution was illustrated to design a constant factor approximation for the metric uncapacitated facility location problem. The primal-dual method was illustrated by designing a 2-approximation algorithm for the generalized Steiner forest problem.<\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-7002\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-7002\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-7001\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tDifferential Privacy - Lecture 5\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-7001\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-7002\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\">Cynthia Dwork<\/a> | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/differential-privacy-lecture-5\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-7004\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-7004\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-7003\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tMetric Rounding of LP Relaxations\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-7003\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-7004\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>R. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/metric-rounding-of-lp-relaxations\/\">Video<\/a><\/p>\n<p>LP relaxations interpreted as metrics (or distance functions in graphs) are useful in designing approximation algorithms for cut problems. This was illustrated by designing an exact algorithm for minimum s-t cut, a 2-approximation for multiway cut in graphs, a 2-approximation for the multicut problem in trees and finally a logarithmic approximation for the multicut problem in general graphs.<\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t<li class=\"m-0\" data-wp-context='{\"id\":\"accordion-content-7006\"}' data-wp-init=\"callbacks.init\">\n\t\t<div class=\"accordion-header\">\n\t\t\t<button\n\t\t\t\taria-controls=\"accordion-content-7006\"\n\t\t\t\tclass=\"btn btn-collapse\"\n\t\t\t\tdata-wp-bind--aria-expanded=\"state.isExpanded\"\n\t\t\t\tdata-wp-on--click=\"actions.onClick\"\n\t\t\t\tid=\"accordion-button-7005\"\n\t\t\t\ttype=\"button\"\n\t\t\t>\n\t\t\t\tIdentity-Based Deterministic Signature Scheme Without Forking-Lemma\t\t\t<\/button>\n\t\t<\/div>\n\t\t<div\n\t\t\taria-labelledby=\"accordion-button-7005\"\n\t\t\tclass=\"msr-accordion__content\"\n\t\t\tdata-wp-bind--inert=\"!state.isExpanded\"\n\t\t\tdata-wp-run=\"callbacks.run\"\n\t\t\tid=\"accordion-content-7006\"\n\t\t>\n\t\t\t<div class=\"msr-accordion__body\">\n\t\t\t\t<p>Prof. Pandu Rangan | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/identity-based-deterministic-signature-scheme-without-forking-lemma\/\">Video<\/a><\/p>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n\t\t\t<\/div>\n\t\t<\/div>\n\t<\/li>\n\t\t\t\t\t\t<\/ul>\n\t<\/div>\n\t<span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n<!-- \/wp:freeform --><!-- \/wp:msr\/content-tab --><!-- \/wp:msr\/content-tabs -->","tab-content":[{"id":0,"name":"Summary","content":"The MSR India Winter School 2012 on Theoretical Computer Science was jointly organized by Microsoft Research India and the International Institute of Information Technology Hyderabad (IITH). The School comprised lectures by eminent researchers and exposed the audience to recent research advances in the area. The School hopefully stimulated new directions of research in Theoretical Computer Science.\r\n\r\nThe School\u00a0was held on 18-22 December 2012 on the <a href=\"http:\/\/www.iiit.ac.in\/\" target=\"_blank\">IIIT-H<\/a> campus, Hyderabad, India, following the conference <a href=\"http:\/\/fsttcs.org\/\" target=\"_blank\"><em>Foundations of Software Technology and Theoretical Computer Science (FSTTCS)<\/em><\/a>. The agenda included talks by eminent speakers like <a title=\"\" href=\"http:\/\/www.cs.princeton.edu\/~arora\/\" target=\"_new\">Sanjeev Arora<\/a>, <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\" target=\"_new\">Cynthia Dwork<\/a>, <a href=\"http:\/\/www2.tepper.cmu.edu\/andrew\/ravi\/\" target=\"_new\">R Ravi<\/a>, and <a href=\"http:\/\/www.cse.iitm.ac.in\/~rangan\/\" target=\"_new\">C. Pandu\u00a0Rangan<\/a>."},{"id":1,"name":"Videos","content":"[accordion]\r\n\r\n[panel header=\"Differential Privacy - Lecture 1\"]\r\n\r\n<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\">Cynthia Dwork<\/a> | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/differential-privacy-lecture-1\/\">Video<\/a>\r\n\r\n[\/panel]\r\n\r\n[panel header=\"How to Approximate it? Introduction and Greedy Algorithms - Part 1\"]\r\n\r\nR. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/how-to-approximate-it-introduction-and-greedy-algorithms-part-1\/\">Video<\/a>\r\n\r\nThe lecture starts with an outline of the topics proposed to be covered, followed by an introduction to greedy algorithms illustrated using the set cover problem (logarithmic ratio approximation). The homework assigned was to analyze the greedy method applied to Uncapacitated Facility Location, and the Generalized Steiner Forest problems.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Greedy Algorithms - Part 2\"]\r\n\r\nR. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/greedy-algorithms-part-2\/\">Video<\/a>\r\n\r\nThe lecture starts with an outline of the topics proposed to be covered, followed by an introduction to greedy algorithms illustrated using the set cover problem (logarithmic ratio approximation). The homework assigned was to analyze the greedy method applied to Uncapacitated Facility Location, and the Generalized Steiner Forest problems.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Towards Provable Bounds for Machine Learning - Lecture 1\"]\r\n\r\nSanjeev Arora | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/towards-provable-bounds-for-machine-learning-lecture-1\/\">Video<\/a>\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Differential Privacy - Lecture 2\"]\r\n\r\n<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\">Cynthia Dwork<\/a> | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/differential-privacy-lecture-2\/\">Video<\/a>\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Towards Provable Bounds for Machine Learning - Lecture 2 Part 1\"]\r\n\r\nSanjeev Arora | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/towards-provable-bounds-for-machine-learning-lecture-2-part-1\/\">Video<\/a>\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Towards Provable Bounds for Machine Learning - Lecture 2 Part 2\"]\r\n\r\nSanjeev Arora | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/towards-provable-bounds-for-machine-learning-lecture-2-part-2\/\">Video<\/a>\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Local Search\"]\r\n\r\nR. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/local-search\/\">Video<\/a>\r\n\r\nThe Local Search method was illustrated using three problems: Maximum cut (2-approximation), Maximum leaf spanning trees (10-approximation) and the metric k-median problem (3-approximation).\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Differential Privacy - Lecture 3\"]\r\n\r\n<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\">Cynthia Dwork<\/a> | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/differential-privacy-lecture-3\/\">Video<\/a>\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Towards Provable Bounds for Machine Learning - Lecture 3\"]\r\n\r\nSanjeev Arora | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/towards-provable-bounds-for-machine-learning-lecture-3\/\">Video<\/a>\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Linear Programs and Deterministic Rounding\"]\r\n\r\nR. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/linear-programs-and-deterministic-rounding\/\">Video<\/a>\r\n\r\nLinear and integer programs were introduced and simple deterministic rounding was demonstrated for the vertex cover problem (2-approximation). The homework assigned was to design a deterministic rounding algorithm for the prize-collecting vertex cover problem.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Differential Privacy - Lecture 4\"]\r\n\r\n<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\">Cynthia Dwork<\/a> | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/differential-privacy-lecture-4\/\">Video<\/a>\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Towards Provable Bounds for Machine Learning - Lecture 4\"]\r\n\r\nSanjeev Arora | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/towards-provable-bounds-for-machine-learning-lecture-4\/\">Video<\/a>\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Filtering and the Primal-Dual Method - Part 1\"]\r\n\r\nR. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/filtering-and-the-primal-dual-method-part-1\/\">Video<\/a>\r\n\r\nTwo LP-based methods were covered. Filtering the optimal LP solution was illustrated to design a constant factor approximation for the metric uncapacitated facility location problem. The primal-dual method was illustrated by designing a 2-approximation algorithm for the generalized Steiner forest problem.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Filtering and the Primal-Dual Method - Part 2\"]\r\n\r\nR. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/filtering-and-the-primal-dual-method-part-2\/\">Video<\/a>\r\n\r\nTwo LP-based methods were covered. Filtering the optimal LP solution was illustrated to design a constant factor approximation for the metric uncapacitated facility location problem. The primal-dual method was illustrated by designing a 2-approximation algorithm for the generalized Steiner forest problem.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Differential Privacy - Lecture 5\"]\r\n\r\n<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/dwork\/\">Cynthia Dwork<\/a> | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/differential-privacy-lecture-5\/\">Video<\/a>\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Metric Rounding of LP Relaxations\"]\r\n\r\nR. Ravi | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/metric-rounding-of-lp-relaxations\/\">Video<\/a>\r\n\r\nLP relaxations interpreted as metrics (or distance functions in graphs) are useful in designing approximation algorithms for cut problems. This was illustrated by designing an exact algorithm for minimum s-t cut, a 2-approximation for multiway cut in graphs, a 2-approximation for the multicut problem in trees and finally a logarithmic approximation for the multicut problem in general graphs.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Identity-Based Deterministic Signature Scheme Without Forking-Lemma\"]\r\n\r\nProf. Pandu Rangan | <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/video\/identity-based-deterministic-signature-scheme-without-forking-lemma\/\">Video<\/a>\r\n\r\n[\/panel]\r\n\r\n[\/accordion]"}],"msr_startdate":"2012-12-18","msr_enddate":"2012-12-22","msr_event_time":"","msr_location":"Hyderabad, India","msr_event_link":"","msr_event_recording_link":"","msr_startdate_formatted":"December 18, 2012","msr_register_text":"Watch now","msr_cta_link":"","msr_cta_text":"","msr_cta_bi_name":"","featured_image_thumbnail":null,"event_excerpt":"The MSR India Winter School 2012 on Theoretical Computer Science was jointly organized by Microsoft Research India and the International Institute of Information Technology Hyderabad (IITH). The School comprised lectures by eminent researchers and exposed the audience to recent research advances in the area. The School hopefully stimulated new directions of research in Theoretical Computer Science. The School\u00a0was held on 18-22 December 2012 on the IIIT-H campus, Hyderabad, India, following the conference Foundations of Software&hellip;","msr_research_lab":[199562],"related-researchers":[{"type":"user_nicename","value":"satya","display_name":"Satya Lokam","author_link":"<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/satya\/\" aria-label=\"Visit the profile page for Satya Lokam\">Satya Lokam<\/a>","is_active":false,"user_id":33532,"last_first":"Lokam, Satya","people_section":0,"alias":"satya"}],"msr_impact_theme":[],"related-academic-programs":[],"related-groups":[],"related-projects":[],"related-opportunities":[],"related-publications":[],"related-videos":[],"related-posts":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/199806","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-event"}],"version-history":[{"count":3,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/199806\/revisions"}],"predecessor-version":[{"id":1147402,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/199806\/revisions\/1147402"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=199806"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=199806"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=199806"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=199806"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=199806"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=199806"},{"taxonomy":"msr-program-audience","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-program-audience?post=199806"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=199806"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=199806"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}