Alán Aspuru-Guzik | Professor of Chemistry and Chemical Biology
Harvard University | 12 Oxford Street, Room M113 | Cambridge, MA 02138
(617)-384-8188 |
http://aspuru.chem.harvard.edu |
http://about.me/aspuru
---------- Forwarded message ----------
From: Ryan O'Donnell <odonnell(a)cs.cmu.edu>
Date: Fri, Oct 9, 2015 at 9:59 AM
Subject: Fwd: Harvard/MIT/MSR Reading Group:
To: Alan(a)aspuru.com
Hi. We haven't met, but I'm giving a talk at Harvard today (Maxwell Dworkin
119 at 1:30) on a couple of papers I thought you might possibly be
interested in, on the mathematics of optimal quantum tomography.
http://www.cs.cmu.edu/~odonnell/papers/quantum-spectrum-testing.pdf
http://www.cs.cmu.edu/~odonnell/papers/quantum-tomography.pdf
In case you or your colleagues are interested. :)
Best,
Ryan
> -------- Forwarded Message --------
> Subject:
> Harvard/MIT/MSR Reading Group:
> Date:
> Sun, 27 Sep 2015 15:50:38 -0400
> From:
> Madhu Sudan <madhu(a)cs.harvard.edu>
> Reply-To:
> madhu(a)cs.harvard.edu
> To:
> theory-reading-group(a)csail.mit.edu
>
>
> Dear Friends
>
> Many of you are probably familiar with the MSR/MIT Reading group that
several
of us co-organized in the past. (For those who are not familiar,
this is a forum for in-depth seminars - 3hrs long - whiteboard only
presentations where the speakers, and audience, get into the technical
details of new and exciting results. While the seminar runs long, the
audience is encouraged to attend for as long as they prefer, with a break
at the 1.5hr mark being a particularly convenient time to stop.)
>
> Based on semi-popular demand, Boaz Barak, Bobby Kleinberg, Aleksander
Madry,
Ankur Moitra are now going to try a v2 of this seminar, now
alternating between Harvard, MIT and MSR! We hope that the three hour
seminar will be worth the additional commute and hope many of you will be
able to make it at all locations. Seminars will start at 1:30, with *pizza
at 1:15*.
>
> This new seminar will start on October 9th with Ryan O'Donnell speaking
(see title and abstract below) at Harvard. This will be followed by Bobby
Kleinberg speaking at MIT and hopefully many more exciting talks in rough
alternation. (And MSR will host in the summer.)
>
> We will continue to use the old mailing list for this seminar, but if
you are
not already subscribed, you may do so by going to
https://lists.csail.mit.edu/mailman/listinfo/theory-reading-group . For
more information on the reading group, please visit
http://theory.csail.mit.edu/reading-group .
>
> Looking forward to seeing many of you on October 9 and then every
Friday
afterwards!
>
> Boaz, Bobby, Aleksander, Ankur & Madhu
>
>
-----------------------------------------------------------------------------------------------------------------------------
>
> Friday, October 9, 2015 (1:30-4:30) at Harvard, Maxwell-Dworkin 119:
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 Robinson-Schensted-Knuth 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 eps-far 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 d-dimensional
*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 one-hour
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.
>
>
>
>