CS6845 Pseudorandomness

Jan - May 2018

Details

  • Where: CS26
  • When: A slot; Mon(8-8.50am), Tue(12-12.50pm), Thu(11-11.50am), Fri(10-10.50am)
  • TA: Krishnamoorthy Dinesh (ACT Lab, kdinesh@cse)

Objectives

The objective of this course is to understand the concept of pseudorandomness and its use in derandomizing algorithms. Various examples of pseudorandom objects like expander graphs, error-correcting codes as well as their application in different areas of theoretical computer science will be studied. The study of pseudorandomness has provided a rich toolkit of techniques that have wide applications in theoretical computer science. This course aims to provide an introduction these techniques as well.

Contents

  • Basic probabilistic method - Introduction to the probabilistic method, first moment and second moment methods, Markov’s and Chebyshev’s inequality with applications, concentration of measure, Chernoff bounds, applications to error reduction, Lovasz local lemma and applications.
  • Basic derandomization techniques - Method of conditional probabilities and pessimistic estimators, Pairwise independent hash families, and introduction to expanders.
  • Expander graphs and applications - Vertex expansion, edge expansion and spectral expansion - relationship between the various notions of expansion, expander mixing lemma, analysis of random walks on expanders, examples of explicit families of expander graphs and constructions, Zig-zag product of graphs and explicit constructions of expanders, application of the zig-zag product for derandomization - undirected reachability in Logspace. Lossless expanders, extractors and their constructions.
  • Error-correcting codes - Shannon’s channel coding theorems and proofs, notion of distance and rate of a code, linear codes, dual codes, Singleton bound. Reed-Solomon codes, unique decoding, list decoding and applications. Locally decodable codes and applications. Local list decoding, Goldreich-Levin theorem and applications.
  • Fourier analytic methods - Introduction to Fourier analysis and Fourier analytic proof of Goldreich-levin theorem, small-bias spaces - constructions, analysis and applications in derandomization.

References

We will cover the course material from a variety of sources. The references for each lecture will be mentioned in class. The following are some of the reference material that we will use. During the course additional material may get added.

Grading policy

  • Assignments: 20%
  • Course project: 15%
  • Quiz 1(Feb 19, 2018): 15%
  • Quiz 2(Apr 2, 2018): 15%
  • Final exam(May 1, 2018): 35%

Course Materials