Jason Miller (9/27/2010-6/30/2012) Interests: All forms of probability theory, with a focus on stochastic interface models such as random surfaces and SLE.
	Shaddin Dughmi (8/15/2011-6/30/2012) Interests: Algorithms, combinatorial optimization, game theory, mechanism design.
	Alexandre Stauffer (7/5/2011-6/30/2012) Interests: Random walks, percolation, interacting particle systems, mixing time of Markov chains, randomized algorithms.

 

Visiting Researchers

• Long-term visitors (see complete list here)

	James Lee (9/6/2011-12/16/2011) Interests: Application of analysis and geometry in various areas of theoretical computer science, including approximation algorithms, geometric search, and spectral analysis.
	Peter Winkler (9/6/2011-12/2/2011)  Interests: Application of combinatorics and probability to the theory of computing; in particular, random walk, percolation, and games.
	Russell Lyons (8/1/2011-10/30/2011) Interests: Discrete probability, ergodic theory, geometric group theory, and statistics.
	Yossi Azar (7/11/2011-9/2/2011). Interests: Discrete optimization and combinatorial algorithms; in particular, resource allocation, scheduling, load balancing, graph algorithms, online and approximations algorithm, algorithmic game theory etc.
	Bruce Shepherd (7/1/2011-12/31/2011). Interests: Optimization, especially combinatorial optimization and graph theory. His recent work has focused on robust optimization of networks and the disjoint paths problem.
	Manor Mendel (6/27/2011-1/6/2012)  Interests: Geometry of discrete metric spaces, and algorithms that use metric data.

• Upcoming long-term visitors

• Full list of visitors (including short-term visitors) is available here.

In memorial

• 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

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 2012 received by December 15, 2011 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 for 2012 and inform us that you have applied by emailing theoryap@microsoft.com.

Additional Links

• Directions to MSR
• Probability in Seattle
• The UW-MSR Theory Center
• Past Members, Postdocs and Interns.
• MSR supported lectures:
  • Minicourse on New Random Geometries (2009)