MSR/MIT Theory Reading Group

Upcoming Talks:

• No upcoming talks

Past Talks:

• Friday, May 11, 2012: Speaker: Nisheeth Vishnoi (MSR India). Topic: Solve, Walk, Cut
  In this talk I will address the following question: Can one speed-up simulation of random walks given the ability to solve a system of linear equations quickly?
  
  The answer to this will be revealed via an intricate story which stitches together methods from spectral graph theory, numerical linear algebra and approximation theory.
  
  As an application, I will highlight the first near-linear time approximation algorithm, that achieves the Cheeger bound, to cut a graph into two roughly equal parts while minimizing the conductance of the partition.
  
  An overview of fast methods to solve linear systems of equations will be provided.
• Friday, May 4, 2012: Speaker: Sham Kakade (MSR New England). Topic: Two SVDs Suffice: Spectral Decompositions for Probabilistic Topic Modeling and Latent Dirichlet Allocation
  The topic modeling problem can be seen as a generalization of the clustering problem, where each document has a mixture of active topics (as opposed to just being about one topic) and that each active topic determines the occurrence of words in the document. Often, probabilistic models for generating the words in a document, such as the popular latent Dirichlet allocation model, possess a rich representational power by allowing the words in each document to be generated from more than one topic. This increased representational power comes at the cost of a more challenging unsupervised estimation problem of how to estimate the topic probability vectors (the distributions over words for each topic), when only the words are observed and the corresponding topics are hidden.
  
  We provide a simple and efficient unsupervised learning procedure that is guaranteed to recover the parameters for a wide class of mixture models, including latent Dirichlet allocation (LDA). For LDA, the procedure correctly recovers both the topic probability vectors and the prior over the topics, using only trigram statistics (i.e. third order moments, which may be estimated with documents that contain just three words). The method, termed Excess Correlation Analysis (ECA), is based on a spectral decomposition of low order moments (third and fourth order) via two singular value decompositions (SVDs). Moreover, the algorithm is scalable since the SVD operations are carried out on k by k matrices, where k is the number of latent factors (e.g. the number of topics), rather than in d-dimensional observed space (typically d >> k).
  
• Friday, April 20, 2012: Speaker: Ivan Corwin (MSR New England). Topic: A Few Ideas from Random Matrix Theory and Related Fields
  I will present a few fundamental ideas and methods from random matrix theory as well as related fields such as growth processes and particle systems. In particular, I will explain the moment method as well as the role of orthogonal polynomials and symmetric functions in the analysis of these systems. No background will be necessary and some detailed examples will be given.
• Friday, April 13, 2012: Speaker: Eric Price (MIT). Topic: Nearly Optimal Sparse Fourier Transform
  We consider the problem of computing the k-sparse approximation to the
  discrete Fourier transform of an n-dimensional signal. We show:
  
  - An O(k log n)-time randomized algorithm for the case where the input signal
  has at most k non-zero Fourier coefficients, and
  
  - An O(k log n log(n/k))-time randomized algorithm for general input signals.
  
  Both algorithms achieve o(n log n) time, and thus improve over the
  Fast Fourier Transform, for any k = o(n). They are the first known
  algorithms that satisfy this property. Also, if one assumes that the
  Fast Fourier Transform is optimal, the algorithm for the exactly
  k-sparse case is optimal for any k = n^{Omega(1)}.
  
  We complement our algorithmic results by showing that any algorithm
  for computing the sparse Fourier transform of a general signal must
  use at least Omega(k log(n/k) / log log n) signal samples, even if it is
  allowed to perform adaptive sampling.
  
  Joint work with Haitham Hassanieh, Piotr Indyk, and Dina Katabi.
  Appearing at STOC, and available at http://arxiv.org/abs/1201.2501
