CS395T: Expanders and Extractors (Fall 2020)

Logistics: This class will meet online while COVID-19 levels in Austin are high, as they are currently (August 17). If and when COVID levels drop to a safe level, we will meet in person, with the room filled to at most 40% capacity. Even if/when we meet in person, students will have the option of attending remotely, although the in-person experience should be better. I encourage you to sign up for the hybrid class, so that you have the option of meeting in person if/when COVID levels improve. However, if you know for sure that you don't want to meet in person at all, for example if you won't even be in Austin, then sign up for the internet class.
TTh 2-3:30
Zoom via Canvas
GDC 5.302 (if/when we meet in person)
Unique Number: 51424 (hybrid or blended); 51425 (internet)
Course web page: http://www.cs.utexas.edu/~diz/395T
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Office: GDC 4.508
Office Hours: TTh 3:30-4:30
TA: William Hoza
Email: whoza@utexas.edu
Office Hours: M 11-12
Course Overview: Expander graphs and randomness extractors are fundamental objects in the study of pseudorandomness. An expander is a graph where any subset of nodes has many neighbors. A randomness extractor is an efficient algorithm to purify randomness. These are related in non-obvious ways and have many applications to a wide variety of areas, including pseudorandomness, coding theory, cryptography, randomized algorithms, network constructions, inapproximability, and data structures. In this course, we will explore these objects and their applications, including recent developments such as two-source extractors and high-dimensional expanders.

Plan for first five lectures:
Lecture 1: Introduction and probabilistic method
Lectures 2-5: Before class, watch the next video in my four-part tutorial on Extractors and Expanders We will discuss the content of the video in the lecture.

A tentative list of topics for the remaining lectures is as follows. I'll probably have to cut at least one of these topics.

Error-correcting codes
Expander constructions
Applications of expanders
Graph sparsifiers
Extractor constructions
Applications of extractors
Small set expansion
Seedless extractors
High-dimensional expanders
Non-malleable extractors and two-source extractors

Useful References: Salil Vadhan's Pseudorandomness survey/monograph
Dan Spielman's draft textbook Spectral and Algebraic Graph Theory
Guruswami, Rudra, and Sudan's book, Essential Coding Theory
Hoory, Linial, and Wigderson's survey, Expander Graphs and their Applications
Nick Harvey's talk Graph Sparsifiers: A Survey
Prerequisites: Mathematical and computational maturity, plus familiarity with the following topics:
  • Discrete Probability, including moments and deviation bounds of Markov, Chebyshev, and Chernoff;
  • Algebra, including vector spaces, eigenvectors/eigenvalues, and finite fields;
  • Combinatorics and Graph Theory, at least knowledge of the basics;
  • Complexity Theory, including P, NP, NP-completeness, and reductions.
Grading: 90%: Homework (every 2-3 weeks)
10%: Participation
Canvas/Piazza: We will use Canvas, which contains Piazza. Homeworks and grades will be posted on Canvas. We will use Piazza for class discussion. Instead of emailing questions to the teaching staff, please post your question to Piazza. The official syllabus is posted on Canvas.
Students with
Any student with a documented disability (physical or cognitive) who requires academic accommodations should contact the Services for Students with Disabilities area of the Office of the Dean of Students at 471-6259 (voice) or 471-4641 (TTY for users who are deaf or hard of hearing) as soon as possible to request an official letter outlining authorized accommodations.

Last modified: October 6, 2020