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). 
Spencer’s paper. 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)  p1729 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)  p2528 from Theorist's Toolkit  
Oct 3: More fun with lossless expanders: Expander Codes. Started eigenvalues <>expansion 
Spielman's lecture notes. For eigenvalues see p 2931 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 2935. Expander mixing lemma is here. Random walks are introduced in Toolkit p 3941. 
Isoperimetry. 
Oct 10: (Guest lectuer Nisheeth Vishnoi) Various ways of understanding/estimating graph expansion.  Arora, Rao, Vazirani paper; read first 89 pages.  
Oct 15: Data problems and fitting models to data. Max. likelihood estimation, a few examples (fitting the best line, the best kdim subspace, and best mixture of identical gaussians) and hardness results.  Intro to MLE estimation.  
Oct 17: Intro to highdimensional geometry. Gaussian nature of projections. JohnsonLindenstrauss 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) Epsilonnet for range spaces. Kleinberg's algorithm for detecting network failures. (b) Epsilonnet in metric spaces. Approx. nearest neighbor search in metric spaces.  Kleinberg's paper on Detecting network failures (only Sections 1 and 2) and KrauthgamerLee paper on Nearest Neighbor Searching. 
Scribe notes by Aditya Bhaskara. 
Nov 5: More continuous thinking; LP and LP duality. Application: LPbased decoding of expander codes.  Discussion of LP duality in toolkit notes. Feldman et al. paper on LP decoding. 
Section on LP in Toolkit. Scribe notes. 
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 p3133) 
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.) Scribe notes. 
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: AlonNaor SDP relaxation for matrix discrepancy. Discussion of problems for final project.  
Dec 3: Natural proofs and meditation on nonconstructive techniques.  Chapter from AroraBarak 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 