Theory Group

The Theory Group was founded in 1997 by Jennifer T. Chayes and Christian Borgs. 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 the areas of expertise we have are probability theory, combinatorics, statistical physics, metric geometry, fractals, algorithms and optimization. We also collaborate with the Mathematics and Computer Science Departments at the University of Washington (see Probability in Seattle and Theoretical Computer Science at UW).

Theory Group (Redmond) - Permanent members

	Kamal Jain Interests: semantics theory, coding theory, cryptography, combinatorics, networking, information theory, game theory and algorithms
	Eyal Lubetzky Interests: Probabilistic methods in Combinatorics, Extremal Combinatorics, Random graph models and processes, Random walks, Mixing times of Markov chains.
	Yuval Peres (Manager) Interests: Random walks, Percolation, Mixing times of Markov chains, Brownian motion, Determinantal point processes, Fractals and Hausdorff dimension, Phase transitions, Ergodic theory, Game theory
	Oded Schramm Interests: Percolation, two dimensional random systems, critical systems, SLE, conformal mappings, dynamical random systems, discrete and coarse geometry, mountains
	David Wilson Interests: statistical physics, dimers, SLE, Markov chain mixing times, randomized algorithms

Long-Term Visitors for 2008

	Yossi Azar (7/5/06-6/30/09) Interests: Design and analysis of algorithms, Scheduling, Load-balancing, Routing, Randomized algorithms, Optimization and Game Theory.
	Itai Benjamini (7/23/07-6/27/08)
	Marek Biskup (7/23/07-6/27/08)
	Alexander Holroyd (1/1/08-6/27/08)

Postdocs

	Reid Andersen (7/2/07-6/30/09) Interests: Graph partitioning and community identification, local approximation algorithms, algorithms for large graphs and datasets.
	Mohsen Bayati (7/2/07-6/30/09) Interests: Analysis and applications of random graphs, distributed algorithms, combinatorial optimization, and machine learning in networking, coding theory, computational biology, and social networks.
	Abie Flaxman (7/24/06-6/30/08) Interests: Measurements, models, algorithms, and decision making for complex networks.
	Satyen Kale (8/6/07-6/30/09) Interests: Design and analysis of algorithms, combinatorial optimization, mathematical programming, machine learning, and game theory.
	Yury Makarychev (7/9/07-6/30/09) Interests: Approximation algorithms, low distortion metric embeddings, random walks.
	Vahab Mirrokni (6/30/06-6/30/08) Interests: Algorithmic game theory, approximation algorithms, algorithms and economics of the Internet, social network analysis.
	Gabor Pete (7/17/06-6/30/08) Interests: Critical discrete systems and their scaling limits (noise and dynamical sensitivity, SLE, critical exponents). Percolation, random walks and geometry on infinite groups. PDE and game theory.
	Sebastien Roch (7/23/07-6/30/09) Interests: Markov models on trees, computational phylogenetics. Stochastic processes on graphs, evolutionary dynamics, social network analysis. Learning theory.
	Asaf Shapira (8/21/06-6/30/08) Interests: Randomized, approximation and sublinear algorithms. Discrete mathematics and extremal combinatorics.

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.