Microsoft Research Theory Group Seminar
Theory Lunches on Wednesdays:
([NC]=noncatered) 

2016:
November 29 
10:30, 99/1915 

November 18 
15:30, 99/1915 

November 10 
15:00, 99/1915 

November 7 
13:30, 99/1915 

November 5 
99/1919 
Alexei Borodin, Sebastien Bubeck, Noah Forman, Tom Hutchcroft, Lionel Levine 

November 3 
13:30, 99/1915 
[V] The invisible hand of Laplace: the role of market structure in price convergence and oscillation 

October 20 
13:30, 99/1915 
[V] A Duality Based Framework for Designing Simple Mechanisms 

October 13 
13:30, 99/1915 

September 1 
15:30, 99/1927 
Improved algorithms for some problems in discrepancy theory 

August 10 
15:30, 99/1915 

August 9 
15:30, 99/1915 

August 8 
15:30, 99/2800 

June 17 
15:30, 99/1915 

June 14 
15:00, 99/4300 
Properties of GaltonWatson trees, continuity, and first order logic 

June 13 
15:30, 99/1915 
[V] A polynomial bound for Green's arithmetic triangle removal lemma in vector spaces 

June 2 
15:30, 99/1915 
Royen's proof of the Gaussian Correlation Conjecture 

May 27 
15:30, 99/2800 
Complex Contagions on Social Networks 

May 17 
15:30, 99/2505 
An Improved Bin Packing Approximation 

May 12 
15:30, 99/1927 
"Continuous" combinatorics 

May 6 
15:30, 99/2817 
The connectivity of the uniform spanning forest on planar graphs 

May 5 
15:30, 99/1915 
Matrix balancing in L_p norms: a new analysis of Osborne's iteration 

May 3 
15:30, 99/1919 

April 20 
15:30, 99/1927 
[V] Approximating the Nash Social Welfare with Indivisible Items 

March 10 
12:00, 99/1927 
Bobby Kleinberg, Ravishankar Krishnaswamy, Janardhan Kulkarni, Miklos Racz, Gireeja Ranade, Milan Vojnovic 
[V] MSR Theory Day 
March 2 
13:30, 99/2300 
The Power of Depth for Feedforward Neural Networks 

February 9 
15:30, 99/1915 
[V] Approximating integer programming problems by partial resampling 

February 4 
15:30, 99/1915 
[V] Random Games 

January 28 
15:30, 99/1915 
[V] A Lasserrebased (1+epsilon)approximation for Makespan Scheduling with Precedence Constraints 
2015:
December 1 
15:30, 99/1915 
[V] Coalescence in branching trees and branching random walks 

November 19 
15:30, 99/1915 

October 28 
12:30, 99/2300 
Covering systems of congruences 

October 26 
15:30, 99/TBA 
[V] Representation power of neural networks 

October 24 
Savery Hall 264, University of Washington 
Mathav Murugan, Yuval Peres, Juan M. Restrepo, Balint Virag, Zhenan Wang 

October 22 
15:30, 99/1915 
[V] Satisfiability of Ordering CSPs Above Average Is FixedParameter Tractable 

October 21 
16:00, 99/2300 

October 13 
15:30, 99/2300 

September 16 
12:30, 99/2300 
Nonasymptotic data compression 

August 18 
14:00, 99/1915 
New examples of spaces satisfying Poincare inequalities 

August 14 
15:30, 99/1915 

August 12 
13:30, 99/1915 
[V] Interpolating Between Truthful and NonTruthful Mechanisms for Combinatorial Auctions 

August 11 
12:30, 99/1915 
Shotgun assembly of labeled graphs 

August 7 
15:30, 99/1915 
Analysis of a Classical Matrix Preconditioning Algorithm 

August 6 
15:30, 99/1927 

August 5 
15:30, 99/1915 

July 29 
12:30, 99/1915 
Braess's paradox for the spectral gap in random graphs 

July 23 
15:30, 99/1927 

July 22 
14:00, 99/1915 

July 20 
15:30, 99/1927 

July 16 
15:30, 99/1927 
[V] A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization 

July 14 
15:30, 99/1915 

July 1 
13:30, 99/1915 

June 25 
MSR NYC 
[V] From “In” to “Over”: Behavioral Experiments on WholeNetwork Computation 

June 24 
15:30, 99/1915 
[V] Energyefficient Scheduling in the Nonclairvoyant Model 

June 24 
MSR New England 
[V] Some Limitations and Possibilities Toward DataDriven Optimization 

June 18 
15:30, 99/1927 
[V] Randomized Interior Point Methods for Sampling and Optimization 

June 10 
15:30, 99/1915 

June 1 
MSR New England 
[V] Learning, Mixing, and Complexity A Free Ride on the Second Law 

