CS6845 - Pseudorandomness

Course Data :

Course Objectives:

The aim is to help the students to gain the ability to use some of the modern tools and techniques used to address and analyse problems that one comes across while doing research in theoretical computer science. The techniques that we intend to touch upon can easily fill up a full course each on their own, but the main objective is to give exposure to the basic ideas involved.

Syllabus

  • Probabilistic Method: Linearity of Expectation Applications of Markov's Inequality, universal traversal sequences. Second moments, Chebyshev's inequality, Chernoff Bounds and applications. Martingales and Azuma's inequality. Lovasz Local Lemma - applications to ramsey number lower bounds, and material from alon and spencer.
  • Essential Coding Theory : Basic codes and constructions, Limits on Performance of Codes, Algebraic (unique) decoding, Algebraic (list) decoding, Applications in Algorithms, Data structures, and complexity theory.
  • Tools for derandomization Construction of d-wise independent sample spaces, Method of conditional probabilities. Construction of extractors, even suboptimal ones, but main thing is to motivate the constructions.
  • Fourier Transforms and Applications : Fourier Transforms and fast fourier transforms. Computing fast fourier transforms. Applications to Integer Multiplications. Fourier analysis on the Boolean cube and constant-depth circuits. Applications to Learning, Derandomization and Property Testing.

References

Course Pre-requisites:

The real pre-requisite is just mathematical maturity and an appreciation towards formal and analytical methods. This course will build on the framework provided by CS6030 (Mathematical Concepts for Computer Science), CS6014 (Advanced Theory of Computation) and CS5800 (Advanced Data Structures and Algorithms).

Course Update History

  • Jan 2012 - Introduced.
  • Mar 2016 - Title Updated

Pre-Requisites

    None

Parameters

Credits Type Date of Introduction
4-0-0-0-8-12 Elective Jan 2012

Previous Instances of the Course


© 2016 - All Rights Reserved - Dept of CSE, IIT Madras
Website Credits