Theory Group

Theory Group

Established: February 3, 1997

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, error-correcting 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 for a list of upcoming and recent talks (often recorded on video).

The group reports to Chris Meek.

Applying for Positions

  • Applications for a Postdoctoral Researcher position for 2017 received by December 1, 2016 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.

Members

 Sebastien Bubeck

 Sebastien Bubeck

Interests: machine learning, convex optimization, multi-armed bandits, random graphs and random matrices, combinatorial statistics, information theory

 Ofer Dekel

 Ofer Dekel

Interests: machine learning and algorithms, multi-armed bandits, online learning, optimization

 Nikhil 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

 Alexander Holroyd

Alexander Holroyd

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

 Yuval 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

 David B. Wilson

David B. Wilson

Interests: Probability theory, including statistical physics, SLE, Markov chains, and randomized algorithms

 Sergey Yekhanin

Sergey Yekhanin

Interests: Error-correcting codes, Combinatorics, Complexity Theory

Postdocs

 Janardhan Kulkarni

Janardhan Kulkarni

Interests: Approximation algorithms, Online algorithms, Online learning, Game theory, Differential privacy and Data-analytics

 Yin Tat Lee

Yin Tat Lee

Interests: convex optimization, spectral graph theory, online learning and approximation algorithms

 Miklos Z. Racz

Miklos Z. Racz

Interests: statistical inference problems on random graphs and in genomics; applied probability, combinatorial statistics, information theory

 

Gireeja Ranade

Interests: information theory, control theory, wireless communication, crowdsourcing and other related areas

Visitors

Recent and Upcoming Visitors

Anna KarlinOne day per week
James LeeOne day per week
Ryokichi Tanaka(2/1/2016 – 2/28/2017)
David Levin(9/12/2016 – 9/16/2016)
Tianyi Zheng(9/12/2016 – 9/16/2016)
Alex Zhai(9/12/2016 – 9/23/2016)
Jonathan Hermon(9/19/2016 – 9/24/2016)
Robin Pemantle(9/25/2016 – 9/29/2016)
Victoria Kostina(10/10/2016 – 10/14/2016)
Oanh Nguyen(10/10/2016 – 10/14/2016)
Marta Lewicka(10/18/2016 – 10/23/2016)
Lionel Levine(10/31/2016 – 11/4/2016)
Yuval Rabani(10/31/2016 – 11/11/2016)
Costis Daskalakis(11/15/2016 – 11/23/2016)
Matt Weinberg(11/29/2016 – 12/9/2016)
Russell Lyons(12/5/2016 – 12/13/2016)
Izabella Stuhl(12/6/2016 – 12/10/2016)
David Levin(12/11/2016 – 12/16/2016)
Alex Zhai(12/11/2016 – 12/16/2016)
Nina Holden(1/4/2017 – 1/27/2017)
Alex Zhai(1/8/2017 – 1/20/2017)
Bob Hough(1/9/2017 – 1/13/2017)
Lisa Hartung(1/15/2017 – 1/20/2017)
Marta Lewicka(1/15/2017 – 1/20/2017)
Ronen Eldan(1/20/2017 – 2/15/2017)
Claire Mathieu(1/30/2017 – 2/24/2017)
Chris Bishop(2/18/2017 – 2/27/2017)
Reza Gheissari(2/20/2017 – 2/25/2017)
Jim Propp(2/20/2017 – 2/24/2017)
Alex Zhai(2/20/2017 – 3/3/2017)
Omer Angel(2/27/2017 – 3/3/2017)
Abbas Mehrabian(2/27/2017 – 3/3/2017)
Geoffrey Grimmett(3/13/2017 – 3/17/2017)
Venkat Guruswami(two weeks in May)
Tim Roughgarden(5/15/2017 – 5/17/2017)
Aleksander Madry(6/26/2017 – 6/29/2017)
Santosh Vempala(7/17/2017 – 7/28/2017)

Links

In memoriam: Oded Schramm

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

People

Publications

2017

2016

2015

2014

2013

2012

2011

2010

2009

Videos

Link description

Theory Day Session 3

Date

March 30, 2015

Speakers

Yishay Mansour