May 22 
14:00, 99/1915 

May 21 
15:30, 99/1927 
[V] Fast and Simple Algorithms for Constrained Submodular Maximization 

May 20 
15:30, 99/1915 
[V] A Fast Distributed Algorithm for alphaFair Packing Problems 

May 13 
15:30, 99/1915 

May 8 
13:30, 99/1927 
[V] An averagecase depth hierarchy theorem for Boolean circuits 

March 26 
14:20, 99/1915 

March 26 
13:30, 99/1915 
[V] Bandit Convex Optimization: SqrtT Regret in One Dimension 

March 26 
12:20, 99/1915 

March 20 
14:00, 99/1915 

March 17 
MSR New England 

March 12 
15:30, 99/1927 
[V] Near Optimal LP Rounding for Correlation Clustering on Complete Graphs 

February 19 
14:00, 99/1927 
[V] Fast Algorithms for Online Stochastic Convex Programming 

January 16 
14:00, 99/1927 
[V] EffectiveResistanceReducing Flows, Spectrally Thin Trees and Asymmetric TSP 

January 7 
15:30, 99/1927 
[V] A Simple O(loglog(rank))Competitive Algorithm for the Matroid Secretary Problem 
2014:
December 15 
15:30, 99/1915 
[V] Solving Optimization Problems with Diseconomies of Scale 

November 24 
16:10, 99/1927 

October 25 
Building 99 
Ioana Dumitriu, Alexander Holroyd, Tim Hulshof, Srinivasa Varadhan, Benjamin Young 

October 15 
99/1927 

October 15 
99/1927 

October 8 
MSR Bangalore 

October 8 
15:30, 99/1927 

August 15 
15:30, 99/1915 

August 14 
15:30, 99/1927 

August 7 
15:30, 99/1927 
[V] Towards optimal algorithms for prediction with expert advice 

August 6 
15:30, 99/1927 

August 5 
15:30, 99/1927 

July 29 
15:30, 99/1915 

July 28 
15:30, 99/1927 

July 24 
15:30, 99/1927 
[V] Turnstile Streaming Algorithms Might as Well Be Linear Sketches 

July 21 
15:30, 99/1927 

July 18 
15:30, 99/1919 

June 19 
10:30, 99/1915 

May 28 
15:30, 99/1927 
2013:
November 25 
15:30, 99/1927 

November 19 
15:30, 99/1927 
[V] Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs 

September 26 
15:30, 99/1927 
Concentration of Lipschitz functions of determinantal and other negatively associated variables 

September 19 
15:30, 99/1927 

September 11 
15:30, 99/1927 
[V] Random Walks on Groups and the KaimanovichVershik Conjecture for Lamplighter Groups 

September 3 
15:30, 99/1927 

May 16 
15:30, 99/1927 
Approximate
constraint satisfaction requires large LP relaxations 

May 16 
15:30, 99/1927 

May 15 
15:30, 99/1927 

May 7 
15:30, 99/1927 

April 17 
15:30, 99/1927 

April 3 
15:30, 99/1927 

March 14 
15:30, 99/1927 

March 13 
15:30, 99/1927 

February 12 
15:30, 99/1927 
[V] Graph
Multipartitioning and Higher Order Cheeger
Inequalities 

February 7 
15:30, 99/1927 

January 9 
15:30, 99/1927 
Jonathan Hermon 
2012:
December 18 
15:30, 99/1927 

December 4 
10:30, 99/1927 

November 15 
13:30, 99/1915 
Markov type
and the multiscale geometry of metric spaces – How well can martingales aim?


November 15 
15:30, 99/1927 

November 6 
15:30, 99/1927 
Asymptotic
behavior of the Cheeger constant of supercritical
percolation in the square lattice 

August 23 
15:30, 99/1927 

August 15 
15:30, 99/1927 

April 25 
15:30, 99/1927 

February 17 
13:30, 99/1915 
2011:
2010:
November 12 
3:30, 99/1927 

November 5 
3:30, 99/1927 

November 3 
3:30, 99/1927 

October 28 
3:30, 99/1927 
Arctic
circles, random domino tilings and square Young
tableaux 

October 27 
3:30, 99/1927 
[V] Solvency Games


October 22 
3:30, 99/1927 

October 20 
3:30, 99/1927 

October 15 
1:30, 99/1927 

September 28 
1:30, 99/1927 

September 2 
3:30, 99/1927 
[V] Glauber dynamics for the 2D Ising
model at low temperature 

September 1 
3:30, 99/1927 
[V] Metastabiity and logarithmic energy barriers for a polymer
dynamics 

September 1 
1:30, 99/1919 

August 31 
1:30, 99/1927 

