| Logistics: | MW 4:30-6:00 TAY 3.144 Unique Number: 52088 Course web page: http://www.cs.utexas.edu/users/diz/395T |
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Office: TAY 3.134 Phone: 471-9729 Office Hours: TTh 5:00-6:00, or by appointment |
| Course Overview: |
Randomization is very useful in almost all areas of computer science,
such as algorithms, cryptography, and distributed computing.
These uses of randomness seem wonderful until one realizes that
computers do not use truly random bits.
Instead, most computers get their random bits by using pseudorandom generators.
A pseudorandom generator is a deterministic algorithm that takes as input a
short random seed and outputs a long string which is ``random'' enough
for the purpose at hand.
In this course, we will develop provably good pseudorandom generators
for a variety of tasks.
I will lecture for the first 60% of the class; the last 40% will be student presentations. Some key topics are expanders, extractors, pseudorandom generators from hard functions, and coding theory. This course will be similar in spirit to the version I taught in 2001, but the overlap will be less than half. We will be able to cover more as I didn't require CS 388C last time. |
| Useful References: | There is no text for this course. Much of the material I cover
can be found in my lecture notes from the 2001 version.
Other useful references are: Salil Vadhan's lecture notes; Oded Goldreich's book, Modern Cryptography, "Probabilistic Proofs and Pseudorandomness"; Peter Bro Miltersen's book chapter, "Derandomizing Complexity Classes." |
| Prerequisites: | CS 388C or equivalent or permission of instructor. |
| Grading: | 50%: Homework 50%: Presentations |
| Homework policy: |
Collaboration policy: I encourage you to discuss homework
problems with your classmates.
However, you must write up your own solutions.
Furthermore, you must acknowledge any collaboration by writing the
names of your collaborators on the front page of the assignment.
Citation policy: If you 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. |
| Student Presentations: | Each student will give two presentations. Paper suggestions will be distributed later in the semester. |
|
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. |