MSR/MIT Theory Reading Group
 |
MSR/MIT Reading Group: Nati Linial, Random Simplicial Complexes Tuesday, September 1, 2015 - 4:00pm to 6:00pm Why do graphs appear in most applications of mathematics to the real world? One reason is that many large systems that we study are defined by pairwise interactions of their constituents. E.g., people in social networks, companies in trading, interacting proteins in biological systems etc. |
 |
Mrinal Kumar: Recent progress on arithmetic circuit lower bounds and exponential lower bounds for depth five circuits over finite fields Friday, July 17, 2015 - 1:15pm to 4:15pm Starting with a beautiful result of Gupta et al in 2012, the last few years have seen exciting progress on the problem of proving lower bounds for interesting special classes of homogeneous depth four arithmetic circuits. |
|
|
Noga Ron-Zewi: High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity Friday, July 10, 2015 - 1:15pm to 4:15pm Locally-correctable codes (LCCs) and locally-testable codes (LTCs) are special families of error-correcting codes that admit extremely efficient, i.e., sub-linear time, algorithms for error correction and detection, respectively, while making a few queries to the received word. |
|
|
Ben Rossman: Correlation Bounds Against Monotone NC^1 Friday, June 26, 2015 - 1:15pm to 4:15pm Product distribution are conjectured to be a source of hard instances for important monotone problems like SAT and CLIQUE. Yet despite a long history of lower bounds in monotone models of computation, average-case lower bounds under product distributions have been an elusive goal. |
 |
Abhishek Bhowmick: The List Decoding Radius of Reed-Muller codes over Small Fields Friday, April 3, 2015 - 12:45pm to 3:30pm Abstract: |
 |
Moses Charikar: Spectral Embedding of k-Cliques, Graph Partitioning and k-Means Friday, February 13, 2015 - 12:45pm Abstract: We introduce and study a new notion of graph partitioning, intimately connected to k-means clustering. Informally, our graph partitioning objective asks for the optimal spectral simplification of a graph as a disjoint union of k normalized cliques. |
|
|
Nike Sun: The Exact k-SAT Threshold for Large k Friday, December 19, 2014 - 12:45pm to 3:45pm We establish the random k-SAT threshold conjecture for all k exceeding an absolute constant k(0). |
|
|
Ilya Razenshteyn: Sketching and Embedding are Equivalent for Norms Friday, December 5, 2014 - 12:45pm to 3:45pm Imagine the following communication task. Alice and Bob each have a point from a metric space. They want to transmit a few bits and decide, whether their points are close to each other or are far apart. |
|
|
Omri Weinstein: Information Complexity, Direct Sums and Products and the Quest for Interactive Compression Friday, December 12, 2014 - 12:45pm to 3:45pm Over the past three decades, communication complexity had a profound impact on nearly every field of theoretical computer science, and constitutes one of the few known methods for proving unconditional lower bounds. |
|
|
Ankur Moitra: The Threshold for Super-resolution Friday, November 21, 2014 - 12:45pm to 3:45pm Super-resolution is a fundamental task in imaging, where the goal is to extract fine-grained structure from coarse-grained measurements. |
Pages
