Theory Group

We work on fundamental problems in mathematics and theoretical computer science, interact extensively with the academic community and collaborate with other researchers at MSR on challenging applied problems. Among our areas of expertise are probability theory, combinatorics, statistical physics, metric geometry, fractals, algorithms and optimization. We host an amazing array of researchers in these areas: see a full list here.

People

Theory Group - Permanent members

 S. Bubeck

Sebastien Bubeck 

Interests: machine learning, combinatorial statistics, multi-armed bandits, online learning, stochastic optimization, convex optimization

 N. Devanur

Nikhil Devanur

Interests: Fundamental algorithmic problems such as graph partitioning and network design. Algorithmic challenges in economics and game theory, such as computing market equilibrium and auction design

 A. Holroyd

Alexander Holroyd

Interests: Probability theory, with emphasis on discrete spatial models, including cellular automata, percolation, matching, coupling

 
 E. Lubetzky

Eyal Lubetzky

Interests: Statistical Physics, Mixing times of Markov chains, Random graphs, Random walks, Probabilistic Combinatorics

 

Kostya Makarychev

Interests: Approximation algorithms and combinatorial optimization, in particular, semidefinite programming and questions related to functional analysis and metric geometry

 Y. Peres

Yuval Peres

Interests: Random walks, Percolation, Mixing times of Markov chains, Brownian motion, Determinantal point processes, Fractals and Hausdorff dimension, Phase transitions, Ergodic theory, Game theory 

Mohit Singh

Interests: Approximation Algorithms, Combinatorial Optimization with applications in network design. Also interested in models and problems dealing with uncertainty in data

 D. Wilson

David B. Wilson

Interests: statistical physics, dimers, SLE, Markov chain mixing times, randomized algorithms 

Postdocs

Balu Sivan (7/22/2013 - 6/30/2015)

Interests: Approximation and online algorithms with stochastic input, prior robust/independent optimization, algorithmic game theory, and mechanism design in particular 

Roy Schwartz (7/2/2012 - 6/30/2014)

Interests: theory of algorithms, approximation algorithms, metric methods and their algorithmic applications, and submodular optimization

 

 

Visiting Researchers

  • Long-term visitors (see complete list here)

 Jeff Steif (8/13/2012 - 7/5/2013)

 Interests: Probability theory, ergodic theory, statistical mechanics

 Béla Bollobás (2/4/2013 - 5/31/2013)

 Interests: Extremal graph theory, Functional analysis, Random graphs, Graph polynomials, Percolation

 Anna Karlin (1/2/2013 - 6/28/2013)

 Interests: Algorithmic game theory, probabilistic and online algorithms

 David Levin (3/18/2013 - 6/14/2013)

 Interests: Markov chains and mixing times, Statistical Physics, dynamical random walks, Gaussian processes, flows in networks 

 Russell Lyons (5/13/2013 - 8/2/2013)

 Interests: Random walks on graphs, probability on trees, geometric group theory, ergodic Theory, percolation, harmonic analysis, determinantal processes

 Shuchi Chawla

 Shuchi Chawla (9/3/2013 - 1/17/2013)

 Interests: Design and analysis of algorithms, algorithmic game theory and mechanism design, combinatorial and stochastic optimization. I am also interested in networking (specifically, applications of game theory in networking) and machine learning

 

Ronen Eldan (8/12/2013 - 6/30/2014)

Interests: Phenomena in High Dimensions, Convex and metric geometry, Concentration of measure, Isoperimetric inequalities, Functional inequalities, Algorithmic Convex Geometry, Stochastic processes, Probability theory

 

Fabio Martinelli (7/1/2013 - 10/18/2013)

Interests: Probabilistic models, Randomized algorithms, Glauber dynamics, Phase transition 

  • Recent and upcoming visitors
Allan Sly  3/25/13 - 6/21/13 
Janko Gravner  3/25/13 - 4/12/13
Christopher Bishop  2/7/13 - 4/10/13 
Robin Pemantle  5/6/13 - 5/10/13 
Lionel Levine  5/6/13 - 5/14/13 
Vladislav Vysotsky  5/13/13 - 5/29/13 
James Martin  5/15/13 - 6/11/13 
Richard Kenyon  6/10/13 - 8/23/13 
Yuval Rabani  6/21/13 - 7/5/13 
Jeff Kahn  7/1/13 - 7/26/13 
R. Ravi 7/8/13 - 7/19/13 
Uri Feige   7/8/13 - 7/19/13 
Adrien Kassel  7/15/13 - 8/9/13 
Seffi Naor  7/15/13 - 8/26/13 
Yossi Azar  7/25/13 - 8/16/13 
Amir Dembo  7/29/13 - 8/9/13 
Elchanan Mossel  7/29/13 - 8/16/13 
Laura Florescu  7/29/13 - 8/23/13 
Lionel Levine 

