Description: Description: Description: Description: Home> Groups > Theory > Seminar

Microsoft Research Theory Group Seminar

Wednesday lunchtimes: ([NC]=non-catered)
12:30-2pm, room 4300
Thursday teatimes:
3:30-4:30pm, room 1927B or 2817
Microsoft Building 99
Page maintained by: Balasubramanian Sivan and Roy Schwartz


Directions
Theory Group
Microsoft Research
Probability in Seattle
Videos (see links below): external access [E]; internal access [I]; Archive of publicly available talks

 

2013:

November 25

15:30, 99/1927

Gil Kalai

Analysis of Boolean Functions: advances and challenges

November 19

15:30, 99/1927

Yuan Zhou

Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs

September 26

15:30, 99/1927

Yuval Peres

Concentration of Lipschitz functions of determinantal and other negatively associated variables

September 19

15:30, 99/1927

Balasubramanian Sivan

Revenue Maximization and Prophet Inequalities

September 11

15:30, 99/1927

Yuval Peres

Random Walks on Groups and the Kaimanovich-Vershik Conjecture for Lamplighter Groups

September 3

15:30, 99/1927

Nikhil Bansal

On the Number of Matroids

May 16

15:30, 99/1927

James Lee

Approximate constraint satisfaction requires large LP relaxations

May 16

15:30, 99/1927

Jacob Leshno

Dynamic Matching in Overloaded Systems

May 15

15:30, 99/1927

Alexander Holroyd

Self-Organizing Cellular Automata

May 7

15:30, 99/1927

Anupam Gupta

Sparsest Cut on Bounded Treewidth Graphs

April 17

15:30, 99/1927

Louigi Addario-Berry

Probabilistic aspects of minimum spanning trees

April 3

15:30, 99/1927

Alex Bocharov

The Incredible Shrinking Quantum Circuit

March 14

15:30, 99/1927

Yashodhan Kanoria

Which side chooses in large random matching markets?

March 13

15:30, 99/1927

Laszlo Vegh

Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives

February 12

15:30, 99/1927

Anand Louis

Graph Multi-partitioning and Higher Order Cheeger Inequalities

February 7

15:30, 99/1927

Balasubramanian Sivan

Prior Robust Optimization

January 9

15:30, 99/1927

Jonathan Hermon

The Social Network Model

 

2012:

December 18

15:30, 99/1927

Ola Svensson

Approximating k-Median via Pseudo-approximation

December 4

10:30, 99/1927

Alistair Sinclair

Random Lattice Triangulations: Structure and Algorithms

November 15

13:30, 99/1915

James Lee

Markov type and the multi-scale geometry of metric spaces – How well can martingales aim?

November 15

15:30, 99/1927

Geoffrey Grimmett

Counting self-avoiding walks

November 6

15:30, 99/1927

Eviatar Procaccia

Asymptotic behavior of the Cheeger constant of super-critical percolation in the square lattice

August 23

15:30, 99/1927

James Lee

The Margulis expanders

August 15

15:30, 99/1927

Laszlo Lovasz

The similarity distance on graphs and graphons

April 25

15:30, 99/1927

Janko Gravner

Digital Snowflakes

February 17

13:30, 99/1915

Roberto Imbuzeiro Oliveira

On the coalescence time of reversible random walks

 

2011:

December 8

15:30, 99/1927

Nisheeth Vishnoi

Approximating the Exponential, the Lanczos Method and an O(m polylog(n))-Time Spectral Algorithm for Balanced Graph Partitioning

October 27

15:30, 99/1927

James Lee

Laplacian eigenvalues and expansion of small sets

October 20

15:30, 99/1927

Niv Buchbinder

The randomized k-server conjecture

October 13

15:30, 99/1927

Nicolas Curien

Introduction to the theory of random planar maps

September 29

15:30, 99/1927

James Lee

Sparsest Cut, discrete differentiation, and local rigidity of sets in the plane

September 21

15:30, 99/1927

Tanmoy Chakraborty

Mechanism Design for a Risk Averse Seller

September 7

15:30, 99/1927

Amin Saberi

Game Dynamics, Equilibrium Selection and Network Structure

September 1

15:30, 99/1927

Itai Benjamini

Aspects of random walks on groups

August 17

15:30, 99/1927

Klaus Schmidt

Abelian Sandpiles and the Harmonic Model

August 11

15:30, 99/1927

Benny Sudakov

Nonnegative k-sums, fractional covers, and probability of small deviations

August 10

15:30, 99/1927

R. Ravi

Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits

August 4

15:30, 99/1927

Balasubramanian Sivan

Near Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problems

July 28

15:30, 99/1927

Omer Tamuz

From Agreement to Asymptotic Learning

July 21

10:30, 99/1915

Venkatesan Guruswami

Bridging Shannon and Hamming: Codes for Computationally Simple Channels

July 20

15:30, 99/1927

Ivan Corwin

Beyond the Gaussian Universality Class

July 7

15:30, 99/1927

Jian Ding

Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees

July 5

15:30, 99/1919

Andrey Raigorodsky

Web graph models: properties and applications

