| Logistics: | TTh 11-12:30 GDC 4.516 Unique Number: 51910 Course web page: http://www.cs.utexas.edu/~diz/395T |
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Office: GDC 4.508 Phone: 471-9729 Office Hours: M 3:30-4:30, W 2:30-3:30 |
| TA: | Akshay Kamath Email: kamath@cs.utexas.edu Office: GDC 1.302 Office Hours: F 10:30-11:30 |
| Course Overview: |
Randomization is extremely useful in almost all areas of computer science,
such as algorithms, cryptography, and distributed computing.
Can we derandomize algorithms, i.e., convert randomized algorithms into
deterministic algorithms?
Can we save random bits for tasks that do require randomness?
How can we get randomness, when the easily accessible sources of randomness
have little entropy?
What does it mean for a fixed object, such as a graph, to be "random-like"?
In this course, we will study these and related questions. Our explorations will lead us to several important, related pseudorandom objects: pseudorandom generators, expander graphs, randomness extractors, and error-correcting codes. A tentative list of topics follows. Basics: Randomized algorithms, basic coding theory, k-wise independence, small-bias spaces. Expander Graphs: Chernoff bound for random walks, explicit constructions, SL=L. Randomness Extractors: Seeded vs. seedless extractors, relation to expanders, constructions. Polynomial Method and List Decoding: List decoders for RS codes and Parvaresh-Vardy codes, uses for extractors, Kakeya sets and mergers, capset problem. Unconditional PRGs: Fourier analysis, PRG for polynomials, AC0, and Space-Bounded Computation. PRGs and Hardness: cryptographic setting, derandomization setting, extractors from black-box PRGs, PRGs from shrinkage. Two-Source Extractors and Ramsey Graphs: Recent constructions using nonmalleable extractors and resilient functions.
|
| Useful References: | The main text for this class will be
Salil Vadhan's
Pseudorandomness survey/monograph. My 2001 class with lecture notes. Simons Institute Pseudorandomness Boot Camp videos.
Similar classes:
Books/Surveys:
Papers: |
| Prerequisites: | Mathematical and computational maturity, plus familiarity with the following topics:
|
| Grading: |
90%: Homework 10%: Participation |
| Homework policy: |
Collaboration policy:
While you should first think about the problems on your own,
you are encouraged to discuss the problems with your classmates.
Please limit your collaborations on any particular homework to
at most three other students.
Discussion of homework problems may include brainstorming and verbally walking through possible solutions, but should not include one person telling the others how to solve the problem. In addition, each person must write up their solutions independently, and these write-ups should not be checked against each other or passed around or emailed.
You must acknowledge any collaboration by writing your collaborators' names on the front page of the assignment.
You don't lose points by having collaborators.
Citation policy: Try to solve the problems without reading any published literature or websites, besides the class text and links off of the class web page. If, however, you do use a solution or part of a solution that you found in the literature or on the web, you must cite it. Furthermore, you must write up the solution in your own words. You will get at most half credit for solutions found in the literature or on the web. Submission policy: Homeworks are due at the beginning of class. No late homeworks will be accepted. |
| Canvas: | 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. |
| Laptops/Phones: | The use of laptops and mobile devices is generally prohibited; however, I will allow use of tablets if you sit in the first row and only use them for class-related purposes. Other exceptions may be made in unusual circumstances. All phones must be silenced. |
|
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. |