Harvard/MIT/MSR Theory Reading Group (v2.0)
About: This is a revival of the MSR/MIT Theory Reading Group.
Goal: The goal of this reading group is to learn in significant depth about (new/exciting) developments in theoretical computer science and related areas.
Formula: Each meeting consists of a threehourlong whiteboard talk given by the speaker. Talks tend to be informal in nature and quite interactive. In particular, questions from the audience are strongly encouraged. There is a break in the middle – it is not impolite to leave during this break, or indeed any time earlier or later. Ah...and we have pizza!
Time and place: The meetings will alternate between Harvard and MIT during terms, and will be held at MSR in the summer. Unless otherwise noted, the meetings will be held
on
Fridays 1:30 pm–4:30 pm (with pizza at 1:15).
Organizers:
Boaz Barak,
Robert D. Kleinberg,
Aleksander Mądry,
Ankur Moitra,
Madhu Sudan.
Mailing list: There is a mailing list where the announcements of upcoming talks, as well as, other information related to the reading group appear. To subscribe to this list, visit this
page. Please note that the mailing list is intended only for local participants. So please subscribe using an email that lets us know you are local, or send email to madhu letting him know who, and where, you are.
Upcoming Talks:

Friday, October 9, 2015 at Harvard, MaxwellDworkin G115: Speaker:
Ryan O'Donnell
(CMU)
Topic:
Lots of fun things ... (And Quantum
PCA).
Uncompressed Title: Lots of fun things, like longest increasing subsequences in random strings, property testing of probability distributions, the RobinsonSchenstedKnuth algorithm, some interesting symmetric polynomials, and basic representation theory of S_n. (And quantum PCA.)
Suppose we want to learn something about an unknown probability distribution p = (p_1, p_2, ..., p_d) on [d] = {1, 2, ..., d}. Assume we get to see n independent draws from p, forming a string w in [d]^n. If we want to learn p to accuracy eps, having n ~ d/eps^2 is necessary and sufficient. (This is one of the most ancient results in statistics: the algorithm is to just output the 'empirical histogram' of w.) If we only want to distinguish whether p is the uniform distribution or epsfar from it, then having n ~ sqrt(d)/eps^2 is necessary and sufficient. (This was only determined in 2008!)
We investigate the problem of learning an unknown ddimensional *quantum state*. This is a strict generalization in which, roughly speaking, p is a probability distribution over d unknown orthonormal *vectors*. By virtue of some basic results in representation theory (which we will explain), a large portion of the job reduces to the following: Suppose we want to learn about an unknown probability distribution p, but instead of getting to see the random string w we only get to see the data (LIS_1(w), LIS_2(w), ..., LIS_d(w)), where LIS_k(w) denotes the total length of the longest k disjoint increasing (=nondecreasing) subsequences in w. Now how large does n need to be to understand various properties of p? (For example, is it true that p_max ~ E[LIS_1(w)]?)
This is joint work with John Wright of Carnegie Mellon. A onehour overview of this material will be presented at the Charles River Lectures on Probability on Oct. 2 but attending that event is not a prerequisite for this talk.

Friday, October 16, 2015 at MIT: Speaker:
Bobby Kleinberg
(MSR)
Topic:
On the before/after privacy guarantees of differentially private mechanisms.
TBD

Friday, October 23, 2015 at Harvard, MaxwellDworkin G100: Speaker:
Cris Moore
(Santa Fe Institute)
Topic:
Statistical inference, statistical physics, and the community detection problem.
There is a deep analogy between statistical inference — where we try to fit a model to data, or (even better) understand the posterior distribution of models given the data — and statistical physics, where we define a probability distribution in terms of some energy function. Many concepts like energy landscapes, partition functions, free energy, the cavity method, and phase transitions can be usefully carried over from physics to machine learning and computer science. At the very least, these techniques are a source of conjectures that have stimulated new work in machine learning, computer science, and probability theory; at their best, they offer strong intuitions about the structure of the problem and its possible solutions.
One recent success of this flow of ideas is the discovery of a sharp phase transition in community detection in sparse graphs. This appeared in Decelle et al. in the physics literature, and was then made rigorous in beautiful work by Mossel, Neeman, and Sly, and Massoulie. Analogous transitions exist in many other inference problems, where our ability to find patterns in data jumps suddenly as a function of how noisy or how sparse they are.
I will discuss why and how the detectability transition occurs, review what is now known rigorously, and present a number of open questions that cry out for proofs. Perhaps more importantly, I will take full advantage of the excellent format of this seminar to dwell on the analogy between physics and inference, and discuss how a thermodynamic point of view helps us find structure in data, test whether this structure is statistically significant, and choose between competing models.
This is based on joint work with many people, including Aurelien Decelle, Florent Krzakala, Lenka Zdeborova, and Pan Zhang. 
Friday, November 6, 2015 at TBD: Speaker:
Zeev Dvir
(Princeton)
Topic:
TBD.
TBD
Past Talks:
Previous Version: MSR/MIT Reading Group .
Website designed by Aleksander Mądry, and currently maintained by Madhu Sudan.