Home > Groups > Theory > Seminar
Microsoft Research Open Problems
The list below contains the open problems presented at Microsoft Research Theory Lunch.
A list of open problems for internal access only can be found here

2013:

May 8 Questions from Kunal Talwar on Makespan Scheduling (see PDF) and Russ Lyons on Herding Cats (see PDF)
April 10 Questions from Mohit Singh on Asymmetric Traveling Salesman (see PDF)
April 3 Questions from Debmalya Panigrahi on Online Steiner Tree and Forest (see PDF)
March 27 Questions from Bella Bollobas on the Number of Graph Colorings (see PDF)
March 13 Questions from Nikhil Devanur on Online Bipartite Matching (see PDF)
February 28 Questions from Bella Bollobas on Neighborhood Bootstrap Percolation (see PDF)
January 23 Questions from Alexander Holroyd on Dyck Words (see PDF) and Debmalya Panigrahi on Additive Spanners (see PDF)

2012:

December 19 Questions from Ola Svensson on Precedence Scheduling (see PDF)
December 5 Questions from Kostya Makarychev on Random Ordering CSP (see PDF)
November 21 Questions from Elad Hazan on Linear Classification (see PDF)
October 10 Questions from Geoffrey Grimmet on Self Avoiding Walks (see PDF)
October 3 Questions from Tom Bohman on random bipartite graphs (see PDF)
September 19 Questions from Jeff Steif on the sensitiviy of boolean functions (see PDF)
September 12 Questions from Shayan Oveis Gharan on random walks and Yuval Peres on the critical probability of random graphs (see PDF)
September 5 Questions from Russell Lyons on Glauber Dynamics and Yuval Peres on another interesting hat question (see PDF)
August 29 Questions from Mohit Singh on demand matchings and distributions over independent sets on trees (see PDF)
August 22 Questions from László Lovász on when to stop a Monte-Carlo Markov chain (see PDF)
August 8 Questions from László Lovász on distances of random graphs (see PDF)
May 24 Questions from Alexander Holroyd on perfect shuffling by random transpositions (see PDF)
May 17 Questions from Chandra Chekuri on complexity of submodular partitioning (see PDF)
February 15 Questions from Roberto Imbuzeiro Oliveira on the cat-and-mouse game (see PDF) and Serguei Popov on the range of many-dimensional martingales (see PDF)

2011:

October 5 Questions from Pawel Pralat on the firefighter problem (see PDF) and Nicolas Curien on Rémy's algorithm for generating random binary trees (see PDF)
September 28 Questions from Pawel Pralat on the cops and robbers problem (see PDF)
September 14 Questions from Ben Morris (see PDF)
September 7 Questions from Peter Winkler (see PDF)
August 31 Questions from Alexandre Stauffer on balls and bins (see PDF)