| 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:
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
|
| 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:
|
| 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 Disabilites: |
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. |