COS 597 D: Thinking Like a Theorist; Fall 2007
        Sanjeev Arora



        LECTURE TOPICS

We will occasionally use lecture notes from A Theorist's Toolkit by Sanjeev Arora.
Additional references appear later.

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) 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.		 Isoperimetry.
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.
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 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.)
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: 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





Lecture topics and references in detail.
  1. Sept 17. Joel Spencer, Randomization, Derandomization, Antirandomization: Three Games. 
  2. Sept  19: Joel Spencer, Peter Winkler. Three thresholds for a liar. We only studied the first of the three  scenarios.
  3.  Sept 24: Fault Tolerant Computation. The problem originates in von Neuman's 1956 paper: Probabilistic Logics and Synthesis of Reliable Organisms from Unreliable Components. Gacs' survey has many other references.
  4. Oct 1: Intrigued by expanders? See the lovely survey on Expanders and their Applications by Hoory, Linial, and Wigderson. The world of expanders is large and growing.
  5. Oct 3: Expander codes are related to LDPC codes, invented by Gallagher in 1963. The analysis of expander codes in this lecture is a simple version of the one in the paper Expander Codes by Sipser and Spielman.
  6. Oct 7: For an introduction to isoperimetry in mathematics, a good starting point is the wikipedia entry.
  7. Oct 10:
  8. Oct 15: The survey Spectral Algorithms by Ravi Kannan and SantoshVempala is recommended. It also contains the analysis of how to fit the best line to n-dimensional data, and an introduction to learning mixtures of gaussians. 
    Probabilistic reasoning (especially bayesian reasoning, which is popular) is a powerful tool in many applications. See this survey of Diaconis and Holmes for a bayesian analysis of many classical settings of probability theory. However, Diaconis also cautions that sometimes it is possible to "Think too much."