Drafts of lecture notes

Lecture 1. Introduction. Sublinear models of computation. .pdf file, .tex file. Scribe: Josh Cain.
Lecture 2. Probability basics. Markov, Chebyshev, Chernoff. .pdf file, .tex file. Scribe: Jacques Pienaar.
Lecture 3. Testing connectivity of graphs. .pdf file, .tex file .bib file. Scribe: Purnima Kapoor.
Lecture 4. Estimating the number of connected components and minimum spanning tree. .pdf file, .tex file .bib file. Scribe: Pinar Delul.
Lecture 5. Szemeredi's regularity lemma. Testing triangle freeness. .pdf file, .tex file .bib file. Scribe: Abram Magner.
Lecture 6. Proof of the triangle-removal lemma. .pdf file, .tex file. Scribe: Stephanie Oh.
Lecture 7. Roth's theorem. Lower bound for testing triangle freeness. .pdf file, .tex file .bib file. Scribe: Greg Hurst.
Lecture 8. Testing if a list is sorted. Testing monotonicity of functions. .pdf file, .tex file. Scribe: Vivek Patel.
Lecture 9. Transitive-closure spanners. .pdf file, .tex file .bib file. Scribe: Bhaskar Sarma.
Lecture 10. Graph expansion, Cheeger's inequality and extensions. .pdf file, .tex file. Scribes: Pinar Delul, Pawan Nagesh.
Lecture 11. The probabilistic method. Existence of vertex-expanders. .pdf file, .tex file .bib file. Scribe: Vaishnavi Chandrasekaran.
Lecture 12. More applications of expanders: application to data structures. .pdf file, .tex file .bib file. Scribe: Jeff Gaither.
Lecture 13. Intro to error-correcting codes. .pdf file, .tex file. Scribe: Nader Alawadi.
Lecture 14. Hamming, Hadamard, Reed-Solomon codes. Hamming bound. .pdf file, .tex file .bib file. Scribe: Selvakumaran Vadivelmurugan.
Lecture 15. No class.
Lecture 16. Singleton bound. Gilbert-Varshamov bound. Good codes from expanders. .pdf file, .tex file. Scribes: Stephanie Oh and Jacques Pienaar.
Lecture 17. Continue good codes from expanders. Linear time decoding algorithm. .pdf file, .tex file. Scribe: Venkata Gandikota.
Lecture 18. Locally testable codes. Intro to the Fourier analytic method. .pdf file, .tex file. Scribe: Gowtham Kaki.
Lecture 19. Testing membership in the Hadamard code a.k.a testing linearity. .pdf file, .tex file .bib file Scribes: Josh Cain, Greg Hurst, Selvakumaran Vadivelmurugan
Lecture 20. Yao's principle. Linear lower bound for testing random LDPC codes. .pdf file, .tex file .bib file. Scribes: Vaishnavi Chandrasekaran, Pawan Nagesh, Abram Magner.
Lecture 21. Locally decodable codes. .pdf file, .tex file. Scribe: Vivek Patel.
Lecture 22. Comunication complexity basics. .pdf file, .tex file . Scribes: Venkata Gandikota, Jeff Gaither, Gowtham Kaki.
Lectures 23-31. Projects.
Lecture 32. Derandomization and pseudorandomness. .pdf file, .tex file . Scribes: Nader Alawadi, Purnima Kapoor, Bhaskar Sarma,