Recorded lectures archive, Microsoft Research Theory Group
2003
2004

On the Measure of Intersecting Families, Spectral Methods
, Ehud Friedgut, March 9, 2004.

The Sharp Form of the Strong Szego Theorem
, Barry Simon, May 10, 2004.

Anomalous Diffusion and Polya Recurrence
, Domokos Szasz, June 16, 2004.

Sharp Thresholds for Random Constraint Satisfaction Problems
, Michael Molloy, July 19, 2004.

The Giant Component
, Joel Spencer, August 13, 2004.

A Unification of Menger's and Edmonds' Theorems and Network Coding Theorems , Yunnan Wu, August 25, 2004.

Designing Ad Auctions: An Algorithmic Perspective
, Amin Saberi, September 1, 2004.

Some Uses of Orthogonal Polynomials
, Richard Askey, October 6, 2004.
2005

Convex Geometry of Orbits
, Greg Blekherman, January 17, 2005.

Bergman Complexes, Coxeter Arrangements, and Graph Associahedra
, Lauren Williams, January 18, 2005.

Menger's Theorem for Infinite Graphs
, Eli Berger, February 5, 2005.

Perelman's Work on the Thurston's Geometrization Conjecture  1
, Bruce Kleiner, May 9, 2005.

Perelman's Work on the Thurston's Geometrization Conjecture  2
, Bruce Kleiner, May 12, 2005.

Perelman's Work on the Thurston's Geometrization Conjecture  3
, Bruce Kleiner, May 13, 2005.

Entanglement Entropy in Extended Systems
, John Cardy, May 24, 2005.

Singularity of Random Bernoulli Matrices
, Van Vu, July 13, 2005.

Approximability of the Unique Coverage Problem
, Mohammad R. Salavatipour, August 18, 2005.

Geometry and Expansion: A Survey of Recent Results
, Sanjeev Arora, August 23, 2005.

A Lower Bound for Cooperative Broadcast in the Presence of Noise , Michael Saks, August 25, 2005.

Extremal Set Theory, Boolean Functions, and Occam's Razor
, Ehud Friedgut, September 14, 2005.
2006

One Dimensional DLA
, Omer Angel, January 1, 2006.

Corner Percolation and the Square Root of 17
, Gabor Pete, January 24, 2006.

A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity , Asaf Shapira, January 27, 2006.

AverageCase Analysis for Combinatorial Problems Featuring Subset Sums and Stochastic Spanning Trees
, Abraham Flaxman, February 1, 2006.

Developments in Dynamic Graph Algorithms
, Liam Roditty, February 20, 2006.

Local Chromatic Number of Quadrangulation of Surfaces
, Gabor Tardos, February 27, 2006.

Counting Independent Sets Up to the Tree Threshold
, Dror Weitz, March 24, 2006.

Fitting a C^M Smooth Function to Data
, Charles Fefferman, March 27, 2006.

Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity
, Joel Friedman, April 20, 2006.

New Market Models and Algorithms
, Vijay Vazirani, May 24, 2006.

Graph Cuts without Eigenvectors
, Brian Kulis, July 10, 2006.

Random Matrices and Spectral Clustering Abstract
, Ravi Kannan, July 27, 2006.

On the Compressibility of NP Instances and Cryptographic Applications
, Moni Naor, August 9, 2006.

Low Distortion Embeddings for Edit Distance
, Yuval Rabani, October 12, 2006.

Random Sorting Networks
, Alexander Holroyd, October 27, 2006.

Algorithmic Performance in Complex Networks , Milena Mihail, November 6, 2006.

A Simple Solution to the kcore Problem , Malwina Luczak, December 7, 2006.

Randomly Coloring Planar Graphs with Fewer Colors Than the Maximum Degree
, Juan Vera, December 11, 2006.
2007

New Locally Decodable Codes and Private Information Retrieval Schemes
, Sergey Yekhanin, January 3, 2007.

Graph Powers and Capacities
, Eyal Lubetzky, January 4, 2007.

Upcrossing Inequalities for Stationary Sequences
, Mike Hochman, January 8, 2007.

Enhancing the Markov Chain Monte Carlo Method
, Nayantara Bhatnagar, January 18, 2007.

Extractors for a Constant Number of Polynomially Small MinEntropy Independent Sources
, Anup Rao, January 19, 2007.

Approximation Algorithms for Unique Games
, Yury Makarychev, January 31, 2007.

Why Almost All KColorable Graphs Are Easy
, Dan Vilenchik, February 12, 2007.

An Axiomatic Approach to Ranking Systems
, Moshe Tennenholtz, February 15, 2007.

Learning and Competition with Finite Automata
, Abraham Neyman, February 22, 2007.

The Diameter and Mixing Time of Critical Random Graphs
, Asaf Nachmias, February 27, 2007.

How Likely is Buffon's Needle to Meet a Cantor Square?
, Fedor Nazarov, April 6, 2007.

Linked Decompositions of Networks and Polya Urns with Choice
, Christos H. Papadimitriou, April 25, 2007.

Dense TriangleFree Digraphs
, Blair D. Sullivan, April 27, 2007.

Which graphs are extremal graphs?
, Laszlo Lovasz , August 7, 2007.

The Scaling Limit of DiaconisFulton Addition , Lionel Levine, August 31, 2007.

Counterexamples in the Central Limit Theory of Markov Chains
, Olle Haggstrom, September 5, 2007.

Universal techniques to analyze preferential attachment trees: Global and Local analysis
, Shankar Bhamidi, October 9, 2007.

Feedback Arc Sets and Girth in Digraphs
, Blair D. Sullivan, October 11, 2007.

Gibbs Measures on Trees and Random Graphs
, Allan Sly, November 14, 2007.

Pricing Games in Networks
, Eva Tardos, December 13, 2007.

Parallel Monotonicity Reconstruction
, C. Seshadhri, December 19, 2007.
2008

Recurrence of the Simple Random Walk Path
, Ori GurelGurevich, January 2, 2008.

Critical percolation on finite graphs
, Asaf Nachmias, January 4, 2008.

Approximation Algorithms for Discrete Stochastic Optimization Problems
, David Shmoys, January 17, 2008.

Computing Nash Equilibria
, Constantinos Daskalakis, January 18, 2008.

Query Lower Bounds for Matroids via Group Representations , Nicholas Harvey, January 28, 2008.

The Limiting Shape of Internal DLA with Multiple Sources , Lionel Levine, January 30, 2008.

The Quest for the Minimal Hardness Assumptions
, Iftach Haitner, March 21, 2008.

Externalities in Online Advertising
, Mohammad Mahdian, June 25, 2008.

Part 1: Improved Mixing Time Bounds for the Thorp Shuffle and LReversal Chain
, Ben Morris, September 16, 2008.

Part 2:Improved mixing time bounds for the Thorp shuffle and Lreversal chain
, Ben Morris, September 18, 2008.

Graph approximation and local clustering, with applications to the solution of diagonallydominant systems of linear equations
, Daniel Spielman, September 29, 2008.
2009