Microsoft Research India, in collaboration with the Indian Institute of Technology Madras (IITM), will host the Third Annual Microsoft Research India Theory Day on 2nd January 2010 at the IITM campus in Chennai, India.
The Theory Day is a day-long annual event. It features talks by world-renowned researchers in theoretical computer science (TCS) on latest research. The talks are intended to be accessible to advanced post-graduate students and be valuable to established researchers. It is hoped that Theory Day will inspire and stimulate young researchers to make new advances in this exciting field.
This page includes information on the Theory Day program and also the key dates. Please note that past experience suggests that many more students than we could possibly accommodate are interested in attending, so we are constrained to select student attendees via a competitive process. While students would comprise the bulk of the attendees, we also expect to have participation from post-doctoral researchers, faculty members and research staff, selected based on the applications we receive.
Venue
Indian Institute of Technology Madras (IITM) campus, Chennai, India
Speakers
Following are the speakers for the Theory Day. Talk abstracts are given at the bottom of this page.
| Naveen Garg, Indian Institute of Technology, Delhi |
| Navin Goyal, Microsoft Research India |
| Piotr Indyk, Massachusetts Institute of Technology |
| Satya Lokam, Microsoft Research India |
| R. Ravi, Carnegie Mellon University |
| Manfred K. Warmuth, University of California, Santa Cruz |
Organizing Committee
Ravi Kannan, Microsoft Research India
Satya Lokam, Microsoft Research India
C. Pandu Rangan, Indian Institute of Technology Madras
How to attend the Microsoft Research India Theory Day
The last date for applying to attend the Theory Day has passed. The organizing committee shall not accept any more applications. All applicants will be notifed of their selection status according to the date mentioned below.
Important Dates
Announcement of selected attendees: Tuesday, November 10th 2009
Theory Day date: Saturday, January 2nd 2010
Please Note:
- Microsoft Research India shall provide for travel, lodging and boarding of all attendees that come from within India, outside of Chennai, for the Theory Day.
- There are no fees that attendees have to pay for the Theory Day.
- Attendees from outside India are welcome to apply though Microsoft Research India will only provide them accommodation in Chennai and no travel funds.
For any enquiries, please email msritdap@microsoft.com.
Previous Editions of Theory Day
First annual Microsoft Research India Theory Day - December 2007
Second annual Microsoft Research India Theory Day - December 2008
Talk Abstracts
Title: Minimizing Average Flow-time
Speaker: Naveen Garg, Indian Institute of Technology, Delhi
In this talk I will consider the problem of scheduling jobs on multiple machines both in the online and offline settings. I will attempt to identify the key ideas in recent work on this problem for different machine models.
Title: Sparse Recovery Using Sparse Random Matrices
Speaker: Piotr Indyk, Massachusetts Institute of Technology
Over the recent years, a new linear method for compressing high-dimensional data (e.g., images) has been discovered. For any high-dimensional vector x, its sketch is equal to Ax, where A is an m x n matrix (possibly chosen at random).
Although typically the sketch length m is much smaller than the number of dimensions n, the sketch contains enough information to recover an approximation to x. At the same time, the linearity of the sketching method is very convenient for many applications, such as data stream computing and compressed sensing.
The major sketching approaches can be classified as either combinatorial (using sparse sketching matrices) or geometric (using dense sketching matrices). They achieve different trade-offs, notably between the compression rate and the running time. Thus, it is desirable to understand the connections between them, with the goal of obtaining the "best of both worlds" solution.
Several recent results established such connections, indicating that the two approaches are just different manifestations of the same underlying phenomenon.
This enabled the development of novel algorithms, including the first algorithms that provably achieve the (asymptotically) optimal compression rate and near-linear recovery time simultaneously.
In this talk we give an overview of the results in the area, as well as look at some of them in more detail. In particular, we will describe a new algorithm, called "Sequential Sparse Matching Pursuit (SSMP)". In addition to having the aforementioned theoretical guarantees, the algorithm works well on real data, with the recovery quality often outperforming that of more complex algorithms, such as l_1 minimization.
Joint work with: Radu Berinde, Anna Gilbert, Howard Karloff, Milan Ruzic and Martin Strauss.
Title: Iterative Methods in Combinatorial Optimization
Speaker: R. Ravi, Carnegie Mellon University
In this talk, I will describe a simple iterative method for proving a variety of results in combinatorial optimization. It is inspired by Jain's iterative rounding method for designing
approximation algorithms for survivable network design problems, and augmented with a relaxation idea in the work of Lau, Naor, Salvatipour and Singh in their work on designing an approximation algorithm for its degree bounded version. Its application was further refined in recent work of Bansal, Khandekar and Nagarajan on degree-bounded directed network design.
In this talk, I will describe its application to showing the integrality of Edmond's characterization of the spanning tree polyhedron and then extend the argument to show a simpler proof of the Lau-Singh approximation algorithm for its degree
constrained version. I will conclude by showing how Jain's original proof can be much simplified by the new perspective, by unifying its treatment with that for the STSP problem.
This talk describes work of all the above authors interpreted in collaboration with Lau, Nagarajan and Singh.
Title: The blessing and the curse of the multiplicative updates - discusses connections between in vitro selection, and the multiplicative updates of online learning
Speaker: Manfred K Warmuth, UC Santa Cruz
Multiplicative updates multiply the parameters by nonnegative factors. These updates are motivated by a Maximum Entropy Principle and they are prevalent in evolutionary processes where the parameters are for example concentrations of species and the factors are survival rates. The simplest such update is Bayes rule and we give an in vitro selection algorithm for RNA strands that implements this rule in the test tube where each RNA strand represents a different model. In one liter of the RNA soup there are approximately 10^20 different strands and therefore this is a rather high-dimensional implementation of Bayes rule.
We investigate multiplicative updates for the purpose of learning online while processing a stream of examples. The ``blessing'' of these updates is that they learn very fast
because the good parameters grow exponentially. However their ``curse'' is that they learn too fast and wipe out parameters too quickly. We describe a number of methods developed in the realm of online learning that ameliorate the curse of these updates. The methods make the algorithm robust against data that changes over time and prevent the currently good parameters from taking over. We also discuss how the curse is circumvented by nature. Some of nature's methods parallel the ones developed in Machine Learning, but nature also has some additional tricks.
This will be a high level talk. No background in online learning or Biology will be required.