• Friday, April 6, 2012: Speaker: Thomas Vidick (MIT). Topic: Multi-prover Interactive Proofs with Entangled Provers
  I will talk about a new result on the hardness of multi-prover
  interactive proofs with entangled provers: we prove that MIP* contains
  NEXP (joint work with Tsuyoshi Ito). This answers a question open
  since entangled-prover interactive proofs were first introduced: it
  was not know if the use of entanglement could lead to a systematic
  collapse of MIP = NEXP [BFL'91]. The result can also be seen as a step
  towards a form of quantum PCP theorem.
  
  The goal will be to give an idea of why we study entangled-prover
  interactive proofs (or, entangled games), why they are challenging,
  and why their analysis may teach us something even about the classical
  setting. I will discuss a quantum analogue of BLR's linearity test,
  and extend it to prove the soundness of Babai, Fortnow and Lund's
  multilinearity test in the presence of entangled provers.
• Friday, March 30, 2012: Speaker: Shubhangi Saraf (IAS). Topic: Tight Lower Bounds for 2-query LCCs Over Finite Fields
  A locally correctable code (LCC) is an error correcting code mapping d
  symbols to n symbols, such that for every codeword c and every received word r
  that is delta-close to c, we can recover any coordinate of c (with high
  probability) by only making a few queries to r. LCCs are a stronger form of
  Locally Decodable Codes (LDCs) which have received a lot of attention recently
  due to their many applications and surprising constructions.
  
  A linear LCC over a finite field F_p is a code where the codewords form a linear
  subspace of F_p^n. The code whose codewords are the truth tables of linear
  functions evaluated on all of F_p^n is an example of a linear LCC that uses
  only 2 queries. In this talk we will show that in some sense this is the only
  example of a linear 2 query LCC over F_p.
  Specifically, we prove a lower bound of the form p^(delta*d) on the length n of
  linear 2-query LCCs over F_p, that encode messages of length d. This also gives
  a separation between 2 query LCCs and 2 query LDCs over finite fields of prime
  order.
  
  Constructions of such 2 query LCCs are intimately related to special
  configurations of lines and points in F_p^n with interesting incidence
  properties. The problem of ruling out constructions of small 2-query LCCs boils
  down to showing that certain configurations of points and lines do not exist.
  Our proof makes use of tools from additive combinatorics. We also obtain, as
  corollaries of our main theorem, new results in incidence geometry over finite
  fields, such as an improvement to the Sylvester-Gallai theorem over finite
  fields and a new analog of Beck's theorem over finite fields.
  
  This is joint work with Arnab Bhattacharyya, Zeev Dvir and Amir Shpilka.
• Friday, March 23, 2012: Speaker: Christian Sommer (MIT). Topic: Exact and Approximate Shortest-Path Queries
  We discuss the problem of efficiently computing a shortest path between two nodes of a network --- a problem with numerous applications. The shortest-path query problem in particular occurs in transportation (route planning and navigation or also logistics and traffic simulations), in packet routing, in social networks, and in many other scenarios.
  
  Strategies for computing answers to shortest-path queries may involve the use of pre-computed data structures (also called distance oracles) in order to improve the query time. We survey the main ideas and techniques of shortest-path query methods --- some of them are used in state-of-the-art route planning software such as Microsoft Bing Maps.
• Friday, March 2, 2012: Speaker: Swastik Kopparty (Rutgers University). Topic: The Complexity of Powering in Finite Fields
  I will talk about lower bounds for computing the map x -> x^k over the finite field F_{2^n}, by bounded depth arithmetic circuits over F_2 (aka AC^0(parity)). It involves studying things like the correlation of the cubic residue character with low degree polynomials over F_2.
• Friday, February 17, 2012: Speaker: Guy Kindler (Hebrew University). Topic: Gaussian Noise Sensitivity and Fourier Tails
  I will show some new work with Ryan O’Donnell where we manage to prove classical results such as Borel’s isoperimetric inequality with very short proofs using only high school trigonometric equalities. Then we combine this with the invariance principle (which we will prove as well) to get results such as Majority is Stablest and Bourgain’s Junta Theorem. No background in Harmonic analysis etc. is assumed.
• Friday, November 11, 2011: Speaker: Ran Raz (Weizmann). Topic: The Surprise Examination Paradox and the Second Incompleteness Theorem
  We give a new proof for Godel's second incompleteness theorem, based
  on Kolmogorov complexity, Chaitin's incompleteness theorem, and an
  argument that resembles the surprise examination paradox.
  
  We then go the other way around and suggest that the second
  incompleteness theorem gives a possible resolution of the surprise
  examination paradox. Roughly speaking, we argue that the flaw in the
  derivation of the paradox is that it contains a hidden assumption that
  one can prove the consistency of the mathematical theory in which the
  derivation is done; which is impossible by the second incompleteness
  theorem.
  
  I will start the talk by a short informal introduction to Godel's
  first and second incompleteness theorems.
  
  No knowledge in logic will be assumed.
  
  Joint work with Shira Kritchman
• Friday, November 4, 2011: Speaker: Eli Ben-Sasson (Technion/MSR New England). Topic: An Additive Combinatorics Approach to the Study of the Log-rank Conjecture in Communication Complexity
  For a {0,1}-valued matrix M let CC(M) denote the deterministic communication complexity of the boolean function associated with M. The log-rank conjecture of Lovasz and Saks [FOCS 1988]
  
  states that CC(M) <= log^c(rank(M)) for some absolute constant c where rank(M) denotes the rank of M over the field of real numbers.
  
  We show that CC(M) <= c rank(M)/ log rank(M) for some absolute constant c, assuming a well-known conjecture from additive combinatorics, known as the Polynomial Freiman-Ruzsa (PFR) conjecture.
  
  Our proof is based on the study of the "approximate duality conjecture" which was recently suggested by Ben-Sasson and Zewi [STOC 2011] and studied there in connection to the PFR conjecture. First we improve the bounds on approximate duality assuming the PFR conjecture. Then we use the approximate duality conjecture (with improved bounds) to get the aforementioned upper bound on the communication complexity of low-rank martices, and this part uses the methodology suggested by Nisan and Wigderson [Combinatorica 1995].
  
  Joint work with Shachar Lovett and Noga Zewi
• Friday, October 28, 2011: Speaker: Irit Dinur (Weizmann/MSR New England). Topic: Hardness of Approximation for Vertex-cover and Approximate Coloring
  I'll talk about an old (2001) result on the hardness of approximating vertex cover, and how we recycled this result to get a newer (FOCS '10) paper about the hardness of approximate coloring.
  
  Based on joint work with Subhash Khot, Will Perkins & Muli Safra
