|Date & Topic||Readings||Additional Links & Activities|
|Sept 17: 20 Questions with a liar; Tenure games
(ideas introduced: perfect information games, winning strategies, error correcting codes, probabilistic method, linearity of expectation).
Lecture slides (unnamed author?) from Heidelberg.
|Google "Ulam's Liar Problem."|
|Sept 19: Analysis of 20 qs with a liar; asymptotic case
(ideas discussed: chip games, adversary strategies, simple chernoff bounds)
|Three Thresholds for a liar by Spencer & Winkler.||John Canny's handout on Chernoff Bounds. (one of many possibilities on the web)|
|Sept 24: Fault Tolerant Computation I: Boolean Circuits. (introduced idea of expanders)||p17-29 of Peter Gacs's chapter on Reliable Computation|
|Sept 26: Fault tolerant computation II: Cellular Automata (might be useful in new computational models, eg those arising in nanotechnology)||Gacs's paper "Toom's proof."|
|Oct 1: Fun with lossless expanders: Circuit switching (routing using disjoint paths)||p25-28 from Theorist's Toolkit|
|Oct 3: More fun with lossless expanders: Expander Codes.
Started eigenvalues <->expansion
|Spielman's lecture notes.
For eigenvalues see
p 29-31 of Theorist's Toolkit.
|Oct 8: Thinking continuously. Eigenvalues and isoperimetry/expansion.
Expander mixing lemma. Introduction to mixing of random walks.
|For eigenvalues and expansion, see Toolkit p 29-35.
Expander mixing lemma is here. Random walks are introduced in Toolkit p 39-41.
|Oct 10: (Guest lectuer Nisheeth Vishnoi) Various ways of understanding/estimating graph expansion.||Arora, Rao, Vazirani paper; read first 8-9 pages.|
|Oct 15: Data problems and fitting models to data. Max. likelihood estimation, a few examples (fitting the best line, the best k-dim subspace, and best mixture of identical gaussians) and hardness results.||Intro to MLE estimation.|
|Oct 17: Intro to high-dimensional geometry.
Gaussian nature of projections. Johnson-Lindenstrauss dimension reduction.
|See toolkit Chapter 7 (excluding Section 7.2) for this and next lecture.|
|Oct 19: Intro to VC dimension, and sampling lemma for range spaces of low VC dimension.||See relevant chapter in Toolkit.|
|Oct 23: No lecture due to FOCS|
|Oct 25: Two different notions that both happen to be called epsilon nets, and their applications. (a) Epsilon-net for range spaces. Kleinberg's algorithm for detecting network failures. (b) Epsilon-net in metric spaces. Approx. nearest neighbor search in metric spaces.||Kleinberg's paper on Detecting network failures (only Sections 1 and 2) and Krauthgamer-Lee paper
on Nearest Neighbor Searching.
|Scribe notes by Aditya Bhaskara.|
|Nov 5: More continuous thinking; LP and LP duality. Application: LP-based decoding of expander codes.||Discussion of LP duality in toolkit notes.
Feldman et al. paper on LP decoding.
|Section on LP in Toolkit.
|Nov 7: SDP; Uses of SDPs in proofs|
|Nov 12: Proof of Roth's 1/4 theorem using SDPs.||Lovasz's survey.
(Roth's Thm p31-33)
|Rest of Lovasz's survey|
|Nov 13: Theta function, theta function of random graphs and of pentagon||Scribe notes coming soon|
|Nov 19: Guest lecture by Venkat Guruswami; Compressed sensing, and subspaces of R^n where l_1 and l_2 norms are similar.||Remark on compressed sensing by Kashin and Temlyakov.||Terry Tao's favorite open problem in this area.
(Also a clear description of the area.)
|Nov 21: no lecture but we will go for coffee to a nearby cafe and discuss research.|
|Nov 26: Uses of tensoring. Theta function of pentagon, SDP duality and Cone duality.|
|Nov 28: More tensoring: Alon-Naor SDP relaxation for matrix discrepancy. Discussion of problems for final project.|
|Dec 3: Natural proofs and meditation on nonconstructive techniques.||Chapter from Arora-Barak book|
|Dec 5: Intro to Fourier analysis and its uses in TCS. Influence and Total Influence; relation to isoperimetry theorems on the hypercube.||Scribe notes|
|Dec 11: More fourier analysis. Friedgut's theorem and intro to hypercontractivity. Uses in TCS.||Scribe notes|