June 30

15:30, 99/1927

Asaf Nachmias

The percolation phase transition in the Hamming cube

June 29

15:30, 99/1927

Charles Smart

Convergence of the Abelian sandpile

May 27

15:30, 99/1927

Sebastian Cioaba

On a conjecture of Brouwer regarding the connectivity of strongly regular graphs

 

2010:

November 12

3:30, 99/1927

S. Muthukrishnan

Ad Exchanges: Auctions and Optimizations

November 5

3:30, 99/1927

Jeff Kahn

Factors in random graphs and hypergraphs

November 3

3:30, 99/1927

Elliot Anshelevich

Contribution Games in Social Networks

October 28

3:30, 99/1927

Dan Romik

Arctic circles, random domino tilings and square Young tableaux

October 27

3:30, 99/1927

Leonard Schulman

Solvency Games

October 22

3:30, 99/1927

Nick Wormald

Asymptotic enumeration of sparse 2-connected graphs

October 20

3:30, 99/1927

Ran Raz

How to fool people to work on circuit lower bounds

October 15

1:30, 99/1927

Sergey Fomin

Total positivity and cluster algebras

September 28

1:30, 99/1927

Elchanan Mossel

Learning on social networks

September 2

3:30, 99/1927

Fabio Martinelli

Glauber dynamics for the 2D Ising model at low temperature

September 1

3:30, 99/1927

Fabio Toninelli

Metastabiity and logarithmic energy barriers for a polymer dynamics

September 1

1:30, 99/1919

Debmalya Panigrahi

Online Non-Metric Facility Location and Related Problems

August 31

1:30, 99/1927

Yossi Azar

Ranking with Unrelated Intents or Submodular Valuations

August 30

3:30, 99/1927

Pietro Caputo

Proof of Aldous' spectral gap conjecture

August 27

3:30, 99/2917

Fabio Toninelli

Zero-temperature 3D Ising dynamics and dimer coverings

August 24

1:30, 99/1915

Siddhartha Sen

New Balanced Search Trees

August 23

10:30, 99/1915

Claire Mathieu

Approximation Schemes for Optimization

August 18

1:30, 99/1927

Konstantin Makarychev

Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability

August 17

1:30, 99/1927

Glencora Borradaile

Finding all min st-cuts in planar graphs.

August 16

3:30, 99/1927

Persi Diaconis

Random Tri-Diagonal Doubly Stochastic Matrices.

August 10

1:30, 99/1927

Michael Krivelevich

Embedding spanning trees in random graphs.

July 30

1:30, 99/1927

Benny Sudakov

All pairs shortest path in quadratic time with high probability.

July 27

1:30, 99/1927

Alexandre Stauffer

Mobile Geometric Graphs: Detection, Coverage and Percolation.

July 26

3:30, 99/1927

Rick Kenyon

The double dimer model with quaternions.

July 22

10:30, 99/1927

Maria Florina Balcan

Approximate Clustering without the Approximation.

July 9

2:00, 99/2817

Zhongyang Li

Vertex models and holographic projection.

July 8

3:30, 99/2817

Nike Sun

On a result by Chatterjee on the maximum of a discrete Gaussian free field.

July 6

3:30, 99/1919

Christos Papadimitriou

Simple stochastic games and a new class of total functions .

June 30

3:30, 99/1919

James Lee

Talagrand's majorizing measure theorem: The proof.

June 30

2:00, 99/1927

Hugo Duminil-Copin

Self-avoiding walks on the honeycomb lattice.

June 23

5:00, 99/1915

James Lee

Talagrand's majorizing measure theory: Lower bounds.

June 22

1:30, 99/1927

Vijay Vazirani

Can the Theory of Algorithms Ratify the "Invisible Hand of the Market"?.

June 17

10:30, 99/1919

Claire Mathieu

How to Route Vehicles in the Plane, in Theory.

June 17

10:30, 99/1915

Aravind Srinivasan

New Constructive Aspects of the Lovasz Local Lemma.

June 15

3:30, 99/1915

David Aldous

Scale-invariant random spatial networks.

June 14

4:00, 99/2817

James Lee

An introduction to Talagrand's majorizing measure theory.

June 11

1:30, 99/1915

Anup Rao

Pseudorandom Generators for Regular Branching Programs.

June 9

3:30, 99/1927

Jonah Sherman

Breaking the Multicommodity Flow Barrier for \sqrt{log(n)}-Approximations to Sparsest Cut.

June 4

1:30, 99/1927

Tobias Friedrich

Quasirandom Load Balancing.

June 3

3:30, 99/1927

Yuval Peres

Cover times, blanket times, and the Gaussian free field.

May 28

1:30, 99/1915

Ryan O'Donnell

Kahn-Kalai-Linial and Kruskal-Katona.

May 27

3:30, 99/1927

Alexandre Stauffer

Percolation in a mobile environment.

May 27

10:30, 99/1927

Chinmay Karande

New Algorithmic Developments in Ad-auctions.

May 25

3:30, 99/1927

Jay Rosen

A sufficient condition for the continuity of permanental processes with applications to local times of Markov processes and loop.

