1;95;0c## CS761: Derandomization and Pseudorandomness (2022-23 Sem I)
Course Contents
The course is about trying to understand randomness and its role in computer science, specifically in design of algorithms. There are settings like cryptography, distributed computing, communication complexity where randomness is known to play a essential role. In algorithm design, use of randomness often leads to elegant, simple, and fast algorithms. However, it is unclear whether use of randomness allows us to design efficient algorithms for a strictly larger class of problems as compared to that without using randomness. It is commonly believed that the answer is no. That is, every problem with an efficient randomized algorithm is believed to have an efficient algorithm without randomization. The course will cover various kinds of settings where randomization is used and
will introduce fundamental techniques which enables one to do away with randomness. Randomness will be viewed as a resource and we will deal with its tradeoff with other resources like -- time, space, communication etc.
We plan to cover the following topics.
Randomized complexity classes like BPP, RP, RL and their relation with other classes
Pairwise independence and applications. Boosting success probability of an algorithm. Hashing.
Problems with some elegant randomized algorithms like primality testing, bipartite matching, connectivity of a graph, polynomial identity testing, minimum cut. Derandomization of these algorithms.
Random walks, expander graphs and applications.
Connection of pseudorandomness with computational hardness. Pseudorandom generators.
Small bias spaces. Pseudorandomness for small space computation. Deterministic identity testing for special classes of polynomials.
Pre-requisites: You are expected to know basics of algorithms (CS218/CS601), linear algebra, graph theory, finite fields.
Course Meetings: Mon, Thu 19:00-20:55 (SIC 201)
Lectures
Lecture 1 pdf tex: Freivald's randomized algorithm for verifying matrix multiplication; Reducing randomness.
Ref: Motwani Raghavan Section 7.1
Lecture 2: Finite fields, GF(p), degree d polynomial has at most d roots.
Reference
Lecture 3 pdf tex: Max cut 2-approximation algorithm and its derandomization via pairwise independence.
Ref: Vadhan section 3.5
Lecture 4 pdf tex: Algebraic construction of k-wise independence. Lower bound on number of random bits.
Ref: Vadhan section 3.5.5
Lecture 5 pdf tex: Estimating number of distinct items in a stream using pairwise independence.
Reference
Lecture 6 pdf tex: Expander graphs, error correcting codes, probability amplification
Ref: Chapter 1, Hoory, Linial, and Wigderson. See this video for bounds on binomial coefficients.
Lecture 7 pdf tex: Codes from magical graphs. Undirected connectivity, small space algorithms.
Ref: Vadhan Section 2.5
Lecture 8: Undirected connectivity in RL (randomized logspace).
Ref: Vadhan Section 2.5
Lecture 9 pdf tex: Expander graphs, combinatorial and spectral defintions and connections
Ref: Vadhan Chapter 4
Lecture 10 pdf tex: Zig-zag product, construction of large expanders, connectivity in logspace.
Ref: Vadhan Chapter 4
Lecture 14 pdf tex: Multiplicity codes, list decoding close to distance.
Lecture 13 pdf tex: Complexity classes BPP, RP. Pseudorandom generators.
Lecture 15 pdf tex: Towards a pseudorandom generator. Unpredictibility implies indistinguishability.
Lecture 16 pdf tex: Nisan-Wigderson PRG from hard on average functions.
Ref (Lecture 13, 15, 16): Arora Barak Chapter 20
Lecture 17 pdf tex: From worst-case to average-case hardness.
Lecture 19 pdf tex: Concatanation of codes. Walsh-Hadmard local decoding. Yao's XOR lemma.
Ref (Lecture 17, 18, 19): Arora Barak Chapter 19
Lecture 20 pdf tex: Randomized parallel algorithms for bipartite matching
Lecture 21 pdf tex: Towards derandomizing the isolation lemma for bipartite matching
Presentation topics
epsilon-biased spaces and almost k-wise indepndence Alon Goldreich Hastad Peralta
Pseudorandom geenrators for space-bounded computation Nisan
Pseudorandomness for DNFs from k-wise independence Razborov
An elementary construction of expanders Alon Schwartz Shapira
Hashing Fredman Komlos Szemeredi
References
Rajeev Motwani and Prabhakar Raghavan, Randomized algorithms
Salil Vadhan's lecture notes and survey on pseudorandomness
Michael Luby and Avi Wigderson, Pairwise independence and derandomization
Sanjeev Arora and Boaz Barak, Computational complexity: a modern approach
Shlomo Hoory, Nathan Linial and Avi Wigderson Expander graphs and their applications