August 30 
3:30, 99/1927 

August 27 
3:30, 99/2917 
Zerotemperature 3D Ising dynamics and dimer coverings 

August 24 
1:30, 99/1915 

August 23 
10:30, 99/1915 

August 18 
1:30, 99/1927 
Metric
Extension Operators, Vertex Sparsifiers and Lipschitz Extendability 

August 17 
1:30, 99/1927 

August 16 
3:30, 99/1927 

August 10 
1:30, 99/1927 

July 30 
1:30, 99/1927 
[V] All pairs
shortest path in quadratic time with high probability. 

July 27 
1:30, 99/1927 
Mobile
Geometric Graphs: Detection, Coverage and Percolation. 

July 26 
3:30, 99/1927 

July 22 
10:30, 99/1927 

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 
[V] Simple
stochastic games and a new class of total functions .


June 30 
3:30, 99/1919 

June 30 
2:00, 99/1927 
Hugo DuminilCopin


June 23 
5:00, 99/1915 

June 22 
1:30, 99/1927 
[V] Can the Theory
of Algorithms Ratify the "Invisible Hand of the Market"?. 

June 17 
10:30, 99/1919 

June 17 
10:30, 99/1915 

June 15 
3:30, 99/1915 

June 14 
4:00, 99/2817 

June 11 
1:30, 99/1915 

June 9 
3:30, 99/1927 
Breaking the Multicommodity Flow Barrier for \sqrt{log(n)}Approximations
to Sparsest Cut. 

June 4 
1:30, 99/1927 

June 3 
3:30, 99/1927 
[V] Cover times,
blanket times, and the Gaussian free field. 

May 28 
1:30, 99/1915 

May 27 
3:30, 99/1927 

May 27 
10:30, 99/1927 

May 25 
3:30, 99/1927 

May 24 
10:30, 99/1927 

May 21 
3:30, 99/1927 

May 18 
3:30, 99/2817 
Marcelo Hilario


May 14 
3:30, 99/2817 

May 13 
3:30, 99/2817 

May 7 
4:00, 99/1915 

Apr 29 
3:30, 99/2817 
[V] Random walks
on the two dimensional uniform spanning tree 

Apr 27 
3:30, 99/2817 

Apr 23 
3:30, 99/2817 
Growth and
random walks in dynamically evolving random environment 

Apr 22 
3:30, 99/2817 

Apr 20 
3:30, 99/2817 

Apr 15 
3:30, 99/2817 

Apr 12 
3:30, 99/2817 

Apr 1 
3:30, 99/2817 

Mar 25 
3:30, 99/2817 

Mar 18 
3:30, 99/1927 

Mar 11 
3:30, 99/1919 

Mar 10 
3:30, 99/1927 

Feb 18 
3:30, 99/1927 

Feb 16 
3:30, 99/1915 
Some
computational and combinatorial applications of simplicial
topology 

Feb 4 
1:30, 99/1915 
Asymmetric
Traveling Salesman Path and Directed Latency Problems 

Jan 27 
1:30, 99/1915 

Jan 25 
10:30, 99/1919 
[V] Local entropy
averages and projections of fractal measures 

Jan 21 
10:30, 99/1919 
[V] Understanding
the Limitations of Linear and Semidefinite
Programming 

Jan 20 
10:30, 99/1919 
The Randomized
kServer Conjecture (Online Algorithms meet Linear Programming) 

Jan 19 
3:30, 99/1915 

Jan 15 
10:30, 99/1927 

Jan 8 
10:30, 99/1915 

Jan 7 
10:30, 99/1919 
[V] Threshold
Functions: Approximation, Pseudorandomness and
Learning 

Jan 6 
10:30, 99/1915 
2009:
Nov 20 
15:30, 99/2817 

Oct 22 
15:30, 99/2817 
[V] Improved
Approximation Algorithms for PrizeCollecting Steiner Tree and TSP 

Oct 8 
15:30, 99/2817 

Oct 1 
15:30, 99/1927B 

Oct 1 
14:00, 99/1927B 

Sep 29 
3:30, 99/1919 

Sep 24 
3:30, 99/1927B 
[I] [V] Economics
meets UI Design: Toll Bridge Pricing and P2P Backup Markets 

Sep 23 
12:30, 99/4300, [NC] 
An O(n log n) algorithm for a load
balancing problem on a tree 

Sep 17 
3:30, 99/1927B 

Sep 16 
12:30, 99/4300, [NC] 
2005:
Aug 30 
15:30, 99/2817 
[V] Is there a model for noise which reduces quantum computation to classical computation? 
2003:
Aug 19 
15:30, 99/2817 
2002:
Jul 29 
15:30, 99/2817 
2001:
Aug 23 
15:30, 99/2817 