CS395T: Pseudorandomness (Fall 2017)

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

Topics will be similar to those in the 2009 version of this class, but I will include newer results as well. I will post a tentative list of topics later.

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;
  • Complexity Theory, including P, NP, NP-completeness, and reductions;
  • Other: basic combinatorics and graph theory; exposure to some randomized algorithms.
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: May 9, 2017.