| Logistics: | TTh 11-12:30 WAG 112 Unique Number: 55015 Course web page: http://www.cs.utexas.edu/~diz/395T |
| Professor: | David Zuckerman Email: diz@cs.utexas.edu Office: TAY 3.134 Phone: 471-9729 www.cs.utexas.edu/~diz Office Hours: TBD |
| 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. We will also study several important, related pseudorandom objects: expander graphs, randomness extractors, and error-correcting codes. We will discuss several recent results, including algebraic extractors from codes, applications of additive number theory, pseudorandom generators for polynomials, and SL=L. |
| Grading: | Based on homework (about three problem sets) and a presentation. |