MSR India Winter School 2012

Summary

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 was held on 18-22 December 2012 on the IIIT-H campus, Hyderabad, India, following the conference Foundations of Software Technology and Theoretical Computer Science (FSTTCS). The agenda included talks by eminent speakers like Sanjeev Arora, Cynthia Dwork, R Ravi, and C. Pandu Rangan.

Videos

Differential Privacy - Lecture 1

How to Approximate it? Introduction and Greedy Algorithms - Part 1

R. Ravi | Video

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.

Greedy Algorithms - Part 2

R. Ravi | Video

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.

Towards Provable Bounds for Machine Learning - Lecture 1

Sanjeev Arora | Video

Differential Privacy - Lecture 2

Towards Provable Bounds for Machine Learning - Lecture 2 Part 1

Sanjeev Arora | Video

Towards Provable Bounds for Machine Learning - Lecture 2 Part 2

Sanjeev Arora | Video

Local Search

R. Ravi | Video

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).

Differential Privacy - Lecture 3

Towards Provable Bounds for Machine Learning - Lecture 3

Sanjeev Arora | Video

Linear Programs and Deterministic Rounding

R. Ravi | Video

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.

Differential Privacy - Lecture 4

Towards Provable Bounds for Machine Learning - Lecture 4

Sanjeev Arora | Video

Filtering and the Primal-Dual Method - Part 1

R. Ravi | Video

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.

Filtering and the Primal-Dual Method - Part 2

R. Ravi | Video

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.

Differential Privacy - Lecture 5

Metric Rounding of LP Relaxations

R. Ravi | Video

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.

Identity-Based Deterministic Signature Scheme Without Forking-Lemma

Prof. Pandu Rangan | Video