The Cortona Lectures on Pseudorandomness and Combinatorial Constructions

A series of 11 lectures on pseudorandomness, derandomization, average-case complexity, and the explicit constructions of expanders and other combinatorial objects.

The lectures will be given in Cortona, Italy, July 18-29, 2005. Notes will be posted.

Summary. 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.

In this two-weeks couse we will begin by reviewing some examples of randomized algorithms (checking polynomial identities, random walks on graphs) and of probabilistic constructions (Ramsey graphs and expander graphs) and we will see a first instantiation of the hardness-versus-approach: the Blum-Micali-Yao construction of pseudorandom generators from "one-way" permutations. We will then see the Nisan-Wigderson construction of a pseudorandom generator under considerably weaker complexity assumption, and then show how to further weaken those assumptions by proving a connection between the average-case complexity and the worst-case complexity of certain problems. Moving on to combinatorial constructions, we will define randomnness extractors, discuss their relation to expander graphs, and give a construction of randomness extractors based on the Nisan-Wigderson pseudorandom generator construction. Time permitting, we will see the zig-zag product approach to the construction of expanders and how this is used back in complexity theory to give constructions of pseudorandom walks on graphs and to show how to do "depth-first search without the stack" in Reingold's algorithm.

schedule of classes

Subject to change

  1. July 18 Introduction
    The power of randomness: primality testing, random walks, Ramsey graphs.
    Reference: notes (to be posted)
  2. July 19 Introduction
    Basic complexity definitions. Statement of main results Definition of indistinguishability and pseudorandom generator. Use of pseudorandom generators in derandomization.
    Reference: notes (to be posted)
  3. July 20 The Blum-Micali-Yao Generator
    Statement of Goldreich-Levin. A generator with one-bit stretch. Generators with larger stretch.
    Reference: notes (to be posted)
  4. July 21 The Nisan-Wigderson Generator
    Construction assuming average-case complexity.
    References: notes (to be posted)
    See also: IAS Notes, Lecture 3
  5. July 22 Worst-Case to Average-Case
    Connection with coding theory. Statement of main results.
    References: notes (to be posted)
    See also: IAS Notes, Lecture 2
  6. July 23 Worst-Case to Average-Case
    Proof of some basic results.
    References: notes (to be posted)
    See also: 2002 Berkeley Notes, Chapter 10
  7. July 25 Randomness Extractors
    Definition, motivations, applications. Construction using Nisan-Wigderson
    References: notes (to be posted)
    See also: IAS Notes, Lecture 4
  8. July 26 Randomness Extractors and Expander Graphs
    Analysis of the construction based on Nisan-Wigderson. Improvements and connections with expander graphs
    References: notes (to be posted)
    See also: IAS Notes, Lecture 4, and the original paper
  9. July 27 Expander Graphs
    Alternative definitions. Eigenvalues and random walks.
    References: notes (to be posted)
  10. July 28 The Zig-Zag Graph Product
    References: notes (to be posted)
    See also the original paper
  11. July 29 Reingold's Theorem
    References: notes (to be posted)
    See also the original paper
Extra notes: old notes on probability

Some excellent survey papers:

related courses