MSR/MIT Theory Reading Group
MSR/MIT Theory Reading Group
Spring 2015
September 1, 2015: Nati Linial: Random Simplicial Complexes
July 24, 2015: Pravesh Kothari: Sum of Squares Lower Bounds from Pairwise Independence
July 10, 2015: Noga Ron-Zewi: High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity
June 26, 2015 Ben Rossman: Correlation Bounds Against Monotone NC1
April 3, 2015 Abhishek Bhowmick: The List Decoding Radius of Reed-Muller Codes Over Small Fields
February 13, 2015: Moses Charikar: Spectral Embedding of k-Cliques, Graph Partitioning and k-Means
Fall 2014
December 19, 2014: Nike Sun: The Exact k-SAT Threshold for Large k
December 12, 2014: Omri Weinstein: Information Complexity, Direct Sums and Products and the Quest for Interactive Compression
December 5, 2014: Ilya Razenshteyn: Sketching and Embedding are Equivalent for Norms
November 21, 2014: Ankur Moitra: The Threshold for Super-resolution
November 14, 2014: Dana Moshkovitz: Candidate Lasserre Integrality Gap for Unique Games
November 7, 2014: Aaron Potechin: Sum of Squares Lower Bounds for the Planted Clique Problem
Summer 2014
August 15, 2014: Rakesh Vohra: Rounding in Matching Problems from Economics
August 1, 2014: Siu On Chan: Lower Bounds for Extended Formulations
July 25, 2014: Bernhard Haeupler: How to Have a Conversation Despite Noise
July 18, 2014: Aaron Sidford: Path Finding Methods for Linear Programming
Spring 2014
May 2, 2014: Or Meir: Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture
April 18, 2014: Amir Shpilka: Depth Reduction for Arithmetic Circuits
April 11, 2014: Lorenzo Orrechia and Zeyuan Allen Zhu: A Survey of First-Order Iterative Methods in the Design of Fast Graph Algorithms
March 28, 2014: Dana Moshkovitz: An Algebraic Parallel Reptition Theorem
March 14, 2014: Constantinos Daskalakis: Learning Structured Distributions from a Constant Number of Samples
February 28, 2014: Emmanuel Abbe: Concentration Results in Random CSP's, Soft CSP's and Applications
February 21, 2014: Venkatesan Guruswami: List Decoding by Evading Subspaces
February 14, 2014: Justin Thaler: Approximate Degree and the Method of Dual Polynomials
Fall 2013
December 6, 2013: Larry Guth: Polynomial Methods in Incidence Geometry (Note special time: 3:30pm-6:30pm)
November 22, 2013: Richard Peng: Algorithm Design uisng Spectral Graph Theory
November 15, 2013: Ben Rossman: Formulas vs. Circuits for Small Distance Connectivity
November 8, 2013: Vinod Vaikuntanathan: Fully Key Homomorphic Encryption and Applications
November 1, 2013: Salil Vadhan: Locally Testable Codes and Cayley Graphs
October 25, 2013: Yael Kalai: 1-round delegation for deterministic computation
October 11, 2013: Jelani Nelson: Dimensionality reduction via sparse matrices.
October 4, 2013: Van Vu: Matrix perturbation with random noise and matrix recovery problems
Click here for more information and past talks.