Affiliation

Microsoft

Link description

Graphical Bandits

Date

August 7, 2014

Speakers

Nicolo Cesa-Bianchi

Affiliation

Universita degli Studi di Milano

Link description

The Frog Model on Trees

Date

July 24, 2014

Speakers

Matthew Junge

Affiliation

University of Washington

Link description

Prior Robust Optimization

Date

February 7, 2013

Speakers

Balasubramanian Sivan

Affiliation

University of Wisconsin-Madison

Link description

The Margulis expanders

Date

August 23, 2012

Speakers

James Lee

Affiliation

University of Washington

Link description

Digital Snowflakes

Date

April 25, 2012

Speakers

Janko Gravner

Affiliation

University of California, Davis

Link description

Finding Dense Subgraphs

Date

February 16, 2012

Speakers

Aditya Bhaskara

Affiliation

Princeton University

Link description

Combinatorial Betting

Date

January 8, 2009

Speakers

David M. Pennock

Affiliation

Yahoo! Research

Link description

Mediators

Date

July 17, 2007

Speakers

Moshe Tennenholtz

Affiliation

Technion

Link description

Random Sorting Networks

Date

October 27, 2006

Speakers

Alexander E. Holroyd

Affiliation

University of British Columbia

Link description

Optimal Dynamic Auctions

Date

March 21, 2006

Speakers

Mallesh M. Pai

Affiliation

Northwestern University, Kellogg School of Management

Link description

One Dimensional DLA

Date

March 10, 2006

Speakers

Omer Angel

Affiliation

University of British Columbia

Link description

Root numbers and ranks

Date

August 10, 2005

Speakers

Brian Conrad

Affiliation

University of Michigan

Link description

The Giant Component

Date

July 13, 2004

Speakers

Joel Spencer

Affiliation

Courant Institute

Events

Theory Seminar

MSR Redmond, Building 99 | January 2017

The Theory Seminar hosts talks in mathematics, theoretical computer science, and related areas.

Northwest Probability Seminar 2016

Microsoft Research 99/1919 | November 2016

The 18th Northwest Probability Seminar, a one-day mini-conference organized by the University of Washington, the Oregon State University, the University of British Columbia, the University of Oregon, and the Theory Group at Microsoft Research, will be held on November 5, 2016. This year the conference is hosted at Microsoft, supported by Microsoft Research and the Pacific Institute for the Mathematical Sciences (PIMS). The Birnbaum Lecture in Probability will be given by Alexei Borodin (MIT). [Past Birnbaum speakers] Other speakers are…

Posts

Maximum Overhang, Optimum Reward

By Janie Chang, Writer, Microsoft Research Yuval Peres, principal researcher at Microsoft Research Redmond and manager of the Theory Group, always advocates both healthy skepticism and an open mind when it comes to problem solving. Even so, Peres was pleasantly surprised when a paper he co-authored won the prestigious David P. Robbins Prize from the Mathematical Association of America (MAA) for taking a completely new approach to a problem mathematicians had considered solved for decades.…

March 2011

Microsoft Research Blog

Microsoft Research Asia’s Guo Discusses the Future of Graphics

By Rob Knies, Managing Editor, Microsoft Research Microsoft Research Asia, celebrating its 10th anniversary, recently presented its annual Computing in the 21st Century academic symposium, held over two days, Nov. 4 in Beijing and Nov. 7 in Singapore. For the second consecutive year, Baining Guo, assistant managing director of the lab, served as chair of the event. “We’re very excited,” Guo said of the anniversary festivities. “It’s a big celebration.” The morning after the Singapore…

December 2008

Microsoft Research Blog

Microsoft Research New England’s Focus: Research Relationships

By Rob Knies, Managing Editor, Microsoft Research On Feb. 4, Microsoft Research unveiled its latest lab, to be called Microsoft Research New England and to be based in Cambridge, Mass., in the midst of the Boston region’s bustling academic environment. Jennifer Chayes will serve as managing director of the lab, with her husband and longtime professional collaborator, Christian Borgs, as deputy managing director, though, given the nature of their relationship, the roles could prove a…

February 2008

Microsoft Research Blog