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 17, 2015: Mrinal Kumar: Recent progress on arithmetic circuit lower bounds and exponential lower bounds for depth five circuits over finite fields

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 NC^1

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.