> 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: Debmalya Panigrahi

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

2013:

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
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)