7/29/13 - 8/3/13 

Perla Sousi  7/29/13 - 8/16/13 
Nati Linial  8/1/13 - 8/21/13 
James Propp   8/5/13 - 8/16/13 
Jian Ding 8/5/13 - 9/6/13 
Nike Sun  8/5/13 - 9/6/13 
Alex Zhai  8/26/13 - 9/13/13 
Nikhil Bansal  8/26/13 - 9/6/13 
Anna Karlin  8/26/13 - 2/28/14 
James Norris  9/3/13 - 9/13/13 
Greta Panova  9/3/13 - 9/13/13 
James R. Lee  9/16/13 - 3/14/14 
Roberto Imbuzeiro Oliviera  10/7/13 - 11/1/13 
Lionel Levine 

11/18/13 - 12/20/13 

Christopher Bishop  1/9/14 - 4/26/14 
David Levin   1/20/14 - 1/23/14 
Boris Solomyak  1/20/14 - 6/30/14 
Itai Benjamini  2/3/14 - 2/14/14 
David Aldous  2/10/14 - 2/14/14 
James R. Lee  3/24/14 - 6/15/14 
Laszlo Vegh  3/31/14 - 4/11/14 
David Gamarnik  4/21/14 - 4/25/14 
Omer Angel  5/5/14 - 5/9/14 
Peter Moerters  5/5/14 - 5/16/14 
James Propp  5/19/14 - 5/30/14 
Lionel Levine  5/29/14 - 8/22/14 
Benjamin Sudakov  6/23/14 - 7/4/14 
Michael Krivelevich  6/23/14 - 7/4/14 
David Levin  8/4/14 - 8/29/14 

 

In memoriam

  • Oded Schramm (died in a tragic accident, September 2008):
  • Oded Schramm

    Oded's interests: Percolation, two dimensional random systems, critical systems, SLE, conformal mappings, dynamical random systems, discrete and coarse geometry, mountains 

Topics of Study

The problems on which we are focusing can be broadly classified in three areas: Probability Theory; Combinatorics and Graph Theory; Algorithms and Optimization.

Probability Theory. Here we consider systems with many degrees of freedom, and study dramatic changes in the behavior of these systems as we vary a control parameter. An example which is studied in our group is the phase transition in the random satisfiability problem. Here one studies random logical formulas in conjunctive normal form involving many Boolean variables. As the formulas get longer, there is a phase transition from formulas which are almost always satisfiable to formulas which are almost never satisfiable. Numerical evidence indicates that the hardest instances of the problem are concentrated at the phase transition. We study this phase transition and possible applications of the hardness of the phase transitions to cryptography. Other possible applications of the phase transition work are to image processing (where certain ferromagnetic statistical mechanical models, so-called Potts models, are used to model the colors of different pixels in the image), networks and decision theory.

Combinatorics and Graph Theory. In addition to the more novel efforts of the group, we also do a substantial amount of work on more traditional combinatorics, including graph theory, extremal combinatorics, random graphs, and enumeration. Probabilistic methods play a central role, including advanced probabilistic techniques like high concentration, nibble methods, and Markov chains. Interactions with classical mathematical disciplines like algebra and geometry are explored. These studies provide the theoretical foundations for the application of combinatorial methods in the analysis of algorithms and complexity theory. They also are closely tied with the theory of phase transitions.

Algorithms and Optimization. Algorithms for a variety of problems arising in computing, from data structures to networking, make use of mathematical methods. Our group has expertise in a variety of these methods, including combinatorial optimization, network algorithms and sampling algorithms through rapid mixing. The analysis of algorithms involving probability (either through a random input or an internal random number generation) is a difficult question, which requires the most advanced techniques from discrete probability.

( See recent talks at the Theory Group Seminar )

Applying for Positions

  • Applications for a Postdoctoral Researcher position for 2014 received by December 15, 2013 will receive full consideration.
    Apply here, and in addition, have your application material (including references) sent to theoryap@microsoft.com.
  • Apply here for a summer internship and inform us that you have applied by emailing theoryap@microsoft.com.