May 24

10:30, 99/1927

Gunnar Carlsson

Topology and Data.

May 21

3:30, 99/1927

Vladas Sidoravicius

Abundance of Maximal Paths.

May 18

3:30, 99/2817

Marcelo Hilario

Fixation for Distributed Clustering Processes.

May 14

3:30, 99/2817

David Wilson

xor-Ising model

May 13

3:30, 99/2817

Karl Mahlburg

Percolation, Probability, and Partitions

May 7

4:00, 99/1915

Svante Janson

Width and height of conditioned Galton-Watson trees

Apr 29

3:30, 99/2817

Robert Masson

Random walks on the two dimensional uniform spanning tree

Apr 27

3:30, 99/2817

Chris Hillar

Word equations in a uniquely divisible group

Apr 23

3:30, 99/2817

Vladas Sidoravicius

Growth and random walks in dynamically evolving random environment

Apr 22

3:30, 99/2817

Lionel Levine

Fast simulation of large-scale growth models

Apr 20

3:30, 99/2817

Nikhil Devanur

Local Dynamics in Bargaining Networks via Random Turn Games

Apr 15

3:30, 99/2817

Allan Sly

Cutoff for the Ising model on the lattice

Apr 12

3:30, 99/2817

Jian Ding

Cover times, blanket times, and majorizing measures.

Apr 1

3:30, 99/2817

Ori Gurel-Gurevich

Nonconcentration of Return Times

Mar 25

3:30, 99/2817

Ander Holroyd

Multi-dimensional percolation

Mar 18

3:30, 99/1927

Soumik Pal

Wright-Fisher model with negative mutation rates

Mar 11

3:30, 99/1919

Nicole Immorlica

Pricing Information Cascades

Mar 10

3:30, 99/1927

Christos Papadimitriou

Computing Nash equilibria: The plot thickens

Feb 18

3:30, 99/1927

David Aldous

Concentration for Markov chain cover times

Feb 16

3:30, 99/1915

Nati Linial

Some computational and combinatorial applications of simplicial topology

Feb 4

1:30, 99/1915

Zoya Svitkina

Asymmetric Traveling Salesman Path and Directed Latency Problems

Jan 27

1:30, 99/1915

Warren Schudy

Approximation Schemes for Dense Variants of Feedback Arc Set, Correlation Clustering, and Other Fragile Min Constraint Satisfaction Problems

Jan 25

10:30, 99/1919

Mike Hochman

Local entropy averages and projections of fractal measures

Jan 21

10:30, 99/1919

Grant Schoenebeck

Understanding the Limitations of Linear and Semidefinite Programming

Jan 20

10:30, 99/1919

Niv Buchbinder

The Randomized k-Server Conjecture (Online Algorithms meet Linear Programming)

Jan 19

3:30, 99/1915

Remco van der Hofstad

First passage percolation on random graphs

Jan 15

10:30, 99/1927

Anne Fey

Limiting shapes for a nonabelian sandpile growth model

Jan 8

10:30, 99/1915

Nitish Korula

Online Allocations and Advertising

Jan 7

10:30, 99/1919

Ilias Diakonikolas

Threshold Functions: Approximation, Pseudorandomness and Learning

Jan 6

10:30, 99/1915

Nikhil Srivastava

Twice-Ramanujan Sparsifiers

 

2009:

Nov 20

15:30, 99/2817

Gagan Goel

Algorithms for Auctions with budget constraints

Oct 22

15:30, 99/2817

Mohammad-Taghi Hajiaghayi

Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP

Oct 8

15:30, 99/2817

Geoffery Grimmett (Cambridge University)

Influence and sharp thresholds for product and FKG measures

Oct 1

15:30, 99/1927B

Robin Moser (ETH Zurich)

A Constructive Proof of the Lovász Local Lemma

Oct 1

14:00, 99/1927B

Noga Alon (Tel-Aviv University)

Eliminating Cycles in the Torus

Sep 29

3:30, 99/1919

Eyal Winter (Hebrew University)

Contracting with Asymmetric Externalities

Sep 24

3:30, 99/1927B

Sven Seuken (MSR and Harvard)

[I] Economics meets UI Design: Toll Bridge Pricing and P2P Backup Markets

Sep 23

12:30, 99/4300, [NC]

Nikhil Devanur (MSR)

An O(n log n) algorithm for a load balancing problem on a tree

Sep 17

3:30, 99/1927B

Ben Birnbaum (U Washington)

[I] On Local Dynamics for Two Equilibrium Concepts

Sep 16

12:30, 99/4300, [NC]

Kamal Jain (MSR)

 

2005:

Aug 30

15:30, 99/2817

Gil Kalai

Is there a model for noise which reduces quantum computation to classical computation?

 

2003:

Aug 19

15:30, 99/2817

Gil Kalai

A topological colorful Helly theorem

 

2002:

Jul 29

15:30, 99/2817

Gil Kalai

Around Borsuk’s Problem

 

2001:

Aug 23

15:30, 99/2817

Gil Kalai

Threshold phenomena and social choice