{"id":310601,"date":"2016-10-25T10:38:00","date_gmt":"2016-10-25T17:38:00","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-event&#038;p=310601"},"modified":"2025-08-06T11:58:55","modified_gmt":"2025-08-06T18:58:55","slug":"2011-school-approximability","status":"publish","type":"msr-event","link":"https:\/\/www.microsoft.com\/en-us\/research\/event\/2011-school-approximability\/","title":{"rendered":"The 2011 School on Approximability"},"content":{"rendered":"\n\n<h3>Event Sponsors<\/h3>\n<ul>\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/lab\/microsoft-research-india\/\">Microsoft Research India<\/a> (MSR India)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cse.iitd.ac.in\/~naveen\/impecs\/\">Indo-German Max-Planck Center for Computer Science <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>(IMPECS)<\/li>\n<\/ul>\n<h3>India Schools<\/h3>\n<ul>\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/lab\/microsoft-research-india\/\">Microsoft Research India<\/a><\/li>\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/event\/2011-summer-school-security-privacy\/\" target=\"_self\">India Summer School on Security and Privacy 2011<\/a><\/li>\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/event\/summer-school-computing-socio-economic-development\/\" target=\"_self\">India Summer School on Computing for Socio-Economic Development 2010<\/a><\/li>\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/event\/summer-school-on-programming-languages-analysis-and-verification\/\" target=\"_self\">India Summer School on Programming Languages, Analysis, and Verification<\/a><\/li>\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/event\/summer-school-on-networking\/\">India Summer School on Networking 2009<\/a><\/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 focus of this school will be the approximability of optimization problems. Traditionally, approximability used to be a two-pronged task divided into algorithms and complexity but recently, a lot of cross-fertilization is taking place and the boundaries between algorithms and complexity are blurring. One of the goals of this school would be to further bring down this divide and promote a holistic thinking about approximability, which should lead to exciting new developments in the area.<\/p>\n<p>The school will bring together key contributors in this area to discuss these modern methods to a large research audience. In addition, the school will also have talks and open sessions for sharing new research and directions in approximability.<\/p>\n<h2>Organization<\/h2>\n<p><strong>Co-Chairs<\/strong><\/p>\n<ul>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cse.iitd.ernet.in\/~naveen\/\">Naveen Garg<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>, Indian Institute of Technology Delhi<\/li>\n<li>Nisheeth Vishnoi, Microsoft Research India<\/li>\n<\/ul>\n<p><strong>Support from IISc and MSR India<\/strong><\/p>\n<ul>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/math.iisc.ernet.in\/~rangaraj\/\">G. Rangarajan <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>(Convener, IISc Mathematics Initiative)<\/li>\n<li>Vidya Natampally (Microsoft Research India, Director of Strategy)<\/li>\n<li>Ashwani Sharma (Microsoft Research\u00a0India, Program Manager, External Research)<\/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><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/school_program.pdf\" target=\"_self\">Click here<\/a> to download the complete program<\/p>\n<table class=\" tWiz tableBorder borderRows borderColumns\" style=\"height: 607px\" width=\"891\">\n<tbody>\n<tr>\n<td colspan=\"7\"><strong>Wednesday, January 5, 2011<\/strong><\/td>\n<\/tr>\n<tr>\n<td colspan=\"7\"><\/td>\n<\/tr>\n<tr>\n<td>0900<\/td>\n<td>0930<\/td>\n<td colspan=\"5\">Registration<\/td>\n<\/tr>\n<tr>\n<td>0915<\/td>\n<td>0945<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1000<\/td>\n<td>1100<\/td>\n<td colspan=\"5\"><strong>Richard M. Karp<\/strong> [Keynote Talk] (<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan5-talk1.pptx\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Effective Heuristics for NP-Hard Problems Arising in Molecular Biology<\/td>\n<\/tr>\n<tr>\n<td>1100<\/td>\n<td>1130<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1130<\/td>\n<td>1230<\/td>\n<td colspan=\"5\"><strong>Sanjeev Arora<\/strong> [Keynote Talk] (<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan5-talk2.ppt\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Semidefinite Programming and Approximation Algorithms: A Survey<\/td>\n<\/tr>\n<tr>\n<td>1230<\/td>\n<td>1400<\/td>\n<td colspan=\"5\">Lunch<\/td>\n<\/tr>\n<tr>\n<td>1400<\/td>\n<td>1500<\/td>\n<td colspan=\"5\"><strong>David Steurer<\/strong> (<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan5-talk3.ppsx\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Algorithms for Unique Games and Related Problems<\/td>\n<\/tr>\n<tr>\n<td>1500<\/td>\n<td>1505<\/td>\n<td colspan=\"5\">Break<\/td>\n<\/tr>\n<tr>\n<td>1505<\/td>\n<td>1605<\/td>\n<td colspan=\"5\"><strong>Mohit Singh<\/strong> (slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">A Randomized Rounding Approach to the Traveling Salesman Problem<\/td>\n<\/tr>\n<tr>\n<td>1605<\/td>\n<td>1630<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1630<\/td>\n<td>1730<\/td>\n<td colspan=\"5\"><strong>Ravi Kannan <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Questions and Algorithms for Tensors<\/td>\n<\/tr>\n<tr>\n<td>1730<\/td>\n<td>1800<\/td>\n<td colspan=\"5\"><strong>Amit Deshpande<\/strong> (<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/amitdeshpande.pdf\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Approximability of Subspace Approximation<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table class=\" tWiz tableBorder borderRows borderColumns\" style=\"height: 558px\" width=\"892\">\n<tbody>\n<tr>\n<td colspan=\"7\"><b>Thursday, January 6, 2011<\/b><\/td>\n<\/tr>\n<tr>\n<td colspan=\"7\"><\/td>\n<\/tr>\n<tr>\n<td>0930<\/td>\n<td>1000<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1000<\/td>\n<td>1100<\/td>\n<td colspan=\"5\"><strong>R. Ravi <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan6-talk1.pdf\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Matching Based Augmentations for Approximating Connectivity Problems<\/td>\n<\/tr>\n<tr>\n<td>1100<\/td>\n<td>1130<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1130<\/td>\n<td>1230<\/td>\n<td colspan=\"5\"><strong>Sanjeev Arora <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan6-talk2.ppt\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Algorithms for Approximating Graph Expansion and Connections to Geometry<\/td>\n<\/tr>\n<tr>\n<td>1230<\/td>\n<td>1400<\/td>\n<td colspan=\"5\">Lunch<\/td>\n<\/tr>\n<tr>\n<td>1400<\/td>\n<td>1500<\/td>\n<td colspan=\"5\"><strong>David Steurer <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan6-talk3.ppsx\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Graph Expansion and the Unique Games Conjecture<\/td>\n<\/tr>\n<tr>\n<td>1500<\/td>\n<td>1505<\/td>\n<td colspan=\"5\">Break<\/td>\n<\/tr>\n<tr>\n<td>1505<\/td>\n<td>1605<\/td>\n<td colspan=\"5\"><strong>Lorenzo Orecchia <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Fast Spectral Algorithms for Graph Partitioning and Graph Decomposition<\/td>\n<\/tr>\n<tr>\n<td>1605<\/td>\n<td>1630<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1630<\/td>\n<td>1730<\/td>\n<td colspan=\"5\"><strong>Subhash Khot <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Introduction to Hardness of Approximation and Probabilistically Checkable Proofs<\/td>\n<\/tr>\n<tr>\n<td>1730<\/td>\n<td>1800<\/td>\n<td colspan=\"5\"><strong>Saket Saurabh <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Slightly Superexponential Parameterized Problems<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table class=\" tWiz tableBorder borderRows borderColumns\" style=\"height: 565px\" width=\"895\">\n<tbody>\n<tr>\n<td colspan=\"7\"><b>Friday, January 7, 2011<\/b><\/td>\n<\/tr>\n<tr>\n<td colspan=\"7\"><\/td>\n<\/tr>\n<tr>\n<td>0930<\/td>\n<td>1000<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1000<\/td>\n<td>1100<\/td>\n<td colspan=\"5\"><strong>Subhash Khot <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry<\/td>\n<\/tr>\n<tr>\n<td>1100<\/td>\n<td>1130<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1130<\/td>\n<td>1230<\/td>\n<td colspan=\"5\"><strong>Prasad Raghavendra <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">How to Round Any CSP?<\/td>\n<\/tr>\n<tr>\n<td>1230<\/td>\n<td>1400<\/td>\n<td colspan=\"5\">Lunch<\/td>\n<\/tr>\n<tr>\n<td>1400<\/td>\n<td>1500<\/td>\n<td colspan=\"5\"><strong>Nikhil Devanur <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">The Steiner Tree Problem<\/td>\n<\/tr>\n<tr>\n<td>1500<\/td>\n<td>1505<\/td>\n<td colspan=\"5\">Break<\/td>\n<\/tr>\n<tr>\n<td>1505<\/td>\n<td>1605<\/td>\n<td colspan=\"5\"><strong>Sambuddha Roy <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/sambuddha.pdf\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Primal Dual Approximation Algorithms<\/td>\n<\/tr>\n<tr>\n<td>1605<\/td>\n<td>1630<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1630<\/td>\n<td>1730<\/td>\n<td colspan=\"5\"><strong>Kamal Jain <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Online Bipartite Matching via a Primal-Dual Technique for Convex Programs<\/td>\n<\/tr>\n<tr>\n<td>1730<\/td>\n<td>1800<\/td>\n<td colspan=\"5\"><strong>Vinayaka Pandit <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/vinayaka.pdf\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Local Search Based Approximation Algorithms for Facility Location Problems<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table class=\" tWiz tableBorder borderRows borderColumns\" style=\"height: 591px\" width=\"893\">\n<tbody>\n<tr>\n<td colspan=\"7\"><b>Saturday, January 8, 2011<\/b><\/td>\n<\/tr>\n<tr>\n<td colspan=\"7\"><\/td>\n<\/tr>\n<tr>\n<td>0930<\/td>\n<td>1000<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1000<\/td>\n<td>1100<\/td>\n<td colspan=\"5\"><strong>R. Ravi <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/prahladh.pptx\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Iterative Methods in Combinatorial Optimization<\/td>\n<\/tr>\n<tr>\n<td>1100<\/td>\n<td>1130<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1130<\/td>\n<td>1230<\/td>\n<td colspan=\"5\"><strong>Subhash Khot <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">On the Unique Games Conjecture<\/td>\n<\/tr>\n<tr>\n<td>1230<\/td>\n<td>1400<\/td>\n<td colspan=\"5\">Lunch<\/td>\n<\/tr>\n<tr>\n<td>1400<\/td>\n<td>1500<\/td>\n<td colspan=\"5\"><strong>Prasad Raghavendra<\/strong> (slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Complexity of Constraint Satisfaction Problems: Exact and Approximate<\/td>\n<\/tr>\n<tr>\n<td>1500<\/td>\n<td>1505<\/td>\n<td colspan=\"5\">Break<\/td>\n<\/tr>\n<tr>\n<td>1505<\/td>\n<td>1605<\/td>\n<td colspan=\"5\"><strong>Prahladh Harsha <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/prahladh.pptx\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Inapproximability Results from Label-Cover Variants and Other Hardness Assumptions<\/td>\n<\/tr>\n<tr>\n<td>1605<\/td>\n<td>1630<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1630<\/td>\n<td>1730<\/td>\n<td colspan=\"5\"><strong>Madhur Tulsiani <\/strong>(<a title=\"\" href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/madhur.pdf\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Introduction to LP and SDP Hierarchies<\/td>\n<\/tr>\n<tr>\n<td>1730<\/td>\n<td>1800<\/td>\n<td colspan=\"5\"><strong>L. Sunil Chandran <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/sunil.pdf\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Rainbow Colouring of Graphs<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table class=\" tWiz tableBorder borderRows borderColumns\" style=\"height: 255px\" width=\"892\">\n<tbody>\n<tr>\n<td colspan=\"7\"><b>Sunday, January 9, 2011<\/b><\/td>\n<\/tr>\n<tr>\n<td colspan=\"7\"><\/td>\n<\/tr>\n<tr>\n<td>0930<\/td>\n<td>1000<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1000<\/td>\n<td>1100<\/td>\n<td colspan=\"5\"><strong>Amit Kumar<\/strong> (slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Scheduling to Minimize Weighted Flow-Time<\/td>\n<\/tr>\n<tr>\n<td>1100<\/td>\n<td>1130<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1130<\/td>\n<td>1230<\/td>\n<td colspan=\"5\"><strong>Naveen Garg <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Fast Combinatorial Algorithms for Solving Positive Linear Programs<\/td>\n<\/tr>\n<tr>\n<td>1230<\/td>\n<td>1400<\/td>\n<td colspan=\"5\">Lunch<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n<ul>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cs.princeton.edu\/~arora\/\">Sanjeev Arora <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>(Princeton)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cse.iitd.ernet.in\/~amitk\/\">Amit Kumar<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (IIT Delhi)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/drona.csa.iisc.ernet.in\/~sunil\/\">Sunil Chandran<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>\u00a0(Indian Institute of Science)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cs.berkeley.edu\/~orecchia\/\">Lorenzo Orecchia <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>(Berkeley)<\/li>\n<li>Amit Deshpande (Microsoft Research)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"https:\/\/researcher.ibm.com\/researcher\/view.php?person=in-pvinayak\">Vinayaka Pandit <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>(IBM IRL)<\/li>\n<li>Nikhil Devanur (Microsoft Research)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.scs.gatech.edu\/people\/prasad-raghavendra\">Prasad Raghavendra<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (Georgia Tech)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cse.iitd.ernet.in\/~naveen\/\">Naveen Garg<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (IIT Delhi)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www2.tepper.cmu.edu\/andrew\/ravi\/\"> R. Ravi<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (Carnegie Mellon)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.tcs.tifr.res.in\/~prahladh\/\">Prahladh Harsha <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>(TIFR)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"https:\/\/researcher.ibm.com\/researcher\/view.php?person=in-sambuddha\">Sambuddha Roy <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>(IBM IRL)<\/li>\n<li>Kamal Jain (Microsoft Research)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.imsc.res.in\/~saket\/\">Saket Saurabh<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (IMSc, Chennai)<\/li>\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/kannan\/\">Ravi Kannan<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (Microsoft Research)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cs.mcgill.ca\/~mohit\/\">Mohit Singh<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (McGill University)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.eecs.berkeley.edu\/~karp\/\">Richard Karp <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>(Berkeley)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cs.princeton.edu\/~dsteurer\/\">David Steurer<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (Microsoft Research)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cs.nyu.edu\/~khot\/\">Subhash Khot<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (New York University)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.math.ias.edu\/~madhurt\/\">Madhur Tulsiani<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (Princeton\/IAS)<\/li>\n<\/ul>\n<p><span id=\"label-external-link\" class=\"sr-only\" aria-hidden=\"true\">Opens in a new tab<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Event Sponsors Microsoft Research India (MSR India) Indo-German Max-Planck Center for Computer Science (opens in new tab)(IMPECS) India Schools Microsoft Research India India Summer School on Security and Privacy 2011 India Summer School on Computing for Socio-Economic Development 2010 India Summer School on Programming Languages, Analysis, and Verification India Summer School on Networking 2009 Opens [&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":"2011-01-05","msr_enddate":"2011-01-09","msr_location":"Bangalore, 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,13556],"msr-region":[],"msr-event-type":[],"msr-video-type":[],"msr-locale":[268875],"msr-program-audience":[],"msr-post-option":[],"msr-impact-theme":[],"class_list":["post-310601","msr-event","type-msr-event","status-publish","hentry","msr-research-area-algorithms","msr-research-area-artificial-intelligence","msr-locale-en_us"],"msr_about":"<!-- wp:msr\/event-details {\"title\":\"The 2011 School on Approximability\",\"backgroundColor\":\"grey\"} \/-->\n\n<!-- wp:msr\/content-tabs --><!-- wp:msr\/content-tab {\"title\":\"About\"} --><!-- wp:freeform --><h3>Event Sponsors<\/h3>\n<ul>\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/lab\/microsoft-research-india\/\">Microsoft Research India<\/a> (MSR India)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cse.iitd.ac.in\/~naveen\/impecs\/\">Indo-German Max-Planck Center for Computer Science <\/a>(IMPECS)<\/li>\n<\/ul>\n<h3>India Schools<\/h3>\n<ul>\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/lab\/microsoft-research-india\/\">Microsoft Research India<\/a><\/li>\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/event\/2011-summer-school-security-privacy\/\" target=\"_self\">India Summer School on Security and Privacy 2011<\/a><\/li>\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/event\/summer-school-computing-socio-economic-development\/\" target=\"_self\">India Summer School on Computing for Socio-Economic Development 2010<\/a><\/li>\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/event\/summer-school-on-programming-languages-analysis-and-verification\/\" target=\"_self\">India Summer School on Programming Languages, Analysis, and Verification<\/a><\/li>\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/event\/summer-school-on-networking\/\">India Summer School on Networking 2009<\/a><\/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 focus of this school will be the approximability of optimization problems. Traditionally, approximability used to be a two-pronged task divided into algorithms and complexity but recently, a lot of cross-fertilization is taking place and the boundaries between algorithms and complexity are blurring. One of the goals of this school would be to further bring down this divide and promote a holistic thinking about approximability, which should lead to exciting new developments in the area.<\/p>\n<p>The school will bring together key contributors in this area to discuss these modern methods to a large research audience. In addition, the school will also have talks and open sessions for sharing new research and directions in approximability.<\/p>\n<h2>Organization<\/h2>\n<p><strong>Co-Chairs<\/strong><\/p>\n<ul>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cse.iitd.ernet.in\/~naveen\/\">Naveen Garg<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>, Indian Institute of Technology Delhi<\/li>\n<li>Nisheeth Vishnoi, Microsoft Research India<\/li>\n<\/ul>\n<p><strong>Support from IISc and MSR India<\/strong><\/p>\n<ul>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/math.iisc.ernet.in\/~rangaraj\/\">G. Rangarajan <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>(Convener, IISc Mathematics Initiative)<\/li>\n<li>Vidya Natampally (Microsoft Research India, Director of Strategy)<\/li>\n<li>Ashwani Sharma (Microsoft Research\u00a0India, Program Manager, External Research)<\/li>\n<\/ul>\n<p><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\":\"Agenda and Talks\"} --><!-- wp:freeform --><p><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/school_program.pdf\" target=\"_self\">Click here<\/a> to download the complete program<\/p>\n<table class=\" tWiz tableBorder borderRows borderColumns\" style=\"height: 607px\" width=\"891\">\n<tbody>\n<tr>\n<td colspan=\"7\"><strong>Wednesday, January 5, 2011<\/strong><\/td>\n<\/tr>\n<tr>\n<td colspan=\"7\"><\/td>\n<\/tr>\n<tr>\n<td>0900<\/td>\n<td>0930<\/td>\n<td colspan=\"5\">Registration<\/td>\n<\/tr>\n<tr>\n<td>0915<\/td>\n<td>0945<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1000<\/td>\n<td>1100<\/td>\n<td colspan=\"5\"><strong>Richard M. Karp<\/strong> [Keynote Talk] (<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan5-talk1.pptx\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Effective Heuristics for NP-Hard Problems Arising in Molecular Biology<\/td>\n<\/tr>\n<tr>\n<td>1100<\/td>\n<td>1130<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1130<\/td>\n<td>1230<\/td>\n<td colspan=\"5\"><strong>Sanjeev Arora<\/strong> [Keynote Talk] (<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan5-talk2.ppt\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Semidefinite Programming and Approximation Algorithms: A Survey<\/td>\n<\/tr>\n<tr>\n<td>1230<\/td>\n<td>1400<\/td>\n<td colspan=\"5\">Lunch<\/td>\n<\/tr>\n<tr>\n<td>1400<\/td>\n<td>1500<\/td>\n<td colspan=\"5\"><strong>David Steurer<\/strong> (<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan5-talk3.ppsx\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Algorithms for Unique Games and Related Problems<\/td>\n<\/tr>\n<tr>\n<td>1500<\/td>\n<td>1505<\/td>\n<td colspan=\"5\">Break<\/td>\n<\/tr>\n<tr>\n<td>1505<\/td>\n<td>1605<\/td>\n<td colspan=\"5\"><strong>Mohit Singh<\/strong> (slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">A Randomized Rounding Approach to the Traveling Salesman Problem<\/td>\n<\/tr>\n<tr>\n<td>1605<\/td>\n<td>1630<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1630<\/td>\n<td>1730<\/td>\n<td colspan=\"5\"><strong>Ravi Kannan <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Questions and Algorithms for Tensors<\/td>\n<\/tr>\n<tr>\n<td>1730<\/td>\n<td>1800<\/td>\n<td colspan=\"5\"><strong>Amit Deshpande<\/strong> (<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/amitdeshpande.pdf\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Approximability of Subspace Approximation<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table class=\" tWiz tableBorder borderRows borderColumns\" style=\"height: 558px\" width=\"892\">\n<tbody>\n<tr>\n<td colspan=\"7\"><b>Thursday, January 6, 2011<\/b><\/td>\n<\/tr>\n<tr>\n<td colspan=\"7\"><\/td>\n<\/tr>\n<tr>\n<td>0930<\/td>\n<td>1000<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1000<\/td>\n<td>1100<\/td>\n<td colspan=\"5\"><strong>R. Ravi <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan6-talk1.pdf\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Matching Based Augmentations for Approximating Connectivity Problems<\/td>\n<\/tr>\n<tr>\n<td>1100<\/td>\n<td>1130<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1130<\/td>\n<td>1230<\/td>\n<td colspan=\"5\"><strong>Sanjeev Arora <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan6-talk2.ppt\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Algorithms for Approximating Graph Expansion and Connections to Geometry<\/td>\n<\/tr>\n<tr>\n<td>1230<\/td>\n<td>1400<\/td>\n<td colspan=\"5\">Lunch<\/td>\n<\/tr>\n<tr>\n<td>1400<\/td>\n<td>1500<\/td>\n<td colspan=\"5\"><strong>David Steurer <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan6-talk3.ppsx\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Graph Expansion and the Unique Games Conjecture<\/td>\n<\/tr>\n<tr>\n<td>1500<\/td>\n<td>1505<\/td>\n<td colspan=\"5\">Break<\/td>\n<\/tr>\n<tr>\n<td>1505<\/td>\n<td>1605<\/td>\n<td colspan=\"5\"><strong>Lorenzo Orecchia <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Fast Spectral Algorithms for Graph Partitioning and Graph Decomposition<\/td>\n<\/tr>\n<tr>\n<td>1605<\/td>\n<td>1630<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1630<\/td>\n<td>1730<\/td>\n<td colspan=\"5\"><strong>Subhash Khot <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Introduction to Hardness of Approximation and Probabilistically Checkable Proofs<\/td>\n<\/tr>\n<tr>\n<td>1730<\/td>\n<td>1800<\/td>\n<td colspan=\"5\"><strong>Saket Saurabh <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Slightly Superexponential Parameterized Problems<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table class=\" tWiz tableBorder borderRows borderColumns\" style=\"height: 565px\" width=\"895\">\n<tbody>\n<tr>\n<td colspan=\"7\"><b>Friday, January 7, 2011<\/b><\/td>\n<\/tr>\n<tr>\n<td colspan=\"7\"><\/td>\n<\/tr>\n<tr>\n<td>0930<\/td>\n<td>1000<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1000<\/td>\n<td>1100<\/td>\n<td colspan=\"5\"><strong>Subhash Khot <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry<\/td>\n<\/tr>\n<tr>\n<td>1100<\/td>\n<td>1130<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1130<\/td>\n<td>1230<\/td>\n<td colspan=\"5\"><strong>Prasad Raghavendra <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">How to Round Any CSP?<\/td>\n<\/tr>\n<tr>\n<td>1230<\/td>\n<td>1400<\/td>\n<td colspan=\"5\">Lunch<\/td>\n<\/tr>\n<tr>\n<td>1400<\/td>\n<td>1500<\/td>\n<td colspan=\"5\"><strong>Nikhil Devanur <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">The Steiner Tree Problem<\/td>\n<\/tr>\n<tr>\n<td>1500<\/td>\n<td>1505<\/td>\n<td colspan=\"5\">Break<\/td>\n<\/tr>\n<tr>\n<td>1505<\/td>\n<td>1605<\/td>\n<td colspan=\"5\"><strong>Sambuddha Roy <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/sambuddha.pdf\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Primal Dual Approximation Algorithms<\/td>\n<\/tr>\n<tr>\n<td>1605<\/td>\n<td>1630<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1630<\/td>\n<td>1730<\/td>\n<td colspan=\"5\"><strong>Kamal Jain <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Online Bipartite Matching via a Primal-Dual Technique for Convex Programs<\/td>\n<\/tr>\n<tr>\n<td>1730<\/td>\n<td>1800<\/td>\n<td colspan=\"5\"><strong>Vinayaka Pandit <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/vinayaka.pdf\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Local Search Based Approximation Algorithms for Facility Location Problems<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table class=\" tWiz tableBorder borderRows borderColumns\" style=\"height: 591px\" width=\"893\">\n<tbody>\n<tr>\n<td colspan=\"7\"><b>Saturday, January 8, 2011<\/b><\/td>\n<\/tr>\n<tr>\n<td colspan=\"7\"><\/td>\n<\/tr>\n<tr>\n<td>0930<\/td>\n<td>1000<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1000<\/td>\n<td>1100<\/td>\n<td colspan=\"5\"><strong>R. Ravi <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/prahladh.pptx\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Iterative Methods in Combinatorial Optimization<\/td>\n<\/tr>\n<tr>\n<td>1100<\/td>\n<td>1130<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1130<\/td>\n<td>1230<\/td>\n<td colspan=\"5\"><strong>Subhash Khot <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">On the Unique Games Conjecture<\/td>\n<\/tr>\n<tr>\n<td>1230<\/td>\n<td>1400<\/td>\n<td colspan=\"5\">Lunch<\/td>\n<\/tr>\n<tr>\n<td>1400<\/td>\n<td>1500<\/td>\n<td colspan=\"5\"><strong>Prasad Raghavendra<\/strong> (slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Complexity of Constraint Satisfaction Problems: Exact and Approximate<\/td>\n<\/tr>\n<tr>\n<td>1500<\/td>\n<td>1505<\/td>\n<td colspan=\"5\">Break<\/td>\n<\/tr>\n<tr>\n<td>1505<\/td>\n<td>1605<\/td>\n<td colspan=\"5\"><strong>Prahladh Harsha <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/prahladh.pptx\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Inapproximability Results from Label-Cover Variants and Other Hardness Assumptions<\/td>\n<\/tr>\n<tr>\n<td>1605<\/td>\n<td>1630<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1630<\/td>\n<td>1730<\/td>\n<td colspan=\"5\"><strong>Madhur Tulsiani <\/strong>(<a title=\"\" href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/madhur.pdf\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Introduction to LP and SDP Hierarchies<\/td>\n<\/tr>\n<tr>\n<td>1730<\/td>\n<td>1800<\/td>\n<td colspan=\"5\"><strong>L. Sunil Chandran <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/sunil.pdf\" target=\"_self\">slides<\/a>)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Rainbow Colouring of Graphs<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<table class=\" tWiz tableBorder borderRows borderColumns\" style=\"height: 255px\" width=\"892\">\n<tbody>\n<tr>\n<td colspan=\"7\"><b>Sunday, January 9, 2011<\/b><\/td>\n<\/tr>\n<tr>\n<td colspan=\"7\"><\/td>\n<\/tr>\n<tr>\n<td>0930<\/td>\n<td>1000<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1000<\/td>\n<td>1100<\/td>\n<td colspan=\"5\"><strong>Amit Kumar<\/strong> (slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Scheduling to Minimize Weighted Flow-Time<\/td>\n<\/tr>\n<tr>\n<td>1100<\/td>\n<td>1130<\/td>\n<td colspan=\"5\">Tea\/Coffee<\/td>\n<\/tr>\n<tr>\n<td>1130<\/td>\n<td>1230<\/td>\n<td colspan=\"5\"><strong>Naveen Garg <\/strong>(slides)<\/td>\n<\/tr>\n<tr>\n<td colspan=\"2\"><\/td>\n<td colspan=\"5\">Fast Combinatorial Algorithms for Solving Positive Linear Programs<\/td>\n<\/tr>\n<tr>\n<td>1230<\/td>\n<td>1400<\/td>\n<td colspan=\"5\">Lunch<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><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\":\"Speakers\"} --><!-- wp:freeform --><ul>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cs.princeton.edu\/~arora\/\">Sanjeev Arora <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>(Princeton)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cse.iitd.ernet.in\/~amitk\/\">Amit Kumar<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (IIT Delhi)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/drona.csa.iisc.ernet.in\/~sunil\/\">Sunil Chandran<span class=\"sr-only\"> (opens in new tab)<\/span><\/a>\u00a0(Indian Institute of Science)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cs.berkeley.edu\/~orecchia\/\">Lorenzo Orecchia <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>(Berkeley)<\/li>\n<li>Amit Deshpande (Microsoft Research)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"https:\/\/researcher.ibm.com\/researcher\/view.php?person=in-pvinayak\">Vinayaka Pandit <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>(IBM IRL)<\/li>\n<li>Nikhil Devanur (Microsoft Research)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.scs.gatech.edu\/people\/prasad-raghavendra\">Prasad Raghavendra<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (Georgia Tech)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cse.iitd.ernet.in\/~naveen\/\">Naveen Garg<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (IIT Delhi)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www2.tepper.cmu.edu\/andrew\/ravi\/\"> R. Ravi<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (Carnegie Mellon)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.tcs.tifr.res.in\/~prahladh\/\">Prahladh Harsha <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>(TIFR)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"https:\/\/researcher.ibm.com\/researcher\/view.php?person=in-sambuddha\">Sambuddha Roy <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>(IBM IRL)<\/li>\n<li>Kamal Jain (Microsoft Research)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.imsc.res.in\/~saket\/\">Saket Saurabh<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (IMSc, Chennai)<\/li>\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/kannan\/\">Ravi Kannan<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (Microsoft Research)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cs.mcgill.ca\/~mohit\/\">Mohit Singh<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (McGill University)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.eecs.berkeley.edu\/~karp\/\">Richard Karp <span class=\"sr-only\"> (opens in new tab)<\/span><\/a>(Berkeley)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cs.princeton.edu\/~dsteurer\/\">David Steurer<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (Microsoft Research)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.cs.nyu.edu\/~khot\/\">Subhash Khot<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (New York University)<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" target=\"_blank\" href=\"http:\/\/www.math.ias.edu\/~madhurt\/\">Madhur Tulsiani<span class=\"sr-only\"> (opens in new tab)<\/span><\/a> (Princeton\/IAS)<\/li>\n<\/ul>\n<p><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":"About","content":"The focus of this school will be the approximability of optimization problems. Traditionally, approximability used to be a two-pronged task divided into algorithms and complexity but recently, a lot of cross-fertilization is taking place and the boundaries between algorithms and complexity are blurring. One of the goals of this school would be to further bring down this divide and promote a holistic thinking about approximability, which should lead to exciting new developments in the area.\r\n\r\nThe school will bring together key contributors in this area to discuss these modern methods to a large research audience. In addition, the school will also have talks and open sessions for sharing new research and directions in approximability.\r\n<h2>Organization<\/h2>\r\n<strong>Co-Chairs<\/strong>\r\n<ul>\r\n \t<li><a href=\"http:\/\/www.cse.iitd.ernet.in\/~naveen\/\">Naveen Garg<\/a>, Indian Institute of Technology Delhi<\/li>\r\n \t<li>Nisheeth Vishnoi, Microsoft Research India<\/li>\r\n<\/ul>\r\n<strong>Support from IISc and MSR India<\/strong>\r\n<ul>\r\n \t<li><a href=\"http:\/\/math.iisc.ernet.in\/~rangaraj\/\">G. Rangarajan <\/a>(Convener, IISc Mathematics Initiative)<\/li>\r\n \t<li>Vidya Natampally (Microsoft Research India, Director of Strategy)<\/li>\r\n \t<li>Ashwani Sharma (Microsoft Research\u00a0India, Program Manager, External Research)<\/li>\r\n<\/ul>"},{"id":1,"name":"Agenda and Talks","content":"<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/school_program.pdf\" target=\"_self\">Click here<\/a> to download the complete program\r\n<table class=\" tWiz tableBorder borderRows borderColumns\" style=\"height: 607px\" width=\"891\">\r\n<tbody>\r\n<tr>\r\n<td colspan=\"7\"><strong>Wednesday, January 5, 2011<\/strong><\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"7\"><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>0900<\/td>\r\n<td>0930<\/td>\r\n<td colspan=\"5\">Registration<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>0915<\/td>\r\n<td>0945<\/td>\r\n<td colspan=\"5\">Tea\/Coffee<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1000<\/td>\r\n<td>1100<\/td>\r\n<td colspan=\"5\"><strong>Richard M. Karp<\/strong> [Keynote Talk] (<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan5-talk1.pptx\" target=\"_self\">slides<\/a>)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Effective Heuristics for NP-Hard Problems Arising in Molecular Biology<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1100<\/td>\r\n<td>1130<\/td>\r\n<td colspan=\"5\">Tea\/Coffee<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1130<\/td>\r\n<td>1230<\/td>\r\n<td colspan=\"5\"><strong>Sanjeev Arora<\/strong> [Keynote Talk] (<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan5-talk2.ppt\" target=\"_self\">slides<\/a>)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Semidefinite Programming and Approximation Algorithms: A Survey<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1230<\/td>\r\n<td>1400<\/td>\r\n<td colspan=\"5\">Lunch<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1400<\/td>\r\n<td>1500<\/td>\r\n<td colspan=\"5\"><strong>David Steurer<\/strong> (<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan5-talk3.ppsx\" target=\"_self\">slides<\/a>)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Algorithms for Unique Games and Related Problems<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1500<\/td>\r\n<td>1505<\/td>\r\n<td colspan=\"5\">Break<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1505<\/td>\r\n<td>1605<\/td>\r\n<td colspan=\"5\"><strong>Mohit Singh<\/strong> (slides)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">A Randomized Rounding Approach to the Traveling Salesman Problem<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1605<\/td>\r\n<td>1630<\/td>\r\n<td colspan=\"5\">Tea\/Coffee<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1630<\/td>\r\n<td>1730<\/td>\r\n<td colspan=\"5\"><strong>Ravi Kannan <\/strong>(slides)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Questions and Algorithms for Tensors<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1730<\/td>\r\n<td>1800<\/td>\r\n<td colspan=\"5\"><strong>Amit Deshpande<\/strong> (<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/amitdeshpande.pdf\" target=\"_self\">slides<\/a>)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Approximability of Subspace Approximation<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n<table class=\" tWiz tableBorder borderRows borderColumns\" style=\"height: 558px\" width=\"892\">\r\n<tbody>\r\n<tr>\r\n<td colspan=\"7\"><b>Thursday, January 6, 2011<\/b><\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"7\"><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>0930<\/td>\r\n<td>1000<\/td>\r\n<td colspan=\"5\">Tea\/Coffee<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1000<\/td>\r\n<td>1100<\/td>\r\n<td colspan=\"5\"><strong>R. Ravi <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan6-talk1.pdf\" target=\"_self\">slides<\/a>)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Matching Based Augmentations for Approximating Connectivity Problems<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1100<\/td>\r\n<td>1130<\/td>\r\n<td colspan=\"5\">Tea\/Coffee<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1130<\/td>\r\n<td>1230<\/td>\r\n<td colspan=\"5\"><strong>Sanjeev Arora <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan6-talk2.ppt\" target=\"_self\">slides<\/a>)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Algorithms for Approximating Graph Expansion and Connections to Geometry<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1230<\/td>\r\n<td>1400<\/td>\r\n<td colspan=\"5\">Lunch<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1400<\/td>\r\n<td>1500<\/td>\r\n<td colspan=\"5\"><strong>David Steurer <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/jan6-talk3.ppsx\" target=\"_self\">slides<\/a>)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Graph Expansion and the Unique Games Conjecture<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1500<\/td>\r\n<td>1505<\/td>\r\n<td colspan=\"5\">Break<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1505<\/td>\r\n<td>1605<\/td>\r\n<td colspan=\"5\"><strong>Lorenzo Orecchia <\/strong>(slides)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Fast Spectral Algorithms for Graph Partitioning and Graph Decomposition<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1605<\/td>\r\n<td>1630<\/td>\r\n<td colspan=\"5\">Tea\/Coffee<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1630<\/td>\r\n<td>1730<\/td>\r\n<td colspan=\"5\"><strong>Subhash Khot <\/strong>(slides)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Introduction to Hardness of Approximation and Probabilistically Checkable Proofs<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1730<\/td>\r\n<td>1800<\/td>\r\n<td colspan=\"5\"><strong>Saket Saurabh <\/strong>(slides)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Slightly Superexponential Parameterized Problems<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n<table class=\" tWiz tableBorder borderRows borderColumns\" style=\"height: 565px\" width=\"895\">\r\n<tbody>\r\n<tr>\r\n<td colspan=\"7\"><b>Friday, January 7, 2011<\/b><\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"7\"><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>0930<\/td>\r\n<td>1000<\/td>\r\n<td colspan=\"5\">Tea\/Coffee<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1000<\/td>\r\n<td>1100<\/td>\r\n<td colspan=\"5\"><strong>Subhash Khot <\/strong>(slides)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1100<\/td>\r\n<td>1130<\/td>\r\n<td colspan=\"5\">Tea\/Coffee<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1130<\/td>\r\n<td>1230<\/td>\r\n<td colspan=\"5\"><strong>Prasad Raghavendra <\/strong>(slides)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">How to Round Any CSP?<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1230<\/td>\r\n<td>1400<\/td>\r\n<td colspan=\"5\">Lunch<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1400<\/td>\r\n<td>1500<\/td>\r\n<td colspan=\"5\"><strong>Nikhil Devanur <\/strong>(slides)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">The Steiner Tree Problem<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1500<\/td>\r\n<td>1505<\/td>\r\n<td colspan=\"5\">Break<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1505<\/td>\r\n<td>1605<\/td>\r\n<td colspan=\"5\"><strong>Sambuddha Roy <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/sambuddha.pdf\" target=\"_self\">slides<\/a>)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Primal Dual Approximation Algorithms<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1605<\/td>\r\n<td>1630<\/td>\r\n<td colspan=\"5\">Tea\/Coffee<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1630<\/td>\r\n<td>1730<\/td>\r\n<td colspan=\"5\"><strong>Kamal Jain <\/strong>(slides)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Online Bipartite Matching via a Primal-Dual Technique for Convex Programs<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1730<\/td>\r\n<td>1800<\/td>\r\n<td colspan=\"5\"><strong>Vinayaka Pandit <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/vinayaka.pdf\" target=\"_self\">slides<\/a>)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Local Search Based Approximation Algorithms for Facility Location Problems<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n<table class=\" tWiz tableBorder borderRows borderColumns\" style=\"height: 591px\" width=\"893\">\r\n<tbody>\r\n<tr>\r\n<td colspan=\"7\"><b>Saturday, January 8, 2011<\/b><\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"7\"><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>0930<\/td>\r\n<td>1000<\/td>\r\n<td colspan=\"5\">Tea\/Coffee<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1000<\/td>\r\n<td>1100<\/td>\r\n<td colspan=\"5\"><strong>R. Ravi <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/prahladh.pptx\" target=\"_self\">slides<\/a>)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Iterative Methods in Combinatorial Optimization<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1100<\/td>\r\n<td>1130<\/td>\r\n<td colspan=\"5\">Tea\/Coffee<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1130<\/td>\r\n<td>1230<\/td>\r\n<td colspan=\"5\"><strong>Subhash Khot <\/strong>(slides)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">On the Unique Games Conjecture<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1230<\/td>\r\n<td>1400<\/td>\r\n<td colspan=\"5\">Lunch<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1400<\/td>\r\n<td>1500<\/td>\r\n<td colspan=\"5\"><strong>Prasad Raghavendra<\/strong> (slides)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Complexity of Constraint Satisfaction Problems: Exact and Approximate<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1500<\/td>\r\n<td>1505<\/td>\r\n<td colspan=\"5\">Break<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1505<\/td>\r\n<td>1605<\/td>\r\n<td colspan=\"5\"><strong>Prahladh Harsha <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/prahladh.pptx\" target=\"_self\">slides<\/a>)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Inapproximability Results from Label-Cover Variants and Other Hardness Assumptions<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1605<\/td>\r\n<td>1630<\/td>\r\n<td colspan=\"5\">Tea\/Coffee<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1630<\/td>\r\n<td>1730<\/td>\r\n<td colspan=\"5\"><strong>Madhur Tulsiani <\/strong>(<a title=\"\" href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/madhur.pdf\" target=\"_self\">slides<\/a>)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Introduction to LP and SDP Hierarchies<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1730<\/td>\r\n<td>1800<\/td>\r\n<td colspan=\"5\"><strong>L. Sunil Chandran <\/strong>(<a href=\"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2016\/10\/sunil.pdf\" target=\"_self\">slides<\/a>)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Rainbow Colouring of Graphs<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n&nbsp;\r\n<table class=\" tWiz tableBorder borderRows borderColumns\" style=\"height: 255px\" width=\"892\">\r\n<tbody>\r\n<tr>\r\n<td colspan=\"7\"><b>Sunday, January 9, 2011<\/b><\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"7\"><\/td>\r\n<\/tr>\r\n<tr>\r\n<td>0930<\/td>\r\n<td>1000<\/td>\r\n<td colspan=\"5\">Tea\/Coffee<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1000<\/td>\r\n<td>1100<\/td>\r\n<td colspan=\"5\"><strong>Amit Kumar<\/strong> (slides)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Scheduling to Minimize Weighted Flow-Time<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1100<\/td>\r\n<td>1130<\/td>\r\n<td colspan=\"5\">Tea\/Coffee<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1130<\/td>\r\n<td>1230<\/td>\r\n<td colspan=\"5\"><strong>Naveen Garg <\/strong>(slides)<\/td>\r\n<\/tr>\r\n<tr>\r\n<td colspan=\"2\"><\/td>\r\n<td colspan=\"5\">Fast Combinatorial Algorithms for Solving Positive Linear Programs<\/td>\r\n<\/tr>\r\n<tr>\r\n<td>1230<\/td>\r\n<td>1400<\/td>\r\n<td colspan=\"5\">Lunch<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>"},{"id":2,"name":"Speakers","content":"<ul>\r\n \t<li><a href=\"http:\/\/www.cs.princeton.edu\/~arora\/\">Sanjeev Arora <\/a>(Princeton)<\/li>\r\n \t<li><a href=\"http:\/\/www.cse.iitd.ernet.in\/~amitk\/\">Amit Kumar<\/a> (IIT Delhi)<\/li>\r\n \t<li><a href=\"http:\/\/drona.csa.iisc.ernet.in\/~sunil\/\">Sunil Chandran<\/a>\u00a0(Indian Institute of Science)<\/li>\r\n \t<li><a href=\"http:\/\/www.cs.berkeley.edu\/~orecchia\/\">Lorenzo Orecchia <\/a>(Berkeley)<\/li>\r\n \t<li>Amit Deshpande (Microsoft Research)<\/li>\r\n \t<li><a href=\"https:\/\/researcher.ibm.com\/researcher\/view.php?person=in-pvinayak\">Vinayaka Pandit <\/a>(IBM IRL)<\/li>\r\n \t<li>Nikhil Devanur (Microsoft Research)<\/li>\r\n \t<li><a href=\"http:\/\/www.scs.gatech.edu\/people\/prasad-raghavendra\">Prasad Raghavendra<\/a> (Georgia Tech)<\/li>\r\n \t<li><a href=\"http:\/\/www.cse.iitd.ernet.in\/~naveen\/\">Naveen Garg<\/a> (IIT Delhi)<\/li>\r\n \t<li><a href=\"http:\/\/www2.tepper.cmu.edu\/andrew\/ravi\/\"> R. Ravi<\/a> (Carnegie Mellon)<\/li>\r\n \t<li><a href=\"http:\/\/www.tcs.tifr.res.in\/~prahladh\/\">Prahladh Harsha <\/a>(TIFR)<\/li>\r\n \t<li><a href=\"https:\/\/researcher.ibm.com\/researcher\/view.php?person=in-sambuddha\">Sambuddha Roy <\/a>(IBM IRL)<\/li>\r\n \t<li>Kamal Jain (Microsoft Research)<\/li>\r\n \t<li><a href=\"http:\/\/www.imsc.res.in\/~saket\/\">Saket Saurabh<\/a> (IMSc, Chennai)<\/li>\r\n \t<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/kannan\/\">Ravi Kannan<\/a> (Microsoft Research)<\/li>\r\n \t<li><a href=\"http:\/\/www.cs.mcgill.ca\/~mohit\/\">Mohit Singh<\/a> (McGill University)<\/li>\r\n \t<li><a href=\"http:\/\/www.eecs.berkeley.edu\/~karp\/\">Richard Karp <\/a>(Berkeley)<\/li>\r\n \t<li><a href=\"http:\/\/www.cs.princeton.edu\/~dsteurer\/\">David Steurer<\/a> (Microsoft Research)<\/li>\r\n \t<li><a href=\"http:\/\/www.cs.nyu.edu\/~khot\/\">Subhash Khot<\/a> (New York University)<\/li>\r\n \t<li><a href=\"http:\/\/www.math.ias.edu\/~madhurt\/\">Madhur Tulsiani<\/a> (Princeton\/IAS)<\/li>\r\n<\/ul>"}],"msr_startdate":"2011-01-05","msr_enddate":"2011-01-09","msr_event_time":"","msr_location":"Bangalore, India","msr_event_link":"","msr_event_recording_link":"","msr_startdate_formatted":"January 5, 2011","msr_register_text":"Watch now","msr_cta_link":"","msr_cta_text":"","msr_cta_bi_name":"","featured_image_thumbnail":null,"event_excerpt":"The focus of this school will be the approximability of optimization problems. Traditionally, approximability used to be a two-pronged task divided into algorithms and complexity but recently, a lot of cross-fertilization is taking place and the boundaries between algorithms and complexity are blurring. One of the goals of this school would be to further bring down this divide and promote a holistic thinking about approximability, which should lead to exciting new developments in the area.&hellip;","msr_research_lab":[199562],"related-researchers":[],"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\/310601","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":2,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/310601\/revisions"}],"predecessor-version":[{"id":1147217,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/310601\/revisions\/1147217"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=310601"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=310601"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=310601"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=310601"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=310601"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=310601"},{"taxonomy":"msr-program-audience","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-program-audience?post=310601"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=310601"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=310601"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}