Current Topics in Theoretical Computer Science

CS 59000 CTT

Fall 2012

Beering Hall of Lib Arts & Ed B232

Tu/Th 3:00 - 4:15 pm


Elena Grigorescu

Office Hours: Send email to set up a meeting.

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:
  • sublinear models of computation
  • error-correcting codes
  • expander graphs
  • additive combinatorics.
We will introduce proof techniques such as discrete Fourier analysis, the probabilistic method, Yao’s principle, and more.

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

  • Scribe 1-2 lectures.
  • Project: Present and write notes for a paper from a theoretical CS conference.
LaTeX sources for notes
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:
  • 10% for class participation.
  • 25% for scribing notes
  • 65% for the project
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.