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:
Computational definition of pseudorandomness
Achieving pseudorandomness against simple adversaries: pairwise indepent
generators; epsilon-biased generators; almost k-wise independent generators.
Connection with error-correcting codes.
Cryptographically strong pseudorandom generators: the Blum-Micali-Yao
construction, the Goldreich-Levin theorem, the coding-theoretic and Fourier-analytic
interpretations of the Goldreich-Levin theorem.
Pseudorandom generators for derandomization: the Nisan-Wigderson generator
and the Impagliazzo-Wigderson worst-case to average case reduction. Another
coding-theoretic connection,
Randomness extractors from the Nisan-Wigderson generator and from other
coding-theoretic constructions.
Extractors, hash functions, Nisan's pseudorandom generator and Nisan-Zuckerman pseudorandom generator
for space-bounded computation.
Seedless extractors and applications of additive number theory
Composition of extractors, extractors for high min-entropy
Expander graphs, random walks, eigenvalues
Simple constructions of expander with super-constant degree
Construction of expanders using the Zig-Zag graph product
Reingold's theorem
schedule of classes
Macros for lecture notes: macros.tex contains the
macros and lecture0.tex shows how to use some
features.
August 30 Introduction. Pairwise independent generator
[Notes not available]
see: [Oded Goldreich. Pseudorandomness.
Survey paper, 2000] for definitions and examples
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]
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.
September 15 Construction of a pseudorandom generator using a
hard-core predicate
[Notes scribed by Ben]
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]
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]
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]