Recorded lectures archive, Microsoft Research Theory Group

2003

• Random Walk and Random Aggregation, Derandomized , James Propp, November 13, 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.
  
  
• Average-Case 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 k-core 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 Min-Entropy Independent Sources , Anup Rao, January 19, 2007.
  
  
• Approximation Algorithms for Unique Games , Yury Makarychev, January 31, 2007.
  
  
• Why Almost All K-Colorable 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 Triangle-Free Digraphs , Blair D. Sullivan, April 27, 2007.
  
  
• Which graphs are extremal graphs? , Laszlo Lovasz , August 7, 2007.
  
  
• The Scaling Limit of Diaconis-Fulton 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 Gurel-Gurevich, 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 L-Reversal Chain , Ben Morris, September 16, 2008.
  
  
• Part 2:Improved mixing time bounds for the Thorp shuffle and L-reversal chain , Ben Morris, September 18, 2008.
  
  
• Graph approximation and local clustering, with applications to the solution of diagonally-dominant systems of linear equations , Daniel Spielman, September 29, 2008.
  
  

2009

• A Rigorous Perspective on Liouville Quantum Gravity and KPZ , Bertrand Duplantier, August 28, 2009.
  
  
• Better Multiple Intents Re-ranking , Nikhil Bansal, September 8, 2009.