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, algorithms, statistical learning, optimization, algorithmic game theory, errorcorrecting codes, combinatorics, statistical physics, and fractals. We host an amazing array of researchers in these areas, see below for a list of recent and upcoming visitors.
See the Theory Seminar page for a list of upcoming and recent talks (often recorded on video).
People
Theory Group  members
Interests: machine learning, convex optimization, multiarmed bandits, random graphs and random matrices, combinatorial statistics, information theory  
Interests: machine learning and algorithms, multiarmed bandits, online learning, optimization  

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 
Interests: Probability theory, with emphasis on discrete spatial models, including cellular automata, percolation, matching, coupling  
Interests: Approximation algorithms and combinatorial optimization, in particular, semidefinite programming and questions related to functional analysis and metric geometry  
Interests: Random walks, Percolation, Mixing times of Markov chains, Brownian motion, Determinantal point processes, Fractals and Hausdorff dimension, Phase transitions, Ergodic theory, Game theory  

Interests: Approximation Algorithms, Combinatorial Optimization with applications in network design. Also interested in models and problems dealing with uncertainty in data 
Interests: Probability theory, including statistical physics, SLE, Markov chains, and randomized algorithms  
Interests: Errorcorrecting codes, Combinatorics, Complexity Theory 
The group reports to Chris Meek.
Postdocs
Interests: Approximation algorithms, Online algorithms, Online learning, Game theory, Differential privacy and Dataanalytics.
 
Interests: Probability theory and its applications, including combinatorial statistics, networks, voting, interacting particle systems, game theory, and mathematical biology.  
Interests: information theory, control theory, wireless communication, crowdsourcing and other related areas

Recent and upcoming visitors
Nick Harvey  20 days during (10/12/2015  12/18/2015) 
Yury Makarychev  (10/21/2015  10/23/2015) 
Omer Angel  (10/22/2015  10/25/2015) 
Balint Virag  (10/23/2015  10/25/2015) 
Bob Hough  (10/24/2015  10/30/2015) 
Matus Telgarsky  (10/26/2015  10/29/2015) 
Lionel Levine  (10/26/2015  11/8/2015) 
Chris Bishop  (11/1/2015  11/8/2015) 
Victoria Kostina  (11/16/2015  11/20/2015) 
Ilya Razenshteyn  (11/16/2015  11/20/2015) 
Tianyi Zheng  (11/23/2015  11/27/2015) 
Yury Makarychev  (11/30/2015  12/11/2015) 
Lionel Levine  (12/28/2015  1/12/2016) 
Marta Lewicka  (1/2/2016  1/5/2016) 
Perla Sousi  (1/2/2016  1/6/2016) 
Chris Bishop  (1/2/2016  1/12/2016) 
Robin Pemantle  (1/3/2016  1/5/2016) and (2/1/2016  2/5/2016) 
James Martin  (1/25/2016  5/6/2016) 
Rachel Vishnepolsky  (2/1/2016  2/5/2016) 
Nina Holden  (2/1/2016  2/5/2016) 
David Harris  (2/8/2016  2/11/2016) 
Ronen Eldan  (2/21/2016  3/3/2016) 
Zhongyang Li  (3/14/2016  3/18/2016) 
Victoria Kostina  (3/21/2016  3/25/2016) 
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, socalled 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 2016 received by December 1, 2015 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.
Additional Links
 Directions to MSR
 Probability in Seattle
 The UWMSR Theory Center
 Past Members, Postdocs and Interns.
 MSR supported lectures:
 Minicourse on New Random Geometries (2009)
In memoriam
 Oded Schramm (died in a tragic accident, September 2008):
Oded's interests: Percolation, two dimensional random systems, critical systems, SLE, conformal mappings, dynamical random systems, discrete and coarse geometry, mountains 