CS 294 | Pseudorandomness and Combinatorial Constructions | Fall '05

[general info]  [lecture notes] [Final Project]

General Information

Lecturer: Luca Trevisan, luca@eecs, 679 Soda Hall, Tel. 642 8006

Classes are Tuesdays and Thursdays, 2:30-4:00pm, 310 Soda

Office hours: Mondays, 2-3pm, or by appointment

Course Requirements: scribing one or two lectures  (depending on attendance); final project.

References: the main reference for the course will be scribed lecture notes. In addition, for each lecture I will give a link to the original papers were the results appeared and/or survey papers discussing the results.

About this course: In computer science, there are some important problems for which randomized algorithms are simpler and faster than the best known deterministic ones. Similarly, in combinatorics, there are some objects (e.g., expander graphs, Ramsey graphs, error-correcting codes, and many others) whose existence is easy to prove using the probabilistic method but for which we only have difficult and sub-optimal explicit constructions.

Perhaps surprisingly, work in the past 20+ years on "hardness versus randomness" suggests that every probabilistic algorithm may be simulated deterministically with comparable efficiency. In particular, this is true under certain plausible complexity-theoretic assumptions, such as that random integers are hard to factor (but much weaker assumptions suffice). Under the same assumptions, every object whose existence can be proved with the probabilistic method has an efficient construction (provided that one can efficiently recognize such an object given one).

These predictions have been recently confirmed by the Agrawal-Kayal-Saxena deterministic algorithm for testing primality in polynomial time, Reingold's deterministic algorithm to solve connectivity problems in undirected graphs using logarithmic memory, and progress on combinatorial constructions. While the primality testing algorithm is somewhat independent of the work on "hardness versus randomness," there is a deep connection between such work and some  recent combinatorial constructions as well as Reingold's algorithm.

This course will have two main, tightly woven, threads: the study of conditional results about pseudorandomness and derandomization, showing that if certain complexity-theoretic conjectures are true then every probabilistic algorithm has an efficient deterministic simulations; and the study of (unconditional) explicit construction of pseudorandom objects, such as randomness extractors and expander graphs. Several results in each thread are inspired and motivated by results in the other. The happy ending of the course will be Reingold's theorem: a use of ideas from expander graphs constructions to provide an unconditional memory-efficient derandomization of the random walk algorithm for undirected graph connectivity.

Highlights of the course:

schedule of classes

Macros for lecture notes: macros.tex contains the macros and lecture0.tex shows how to use some features.


  1. August 30 Introduction. Pairwise independent generator
    [Notes not available]
    see: [Oded Goldreich. Pseudorandomness. Survey paper, 2000] for definitions and examples
  2. September 1 epsilon-biased generators and error-correcting codes
    [Notes not available]
    see [Joseph Naor and Moni Naor. Small-bias Probability Spaces: efficient constructions and Applications, 1990] and [Noga Alon, Oded Goldreich Johan Hastad and Rene Peralta, Simple Constructions of Almost k-wise Independent Random Variables, 1992]
  3. September 6 Fourier analysis and epsilon-biased generators
    [Notes not available]
    see previous references, and also sections 2 and 3 of  [Eyal Kushilevitz, Yishay Mansour. Learning Decision Trees using the Fourier Spectrum, 1991] 
  4. September 8 Examples of functions that are ``fooled'' by epsilon-biased generator
    [Notes scribed by Varsha]
    see section 5 of Kushilevitz-Mansour and [Luca Trevisan. A Note on Deterministic Approximate Counting for k-DNF, 2004]
  5. September 13 Formal definitions of computational indistinguishability, pseudorandom generators, one-way permutation and hard-core predicates
    [Notes scribed by Gatis]
    see [Andrew Yao, Theory and applications of trapdoor functions, FOCS 1982]. I don't have an electronic version.
  6.  September 15 Construction of a pseudorandom generator using a hard-core predicate
    [Notes scribed by Ben]
  7. September 20 Extending the stretch of a pseudorandom generator
    [Notes scribed by Costas]
  8. September 22 The Goldreich-Levin theorem
    [Notes scribed by Madhur]
  9. September 27 Applications of the Goldreich-Levin theorem to learning
    [Notes scribed by Omid]
  10. September 29 Applications of very strong pseudorandom generators
    [Notes scribed by Varsha]
  11. October 4 The Nisan-Wigderson generator
    see the original paper [N. Nisan and A. Wigderson, Hardness versus Randomness]
    [Notes scribed by Alexandra] (temporarily without pictures)
  12. October 6 Constructing set systems for the Nisan-Wigderson generator. Statement of the Impagliazzo-Wigderson Theorem. Decoding the Reed-Solomon code
    [Notes scribed by Madhur]
  13. October 11 List-decoding of the Reed-Solomon code
    see the original paper [M. Sudan, Decoding of Reed-Solomon codes beyond the error-correction bound, 1996]
    [Notes from Luca's coding theory course]
  14. October 13 Concatenation of Reed-Solomon code and Hadamard code. Reed-Muller codes. Sublinear time unique decoding of Reed-Muller code.
    [Notes scribed by Radu]
  15. October 18 Sublinear time list-decoding of the Reed-Muller code. 
    see [M. Sudan L. Trevisan S. Vadhan, Pseudorandom generators without the XOR Lemma, 1997]
    [Notes scribed by Sebastien]
  16. October 20 Concatenation with of Reed-Muller code and Hadamard codes. Proof of the Impagliazzo-Wigderson theorem. Introduction to randomness extractors
    [Notes scribed by Anand]

    No class on October 25
  17. October 27 More on extractors, negative results for extractors.
    see [N. Nisan and D. Zuckerman, Randomness is Linear in Space] and [Jaikumar Radhakrishnan and Amnon Ta-Shma. Tight bounds for depth-two superconcentrators]
    [Notes  scribed by Sebastien]
  18. November 1 Extractors from the Nisan-Wigderson generator.
    see [L. Trevisan. Extractors and Pseudorandom Generators]
    [Notes scribed by Costas]
  19. November 3  Randomness condensers. Condensers from Nisan-Wigderson
    [A. Ta-Shma, C. Umans, and D. Zuckerman, Loss-less Condensers, Unbalanced Expanders, and Extractors]
    [Notes scribed by Anand]
  20. November 8 More on randomness condensers
    see the Ta-Shma-Umans-Zuckerman paper
    [Notes scribed by Alexandra]
  21. November 10 Even more on randomness condensers and on extractors from the Nisan-Wigderson generator.
    see  [R. Raz, O. Reingold, S. Vadhan. Extracting all the Randomness and Reducing the Error in Trevisan's Extractors]
    [Notes scribed by Gatis]
  22. November 15  Expanders,  random walks
    [Notes not available]
  23. November 17  Eigenvalues and expansion
    [Notes not available]
  24. November 22 The zig-zag graph product and construction of expanders 
    [Notes not available]
  25. November 29Project presentation: Varsha
  26. December 1 Project presentations: Sebastien and Gatis
  27. December 6 Project presentations Madhur and Anand
  28. December 8 Project presentations Costis and Alexandra



Extra notes: old notes on probability

Some excellent survey papers:

final projects

Choose one or two related papers. Write a report and give a 40 minutes presentation at the end of the semester. Choose your paper(s) by November 3.

Pseudorandomness against low-degree polynomials

Pseudorandomness against nondeterministic adversaries

Derandomization versus lower bounds

Pseudorandomness and average-case complexity in the uniform setting

Error-correcting codes from extractors


Extractors for bit-fixing sources

Extractors for a constant number of independent sources


More on Reingold's algorithm

related courses

Since Oct 27, 2005