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

A list of open problems for internal access only can be found here

# 2016:

June 1 | Questions from Sahil Singla on adaptivity gaps for stochastic probing (see PDF) |

March 16 | Questions from Ilya Shkredov on sum-products in the prime field (see PDF) |

February 3 | Questions from Robin Pemantle on random Boolean functions (see PDF) |

# 2015:

September | Questions from Alexander Holroyd on Permutations and Moves (see PDF) |

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