| Syllabus: | Syllabus. |
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Office: GDC 4.508 Phone: 471-9729 Office Hours: TTh 3:30 - 4:30 |
| TA: | Yan Zheng Email: yanzheng@utexas.edu Office (for office hours): TA Station (GDC 1.302), Desk 2 Office Hours: MW 5:00 - 6:00. |
Required Text: | Stasys Jukna, Extremal Combinatorics, with applications in computer science (2nd edition) |
| Optional Texts: |
N. Alon and J. H. Spencer,
The Probabilistic Method
(
ebook
available with UT EID)
L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics, with applications to geometry and computer science V. Guruswami, A. Rudra, and M. Sudan, Essential Coding Theory L. Guth, Polynomial Methods in Combinatorics S. Vadhan, Pseudorandomness survey/monograph. J.H. van Lint and R.M. Wilson, A Course in Combinatorics |
| Useful References: |
Richard Stanley's
Twelvefold Way
for balls in bins.
Scribe notes containing Shannon's counting argument for the existence of functions with large circuit complexity Salil Vadhan's monograph on pseudorandomness contains chapters on expander graphs and randomness extractors. S. Hoory, N. Linial, and A. Wigderson, Expander Graphs and Their Applications, a survey. Excerpts from L. Guth, Polynomial Methods in Combinatorics includes Nikodym sets on pages 11-12. J.A. Grochow, New applications of the polynomial method: The cap set conjecture and beyond Lecture notes from my class includes pseudorandomness, codes, expanders, and more. My four-part tutorial on Extractors and Expanders at the Simons Institute. My slides on randomness extractors. |
| Final Exam: | The final exam will be held on Wednesday, December 18 from 2:00 pm-5:00 pm in GDC 5.302. No make-up exams will be given, so plan accordingly. You may bring a single, 8.5x11 inch, handwritten sheet of paper (you may use both sides). No calculators are allowed (they won't be necessary). If you're taking the course pass/fail, then you do not need to take the final exam. Instead, I will count your homework grade as your final exam grade. |