Course description

This is a graduate level/advanced undergraduate course intended to introduce students to some exciting research directions in theoretical CS. We will cover a broad selection of areas, tentatively including topics on interconnections between:

This is a graduate level/advanced undergraduate course intended to introduce students to some exciting research directions in theoretical CS. We will cover a broad selection of areas, tentatively including topics on interconnections between:

- sublinear models of computation
- error-correcting codes
- expander graphs
- additive combinatorics.

**Prerequisites:** There are no specific course requirements other than some mathematical maturity. Some familiarity with discrete math and algorithms would be useful.

Assignments

- Scribe 1-2 lectures.
- Project: Present and write notes for a paper from a theoretical CS conference.

Resources

Books

We will not be using a textbook for the course. Some standard references are:

We will not be using a textbook for the course. Some standard references are:

- Computational Complexity

Sanjeev Arora and Boaz Barak - Randomized Algorithms

Rajeev Motwani, Prabhakar Raghavan - Probability and Computing

Michael Mitzenmacher and Eli Upfal

Related courses

The content of this course is based on the following courses:

The content of this course is based on the following courses:

- Sublinear algorithms by Sofya Raskhodnikova
- Sublinear algorithms by Ronitt Rubinfeld.
- Essential coding theory by Madhu Sudan.

Grading

- 10% for class participation.
- 25% for scribing notes
- 65% for the project

Schedule

Scribe notes.

Scribe notes.

- Aug. 21 Lecture 1. Introduction. Sublinear models of computation. Slides
- Aug. 23 Lecture 2. Probability basics. Markov, Chebyshev, Chernoff. Reference1 and Reference2
- Aug. 28 Lecture 3. Testing connectivity of graphs. Goldreich and Ron
- Aug. 30 Lecture 4. Estimating the number of connected components and minimum spanning tree Chazelle et al
- Sep. 4 Lecture 5. Szemeredi's regularity lemma. Testing triangle freeness.
- Sep. 6 Lecture 6. Proof of the triangle-removal lemma.
- Sep. 11 Lecture 7. Roth's theorem. Lower bound for testing triangle freeness. Mini-course notes and Alon
- Sep. 13 Lecture 8. Testing if a list is sorted. Testing monotonicity of functions. Dodis et al.
- Sep. 18 Lecture 9. Transitive-closure spanners. Survey
- Sep. 20 Lecture 10. Graph expansion, Cheeger's inequality and extensions. Guest lecture by Anand Louis.
- Sep. 25 Lecture 11. The probabilistic method. Existence of vertex-expanders. Lecture and Survey.
- Sep. 27 Lecture 12. More applications of expanders: application to data structures Buhrman et al.
- Oct. 2 Lecture 13. Intro to error-correcting codes.
- Oct. 4 Lecture 14. Hamming, Hadamard, Reed-Solomon codes. Hamming bound.
- Oct. 9 Lecture 15. Fall break. No class.
- Oct. 11 Lecture 16. Singleton bound. Gilbert-Varshamov bound. Good codes from expanders.
- Oct. 16 Lecture 17. Continue good codes from expanders. Linear time decoding algorithm. Sipser and Spielman
- Oct. 18 Lecture 18. Locally testable codes. Intro to the Fourier analytic method.
- Oct. 23 Lecture 19. Testing membership in the Hadamard code a.k.a testing linearity. Blum et al. and Bellare et al.
- Oct. 25 Lecture 20. Yao's principle. Linear lower bound for testing random LDPC codes. Ben-Sasson et al.
- Oct. 30 Lecture 21 Locally decodable codes. Survey
- Nov. 1 Lecture 22 Comunication complexity basics. Survey, Mihai's blog
- Nov. 6 Lecture 23. Project presentation. Gowtham & Venkata. Reference
- Nov. 8 Lecture 24. Project presentation. Pinar & Selva Reference
- Nov. 13 Lecture 25. Project presentation. Jeff & Nader Reference
- Nov. 15 Lecture 26. Project presentation. Josh & Greg Reference
- Nov. 20 Lecture 27. Project presentation. Jacques & Pawan Reference
- Nov. 22 Lecture 28. Thanksgiving. No Class
- Nov. 27 Lecture 29. Project presentation. Abram & Stephanie Reference1 Reference2
- Nov. 29 Lecture 30. Project presentation. Bhaskar & Purnima Reference
- Dec. 4 Lecture 31. Project presentation. Vaishnavi & Vivek Reference
- Dec. 6 Lecture 32. Derandomization and pseudorandomness. Course

webpage designed by Will Perkins. Contact him if you'd like to use this template.