Basic Information

Course Description

There are several algorithmic problems for which we know very efficient randomized algorithms (algorithms which toss pure unbiased coins during its execution and uses the outcome, for its computation) but we do not know deterministic efficient algorithms. Hence it is an important task to explore methods of "derandomizing" randomized algorithms. An important technique for which is what is called the "pseudorandomness". This also has close connections to explicitly constructing several combinatorial objects - hash functions, expander graphs, linear codes, extractors, dispersers and finally what are called the pseudorandom generators etc. ... all of which have the following common feature - if we choose a random one among the underlying objects of each type they satisfy nice properties (that we want for our application in derandomization) with high probability. However, we do not know how to deterministically efficiently construct many of them.

Course Syllabus

• Probability Toolkit Review:
  Linearity of Expectation Applications of Markov's Inequality, Stronger tail inequalities. Chebyshev's inequality, Chernoff-Hoeffding Bounds and applications. Martingales and applications. Azuma-Hoeffding inequality. Lovasz Local Lemma. Entropy Method.
• Construction of Pseudo-random Objects:
  Construction of d-wise independent sample spaces, Method of conditional probabilities. Construction of expanders, extractors, dispersers, condensers, error correcting codees. Basic codes and constructions, Limits on Performance of Codes. Algebraic (unique) decoding, Algebraic (list) decoding. Applications in Algorithms, Data structures, and complexity theory.
• Fourier Transforms and Applications : Fourier analysis on the Boolean cube and constant-depth circuits. Applications to Learning and Psuedorandomness

Pre-requisites

The course will build on ideas from the standard algorithms course and discrete mathematics course at the undergraduate level. Basic exposure to probability theory and linear algebra (matrix theory, determinant) is also a requirement.