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.

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

 Kostya Makarychev

Kostya Makarychev

Interests: Approximation algorithms and combinatorial optimization, in particular, semidefinite programming and questions related to functional analysis and metric geometry

 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

 Mohit Singh

Mohit Singh

Interests: Approximation Algorithms, Combinatorial Optimization with applications in network design. Also interested in models and problems dealing with uncertainty in data

 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: Probability theory and its applications, combinatorial statistics, information theory, genomics

 

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
James Martin(1/25/2016 – 5/6/2016)
Janos Englander(2/1/2016 – 5/31/2016)
Ryokichi Tanaka(2/1/2016 – 2/28/2017)
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)
Ilya Shkredov(2/29/2016 – 3/18/2016)
Marta Lewicka(3/7/2016 – 3/11/2016) and (8/1/2016 – 8/26/2016)
Victoria Kostina(3/14/2016 – 3/16/2016)
Zhongyang Li(3/14/2016 – 3/18/2016)
Laura Florescu(3/16/2016 – 3/20/2016)
Tianyi Zheng(3/21/2016 – 3/25/2016)
David Levin(3/24/2016 – 3/26/2016)
Lionel Levine(3/27/2016 – 4/1/2016)
Chris Bishop(4/14/2016 – 4/24/2016)
Omer AngelThree weeks during (4/25/2016 – 6/23/2016)
Yuval Rabani(4/25/2016 – 5/6/2016)
Laszlo M. Lovasz(4/28/2016 – 5/2/2016)
Daniel Ahlberg(5/3/2016 – 5/6/2016)
Asaf Nachmias(5/3/2016 – 5/8/2016)
Swastik Kopparty(5/9/2016 – 5/20/2016)
Shubhangi Saraf(5/9/2016 – 5/20/2016)
Alexander Razborov(5/12/2016)
Shuchi ChawlaSeveral weeks during (5/16/2016 – 7/31/2016)
Fedor Nazarov(5/26/2016 – 6/4/2016)
Nina Holden(5/30/2016 – 6/3/2016), (7/18/2016 – 7/29/2016), and (8/8/2016 – 8/26/2016)
Ilias Zadik(5/30/2016 – 6/3/2016)
Lionel Levine(5/30/2016 – 7/4/2016)
Nima Haghpanah(6/1/2016 – 6/6/2016)
Alex Psomas(6/1/2016 – 6/6/2016)
Moumanti Podder(6/13/2016 – 6/17/2016)
Perla Sousi(6/13/2016 – 7/15/2016)
Russell Lyons(6/13/2016 – 8/19/2016)
Zhiyi Huang(6/27/2016 – 7/1/2016)
Grigory Yaroslavtsev(6/27/2016 – 7/1/2016)
Eyal Lubetzky(7/1/2016 – 8/31/2016)
Roy Schwartz(7/18/2016 – 8/12/2016)
Robin Pemantle(7/25/2016 – 7/29/2016)
Xin Sun(7/25/2016 – 7/29/2016)
Rick Kenyon(7/28/2016 – 8/12/2016)
Victoria Kostina(8/15/2016 – 8/19/2016)
Jian Ding(8/15/2016 – 8/26/2016)
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) and (12/5/2016 – 12/9/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)
Russell Lyons(12/5/2016 – 12/13/2016)
Nina Holden(1/4/2016 – 1/27/2016)
Bob Hough(1/9/2016 – 1/13/2016)
Claire Mathieu(1/30/2017 – 2/24/2017)

Topics of Study

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.

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

Videos

Theory Day Session 3 Link description

Theory Day Session 3

Date

March 30, 2015

Speakers

Yishay Mansour

Affiliation

Microsoft

Graphical Bandits Link description

Graphical Bandits

Date

August 7, 2014

Speakers

Nicolo Cesa-Bianchi

Affiliation

Universita degli Studi di Milano

The Frog Model on Trees Link description

The Frog Model on Trees

Date

July 24, 2014

Speakers

Matthew Junge

Affiliation

University of Washington

Prior Robust Optimization Link description

Prior Robust Optimization

Date

February 7, 2013

Speakers

Balasubramanian Sivan

Affiliation

University of Wisconsin-Madison

The Margulis expanders Link description

The Margulis expanders

Date

August 23, 2012

Speakers

James Lee

Affiliation

University of Washington

Digital Snowflakes Link description

Digital Snowflakes

Date

April 25, 2012

Speakers

Janko Gravner

Affiliation

University of California, Davis

Finding Dense Subgraphs Link description

Finding Dense Subgraphs

Date

February 16, 2012

Speakers

Aditya Bhaskara

Affiliation

Princeton University

Combinatorial Betting Link description

Combinatorial Betting

Date

January 8, 2009

Speakers

David M. Pennock

Affiliation

Yahoo! Research