• Friday, October 21, 2011: Speaker: Eric Blais (CMU). Topic: Testing k-linear Functions
  Blum, Luby, and Rubinfeld (1993) showed that it is possible to test whether a boolean function is linear -- or, equivalently, whether it returns the parity of some of its inputs -- with a constant number of queries. A closely related problem is testing whether a function returns the parity of *exactly* k of its input bits. We call this problem the k-linearity testing problem.
  
  The k-linearity testing problem plays a central role in property testing on boolean functions. In particular, lower bounds on the query complexity of this problem imply strong lower bounds for testing juntas, for testing small-depth decision trees, for function isomorphism testing, and for a number of other property testing problems. Yet, despite much attention, the query complexity of the k-linearity testing problem has only been settled very recently.
  
  In this talk, we will present the near-optimal analysis of the query complexity for testing k-linearity. We will discuss the connection to other property testing problems. We will also show the connections between testing k-linearity and other areas of mathematics, including high-dimensional geometry, intersecting families, parity decision trees, and communication complexity.
  
  This talk will cover joint work with Noga Alon, Joshua Brody, Daniel Kane, Kevin Matulef, Ryan O'Donnell, Amit Weinstein, and Yuichi Yoshida.
• Friday, October 14, 2011: Speaker: Michael Forbes (MIT). Topic: Identity Testing of Tensors, Low Rank Recovery and Compressed Sensing
  A matrix A naturally defines a quadratic form x^tAy. If A is of rank <=r, then the rank<=r decomposition of A corresponds naturally to a size ~2nr circuit for computing the quadratic form. It is clear how to perform "white box" polynomial identity testing for such circuits, and the motivating question for this work is to explore black-box identity testing. The probabilistic method shows that there is a size ~2nr hitting set for such polynomials. In this work we match this bound (over large fields), which is optimal up to constant factors.
  
  Further, we explore how A can be reconstructed from the evaluations of the quadratic form. Similar probabilistic constructions show that there exist ~4nr evaluations which determine any such matrix A. Again, we match this bound (over large fields) with an explicit construction, and furthermore give a polynomial-time algorithm to reconstruct A from such evaluations. More generally, we show an efficient reduction from (exact) low-rank matrix reconstruction to (exact) sparse recovery. This reduction is novel in the compressed-sensing realm as it is field independent and unrelated to convex optimization.
  
  Finally, we also derive some similar, but weaker, results for higher-order tensors.
  
  Joint work with Amir Shpilka.
