Long-Term Visitors for 2008-2009

Yossi Azar (7/5/06-6/30/09) Interests: Design and analysis of algorithms, Scheduling, Load-balancing, Routing, Randomized algorithms, Optimization and Game Theory.

David Aldous (6/29/09-6/30/10) Interests: Various topics in mathematical and applied probability. Current focus: (i) spatial random networks (ii) articulating what probability asserts about the real world that is empirically verifiable. Career research: large finite random structures (trees, graphs, networks), distances and flows therein; infinite and continuum limits theoreof. Stochastic coalescence, random walks, Markov chains and mixing times, exchangeability, Poisson approximation, weak convergence.

 Postdocs

	Nikhil Devanur (10/6/08-6/30/10) 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.
	Ori Gurel-Gurevich (7/7/08-6/30/10)  Interests: All aspects of Probability: from Random walks to Measure Theory, from Stochastic Processes to Percolation. Set Theory and Logic.
	Asaf Nachmias (7/7/08-6/30/10) Interests: Probability Theory & Statistical Physics, with emphasis on Percolation, Random Walks and Mixing time of Markov chains.
	Allan Sly (7/6/09-6/30/11) Interests: Probability Theory and Statistical Physics, particularly MCMC, Markov models on trees, random walks.

 Former permanent members

• Christian Borgs (now Deputy Director of Microsoft Research New England)
• Jennifer T. Chayes (now Director of Microsoft Research New England)
• Henry Cohn (now at Microsoft Research New England)
• Uriel Feige (now at Weizmann Institute, Israel)
• Mike Freedman (now Director of Microsoft Station Q)
• Jeong Han Kim (now at Yonsei University, Korea)
• László Lovász (now at Eötvös Loránd University, Hungary)
• Assaf Naor (now at Courant Institute of Mathematical Sciences, NYU)

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.
 

Applying for Positions

• Applications for a Post-doctoral Researcher position are due by December 15, 2009.
  Apply here, and in addition, have your application material (including references) sent to theoryap@microsoft.com.
• Applications for summer internships are due by February 28, 2010.
  Apply here, and in addition, have your application material (including references) sent to theoryap@microsoft.com.

Additional Links

• Past Visitors, Postdocs and Interns.