IAP 2009, taught by Greg Price under the auspices of SIPB.
Each lecture is at 7:30 PM in 56-114. The lectures are independent; come to any subset.
Jan 20: Cryptography. What is a secret? Do we really know how to keep one? We'll study what we can hope to prove about a cryptosystem's security, and sketch how we achieve those limits for one cryptosystem—and how your favorite cryptosystem doesn't.
Corresponds to most of 6.875 but without the proofs. In the Spring 2008 notes (which unfortunately require certs), see 3-13 for philosophy, 2-14 and 2-21 for the main cryptosystem of that course and this lecture, 2-26 for extending it from one bit to many, 2-28 and 3-4 for the precise, essentially maximal notion of security it satisfies (modulo, as always, a hardness assumption.)
Jan 22: Linear Programming and Beyond: How to Optimize (Almost) Anything.
Taught in a segment of 6.854. For a written presentation of LP try David Karger's 6.854 lecture notes, or this short book on the web.
Jan 27: More Randomness, Less Data, Better Results. We'll study how we can analyze big datasets in a small amount of space by a random linear projection, and how to break down a big matrix into its few most interesting pieces.
Not part of the regular curriculum. The central Johnson-Lindenstrauss lemma is briefly stated on Wikipedia and proved with concrete bounds in these lecture notes, as well as many other proofs on the web.
(cancelled) Jan 29: Information, Learning, Inference.
This lecture would have studied the maximum-entropy principle
(wikipedia,
expository paper)
as an organizing principle for combining different forms of
knowledge, including
a derivation of Bayes'
Theorem, as well as for understanding how a sample from a
distribution is likely to diverge from its average.
Roughly corresponds to part of 6.437. Unfortunately the lecture notes from there are restricted; try the links above.