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
September 13 Formal definitions of computational
indistinguishability, pseudorandom generators, one-way permutation and
[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
[Notes scribed by Ben]