Preamble
Randomness is often used to prove the existence of combinatorial objects with a desired property. Examples of such objects include - good codes (which finds applications in theoretical computer science and communications), graphs which achieves good connectivity properties but with very few edges (which finds applications in networks and theoretical computer science), algorithms that "extract" pure random bits from a source of impure random bits, algorithms that generate "pure looking" random bits from biased random bits.
Here is a strategy for proving existence of such objects : if one can show that a randomly chosen object has the property with nonzero probability, then it follows that such an object must, in fact, exist. Interestingly, in many situations, the randomly chosen object has the desired property with high probability (not just nonzero). This course will focus on such "pseudo-random" objects. In many applications in computer science, it is essential that we have a deterministic construction of such objects. So how do we derandomize these constructions? This will be one of the main points of focus in the course.
The study of pseudorandom objects and their derandomization has also provided us with a wide toolkit of techniques that have found applications in different areas of theoretical computer science.​ ​This course also aims to provide an introduction to these techniques.​
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