• Friday, October 7, 2011: Speaker: Gregory Valiant (UC Berkeley). Topic: The Surprising Power of Linear Estimators
  For a broad class of practically relevant distribution properties, which includes entropy and support size, nearly all of the proposed estimators have an especially simple form. Given a set of independent samples from a discrete distribution, these estimators tally the vector of summary statistics - the number of domain elements seen once, twice, etc. in the sample - and output the dot product between these summary statistics, and a fixed vector of coefficients. We term such estimators linear. This historical proclivity towards linear estimators is slightly perplexing, since, despite many efforts over nearly 60 years, all proposed such estimators have significantly suboptimal convergence, compared to our recent bounds. In joint work with Paul Valiant, in some sense vindicating this historical insistence on linear estimators, we show that for any property in this broad class, there exists a near-optimal linear estimator. Our proof exposes---and relies on---a fundamental relationship between `good' lower bound instances, and 'good' linear estimators.
• Friday, September 30, 2011: Speaker: David Steurer (MSR New England). Topic: Making the Long Code Shorter with Applications to the Unique Games Conjecture
  The long code is a central tool in hardness of approximation, especially in questions related to the Unique Games Conjecture. We construct a new code that is exponentially more efficient, but can still be used in many of these applications. Using the new code we obtain exponential improvements over several previous results on integrality gaps and alphabet reductions.
  
  Underlying our results is a new connection between locally testable codes and small-set expanders with many large eigenvalues.
  
  As a prequel to this talk, I will also report on the status of the Unique Games Conjecture in general.
  Based on joint work with Boaz Barak, Parikshit Gopalan, Johan Hastad, Raghu Meka, and Prasad Raghavendra.
• Friday, September 23, 2011: Speaker: Aleksander Mądry (MSR New England). Topic: Online Algorithms and the k-server Problem
  I will be talking about a recent result that establishes a polylogarithmic-competitive algorithm for the k-server problem (this is joint work with Nikhil Bansal, Niv Buchbinder, and Seffi Naor). I plan to start with a brief presentation of the history and background of the problem and then will describe the sketch of the result, as well as, cover in more detail some of its parts that I believe to be interesting. No background on the k-server problem (or online algorithms, in general) is assumed.
• Friday, September 16, 2011: Speaker: Shachar Lovett (IAS). Topic: T-designs and k-wise Independent Permutations
  I will speak on a recent work with Greg Kuperberg and Ron Peled. We show existence of small families of t-designs and k-wise independent permutations using local limit theorems. For t-designs we are able to handle almost all setting of parameters, while previous results (e.g. Teirlinck thm) were able to show existence only for a few settings; and for k-wise independent permutations we can handle any k, while previous results could only handle k=1,2,3).
• Friday, September 9, 2011: Speaker: László Lovász (Eötvös Loránd University). Topic: Theory of Graph Limits
  (no abstract)
• Friday, September 2, 2011: Speaker: Avi Wigderson (IAS). Topic: Determinant and Permanent
  I'll survey a few of many old and new results about these two similar, yet so different polynomials.
  The main purpose is to ask a few of many, old and new open problems about them, and prove few of many old and new results, focusing on arithmetic complexity. No particular knowledge is required.